ARB
ap_tree_nlen.hxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : ap_tree_nlen.hxx //
4 // Purpose : //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in Summer 1995 //
7 // Institute of Microbiology (Technical University Munich) //
8 // http://www.arb-home.de/ //
9 // //
10 // =============================================================== //
11 
12 #ifndef AP_TREE_NLEN_HXX
13 #define AP_TREE_NLEN_HXX
14 
15 #ifndef _GLIBCXX_IOSTREAM
16 #include <iostream>
17 #endif
18 #ifndef _GLIBCXX_CLIMITS
19 #include <climits>
20 #endif
21 #ifndef ARBDB_BASE_H
22 #include <arbdb_base.h>
23 #endif
24 #ifndef AP_TREE_HXX
25 #include <AP_Tree.hxx>
26 #endif
27 #ifndef AP_BUFFER_HXX
28 #include "AP_buffer.hxx"
29 #endif
30 #ifndef AP_MAIN_TYPE_HXX
31 #include "ap_main_type.hxx"
32 #endif
33 #ifndef PARS_AWARS_H
34 #include "pars_awars.h"
35 #endif
36 
37 class AP_tree_nlen;
38 
39 enum KL_RECURSION_TYPE { // =path reduction
40  // bit-values!
43  AP_STATIC = 2,
44 };
45 
47  double a, b, c;
48 public:
50  QuadraticThreshold(KL_DYNAMIC_THRESHOLD_TYPE type, double startx, double maxy, double maxx, double maxDepth, Mutations pars_start);
51 
52  double calculate(double x) const {
53  // y = ax^2 + bx + c
54  return
55  x * x * a +
56  x * b +
57  c;
58  }
59 
61  c += offset;
62  }
63 };
64 
65 struct KL_params {
67  KL_RECURSION_TYPE rec_type; // recursion type
68  int rec_width[CUSTOM_DEPTHS]; // customized recursion width (static path reduction)
69  QuadraticThreshold thresFunctor; // functor for dynamic path reduction (start parsvalue -> worst allowed parsvalue @ depth)
70  int inc_rec_depth; // increment max. recursion depth (if better topology found)
71  bool stopAtFoldedGroups; // if true = > do not swap across folded groups
72 };
73 
74 enum AP_BL_MODE {
75  APBL_NONE = 0,
76  AP_BL_NNI_ONLY = 1, // try te find a better tree only
77  AP_BL_BL_ONLY = 2, // try to calculate the branch lengths
78  AP_BL_BOOTSTRAP_LIMIT = 4, // calculate upper bootstrap limits
79  AP_BL_BOOTSTRAP_ESTIMATE = 12 // calculate estimate of bootstrap (includes AP_BL_BOOTSTRAP_LIMIT)
80 };
81 
85 };
86 
87 class AP_tree_edge;
88 class AP_main;
89 
90 class AP_pars_root FINAL_TYPE : public AP_tree_root {
91  // @@@ add responsibility for node/edge resources
92  bool has_been_saved;
93 public:
94  AP_pars_root(AliView *aliView, AP_sequence *seq_proto, bool add_delete_callbacks, const group_scaling *scaling)
95  : AP_tree_root(aliView, seq_proto, add_delete_callbacks, scaling),
96  has_been_saved(false)
97  {}
98  inline TreeNode *makeNode() const OVERRIDE;
99  inline void destroyNode(TreeNode *node) const OVERRIDE;
100  GB_ERROR saveToDB() OVERRIDE;
101  AP_UPDATE_FLAGS check_update() OVERRIDE;
102 
103  bool was_saved() const { return has_been_saved; }
104 };
105 
106 typedef uint8_t EdgeIndex;
107 
108 class AP_tree_nlen FINAL_TYPE : public AP_tree { // derived from a Noncopyable // @@@ rename -> AP_pars_tree? (later!)
109  // tree that is independent of branch lengths and root
110 
111  // definitions for AP_tree_edge:
112  AP_tree_edge *edge[3]; // the edges to the father and the sons
113  EdgeIndex index[3]; // index to node[] in AP_tree_edge
114 
115  Mutations mutations; // = costs of subtree (=mutations caused by combine + costs of both child-subtrees)
116 
117  Level remembered_for_frame; // last frame this nodes' state has been remembered, 0 = none
118  StateStack states; // containes previous states of 'this'
119 
121 
122  void restore_structure(const NodeState& state);
123  void restore_sequence(NodeState& state);
124  void restore_sequence_nondestructive(const NodeState& state);
125  void restore_root(const NodeState& state);
126 
127 protected:
129  friend void AP_main::destroyNode(AP_tree_nlen *node); // allowed to call dtor
130  friend void ResourceStack::destroy_nodes();
131  friend void ResourceStack::destroy_edges();
132  friend void StackFrameData::destroyNode(AP_tree_nlen *node);
133 public:
134  explicit AP_tree_nlen(AP_pars_root *troot)
135  : AP_tree(troot),
136  mutations(0),
137  remembered_for_frame(0)
138  {
139  edge[0] = edge[1] = edge[2] = NULp;
140  index[0] = index[1] = index[2] = 0;
141  }
142 
143  DEFINE_TREE_ACCESSORS(AP_pars_root, AP_tree_nlen);
145 
146  void unhash_sequence();
147 
148  Mutations costs(char *mutPerSite = NULp); // cost of a tree (number of changes ..)
149  Mutations stored_costs() const { return mutations; }
150 
151  bool rememberState(AP_STACK_MODE, Level frame_level);
152  void revertToPreviousState(Level curr_frameLevel, bool& rootPopped);
153  void restore(NodeState& state);
154  void restore_nondestructive(const NodeState& state);
155  bool acceptCurrentState(Level frame_level);
156 
157  Level last_remembered_frame() const { return remembered_for_frame; }
158  bool may_be_recollected() const { return !states.empty(); }
159  const StateStack& get_states() const { return states; }
160 
162  // return true if changed
163  if (is_leaf()) return false;
164  unsigned marked_childs = get_leftson()->gr.mark_sum + get_rightson()->gr.mark_sum;
165  if (marked_childs == gr.mark_sum) return false;
166  gr.mark_sum = marked_childs;
167  return true;
168  }
169 
171  if (recalc_marked_from_sons() && father) {
172  get_father()->recalc_marked_from_sons_and_forward_upwards();
173  }
174  }
175 
176  // tree reconstruction methods:
177  void insert(AP_tree_nlen *new_brother);
178  void initial_insert(AP_tree_nlen *new_brother, AP_pars_root *troot);
179 
180  AP_tree_nlen *REMOVE() OVERRIDE;
181  void swap_sons() OVERRIDE;
182  void swap_assymetric(AP_TREE_SIDE mode);
183  void moveNextTo(AP_tree_nlen *new_brother, AP_FLOAT rel_pos); // if unsure, use cantMoveNextTo to test if possible
184  void set_root() OVERRIDE;
185 
186  inline void moveTo(AP_tree_edge *e);
187 
188  // overload virtual methods from AP_tree:
189  void insert(AP_tree *new_brother) OVERRIDE { insert(DOWNCAST(AP_tree_nlen*, new_brother)); }
190  void initial_insert(AP_tree *new_brother, AP_tree_root *troot) OVERRIDE { initial_insert(DOWNCAST(AP_tree_nlen*, new_brother), DOWNCAST(AP_pars_root*, troot)); }
191  void moveNextTo(AP_tree *node, AP_FLOAT rel_pos) OVERRIDE { moveNextTo(DOWNCAST(AP_tree_nlen*, node), rel_pos); }
192 
193  void exchange(AP_tree_nlen *other);
194 
195  // tree optimization methods:
196  void parsimony_rec(char *mutPerSite = NULp);
197 
198  Mutations nn_interchange_rec(EdgeSpec whichEdges, AP_BL_MODE mode);
199  AP_FLOAT nn_interchange(AP_FLOAT parsimony, AP_BL_MODE mode);
200 
201  // misc stuff:
202 
203  void setBranchlen(double leftLen, double rightLen) { leftlen = leftLen; rightlen = rightLen; }
204 
205  const char* fullname() const;
206  const char* sortByName();
207 
208  // AP_tree_edge access functions:
209 
210  int indexOf(const AP_tree_edge *e) const { int i; for (i=0; i<3; i++) if (edge[i]==e) return i; return -1; }
211 
212  AP_tree_edge* edgeTo(const AP_tree_nlen *brother) const;
213  AP_tree_edge* nextEdge(const AP_tree_edge *afterThatEdge=NULp) const;
214  int unusedEdgeIndex() const; // [0..2], -1 if none
215 
216  // more complex edge functions:
217 
218  void linkAllEdges(AP_tree_edge *edge1, AP_tree_edge *edge2, AP_tree_edge *edge3);
219  void unlinkAllEdges(AP_tree_edge **edgePtr1, AP_tree_edge **edgePtr2, AP_tree_edge **edgePtr3);
220 
221  char *getSequenceCopy();
222 
223 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
224  Validity has_valid_edges() const;
225  Validity sequence_state_valid() const;
226  Validity is_valid() const;
227 #endif // PROVIDE_TREE_STRUCTURE_TESTS
228 
229 #if defined(PROVIDE_PRINT)
230  void print(std::ostream& out, int indentLevel, const char *label) const;
231 #endif
232 
233 #if defined(UNIT_TESTS)
234  void remember_subtree(AP_main *main) { // dont use in production
235  if (is_leaf()) {
236  main->push_node(this, STRUCTURE);
237  }
238  else {
239  main->push_node(this, BOTH);
240  get_leftson()->remember_subtree(main);
241  get_rightson()->remember_subtree(main);
242  }
243  }
244 #endif
245 
246 
247  friend class AP_tree_edge;
248  friend std::ostream& operator<<(std::ostream&, const AP_tree_nlen*);
249 };
250 
251 #if defined(ASSERTION_USED) || defined(UNIT_TESTS)
253 #endif
254 
255 // ---------------------
256 // AP_tree_edge
257 
258 class MutationsPerSite;
259 
260 class AP_tree_edge : virtual Noncopyable {
261  // the following members are stored/restored by
262  // AP_tree_nlen::push/pop:
263 
264  AP_tree_nlen *node[2]; // the two nodes of this edge
265  EdgeIndex index[2]; // index to edge[] in AP_tree_nlen
266 
267  // and these arent pushed:
268 
269  AP_tree_edge *next_in_chain; // do not use (use EdgeChain!)
270  int used; // test-counter
271  long age; // age of the edge
272  bool kl_visited;
273 
274  static long timeStamp; // static counter for edge-age
275 
276  size_t buildChainInternal(EdgeSpec whichEdges, bool depthFirst, const AP_tree_nlen *skip, AP_tree_edge**& prevNextPtr);
277 
278  bool is_linked() const { return node[0]; }
279 
280  void set_inner_branch_length_and_calc_adj_leaf_lengths(AP_FLOAT bcosts);
281 
282  // my friends:
283  friend class AP_tree_nlen;
284  friend class EdgeChain;
285 
286  friend std::ostream& operator<<(std::ostream&, const AP_tree_edge*);
287  friend AP_tree_edge *StackFrameData::makeEdge(AP_tree_nlen *n1, AP_tree_nlen *n2); // allowed to relink edge
288  friend void AP_main::destroyEdge(AP_tree_edge *edge); // allowed to delete edge
289  friend void ResourceStack::destroy_edges(); // allowed to delete edge
290 #if defined(UNIT_TESTS) // UT_DIFF
291  friend void TEST_basic_tree_modifications();
292 #endif
293 
294 protected:
295 
296  ~AP_tree_edge();
297 
298  // relink & unlink (they are also used by constructor & destructor)
299 
300  void relink(AP_tree_nlen *node1, AP_tree_nlen *node2);
301  AP_tree_edge *unlink();
302 
303 public:
304 
305  AP_tree_edge(AP_tree_nlen *node1, AP_tree_nlen *node2);
306 
307  static void initialize(AP_tree_nlen *root);
308  static void destroy(AP_tree_nlen *root);
309 
310  // access methods:
311 
312  bool isConnectedTo(const AP_tree_nlen *n) const { return node[0]==n || node[1]==n; }
313  int indexOf(const AP_tree_nlen *n) const { ap_assert(isConnectedTo(n)); return node[1] == n; }
314  AP_tree_nlen* otherNode(const AP_tree_nlen *n) const { return node[1-indexOf(n)]; }
315  AP_tree_nlen* sonNode() const { return node[0]->get_father() == node[1] ? node[0] : node[1]; }
316  AP_tree_nlen* notSonNode() const { return otherNode(sonNode()); }
317 
318  long Age() const { return age; }
319 
320  // queries
321 
322  bool is_root_edge() const { return node[0]->father != node[1] && node[1]->father != node[0]; }
323  bool is_leaf_edge() const { return node[0]->is_leaf() || node[1]->is_leaf(); }
324  bool next_to_folded_group() const { return node[0]->gr.grouped || node[1]->gr.grouped; }
325  bool has_marked() const { // true if subtree contains marked species
326  return is_root_edge()
327  ? node[0]->gr.mark_sum+node[1]->gr.mark_sum
328  : sonNode()->gr.mark_sum;
329  }
330 
331  // encapsulated AP_tree_nlen methods:
332 
333  void set_root() { return sonNode()->set_root(); }
334 
335  // tree optimization:
336 
337  Mutations nni_rec(EdgeSpec whichEdges, AP_BL_MODE mode, AP_tree_nlen *skipNode, bool includeStartEdge);
338  bool kl_rec(const KL_params& KL, const int rec_depth, Mutations pars_best);
339 
341 
343 
344  void mixTree(int repeat, int percent, EdgeSpec whichEdges);
345 
346  void set_visited(bool vis) { kl_visited = vis; }
347 };
348 
349 std::ostream& operator<<(std::ostream&, const AP_tree_edge*);
350 
351 inline void AP_tree_nlen::moveTo(AP_tree_edge *e) {
352  moveNextTo(e->sonNode(), 0.5);
353 }
354 
355 class EdgeChain : virtual Noncopyable {
356  AP_tree_edge *start; // start edge
357  AP_tree_edge *curr; // current edge (for iteration)
358  size_t len; // chain size
359  static bool exists; // singleton flag
360 public:
361  EdgeChain(AP_tree_edge *start_, EdgeSpec whichEdges, bool depthFirst, const AP_tree_nlen *skip = NULp, bool includeStart = true);
362  ~EdgeChain() { exists = false; }
363 
364  size_t size() const {
365  return len;
366  }
367  operator bool() const {
368  return curr;
369  }
371  return curr;
372  }
374  ap_assert(curr);
375  curr = curr->next_in_chain;
376  return *this;
377  }
378  void restart() {
379  curr = start;
380  }
381 };
382 
383 #else
384 #error ap_tree_nlen.hxx included twice
385 #endif // AP_TREE_NLEN_HXX
bool isConnectedTo(const AP_tree_nlen *n) const
const char * GB_ERROR
Definition: arb_core.h:25
GB_TYPES type
void destroy_nodes()
Definition: AP_buffer.cxx:172
void moveNextTo(AP_tree *node, AP_FLOAT rel_pos) OVERRIDE
AP_tree_edge * makeEdge(AP_tree_nlen *n1, AP_tree_nlen *n2)
Definition: ap_main.hxx:70
static int maxDepth
Definition: rns.c:53
AP_BL_MODE
bool may_be_recollected() const
~AP_tree_nlen() OVERRIDE
AP_tree_edge(AP_tree_nlen *node1, AP_tree_nlen *node2)
int indexOf(const AP_tree_edge *e) const
long Age() const
void restart()
Level last_remembered_frame() const
Mutations nni_rec(EdgeSpec whichEdges, AP_BL_MODE mode, AP_tree_nlen *skipNode, bool includeStartEdge)
int main(int argc, char **argv)
Definition: aisc.c:359
AP_tree_nlen * sonNode() const
AP_pars_root(AliView *aliView, AP_sequence *seq_proto, bool add_delete_callbacks, const group_scaling *scaling)
AP_tree_edge * operator*()
void destroy_edges()
Definition: AP_buffer.cxx:186
void relink(AP_tree_nlen *node1, AP_tree_nlen *node2)
Mutations stored_costs() const
bool empty() const
Definition: AP_buffer.hxx:100
AP_TREE_SIDE
void set_visited(bool vis)
size_t size() const
int rec_width[CUSTOM_DEPTHS]
bool recalc_marked_from_sons()
#define OVERRIDE_SEQ_ACCESSORS(SEQTYPE, BASETREETYPE)
Definition: ARB_Tree.hxx:181
virtual void insert(AP_tree *new_brother)
Definition: AP_Tree.cxx:178
friend std::ostream & operator<<(std::ostream &, const AP_tree_edge *)
#define DOWNCAST(totype, expr)
Definition: downcast.h:141
double AP_FLOAT
Definition: AP_matrix.hxx:27
void change_parsimony_start(Mutations offset)
AP_tree_edge * unlink()
AP_UPDATE_FLAGS
Definition: AP_Tree.hxx:28
KL_DYNAMIC_THRESHOLD_TYPE
Definition: pars_awars.h:52
EdgeChain(AP_tree_edge *start_, EdgeSpec whichEdges, bool depthFirst, const AP_tree_nlen *skip=NULp, bool includeStart=true)
virtual AP_tree * REMOVE()
Definition: AP_Tree.cxx:259
bool push_node(AP_tree_nlen *node, AP_STACK_MODE)
Definition: AP_main.cxx:252
POS_TREE1 * father
Definition: probe_tree.h:39
POS_TREE1 * get_father() const
Definition: probe_tree.h:49
int indexOf(const AP_tree_nlen *n) const
DEFINE_TREE_ACCESSORS(AP_tree_root, AP_tree)
void initial_insert(AP_tree *new_brother, AP_tree_root *troot) OVERRIDE
static void destroy(AP_tree_nlen *root)
AP_STACK_MODE
Definition: AP_buffer.hxx:117
#define false
Definition: ureadseq.h:13
bool is_leaf_edge() const
long Mutations
Definition: AP_sequence.hxx:99
std::ostream & operator<<(std::ostream &, const AP_tree_edge *)
uint8_t EdgeIndex
AP_tree_nlen(AP_pars_root *troot)
const EdgeChain & operator++()
const StateStack & get_states() const
#define ap_assert(cond)
void destroyNode(AP_tree_nlen *node)
Definition: ap_main.hxx:90
bool next_to_folded_group() const
KL_RECURSION_TYPE rec_type
QuadraticThreshold thresFunctor
virtual void initial_insert(AP_tree *new_brother, AP_tree_root *troot)
Definition: AP_Tree.cxx:151
bool is_leaf() const
Definition: TreeNode.h:171
void insert(AP_tree *new_brother) OVERRIDE
xml element
int inc_rec_depth
Mutations calc_branchlengths()
#define OVERRIDE
Definition: cxxforward.h:93
KL_RECURSION_TYPE
void recalc_marked_from_sons_and_forward_upwards()
int max_rec_depth
void destroyEdge(AP_tree_edge *edge)
Definition: ap_main.hxx:100
TreeNode * makeNode() const OVERRIDE
Definition: AP_Tree.hxx:386
bool allBranchlengthsAreDefined(AP_tree_nlen *tree)
AP_tree_nlen * otherNode(const AP_tree_nlen *n) const
friend class AP_tree_nlen
bool is_root_edge() const
void destroyNode(AP_tree_nlen *node)
Definition: ap_main.hxx:81
static void initialize(AP_tree_nlen *root)
#define NULp
Definition: cxxforward.h:97
#define offset(field)
Definition: GLwDrawA.c:73
EdgeSpec
Definition: pars_awars.h:57
double calculate(double x) const
bool kl_rec(const KL_params &KL, const int rec_depth, Mutations pars_best)
void mixTree(int repeat, int percent, EdgeSpec whichEdges)
bool stopAtFoldedGroups
bool has_marked() const
void forget_relatives()
Definition: TreeNode.h:374
Mutations nni_mutPerSite(Mutations pars_one, AP_BL_MODE mode, MutationsPerSite *mps)
const int CUSTOM_DEPTHS
Definition: pars_awars.h:50
AP_tree_nlen * notSonNode() const
unsigned long Level
Definition: AP_buffer.hxx:126
const char * label
void setBranchlen(double leftLen, double rightLen)
void print(const T &t)
Definition: test_unit.h:348