Space partitioning structure for fast access to drawable elements on canvas. More...

#include <kdtree.h>

Inheritance diagram for CAKDTree< T >:

Public Member Functions
	CAKDTree ()

void	addElement (T elt)

bool	removeElement (T elt)

T	removeElement (double x, double y, bool autoDelete=true)

void	import (CAKDTree *tree)

QList< T >	findInRange (double x, double y, double w=0, double h=0)

QList< T >	findInRange (QRect &area)

T	findNearestLeft (double x, bool timeBased=false, CADrawableContext context=0, CAVoice voice=0)

T	findNearestRight (double x, bool timeBased=false, CADrawableContext context=0, CAVoice voice=0)

T	findNearestUp (double y)

T	findNearestDown (double y)

double	getMaxX ()

double	getMaxY ()

void	clear (bool autoDelete=true)

int	size ()

T	at (int i)

QList< T > &	list ()

Private Member Functions
void	calculateMaxXY ()

Private Attributes
QList< T >	_list

double	_maxX

double	_maxY

Detailed Description

template<typename T>
class CAKDTree< T >

Space partitioning structure for fast access to drawable elements on canvas.

Licensed under the GNU GENERAL PUBLIC LICENSE. See LICENSE.GPL for details.

kd-tree is usually used for description of the music elements on the canvas. It's used for fast insertion/lookup of a list of elements in the given region. Each canvas has its own kd-tree of drawable elements. One for contexts and the other for music elements.

Canorus kd-tree is a template class which requires derivates of CADrawable base class elements to work.

See http://en.wikipedia.org/wiki/Kd_tree

Todo:: Currently, an ordinary vector is used. No tree structure present yet, so all the operations are slow - O(n).

See Also: CAScoreViewPort, CADrawable

Constructor & Destructor Documentation

template<typename T >

CAKDTree< T >::CAKDTree ( )

The default constructor.

Member Function Documentation

template<typename T>

void CAKDTree< T >::addElement ( T elt )

Adds a drawable element elt to the tree.

References CADrawable::yPos().

Referenced by CAScoreViewPort::addCElement(), CAScoreViewPort::addMElement(), and CAScoreViewPort::coordsToTime().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T>

T CAKDTree< T >::at ( int i )

inline

Referenced by CAScoreViewPort::addToSelection(), CAScoreViewPort::findCElement(), CAScoreViewPort::findMElement(), CAScoreViewPort::importCElements(), CAScoreViewPort::importElements(), CAScoreViewPort::importMElements(), CAScoreViewPort::invertSelection(), CAScoreViewPort::selectAll(), CAScoreViewPort::selectContext(), CAScoreViewPort::selectMElement(), CAScoreViewPort::setLastMousePressCoordsAfter(), CAScoreViewPort::timeToCoords(), and CAScoreViewPort::timeToCoordsSimpleVersion().

Here is the caller graph for this function:

template<typename T >

void CAKDTree< T >::calculateMaxXY ( )

private

Used internally for the maxX and maxY properties to update. Calculates the largest X and Y coordinates among all ends of elements and store it locally. This operation takes O(n) time complexity where n is number of elements in the tree.

References CADrawable::yPos().

Here is the call graph for this function:

template<typename T >

void CAKDTree< T >::clear ( bool autoDelete = true )

Removes all elements from the tree. Also destroys the elements if autoDelete is true.

Referenced by CAScoreViewPort::clearCElements(), CAScoreViewPort::clearMElements(), CAScoreViewPort::rebuild(), and CAScoreViewPort::~CAScoreViewPort().

Here is the caller graph for this function:

template<typename T >

QList< T > CAKDTree< T >::findInRange	(	double	x,
		double	y,
		double	w = `0`,
		double	h = `0`
	)

Returns the list of elements present in the given rectangular area or an empty list if none found. Element is in the list, if the region only touches it - not neccessarily fits the whole in the region.

Referenced by CAScoreViewPort::contextCollision(), CAScoreViewPort::findContextsInRegion(), CAScoreViewPort::musElementsAt(), CAScoreViewPort::paintEvent(), and CAScoreViewPort::selectCElement().

Here is the caller graph for this function:

template<typename T >

QList< T > CAKDTree< T >::findInRange ( QRect & rect )

This function is provided for convenience. Returns the list of elements present in the given rectangular area or an empty list if none found. Element is in the list, if the region only touches it - not neccessarily fits the whole in the region.

template<typename T >

T CAKDTree< T >::findNearestDown ( double y )

Finds the nearest lower element to the given coordinate and returns a pointer to it or 0 if none found. Top element border is taken into account.

If timeBased is false (default), the lookup should be view-based - the nearest element is selected as it appears on the screen. If timeBased if true, the nearest element is selected according to the nearest start/end time.

References CADrawable::yPos().

Referenced by CAScoreViewPort::nearestDownContext().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

T CAKDTree< T >::findNearestLeft	(	double	x,
		bool	timeBased = `false`,
		CADrawableContext *	context = `0`,
		CAVoice *	voice = `0`
	)

Finds the nearest left element to the given coordinate and returns a pointer to it or 0 if none found. Left elements borders are taken into account.

If timeBased is false (default), the lookup should be view-based - the nearest element is selected as it appears on the screen. If timeBased if true, the nearest element is selected according to the nearest start/end time.

References CAVoice::contains(), CAVoice::staff(), and CADrawable::xPos().

Referenced by CAScoreViewPort::calculateTime(), and CAScoreViewPort::nearestLeftElement().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

T CAKDTree< T >::findNearestRight	(	double	x,
		bool	timeBased = `false`,
		CADrawableContext *	context = `0`,
		CAVoice *	voice = `0`
	)

Finds the nearest right element to the given coordinate and returns a pointer to it or 0 if none found. Left elements borders are taken into account.

If timeBased is false (default), the lookup should be view-based - the nearest element is selected as it appears on the screen. If timeBased if true, the nearest element is selected according to the nearest start/end time.

References CAVoice::contains(), CAVoice::staff(), and CADrawable::xPos().

Referenced by CAScoreViewPort::calculateTime(), and CAScoreViewPort::nearestRightElement().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

T CAKDTree< T >::findNearestUp ( double y )

Finds the nearest upper element to the given coordinate and returns a pointer to it or 0 if none found. Top element border is taken into account.

If timeBased is false (default), the lookup should be view-based - the nearest element is selected as it appears on the screen. If timeBased if true, the nearest element is selected according to the nearest start/end time.

References CADrawable::height(), and CADrawable::yPos().

Referenced by CAScoreViewPort::nearestUpContext().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

double CAKDTree< T >::getMaxX ( )

Returns the max X coordinate of the end of the most-right element. This value is read from buffer, so the calculation time is constant.

Referenced by CAScoreViewPort::getMaxXExtended(), and CAScoreViewPort::zoomToFit().

Here is the caller graph for this function:

template<typename T >

double CAKDTree< T >::getMaxY ( )

Returns the max Y coordinate of the end of the most-bottom element. This value is read from buffer, so the calculation time is constant.

Referenced by CAScoreViewPort::getMaxYExtended(), and CAScoreViewPort::zoomToFit().

Here is the caller graph for this function:

template<typename T >

void CAKDTree< T >::import ( CAKDTree< T > * tree )

Imports all the elements from the given tree. It actually merges the given tree with this one.

References CAKDTree< T >::list().

Here is the call graph for this function:

template<typename T>

QList<T>& CAKDTree< T >::list ( )

inline

Referenced by CAScoreViewPort::coordsToTime(), CAKDTree< T >::import(), CAScoreViewPort::importElements(), and CAScoreViewPort::rebuild().

Here is the caller graph for this function:

template<typename T>

bool CAKDTree< T >::removeElement ( T elt )

Removes the given element elt from the tree. Returns true, if the given element was found and deleted; otherwise false.

Referenced by CAScoreViewPort::removeMElement().

Here is the caller graph for this function:

template<typename T>

T CAKDTree< T >::removeElement	(	double	x,
		double	y,
		bool	autoDelete = `true`
	)

Removes the first element at the given x and y absolute world coordinates and returns the pointer to this element, if successful. Destroys element, if autoDelete is true. Returns pointer to the deleted element or null, if no element found at the given coordinates.

template<typename T>

int CAKDTree< T >::size ( )

inline

Returns the number of elements currently in the tree.

Referenced by CAScoreViewPort::addToSelection(), CAScoreViewPort::findCElement(), CAScoreViewPort::findMElement(), CAScoreViewPort::importCElements(), CAScoreViewPort::importElements(), CAScoreViewPort::importMElements(), CAScoreViewPort::invertSelection(), CAScoreViewPort::paintEvent(), CAScoreViewPort::rebuild(), CAScoreViewPort::selectAll(), CAScoreViewPort::selectContext(), CAScoreViewPort::selectMElement(), CAScoreViewPort::setLastMousePressCoordsAfter(), CAScoreViewPort::timeToCoords(), and CAScoreViewPort::timeToCoordsSimpleVersion().

Here is the caller graph for this function:

Member Data Documentation

template<typename T>

QList<T> CAKDTree< T >::_list

private

Referenced by CAKDTree< CADrawableMusElement * >::at(), CAKDTree< CADrawableMusElement * >::list(), and CAKDTree< CADrawableMusElement * >::size().

template<typename T>

double CAKDTree< T >::_maxX

private

template<typename T>

double CAKDTree< T >::_maxY

private

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

/home/iurt/rpmbuild/BUILD/canorus-0.7.R1002/src/core/kdtree.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename T> class CAKDTree< T >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class CAKDTree< T >