ARB
PRD_SearchFIFO.cxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : PRD_SearchFIFO.cxx //
4 // Purpose : //
5 // //
6 // Coded by Wolfram Foerster in February 2001 //
7 // Institute of Microbiology (Technical University Munich) //
8 // http://www.arb-home.de/ //
9 // //
10 // =============================================================== //
11 
12 #include "PRD_SearchFIFO.hxx"
13 #include <cmath>
14 
15 using std::printf;
16 using std::fabs;
17 
18 //
19 // Constructor
20 //
21 void SearchFIFO::init(Node *root_, PRD_Sequence_Pos min_distance_to_next_match_, bool expand_IUPAC_Codes_) {
22  begin = NULp;
23  end = NULp;
24  current = NULp;
25 
26  root = root_;
27  expand_IUPAC_Codes = expand_IUPAC_Codes_;
28  min_distance_to_next_match = min_distance_to_next_match_;
29 }
30 
31 SearchFIFO::SearchFIFO (Node *root_, PRD_Sequence_Pos min_distance_to_next_match_, bool expand_IUPAC_Codes_) {
32  init(root_, min_distance_to_next_match_, expand_IUPAC_Codes_);
33 }
34 
36  init(NULp, -1, false);
37 }
38 
39 
40 //
41 // Destructor
42 //
44  flush();
45 }
46 
47 
48 //
49 // flush : clear FIFO
50 //
52  SearchParameter *to_delete;
53 
54  current = begin;
55  while (current) {
56  to_delete = current;
57  current = current->next;
58  delete to_delete;
59  }
60 
61  begin = NULp;
62  end = NULp;
63  current = NULp;
64 }
65 
66 
67 //
68 // append new SearchParameter to the FIFO
69 //
70 // the current_node is determined from root with the given base
71 // multiple parameters are generated for unsure bases like 'N'
72 //
73 void SearchFIFO::push (unsigned char base_) {
74  unsigned int bits = CHAR2BIT.FIELD[base_];
75  Node *child_of_root;
76  SearchParameter *new_parameter;
77 
78  if (bits & 1) {
79  child_of_root = root->child[2]; // 2 = A
80  if (child_of_root) {
81  new_parameter = new SearchParameter;
82 
83  new_parameter->node = child_of_root;
84  new_parameter->next = NULp;
85  new_parameter->previous = end;
86 
87  if (end) end->next = new_parameter;
88  if (!begin) begin = new_parameter;
89  end = new_parameter;
90  }
91  }
92 
93  if (bits & 2) {
94  child_of_root = root->child[3]; // 3 = T/U
95  if (child_of_root) {
96  new_parameter = new SearchParameter;
97 
98  new_parameter->node = child_of_root;
99  new_parameter->next = NULp;
100  new_parameter->previous = end;
101 
102  if (end) end->next = new_parameter;
103  if (!begin) begin = new_parameter;
104  end = new_parameter;
105  }
106  }
107 
108  if (bits & 4) {
109  child_of_root = root->child[0]; // 0 = C
110  if (child_of_root) {
111  new_parameter = new SearchParameter;
112 
113  new_parameter->node = child_of_root;
114  new_parameter->next = NULp;
115  new_parameter->previous = end;
116 
117  if (end) end->next = new_parameter;
118  if (!begin) begin = new_parameter;
119  end = new_parameter;
120  }
121  }
122 
123  if (bits & 8) {
124  child_of_root = root->child[1]; // 1 = G
125  if (child_of_root) {
126  new_parameter = new SearchParameter;
127 
128  new_parameter->node = child_of_root;
129  new_parameter->next = NULp;
130  new_parameter->previous = end;
131 
132  if (end) end->next = new_parameter;
133  if (!begin) begin = new_parameter;
134  end = new_parameter;
135  }
136  }
137 
138 }
139 
140 
141 //
142 // step down in tree at all the SearchParameters with the given base(s)
143 //
144 void SearchFIFO::push_front(Node *child_of_current_) {
145  SearchParameter *new_parameter = new SearchParameter;
146 
147  new_parameter->node = child_of_current_;
148  new_parameter->next = begin;
149  new_parameter->previous = NULp;
150 
151  if (!end) end = new_parameter;
152  if (begin) begin->previous = new_parameter;
153  begin = new_parameter;
154 }
155 
156 void SearchFIFO::iterateWith (PRD_Sequence_Pos pos_, unsigned char base_) {
157  if (!begin) return;
158 
159  current = begin;
160 
161  if (!expand_IUPAC_Codes) {
162  while (current) {
163 
164  // get childnode of parameters current node
165  Node *child = current->node->childByBase(base_);
166 
167  // erase parameter if child doesn't exist
168  if (!child) {
169  erase(current);
170  }
171  else {
172  // step down as child exists
173  current->node = child;
174 
175  // invalidate if node is primer and is in range
176  if (child->isValidPrimer()) {
177  if (min_distance_to_next_match <= 0) {
178  child->last_base_index = -pos_;
179  }
180  else {
181  if (min_distance_to_next_match >= fabs(double(pos_ - child->last_base_index))) child->last_base_index = -pos_;
182  }
183  }
184 
185  // erase parameter if child is leaf
186  if (child->isLeaf()) {
187  erase(current);
188 
189  // erase node in tree if leaf and invalid primer
190  if (!child->isValidPrimer()) {
191  // remove child from parent
192  child->parent->child[CHAR2CHILD.INDEX[base_]] = NULp;
193  child->parent->child_bits &= ~CHAR2BIT.FIELD[base_];
194  // erase node
195  delete child;
196  }
197  }
198  }
199 
200  // next parameter (or begin if erase killed current while pointing to begin)
201  current = current ? current->next : begin;
202  }
203  }
204  else { // expand IUPAC-Codes
205  while (current) {
206  int bits = current->node->child_bits & CHAR2BIT.FIELD[base_];
207 
208  if (bits & 1) { // A
209  Node *child = current->node->child[2]; // 2 = A
210 
211  // invalidate if node is primer and is in range
212  if (child->isValidPrimer()) {
213  if (min_distance_to_next_match <= 0) {
214  child->last_base_index = -pos_;
215  }
216  else {
217  if (min_distance_to_next_match >= fabs(double(pos_ - child->last_base_index))) child->last_base_index = -pos_;
218  }
219  }
220 
221  // erase child if child is leaf
222  if (child->isLeaf()) {
223  // erase node in tree if leaf and invalid primer
224  if (!child->isValidPrimer()) {
225  // remove child from parent
226  child->parent->child[CHAR2CHILD.INDEX[base_]] = NULp;
227  child->parent->child_bits &= ~CHAR2BIT.FIELD[base_];
228  // erase node
229  delete child;
230  }
231  }
232  else { // add new parameter at the begin of fifo
233  push_front(child);
234  }
235  }
236 
237  if (bits & 2) { // T/U
238  Node *child = current->node->child[3]; // 3 = T/U
239 
240  // invalidate if node is primer and is in range
241  if (child->isValidPrimer()) {
242  if (min_distance_to_next_match <= 0) {
243  child->last_base_index = -pos_;
244  }
245  else {
246  if (min_distance_to_next_match >= fabs(double(pos_ - child->last_base_index))) child->last_base_index = -pos_;
247  }
248  }
249 
250  // erase child if child is leaf
251  if (child->isLeaf()) {
252  // erase node in tree if leaf and invalid primer
253  if (!child->isValidPrimer()) {
254  // remove child from parent
255  child->parent->child[CHAR2CHILD.INDEX[base_]] = NULp;
256  child->parent->child_bits &= ~CHAR2BIT.FIELD[base_];
257  // erase node
258  delete child;
259  }
260  }
261  else { // add new parameter at the begin of fifo
262  push_front(child);
263  }
264  }
265 
266  if (bits & 4) { // C
267  Node *child = current->node->child[0]; // 0 = C
268 
269  // invalidate if node is primer and is in range
270  if (child->isValidPrimer()) {
271  if (min_distance_to_next_match <= 0) {
272  child->last_base_index = -pos_;
273  }
274  else {
275  if (min_distance_to_next_match >= fabs(double(pos_ - child->last_base_index))) child->last_base_index = -pos_;
276  }
277  }
278 
279  // erase child if child is leaf
280  if (child->isLeaf()) {
281  // erase node in tree if leaf and invalid primer
282  if (!child->isValidPrimer()) {
283  // remove child from parent
284  child->parent->child[CHAR2CHILD.INDEX[base_]] = NULp;
285  child->parent->child_bits &= ~CHAR2BIT.FIELD[base_];
286  // erase node
287  delete child;
288  }
289  }
290  else { // add new parameter at the begin of fifo
291  push_front(child);
292  }
293  }
294 
295  if (bits & 8) { // G
296  Node *child = current->node->child[1]; // 1 = G
297 
298  // invalidate if node is primer and is in range
299  if (child->isValidPrimer()) {
300  if (min_distance_to_next_match <= 0) {
301  child->last_base_index = -pos_;
302  }
303  else {
304  if (min_distance_to_next_match >= fabs(double(pos_ - child->last_base_index))) child->last_base_index = -pos_;
305  }
306  }
307 
308  // erase child if child is leaf
309  if (child->isLeaf()) {
310  // erase node in tree if leaf and invalid primer
311  if (!child->isValidPrimer()) {
312  // remove child from parent
313  child->parent->child[CHAR2CHILD.INDEX[base_]] = NULp;
314  child->parent->child_bits &= ~CHAR2BIT.FIELD[base_];
315  // erase node
316  delete child;
317  }
318  }
319  else { // add new parameter at the begin of fifo
320  push_front(child);
321  }
322  }
323 
324  // erase old parameter
325  erase(current);
326 
327  // next parameter (or begin if erase killed current while pointing to begin)
328  current = current ? current->next : begin;
329  }
330  }
331 }
332 
333 
334 //
335 // erase given parameter while not invalidating current
336 //
337 void SearchFIFO::erase (SearchParameter *param_) {
338  // unlink from doublelinked list
339  if (param_->next) param_->next->previous = param_->previous; else end = param_->previous;
340  if (param_->previous) param_->previous->next = param_->next; else begin = param_->next;
341 
342  // set current to current->previous if current is to delete
343  if (param_ == current) current = param_->previous;
344 
345  delete param_;
346 }
347 
348 
349 //
350 // print positions-list
351 //
353  current = begin;
354  if (begin)
355  printf("print : begin %p (%p[%c],%p,%p)\t", begin, begin->node, begin->node->base, begin->previous, begin->next);
356  else
357  printf("print : begin (nil)\n");
358 
359  if (end)
360  printf("end %p (%p[%c],%p,%p)\n", end, end->node, end->node->base, end->previous, end->next);
361  else
362  printf("end (nil)\n");
363 
364  while (current) {
365  printf("print : %p (%p[%c],%p,%p)\n", current, current->node, current->node->base, current->previous, current->next);
366  current = current->next;
367  }
368 }
unsigned char base
Definition: PRD_Node.hxx:15
unsigned int FIELD[128]
Definition: PRD_Globals.hxx:82
Definition: PRD_Node.hxx:9
Node * child[4]
Definition: PRD_Node.hxx:14
void push(unsigned char base_)
static BitField CHAR2BIT
bool isLeaf()
Definition: PRD_Node.hxx:29
static ChildLookupTable CHAR2CHILD
Definition: PRD_Globals.hxx:72
unsigned int child_bits
Definition: PRD_Node.hxx:16
Node * childByBase(unsigned char base_)
Definition: PRD_Node.hxx:26
PRD_Sequence_Pos last_base_index
Definition: PRD_Node.hxx:18
bool isValidPrimer()
Definition: PRD_Node.hxx:27
SearchParameter * previous
void iterateWith(PRD_Sequence_Pos pos_, unsigned char base_)
#define NULp
Definition: cxxforward.h:97
long int PRD_Sequence_Pos
Definition: PRD_Globals.hxx:21
Node * parent
Definition: PRD_Node.hxx:13
SearchParameter * next