kdtree.h

Go to the documentation of this file.

#ifndef KDTREE_H
#define KDTREE_H

#include <QList>
#include <QRect>

#include "drawable/drawable.h"
#include "drawable/drawablecontext.h"
#include "drawable/drawablemuselement.h"

#include "core/kdtree.h"
#include "core/muselement.h"
#include "core/playable.h"
#include "core/voice.h"

/*class Node {
public:
        CADrawable *elt;              // pointer to the element
        CADrawable *right, *left; // pointer to the left/right son
        int x1,y1,x2,y2;              // element keys
};*/

template <typename T>
class CAKDTree {
public:
        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);
        inline int size() { return _list.size(); }
        T at(int i) { return _list[i]; }
        QList<T>& list() { return _list; }

private:
        // Basic properties //
        QList<T> _list;        // List of all the drawable elements.
        double _maxX, _maxY;   // MaxX and MaxY bound of the end of the most-right and the most-bottom elements.

        void calculateMaxXY();
};

template <typename T>
CAKDTree<T>::CAKDTree() {
        _maxX = 0;
        _maxY = 0;
}

template <typename T>
void CAKDTree<T>::addElement(T elt) {
        _list << elt;

        if (static_cast<CADrawable*>(elt)->xPos() + static_cast<CADrawable*>(elt)->width() > _maxX)
                _maxX = static_cast<CADrawable*>(elt)->xPos() + static_cast<CADrawable*>(elt)->width();
        if (static_cast<CADrawable*>(elt)->yPos() + static_cast<CADrawable*>(elt)->height() > _maxY)
                _maxY = static_cast<CADrawable*>(elt)->yPos() + static_cast<CADrawable*>(elt)->height();
}

template <typename T>
bool CAKDTree<T>::removeElement(T elt) {
        delete elt;

        return _list.removeAll(elt);
}

template <typename T>
T CAKDTree<T>::removeElement(double x, double y, bool autoDelete) {
        T elt;
        for (int i=0; i<_list.size(); i++) {
                if (static_cast<CADrawable*>(_list.at(i))->bBox().contains(x,y)) {
                        elt = _list[i];
                        _list.removeAt(i);
                        if (autoDelete) delete elt;

                        calculateMaxXY();

                        return elt;
                }
        }

        return 0;
}

template <typename T>
void CAKDTree<T>::clear(bool autoDelete) {
        if (autoDelete) {
                for (int i=0; i<_list.size(); i++)
                        delete _list[i];
        }

        _list.clear();
}
#include <iostream>
template <typename T>
QList<T> CAKDTree<T>::findInRange(double x, double y, double w, double h) {
        QList<T> l;

        for (int i=0; i<_list.size(); i++) {
                if ( ((static_cast<CADrawable*>(_list[i])->xPos() <= x+w) &&                       // The object is normal and fits into the area
                      (static_cast<CADrawable*>(_list[i])->yPos() <= y+h) &&
                      (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() >= x) &&
                      (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() >= y)) ||
                     ((static_cast<CADrawable*>(_list[i])->width() == 0) &&                        // The object is unlimited in width (eg. contexts)
                      (static_cast<CADrawable*>(_list[i])->yPos() <= y+h) &&
                      (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() >= y)) ||
                     ((static_cast<CADrawable*>(_list[i])->height() == 0) &&                       // The object is unlimited in height (eg. helper lines)
                      (static_cast<CADrawable*>(_list[i])->xPos() <= x+w) &&
                      (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() >= x))
                    ) {
                        l << _list[i];
                }
        }

        return l;
}

template <typename T>
QList<T> CAKDTree<T>::findInRange(QRect &rect) {
        return findInRange(rect.x(), rect.y(), rect.width(), rect.height());
}

template <typename T>
T CAKDTree<T>::findNearestLeft(double x, bool timeBased, CADrawableContext *context, CAVoice *voice) {
        if (_list.isEmpty())
                return 0;

        CADrawable *elt=0;
        int i;
        for (i=0; i < _list.size(); i++) {
                if ( static_cast<CADrawableMusElement*>(_list[i])->musElement() && // drawable must have a music element
                        ( !elt || (timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos()) > (timeBased?elt->xPos():elt->xPos()) ) && // element's X is lesser than the already found element's X
                     ( ( timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos() ) < x) && // element's X is lesser than the given X
                     ( !context  || static_cast<CADrawableMusElement*>(_list[i])->drawableContext() == context ) && // compare contexts
                     ( !voice || // compare voices
                       (
                         !(static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element isn't playable, see if it has the same context as the voice
                         ((static_cast<CADrawableMusElement*>(_list[i]))->musElement()->context() == voice->staff() && voice->contains(static_cast<CADrawableMusElement*>(_list[i])->musElement()))
                         ||
                         (static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element is playable, see if it has the exactly same voice
                         static_cast<CAPlayable*>(static_cast<CADrawableMusElement*>(_list[i])->musElement())->voice() == voice
                      )
                         )
                   ) {
                        elt = static_cast<CADrawable*>(_list[i]);
                }
        }

        return static_cast<T>(elt);
}

template <typename T>
T CAKDTree<T>::findNearestRight(double x, bool timeBased, CADrawableContext *context, CAVoice *voice) {
        if (_list.isEmpty())
                return 0;

        CADrawable *elt=0;
        int i;
        for (i=0; i < _list.size(); i++) {
                if ( static_cast<CADrawableMusElement*>(_list[i])->musElement() && // drawable must have a music element
                         ( !elt || (timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos()) < (timeBased?elt->xPos():elt->xPos()) ) && // element's X is greater than the already found element's X
                     ( ( timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos() ) > x) && // element's X is lesser than the given X
                     ( !context  || static_cast<CADrawableMusElement*>(_list[i])->drawableContext() == context ) && // compare contexts
                     ( !voice || // compare voices
                       (
                         !(static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element isn't playable, see if it has the same context as the voice
                         ((static_cast<CADrawableMusElement*>(_list[i]))->musElement()->context() == voice->staff() && voice->contains((static_cast<CADrawableMusElement*>(_list[i]))->musElement()))
                         ||
                         (static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element is playable, see if it has the exactly same voice
                         static_cast<CAPlayable*>(static_cast<CADrawableMusElement*>(_list[i])->musElement())->voice() == voice
                       )
                     )
                   ) {
                        elt = static_cast<CADrawable*>(_list[i]);
                }
        }

        return static_cast<T>(elt);
}

template <typename T>
T CAKDTree<T>::findNearestUp(double y) {
        if (_list.isEmpty())
                return 0;

        CADrawable *elt=0;
        int i;
        for (i=0; i<_list.size(); i++) {
                if ( ((!elt) || ((static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height()) > (elt->yPos() + elt->height())))
                      && ((static_cast<CADrawable*>(_list[i])->yPos()+ static_cast<CADrawable*>(_list[i])->height()) < y) ) {
                        elt = static_cast<CADrawable*>(_list[i]);
                }
        }
        return static_cast<T>(elt);

}

template <typename T>
T CAKDTree<T>::findNearestDown(double y) {
        if (_list.isEmpty())
                return 0;

        CADrawable *elt=0;
        int i;
        for (i=0; i<_list.size(); i++) {
                if ( ((!elt) || (static_cast<CADrawable*>(_list[i])->yPos() < elt->yPos())) && (static_cast<CADrawable*>(_list[i])->yPos() > y) ) {
                        elt = static_cast<CADrawable*>(_list[i]);
                }
        }

        return static_cast<T>(elt);
}

template <typename T>
double CAKDTree<T>::getMaxX() {
        return _maxX;
}

template <typename T>
double CAKDTree<T>::getMaxY() {
        return _maxY;
}

template <typename T>
void CAKDTree<T>::calculateMaxXY() {
        _maxX = 0;
        _maxY = 0;
        for (int i=0; i<_list.size(); i++) {
                if (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() > _maxX)
                        _maxX = static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width();
                if (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() > _maxY)
                        _maxY = static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height();
        }
}

template <typename T>
void CAKDTree<T>::import(CAKDTree *tree) {
        for (int i=0; i<tree->list().size(); i++)
                _list += tree->list().at(i)->clone();

        calculateMaxXY();
}
#endif