Class Acts::KDTree::KDTreeAbstractNode

class KDTreeAbstractNode

An abstract class containing common features of k-d tree node types.

A k-d tree consists of two different node types: leaf nodes and inner nodes. These nodes have some common functionality, which is captured by this common parent node type.

Public Functions

inline KDTreeAbstractNode(iterator_t _b, iterator_t _e)

Construct the common data for all node types.

The node types share a few concepts, like an n-dimensional range, and a begin and end of the range of elements managed. This constructor calculates these things so that the individual child constructors don’t have to.

virtual ~KDTreeAbstractNode(void) = default

Destroy this node in the k-d tree, and indirectly all of its children.

inline const range_t &range(void) const

The axis-aligned bounding box containing all elements in this node.


The minimal axis-aligned bounding box that contains all the elements under this node.

virtual void rangeSearchMapDiscard(const range_t &r, std::function<void(const coordinate_t&, const Type&)> f) const = 0

Perform a range search in the k-d tree, mapping the key-value pairs to a side-effecting function.

This is the most powerful range search method we have, assuming that we can use arbitrary side effects, which we can. All other range search methods are implemented in terms of this particular function.

  • r – The range to search for.

  • f – The mapping function to apply to matching elements.

inline std::size_t size(void) const

Determine the number of elements managed by this node.

Conveniently, this number is always equal to the distance between the begin iterator and the end iterator, so we can simply delegate to the relevant standard library method.


The number of elements below this node.

virtual std::string toString(std::size_t d) const = 0

Debugging method that gives a textual representation of a k-d tree.

It is probably best not to use this method in real code. It is designed for debugging purposes only.


d – The depth of this node (for indentation).