cftree.py

"""!

@brief Data Structure: CF-Tree
@details Implementation based on paper @cite article::birch::1.

@authors Andrei Novikov (pyclustering@yandex.ru)
@date 2014-2019
@copyright GNU Public License

@cond GNU_PUBLIC_LICENSE
    PyClustering is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    
    PyClustering is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
@endcond

"""

from copy import copy

from pyclustering.cluster import cluster_visualizer

from pyclustering.utils import euclidean_distance_square
from pyclustering.utils import manhattan_distance
from pyclustering.utils import list_math_addition, list_math_subtraction, list_math_multiplication
from pyclustering.utils import linear_sum, square_sum

from enum import IntEnum


class measurement_type(IntEnum):
    """!
    @brief Enumeration of measurement types for CF-Tree.
    
    @see cftree
    
    """
    
    
    CENTROID_EUCLIDEAN_DISTANCE = 0
    
    
    CENTROID_MANHATTAN_DISTANCE = 1
    
    
    AVERAGE_INTER_CLUSTER_DISTANCE = 2
    
    
    AVERAGE_INTRA_CLUSTER_DISTANCE = 3
    
    
    VARIANCE_INCREASE_DISTANCE = 4


class cfnode_type(IntEnum):
    """!
    @brief Enumeration of CF-Node types that are used by CF-Tree.
    
    @see cfnode
    @see cftree
    
    """
    
    
    CFNODE_DUMMY = 0
    
    
    CFNODE_LEAF = 1
    
    
    CFNODE_NONLEAF = 2


class cfentry:
    """!
    @brief Clustering feature representation.
    
    @see cfnode
    @see cftree
    
    """
    
    @property
    def number_points(self):
        """!
        @brief Returns number of points that are encoded.
        
        @return (uint) Number of encoded points.
        
        """
        return self.__number_points
    
    @property
    def linear_sum(self):
        """!
        @brief Returns linear sum.
        
        @return (list) Linear sum.
        
        """
        
        return self.__linear_sum
    
    @property
    def square_sum(self):
        """!
        @brief Returns square sum.
        
        @return (double) Square sum.
        
        """
        return self.__square_sum
    
    
    def __init__(self, number_points, linear_sum, square_sum):
        """!
        @brief CF-entry constructor.
        
        @param[in] number_points (uint): Number of objects that is represented by the entry.
        @param[in] linear_sum (list): Linear sum of values that represent objects in each dimension.
        @param[in] square_sum (double): Square sum of values that represent objects.
        
        """
        
        self.__number_points = number_points
        self.__linear_sum = linear_sum
        self.__square_sum = square_sum
        
        self.__centroid = None
        self.__radius = None
        self.__diameter = None
    
    
    def __copy__(self):
        """!
        @returns (cfentry) Makes copy of the cfentry instance.
        
        """
        return cfentry(self.__number_points, self.__linear_sum, self.__square_sum)
    
    
    def __repr__(self):
        """!
        @return (string) Default cfentry representation.
        
        """
        return 'CF (%s, %s, %0.2f) [%s]' % (self.number_points, self.linear_sum, self.__square_sum, hex(id(self)))
    
    
    def __str__(self):
        """!
        @brief Default cfentry string representation.
        
        """
        return self.__repr__()
    
    
    def __add__(self, entry):
        """!
        @brief Overloaded operator add. Performs addition of two clustering features.
        
        @param[in] entry (cfentry): Entry that is added to the current.
        
        @return (cfentry) Result of addition of two clustering features.
        
        """
        
        number_points = self.number_points + entry.number_points
        result_linear_sum = list_math_addition(self.linear_sum, entry.linear_sum)
        result_square_sum = self.square_sum + entry.square_sum
        
        return cfentry(number_points, result_linear_sum, result_square_sum)
    
    
    def __sub__(self, entry):
        """!
        @brief Overloaded operator sub. Performs substraction of two clustering features.
        @details Substraction can't be performed with clustering feature whose description is less then substractor.
        
        @param[in] entry (cfentry): Entry that is substracted from the current.
        
        @return (cfentry) Result of substraction of two clustering features.
        
        """
                
        number_points = self.number_points - entry.number_points
        result_linear_sum = list_math_subtraction(self.linear_sum, entry.linear_sum)
        result_square_sum = self.square_sum - entry.square_sum
        
        if (number_points < 0) or (result_square_sum < 0):
            raise NameError("Substruction with negative result is not possible for clustering features.")
        
        return cfentry(number_points, result_linear_sum, result_square_sum)
    
    
    def __eq__(self, entry):
        """!
        @brief Overloaded operator eq. 
        @details Performs comparison of two clustering features.
        
        @param[in] entry (cfentry): Entry that is used for comparison with current.
        
        @return (bool) True is both clustering features are equals in line with tolerance, otherwise False.
        
        """
                
        tolerance = 0.00001
        
        result = (self.__number_points == entry.number_points)
        result &= ((self.square_sum + tolerance > entry.square_sum) and (self.square_sum - tolerance < entry.square_sum))
        
        for index_dimension in range(0, len(self.linear_sum)):
            result &= ((self.linear_sum[index_dimension] + tolerance > entry.linear_sum[index_dimension]) and (self.linear_sum[index_dimension] - tolerance < entry.linear_sum[index_dimension]))
        
        return result
    
    
    def get_distance(self, entry, type_measurement):
        """!
        @brief Calculates distance between two clusters in line with measurement type.
        
        @details In case of usage CENTROID_EUCLIDIAN_DISTANCE square euclidian distance will be returned.
                 Square root should be taken from the result for obtaining real euclidian distance between
                 entries. 
        
        @param[in] entry (cfentry): Clustering feature to which distance should be obtained.
        @param[in] type_measurement (measurement_type): Distance measurement algorithm between two clusters.
        
        @return (double) Distance between two clusters.
        
        """
        
        if type_measurement is measurement_type.CENTROID_EUCLIDEAN_DISTANCE:
            return euclidean_distance_square(entry.get_centroid(), self.get_centroid())
        
        elif type_measurement is measurement_type.CENTROID_MANHATTAN_DISTANCE:
            return manhattan_distance(entry.get_centroid(), self.get_centroid())
        
        elif type_measurement is measurement_type.AVERAGE_INTER_CLUSTER_DISTANCE:
            return self.__get_average_inter_cluster_distance(entry)
            
        elif type_measurement is measurement_type.AVERAGE_INTRA_CLUSTER_DISTANCE:
            return self.__get_average_intra_cluster_distance(entry)
        
        elif type_measurement is measurement_type.VARIANCE_INCREASE_DISTANCE:
            return self.__get_variance_increase_distance(entry)

        else:
            raise ValueError("Unsupported type of measurement '%s' is specified." % type_measurement)
    
        
    def get_centroid(self):
        """!
        @brief Calculates centroid of cluster that is represented by the entry. 
        @details It's calculated once when it's requested after the last changes.
        
        @return (list) Centroid of cluster that is represented by the entry.
        
        """
        
        if self.__centroid is not None:
            return self.__centroid
        
        self.__centroid = [0] * len(self.linear_sum)
        for index_dimension in range(0, len(self.linear_sum)):
            self.__centroid[index_dimension] = self.linear_sum[index_dimension] / self.number_points
        
        return self.__centroid
    
    
    def get_radius(self):
        """!
        @brief Calculates radius of cluster that is represented by the entry.
        @details It's calculated once when it's requested after the last changes.
        
        @return (double) Radius of cluster that is represented by the entry.
        
        """
        
        if self.__radius is not None:
            return self.__radius
        
        centroid = self.get_centroid()
        
        radius_part_1 = self.square_sum
        
        if type(centroid) == list:
            radius_part_2 = 2.0 * sum(list_math_multiplication(self.linear_sum, centroid))
            radius_part_3 = self.number_points * sum(list_math_multiplication(centroid, centroid))
        else:
            radius_part_2 = 2.0 * self.linear_sum * centroid
            radius_part_3 = self.number_points * centroid * centroid
        
        self.__radius = ((1.0 / self.number_points) * (radius_part_1 - radius_part_2 + radius_part_3)) ** 0.5
        return self.__radius
        
    
    def get_diameter(self):
        """!
        @brief Calculates diameter of cluster that is represented by the entry.
        @details It's calculated once when it's requested after the last changes.
        
        @return (double) Diameter of cluster that is represented by the entry.
        
        """
        
        if self.__diameter is not None:
            return self.__diameter

        if type(self.linear_sum) == list:
            diameter_part = self.square_sum * self.number_points - 2.0 * sum(list_math_multiplication(self.linear_sum, self.linear_sum)) + self.square_sum * self.number_points
        else:
            diameter_part = self.square_sum * self.number_points - 2.0 * self.linear_sum * self.linear_sum + self.square_sum * self.number_points
            
        self.__diameter = (diameter_part / (self.number_points * (self.number_points - 1))) ** 0.5
        return self.__diameter
    
        
    def __get_average_inter_cluster_distance(self, entry):
        """!
        @brief Calculates average inter cluster distance between current and specified clusters.
        
        @param[in] entry (cfentry): Clustering feature to which distance should be obtained.
        
        @return (double) Average inter cluster distance.
        
        """
        
        linear_part_distance = sum(list_math_multiplication(self.linear_sum, entry.linear_sum))
        
        return ((entry.number_points * self.square_sum - 2.0 * linear_part_distance + self.number_points * entry.square_sum) / (self.number_points * entry.number_points)) ** 0.5
    
    
    def __get_average_intra_cluster_distance(self, entry):
        """!
        @brief Calculates average intra cluster distance between current and specified clusters.
        
        @param[in] entry (cfentry): Clustering feature to which distance should be obtained.
        
        @return (double) Average intra cluster distance.
        
        """
        
        linear_part_first = list_math_addition(self.linear_sum, entry.linear_sum)
        linear_part_second = linear_part_first
        
        linear_part_distance = sum(list_math_multiplication(linear_part_first, linear_part_second))
        
        general_part_distance = 2.0 * (self.number_points + entry.number_points) * (self.square_sum + entry.square_sum) - 2.0 * linear_part_distance
        
        return (general_part_distance / ((self.number_points + entry.number_points) * (self.number_points + entry.number_points - 1.0))) ** 0.5
    
    
    def __get_variance_increase_distance(self, entry):
        """!
        @brief Calculates variance increase distance between current and specified clusters.
        
        @param[in] entry (cfentry): Clustering feature to which distance should be obtained.
        
        @return (double) Variance increase distance.
        
        """
                
        linear_part_12 = list_math_addition(self.linear_sum, entry.linear_sum)
        variance_part_first = (self.square_sum + entry.square_sum) - \
            2.0 * sum(list_math_multiplication(linear_part_12, linear_part_12)) / (self.number_points + entry.number_points) + \
            (self.number_points + entry.number_points) * sum(list_math_multiplication(linear_part_12, linear_part_12)) / (self.number_points + entry.number_points)**2.0
        
        linear_part_11 = sum(list_math_multiplication(self.linear_sum, self.linear_sum))
        variance_part_second = -(self.square_sum - (2.0 * linear_part_11 / self.number_points) + (linear_part_11 / self.number_points))
        
        linear_part_22 = sum(list_math_multiplication(entry.linear_sum, entry.linear_sum))
        variance_part_third = -(entry.square_sum - (2.0 / entry.number_points) * linear_part_22 + entry.number_points * (1.0 / entry.number_points ** 2.0) * linear_part_22)

        return variance_part_first + variance_part_second + variance_part_third
        

class cfnode:
    """!
    @brief Representation of node of CF-Tree.
    
    """
    
    def __init__(self, feature, parent, payload):
        """!
        @brief Constructor of abstract CF node.
        
        @param[in] feature (cfentry): Clustering feature of the created node.
        @param[in] parent (cfnode): Parent of the created node.
        @param[in] payload (*): Data that is stored by the node.
        
        """
        
        
        self.feature = copy(feature)

        
        self.parent = parent
        
        
        self.type = cfnode_type.CFNODE_DUMMY
        
        
        self.payload = payload
    
    
    def __repr__(self):
        """!
        @return (string) Default representation of CF node.
        
        """
        
        return 'CF node %s, parent %s, feature %s' % (hex(id(self)), self.parent, self.feature)


    def __str__(self):
        """!
        @return (string) String representation of CF node.
        
        """
        return self.__repr__()
    
    
    def get_distance(self, node, type_measurement):
        """!
        @brief Calculates distance between nodes in line with specified type measurement.
        
        @param[in] node (cfnode): CF-node that is used for calculation distance to the current node.
        @param[in] type_measurement (measurement_type): Measurement type that is used for calculation distance.
        
        @return (double) Distance between two nodes.
        
        """
        
        return self.feature.get_distance(node.feature, type_measurement)
    

class non_leaf_node(cfnode):
    """!
    @brief Representation of clustering feature non-leaf node.
    
    """ 
    
    @property
    def successors(self):
        """!
        @return (list) List of successors of the node.
        
        """
        return self.__successors
    
    
    def __init__(self, feature, parent, successors, payload):
        """!
        @brief Create CF Non-leaf node.
        
        @param[in] feature (cfentry): Clustering feature of the created node.
        @param[in] parent (non_leaf_node): Parent of the created node.
        @param[in] successors (list): List of successors of the node.
        @param[in] payload (*): Data that is stored by the node.
        
        """
                
        super().__init__(feature, parent, payload)
        
        
        self.type = cfnode_type.CFNODE_NONLEAF
        
        self.__successors = successors
    
    
    def __repr__(self):
        """!
        @return (string) Representation of non-leaf node representation.
        
        """   
        return 'Non-leaf node %s, parent %s, feature %s, successors: %d' % (hex(id(self)), self.parent, self.feature, len(self.successors))
    
    
    def __str__(self):
        """!
        @return (string) String non-leaf representation.
        
        """
        return self.__repr__()
    
    
    def insert_successor(self, successor):
        """!
        @brief Insert successor to the node.
        
        @param[in] successor (cfnode): Successor for adding.
        
        """
        
        self.feature += successor.feature
        self.successors.append(successor)
        
        successor.parent = self
    
    
    def remove_successor(self, successor):
        """!
        @brief Remove successor from the node.
        
        @param[in] successor (cfnode): Successor for removing.
        
        """
        
        self.feature -= successor.feature
        self.successors.append(successor)
        
        successor.parent = self
    
    
    def merge(self, node):
        """!
        @brief Merge non-leaf node to the current.
        
        @param[in] node (non_leaf_node): Non-leaf node that should be merged with current.
        
        """
                
        self.feature += node.feature
        
        for child in node.successors:
            child.parent = self
            self.successors.append(child)
    
    
    def get_farthest_successors(self, type_measurement):
        """!
        @brief Find pair of farthest successors of the node in line with measurement type.
        
        @param[in] type_measurement (measurement_type): Measurement type that is used for obtaining farthest successors.
        
        @return (list) Pair of farthest successors represented by list [cfnode1, cfnode2].
        
        """
        
        farthest_node1 = None
        farthest_node2 = None
        farthest_distance = 0.0
        
        for i in range(0, len(self.successors)):
            candidate1 = self.successors[i]
            
            for j in range(i + 1, len(self.successors)):
                candidate2 = self.successors[j]
                candidate_distance = candidate1.get_distance(candidate2, type_measurement)
                
                if candidate_distance > farthest_distance:
                    farthest_distance = candidate_distance
                    farthest_node1 = candidate1
                    farthest_node2 = candidate2
        
                    return [farthest_node1, farthest_node2]
    
    
    def get_nearest_successors(self, type_measurement):
        """!
        @brief Find pair of nearest successors of the node in line with measurement type.
        
        @param[in] type_measurement (measurement_type): Measurement type that is used for obtaining nearest successors.
        
        @return (list) Pair of nearest successors represented by list.
        
        """
                
        nearest_node1 = None
        nearest_node2 = None
        nearest_distance = float("Inf")
        
        for i in range(0, len(self.successors)):
            candidate1 = self.successors[i]
            
            for j in range(i + 1, len(self.successors)):
                candidate2 = self.successors[j]
                candidate_distance = candidate1.get_distance(candidate2, type_measurement)
                
                if candidate_distance < nearest_distance:
                    nearest_distance = candidate_distance
                    nearest_node1 = candidate1
                    nearest_node2 = candidate2
        
                return [nearest_node1, nearest_node2]


class leaf_node(cfnode):
    """!
    @brief Represents clustering feature leaf node.
    
    """
    
    @property
    def entries(self):
        """!
        @return (list) List of leaf nodes.
        
        """
        return self.__entries
    
    
    def __init__(self, feature, parent, entries, payload):
        """!
        @brief Create CF Leaf node.
        
        @param[in] feature (cfentry): Clustering feature of the created node.
        @param[in] parent (non_leaf_node): Parent of the created node.
        @param[in] entries (list): List of entries of the node.
        @param[in] payload (*): Data that is stored by the node.
        
        """
        
        super().__init__(feature, parent, payload)
        
        
        self.type = cfnode_type.CFNODE_LEAF
        
        self.__entries = entries   # list of clustering features
        
    
    def __repr__(self):
        """!
        @return (string) Default leaf node represenation.
        
        """
        text_entries = "\n"
        for entry in self.entries:
            text_entries += "\t" + str(entry) + "\n"
        
        return 'Leaf-node %s, parent %s, feature %s, entries: %d %s' % (hex(id(self)), self.parent, self.feature, len(self.entries), text_entries)
    
    
    def __str__(self):
        """!
        @return (string) String leaf node representation.
        
        """
        return self.__repr__()
    
    
    def insert_entry(self, entry):
        """!
        @brief Insert new clustering feature to the leaf node.
        
        @param[in] entry (cfentry): Clustering feature.
        
        """

        self.feature += entry
        self.entries.append(entry)
        
    
    def remove_entry(self, entry):
        """!
        @brief Remove clustering feature from the leaf node.
        
        @param[in] entry (cfentry): Clustering feature.
        
        """

        self.feature -= entry
        self.entries.remove(entry)
    
    
    def merge(self, node):
        """!
        @brief Merge leaf node to the current.
        
        @param[in] node (leaf_node): Leaf node that should be merged with current.
        
        """
        
        self.feature += node.feature
        
        # Move entries from merged node
        for entry in node.entries:
            self.entries.append(entry)
            
    
    def get_farthest_entries(self, type_measurement):
        """!
        @brief Find pair of farthest entries of the node.
        
        @param[in] type_measurement (measurement_type): Measurement type that is used for obtaining farthest entries.
        
        @return (list) Pair of farthest entries of the node that are represented by list.
        
        """
        
        farthest_entity1 = None
        farthest_entity2 = None
        farthest_distance = 0
        
        for i in range(0, len(self.entries)):
            candidate1 = self.entries[i]
            
            for j in range(i + 1, len(self.entries)):
                candidate2 = self.entries[j]
                candidate_distance = candidate1.get_distance(candidate2, type_measurement)
                
                if candidate_distance > farthest_distance:
                    farthest_distance = candidate_distance
                    farthest_entity1 = candidate1
                    farthest_entity2 = candidate2
        
        return [farthest_entity1, farthest_entity2]
    
    
    def get_nearest_index_entry(self, entry, type_measurement):
        """!
        @brief Find nearest index of nearest entry of node for the specified entry.
        
        @param[in] entry (cfentry): Entry that is used for calculation distance.
        @param[in] type_measurement (measurement_type): Measurement type that is used for obtaining nearest entry to the specified.
        
        @return (uint) Index of nearest entry of node for the specified entry.
        
        """
        
        minimum_distance = float('Inf')
        nearest_index = 0
        
        for candidate_index in range(0, len(self.entries)):
            candidate_distance = self.entries[candidate_index].get_distance(entry, type_measurement)
            if candidate_distance < minimum_distance:
                nearest_index = candidate_index
        
        return nearest_index
    
    
    def get_nearest_entry(self, entry, type_measurement):
        """!
        @brief Find nearest entry of node for the specified entry.
        
        @param[in] entry (cfentry): Entry that is used for calculation distance.
        @param[in] type_measurement (measurement_type): Measurement type that is used for obtaining nearest entry to the specified.
        
        @return (cfentry) Nearest entry of node for the specified entry.
        
        """
        
        min_key = lambda cur_entity: cur_entity.get_distance(entry, type_measurement)
        return min(self.__entries, key=min_key)


class cftree:
    """!
    @brief CF-Tree representation.
    @details A CF-tree is a height-balanced tree with two parameters: branching factor and threshold.
    
    """
    
    @property
    def root(self):
        """!
        @return (cfnode) Root of the tree.
        
        """
        return self.__root
    
    
    @property
    def leafes(self):
        """!
        @return (list) List of all non-leaf nodes in the tree.
        
        """
        return self.__leafes
    
    
    @property
    def amount_nodes(self):
        """!
        @return (unit) Number of nodes (leaf and non-leaf) in the tree.
        
        """
        return self.__amount_nodes
    
    
    @property
    def amount_entries(self):
        """!
        @return (uint) Number of entries in the tree.
        
        """
        return self.__amount_entries
    
    
    @property
    def height(self):
        """!
        @return (uint) Height of the tree.
        
        """
        return self.__height
    
    
    @property
    def branch_factor(self):
        """!
        @return (uint) Branching factor of the tree.
        @details Branching factor defines maximum number of successors in each non-leaf node.
        
        """
        return self.__branch_factor
    
    
    @property
    def threshold(self):
        """!
        @return (double) Threshold of the tree that represents maximum diameter of sub-clusters that is formed by leaf node entries.
        
        """
        return self.__threshold
    
    
    @property
    def max_entries(self):
        """!
        @return (uint) Maximum number of entries in each leaf node.
        
        """
        return self.__max_entries
    
    
    @property
    def type_measurement(self):
        """!
        @return (measurement_type) Type that is used for measuring.
        
        """
        return self.__type_measurement
    
    
    def __init__(self, branch_factor, max_entries, threshold, type_measurement = measurement_type.CENTROID_EUCLIDEAN_DISTANCE):
        """!
        @brief Create CF-tree.
        
        @param[in] branch_factor (uint): Maximum number of children for non-leaf nodes.
        @param[in] max_entries (uint): Maximum number of entries for leaf nodes.
        @param[in] threshold (double): Maximum diameter of feature clustering for each leaf node.
        @param[in] type_measurement (measurement_type): Measurement type that is used for calculation distance metrics.
        
        """

        self.__root = None

        self.__branch_factor = branch_factor  # maximum number of children
        if self.__branch_factor < 2:
            self.__branch_factor = 2
        
        self.__threshold = threshold  # maximum diameter of sub-clusters stored at the leaf nodes
        self.__max_entries = max_entries
        
        self.__leafes = []
        
        self.__type_measurement = type_measurement
        
        # statistics
        self.__amount_nodes = 0    # root, despite it can be None.
        self.__amount_entries = 0
        self.__height = 0          # tree size with root.
    
    
    def get_level_nodes(self, level):
        """!
        @brief Traverses CF-tree to obtain nodes at the specified level.
        
        @param[in] level (uint): CF-tree level from that nodes should be returned.
        
        @return (list) List of CF-nodes that are located on the specified level of the CF-tree.
        
        """
        
        level_nodes = [];
        if (level < self.__height):
            level_nodes = self.__recursive_get_level_nodes(level, self.__root);
        
        return level_nodes;
    
    
    def __recursive_get_level_nodes(self, level, node):
        """!
        @brief Traverses CF-tree to obtain nodes at the specified level recursively.
        
        @param[in] level (uint): Current CF-tree level.
        @param[in] node (cfnode): CF-node from that traversing is performed.
        
        @return (list) List of CF-nodes that are located on the specified level of the CF-tree.
        
        """
        
        level_nodes = [];
        if (level is 0):
            level_nodes.append(node);
        
        else:
            for sucessor in node.successors:
                level_nodes += self.__recursive_get_level_nodes(level - 1, sucessor);
        
        return level_nodes;
    
    
    def insert_cluster(self, cluster):
        """!
        @brief Insert cluster that is represented as list of points where each point is represented by list of coordinates.
        @details Clustering feature is created for that cluster and inserted to the tree.
        
        @param[in] cluster (list): Cluster that is represented by list of points that should be inserted to the tree.
        
        """
        
        entry = cfentry(len(cluster), linear_sum(cluster), square_sum(cluster));
        self.insert(entry);
    
    
    def insert(self, entry):
        """!
        @brief Insert clustering feature to the tree.
        
        @param[in] entry (cfentry): Clustering feature that should be inserted.
        
        """
                
        if (self.__root is None):
            node = leaf_node(entry, None, [ entry ], None);
            
            self.__root = node;
            self.__leafes.append(node);
            
            # Update statistics
            self.__amount_entries += 1;
            self.__amount_nodes += 1;
            self.__height += 1;             # root has successor now
        else:
            child_node_updation = self.__recursive_insert(entry, self.__root);
            if (child_node_updation is True):
                # Splitting has been finished, check for possibility to merge (at least we have already two children).
                if (self.__merge_nearest_successors(self.__root) is True):
                    self.__amount_nodes -= 1;
    
    
    def find_nearest_leaf(self, entry, search_node = None):
        """!
        @brief Search nearest leaf to the specified clustering feature.
        
        @param[in] entry (cfentry): Clustering feature.
        @param[in] search_node (cfnode): Node from that searching should be started, if None then search process will be started for the root.
        
        @return (leaf_node) Nearest node to the specified clustering feature.
        
        """
        
        if (search_node is None):
            search_node = self.__root;
        
        nearest_node = search_node;
        
        if (search_node.type == cfnode_type.CFNODE_NONLEAF):
            min_key = lambda child_node: child_node.feature.get_distance(entry, self.__type_measurement);
            nearest_child_node = min(search_node.successors, key = min_key);
            
            nearest_node = self.find_nearest_leaf(entry, nearest_child_node);
        
        return nearest_node;
    
    
    def __recursive_insert(self, entry, search_node):
        """!
        @brief Recursive insert of the entry to the tree.
        @details It performs all required procedures during insertion such as splitting, merging.
        
        @param[in] entry (cfentry): Clustering feature.
        @param[in] search_node (cfnode): Node from that insertion should be started.
        
        @return (bool) True if number of nodes at the below level is changed, otherwise False.
        
        """
        
        # None-leaf node
        if (search_node.type == cfnode_type.CFNODE_NONLEAF):
            return self.__insert_for_noneleaf_node(entry, search_node);
        
        # Leaf is reached 
        else:
            return self.__insert_for_leaf_node(entry, search_node);
    
    
    def __insert_for_leaf_node(self, entry, search_node):
        """!
        @brief Recursive insert entry from leaf node to the tree.
        
        @param[in] entry (cfentry): Clustering feature.
        @param[in] search_node (cfnode): None-leaf node from that insertion should be started.
        
        @return (bool) True if number of nodes at the below level is changed, otherwise False.
        
        """
        
        node_amount_updation = False;
        
        # Try to absorb by the entity
        index_nearest_entry = search_node.get_nearest_index_entry(entry, self.__type_measurement);
        merged_entry = search_node.entries[index_nearest_entry] + entry;
        
        # Otherwise try to add new entry
        if (merged_entry.get_diameter() > self.__threshold):
            # If it's not exceeded append entity and update feature of the leaf node.
            search_node.insert_entry(entry);
            
            # Otherwise current node should be splitted
            if (len(search_node.entries) > self.__max_entries):
                self.__split_procedure(search_node);
                node_amount_updation = True;
            
            # Update statistics
            self.__amount_entries += 1;
            
        else:
            search_node.entries[index_nearest_entry] = merged_entry;
            search_node.feature += entry;
        
        return node_amount_updation;
    
    
    def __insert_for_noneleaf_node(self, entry, search_node):
        """!
        @brief Recursive insert entry from none-leaf node to the tree.
        
        @param[in] entry (cfentry): Clustering feature.
        @param[in] search_node (cfnode): None-leaf node from that insertion should be started.
        
        @return (bool) True if number of nodes at the below level is changed, otherwise False.
        
        """
        
        node_amount_updation = False;
        
        min_key = lambda child_node: child_node.get_distance(search_node, self.__type_measurement);
        nearest_child_node = min(search_node.successors, key = min_key);
        
        child_node_updation = self.__recursive_insert(entry, nearest_child_node);
        
        # Update clustering feature of none-leaf node.
        search_node.feature += entry;
            
        # Check branch factor, probably some leaf has been splitted and threshold has been exceeded.
        if (len(search_node.successors) > self.__branch_factor):
            
            # Check if it's aleady root then new root should be created (height is increased in this case).
            if (search_node is self.__root):
                self.__root = non_leaf_node(search_node.feature, None, [ search_node ], None);
                search_node.parent = self.__root;
                
                # Update statistics
                self.__amount_nodes += 1;
                self.__height += 1;
                
            [new_node1, new_node2] = self.__split_nonleaf_node(search_node);
            
            # Update parent list of successors
            parent = search_node.parent;
            parent.successors.remove(search_node);
            parent.successors.append(new_node1);
            parent.successors.append(new_node2);
            
            # Update statistics
            self.__amount_nodes += 1;
            node_amount_updation = True;
            
        elif (child_node_updation is True):
            # Splitting has been finished, check for possibility to merge (at least we have already two children).
            if (self.__merge_nearest_successors(search_node) is True):
                self.__amount_nodes -= 1;
        
        return node_amount_updation;
    
    
    def __merge_nearest_successors(self, node):
        """!
        @brief Find nearest sucessors and merge them.
        
        @param[in] node (non_leaf_node): Node whose two nearest successors should be merged.
        
        @return (bool): True if merging has been successfully performed, otherwise False.
        
        """
        
        merging_result = False;
        
        if (node.successors[0].type == cfnode_type.CFNODE_NONLEAF):
            [nearest_child_node1, nearest_child_node2] = node.get_nearest_successors(self.__type_measurement);
            
            if (len(nearest_child_node1.successors) + len(nearest_child_node2.successors) <= self.__branch_factor):
                node.successors.remove(nearest_child_node2);
                if (nearest_child_node2.type == cfnode_type.CFNODE_LEAF):
                    self.__leafes.remove(nearest_child_node2);
                
                nearest_child_node1.merge(nearest_child_node2);
                
                merging_result = True;
        
        return merging_result;
    
    
    def __split_procedure(self, split_node):
        """!
        @brief Starts node splitting procedure in the CF-tree from the specify node.
        
        @param[in] split_node (cfnode): CF-tree node that should be splitted.
        
        """
        if (split_node is self.__root):
            self.__root = non_leaf_node(split_node.feature, None, [ split_node ], None);
            split_node.parent = self.__root;
            
            # Update statistics
            self.__amount_nodes += 1;
            self.__height += 1;
        
        [new_node1, new_node2] = self.__split_leaf_node(split_node);
        
        self.__leafes.remove(split_node);
        self.__leafes.append(new_node1);
        self.__leafes.append(new_node2);
        
        # Update parent list of successors
        parent = split_node.parent;
        parent.successors.remove(split_node);
        parent.successors.append(new_node1);
        parent.successors.append(new_node2);
        
        # Update statistics
        self.__amount_nodes += 1;
    
    
    def __split_nonleaf_node(self, node):
        """!
        @brief Performs splitting of the specified non-leaf node.
        
        @param[in] node (non_leaf_node): Non-leaf node that should be splitted.
        
        @return (list) New pair of non-leaf nodes [non_leaf_node1, non_leaf_node2].
        
        """
        
        [farthest_node1, farthest_node2] = node.get_farthest_successors(self.__type_measurement);
        
        # create new non-leaf nodes
        new_node1 = non_leaf_node(farthest_node1.feature, node.parent, [ farthest_node1 ], None);
        new_node2 = non_leaf_node(farthest_node2.feature, node.parent, [ farthest_node2 ], None);
        
        farthest_node1.parent = new_node1;
        farthest_node2.parent = new_node2;
        
        # re-insert other successors
        for successor in node.successors:
            if ( (successor is not farthest_node1) and (successor is not farthest_node2) ):
                distance1 = new_node1.get_distance(successor, self.__type_measurement);
                distance2 = new_node2.get_distance(successor, self.__type_measurement);
                
                if (distance1 < distance2):
                    new_node1.insert_successor(successor);
                else:
                    new_node2.insert_successor(successor);
        
        return [new_node1, new_node2];
    
    
    def __split_leaf_node(self, node):
        """!
        @brief Performs splitting of the specified leaf node.
        
        @param[in] node (leaf_node): Leaf node that should be splitted.
        
        @return (list) New pair of leaf nodes [leaf_node1, leaf_node2].
        
        @warning Splitted node is transformed to non_leaf.
        
        """
        
        # search farthest pair of entries
        [farthest_entity1, farthest_entity2] = node.get_farthest_entries(self.__type_measurement);
                    
        # create new nodes
        new_node1 = leaf_node(farthest_entity1, node.parent, [ farthest_entity1 ], None);
        new_node2 = leaf_node(farthest_entity2, node.parent, [ farthest_entity2 ], None);
        
        # re-insert other entries
        for entity in node.entries:
            if ( (entity is not farthest_entity1) and (entity is not farthest_entity2) ):
                distance1 = new_node1.feature.get_distance(entity, self.__type_measurement);
                distance2 = new_node2.feature.get_distance(entity, self.__type_measurement);
                
                if (distance1 < distance2):
                    new_node1.insert_entry(entity);
                else:
                    new_node2.insert_entry(entity);
        
        return [new_node1, new_node2];
    
    
    def show_feature_destibution(self, data = None):
        """!
        @brief Shows feature distribution.
        @details Only features in 1D, 2D, 3D space can be visualized.
        
        @param[in] data (list): List of points that will be used for visualization, if it not specified than feature will be displayed only.
        
        """
        visualizer = cluster_visualizer();
        
        print("amount of nodes: ", self.__amount_nodes);
        
        if (data is not None):
            visualizer.append_cluster(data, marker = 'x');
        
        for level in range(0, self.height):
            level_nodes = self.get_level_nodes(level);
            
            centers = [ node.feature.get_centroid() for node in level_nodes ];
            visualizer.append_cluster(centers, None, markersize = (self.height - level + 1) * 5);
        
        visualizer.show();