Base class for metric space indexes which have tree-like properties.
It's implementation is not complete enough to make it actually
usable, but it should make it quite easy to implement other indexing
and searching strategies. In an ideal case, all you have to do is to
derive from this class, implement the methods construct,
_get_child_candidates and optionally insert and make children
an attribute or property returning all child nodes of the current
node. If you need an __init__ method, you should call
super(YourClass, self).__init__(objects, func, parent) in its
end as well.
Instances of this class (and its subclasses, of course) are supposed
to be recursive data structures. This means that they may be treated
like the root of a tree whether they have a parent or not. This
means every node has:
Note that in many (most? some?) cases, implementors don't have to
fiddle with these values directly. Instead, there are some helper
methods like _incr_node_counter and _incr_size that may be
called at appropriate times. If in doubt, just implement what you
strictly need first and then take a look whether node, size and
height counting works as expected (and whether you care).
As a bonus, this class implements some of python's magic methods so
that you can iterate over its instances' content and use the in
operator to test for the existence of an object using the distance
function.
|
|
__init__(self,
objects=None,
func=None,
parent=None)
Create a new metric tree. If objects and func are given,
the given objects will be indexed immediately using the distance
function which makes it possible to immediately start so search
for other objects in it. Otherwise, you have to call construct
later in order to make use of this metric tree. |
source code
|
|
|
|
range_search(self,
obj,
min_dist=0,
max_dist=0)
Return a list of all objects in this subtree whose distance to
obj is at least min_dist and at most max_dist. min_dist
and max_dist have to satisfy the condition 0 <= min_dist <=
max_dist. |
source code
|
|
|
|
search(self,
obj,
max_dist)
Equivalent to range_search(obj, min_dist=0, max_dist). |
source code
|
|
|
|
nn_search(self,
obj,
num=1)
Perform a k-nearest-neighbour search and return a sorted list of
at most num objects together with their distance to the
query object ((object, distance) tuples). Sorting is done by
the distance (ascending). Of course, num has to be an int
(or long, for that matter) larger than zero. |
source code
|
|
|
|
_get_child_candidates(self,
distance,
min_dist,
max_dist)
Return a sequence of child nodes that may contain objects with a
distance difference between (inclusive) min and max to a
certain query object. Note that the query object is not
passed to this method. Instead, distance is the query
object's previously calculated distance to this node. |
source code
|
|
|
|
construct(self,
objects,
func)
(Re)Index this space with the given objects using the
distance function func. Previous contents will be
discarded. objects has to be a sequence or an iterable. The
distance function func needs to be applicable to all objects
contained in objects. |
source code
|
|
|
|
insert(self,
obj)
Insert a single object into the metric tree. Returns self,
i.e. the tree itself. |
source code
|
|
|
|
is_root(self)
Answer whether this node is the root of a tree (i.e. it has no
parent). |
source code
|
|
|
|
is_leaf(self)
Answer whether this node is a leaf node (i.e. it has no
children) |
source code
|
|
|
|
|
|
|
|
|
|
|
|
|
__parent(self)
The parent of this node. None if this node is the root
of a tree. |
source code
|
|
|
|
|
|
|
_incr_size(self,
incr=1)
Increment the size counter for this node and all its parents
recursively. |
source code
|
|
|
|
_calculate_height(self,
recursive=True)
Set this node's height to one and (if recursive is True)
propagate this change upwards in the tree. |
source code
|
|
|
|
|
|
|
_apply_upwards(self,
func,
**args)
Helper method to apply a function to this node and all its
parents recursively. The given function must accept one node as
the first parameter and may accept arbitrary keyword parameters
as well. |
source code
|
|
|
|
_get_dist(self,
obj)
Apply this node's distance function to the given object and one
of this node's values. |
source code
|
|
|
|
__iter__(self)
A generator that yields all objects in this node and its
children by doing recursive pre-order traversal. Implementors
might choose to use another traversal method which better suits
their data structure. |
source code
|
|
|
|
itervalues(self)
A generator that yields all objects in this node and its
children by doing recursive pre-order traversal. Implementors
might choose to use another traversal method which better suits
their data structure. |
source code
|
|
|
|
iternodes(self)
A generator that yields all nodes in this subtree by doing
recursive pre-order traversal. Implementors might choose to use
another traversal method which better suits their data
structure. |
source code
|
|
|
|
__nonzero__(self)
Return True if this node contains any objects. |
source code
|
|
|
|
__len__(self)
Return the number of objects in this subtree |
source code
|
|
|
|
__contains__(self,
item)
Search for objects with a distance of zero to item and return
True if something is found, otherwise False. |
source code
|
|
|
|
|
|
Inherited from object:
__delattr__,
__format__,
__getattribute__,
__hash__,
__new__,
__reduce__,
__reduce_ex__,
__setattr__,
__sizeof__,
__str__,
__subclasshook__
|