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