LibMusicXML 3.22
ctree.h
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
28namespace MusicXML2
29{
30
31//______________________________________________________________________________
32template <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:
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 }
49 treeIterator(const treeIterator& a) { *this = a; }
50 virtual ~treeIterator() {}
51
52 T operator *() const { return *fCurrentIterator; }
53 T operator ->() const { return *fCurrentIterator; }
54
55 //________________________________________________________________________
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
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
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
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 //________________________________________________________________________
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 //________________________________________________________________________
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
122//______________________________________________________________________________
123template <typename T> class EXP ctree : virtual public smartable
124{
125 public:
127 typedef std::vector<treePtr> branchs;
128 typedef typename branchs::iterator literator;
130
131 static treePtr new_tree() { ctree<T>* o = new ctree<T>; assert(o!=0); return o; }
132
133 branchs& elements() { return fElements; }
134 const branchs& elements() const { return fElements; }
135 virtual void push (const treePtr& t) { fElements.push_back(t); }
136 virtual int size () const { return int(fElements.size()); }
137 virtual bool empty () const { return fElements.size()==0; }
138
139 iterator begin() { treePtr start=dynamic_cast<T*>(this); return iterator(start); }
140 iterator end() { treePtr start=dynamic_cast<T*>(this); return iterator(start, true); }
141 iterator erase(iterator i) { return i.erase(); }
142 iterator insert(iterator before, const treePtr& value) { return before.insert(value); }
143
144 literator lbegin() { return fElements.begin(); }
145 literator lend() { return fElements.end(); }
146
147 protected:
148 ctree() {}
149 virtual ~ctree() {}
150
151 private:
152 branchs fElements;
153};
154
155
156}
157
158#endif
the smart pointer implementation
Definition smartpointer.h:58
std::vector< treePtr > branchs
Definition ctree.h:127
SMARTP< xmlelement > treePtr
Definition ctree.h:126
branchs::iterator literator
Definition ctree.h:128
treeIterator< treePtr > iterator
Definition ctree.h:129
Definition ctree.h:33