kdtree.__recursive_remove() - Code Metrics - Inspection of "#438: numpy.array is supported for KD-tree." - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 74690e...60d876 )

by Andrei

created 2018-05-29 22:38 UTC

kdtree.__recursive_remove() D

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	8
dl	0
loc	43
rs	4
c	0
b	0
f	0

"""!

@brief Data Structure: KD-Tree
@details Implementation based on paper @cite book::the_design_and_analysis.

@authors Andrei Novikov ([email protected])
@date 2014-2018
@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

"""


import numpy
# .scrutinizer.yml
before_commands:
    - sudo pip install abc # Python2
    - sudo pip3 install abc # Python3

from pyclustering.utils import euclidean_distance_square


class kdtree_text_visualizer:
    """!
    @brief KD-tree text visualizer that provides service to diplay tree structure using text representation.
    
    """

    def __init__(self, kdtree_instance):
        """!
        @brief Initialize KD-tree text visualizer.
        
        @param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized.
        
        """
        self.__kdtree_instance = kdtree_instance;
        
        self.__tree_level_text  = "";
        self.__tree_text        = "";


    def visualize(self, display=True):
        """!
        @brief Display KD-tree to console.
        
        @param[in] display (bool): If 'True' then tree will be shown in console.
        
        @return (string) Text representation of the KD-tree.
        
        """
        
        nodes = self.__get_nodes();
        level = nodes[0];
        
        for node in nodes:
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
            self.__print_node(level, node)

        self.__tree_text += self.__tree_level_text;
        if (display is True):
            print(self.__tree_text);
        
        return self.__tree_text;


    def __print_node(self, level, node):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        if (level == node[0]):
            self.__tree_level_text += str(node[1]) + "\t";

        else:
            self.__tree_text += self.__tree_level_text + "\n";
            level = node[0];
            self.__tree_level_text = str(node[1]) + "\t";


    def __get_nodes(self):
        nodes = self.__kdtree_instance.traverse();
        if (nodes == []):
            return;
        
        nodes.sort(key = lambda item: item[0]);
        return nodes;



class node:
    """!
    @brief Represents node of KD-Tree.
    
    """
    
    def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
        """!
        @brief 
        
        @param[in] data (list): Data point that is presented as list of coodinates.
        @param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
        @param[in] left (node): Node of KD-Tree that is represented left successor.
        @param[in] right (node): Node of KD-Tree that is represented right successor.
        @param[in] disc (uint): Index of dimension of that node.
        @param[in] parent (node): Node of KD-Tree that is represented parent.
        
        """
        
        ## Data point that is presented as list of coodinates.
        self.data = data;
        
        ## Payload of node that can be used by user for storing specific information in the node.
        self.payload = payload;
        
        ## Left node successor of the node.
        self.left = left;
        
        ## Right node successor of the node.
        self.right = right;
        
        ## Index of dimension.
        self.disc = disc;
        
        ## Parent node of the node.
        self.parent = parent;


    def __repr__(self):
        """!
        @return (string) Default representation of the node.
        
        """
        left = None; 
        right = None; 
        
        if (self.left is not None):
            left = self.left.data;
            
        if (self.right is not None):
            right = self.right.data;
        
        return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
    
    def __str__(self):
        """!
        @return (string) String representation of the node.
        
        """
        return self.__repr__();


class kdtree:
    """!
    @brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
    @details In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is represented 
              as a node in the k-d tree in the form of a record of type node.
    
    Examples:
    @code
        # Import required modules
        from pyclustering.samples.definitions import SIMPLE_SAMPLES;
        from pyclustering.container.kdtree import kdtree;
        from pyclustering.utils import read_sample;
        
        # Read data from text file
        sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
        
        # Create instance of KD-tree and initialize (fill) it by read data.
        tree_instance = kdtree(sample);
        
        # Search for nearest point
        search_distance = 0.3;
        nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
        
        # Search for nearest point in radius 0.3
        nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
        print("Nearest nodes:", nearest_nodes);
    @endcode
    
    """
    
    def __init__(self, data_list = None, payload_list = None):
        """!
        @brief Create kd-tree from list of points and from according list of payloads.
        @details If lists were not specified then empty kd-tree will be created.
        
        @param[in] data_list (list): Insert points from the list to created KD tree.
        @param[in] payload_list (list): Insert payload from the list to created KD tree, length should be equal to length of data_list if it is specified.
        
        """
        
        self.__root = None
        self.__dimension = None
        self.__point_comparator = None

        self.__fill_tree(data_list, payload_list)


    def insert(self, point, payload):
        """!
        @brief Insert new point with payload to kd-tree.
        
        @param[in] point (list): Coordinates of the point of inserted node.
        @param[in] payload (any-type): Payload of inserted node. It can be identificator of the node or
                    some useful payload that belongs to the point.
        
        @return (node) Inserted node to the kd-tree.
        
        """
        
        if self.__root is None:
            self.__dimension = len(point)
            self.__root = node(point, payload, None, None, 0)
            self.__point_comparator = self.__create_point_comparator(type(point))
            return self.__root
        
        cur_node = self.__root
        
        while True:
            if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
                # If new node is greater or equal than current node then check right leaf
                if cur_node.right is None:
                    discriminator = cur_node.disc + 1;
                    if discriminator >= self.__dimension:
                        discriminator = 0;
                        
                    cur_node.right = node(point, payload, None, None, discriminator, cur_node);
                    return cur_node.right;
                else: 
                    cur_node = cur_node.right;
            
            else:
                # If new node is less than current then check left leaf
                if cur_node.left is None:
                    discriminator = cur_node.disc + 1;
                    if discriminator >= self.__dimension:
                        discriminator = 0;
                        
                    cur_node.left = node(point, payload, None, None, discriminator, cur_node);
                    return cur_node.left;
                else:
                    cur_node = cur_node.left;
    
    
    def remove(self, point, **kwargs):
        """!
        @brief Remove specified point from kd-tree.
        @details It removes the first found node that satisfy to the input parameters. Make sure that
                  pair (point, payload) is unique for each node, othewise the first found is removed.
        
        @param[in] point (list): Coordinates of the point of removed node.
        @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'payload').
        
        <b>Keyword Args:</b><br>
            - payload (any): Payload of the node that should be removed.
        
        @return (node) Root if node has been successfully removed, otherwise None.
        
        """
        
        # Get required node
        node_for_remove = None;
        if 'payload' in kwargs:
            node_for_remove = self.find_node_with_payload(point, kwargs['payload'], None);
        else:
            node_for_remove = self.find_node(point, None);
        
        if node_for_remove is None:
            return None;
        
        parent = node_for_remove.parent;
        minimal_node = self.__recursive_remove(node_for_remove);
        if parent is None:
            self.__root = minimal_node;
            
            # If all k-d tree was destroyed
            if minimal_node is not None:
                minimal_node.parent = None;
        else:
            if parent.left is node_for_remove:
                parent.left = minimal_node;
            elif parent.right is node_for_remove:
                parent.right = minimal_node;
        
        return self.__root;
    
    
    def __recursive_remove(self, node_removed):
        """!
        @brief Delete node and return root of subtree.
        
        @param[in] node_removed (node): Node that should be removed.
        
        @return (node) Minimal node in line with coordinate that is defined by descriminator.
        
        """
                
        # Check if it is leaf
        if (node_removed.right is None) and (node_removed.left is None):
            return None;
        
        discriminator = node_removed.disc;
        
        # Check if only left branch exist
        if node_removed.right is None:
            node_removed.right = node_removed.left;
            node_removed.left = None;
        
        # Find minimal node in line with coordinate that is defined by discriminator
        minimal_node = self.find_minimal_node(node_removed.right, discriminator);
        parent = minimal_node.parent;
        
        if parent.left is minimal_node:
            parent.left = self.__recursive_remove(minimal_node);
        elif parent.right is minimal_node:
            parent.right = self.__recursive_remove(minimal_node);
        
        minimal_node.parent = node_removed.parent;
        minimal_node.disc = node_removed.disc;
        minimal_node.right = node_removed.right;
        minimal_node.left = node_removed.left;
        
        # Update parent for successors of previous parent.
        if minimal_node.right is not None:
            minimal_node.right.parent = minimal_node;
             
        if minimal_node.left is not None:
            minimal_node.left.parent = minimal_node;
        
        return minimal_node;


    def find_minimal_node(self, node_head, discriminator):
        """!
        @brief Find minimal node in line with coordinate that is defined by discriminator.
        
        @param[in] node_head (node): Node of KD tree from that search should be started.
        @param[in] discriminator (uint): Coordinate number that is used for comparison.
        
        @return (node) Minimal node in line with descriminator from the specified node.
        
        """
        
        min_key = lambda cur_node: cur_node.data[discriminator];
        stack = [];
        candidates = [];
        isFinished = False;
        while isFinished is False:
            if node_head is not None:
                stack.append(node_head);
                node_head = node_head.left;
            else:
                if len(stack) != 0:
                    node_head = stack.pop();
                    candidates.append(node_head);
                    node_head = node_head.right;
                else:
                    isFinished = True;

        return min(candidates, key = min_key);


    def __fill_tree(self, data_list, payload_list):
        """!
        @brief Fill KD-tree by specified data and create point comparator in line with data type.

        @param[in] data_list (array_like): Data points that should be inserted to the tree.
        @param[in] payload_list (array_like): Data point payloads that follows data points inserted to the tree.

        """
        if data_list is None or len(data_list) == 0:
            return; # Just return from here, tree can be filled by insert method later

        if payload_list is None:
            # Case when payload is not specified.
            for index in range(0, len(data_list)):
                self.insert(data_list[index], None);
        else:
            # Case when payload is specified.
            for index in range(0, len(data_list)):
                self.insert(data_list[index], payload_list[index]);

        self.__point_comparator = self.__create_point_comparator(type(self.__root.data))


    def __create_point_comparator(self, type_node):
        """!
        @brief Create point comparator.
        @details In case of numpy.array specific comparator is required.

        @return (callable) Callable point comparator to compare to points.

        """
        if type_node == numpy.ndarray:
            return lambda obj1, obj2: numpy.array_equal(obj1, obj2)

        return lambda obj1, obj2: obj1 == obj2


    def __find_node_by_rule(self, point, search_rule, cur_node):
        """!
        @brief Search node that satisfy to parameters in search rule.
        @details If node with specified parameters does not exist then None will be returned, 
                  otherwise required node will be returned.
        
        @param[in] point (list): Coordinates of the point whose node should be found.
        @param[in] search_rule (lambda): Rule that is called to check whether node satisfies to search parameter.
        @param[in] cur_node (node): Node from which search should be started.
        
        @return (node) Node if it satisfies to input parameters, otherwise it return None.
        
        """
        
        req_node = None;
        
        if cur_node is None:
            cur_node = self.__root;
        
        while cur_node:
            if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
                # Check if it's required node
                if search_rule(cur_node):
                    req_node = cur_node;
                    break;
                
                cur_node = cur_node.right;
            
            else:
                cur_node = cur_node.left;
        
        return req_node;


    def find_node_with_payload(self, point, payload, cur_node = None):

        """!
        @brief Find node with specified coordinates and payload.
        @details If node with specified parameters does not exist then None will be returned, 
                  otherwise required node will be returned.
        
        @param[in] point (list): Coordinates of the point whose node should be found.
        @param[in] payload (any): Payload of the node that is searched in the tree.
        @param[in] cur_node (node): Node from which search should be started.
        
        @return (node) Node if it satisfies to input parameters, otherwise it return None.
        
        """
        
        rule_search = lambda node, point=point, payload=payload: self.__point_comparator(node.data, point) and node.payload == payload;
        return self.__find_node_by_rule(point, rule_search, cur_node);


    def find_node(self, point, cur_node = None):
        """!
        @brief Find node with coordinates that are defined by specified point.
        @details If node with specified parameters does not exist then None will be returned, 
                  otherwise required node will be returned.
        
        @param[in] point (list): Coordinates of the point whose node should be found.
        @param[in] cur_node (node): Node from which search should be started.
        
        @return (node) Node if it satisfies to input parameters, otherwise it return None.
        
        """
        
        rule_search = lambda node, point=point: self.__point_comparator(node.data, point);
        return self.__find_node_by_rule(point, rule_search, cur_node);
    
    
    def find_nearest_dist_node(self, point, distance, retdistance = False):
        """!
        @brief Find nearest neighbor in area with radius = distance.
        
        @param[in] point (list): Maximum distance where neighbors are searched.
        @param[in] distance (double): Maximum distance where neighbors are searched.
        @param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
        
        @return (node|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True,
                 where the first element is pointer to node and the second element is distance to it.
        
        """
        
        best_nodes = self.find_nearest_dist_nodes(point, distance);
            
        if best_nodes == []:
            return None;
        
        nearest = min(best_nodes, key = lambda item: item[0]);
        
        if retdistance is True:
            return nearest;
        else:
            return nearest[1];
    
    
    def find_nearest_dist_nodes(self, point, distance):
        """!
        @brief Find neighbors that are located in area that is covered by specified distance.
        
        @param[in] point (list): Coordinates that is considered as centroind for searching.
        @param[in] distance (double): Distance from the center where seaching is performed.
        
        @return (list) Neighbors in area that is specified by point (center) and distance (radius).
        
        """

        best_nodes = [];
        if self.__root is not None:
            self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);

        return best_nodes;


    def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
        """!
        @brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
        
        @param[in] point (list): Coordinates that is considered as centroind for searching
        @param[in] distance (double): Distance from the center where seaching is performed.
        @param[in] sqrt_distance (double): Square distance from the center where searching is performed.
        @param[in] node_head (node): Node from that searching is performed.
        @param[in|out] best_nodes (list): List of founded nodes.
        
        """

        if node_head.right is not None:
            minimum = node_head.data[node_head.disc] - distance;
            if point[node_head.disc] >= minimum:
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
        
        if node_head.left is not None:
            maximum = node_head.data[node_head.disc] + distance;
            if point[node_head.disc] < maximum:
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
        
        candidate_distance = euclidean_distance_square(point, node_head.data);
        if candidate_distance <= sqrt_distance:
            best_nodes.append( (candidate_distance, node_head) );


    def children(self, node_parent):
        """!
        @brief Returns list of children of node.
        
        @param[in] node_parent (node): Node whose children are required. 
        
        @return (list) Children of node. If node haven't got any child then None is returned.
        
        """
        
        if node_parent.left is not None:
            yield node_parent.left;
        if node_parent.right is not None:
            yield node_parent.right;


    def traverse(self, start_node = None, level = None):
        """!
        @brief Traverses all nodes of subtree that is defined by node specified in input parameter.
        
        @param[in] start_node (node): Node from that travering of subtree is performed.
        @param[in, out] level (uint): Should be ignored by application.
        
        @return (list) All nodes of the subtree.
        
        """
        
        if start_node is None:
            start_node  = self.__root;
            level = 0;
        
        if start_node is None:
            return [];
        
        items = [ (level, start_node) ];
        for child in self.children(start_node):
            if child is not None:
                items += self.traverse(child, level + 1);
        
        return items;


Push — master ( 74690e...60d876 )

kdtree.__recursive_remove() D

Complexity

Size

Duplication

Importance

1. Missing Dependencies

2. Missing init.py files

1			"""!
2
3			@brief Data Structure: KD-Tree
4			@details Implementation based on paper @cite book::the_design_and_analysis.
5
6			@authors Andrei Novikov ([email protected])
7			@date 2014-2018
8			@copyright GNU Public License
9
10			@cond GNU_PUBLIC_LICENSE
11			PyClustering is free software: you can redistribute it and/or modify
12			it under the terms of the GNU General Public License as published by
13			the Free Software Foundation, either version 3 of the License, or
14			(at your option) any later version.
15
16			PyClustering is distributed in the hope that it will be useful,
17			but WITHOUT ANY WARRANTY; without even the implied warranty of
18			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19			GNU General Public License for more details.
20
21			You should have received a copy of the GNU General Public License
22			along with this program. If not, see <http://www.gnu.org/licenses/>.
23			@endcond
24
25			"""
26
27
28			import numpy
			0 ignored issues – show Configuration introduced 2018-05-29 22:39 UTC by Report Bug Copy Issue Report The import `numpy` could not be resolved. This can be caused by one of the following: 1. Missing Dependencies This error could indicate a configuration issue of Pylint. Make sure that your libraries are available by adding the necessary commands. # .scrutinizer.yml before_commands: - sudo pip install abc # Python2 - sudo pip3 install abc # Python3 Tip: We are currently not using virtualenv to run pylint, when installing your modules make sure to use the command for the correct version. 2. Missing __init__.py files This error could also result from missing `__init__.py` files in your module folders. Make sure that you place one file in each sub-folder. Loading history...
29
30			from pyclustering.utils import euclidean_distance_square
31
32
33			class kdtree_text_visualizer:
34			"""!
35			@brief KD-tree text visualizer that provides service to diplay tree structure using text representation.
36
37			"""
38
39			def __init__(self, kdtree_instance):
40			"""!
41			@brief Initialize KD-tree text visualizer.
42
43			@param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized.
44
45			"""
46			self.__kdtree_instance = kdtree_instance;
47
48			self.__tree_level_text = "";
49			self.__tree_text = "";
50
51
52			def visualize(self, display=True):
53			"""!
54			@brief Display KD-tree to console.
55
56			@param[in] display (bool): If 'True' then tree will be shown in console.
57
58			@return (string) Text representation of the KD-tree.
59
60			"""
61
62			nodes = self.__get_nodes();
63			level = nodes[0];
64
65			for node in nodes:
			0 ignored issues – show Comprehensibility Bug introduced 2017-10-23 12:23 UTC by Report Bug Copy Issue Report `node` is re-defining a name which is already available in the outer-scope (previously defined on line `95`). It is generally a bad practice to shadow variables from the outer-scope. In most cases, this is done unintentionally and might lead to unexpected behavior: param = 5 class Foo: def __init__(self, param): # "param" would be flagged here self.param = param Loading history...
66			self.__print_node(level, node)
67
68			self.__tree_text += self.__tree_level_text;
69			if (display is True):
70			print(self.__tree_text);
71
72			return self.__tree_text;
73
74
75			def __print_node(self, level, node):
			0 ignored issues – show Comprehensibility Bug introduced 2017-10-23 12:23 UTC by Report Bug Copy Issue Report `node` is re-defining a name which is already available in the outer-scope (previously defined on line `95`). It is generally a bad practice to shadow variables from the outer-scope. In most cases, this is done unintentionally and might lead to unexpected behavior: param = 5 class Foo: def __init__(self, param): # "param" would be flagged here self.param = param Loading history...
76			if (level == node[0]):
77			self.__tree_level_text += str(node[1]) + "\t";
78
79			else:
80			self.__tree_text += self.__tree_level_text + "\n";
81			level = node[0];
82			self.__tree_level_text = str(node[1]) + "\t";
83
84
85			def __get_nodes(self):
86			nodes = self.__kdtree_instance.traverse();
87			if (nodes == []):
88			return;
89
90			nodes.sort(key = lambda item: item[0]);
91			return nodes;
92
93
94
95			class node:
96			"""!
97			@brief Represents node of KD-Tree.
98
99			"""
100
101			def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
102			"""!
103			@brief
104
105			@param[in] data (list): Data point that is presented as list of coodinates.
106			@param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
107			@param[in] left (node): Node of KD-Tree that is represented left successor.
108			@param[in] right (node): Node of KD-Tree that is represented right successor.
109			@param[in] disc (uint): Index of dimension of that node.
110			@param[in] parent (node): Node of KD-Tree that is represented parent.
111
112			"""
113
114			## Data point that is presented as list of coodinates.
115			self.data = data;
116
117			## Payload of node that can be used by user for storing specific information in the node.
118			self.payload = payload;
119
120			## Left node successor of the node.
121			self.left = left;
122
123			## Right node successor of the node.
124			self.right = right;
125
126			## Index of dimension.
127			self.disc = disc;
128
129			## Parent node of the node.
130			self.parent = parent;
131
132
133			def __repr__(self):
134			"""!
135			@return (string) Default representation of the node.
136
137			"""
138			left = None;
139			right = None;
140
141			if (self.left is not None):
142			left = self.left.data;
143
144			if (self.right is not None):
145			right = self.right.data;
146
147			return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
148
149			def __str__(self):
150			"""!
151			@return (string) String representation of the node.
152
153			"""
154			return self.__repr__();
155
156
157			class kdtree:
158			"""!
159			@brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
160			@details In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is represented
161			as a node in the k-d tree in the form of a record of type node.
162
163			Examples:
164			@code
165			# Import required modules
166			from pyclustering.samples.definitions import SIMPLE_SAMPLES;
167			from pyclustering.container.kdtree import kdtree;
168			from pyclustering.utils import read_sample;
169
170			# Read data from text file
171			sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
172
173			# Create instance of KD-tree and initialize (fill) it by read data.
174			tree_instance = kdtree(sample);
175
176			# Search for nearest point
177			search_distance = 0.3;
178			nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
179
180			# Search for nearest point in radius 0.3
181			nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
182			print("Nearest nodes:", nearest_nodes);
183			@endcode
184
185			"""
186
187			def __init__(self, data_list = None, payload_list = None):
188			"""!
189			@brief Create kd-tree from list of points and from according list of payloads.
190			@details If lists were not specified then empty kd-tree will be created.
191
192			@param[in] data_list (list): Insert points from the list to created KD tree.
193			@param[in] payload_list (list): Insert payload from the list to created KD tree, length should be equal to length of data_list if it is specified.
194
195			"""
196
197			self.__root = None
198			self.__dimension = None
199			self.__point_comparator = None
200
201			self.__fill_tree(data_list, payload_list)
202
203
204			def insert(self, point, payload):
205			"""!
206			@brief Insert new point with payload to kd-tree.
207
208			@param[in] point (list): Coordinates of the point of inserted node.
209			@param[in] payload (any-type): Payload of inserted node. It can be identificator of the node or
210			some useful payload that belongs to the point.
211
212			@return (node) Inserted node to the kd-tree.
213
214			"""
215
216			if self.__root is None:
217			self.__dimension = len(point)
218			self.__root = node(point, payload, None, None, 0)
219			self.__point_comparator = self.__create_point_comparator(type(point))
220			return self.__root
221
222			cur_node = self.__root
223
224			while True:
225			if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
226			# If new node is greater or equal than current node then check right leaf
227			if cur_node.right is None:
228			discriminator = cur_node.disc + 1;
229			if discriminator >= self.__dimension:
230			discriminator = 0;
231
232			cur_node.right = node(point, payload, None, None, discriminator, cur_node);
233			return cur_node.right;
234			else:
235			cur_node = cur_node.right;
236
237			else:
238			# If new node is less than current then check left leaf
239			if cur_node.left is None:
240			discriminator = cur_node.disc + 1;
241			if discriminator >= self.__dimension:
242			discriminator = 0;
243
244			cur_node.left = node(point, payload, None, None, discriminator, cur_node);
245			return cur_node.left;
246			else:
247			cur_node = cur_node.left;
248
249
250			def remove(self, point, **kwargs):
251			"""!
252			@brief Remove specified point from kd-tree.
253			@details It removes the first found node that satisfy to the input parameters. Make sure that
254			pair (point, payload) is unique for each node, othewise the first found is removed.
255
256			@param[in] point (list): Coordinates of the point of removed node.
257			@param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'payload').
258
259			<b>Keyword Args:</b><br>
260			- payload (any): Payload of the node that should be removed.
261
262			@return (node) Root if node has been successfully removed, otherwise None.
263
264			"""
265
266			# Get required node
267			node_for_remove = None;
268			if 'payload' in kwargs:
269			node_for_remove = self.find_node_with_payload(point, kwargs['payload'], None);
270			else:
271			node_for_remove = self.find_node(point, None);
272
273			if node_for_remove is None:
274			return None;
275
276			parent = node_for_remove.parent;
277			minimal_node = self.__recursive_remove(node_for_remove);
278			if parent is None:
279			self.__root = minimal_node;
280
281			# If all k-d tree was destroyed
282			if minimal_node is not None:
283			minimal_node.parent = None;
284			else:
285			if parent.left is node_for_remove:
286			parent.left = minimal_node;
287			elif parent.right is node_for_remove:
288			parent.right = minimal_node;
289
290			return self.__root;
291
292
293			def __recursive_remove(self, node_removed):
294			"""!
295			@brief Delete node and return root of subtree.
296
297			@param[in] node_removed (node): Node that should be removed.
298
299			@return (node) Minimal node in line with coordinate that is defined by descriminator.
300
301			"""
302
303			# Check if it is leaf
304			if (node_removed.right is None) and (node_removed.left is None):
305			return None;
306
307			discriminator = node_removed.disc;
308
309			# Check if only left branch exist
310			if node_removed.right is None:
311			node_removed.right = node_removed.left;
312			node_removed.left = None;
313
314			# Find minimal node in line with coordinate that is defined by discriminator
315			minimal_node = self.find_minimal_node(node_removed.right, discriminator);
316			parent = minimal_node.parent;
317
318			if parent.left is minimal_node:
319			parent.left = self.__recursive_remove(minimal_node);
320			elif parent.right is minimal_node:
321			parent.right = self.__recursive_remove(minimal_node);
322
323			minimal_node.parent = node_removed.parent;
324			minimal_node.disc = node_removed.disc;
325			minimal_node.right = node_removed.right;
326			minimal_node.left = node_removed.left;
327
328			# Update parent for successors of previous parent.
329			if minimal_node.right is not None:
330			minimal_node.right.parent = minimal_node;
331
332			if minimal_node.left is not None:
333			minimal_node.left.parent = minimal_node;
334
335			return minimal_node;
336
337
338			def find_minimal_node(self, node_head, discriminator):
339			"""!
340			@brief Find minimal node in line with coordinate that is defined by discriminator.
341
342			@param[in] node_head (node): Node of KD tree from that search should be started.
343			@param[in] discriminator (uint): Coordinate number that is used for comparison.
344
345			@return (node) Minimal node in line with descriminator from the specified node.
346
347			"""
348
349			min_key = lambda cur_node: cur_node.data[discriminator];
350			stack = [];
351			candidates = [];
352			isFinished = False;
353			while isFinished is False:
354			if node_head is not None:
355			stack.append(node_head);
356			node_head = node_head.left;
357			else:
358			if len(stack) != 0:
359			node_head = stack.pop();
360			candidates.append(node_head);
361			node_head = node_head.right;
362			else:
363			isFinished = True;
364
365			return min(candidates, key = min_key);
366
367
368			def __fill_tree(self, data_list, payload_list):
369			"""!
370			@brief Fill KD-tree by specified data and create point comparator in line with data type.
371
372			@param[in] data_list (array_like): Data points that should be inserted to the tree.
373			@param[in] payload_list (array_like): Data point payloads that follows data points inserted to the tree.
374
375			"""
376			if data_list is None or len(data_list) == 0:
377			return; # Just return from here, tree can be filled by insert method later
378
379			if payload_list is None:
380			# Case when payload is not specified.
381			for index in range(0, len(data_list)):
382			self.insert(data_list[index], None);
383			else:
384			# Case when payload is specified.
385			for index in range(0, len(data_list)):
386			self.insert(data_list[index], payload_list[index]);
387
388			self.__point_comparator = self.__create_point_comparator(type(self.__root.data))
389
390
391			def __create_point_comparator(self, type_node):
392			"""!
393			@brief Create point comparator.
394			@details In case of numpy.array specific comparator is required.
395
396			@return (callable) Callable point comparator to compare to points.
397
398			"""
399			if type_node == numpy.ndarray:
400			return lambda obj1, obj2: numpy.array_equal(obj1, obj2)
401
402			return lambda obj1, obj2: obj1 == obj2
403
404
405			def __find_node_by_rule(self, point, search_rule, cur_node):
406			"""!
407			@brief Search node that satisfy to parameters in search rule.
408			@details If node with specified parameters does not exist then None will be returned,
409			otherwise required node will be returned.
410
411			@param[in] point (list): Coordinates of the point whose node should be found.
412			@param[in] search_rule (lambda): Rule that is called to check whether node satisfies to search parameter.
413			@param[in] cur_node (node): Node from which search should be started.
414
415			@return (node) Node if it satisfies to input parameters, otherwise it return None.
416
417			"""
418
419			req_node = None;
420
421			if cur_node is None:
422			cur_node = self.__root;
423
424			while cur_node:
425			if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
426			# Check if it's required node
427			if search_rule(cur_node):
428			req_node = cur_node;
429			break;
430
431			cur_node = cur_node.right;
432
433			else:
434			cur_node = cur_node.left;
435
436			return req_node;
437
438
439			def find_node_with_payload(self, point, payload, cur_node = None):
			0 ignored issues – show Unused Code introduced 2018-02-16 10:28 UTC by Report Bug Copy Issue Report The argument `payload` seems to be unused. Loading history...
440			"""!
441			@brief Find node with specified coordinates and payload.
442			@details If node with specified parameters does not exist then None will be returned,
443			otherwise required node will be returned.
444
445			@param[in] point (list): Coordinates of the point whose node should be found.
446			@param[in] payload (any): Payload of the node that is searched in the tree.
447			@param[in] cur_node (node): Node from which search should be started.
448
449			@return (node) Node if it satisfies to input parameters, otherwise it return None.
450
451			"""
452
453			rule_search = lambda node, point=point, payload=payload: self.__point_comparator(node.data, point) and node.payload == payload;
454			return self.__find_node_by_rule(point, rule_search, cur_node);
455
456
457			def find_node(self, point, cur_node = None):
458			"""!
459			@brief Find node with coordinates that are defined by specified point.
460			@details If node with specified parameters does not exist then None will be returned,
461			otherwise required node will be returned.
462
463			@param[in] point (list): Coordinates of the point whose node should be found.
464			@param[in] cur_node (node): Node from which search should be started.
465
466			@return (node) Node if it satisfies to input parameters, otherwise it return None.
467
468			"""
469
470			rule_search = lambda node, point=point: self.__point_comparator(node.data, point);
471			return self.__find_node_by_rule(point, rule_search, cur_node);
472
473
474			def find_nearest_dist_node(self, point, distance, retdistance = False):
475			"""!
476			@brief Find nearest neighbor in area with radius = distance.
477
478			@param[in] point (list): Maximum distance where neighbors are searched.
479			@param[in] distance (double): Maximum distance where neighbors are searched.
480			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
481
482			@return (node\|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True,
483			where the first element is pointer to node and the second element is distance to it.
484
485			"""
486
487			best_nodes = self.find_nearest_dist_nodes(point, distance);
488
489			if best_nodes == []:
490			return None;
491
492			nearest = min(best_nodes, key = lambda item: item[0]);
493
494			if retdistance is True:
495			return nearest;
496			else:
497			return nearest[1];
498
499
500			def find_nearest_dist_nodes(self, point, distance):
501			"""!
502			@brief Find neighbors that are located in area that is covered by specified distance.
503
504			@param[in] point (list): Coordinates that is considered as centroind for searching.
505			@param[in] distance (double): Distance from the center where seaching is performed.
506
507			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
508
509			"""
510
511			best_nodes = [];
512			if self.__root is not None:
513			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
514
515			return best_nodes;
516
517
518			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
519			"""!
520			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
521
522			@param[in] point (list): Coordinates that is considered as centroind for searching
523			@param[in] distance (double): Distance from the center where seaching is performed.
524			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
525			@param[in] node_head (node): Node from that searching is performed.
526			@param[in\|out] best_nodes (list): List of founded nodes.
527
528			"""
529
530			if node_head.right is not None:
531			minimum = node_head.data[node_head.disc] - distance;
532			if point[node_head.disc] >= minimum:
533			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
534
535			if node_head.left is not None:
536			maximum = node_head.data[node_head.disc] + distance;
537			if point[node_head.disc] < maximum:
538			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
539
540			candidate_distance = euclidean_distance_square(point, node_head.data);
541			if candidate_distance <= sqrt_distance:
542			best_nodes.append( (candidate_distance, node_head) );
543
544
545			def children(self, node_parent):
546			"""!
547			@brief Returns list of children of node.
548
549			@param[in] node_parent (node): Node whose children are required.
550
551			@return (list) Children of node. If node haven't got any child then None is returned.
552
553			"""
554
555			if node_parent.left is not None:
556			yield node_parent.left;
557			if node_parent.right is not None:
558			yield node_parent.right;
559
560
561			def traverse(self, start_node = None, level = None):
562			"""!
563			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
564
565			@param[in] start_node (node): Node from that travering of subtree is performed.
566			@param[in, out] level (uint): Should be ignored by application.
567
568			@return (list) All nodes of the subtree.
569
570			"""
571
572			if start_node is None:
573			start_node = self.__root;
574			level = 0;
575
576			if start_node is None:
577			return [];
578
579			items = [ (level, start_node) ];
580			for child in self.children(start_node):
581			if child is not None:
582			items += self.traverse(child, level + 1);
583
584			return items;
585

annoviko / pyclustering

Push — master ( 74690e...60d876 )

kdtree.__recursive_remove() D

Complexity

Size

Duplication

Importance

1. Missing Dependencies

2. Missing __init__.py files

Duplication Side-by-Side

Filter issues like

2. Missing init.py files