ARB
AP_Tree.hxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : AP_Tree.hxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // =============================================================== //
10 
11 #ifndef AP_TREE_HXX
12 #define AP_TREE_HXX
13 
14 #define AP_F_LOADED ((AW_active)1)
15 #define AP_F_NLOADED ((AW_active)2)
16 #define AP_F_SEQUENCES ((AW_active)4)
17 #define AP_F_MATRIX ((AW_active)8)
18 #define AP_F_TREE ((AW_active)16)
19 #define AP_F_ALL ((AW_active)-1)
20 
21 #ifndef ARB_TREE_HXX
22 #include <ARB_Tree.hxx>
23 #endif
24 #ifndef AP_SEQUENCE_HXX
25 #include <AP_sequence.hxx>
26 #endif
27 
33 };
34 
35 enum AWT_RemoveType { // bit flags
40 
41  // please keep AWT_RemoveType in sync with GBT_TreeRemoveType
42  // see ../../ARBDB/arbdbt.h@sync_GBT_TreeRemoveType__AWT_RemoveType
43 
44  // combined defines:
46 };
47 
48 struct AP_rates : virtual Noncopyable {
50  long rate_len;
52  long update;
53 
54  AP_rates();
55  char *init(AP_filter *fil);
56  char *init(AP_FLOAT * ra, AP_filter *fil);
57  ~AP_rates();
58  void print();
59 };
60 
61 struct group_scaling {
62  double linear; // linear factor applied to group size
63  double pow; // downscaling for big groups (0=all groups same size; 1=unfolded size)
64 
65  group_scaling() : linear(-1.0), pow(-1.0) { } // init with nonsense-values
66 
67 #if defined(ASSERTION_USED)
68  bool has_been_set() const { return linear>=0 || pow>=0; }
69 #endif
70 };
71 
72 // ---------------------
73 // AP_tree_root
74 
75 class AP_tree;
76 class AP_TreeShader;
77 
78 typedef void (*AP_rootChangedCb)(void *cd, AP_tree *old, AP_tree *newroot);
79 typedef void (*AP_nodeDelCb)(void *cd, AP_tree *del);
80 
81 class AP_tree_root : public ARB_seqtree_root { // derived from a Noncopyable
82  AP_rootChangedCb root_changed_cb;
83  void *root_changed_cd;
84  AP_nodeDelCb node_deleted_cb;
85  void *node_deleted_cd;
86 
87  GBDATA *gb_species_data; // @@@ needed ?
88 
89  const group_scaling *gScale; // normally refers to AWT_graphic_tree::groupScale
90 
91 public:
92  GBDATA *gb_tree_gone; // if all leafs have been removed by tree operations, remember 'ARB_seqtree_root::gb_tree' here (see change_root)
93  char *gone_tree_name; // set to old tree name when gb_tree_gone gets deleted (used for auto-recreation)
94 
95  long tree_timer;
97 
99 
100  AP_tree_root(AliView *aliView, AP_sequence *seq_proto, bool add_delete_callbacks, const group_scaling *scaling);
103 
104  // TreeRoot interface
105  inline TreeNode *makeNode() const OVERRIDE;
106  inline void destroyNode(TreeNode *node) const OVERRIDE;
107 
108  // ARB_seqtree_root interface
109 
110  void change_root(TreeNode *old, TreeNode *newroot) FINAL_OVERRIDE;
111 
112  GB_ERROR loadFromDB(const char *name) FINAL_OVERRIDE;
113  GB_ERROR saveToDB() OVERRIDE;
114 
115  // AP_tree_root interface
116 
117  virtual AP_UPDATE_FLAGS check_update();
118  void update_timers(); // update the timer
119  bool is_tree_updated();
120  bool is_species_updated();
121 
122  const group_scaling *get_group_scaling() const { return gScale; }
123 
124  void inform_about_delete(AP_tree *old);
125 
127  void set_node_deleted_callback(AP_nodeDelCb cb, void *cd);
128 
129  long remove_leafs(AWT_RemoveType awt_remove_type);
131 };
135 MARK_NONFINAL_METHOD(AP_tree_root,destroyNode,(TreeNode*)const);
137 
138 namespace tree_defaults {
139  const float SPREAD = 1.0;
140  const float ANGLE = 0.0;
141  const char LINEWIDTH = 0;
143 };
144 
146 public: // @@@ make members private
147 
148  bool grouped; // indicates a folded group
149  bool hidden; // not shown (because an ancestor is a folded group)
151 
152  uint32_t gc; // color
153 
154  char left_linewidth; // @@@ it's stupid to store linewidth IN FATHER (also wastes space)
156 
157  unsigned leaf_sum; // number of leafs below this node
158  unsigned mark_sum; // number of marked leafs below this node
159  unsigned view_sum; // virtual size of node for display (at folded groups: sqrt(leaf_sum); otherwise sum of childs view_sum)
160 
161  float max_tree_depth; // max length of path; for drawing triangles
162  float min_tree_depth; // min length of path; for drawing triangle
163  float spread;
164 
165  float left_angle; // @@@ it's stupid to store angles IN FATHER (also wastes space)
166  float right_angle;
167 
169  spread = tree_defaults::SPREAD;
170  }
172  left_angle = tree_defaults::ANGLE;
173  right_angle = tree_defaults::ANGLE;
174  }
176  left_linewidth = tree_defaults::LINEWIDTH;
177  right_linewidth = tree_defaults::LINEWIDTH;
178  }
183  }
184 
185  void clear() {
187 
188  grouped = false;
189  hidden = false;
190  callback_exists = false;
191  gc = 0;
192  leaf_sum = 0;
193  mark_sum = 0;
194  view_sum = 0;
195  max_tree_depth = 0;
196  min_tree_depth = 0;
197  }
198 
200  std::swap(left_linewidth, right_linewidth);
201 
202  // angles need to change orientation when swapped
203  // (they are relative angles, i.e. represent the difference to the default-angle)
204  float org_left = left_angle;
205  left_angle = -right_angle;
206  right_angle = -org_left;
207  }
208 };
209 
210 class AP_tree : public ARB_seqtree {
211  static AP_TreeShader *shader;
212 
213 public: // @@@ fix public members
215 
216  // ------------------
217  // functions
218 private:
219  void load_node_info(); // load linewidth etc from DB
220  GB_ERROR swap_group_with(AP_tree *dest, bool swapKeeled);
221 
222  char& linewidth_ref() {
223  AP_tree_members& tm = get_father()->gr;
224  return is_leftson() ? tm.left_linewidth : tm.right_linewidth;
225  }
226  const char& linewidth_ref() const { return const_cast<AP_tree*>(this)->linewidth_ref(); }
227 
228  float& angle_ref() {
229  AP_tree_members& tm = get_father()->gr;
230  return is_leftson() ? tm.left_angle : tm.right_angle;
231  }
232  const float& angle_ref() const { return const_cast<AP_tree*>(this)->angle_ref(); }
233 
234  static inline int force_legal_width(int width) { return width<0 ? 0 : (width>128 ? 128 : width); }
235 
236  void buildLeafList_rek(AP_tree **list, long& num);
237 
238  const AP_tree *flag_branch() const { return get_father()->get_father() ? this : get_father()->get_leftson(); }
239 
240  void reset_child_angles();
241  void reset_child_linewidths();
242  void reset_child_layout();
243 
244  template<class RESULT> RESULT update_subtree_information(const group_scaling& gscaling);
245 
246  GB_ERROR update_and_write_folding(GBDATA *gb_tree, const group_scaling& gscaling);
247  inline void recalc_view_sum(const group_scaling& gscaling);
248  inline void recalc_hidden();
249 
250  inline void remove_root_remark() {
251  // removes remark from root edge.
252  //
253  // Legal states:
254  // - both sons have same comment
255  // - 1 son is a leaf, other son has comment
256  // - no son has comment
257  //
258  // Also removes comments from illegal states.
259  // see also: has_valid_root_remarks()
260 
262  if (!leftson->is_leaf()) leftson->remove_remark();
265  }
266  inline void smart_remove_remark() {
267  // removes remark (if there is any).
268  // when called for son of root -> automatically removes remark from brother.
269  if (father) {
270  if (is_son_of_root()) get_father()->remove_root_remark();
271  else if (!is_leaf()) remove_remark();
272  }
273  }
274  inline void remove_remarks_from_this_and_parent() {
275  if (father) {
276  get_father()->smart_remove_remark();
277  smart_remove_remark();
278  }
279  }
280 
281 protected:
282  ~AP_tree() OVERRIDE;
283  friend class AP_tree_root; // allowed to call dtor
284 public:
285  explicit AP_tree(AP_tree_root *troot)
286  : ARB_seqtree(troot)
287  {
288  gr.clear();
289  }
290 
292 
294 
296 
297  unsigned count_leafs() const;
298  unsigned get_leaf_count() const OVERRIDE { // assumes compute_tree has been called (since last tree modification)
299  return gr.leaf_sum;
300  }
301 
302 
303  void load_subtree_info(); // recursive load_node_info (no need to call, called by loadFromDB)
304 
305  int colorize(GB_HASH *hashptr); // function for coloring the tree; ak
306  void uncolorize() { compute_tree(); }
307 
308  virtual void insert(AP_tree *new_brother);
309  virtual void initial_insert(AP_tree *new_brother, AP_tree_root *troot);
310  virtual AP_tree *REMOVE();
311 
313  ap_assert(!is_leaf()); // @@@ if this never fails -> remove condition below
314  if (!is_leaf()) {
316  gr.swap_son_layout();
317  }
318  }
319 
320  GB_ERROR cantMoveNextTo(AP_tree *new_brother); // use this to detect impossible moves
321  virtual void moveNextTo(AP_tree *new_brother, AP_FLOAT rel_pos); // move to new brother
322 
324  GB_ERROR relink() __ATTR__USERESULT; // @@@ used ? if yes -> move to AP_tree_root or ARB_seqtree_root
325 
326  int get_linewidth() const { return is_root_node() ? 0 : linewidth_ref(); }
327  void set_linewidth(int width) { if (father) linewidth_ref() = force_legal_width(width); }
329  void set_linewidth_recursive(int width);
330 
331  float get_angle() const { return is_root_node() ? 0.0 : angle_ref(); }
332  void set_angle(float angle) {
333  if (father) {
334  angle_ref() = angle;
335  if (get_father()->is_root_node()) {
336  // always set angle of other son at root-node
337  // @@@ works wrong if locigal-zoom is active
338  get_brother()->angle_ref() = angle;
339  }
340  }
341  }
343 
344  void buildLeafList(AP_tree **&list, long &num); // returns a list of leafs
345 
347 
348  bool is_folded_group() const {
349  return
350  (gr.grouped && is_normal_group())
351  ||
352  (father && get_father()->gr.grouped && is_keeled_group());
353  }
354  bool is_inside_folded_group() const;
355 
356  void mark_duplicates();
357  const char *mark_long_branches(double min_rel_diff, double min_abs_diff, double& found_max_abs_diff);
358  const char *mark_deep_leafs(int min_depth, double min_rootdist, int& found_max_depth, double& found_max_rootdist);
359  double mark_degenerated_branches(double degeneration_factor);
360  const char *analyse_distances();
361 
363  void relink_tree(GBDATA *gb_main, void (*relinker)(GBDATA *&ref_gb_node, char *&ref_name, GB_HASH *organism_hash), GB_HASH *organism_hash);
364 
365  // reset-functions below affect 'this' and childs:
366  void reset_subtree_spreads();
367  void reset_subtree_angles();
369  void reset_subtree_layout();
370 
371  static void set_tree_shader(AP_TreeShader *new_shader);
372  static const AP_TreeShader *get_tree_shader() { return shader; }
373 
374  bool hasName(const char *Name) const { return Name && name && Name[0] == name[0] && strcmp(Name, name) == 0; }
375 
376 #if defined(ASSERTION_USED) || defined(UNIT_TESTS)
377  bool has_correct_mark_flags() const;
378 #endif
380 };
383 MARK_NONFINAL_METHOD(AP_tree,swap_sons,());
385 
386 inline TreeNode *AP_tree_root::makeNode() const { return new AP_tree(const_cast<AP_tree_root*>(this)); }
387 inline void AP_tree_root::destroyNode(TreeNode *node) const { delete DOWNCAST(AP_tree*, node); }
388 
389 #else
390 #error AP_Tree.hxx included twice
391 #endif // AP_TREE_HXX
float get_angle() const
Definition: AP_Tree.hxx:331
bool callback_exists
Definition: AP_Tree.hxx:150
void reset_subtree_angles()
Definition: AP_Tree.cxx:1626
const char * GB_ERROR
Definition: arb_core.h:25
unsigned view_sum
Definition: AP_Tree.hxx:159
long remove_leafs(AWT_RemoveType awt_remove_type)
Definition: AP_Tree.cxx:944
char left_linewidth
Definition: AP_Tree.hxx:154
void change_root(TreeNode *old, TreeNode *newroot) FINAL_OVERRIDE
Definition: AP_Tree.cxx:223
void buildLeafList(AP_tree **&list, long &num)
Definition: AP_Tree.cxx:933
virtual void swap_sons()
Definition: TreeNode.h:512
void recompute_and_write_folding()
Definition: AP_Tree.cxx:754
char right_linewidth
Definition: AP_Tree.hxx:155
GB_ERROR move_group_to(AP_tree *new_group) __ATTR__USERESULT
Definition: AP_Tree.cxx:627
float right_angle
Definition: AP_Tree.hxx:166
~AP_rates()
Definition: AP_Tree.cxx:78
unsigned get_leaf_count() const OVERRIDE
Definition: AP_Tree.hxx:298
PREPARE_MARK_NONFINAL_CLASS(AP_tree)
virtual void moveNextTo(AP_tree *new_brother, AP_FLOAT rel_pos)
Definition: AP_Tree.cxx:351
char * init(AP_filter *fil)
Definition: AP_Tree.cxx:49
unsigned mark_sum
Definition: AP_Tree.hxx:158
float min_tree_depth
Definition: AP_Tree.hxx:162
void swap_son_layout()
Definition: AP_Tree.hxx:199
unsigned leaf_sum
Definition: AP_Tree.hxx:157
void set_node_deleted_callback(AP_nodeDelCb cb, void *cd)
Definition: AP_Tree.cxx:253
AP_FLOAT * rates
Definition: AP_Tree.hxx:49
POS_TREE1 * get_father() const
Definition: probe_tree.h:211
void reset_angle()
Definition: AP_Tree.hxx:342
bool is_folded_group() const
Definition: AP_Tree.hxx:348
#define DEFAULT_BRANCH_LENGTH
Definition: arbdbt.h:18
const char * analyse_distances()
Definition: AP_Tree.cxx:1461
void load_subtree_info()
Definition: AP_Tree.cxx:454
GB_ERROR tree_write_tree_rek(GBDATA *gb_tree)
Definition: AP_Tree.cxx:520
void(* AP_nodeDelCb)(void *cd, AP_tree *del)
Definition: AP_Tree.hxx:79
AP_tree_root(AliView *aliView, AP_sequence *seq_proto, bool add_delete_callbacks, const group_scaling *scaling)
Definition: AP_Tree.cxx:85
MARK_NONFINAL_METHOD(AP_tree_root, destroyNode,(TreeNode *) const)
AP_tree_members gr
Definition: AP_Tree.hxx:214
int colorize(GB_HASH *hashptr)
Definition: AP_Tree.cxx:846
const char * mark_long_branches(double min_rel_diff, double min_abs_diff, double &found_max_abs_diff)
Definition: AP_Tree.cxx:1299
GB_ERROR cantMoveNextTo(AP_tree *new_brother)
Definition: AP_Tree.cxx:338
float left_angle
Definition: AP_Tree.hxx:165
void swap_sons() OVERRIDE
Definition: AP_Tree.hxx:312
const float LENGTH
Definition: AP_Tree.hxx:142
bool hasName(const char *Name) const
Definition: AP_Tree.hxx:374
void reset_subtree_linewidths()
Definition: AP_Tree.cxx:1630
virtual void insert(AP_tree *new_brother)
Definition: AP_Tree.cxx:178
const float ANGLE
Definition: AP_Tree.hxx:140
#define cb(action)
TreeNode * rightson
Definition: TreeNode.h:131
#define DOWNCAST(totype, expr)
Definition: downcast.h:141
#define FINAL_OVERRIDE
Definition: cxxforward.h:95
double AP_FLOAT
Definition: AP_matrix.hxx:27
AP_UPDATE_FLAGS
Definition: AP_Tree.hxx:28
unsigned count_leafs() const
Definition: AP_Tree.cxx:840
virtual AP_tree * REMOVE()
Definition: AP_Tree.cxx:259
bool has_valid_root_remarks() const
Definition: TreeNode.cxx:778
void set_linewidth_recursive(int width)
Definition: AP_Tree.cxx:1601
long species_timer
Definition: AP_Tree.hxx:96
POS_TREE1 * get_father() const
Definition: probe_tree.h:49
long update
Definition: AP_Tree.hxx:52
void set_angle(float angle)
Definition: AP_Tree.hxx:332
void compute_tree() FINAL_OVERRIDE
Definition: AP_Tree.cxx:876
PREPARE_MARK_NONFINAL_CLASS(AP_tree_root)
bool is_son_of_root() const
Definition: TreeNode.h:215
int get_linewidth() const
Definition: AP_Tree.hxx:326
DEFINE_TREE_ACCESSORS(AP_tree_root, AP_tree)
const float SPREAD
Definition: AP_Tree.hxx:139
AWT_RemoveType
Definition: AP_Tree.hxx:35
bool is_leftson() const
Definition: TreeNode.h:188
MARK_NONFINAL_FUNCTION(AP_tree_root, GB_ERROR, saveToDB,(), NULp)
void reset_linewidth()
Definition: AP_Tree.hxx:328
void mark_duplicates()
Definition: AP_Tree.cxx:1530
TreeNode * father
Definition: TreeNode.h:131
void print()
Definition: AP_Tree.cxx:30
bool is_species_updated()
Definition: AP_Tree.cxx:117
bool is_root_node() const
Definition: TreeNode.h:391
void relink_tree(GBDATA *gb_main, void(*relinker)(GBDATA *&ref_gb_node, char *&ref_name, GB_HASH *organism_hash), GB_HASH *organism_hash)
Definition: AP_Tree.cxx:1575
CONSTEXPR_INLINE_Cxx14 void swap(unsigned char &c1, unsigned char &c2)
Definition: ad_io_inline.h:19
GB_ERROR loadFromDB(const char *name) FINAL_OVERRIDE
Definition: AP_Tree.cxx:891
bool is_keeled_group() const
Definition: TreeNode.h:434
bool is_tree_updated()
Definition: AP_Tree.cxx:108
TreeNode * get_brother()
Definition: TreeNode.h:394
void reset_subtree_spreads()
Definition: AP_Tree.cxx:1619
DEFINE_TREE_ROOT_ACCESSORS(AP_tree_root, AP_tree)
#define ap_assert(cond)
void(* AP_rootChangedCb)(void *cd, AP_tree *old, AP_tree *newroot)
Definition: AP_Tree.hxx:78
void reset_both_child_linewidths()
Definition: AP_Tree.hxx:175
bool is_inside_folded_group() const
Definition: AP_Tree.cxx:1640
TreeNode * leftson
Definition: TreeNode.h:131
bool has_been_set() const
Definition: AP_Tree.hxx:68
char * gone_tree_name
Definition: AP_Tree.hxx:93
double pow
Definition: AP_Tree.hxx:63
AP_rates * rates
Definition: AP_Tree.hxx:98
AP_filter * filter
Definition: AP_Tree.hxx:51
double mark_degenerated_branches(double degeneration_factor)
Definition: AP_Tree.cxx:1496
long tree_timer
Definition: AP_Tree.hxx:95
GB_ERROR saveToDB() OVERRIDE
Definition: AP_Tree.cxx:536
void remove_remark()
Definition: TreeNode.h:285
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 reset_subtree_layout()
Definition: AP_Tree.cxx:1634
bool has_correct_mark_flags() const
Definition: AP_Tree.cxx:670
void update_timers()
Definition: AP_Tree.cxx:125
#define OVERRIDE
Definition: cxxforward.h:93
AP_rates()
Definition: AP_Tree.cxx:45
~AP_tree_root() OVERRIDE
Definition: AP_Tree.cxx:102
#define __ATTR__USERESULT
Definition: attributes.h:58
char * name
Definition: TreeNode.h:134
void justify_branch_lenghs(GBDATA *gb_main)
Definition: AP_Tree.cxx:1559
TreeNode * makeNode() const OVERRIDE
Definition: AP_Tree.hxx:386
double linear
Definition: AP_Tree.hxx:62
const char LINEWIDTH
Definition: AP_Tree.hxx:141
#define NULp
Definition: cxxforward.h:97
~AP_tree() OVERRIDE
Definition: AP_Tree.cxx:142
const group_scaling * get_group_scaling() const
Definition: AP_Tree.hxx:122
const char * mark_deep_leafs(int min_depth, double min_rootdist, int &found_max_depth, double &found_max_rootdist)
Definition: AP_Tree.cxx:1305
void reset_child_layout()
Definition: AP_Tree.hxx:179
long rate_len
Definition: AP_Tree.hxx:50
static const AP_TreeShader * get_tree_shader()
Definition: AP_Tree.hxx:372
GBDATA * gb_main
Definition: adname.cxx:33
static void set_tree_shader(AP_TreeShader *new_shader)
Definition: AP_Tree.cxx:704
void set_linewidth(int width)
Definition: AP_Tree.hxx:327
MARK_NONFINAL_CLASS(AP_tree_root)
void set_root_changed_callback(AP_rootChangedCb cb, void *cd)
Definition: AP_Tree.cxx:248
uint32_t gc
Definition: AP_Tree.hxx:152
GB_ERROR relink() __ATTR__USERESULT
Definition: AP_Tree.cxx:900
float max_tree_depth
Definition: AP_Tree.hxx:161
bool is_normal_group() const
Definition: TreeNode.h:429
void reset_both_child_angles()
Definition: AP_Tree.hxx:171
void destroyNode(TreeNode *node) const OVERRIDE
Definition: AP_Tree.hxx:387
void inform_about_delete(AP_tree *old)
Definition: AP_Tree.cxx:244
GBDATA * gb_tree_gone
Definition: AP_Tree.hxx:92
void reset_child_spread()
Definition: AP_Tree.hxx:168
virtual AP_UPDATE_FLAGS check_update()
Definition: AP_Tree.cxx:907
void uncolorize()
Definition: AP_Tree.hxx:306