Implentation of the reduced quadtree for Dim dimensions. More...

#include <ogdf/energybased/dtree/DTree.h>

Classes
struct	MortonEntry
	The entry in the sorted order for a point. More...

struct	Node
	The node class. More...

struct	Point
	The point class with integer coords. More...

Public Member Functions
	DTree (int numPoints)
	constructor

	~DTree ()
	destructor

void	adjustPointInfo (int curr)
	used to update the first and numPoints of inner nodes by linkNodes

void	build ()
	Does all required steps except the allocate, deallocate, randomPoints.

int	child (int i, int j) const
	returns the index of the j th child of node i

int	countPoints () const
	Just for fun: traverse the tree and count the points in the leaves.

int	countPoints (int curr) const
	Just for fun: traverse the tree and count the points in the leaves.

void	linkNodes ()
	The Recursive Bottom-Up Construction (recursion start)

int	linkNodes (int curr, int maxLevel)
	The Recursive Bottom-Up Construction.

int	maxNumNodes () const
	returns the maximum number of nodes (and the max index of a node)

void	mergeWithNext (int curr)
	Merges curr with next node in the chain (used by linkNodes)

Node &	node (int i)
	Just to access the nodes a little bit easier.

const Node &	node (int i) const
	Just to access the nodes a little bit easier.

int	numChilds (int i) const
	returns the number of children of node i

int	numPoints () const
	returns the number of points the quadtree contains

int	numPoints (int i) const
	returns the number of points covered by this subtree

const Point &	point (int i) const
	returns the ith point in the input sequence

int	point (int i, int j) const
	returns the index of the jth point covered by i's subtree.

void	prepareMortonOrder ()
	Prepares the morton numbers for sorting.

void	prepareNodeLayer ()
	Prepares both the leaf and inner node layer.

int	rootIndex () const
	returns the index of the root node

void	setPoint (int i, int d, IntType value)
	sets the point to the given grid coords

void	sortMortonNumbers ()
	Sorts the points by morton number.

Static Public Attributes
static constexpr int	MaxNumChildrenPerNode = (1 << Dim)
	the maximum number of children per node = 2^d

Private Member Functions
void	allocate (int n)
	Allocates memory for n points.

void	deallocate ()
	Releases memory.

Private Attributes
int	m_maxLevel

MortonEntry *	m_mortonOrder = nullptr
	The order to be sorted.

Node *	m_nodes = nullptr
	Memory for all nodes.

int	m_numPoints
	Total number of points.

Point *	m_points = nullptr
	The input set.

int	m_rootIndex
	The index of the root node.

Detailed Description

template<typename IntType, int Dim>
class ogdf::energybased::dtree::DTree< IntType, Dim >

Implentation of the reduced quadtree for Dim dimensions.

Definition at line 41 of file DTree.h.

Constructor & Destructor Documentation

◆ DTree()

template<typename IntType , int Dim>

ogdf::energybased::dtree::DTree< IntType, Dim >::DTree ( int numPoints )

inlineexplicit

constructor

Definition at line 47 of file DTree.h.

◆ ~DTree()

template<typename IntType , int Dim>

ogdf::energybased::dtree::DTree< IntType, Dim >::~DTree ( )

inline

destructor

Definition at line 53 of file DTree.h.

Member Function Documentation

◆ adjustPointInfo()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::adjustPointInfo ( int curr )

inline

used to update the first and numPoints of inner nodes by linkNodes

Definition at line 281 of file DTree.h.

◆ allocate()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::allocate ( int n )

private

Allocates memory for n points.

allocates memory for n points

Definition at line 167 of file DTree.h.

◆ build()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::build ( )

Does all required steps except the allocate, deallocate, randomPoints.

link the inner nodes using the recursive bottom-up method

Definition at line 349 of file DTree.h.

◆ child()

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::child	(	int	i,
		int	j
	)		const

inline

returns the index of the j th child of node i

Definition at line 97 of file DTree.h.

◆ countPoints() [1/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::countPoints ( ) const

inline

Just for fun: traverse the tree and count the points in the leaves.

Definition at line 145 of file DTree.h.

◆ countPoints() [2/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::countPoints ( int curr ) const

Just for fun: traverse the tree and count the points in the leaves.

Definition at line 334 of file DTree.h.

◆ deallocate()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::deallocate ( )

private

Releases memory.

releases memory

Definition at line 176 of file DTree.h.

◆ linkNodes() [1/2]

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::linkNodes ( )

The Recursive Bottom-Up Construction (recursion start)

Definition at line 328 of file DTree.h.

◆ linkNodes() [2/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::linkNodes	(	int	curr,
		int	maxLevel
	)

The Recursive Bottom-Up Construction.

Definition at line 295 of file DTree.h.

◆ maxNumNodes()

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::maxNumNodes ( ) const

inline

returns the maximum number of nodes (and the max index of a node)

Definition at line 112 of file DTree.h.

◆ mergeWithNext()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::mergeWithNext ( int curr )

inline

Merges curr with next node in the chain (used by linkNodes)

Definition at line 268 of file DTree.h.

◆ node() [1/2]

template<typename IntType , int Dim>

Node & ogdf::energybased::dtree::DTree< IntType, Dim >::node ( int i )

inline

Just to access the nodes a little bit easier.

Definition at line 91 of file DTree.h.

◆ node() [2/2]

template<typename IntType , int Dim>

const Node & ogdf::energybased::dtree::DTree< IntType, Dim >::node ( int i ) const

inline

Just to access the nodes a little bit easier.

Definition at line 88 of file DTree.h.

◆ numChilds()

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::numChilds ( int i ) const

inline

returns the number of children of node i

Definition at line 94 of file DTree.h.

◆ numPoints() [1/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::numPoints ( ) const

inline

returns the number of points the quadtree contains

Definition at line 109 of file DTree.h.

◆ numPoints() [2/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::numPoints ( int i ) const

inline

returns the number of points covered by this subtree

Definition at line 100 of file DTree.h.

◆ point() [1/2]

template<typename IntType , int Dim>

const Point & ogdf::energybased::dtree::DTree< IntType, Dim >::point ( int i ) const

inline

returns the ith point in the input sequence

Definition at line 115 of file DTree.h.

◆ point() [2/2]

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::point	(	int	i,
		int	j
	)		const

inline

returns the index of the jth point covered by i's subtree.

Definition at line 103 of file DTree.h.

◆ prepareMortonOrder()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::prepareMortonOrder ( )

Prepares the morton numbers for sorting.

Definition at line 190 of file DTree.h.

◆ prepareNodeLayer()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::prepareNodeLayer ( )

Prepares both the leaf and inner node layer.

Definition at line 210 of file DTree.h.

◆ rootIndex()

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::rootIndex ( ) const

inline

returns the index of the root node

Definition at line 148 of file DTree.h.

◆ setPoint()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::setPoint	(	int	i,
		int	d,
		IntType	value
	)

sets the point to the given grid coords

Definition at line 183 of file DTree.h.

◆ sortMortonNumbers()

template<typename IntType , int Dim>

void ogdf::energybased::dtree::DTree< IntType, Dim >::sortMortonNumbers ( )

Sorts the points by morton number.

Definition at line 203 of file DTree.h.

Member Data Documentation

◆ m_maxLevel

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::m_maxLevel

private

Definition at line 157 of file DTree.h.

◆ m_mortonOrder

template<typename IntType , int Dim>

MortonEntry* ogdf::energybased::dtree::DTree< IntType, Dim >::m_mortonOrder = nullptr

private

The order to be sorted.

Definition at line 160 of file DTree.h.

◆ m_nodes

template<typename IntType , int Dim>

Node* ogdf::energybased::dtree::DTree< IntType, Dim >::m_nodes = nullptr

private

Memory for all nodes.

Definition at line 161 of file DTree.h.

◆ m_numPoints

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::m_numPoints

private

Total number of points.

Definition at line 159 of file DTree.h.

◆ m_points

template<typename IntType , int Dim>

Point* ogdf::energybased::dtree::DTree< IntType, Dim >::m_points = nullptr

private

The input set.

Definition at line 158 of file DTree.h.

◆ m_rootIndex

template<typename IntType , int Dim>

int ogdf::energybased::dtree::DTree< IntType, Dim >::m_rootIndex

private

The index of the root node.

Definition at line 162 of file DTree.h.

◆ MaxNumChildrenPerNode

template<typename IntType , int Dim>

constexpr int ogdf::energybased::dtree::DTree< IntType, Dim >::MaxNumChildrenPerNode = (1 << Dim)

staticconstexpr

the maximum number of children per node = 2^d

Definition at line 44 of file DTree.h.

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

include/ogdf/energybased/dtree/DTree.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ DTree()

◆ ~DTree()

Member Function Documentation

◆ adjustPointInfo()

◆ allocate()

◆ build()

◆ child()

◆ countPoints() [1/2]

◆ countPoints() [2/2]

◆ deallocate()

◆ linkNodes() [1/2]

◆ linkNodes() [2/2]

◆ maxNumNodes()

◆ mergeWithNext()

◆ node() [1/2]

◆ node() [2/2]

◆ numChilds()

◆ numPoints() [1/2]

◆ numPoints() [2/2]

◆ point() [1/2]

◆ point() [2/2]

◆ prepareMortonOrder()

◆ prepareNodeLayer()

◆ rootIndex()

◆ setPoint()

◆ sortMortonNumbers()

Member Data Documentation

◆ m_maxLevel

◆ m_mortonOrder

◆ m_nodes

◆ m_numPoints

◆ m_points

◆ m_rootIndex

◆ MaxNumChildrenPerNode

Open
Graph Drawing
Framework