Hilbert_TGSinsert_tree< base_tree > Class Template Reference

#include <HilbertTGSinsert.h>

Inherits TGS_tree< base_tree >< base_tree >.

Inheritance diagram for Hilbert_TGSinsert_tree< base_tree >:

[legend]Collaboration diagram for Hilbert_TGSinsert_tree< base_tree >:


Public Member Functions
	Hilbert_TGSinsert_tree ()
	Hilbert_TGSinsert_tree (R_tree_props *props)
virtual base_tree *	insert (BB_container *element)
Protected Member Functions
virtual vector< Ordering< BB_container > * >	useOrderings () const
Private Member Functions
void	insertionSort (BB_container *element)
unsigned int	lowestGeqThan (const double currentVal, const unsigned int left, const unsigned int right) const
Private Attributes
vector< double >	hilbertCache

Detailed Description

template<typename base_tree>
class Hilbert_TGSinsert_tree< base_tree >

Same as Hilbert_TGS_tree, but instead of pre-caching and then applying quicksort, we now apply insertion sort.

NOTE: Due to implementation using a vector, this method is outperformed by the original Hilbert_TGS_tree. A linked-list would be better, but then the insertion sort algorithm is harder to implement efficiently.

Definition at line 27 of file HilbertTGSinsert.h.

Constructor & Destructor Documentation

template<typename base_tree>

Hilbert_TGSinsert_tree< base_tree >::Hilbert_TGSinsert_tree ( ) [inline]

Inherited constructor.

Definition at line 59 of file HilbertTGSinsert.h.

template<typename base_tree>

Hilbert_TGSinsert_tree< base_tree >::Hilbert_TGSinsert_tree ( R_tree_props * props ) [inline]

Inherited constructor.

Definition at line 62 of file HilbertTGSinsert.h.

Member Function Documentation

template<typename base_tree>

void Hilbert_TGSinsert_tree< base_tree >::insertionSort ( BB_container * element ) [inline, private]

The actual insertion sort algorithm.

Parameters:

element

Pointer to the element needed to be inserted into the cache.

Definition at line 85 of file HilbertTGSinsert.h.

References TGS_tree< base_tree >::cache, Cubic_Bounding_Box::getCenterCoordinate(), Hilbert_TGSinsert_tree< base_tree >::hilbertCache, Hilbert_TGSinsert_tree< base_tree >::lowestGeqThan(), and HilbertCoordinateMapper::toHilbert3D().

Referenced by Hilbert_TGSinsert_tree< base_tree >::insert().

template<typename base_tree>

unsigned int Hilbert_TGSinsert_tree< base_tree >::lowestGeqThan	(	const double	currentVal,
		const unsigned int	left,
		const unsigned int	right
	)			const `[inline, private]`

Searches and returns the index of the first element in the cache with a higher Hilbert value. Hilbert values are not continuously re-calculated - they are cached.

Parameters: