kdtree.__recursive_remove() - Code Metrics - Inspection of "[refactoring] ant_colony params [phase 2 - final]" - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( a63a82...61f52c )

unknown

created 2016-04-12 15:26 UTC

kdtree.__recursive_remove() F

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Metric	Value
cc	9
dl	0
loc	45
rs	3

"""!

@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.
    
    """
    
    __root = None;
    __dimension = None;
    
    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.
        
        """
        
        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;
        node = self.__recursive_remove(node_for_remove);
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        if (parent is None):
            self.__root = node;
            
            # If all k-d tree was destroyed
            if (node is not None):
                node.parent = None;
        else:
            if (parent.left is node_for_remove):
                parent.left = node;
            elif (parent.right is node_for_remove):
                parent.right = node;
            else:
                assert 0;   # FATAL ERROR
        
        return self.__root;
    
    
    def __recursive_remove(self, node):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        """!
        @brief Delete node and return root of subtree.
        
        @param[in] node (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.right is None) and (node.left is None) ):
            return None;
        
        discriminator = node.disc;
        
        # Check if only left branch exist
        if (node.right is None):
            node.right = node.left;
            node.left = None;
        
        # Find minimal node in line with coordinate that is defined by discriminator
        minimal_node = self.find_minimal_node(node.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);
        else:
            assert 0;
        
        minimal_node.parent = node.parent;
        minimal_node.disc = node.disc;
        minimal_node.right = node.right;
        minimal_node.left = node.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, discriminator):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        """!
        @brief Find minimal node in line with coordinate that is defined by discriminator.
        
        @param[in] node (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 is not None:
                stack.append(node);
                node = node.left;
            else:
                if len(stack) != 0:
                    node = stack.pop();
                    candidates.append(node);
                    node = node.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:
                    assert 0
            
            else:
                if (cur_node.left is not None):
                    cur_node = cur_node.left;
                else:
                    assert 0
                
        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, best_nodes):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        """!
        @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 (node): Node from that searching is performed.
        @param[in|out] best_nodes (list): List of founded nodes.
        
        """
        
        minimum = node.data[node.disc] - distance;
        maximum = node.data[node.disc] + distance;
        
        if (node.right is not None):
            if (point[node.disc] >= minimum):
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node.right, best_nodes);
        
        if (node.left is not None):
            if (point[node.disc] < maximum):
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node.left, best_nodes);
        
        candidate_distance = euclidean_distance_sqrt(point, node.data);
        if (candidate_distance <= sqrt_distance):
            best_nodes.append( (candidate_distance, node) );
    
    
    def children(self, node):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        """!
        @brief Returns list of children of node.
        
        @param[in] node (node): Node whose children are required. 
        
        @return (list) Children of node. If node haven't got any child then None is returned.
        
        """
        
        if (node.left is not None):
            yield node.left;
        if (node.right is not None):
            yield node.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.
        
        """
        
        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 ( a63a82...61f52c )

kdtree.__recursive_remove() F

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			__root = None;
100			__dimension = None;
101
102			def __init__(self, data_list = None, payload_list = None):
103			"""!
104			@brief Create kd-tree from list of points and from according list of payloads.
105			@details If lists were not specified then empty kd-tree will be created.
106
107			@param[in] data_list (list): Insert points from the list to created KD tree.
108			@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.
109
110			"""
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			node = self.__recursive_remove(node_for_remove);
			0 ignored issues – show Comprehensibility Bug introduced 2016-03-31 09:26 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 `32`). 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...
184			if (parent is None):
185			self.__root = node;
186
187			# If all k-d tree was destroyed
188			if (node is not None):
189			node.parent = None;
190			else:
191			if (parent.left is node_for_remove):
192			parent.left = node;
193			elif (parent.right is node_for_remove):
194			parent.right = node;
195			else:
196			assert 0; # FATAL ERROR
197
198			return self.__root;
199
200
201			def __recursive_remove(self, node):
			0 ignored issues – show Comprehensibility Bug introduced 2016-03-31 09:26 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 `32`). 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...
202			"""!
203			@brief Delete node and return root of subtree.
204
205			@param[in] node (node): Node that should be removed.
206
207			@return (node) Minimal node in line with coordinate that is defined by descriminator.
208
209			"""
210
211			# Check if it is leaf
212			if ( (node.right is None) and (node.left is None) ):
213			return None;
214
215			discriminator = node.disc;
216
217			# Check if only left branch exist
218			if (node.right is None):
219			node.right = node.left;
220			node.left = None;
221
222			# Find minimal node in line with coordinate that is defined by discriminator
223			minimal_node = self.find_minimal_node(node.right, discriminator);
224			parent = minimal_node.parent;
225
226			if (parent.left is minimal_node):
227			parent.left = self.__recursive_remove(minimal_node);
228			elif (parent.right is minimal_node):
229			parent.right = self.__recursive_remove(minimal_node);
230			else:
231			assert 0;
232
233			minimal_node.parent = node.parent;
234			minimal_node.disc = node.disc;
235			minimal_node.right = node.right;
236			minimal_node.left = node.left;
237
238			# Update parent for successors of previous parent.
239			if (minimal_node.right is not None):
240			minimal_node.right.parent = minimal_node;
241
242			if (minimal_node.left is not None):
243			minimal_node.left.parent = minimal_node;
244
245			return minimal_node;
246
247
248			def find_minimal_node(self, node, discriminator):
			0 ignored issues – show Comprehensibility Bug introduced 2016-03-31 09:26 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 `32`). 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...
249			"""!
250			@brief Find minimal node in line with coordinate that is defined by discriminator.
251
252			@param[in] node (node): Node of KD tree from that search should be started.
253			@param[in] discriminator (uint): Coordinate number that is used for comparison.
254
255			@return (node) Minimal node in line with descriminator from the specified node.
256
257			"""
258
259			min_key = lambda cur_node: cur_node.data[discriminator];
260			stack = [];
261			candidates = [];
262			isFinished = False;
263			while isFinished is False:
264			if node is not None:
265			stack.append(node);
266			node = node.left;
267			else:
268			if len(stack) != 0:
269			node = stack.pop();
270			candidates.append(node);
271			node = node.right;
272			else:
273			isFinished = True;
274
275			return min(candidates, key = min_key);
276
277
278			def find_node(self, point, cur_node = None):
279			"""!
280			@brief Find node with coordinates that are defined by specified point.
281			@details If node does not exist then None will be returned. Otherwise required node will be returned.
282
283			@param[in] point (list): Coordinates of the point whose node should be found.
284			@param[in] cur_node (node): Node from which search should be started.
285
286			@return (node) Node in case of existance of node with specified coordinates, otherwise it return None.
287
288			"""
289
290			req_node = None;
291
292			if (cur_node is None):
293			cur_node = self.__root;
294
295			while True:
296			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
297			# Check if it's required node
298			if (cur_node.data == point):
299			req_node = cur_node;
300			break;
301
302			if (cur_node.right is not None):
303			cur_node = cur_node.right;
304			else:
305			assert 0
306
307			else:
308			if (cur_node.left is not None):
309			cur_node = cur_node.left;
310			else:
311			assert 0
312
313			return req_node;
314
315
316
317			def find_nearest_dist_node(self, point, distance, retdistance = False):
318			"""!
319			@brief Find nearest neighbor in area with radius = distance.
320
321			@param[in] point (list): Maximum distance where neighbors are searched.
322			@param[in] distance (double): Maximum distance where neighbors are searched.
323			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
324
325			@return (list) Neighbors, if redistance is True then neighbors with distances to them will be returned.
326
327			"""
328
329			best_nodes = self.find_nearest_dist_nodes(point, distance);
330
331			if (best_nodes == []):
332			return None;
333
334			nearest = min(best_nodes, key = lambda item: item[0]);
335
336			if (retdistance == True):
337			return nearest;
338			else:
339			return nearest[1];
340
341
342			def find_nearest_dist_nodes(self, point, distance):
343			"""!
344			@brief Find neighbors that are located in area that is covered by specified distance.
345
346			@param[in] point (list): Coordinates that is considered as centroind for searching.
347			@param[in] distance (double): Distance from the center where seaching is performed.
348
349			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
350
351			"""
352
353			best_nodes = [];
354			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
355
356			return best_nodes;
357
358
359			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node, best_nodes):
			0 ignored issues – show Comprehensibility Bug introduced 2016-03-31 09:26 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 `32`). 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...
360			"""!
361			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
362
363			@param[in] point (list): Coordinates that is considered as centroind for searching
364			@param[in] distance (double): Distance from the center where seaching is performed.
365			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
366			@param[in] node (node): Node from that searching is performed.
367			@param[in\|out] best_nodes (list): List of founded nodes.
368
369			"""
370
371			minimum = node.data[node.disc] - distance;
372			maximum = node.data[node.disc] + distance;
373
374			if (node.right is not None):
375			if (point[node.disc] >= minimum):
376			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node.right, best_nodes);
377
378			if (node.left is not None):
379			if (point[node.disc] < maximum):
380			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node.left, best_nodes);
381
382			candidate_distance = euclidean_distance_sqrt(point, node.data);
383			if (candidate_distance <= sqrt_distance):
384			best_nodes.append( (candidate_distance, node) );
385
386
387			def children(self, node):
			0 ignored issues – show Comprehensibility Bug introduced 2016-03-31 09:26 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 `32`). 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...
388			"""!
389			@brief Returns list of children of node.
390
391			@param[in] node (node): Node whose children are required.
392
393			@return (list) Children of node. If node haven't got any child then None is returned.
394
395			"""
396
397			if (node.left is not None):
398			yield node.left;
399			if (node.right is not None):
400			yield node.right;
401
402
403			def traverse(self, start_node = None, level = None):
404			"""!
405			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
406
407			@param[in] start_node (node): Node from that travering of subtree is performed.
408			@param[in, out] level (uint): Should be ignored by application.
409
410			@return (list) All nodes of the subtree.
411
412			"""
413
414			if (start_node is None):
415			start_node = self.__root;
416			level = 0;
417
418			if (start_node is None):
419			return [];
420
421			items = [ (level, start_node) ];
422			for child in self.children(start_node):
423			if child is not None:
424			items += self.traverse(child, level + 1);
425
426			return items;
427
428
429			def show(self):
430			"""!
431			@brief Display tree on the console.
432
433			"""
434
435			nodes = self.traverse();
436			if (nodes == []):
437			return;
438
439			nodes.sort(key = lambda item: item[0]);
440
441			level = nodes[0];
442			string = "";
443			for item in nodes:
444			if (level == item[0]):
445			string += str(item[1]) + "\t";
446
447			else:
448			print(string);
449			level = item[0];
450			string = str(item[1]) + "\t";
451
452			print(string);
453

annoviko / pyclustering

Push — master ( a63a82...61f52c )

kdtree.__recursive_remove() F

Complexity

Size

Duplication

1. Missing Dependencies

2. Missing __init__.py files

Duplication Side-by-Side

Filter issues like

2. Missing init.py files