# -*- coding: utf-8 -*-
"""Connectivity-Based Outlier Factor (COF) Algorithm
"""
# Author: Yahya Almardeny <almardeny@gmail.com>, Roel Bouman <roel.bouman@ru.nl> (memory efficient COF)
# License: BSD 2 clause

from __future__ import division
from __future__ import print_function

import warnings
from operator import itemgetter

import numpy as np
from scipy.spatial import distance_matrix
from scipy.spatial import minkowski_distance
from sklearn.utils import check_array

from .base import BaseDetector
from ..utils.utility import check_parameter


class COF(BaseDetector):
    """Connectivity-Based Outlier Factor (COF) COF uses the ratio of average
    chaining distance of data point and the average of average chaining
    distance of k nearest neighbor of the data point, as the outlier score
    for observations.

    See :cite:`tang2002enhancing` for details.
    
    Two version of COF are supported:

    - Fast COF: computes the entire pairwise distance matrix at the cost of a
      O(n^2) memory requirement.
    - Memory efficient COF: calculates pairwise distances incrementally.
      Use this implementation when it is not feasible to fit the n-by-n 
      distance in memory. This leads to a linear overhead because many 
      distances will have to be recalculated.

    Parameters
    ----------
    contamination : float in (0., 0.5), optional (default=0.1)
        The amount of contamination of the data set, i.e.
        the proportion of outliers in the data set. Used when fitting to
        define the threshold on the decision function.

    n_neighbors : int, optional (default=20)
        Number of neighbors to use by default for k neighbors queries.
        Note that n_neighbors should be less than the number of samples.
        If n_neighbors is larger than the number of samples provided,
        all samples will be used.
        
    method : string, optional (default='fast')
        Valid values for method are:
            
        - 'fast' Fast COF, computes the full pairwise distance matrix up front.
        - 'memory' Memory-efficient COF, computes pairwise distances only when
          needed at the cost of computational speed.

    Attributes
    ----------
    decision_scores_ : numpy array of shape (n_samples,)
        The outlier scores of the training data.
        The higher, the more abnormal. Outliers tend to have higher
        scores. This value is available once the detector is
        fitted.

    threshold_ : float
        The threshold is based on ``contamination``. It is the
        ``n_samples * contamination`` most abnormal samples in
        ``decision_scores_``. The threshold is calculated for generating
        binary outlier labels.

    labels_ : int, either 0 or 1
        The binary labels of the training data. 0 stands for inliers
        and 1 for outliers/anomalies. It is generated by applying
        ``threshold_`` on ``decision_scores_``.

    n_neighbors_: int
        Number of neighbors to use by default for k neighbors queries.
    """

    def __init__(self, contamination=0.1, n_neighbors=20, method="fast"):
        super(COF, self).__init__(contamination=contamination)
        if isinstance(n_neighbors, int):
            check_parameter(n_neighbors, low=1, param_name='n_neighbors')
        else:
            raise TypeError(
                "n_neighbors should be int. Got %s" % type(n_neighbors))
        self.n_neighbors = n_neighbors
        self.method = method

    def fit(self, X, y=None):
        """Fit detector. y is ignored in unsupervised methods.

        Parameters
        ----------
        X : numpy array of shape (n_samples, n_features)
            The input samples.

        y : Ignored
            Not used, present for API consistency by convention.

        Returns
        -------
        self : object
            Fitted estimator.
        """
        X = check_array(X)
        self.n_train_ = X.shape[0]
        self.n_neighbors_ = self.n_neighbors

        if self.n_neighbors_ >= self.n_train_:
            self.n_neighbors_ = self.n_train_ - 1
            warnings.warn(
                "n_neighbors is set to the number of training points "
                "minus 1: {0}".format(self.n_neighbors_))

            check_parameter(self.n_neighbors_, 1, self.n_train_,
                            include_left=True, include_right=True)

        self._set_n_classes(y)
        self.decision_scores_ = self.decision_function(X)
        self._process_decision_scores()

        return self

    def decision_function(self, X):
        """Predict raw anomaly score of X using the fitted detector.
        The anomaly score of an input sample is computed based on different
        detector algorithms. For consistency, outliers are assigned with
        larger anomaly scores.

        Parameters
        ----------
        X : numpy array of shape (n_samples, n_features)
            The training input samples. Sparse matrices are accepted only
            if they are supported by the base estimator.

        Returns
        -------
        anomaly_scores : numpy array of shape (n_samples,)
            The anomaly score of the input samples.
        """
        if self.method.lower() == "fast":
            return self._cof_fast(X)
        elif self.method.lower() == "memory":
            return self._cof_memory(X)
        else:
            raise ValueError("method should be set to either \'fast\' or \'memory\'. Got %s" % self.method)

    def _cof_memory(self, X):
        """
        Connectivity-Based Outlier Factor (COF) Algorithm
        This function is called internally to calculate the
        Connectivity-Based Outlier Factor (COF) as an outlier
        score for observations.
        This function uses a memory efficient implementation at the cost of 
        speed.
        :return: numpy array containing COF scores for observations.
                 The greater the COF, the greater the outlierness.
        """
        #dist_matrix = np.array(distance_matrix(X, X))
        sbn_path_index = np.zeros((X.shape[0],self.n_neighbors_), dtype=np.int64)
        ac_dist, cof_ = np.zeros((X.shape[0])), np.zeros((X.shape[0]))
        for i in range(X.shape[0]):
            #sbn_path = np.argsort(dist_matrix[i])
            sbn_path = np.argsort(minkowski_distance(X[i,:],X,p=2))
            sbn_path_index[i,:] = sbn_path[1: self.n_neighbors_ + 1]
            cost_desc = np.zeros((self.n_neighbors_))
            for j in range(self.n_neighbors_):
                #cost_desc.append(
                #    np.min(dist_matrix[sbn_path[j + 1]][sbn_path][:j + 1]))
                cost_desc[j] = np.min(minkowski_distance(X[sbn_path[j + 1]],X,p=2)[sbn_path][:j + 1])
            acd = np.zeros((self.n_neighbors_))
            for _h, cost_ in enumerate(cost_desc):
                neighbor_add1 = self.n_neighbors_ + 1
                acd[_h] = ((2. * (neighbor_add1 - (_h + 1))) / (neighbor_add1 * self.n_neighbors_)) * cost_
            ac_dist[i] = np.sum(acd)
        for _g in range(X.shape[0]):
            cof_[_g] = (ac_dist[_g] * self.n_neighbors_) / np.sum(ac_dist[sbn_path_index[_g]])
        return np.nan_to_num(cof_)
    
    def _cof_fast(self, X):
        """
        Connectivity-Based Outlier Factor (COF) Algorithm
        This function is called internally to calculate the
        Connectivity-Based Outlier Factor (COF) as an outlier
        score for observations.
        This function uses a fast implementation at the cost of memory.
        :return: numpy array containing COF scores for observations.
                 The greater the COF, the greater the outlierness.
        """
        dist_matrix = np.array(distance_matrix(X, X))
        sbn_path_index, ac_dist, cof_ = [], [], []
        for i in range(X.shape[0]):
            sbn_path = np.argsort(dist_matrix[i])
            sbn_path_index.append(sbn_path[1: self.n_neighbors_ + 1])
            cost_desc = []
            for j in range(self.n_neighbors_):
                cost_desc.append(
                    np.min(dist_matrix[sbn_path[j + 1]][sbn_path][:j + 1]))
            acd = []
            for _h, cost_ in enumerate(cost_desc):
                neighbor_add1 = self.n_neighbors_ + 1
                acd.append(((2. * (neighbor_add1 - (_h + 1))) / (
                        neighbor_add1 * self.n_neighbors_)) * cost_)
            ac_dist.append(np.sum(acd))
        for _g in range(X.shape[0]):
            cof_.append((ac_dist[_g] * self.n_neighbors_) /
                        np.sum(itemgetter(*sbn_path_index[_g])(ac_dist)))
        return np.nan_to_num(cof_)
