1 /* 2 MusicXML Library 3 Copyright (C) Grame 2006-2013 4 5 This Source Code Form is subject to the terms of the Mozilla Public 6 License, v. 2.0. If a copy of the MPL was not distributed with this 7 file, You can obtain one at http://mozilla.org/MPL/2.0/. 8 9 Grame Research Laboratory, 11, cours de Verdun Gensoul 69002 Lyon - France 10 research@grame.fr 11 */ 12 13 #ifndef __ctree__ 14 #define __ctree__ 15 16 #include <iostream> 17 #include <stack> 18 #include <vector> 19 #include <iterator> 20 21 #ifdef WIN32 22 #pragma warning (disable : 4251) 23 #endif 24 25 #include "smartpointer.h" 26 #include "visitable.h" 27 28 namespace MusicXML2 29 { 30 31 //______________________________________________________________________________ 32 template <typename T> class EXP treeIterator : public std::iterator<std::input_iterator_tag, T> 33 { 34 protected: 35 typedef typename std::vector<T>::iterator nodes_iterator; 36 typedef std::pair<nodes_iterator, T> state; 37 38 std::stack<state> fStack; 39 T fRootElement; 40 nodes_iterator fCurrentIterator; 41 42 public: treeIterator()43 treeIterator() {} 44 treeIterator(const T& t, bool end=false) { 45 fRootElement = t; 46 if (end) fCurrentIterator = t->elements().end(); 47 else forward_down (t); 48 } treeIterator(const treeIterator & a)49 treeIterator(const treeIterator& a) { *this = a; } ~treeIterator()50 virtual ~treeIterator() {} 51 52 T operator *() const { return *fCurrentIterator; } 53 T operator ->() const { return *fCurrentIterator; } 54 55 //________________________________________________________________________ getParent()56 T getParent() const { return fStack.size() ? fStack.top().second : fRootElement; } 57 58 //________________________________________________________________________ 59 // current element has sub-elements: go down to sub-elements first forward_down(const T & t)60 virtual void forward_down(const T& t) { 61 fCurrentIterator = t->elements().begin(); 62 if (fCurrentIterator != t->elements().end()) 63 fStack.push( make_pair(fCurrentIterator+1, t)); 64 } 65 66 //________________________________________________________________________ 67 // current element is empty: go up to parent element and possibly down to neighbor element forward_up()68 void forward_up() { 69 while (fStack.size()) { 70 state s = fStack.top(); 71 fStack.pop(); 72 73 fCurrentIterator = s.first; 74 if (fCurrentIterator != s.second->elements().end()) { 75 fStack.push( make_pair(fCurrentIterator+1, s.second)); 76 return; 77 } 78 } 79 } 80 81 //________________________________________________________________________ 82 // move the iterator forward forward()83 void forward() { 84 if ((*fCurrentIterator)->size()) forward_down(*fCurrentIterator); 85 else forward_up(); 86 } 87 treeIterator& operator ++() { forward(); return *this; } 88 treeIterator& operator ++(int) { forward(); return *this; } 89 90 //________________________________________________________________________ erase()91 treeIterator& erase() { 92 T parent = getParent(); 93 fCurrentIterator = parent->elements().erase(fCurrentIterator); 94 if (fStack.size()) fStack.pop(); 95 if (fCurrentIterator != parent->elements().end()) { 96 fStack.push( make_pair(fCurrentIterator+1, parent)); 97 } 98 else forward_up(); 99 return *this; 100 } 101 102 //________________________________________________________________________ insert(const T & value)103 treeIterator& insert(const T& value) { 104 T parent = getParent(); 105 fCurrentIterator = parent->elements().insert(fCurrentIterator, value); 106 if (fStack.size()) fStack.pop(); 107 fStack.push( make_pair(fCurrentIterator+1, parent)); 108 return *this; 109 } 110 111 //________________________________________________________________________ 112 bool operator ==(const treeIterator& i) const { 113 // we check that the iterators have the same parent (due to iterator compatibility issue with visual c++) 114 return getParent() == i.getParent() ? ( fCurrentIterator==i.fCurrentIterator ) : false; 115 } 116 bool operator !=(const treeIterator& i) const { return !(*this == i); } 117 }; 118 119 /*! 120 \brief a simple tree representation 121 */ 122 //______________________________________________________________________________ 123 template <typename T> class EXP ctree : virtual public smartable 124 { 125 public: 126 typedef SMARTP<T> treePtr; ///< the node sub elements type 127 typedef std::vector<treePtr> branchs; ///< the node sub elements container type 128 typedef typename branchs::iterator literator; ///< the current level iterator type 129 typedef treeIterator<treePtr> iterator; ///< the top -> bottom iterator type 130 new_tree()131 static treePtr new_tree() { ctree<T>* o = new ctree<T>; assert(o!=0); return o; } 132 elements()133 branchs& elements() { return fElements; } elements()134 const branchs& elements() const { return fElements; } push(const treePtr & t)135 virtual void push (const treePtr& t) { fElements.push_back(t); } size()136 virtual int size () const { return int(fElements.size()); } empty()137 virtual bool empty () const { return fElements.size()==0; } 138 begin()139 iterator begin() { treePtr start=dynamic_cast<T*>(this); return iterator(start); } end()140 iterator end() { treePtr start=dynamic_cast<T*>(this); return iterator(start, true); } erase(iterator i)141 iterator erase(iterator i) { return i.erase(); } insert(iterator before,const treePtr & value)142 iterator insert(iterator before, const treePtr& value) { return before.insert(value); } 143 lbegin()144 literator lbegin() { return fElements.begin(); } lend()145 literator lend() { return fElements.end(); } 146 147 protected: ctree()148 ctree() {} ~ctree()149 virtual ~ctree() {} 150 151 private: 152 branchs fElements; 153 }; 154 155 156 } 157 158 #endif 159