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

#include <kdtree.h>

Inheritance diagram for CAKDTree< T >:

[legend]

Public Member Functions
	CAKDTree ()

void	addElement (T elt)

T	removeElement (double x, double y)

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 ()

QList< T >	list ()

Private Member Functions
void	calculateMaxY ()

Private Attributes
QMultiMap< double, T >	_mapX

QMultiMap< double, T >	_mapXW

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.

This class is a data structure focused on efficient access to the drawable instances of the music elements. It is based on an interval tree and employs multiple QMap instances to enable efficient query of elements in the given interval, finding the next element in the same staff and mapping a music element to one or more drawable instances.

See also: CAScoreView, CADrawable

Constructor & Destructor Documentation

◆ CAKDTree()

template<typename T >

CAKDTree< T >::CAKDTree

The default constructor.

Member Function Documentation

◆ addElement()

template<typename T >

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

Adds a drawable element elt to the tree.

Referenced by CAScoreView::addCElement(), CAScoreView::addDrawableNoteCheckerError(), and CAScoreView::addMElement().

Here is the caller graph for this function:

◆ calculateMaxY()

template<typename T >

void CAKDTree< T >::calculateMaxY

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.

◆ clear()

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 CAScoreView::clearCElements(), CAScoreView::clearMElements(), CAScoreView::rebuild(), and CAScoreView::~CAScoreView().

Here is the caller graph for this function:

◆ findInRange() [1/2]

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 CAScoreView::contextCollision(), CAScoreView::findContextsInRegion(), CAScoreView::musElementsAt(), CAScoreView::paintEvent(), and CAScoreView::selectCElement().

Here is the caller graph for this function:

◆ findInRange() [2/2]

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.

◆ findNearestDown()

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.

Referenced by CAScoreView::nearestDownContext().

Here is the caller graph for this function:

◆ findNearestLeft()

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::staff(), and CAPlayable::voice().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findNearestRight()

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::staff(), and CAPlayable::voice().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findNearestUp()

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.

Referenced by CAScoreView::nearestUpContext().

Here is the caller graph for this function: