|
Canorus
0.7
|
|
Canorus
0.7
|
00001 00008 #ifndef KDTREE_H 00009 #define KDTREE_H 00010 00011 #include <QList> 00012 #include <QRect> 00013 00014 #include "drawable/drawable.h" 00015 #include "drawable/drawablecontext.h" 00016 #include "drawable/drawablemuselement.h" 00017 00018 #include "core/kdtree.h" 00019 #include "core/muselement.h" 00020 #include "core/playable.h" 00021 #include "core/voice.h" 00022 00023 /*class Node { 00024 public: 00025 CADrawable *elt; // pointer to the element 00026 CADrawable *right, *left; // pointer to the left/right son 00027 int x1,y1,x2,y2; // element keys 00028 };*/ 00029 00030 template <typename T> 00031 class CAKDTree { 00032 public: 00033 CAKDTree(); 00034 00035 void addElement(T elt); 00036 bool removeElement(T elt); 00037 T removeElement(double x, double y, bool autoDelete=true); 00038 void import(CAKDTree *tree); 00039 00040 QList<T> findInRange(double x, double y, double w=0, double h=0); 00041 QList<T> findInRange(QRect &area); 00042 T findNearestLeft(double x, bool timeBased=false, CADrawableContext *context=0, CAVoice *voice=0); 00043 T findNearestRight(double x, bool timeBased=false, CADrawableContext *context=0, CAVoice *voice=0); 00044 T findNearestUp(double y); 00045 T findNearestDown(double y); 00046 00047 double getMaxX(); 00048 double getMaxY(); 00049 00050 void clear(bool autoDelete=true); 00051 inline int size() { return _list.size(); } 00052 T at(int i) { return _list[i]; } 00053 QList<T>& list() { return _list; } 00054 00055 private: 00057 // Basic properties // 00059 QList<T> _list; // List of all the drawable elements. 00060 double _maxX, _maxY; // MaxX and MaxY bound of the end of the most-right and the most-bottom elements. 00061 00062 void calculateMaxXY(); 00063 }; 00064 00086 template <typename T> 00087 CAKDTree<T>::CAKDTree() { 00088 _maxX = 0; 00089 _maxY = 0; 00090 } 00091 00095 template <typename T> 00096 void CAKDTree<T>::addElement(T elt) { 00097 _list << elt; 00098 00099 if (static_cast<CADrawable*>(elt)->xPos() + static_cast<CADrawable*>(elt)->width() > _maxX) 00100 _maxX = static_cast<CADrawable*>(elt)->xPos() + static_cast<CADrawable*>(elt)->width(); 00101 if (static_cast<CADrawable*>(elt)->yPos() + static_cast<CADrawable*>(elt)->height() > _maxY) 00102 _maxY = static_cast<CADrawable*>(elt)->yPos() + static_cast<CADrawable*>(elt)->height(); 00103 } 00104 00109 template <typename T> 00110 bool CAKDTree<T>::removeElement(T elt) { 00111 delete elt; 00112 00113 return _list.removeAll(elt); 00114 } 00115 00121 template <typename T> 00122 T CAKDTree<T>::removeElement(double x, double y, bool autoDelete) { 00123 T elt; 00124 for (int i=0; i<_list.size(); i++) { 00125 if (static_cast<CADrawable*>(_list.at(i))->bBox().contains(x,y)) { 00126 elt = _list[i]; 00127 _list.removeAt(i); 00128 if (autoDelete) delete elt; 00129 00130 calculateMaxXY(); 00131 00132 return elt; 00133 } 00134 } 00135 00136 return 0; 00137 } 00138 00143 template <typename T> 00144 void CAKDTree<T>::clear(bool autoDelete) { 00145 if (autoDelete) { 00146 for (int i=0; i<_list.size(); i++) 00147 delete _list[i]; 00148 } 00149 00150 _list.clear(); 00151 } 00152 #include <iostream> 00157 template <typename T> 00158 QList<T> CAKDTree<T>::findInRange(double x, double y, double w, double h) { 00159 QList<T> l; 00160 00161 for (int i=0; i<_list.size(); i++) { 00162 if ( ((static_cast<CADrawable*>(_list[i])->xPos() <= x+w) && // The object is normal and fits into the area 00163 (static_cast<CADrawable*>(_list[i])->yPos() <= y+h) && 00164 (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() >= x) && 00165 (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() >= y)) || 00166 ((static_cast<CADrawable*>(_list[i])->width() == 0) && // The object is unlimited in width (eg. contexts) 00167 (static_cast<CADrawable*>(_list[i])->yPos() <= y+h) && 00168 (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() >= y)) || 00169 ((static_cast<CADrawable*>(_list[i])->height() == 0) && // The object is unlimited in height (eg. helper lines) 00170 (static_cast<CADrawable*>(_list[i])->xPos() <= x+w) && 00171 (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() >= x)) 00172 ) { 00173 l << _list[i]; 00174 } 00175 } 00176 00177 return l; 00178 } 00179 00185 template <typename T> 00186 QList<T> CAKDTree<T>::findInRange(QRect &rect) { 00187 return findInRange(rect.x(), rect.y(), rect.width(), rect.height()); 00188 } 00189 00198 template <typename T> 00199 T CAKDTree<T>::findNearestLeft(double x, bool timeBased, CADrawableContext *context, CAVoice *voice) { 00200 if (_list.isEmpty()) 00201 return 0; 00202 00203 CADrawable *elt=0; 00204 int i; 00205 for (i=0; i < _list.size(); i++) { 00206 if ( static_cast<CADrawableMusElement*>(_list[i])->musElement() && // drawable must have a music element 00207 ( !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 00208 ( ( timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos() ) < x) && // element's X is lesser than the given X 00209 ( !context || static_cast<CADrawableMusElement*>(_list[i])->drawableContext() == context ) && // compare contexts 00210 ( !voice || // compare voices 00211 ( 00212 !(static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element isn't playable, see if it has the same context as the voice 00213 ((static_cast<CADrawableMusElement*>(_list[i]))->musElement()->context() == voice->staff() && voice->contains(static_cast<CADrawableMusElement*>(_list[i])->musElement())) 00214 || 00215 (static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element is playable, see if it has the exactly same voice 00216 static_cast<CAPlayable*>(static_cast<CADrawableMusElement*>(_list[i])->musElement())->voice() == voice 00217 ) 00218 ) 00219 ) { 00220 elt = static_cast<CADrawable*>(_list[i]); 00221 } 00222 } 00223 00224 return static_cast<T>(elt); 00225 } 00226 00235 template <typename T> 00236 T CAKDTree<T>::findNearestRight(double x, bool timeBased, CADrawableContext *context, CAVoice *voice) { 00237 if (_list.isEmpty()) 00238 return 0; 00239 00240 CADrawable *elt=0; 00241 int i; 00242 for (i=0; i < _list.size(); i++) { 00243 if ( static_cast<CADrawableMusElement*>(_list[i])->musElement() && // drawable must have a music element 00244 ( !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 00245 ( ( timeBased?(static_cast<CADrawable*>(_list[i]))->xPos():(static_cast<CADrawable*>(_list[i]))->xPos() ) > x) && // element's X is lesser than the given X 00246 ( !context || static_cast<CADrawableMusElement*>(_list[i])->drawableContext() == context ) && // compare contexts 00247 ( !voice || // compare voices 00248 ( 00249 !(static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element isn't playable, see if it has the same context as the voice 00250 ((static_cast<CADrawableMusElement*>(_list[i]))->musElement()->context() == voice->staff() && voice->contains((static_cast<CADrawableMusElement*>(_list[i]))->musElement())) 00251 || 00252 (static_cast<CADrawableMusElement*>(_list[i]))->musElement()->isPlayable() && // if the element is playable, see if it has the exactly same voice 00253 static_cast<CAPlayable*>(static_cast<CADrawableMusElement*>(_list[i])->musElement())->voice() == voice 00254 ) 00255 ) 00256 ) { 00257 elt = static_cast<CADrawable*>(_list[i]); 00258 } 00259 } 00260 00261 return static_cast<T>(elt); 00262 } 00263 00272 template <typename T> 00273 T CAKDTree<T>::findNearestUp(double y) { 00274 if (_list.isEmpty()) 00275 return 0; 00276 00277 CADrawable *elt=0; 00278 int i; 00279 for (i=0; i<_list.size(); i++) { 00280 if ( ((!elt) || ((static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height()) > (elt->yPos() + elt->height()))) 00281 && ((static_cast<CADrawable*>(_list[i])->yPos()+ static_cast<CADrawable*>(_list[i])->height()) < y) ) { 00282 elt = static_cast<CADrawable*>(_list[i]); 00283 } 00284 } 00285 return static_cast<T>(elt); 00286 00287 } 00288 00297 template <typename T> 00298 T CAKDTree<T>::findNearestDown(double y) { 00299 if (_list.isEmpty()) 00300 return 0; 00301 00302 CADrawable *elt=0; 00303 int i; 00304 for (i=0; i<_list.size(); i++) { 00305 if ( ((!elt) || (static_cast<CADrawable*>(_list[i])->yPos() < elt->yPos())) && (static_cast<CADrawable*>(_list[i])->yPos() > y) ) { 00306 elt = static_cast<CADrawable*>(_list[i]); 00307 } 00308 } 00309 00310 return static_cast<T>(elt); 00311 } 00312 00317 template <typename T> 00318 double CAKDTree<T>::getMaxX() { 00319 return _maxX; 00320 } 00321 00326 template <typename T> 00327 double CAKDTree<T>::getMaxY() { 00328 return _maxY; 00329 } 00330 00336 template <typename T> 00337 void CAKDTree<T>::calculateMaxXY() { 00338 _maxX = 0; 00339 _maxY = 0; 00340 for (int i=0; i<_list.size(); i++) { 00341 if (static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width() > _maxX) 00342 _maxX = static_cast<CADrawable*>(_list[i])->xPos() + static_cast<CADrawable*>(_list[i])->width(); 00343 if (static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height() > _maxY) 00344 _maxY = static_cast<CADrawable*>(_list[i])->yPos() + static_cast<CADrawable*>(_list[i])->height(); 00345 } 00346 } 00347 00352 template <typename T> 00353 void CAKDTree<T>::import(CAKDTree *tree) { 00354 for (int i=0; i<tree->list().size(); i++) 00355 _list += tree->list().at(i)->clone(); 00356 00357 calculateMaxXY(); 00358 } 00359 #endif 00360
1.8.0
