'Find all pairs of points within a distance.
Parameters
r : positive float
The maximum distance.
p : float, optional
Which Minkowski norm to use.  `p` has to meet the condition
``1 <= p <= infinity``.
eps : float, optional
Approximate search.  Branches of the tree are not explored
if their nearest points are further than ``r/(1+eps)``, and
branches are added in bulk if their furthest points are nearer
than ``r * (1+eps)``.  `eps` has to be non-negative.
Returns
results : set
Set of pairs ``(i,j)``, with ``i < j``, for which the corresponding
positions are close.'

def query_pairs(self, r, p=2.0, eps=0):

    results = set()
    def traverse_checking(node1, rect1, node2, rect2):
        if (rect1.min_distance_rectangle(rect2, p) > (r / (1.0 + eps))):
            return
        elif (rect1.max_distance_rectangle(rect2, p) < (r * (1.0 + eps))):
            traverse_no_checking(node1, node2)
        elif isinstance(node1, KDTree.leafnode):
            if isinstance(node2, KDTree.leafnode):
                if (id(node1) == id(node2)):
                    d = self.data[node2.idx]
                    for i in node1.idx:
                        for j in node2.idx[(minkowski_distance(d, self.data[i], p) <= r)]:
                            if (i < j):
                                results.add((i, j))
                else:
                    d = self.data[node2.idx]
                    for i in node1.idx:
                        for j in node2.idx[(minkowski_distance(d, self.data[i], p) <= r)]:
                            if (i < j):
                                results.add((i, j))
                            elif (j < i):
                                results.add((j, i))
            else:
                (less, greater) = rect2.split(node2.split_dim, node2.split)
                traverse_checking(node1, rect1, node2.less, less)
                traverse_checking(node1, rect1, node2.greater, greater)
        elif isinstance(node2, KDTree.leafnode):
            (less, greater) = rect1.split(node1.split_dim, node1.split)
            traverse_checking(node1.less, less, node2, rect2)
            traverse_checking(node1.greater, greater, node2, rect2)
        else:
            (less1, greater1) = rect1.split(node1.split_dim, node1.split)
            (less2, greater2) = rect2.split(node2.split_dim, node2.split)
            traverse_checking(node1.less, less1, node2.less, less2)
            traverse_checking(node1.less, less1, node2.greater, greater2)
            if (id(node1) != id(node2)):
                traverse_checking(node1.greater, greater1, node2.less, less2)
            traverse_checking(node1.greater, greater1, node2.greater, greater2)
    def traverse_no_checking(node1, node2):
        if isinstance(node1, KDTree.leafnode):
            if isinstance(node2, KDTree.leafnode):
                if (id(node1) == id(node2)):
                    for i in node1.idx:
                        for j in node2.idx:
                            if (i < j):
                                results.add((i, j))
                else:
                    for i in node1.idx:
                        for j in node2.idx:
                            if (i < j):
                                results.add((i, j))
                            elif (j < i):
                                results.add((j, i))
            else:
                traverse_no_checking(node1, node2.less)
                traverse_no_checking(node1, node2.greater)
        elif (id(node1) == id(node2)):
            traverse_no_checking(node1.less, node2.less)
            traverse_no_checking(node1.less, node2.greater)
            traverse_no_checking(node1.greater, node2.greater)
        else:
            traverse_no_checking(node1.less, node2)
            traverse_no_checking(node1.greater, node2)
    traverse_checking(self.tree, Rectangle(self.maxes, self.mins), self.tree, Rectangle(self.maxes, self.mins))
    return results
