kdtree.__recursive_nearest_nodes() - Code Metrics - Inspection of "[.] Merge branch '0.8.dev'." - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( c8bc69...89bc14 )

by Andrei

created 2018-02-23 14:25 UTC

kdtree.__recursive_nearest_nodes() B

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	6
dl	0
loc	25
rs	7.5384
c	0
b	0
f	0

"""!

@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-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

"""


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;
        
        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 (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);
            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 (payload).
        
        Keyword Args:
            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 __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: 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: 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 == 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;


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-2018
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
29			from pyclustering.utils import euclidean_distance_square;
30
31
32			class kdtree_text_visualizer:
33			"""!
34			@brief KD-tree text visualizer that provides service to diplay tree structure using text representation.
35
36			"""
37
38			def __init__(self, kdtree_instance):
39			"""!
40			@brief Initialize KD-tree text visualizer.
41
42			@param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized.
43
44			"""
45			self.__kdtree_instance = kdtree_instance;
46
47			self.__tree_level_text = "";
48			self.__tree_text = "";
49
50			def visualize(self, display=True):
51			"""!
52			@brief Display KD-tree to console.
53
54			@param[in] display (bool): If 'True' then tree will be shown in console.
55
56			@return (string) Text representation of the KD-tree.
57
58			"""
59
60			nodes = self.__get_nodes();
61			level = nodes[0];
62
63			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 `93`). 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...
64			self.__print_node(level, node)
65
66			self.__tree_text += self.__tree_level_text;
67			if (display is True):
68			print(self.__tree_text);
69
70			return self.__tree_text;
71
72
73			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 `93`). 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...
74			if (level == node[0]):
75			self.__tree_level_text += str(node[1]) + "\t";
76
77			else:
78			self.__tree_text += self.__tree_level_text + "\n";
79			level = node[0];
80			self.__tree_level_text = str(node[1]) + "\t";
81
82
83			def __get_nodes(self):
84			nodes = self.__kdtree_instance.traverse();
85			if (nodes == []):
86			return;
87
88			nodes.sort(key = lambda item: item[0]);
89			return nodes;
90
91
92
93			class node:
94			"""!
95			@brief Represents node of KD-Tree.
96
97			"""
98
99			def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
100			"""!
101			@brief
102
103			@param[in] data (list): Data point that is presented as list of coodinates.
104			@param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
105			@param[in] left (node): Node of KD-Tree that is represented left successor.
106			@param[in] right (node): Node of KD-Tree that is represented right successor.
107			@param[in] disc (uint): Index of dimension of that node.
108			@param[in] parent (node): Node of KD-Tree that is represented parent.
109
110			"""
111
112			## Data point that is presented as list of coodinates.
113			self.data = data;
114
115			## Payload of node that can be used by user for storing specific information in the node.
116			self.payload = payload;
117
118			## Left node successor of the node.
119			self.left = left;
120
121			## Right node successor of the node.
122			self.right = right;
123
124			## Index of dimension.
125			self.disc = disc;
126
127			## Parent node of the node.
128			self.parent = parent;
129
130
131			def __repr__(self):
132			"""!
133			@return (string) Default representation of the node.
134
135			"""
136			left = None;
137			right = None;
138
139			if (self.left is not None):
140			left = self.left.data;
141
142			if (self.right is not None):
143			right = self.right.data;
144
145			return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
146
147			def __str__(self):
148			"""!
149			@return (string) String representation of the node.
150
151			"""
152			return self.__repr__();
153
154
155			class kdtree:
156			"""!
157			@brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
158			@details In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is represented
159			as a node in the k-d tree in the form of a record of type node.
160
161			Examples:
162			@code
163			# Import required modules
164			from pyclustering.samples.definitions import SIMPLE_SAMPLES;
165			from pyclustering.container.kdtree import kdtree;
166			from pyclustering.utils import read_sample;
167
168			# Read data from text file
169			sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
170
171			# Create instance of KD-tree and initialize (fill) it by read data.
172			tree_instance = kdtree(sample);
173
174			# Search for nearest point
175			search_distance = 0.3;
176			nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
177
178			# Search for nearest point in radius 0.3
179			nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
180			print("Nearest nodes:", nearest_nodes);
181			@endcode
182
183			"""
184
185			def __init__(self, data_list = None, payload_list = None):
186			"""!
187			@brief Create kd-tree from list of points and from according list of payloads.
188			@details If lists were not specified then empty kd-tree will be created.
189
190			@param[in] data_list (list): Insert points from the list to created KD tree.
191			@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.
192
193			"""
194
195			self.__root = None;
196			self.__dimension = None;
197
198			if (data_list is None):
199			return; # Just return from here, tree can be filled by insert method later
200
201			if (payload_list is None):
202			# Case when payload is not specified.
203			for index in range(0, len(data_list)):
204			self.insert(data_list[index], None);
205			else:
206			# Case when payload is specified.
207			for index in range(0, len(data_list)):
208			self.insert(data_list[index], payload_list[index]);
209
210
211			def insert(self, point, payload):
212			"""!
213			@brief Insert new point with payload to kd-tree.
214
215			@param[in] point (list): Coordinates of the point of inserted node.
216			@param[in] payload (any-type): Payload of inserted node. It can be identificator of the node or
217			some useful payload that belongs to the point.
218
219			@return (node) Inserted node to the kd-tree.
220
221			"""
222
223			if (self.__root is None):
224			self.__dimension = len(point);
225			self.__root = node(point, payload, None, None, 0);
226			return self.__root;
227
228			cur_node = self.__root;
229
230			while True:
231			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
232			# If new node is greater or equal than current node then check right leaf
233			if (cur_node.right is None):
234			discriminator = cur_node.disc + 1;
235			if (discriminator >= self.__dimension):
236			discriminator = 0;
237
238			cur_node.right = node(point, payload, None, None, discriminator, cur_node);
239			return cur_node.right;
240			else:
241			cur_node = cur_node.right;
242
243			else:
244			# If new node is less than current then check left leaf
245			if (cur_node.left is None):
246			discriminator = cur_node.disc + 1;
247			if (discriminator >= self.__dimension):
248			discriminator = 0;
249
250			cur_node.left = node(point, payload, None, None, discriminator, cur_node);
251			return cur_node.left;
252			else:
253			cur_node = cur_node.left;
254
255
256			def remove(self, point, **kwargs):
257			"""!
258			@brief Remove specified point from kd-tree.
259			@details It removes the first found node that satisfy to the input parameters. Make sure that
260			pair (point, payload) is unique for each node, othewise the first found is removed.
261
262			@param[in] point (list): Coordinates of the point of removed node.
263			@param[in] **kwargs: Arbitrary keyword arguments (payload).
264
265			Keyword Args:
266			payload (any): Payload of the node that should be removed.
267
268			@return (node) Root if node has been successfully removed, otherwise None.
269
270			"""
271
272			# Get required node
273			node_for_remove = None;
274			if ('payload' in kwargs):
275			node_for_remove = self.find_node_with_payload(point, kwargs['payload'], None);
276			else:
277			node_for_remove = self.find_node(point, None);
278
279			if (node_for_remove is None):
280			return None;
281
282			parent = node_for_remove.parent;
283			minimal_node = self.__recursive_remove(node_for_remove);
284			if (parent is None):
285			self.__root = minimal_node;
286
287			# If all k-d tree was destroyed
288			if (minimal_node is not None):
289			minimal_node.parent = None;
290			else:
291			if (parent.left is node_for_remove):
292			parent.left = minimal_node;
293			elif (parent.right is node_for_remove):
294			parent.right = minimal_node;
295
296			return self.__root;
297
298
299			def __recursive_remove(self, node_removed):
300			"""!
301			@brief Delete node and return root of subtree.
302
303			@param[in] node_removed (node): Node that should be removed.
304
305			@return (node) Minimal node in line with coordinate that is defined by descriminator.
306
307			"""
308
309			# Check if it is leaf
310			if ( (node_removed.right is None) and (node_removed.left is None) ):
311			return None;
312
313			discriminator = node_removed.disc;
314
315			# Check if only left branch exist
316			if (node_removed.right is None):
317			node_removed.right = node_removed.left;
318			node_removed.left = None;
319
320			# Find minimal node in line with coordinate that is defined by discriminator
321			minimal_node = self.find_minimal_node(node_removed.right, discriminator);
322			parent = minimal_node.parent;
323
324			if (parent.left is minimal_node):
325			parent.left = self.__recursive_remove(minimal_node);
326			elif (parent.right is minimal_node):
327			parent.right = self.__recursive_remove(minimal_node);
328
329			minimal_node.parent = node_removed.parent;
330			minimal_node.disc = node_removed.disc;
331			minimal_node.right = node_removed.right;
332			minimal_node.left = node_removed.left;
333
334			# Update parent for successors of previous parent.
335			if (minimal_node.right is not None):
336			minimal_node.right.parent = minimal_node;
337
338			if (minimal_node.left is not None):
339			minimal_node.left.parent = minimal_node;
340
341			return minimal_node;
342
343
344			def find_minimal_node(self, node_head, discriminator):
345			"""!
346			@brief Find minimal node in line with coordinate that is defined by discriminator.
347
348			@param[in] node_head (node): Node of KD tree from that search should be started.
349			@param[in] discriminator (uint): Coordinate number that is used for comparison.
350
351			@return (node) Minimal node in line with descriminator from the specified node.
352
353			"""
354
355			min_key = lambda cur_node: cur_node.data[discriminator];
356			stack = [];
357			candidates = [];
358			isFinished = False;
359			while isFinished is False:
360			if node_head is not None:
361			stack.append(node_head);
362			node_head = node_head.left;
363			else:
364			if len(stack) != 0:
365			node_head = stack.pop();
366			candidates.append(node_head);
367			node_head = node_head.right;
368			else:
369			isFinished = True;
370
371			return min(candidates, key = min_key);
372
373
374			def __find_node_by_rule(self, point, search_rule, cur_node):
375			"""!
376			@brief Search node that satisfy to parameters in search rule.
377			@details If node with specified parameters does not exist then None will be returned,
378			otherwise required node will be returned.
379
380			@param[in] point (list): Coordinates of the point whose node should be found.
381			@param[in] search_rule (lambda): Rule that is called to check whether node satisfies to search parameter.
382			@param[in] cur_node (node): Node from which search should be started.
383
384			@return (node) Node if it satisfies to input parameters, otherwise it return None.
385
386			"""
387
388			req_node = None;
389
390			if (cur_node is None):
391			cur_node = self.__root;
392
393			while cur_node:
394			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
395			# Check if it's required node
396			if (search_rule(cur_node)):
397			req_node = cur_node;
398			break;
399
400			cur_node = cur_node.right;
401
402			else:
403			cur_node = cur_node.left;
404
405			return req_node;
406
407
408			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...
409			"""!
410			@brief Find node with specified coordinates and payload.
411			@details If node with specified parameters does not exist then None will be returned,
412			otherwise required node will be returned.
413
414			@param[in] point (list): Coordinates of the point whose node should be found.
415			@param[in] payload (any): Payload of the node that is searched in the tree.
416			@param[in] cur_node (node): Node from which search should be started.
417
418			@return (node) Node if it satisfies to input parameters, otherwise it return None.
419
420			"""
421
422			rule_search = lambda node, point=point, payload=payload: node.data == point and node.payload == payload;
423			return self.__find_node_by_rule(point, rule_search, cur_node);
424
425
426			def find_node(self, point, cur_node = None):
427			"""!
428			@brief Find node with coordinates that are defined by specified point.
429			@details If node with specified parameters does not exist then None will be returned,
430			otherwise required node will be returned.
431
432			@param[in] point (list): Coordinates of the point whose node should be found.
433			@param[in] cur_node (node): Node from which search should be started.
434
435			@return (node) Node if it satisfies to input parameters, otherwise it return None.
436
437			"""
438
439			rule_search = lambda node, point=point: node.data == point;
440			return self.__find_node_by_rule(point, rule_search, cur_node);
441
442
443			def find_nearest_dist_node(self, point, distance, retdistance = False):
444			"""!
445			@brief Find nearest neighbor in area with radius = distance.
446
447			@param[in] point (list): Maximum distance where neighbors are searched.
448			@param[in] distance (double): Maximum distance where neighbors are searched.
449			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
450
451			@return (node\|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True,
452			where the first element is pointer to node and the second element is distance to it.
453
454			"""
455
456			best_nodes = self.find_nearest_dist_nodes(point, distance);
457
458			if (best_nodes == []):
459			return None;
460
461			nearest = min(best_nodes, key = lambda item: item[0]);
462
463			if (retdistance == True):
464			return nearest;
465			else:
466			return nearest[1];
467
468
469			def find_nearest_dist_nodes(self, point, distance):
470			"""!
471			@brief Find neighbors that are located in area that is covered by specified distance.
472
473			@param[in] point (list): Coordinates that is considered as centroind for searching.
474			@param[in] distance (double): Distance from the center where seaching is performed.
475
476			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
477
478			"""
479
480			best_nodes = [];
481			if (self.__root is not None):
482			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
483
484			return best_nodes;
485
486
487			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
488			"""!
489			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
490
491			@param[in] point (list): Coordinates that is considered as centroind for searching
492			@param[in] distance (double): Distance from the center where seaching is performed.
493			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
494			@param[in] node_head (node): Node from that searching is performed.
495			@param[in\|out] best_nodes (list): List of founded nodes.
496
497			"""
498
499			if (node_head.right is not None):
500			minimum = node_head.data[node_head.disc] - distance;
501			if (point[node_head.disc] >= minimum):
502			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
503
504			if (node_head.left is not None):
505			maximum = node_head.data[node_head.disc] + distance;
506			if (point[node_head.disc] < maximum):
507			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
508
509			candidate_distance = euclidean_distance_square(point, node_head.data);
510			if (candidate_distance <= sqrt_distance):
511			best_nodes.append( (candidate_distance, node_head) );
512
513
514			def children(self, node_parent):
515			"""!
516			@brief Returns list of children of node.
517
518			@param[in] node_parent (node): Node whose children are required.
519
520			@return (list) Children of node. If node haven't got any child then None is returned.
521
522			"""
523
524			if (node_parent.left is not None):
525			yield node_parent.left;
526			if (node_parent.right is not None):
527			yield node_parent.right;
528
529
530			def traverse(self, start_node = None, level = None):
531			"""!
532			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
533
534			@param[in] start_node (node): Node from that travering of subtree is performed.
535			@param[in, out] level (uint): Should be ignored by application.
536
537			@return (list) All nodes of the subtree.
538
539			"""
540
541			if (start_node is None):
542			start_node = self.__root;
543			level = 0;
544
545			if (start_node is None):
546			return [];
547
548			items = [ (level, start_node) ];
549			for child in self.children(start_node):
550			if child is not None:
551			items += self.traverse(child, level + 1);
552
553			return items;
554

annoviko / pyclustering

Push — master ( c8bc69...89bc14 )

kdtree.__recursive_nearest_nodes() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like