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:

◆ getMaxX()

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 CAScoreView::getMaxXExtended(), and CAScoreView::zoomToFit().

Here is the caller graph for this function:

◆ getMaxY()

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 CAScoreView::getMaxYExtended(), and CAScoreView::zoomToFit().

Here is the caller graph for this function:

◆ list()

template<typename T >

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

inline

Referenced by CAScoreView::computeBarlinePositions(), CAScoreView::importElements(), CAScoreView::invertSelection(), CAScoreView::rebuild(), CAScoreView::selectAll(), and CAScoreView::selectContext().

Here is the caller graph for this function:

◆ removeElement()

template<typename T >

T CAKDTree< T >::removeElement	(	double	x,
		double	y
	)

◆ size()

template<typename T >

int CAKDTree< T >::size ( )

inline

Returns the number of elements currently in the tree.

Referenced by CAScoreView::rebuild().

Here is the caller graph for this function:

Member Data Documentation

◆ _mapX

template<typename T >

QMultiMap<double, T> CAKDTree< T >::_mapX

private

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

◆ _mapXW

template<typename T >

QMultiMap<double, T> CAKDTree< T >::_mapXW

private

◆ _maxY

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.3svn20190422/src/layout/kdtree.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename T> class CAKDTree< T >

Constructor & Destructor Documentation

◆ CAKDTree()

Member Function Documentation

◆ addElement()

◆ calculateMaxY()

◆ clear()

◆ findInRange() [1/2]

◆ findInRange() [2/2]

◆ findNearestDown()

◆ findNearestLeft()

◆ findNearestRight()

◆ findNearestUp()

◆ getMaxX()

◆ getMaxY()

◆ list()

◆ removeElement()

◆ size()

Member Data Documentation

◆ _mapX

◆ _mapXW

◆ _maxY

template<typename T>
class CAKDTree< T >