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