1 | // =============================================================== // |
---|
2 | // // |
---|
3 | // File : AP_buffer.hxx // |
---|
4 | // Purpose : // |
---|
5 | // // |
---|
6 | // Institute of Microbiology (Technical University Munich) // |
---|
7 | // http://www.arb-home.de/ // |
---|
8 | // // |
---|
9 | // =============================================================== // |
---|
10 | |
---|
11 | #ifndef AP_BUFFER_HXX |
---|
12 | #define AP_BUFFER_HXX |
---|
13 | |
---|
14 | #ifndef AP_SEQUENCE_HXX |
---|
15 | #include <AP_sequence.hxx> |
---|
16 | #endif |
---|
17 | #ifndef ARB_FORWARD_LIST_H |
---|
18 | #include <arb_forward_list.h> |
---|
19 | #endif |
---|
20 | #ifndef _GLIBCXX_SET |
---|
21 | #include <set> |
---|
22 | #endif |
---|
23 | |
---|
24 | /* AP_STACK Stack container |
---|
25 | * |
---|
26 | * -- buffers |
---|
27 | * |
---|
28 | * NodeState holds (partial) state of AP_tree_nlen |
---|
29 | * |
---|
30 | * -- used stacks |
---|
31 | * |
---|
32 | * StateStack stack containing NodeState* (each AP_tree_nlen contains one) |
---|
33 | * NodeStack stack containing AP_tree_nlen* (NodeStack of current frame is member of AP_main) |
---|
34 | * FrameStack stack containing NodeStacks (member of AP_main, stores previous NodeStack frames) |
---|
35 | */ |
---|
36 | |
---|
37 | template <typename ELEM> |
---|
38 | struct AP_STACK : public arb_forward_list<ELEM*> { |
---|
39 | typedef arb_forward_list<ELEM*> BASE; |
---|
40 | typedef typename BASE::iterator iterator; |
---|
41 | typedef typename BASE::const_iterator const_iterator; |
---|
42 | |
---|
43 | void push(ELEM *element) { |
---|
44 | //! add 'element' to top of stack |
---|
45 | BASE::push_front(element); |
---|
46 | } |
---|
47 | void shift(ELEM *element) { |
---|
48 | //! add 'element' to bottom of stack |
---|
49 | #if defined(Cxx11) |
---|
50 | // uses forward_list |
---|
51 | if (BASE::empty()) { |
---|
52 | push(element); |
---|
53 | } |
---|
54 | else { |
---|
55 | iterator i = BASE::begin(); |
---|
56 | iterator n = i; |
---|
57 | while (true) { |
---|
58 | if (++n == BASE::end()) { |
---|
59 | BASE::insert_after(i, element); |
---|
60 | break; |
---|
61 | } |
---|
62 | i = n; |
---|
63 | } |
---|
64 | } |
---|
65 | #else |
---|
66 | // uses list |
---|
67 | BASE::push_back(element); |
---|
68 | #endif |
---|
69 | } |
---|
70 | ELEM *pop() { |
---|
71 | if (BASE::empty()) return NULL; |
---|
72 | |
---|
73 | ELEM *result = top(); |
---|
74 | BASE::pop_front(); |
---|
75 | return result; |
---|
76 | } |
---|
77 | |
---|
78 | ELEM *top() { |
---|
79 | ap_assert(!BASE::empty()); |
---|
80 | return BASE::front(); |
---|
81 | } |
---|
82 | const ELEM *top() const { |
---|
83 | ap_assert(!BASE::empty()); |
---|
84 | return BASE::front(); |
---|
85 | } |
---|
86 | |
---|
87 | size_t count_elements() const { |
---|
88 | #if defined(Cxx11) |
---|
89 | size_t s = 0; |
---|
90 | for (const_iterator i = BASE::begin(); i != BASE::end(); ++i) ++s; |
---|
91 | return s; |
---|
92 | #else // !defined(Cxx11) |
---|
93 | return BASE::size(); |
---|
94 | #endif |
---|
95 | } |
---|
96 | }; |
---|
97 | |
---|
98 | // ---------------------------------------------------------------- |
---|
99 | // special buffer-structures for AP_tree and AP_tree_edge |
---|
100 | |
---|
101 | #if defined(DEBUG) |
---|
102 | #define PROVIDE_PRINT |
---|
103 | #endif |
---|
104 | |
---|
105 | #if defined(PROVIDE_PRINT) |
---|
106 | #include <ostream> |
---|
107 | #endif |
---|
108 | |
---|
109 | |
---|
110 | class AP_tree_edge; // defined in ap_tree_nlen.hxx |
---|
111 | |
---|
112 | enum AP_STACK_MODE { |
---|
113 | NOTHING = 0, // nothing to buffer in AP_tree node |
---|
114 | STRUCTURE = 1, // only structure |
---|
115 | SEQUENCE = 2, // only sequence |
---|
116 | BOTH = 3, // sequence & treestructure is buffered |
---|
117 | ROOT = 7 // old root is buffered (includes BOTH) |
---|
118 | }; |
---|
119 | |
---|
120 | class AP_tree_nlen; |
---|
121 | class AP_pars_root; |
---|
122 | |
---|
123 | typedef unsigned long Level; |
---|
124 | |
---|
125 | struct NodeState : virtual Noncopyable { // buffers previous states of AP_tree_nlen |
---|
126 | Level frameNr; // state of AP_tree_nlen::remembered_for_frame at creation time of NodeState |
---|
127 | AP_STACK_MODE mode; // what has been stored? |
---|
128 | |
---|
129 | // only defined if mode & SEQUENCE: |
---|
130 | AP_sequence *sequence; // if set -> NodeState is owner! |
---|
131 | AP_FLOAT mutation_rate; |
---|
132 | |
---|
133 | // only defined if mode & STRUCTURE: |
---|
134 | double leftlen, rightlen; |
---|
135 | AP_tree_nlen *father; |
---|
136 | AP_tree_nlen *leftson; |
---|
137 | AP_tree_nlen *rightson; |
---|
138 | AP_pars_root *root; |
---|
139 | GBDATA *gb_node; |
---|
140 | AP_tree_edge *edge[3]; |
---|
141 | int edgeIndex[3]; |
---|
142 | |
---|
143 | // defined/restored if mode & (SEQUENCE|STRUCTURE): |
---|
144 | unsigned mark_sum; |
---|
145 | |
---|
146 | void move_info_to(NodeState& target, AP_STACK_MODE what); |
---|
147 | |
---|
148 | #if defined(PROVIDE_PRINT) |
---|
149 | void print(std::ostream& out, int indentLevel = 0) const; |
---|
150 | #endif |
---|
151 | |
---|
152 | explicit NodeState(Level frame_nr) : frameNr(frame_nr), mode(NOTHING) {} |
---|
153 | ~NodeState() { if (mode & SEQUENCE) delete sequence; } |
---|
154 | }; |
---|
155 | |
---|
156 | struct StateStack : public AP_STACK<NodeState> { |
---|
157 | #if defined(PROVIDE_PRINT) |
---|
158 | void print(std::ostream& out, int indentLevel = 0) const; |
---|
159 | #endif |
---|
160 | }; |
---|
161 | |
---|
162 | class AP_tree_nlen; |
---|
163 | class AP_tree_edge; |
---|
164 | |
---|
165 | #if defined(ASSERTION_USED) |
---|
166 | #define CHECK_ROOT_POPS |
---|
167 | #endif |
---|
168 | |
---|
169 | typedef std::set<AP_tree_nlen*> NodeSet; |
---|
170 | typedef std::set<AP_tree_edge*> EdgeSet; |
---|
171 | |
---|
172 | class ResourceStack { |
---|
173 | // stores nodes and edges for resource management |
---|
174 | NodeSet nodes; |
---|
175 | EdgeSet edges; |
---|
176 | public: |
---|
177 | ResourceStack() {} |
---|
178 | ~ResourceStack() { |
---|
179 | ap_assert(nodes.empty()); |
---|
180 | ap_assert(edges.empty()); |
---|
181 | } |
---|
182 | |
---|
183 | void extract_common(ResourceStack& stack1, ResourceStack& stack2); |
---|
184 | |
---|
185 | void destroy_nodes(); |
---|
186 | void destroy_edges(); |
---|
187 | void forget_nodes(); |
---|
188 | void forget_edges(); |
---|
189 | void move_nodes(ResourceStack& target); |
---|
190 | void move_edges(ResourceStack& target); |
---|
191 | |
---|
192 | AP_tree_nlen *put(AP_tree_nlen *node) { nodes.insert(node); return node; } |
---|
193 | AP_tree_edge *put(AP_tree_edge *edge) { edges.insert(edge); return edge; } |
---|
194 | |
---|
195 | AP_tree_nlen *getNode() { ap_assert(!nodes.empty()); AP_tree_nlen *result = *nodes.begin(); nodes.erase(nodes.begin()); return result; } |
---|
196 | AP_tree_edge *getEdge() { ap_assert(!edges.empty()); AP_tree_edge *result = *edges.begin(); edges.erase(edges.begin()); return result; } |
---|
197 | |
---|
198 | bool has_nodes() const { return !nodes.empty(); } |
---|
199 | bool has_edges() const { return !edges.empty(); } |
---|
200 | |
---|
201 | bool has_node(AP_tree_nlen *node) const { return nodes.find(node) != nodes.end(); } |
---|
202 | }; |
---|
203 | |
---|
204 | class StackFrameData : virtual Noncopyable { |
---|
205 | // data local to current stack frame |
---|
206 | // as well exists for stack frame = 0 (i.e. when nothing has been remember()ed yet) |
---|
207 | |
---|
208 | ResourceStack created; // nodes and edges created in the current stack frame |
---|
209 | ResourceStack destroyed; // same for destroyed |
---|
210 | |
---|
211 | public: |
---|
212 | bool root_pushed; // @@@ move into NodeStack |
---|
213 | StackFrameData() : root_pushed(false) {} |
---|
214 | |
---|
215 | void revert_resources(StackFrameData *previous); |
---|
216 | void accept_resources(StackFrameData *previous, ResourceStack *common); |
---|
217 | |
---|
218 | void extract_common_to(ResourceStack& common) { common.extract_common(created, destroyed); } |
---|
219 | |
---|
220 | inline AP_tree_nlen *makeNode(AP_pars_root *proot); |
---|
221 | inline AP_tree_edge *makeEdge(AP_tree_nlen *n1, AP_tree_nlen *n2); |
---|
222 | inline void destroyNode(AP_tree_nlen *node); |
---|
223 | inline void destroyEdge(AP_tree_edge *edge); |
---|
224 | }; |
---|
225 | |
---|
226 | #if defined(ASSERTION_USED) |
---|
227 | #define CHECK_STACK_RESOURCE_HANDLING |
---|
228 | #endif |
---|
229 | |
---|
230 | class NodeStack : public AP_STACK<AP_tree_nlen> { // derived from Noncopyable |
---|
231 | StackFrameData *previous; |
---|
232 | #if defined(CHECK_STACK_RESOURCE_HANDLING) |
---|
233 | enum ResHandled { NO, ACCEPTED, REVERTED } resources_handled; |
---|
234 | #endif |
---|
235 | |
---|
236 | public: |
---|
237 | explicit NodeStack(StackFrameData*& data) |
---|
238 | : previous(data) |
---|
239 | #if defined(CHECK_STACK_RESOURCE_HANDLING) |
---|
240 | , resources_handled(NO) |
---|
241 | #endif |
---|
242 | { |
---|
243 | data = NULL; // take ownership |
---|
244 | } |
---|
245 | ~NodeStack() { |
---|
246 | ap_assert(!previous); // forgot to use take_previous_frame_data() |
---|
247 | #if defined(CHECK_STACK_RESOURCE_HANDLING) |
---|
248 | ap_assert(resources_handled != NO); |
---|
249 | #endif |
---|
250 | } |
---|
251 | |
---|
252 | StackFrameData *take_previous_frame_data() { |
---|
253 | StackFrameData *release = previous; |
---|
254 | previous = NULL; // release ownership |
---|
255 | return release; |
---|
256 | } |
---|
257 | |
---|
258 | void revert_resources(StackFrameData *current) { |
---|
259 | #if defined(CHECK_STACK_RESOURCE_HANDLING) |
---|
260 | ap_assert(resources_handled == NO); |
---|
261 | resources_handled = REVERTED; |
---|
262 | #endif |
---|
263 | current->revert_resources(previous); |
---|
264 | } |
---|
265 | void accept_resources(StackFrameData *current, ResourceStack *common) { |
---|
266 | #if defined(CHECK_STACK_RESOURCE_HANDLING) |
---|
267 | ap_assert(resources_handled == NO); |
---|
268 | resources_handled = ACCEPTED; |
---|
269 | #endif |
---|
270 | current->accept_resources(previous, common); |
---|
271 | } |
---|
272 | |
---|
273 | #if defined(CHECK_ROOT_POPS) |
---|
274 | AP_tree_nlen *root_at_create; // root at creation time of stack |
---|
275 | #endif |
---|
276 | #if defined(PROVIDE_PRINT) |
---|
277 | void print(std::ostream& out, int indentLevel, Level frameNr) const; |
---|
278 | #endif |
---|
279 | }; |
---|
280 | |
---|
281 | struct FrameStack : public AP_STACK<NodeStack> { |
---|
282 | #if defined(PROVIDE_PRINT) |
---|
283 | void print(std::ostream& out, int indentLevel = 0) const; |
---|
284 | #endif |
---|
285 | }; |
---|
286 | |
---|
287 | #else |
---|
288 | #error AP_buffer.hxx included twice |
---|
289 | #endif // AP_BUFFER_HXX |
---|