Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
ImplicitTree Class Reference

Detailed Description

Balanced binary tree using implicit references to content.

ImplicitTree is a fully balanced binary tree which does not store nor define tree nodes. It is therefore suitable for very deep trees since the memory requirements increase only with the number of items to be represented, and not with the depth of the tree. Only a single memory allocation is performed in init().

The tree object does not store copies or references to the items contained in it, but only an array of item indices. It does not support insertion or removal of items. Items are accessed using the comparison object passed to sort().

The tree is partitioned using std::nth_element() using a user-supplied comparison functor, which implements a call operator taking unsigned integer values. As the comparison functor needs to be copied for each call of nth_element, it should not be too large. Before sorting, the method

  bool divide(begin, end);

of the comparison object is called in order to

In parallel mode, (TBB or OpenMP), each thread will use a private copy of the comparison object, which means that it cannot contain data which needs to be shared between calls on different nodes.

Note: The comparison object must handle the case where the item index passed to divide() or operator() evaluates to the constant NotFound, since that value might be present in nodes which are not fully populated.

See Also
NDPointTree, MxElementTree

#include <implicittree.h>

Public Member Functions

 ImplicitTree (uint n=0, uint mincount=1)
 create initial tree for n items
void init (uint n, uint mincount=1)
 initialize tree for n items
void parallelThreshold (uint n)
 change threshold node size for switching down to serial sort
uint size () const
 number of valid item indices
uint nnodes () const
 number of nodes in this tree
uint minSize () const
 minimum number of items in node
uint parent (uint k) const
 compute parent index
uint leftChild (uint k) const
 left child node index
uint rightChild (uint k) const
 left child node index
uint level (uint k) const
 compute depth level of node k
uint index (uint k) const
 access index
uint begin (uint k) const
 first index of node k
uint end (uint k) const
 last+1 index of node k
const Indices & indexRanges () const
 access ranges
uint size (uint k) const
 return node size
bool offsetRange (uint k, uint &ibegin, uint &iend) const
 extract range of valid indices, relies on NotFound sorted back
template<class Comparison >
void sort (Comparison cmp, bool inparallel=true)
 sort entire tree
XmlElement toXml (bool share=false) const
 create XML representation
void fromXml (const XmlElement &xe)
 retrieve from XML representation
template<class Comparison >
void sortNode (Comparison &cmp, uint k)
 sort node with index k
float megabyte () const
 determine memory footprint

Protected Member Functions

template<class Comparison >
void itersort (Comparison cmp, uint inode)
 serial stack-based sort
template<class Comparison >
void ompsort (Comparison cmp)
 sort entire tree

Protected Attributes

ItemArray items
 sorted index set
Indices irange
 begin and end indices for each node
uint nitem
 number of items stored
uint minsize
 minimum number of items in node
uint parthreshold
 parallelization threshold

The documentation for this class was generated from the following files: