kdtree.find_nearest_dist_node() - Code Metrics - Inspection of "[pyclustering] Refactoring." - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 1d669d...037fe6 )

by Andrei

created 2016-05-23 17:00 UTC

kdtree.find_nearest_dist_node() B

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Metric	Value
cc	4
dl	0
loc	23
rs	8.7972

"""!

@brief Data Structure: KD-Tree
@details Based on book description:
         - M.Samet. The Design And Analysis Of Spatial Data Structures. 1994.

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

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 'Node (%s, [%s %s])' % (self.data, left, right);
    
    def __str__(self):
        """!
        @return (string) String representation of the node.
        
        """
        return self.__repr__();


class kdtree:
    """!
    @brief Represents KD Tree.
    
    """
    
    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;
        
        if (data_list is None):
            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]);
            
                    
    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 (*): Payload of inserted node.
        
        """
        
        if (self.__root is None):
            self.__dimension = len(point);
            self.__root = node(point, payload, None, None, 0);
            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):
        """!
        @brief Remove specified point from kd-tree.
        
        @param[in] point (list): Coordinates of the point of removed node.
        
        @return (node) Root if node has been successfully removed, otherwise None.
        
        """
        
        # Get required node
        node_for_remove = self.find_node(point);
        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 find_node(self, point, cur_node = None):
        """!
        @brief Find node with coordinates that are defined by specified point.
        @details If node 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 in case of existance of node with specified coordinates, otherwise it return None.
        
        """
        
        req_node = None;
        
        if (cur_node is None):
            cur_node = self.__root;
        
        while True:
            if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
                # Check if it's required node
                if (cur_node.data == point):
                    req_node = cur_node;
                    break;
                
                if (cur_node.right is not None):
                    cur_node = cur_node.right;
            
            else:
                if (cur_node.left is not None):
                    cur_node = cur_node.left;
                
        return req_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 (list) Neighbors, if redistance is True then neighbors with distances to them will be returned.
        
        """
        
        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 == 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 = [];
        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.
        
        """
        
        minimum = node_head.data[node_head.disc] - distance;
        maximum = node_head.data[node_head.disc] + distance;
        
        if (node_head.right is not None):
            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):
            if (point[node_head.disc] < maximum):
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
        
        candidate_distance = euclidean_distance_sqrt(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;
            
    
    def show(self):
        """!
        @brief Display tree on the console using text representation.
        
        """
        
        nodes = self.traverse();
        if (nodes == []):
            return;
        
        nodes.sort(key = lambda item: item[0]);
        
        level = nodes[0];
        string = "";
        for item in nodes:
            if (level == item[0]):
                string += str(item[1]) + "\t";
                
            else:
                print(string);
                level = item[0];
                string = str(item[1]) + "\t";
                
        print(string);
    

Push — master ( 1d669d...037fe6 )

kdtree.find_nearest_dist_node() B

Complexity

Size

Duplication

1. Missing Dependencies

2. Missing init.py files

1			"""!
2
3			@brief Data Structure: KD-Tree
4			@details Based on book description:
5			- M.Samet. The Design And Analysis Of Spatial Data Structures. 1994.
6
7			@authors Andrei Novikov ([email protected])
8			@date 2014-2016
9			@copyright GNU Public License
10
11			@cond GNU_PUBLIC_LICENSE
12			PyClustering is free software: you can redistribute it and/or modify
13			it under the terms of the GNU General Public License as published by
14			the Free Software Foundation, either version 3 of the License, or
15			(at your option) any later version.
16
17			PyClustering is distributed in the hope that it will be useful,
18			but WITHOUT ANY WARRANTY; without even the implied warranty of
19			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20			GNU General Public License for more details.
21
22			You should have received a copy of the GNU General Public License
23			along with this program. If not, see <http://www.gnu.org/licenses/>.
24			@endcond
25
26			"""
27
28			import numpy;
			0 ignored issues – show Configuration introduced 2016-03-31 09:26 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... Unused Code introduced 2016-03-31 09:26 UTC by Report Bug Copy Issue Report The import `numpy` seems to be unused. Loading history...
29
30			from pyclustering.utils import euclidean_distance_sqrt;
31
32			class node:
33			"""!
34			@brief Represents node of KD-Tree.
35
36			"""
37
38			def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
39			"""!
40			@brief
41
42			@param[in] data (list): Data point that is presented as list of coodinates.
43			@param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
44			@param[in] left (node): Node of KD-Tree that is represented left successor.
45			@param[in] right (node): Node of KD-Tree that is represented right successor.
46			@param[in] disc (uint): Index of dimension of that node.
47			@param[in] parent (node): Node of KD-Tree that is represented parent.
48
49			"""
50
51			## Data point that is presented as list of coodinates.
52			self.data = data;
53
54			## Payload of node that can be used by user for storing specific information in the node.
55			self.payload = payload;
56
57			## Left node successor of the node.
58			self.left = left;
59
60			## Right node successor of the node.
61			self.right = right;
62
63			## Index of dimension.
64			self.disc = disc;
65
66			## Parent node of the node.
67			self.parent = parent;
68
69			def __repr__(self):
70			"""!
71			@return (string) Default representation of the node.
72
73			"""
74			left = None;
75			right = None;
76
77			if (self.left is not None):
78			left = self.left.data;
79
80			if (self.right is not None):
81			right = self.right.data;
82
83			return 'Node (%s, [%s %s])' % (self.data, left, right);
84
85			def __str__(self):
86			"""!
87			@return (string) String representation of the node.
88
89			"""
90			return self.__repr__();
91
92
93			class kdtree:
94			"""!
95			@brief Represents KD Tree.
96
97			"""
98
99			def __init__(self, data_list = None, payload_list = None):
100			"""!
101			@brief Create kd-tree from list of points and from according list of payloads.
102			@details If lists were not specified then empty kd-tree will be created.
103
104			@param[in] data_list (list): Insert points from the list to created KD tree.
105			@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.
106
107			"""
108
109			self.__root = None;
110			self.__dimension = None;
111
112			if (data_list is None):
113			return; # Just return from here, tree can be filled by insert method later
114
115			if (payload_list is None):
116			# Case when payload is not specified.
117			for index in range(0, len(data_list)):
118			self.insert(data_list[index], None);
119			else:
120			# Case when payload is specified.
121			for index in range(0, len(data_list)):
122			self.insert(data_list[index], payload_list[index]);
123
124
125			def insert(self, point, payload):
126			"""!
127			@brief Insert new point with payload to kd-tree.
128
129			@param[in] point (list): Coordinates of the point of inserted node.
130			@param[in] payload (*): Payload of inserted node.
131
132			"""
133
134			if (self.__root is None):
135			self.__dimension = len(point);
136			self.__root = node(point, payload, None, None, 0);
137			return self.__root;
138
139			cur_node = self.__root;
140
141			while True:
142			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
143			# If new node is greater or equal than current node then check right leaf
144			if (cur_node.right is None):
145			discriminator = cur_node.disc + 1;
146			if (discriminator >= self.__dimension):
147			discriminator = 0;
148
149			cur_node.right = node(point, payload, None, None, discriminator, cur_node);
150			return cur_node.right;
151			else:
152			cur_node = cur_node.right;
153
154			else:
155			# If new node is less than current then check left leaf
156			if (cur_node.left is None):
157			discriminator = cur_node.disc + 1;
158			if (discriminator >= self.__dimension):
159			discriminator = 0;
160
161			cur_node.left = node(point, payload, None, None, discriminator, cur_node);
162			return cur_node.left;
163			else:
164			cur_node = cur_node.left;
165
166
167			def remove(self, point):
168			"""!
169			@brief Remove specified point from kd-tree.
170
171			@param[in] point (list): Coordinates of the point of removed node.
172
173			@return (node) Root if node has been successfully removed, otherwise None.
174
175			"""
176
177			# Get required node
178			node_for_remove = self.find_node(point);
179			if (node_for_remove is None):
180			return None;
181
182			parent = node_for_remove.parent;
183			minimal_node = self.__recursive_remove(node_for_remove);
184			if (parent is None):
185			self.__root = minimal_node;
186
187			# If all k-d tree was destroyed
188			if (minimal_node is not None):
189			minimal_node.parent = None;
190			else:
191			if (parent.left is node_for_remove):
192			parent.left = minimal_node;
193			elif (parent.right is node_for_remove):
194			parent.right = minimal_node;
195
196			return self.__root;
197
198
199			def __recursive_remove(self, node_removed):
200			"""!
201			@brief Delete node and return root of subtree.
202
203			@param[in] node_removed (node): Node that should be removed.
204
205			@return (node) Minimal node in line with coordinate that is defined by descriminator.
206
207			"""
208
209			# Check if it is leaf
210			if ( (node_removed.right is None) and (node_removed.left is None) ):
211			return None;
212
213			discriminator = node_removed.disc;
214
215			# Check if only left branch exist
216			if (node_removed.right is None):
217			node_removed.right = node_removed.left;
218			node_removed.left = None;
219
220			# Find minimal node in line with coordinate that is defined by discriminator
221			minimal_node = self.find_minimal_node(node_removed.right, discriminator);
222			parent = minimal_node.parent;
223
224			if (parent.left is minimal_node):
225			parent.left = self.__recursive_remove(minimal_node);
226			elif (parent.right is minimal_node):
227			parent.right = self.__recursive_remove(minimal_node);
228
229			minimal_node.parent = node_removed.parent;
230			minimal_node.disc = node_removed.disc;
231			minimal_node.right = node_removed.right;
232			minimal_node.left = node_removed.left;
233
234			# Update parent for successors of previous parent.
235			if (minimal_node.right is not None):
236			minimal_node.right.parent = minimal_node;
237
238			if (minimal_node.left is not None):
239			minimal_node.left.parent = minimal_node;
240
241			return minimal_node;
242
243
244			def find_minimal_node(self, node_head, discriminator):
245			"""!
246			@brief Find minimal node in line with coordinate that is defined by discriminator.
247
248			@param[in] node_head (node): Node of KD tree from that search should be started.
249			@param[in] discriminator (uint): Coordinate number that is used for comparison.
250
251			@return (node) Minimal node in line with descriminator from the specified node.
252
253			"""
254
255			min_key = lambda cur_node: cur_node.data[discriminator];
256			stack = [];
257			candidates = [];
258			isFinished = False;
259			while isFinished is False:
260			if node_head is not None:
261			stack.append(node_head);
262			node_head = node_head.left;
263			else:
264			if len(stack) != 0:
265			node_head = stack.pop();
266			candidates.append(node_head);
267			node_head = node_head.right;
268			else:
269			isFinished = True;
270
271			return min(candidates, key = min_key);
272
273
274			def find_node(self, point, cur_node = None):
275			"""!
276			@brief Find node with coordinates that are defined by specified point.
277			@details If node does not exist then None will be returned. Otherwise required node will be returned.
278
279			@param[in] point (list): Coordinates of the point whose node should be found.
280			@param[in] cur_node (node): Node from which search should be started.
281
282			@return (node) Node in case of existance of node with specified coordinates, otherwise it return None.
283
284			"""
285
286			req_node = None;
287
288			if (cur_node is None):
289			cur_node = self.__root;
290
291			while True:
292			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
293			# Check if it's required node
294			if (cur_node.data == point):
295			req_node = cur_node;
296			break;
297
298			if (cur_node.right is not None):
299			cur_node = cur_node.right;
300
301			else:
302			if (cur_node.left is not None):
303			cur_node = cur_node.left;
304
305			return req_node;
306
307
308
309			def find_nearest_dist_node(self, point, distance, retdistance = False):
310			"""!
311			@brief Find nearest neighbor in area with radius = distance.
312
313			@param[in] point (list): Maximum distance where neighbors are searched.
314			@param[in] distance (double): Maximum distance where neighbors are searched.
315			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
316
317			@return (list) Neighbors, if redistance is True then neighbors with distances to them will be returned.
318
319			"""
320
321			best_nodes = self.find_nearest_dist_nodes(point, distance);
322
323			if (best_nodes == []):
324			return None;
325
326			nearest = min(best_nodes, key = lambda item: item[0]);
327
328			if (retdistance == True):
329			return nearest;
330			else:
331			return nearest[1];
332
333
334			def find_nearest_dist_nodes(self, point, distance):
335			"""!
336			@brief Find neighbors that are located in area that is covered by specified distance.
337
338			@param[in] point (list): Coordinates that is considered as centroind for searching.
339			@param[in] distance (double): Distance from the center where seaching is performed.
340
341			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
342
343			"""
344
345			best_nodes = [];
346			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
347
348			return best_nodes;
349
350
351			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
352			"""!
353			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
354
355			@param[in] point (list): Coordinates that is considered as centroind for searching
356			@param[in] distance (double): Distance from the center where seaching is performed.
357			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
358			@param[in] node_head (node): Node from that searching is performed.
359			@param[in\|out] best_nodes (list): List of founded nodes.
360
361			"""
362
363			minimum = node_head.data[node_head.disc] - distance;
364			maximum = node_head.data[node_head.disc] + distance;
365
366			if (node_head.right is not None):
367			if (point[node_head.disc] >= minimum):
368			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
369
370			if (node_head.left is not None):
371			if (point[node_head.disc] < maximum):
372			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
373
374			candidate_distance = euclidean_distance_sqrt(point, node_head.data);
375			if (candidate_distance <= sqrt_distance):
376			best_nodes.append( (candidate_distance, node_head) );
377
378
379			def children(self, node_parent):
380			"""!
381			@brief Returns list of children of node.
382
383			@param[in] node_parent (node): Node whose children are required.
384
385			@return (list) Children of node. If node haven't got any child then None is returned.
386
387			"""
388
389			if (node_parent.left is not None):
390			yield node_parent.left;
391			if (node_parent.right is not None):
392			yield node_parent.right;
393
394
395			def traverse(self, start_node = None, level = None):
396			"""!
397			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
398
399			@param[in] start_node (node): Node from that travering of subtree is performed.
400			@param[in, out] level (uint): Should be ignored by application.
401
402			@return (list) All nodes of the subtree.
403
404			"""
405
406			if (start_node is None):
407			start_node = self.__root;
408			level = 0;
409
410			if (start_node is None):
411			return [];
412
413			items = [ (level, start_node) ];
414			for child in self.children(start_node):
415			if child is not None:
416			items += self.traverse(child, level + 1);
417
418			return items;
419
420
421			def show(self):
422			"""!
423			@brief Display tree on the console using text representation.
424
425			"""
426
427			nodes = self.traverse();
428			if (nodes == []):
429			return;
430
431			nodes.sort(key = lambda item: item[0]);
432
433			level = nodes[0];
434			string = "";
435			for item in nodes:
436			if (level == item[0]):
437			string += str(item[1]) + "\t";
438
439			else:
440			print(string);
441			level = item[0];
442			string = str(item[1]) + "\t";
443
444			print(string);
445

annoviko / pyclustering

Push — master ( 1d669d...037fe6 )

kdtree.find_nearest_dist_node() B

Complexity

Size

Duplication

1. Missing Dependencies

2. Missing __init__.py files

Duplication Side-by-Side

Filter issues like

2. Missing init.py files