ARB
group_search.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : group_search.cxx //
4 // Purpose : provides group search functionality //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in April 2017 //
7 // http://www.arb-home.de/ //
8 // //
9 // ============================================================= //
10 
11 #include "group_search.h"
12 
13 #include <arb_strarray.h>
14 #include <arb_progress.h>
15 #include <arb_sort.h>
16 #include <arb_strbuf.h>
17 #include <arb_defs.h>
18 
19 #include <gb_aci_impl.h>
20 
21 #include <ad_cb.h>
22 #include <TreeNode.h>
23 
24 #include <map>
25 #include <stack>
26 #include <arb_misc.h>
27 
28 using namespace std;
29 
30 class GroupSearchTree;
31 
32 class GroupSearchRoot FINAL_TYPE : public TreeRoot {
33 public:
36  {}
37  ~GroupSearchRoot() FINAL_OVERRIDE { predelete(); }
38 
39  DEFINE_TREE_ROOT_ACCESSORS(GroupSearchRoot, GroupSearchTree);
40 
41  // TreeRoot interface
42  inline TreeNode *makeNode() const OVERRIDE;
43  inline void destroyNode(TreeNode *node) const OVERRIDE;
44 };
45 
46 class GroupSearchTree FINAL_TYPE : public TreeNode {
47  mutable Lazy<int,-1> size; // number of leafs (=zombies+species); -1 -> need update
48  mutable Lazy<int,-1> marked; // number of marked species; -1 -> need update
49  mutable Lazy<int,-1> zombies; // number of zombies
50  mutable LazyFloat<double> aid; // average ingroup distance
51 
52  enum UpdateWhat {
53  UPDATE_SIZE, // quick (update 'size' only)
54  UPDATE_MARKED, // slow (update all)
55  };
56 
57  void update_info(UpdateWhat what) const;
58  void calc_average_ingroup_distance(int group_size) const;
59  double weighted_branchlength_sum(int group_size) const;
60 
61  static GBDATA *gb_species_data;
62 
63 public:
64  GroupSearchTree(GroupSearchRoot *root) :
65  TreeNode(root)
66  {}
67 
68  DEFINE_TREE_RELATIVES_ACCESSORS(GroupSearchTree);
69 
70  static void set_species_data(GBDATA *gb_species_data_) { gb_species_data = gb_species_data_; }
71 
72  // TreeNode interface
73  unsigned get_leaf_count() const FINAL_OVERRIDE {
74  if (size.needs_eval()) update_info(UPDATE_SIZE);
75  return size;
76  }
77  void compute_tree() OVERRIDE {
78  gs_assert(0); // should be unused
79  }
80 
81  unsigned get_marked_count() const {
82  if (marked.needs_eval()) update_info(UPDATE_MARKED);
83  return marked;
84  }
85  unsigned get_zombie_count() const {
86  if (zombies.needs_eval()) update_info(UPDATE_MARKED);
87  return zombies;
88  }
89 
91  if (aid.needs_eval()) calc_average_ingroup_distance(get_leaf_count());
92  return aid;
93  }
94 };
95 
97 
98 inline TreeNode *GroupSearchRoot::makeNode() const { return new GroupSearchTree(const_cast<GroupSearchRoot*>(this)); }
99 inline void GroupSearchRoot::destroyNode(TreeNode *node) const { delete DOWNCAST(GroupSearchTree*,node); }
100 
101 void GroupSearchTree::update_info(UpdateWhat what) const {
102  if (is_leaf()) {
103  size = 1;
104  if (what == UPDATE_MARKED) {
106 
108  if (gb_species) {
109  marked = GB_read_flag(gb_species);
110  zombies = 0;
111  }
112  else {
113  marked = 0;
114  zombies = 1;
115  }
116  }
117  }
118  else {
119  switch (what) {
120  case UPDATE_MARKED:
121  marked = get_leftson()->get_marked_count() + get_rightson()->get_marked_count(); // triggers lazy-update (UPDATE_MARKED)
122  zombies = get_leftson()->get_zombie_count() + get_rightson()->get_zombie_count();
123  // fall-through
124  case UPDATE_SIZE:
125  size = get_leftson()->get_leaf_count() + get_rightson()->get_leaf_count(); // triggers lazy-update (UPDATE_SIZE)
126  break;
127  }
128  }
129 }
130 
132 
134  string name;
135  RefPtr<GBDATA> gb_tree;
136  long inner_nodes; // number of inner nodes in binary tree
137 
138  GroupSearchRootPtr troot; // (optional) loaded tree
139  string load_error;
140 
141  void load_tree() {
142  gs_assert(!tree_is_loaded() && !failed_to_load());
143  troot = new GroupSearchRoot;
144  TreeNode *rootNode = GBT_read_tree(GB_get_root(gb_tree), get_name(), &*troot);
145  gs_assert(implicated(rootNode, !rootNode->is_normal_group())); // otherwise parent caching will get confused
146  if (!rootNode) {
147  load_error = GB_await_error();
148  }
149  else {
150  gs_assert(rootNode == troot->get_root_node());
151  }
152  }
153 
154 public:
155  SearchedTree(const char *name_, GBDATA *gb_main) :
156  name(name_),
157  gb_tree(GBT_find_tree(gb_main, name_)),
158  inner_nodes(-1)
159  {
160  gs_assert(gb_tree);
161  GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
162  if (gb_nnodes) inner_nodes = GB_read_int(gb_nnodes); // see GBT_size_of_tree
163  }
164 
165  GBDATA *get_tree_data() { return gb_tree; }
166  const char *get_name() const { return name.c_str(); }
167 
168  int get_leaf_count() const { return inner_nodes+1; }
169  int get_edge_iteration_count() const { return ARB_edge::iteration_count(get_leaf_count()); }
170 
171  bool tree_is_loaded() const { return troot.isSet(); }
172  bool failed_to_load() const { return !load_error.empty(); }
173  const char *get_load_error() const {
174  gs_assert(failed_to_load());
175  return load_error.c_str();
176  }
177  GroupSearchRoot *get_tree_root() {
178  if (!tree_is_loaded()) load_tree();
179  return failed_to_load() ? NULp : &*troot;
180  }
181  void flush_loaded_tree() { troot.setNull(); }
182 };
183 
184 typedef vector<SearchedTree> SearchedTreeContainer;
185 typedef SearchedTreeContainer::iterator SearchedTreeIter;
186 
187 const char *FoundGroup::get_name() const {
188  GBDATA *gb_name = GB_search(gb_group, "group_name", GB_STRING);
189  return gb_name ? GB_read_char_pntr(gb_name) : NULp;
190 }
191 int FoundGroup::get_name_length() const {
192  GB_transaction ta(gb_group);
193  GBDATA *gb_name = GB_search(gb_group, "group_name", GB_STRING);
194  return GB_read_string_count(gb_name);
195 }
196 
198  return GB_get_father(gb_group);
199 }
200 
201 const char *FoundGroup::get_tree_name() const {
202  GBDATA *gb_tree = get_tree_data();
203  return gb_tree ? GB_read_key_pntr(gb_tree) : NULp;
204 }
205 
207  GBDATA *gb_tree = GB_get_father(gb_group);
208  int order = -1;
209  if (gb_tree) {
210  GBDATA *gb_order = GB_entry(gb_tree, "order");
211  if (gb_order) {
212  order = GB_read_int(gb_order);
213  }
214  }
215  return order;
216 }
217 
219  GB_ERROR error = NULp;
220  GB_transaction ta(gb_group);
221 
222  GBDATA *gb_gname = GB_entry(gb_group, "group_name");
223  gs_assert(gb_gname); // groups shall always have a name
224  if (gb_gname) error = GB_delete(gb_gname);
225 
226  if (!error) {
227  GBDATA *gb_grouped = GB_entry(gb_group, "grouped");
228  if (gb_grouped) error = GB_delete(gb_grouped);
229  }
230 
231  if (!error) {
232  bool keep_node = false;
233  GBQUARK qid = GB_find_existing_quark(gb_group, "id");
234  for (GBDATA *gb_child = GB_child(gb_group); gb_child && !keep_node; gb_child = GB_nextChild(gb_child)) {
235  if (GB_get_quark(gb_child) != qid) {
236  keep_node = true;
237  }
238  }
239  if (!keep_node) { // no child beside "id" left -> delete node
240  error = GB_delete(gb_group.pointer_ref());
241  }
242  }
243 
244  return error;
245 }
246 
247 ARB_ERROR FoundGroup::rename_by_ACI(const char *acisrt, const QueriedGroups& results, int hit_idx) {
249  GB_transaction ta(gb_group);
250 
251  GBDATA *gb_gname = GB_entry(gb_group, "group_name");
252  if (!gb_gname) {
253  gs_assert(0); // groups shall always have a name
254  error = "FATAL: unnamed group detected";
255  }
256  else {
257  char *old_name = GB_read_string(gb_gname);
258  char *new_name = GS_calc_resulting_groupname(gb_group, results, hit_idx, old_name, acisrt, error);
259 
260  if (!error && new_name[0]) { // if ACI produces empty result -> skip rename
261  error = GBT_write_group_name(gb_gname, new_name, true);
262  }
263 
264  free(new_name);
265  free(old_name);
266  }
267 
268  return error;
269 }
270 
271 inline bool group_is_folded(GBDATA *gb_group) {
272  if (!gb_group) return false;
273  GBDATA *gb_grouped = GB_entry(gb_group, "grouped");
274  return gb_grouped && GB_read_byte(gb_grouped) != 0;
275 }
276 inline ARB_ERROR group_set_folded(GBDATA *gb_group, bool folded) {
277  gs_assert(gb_group);
278 
280  GBDATA *gb_grouped = GB_entry(gb_group, "grouped");
281 
282  if (!gb_grouped && folded) {
283  gb_grouped = GB_create(gb_group, "grouped", GB_BYTE);
284  if (!gb_grouped) error = GB_await_error();
285  }
286  if (gb_grouped) {
287  gs_assert(!error);
288  error = GB_write_byte(gb_grouped, folded);
289  }
290 #if defined(ASSERTION_USED)
291  else gs_assert(!folded);
292 #endif
293  return error;
294 }
295 
297  return group_is_folded(get_overlap_group());
298 }
299 bool FoundGroup::is_folded() const {
300  return group_is_folded(gb_group);
301 }
302 
303 ARB_ERROR FoundGroup::set_folded(bool folded) {
304  return group_set_folded(gb_group, folded);
305 }
306 ARB_ERROR FoundGroup::set_overlap_folded(bool folded) {
307  return group_set_folded(get_overlap_group(), folded);
308 }
309 
311  GB_transaction ta(gb_group);
312 
314 
315  bool was_folded = is_folded();
316  bool knows_overlap = knows_details(); // may be false when called by fold_found_groups(); acceptable
317  bool overlap_was_folded = knows_overlap && overlap_is_folded();
318  bool want_folded = was_folded;
319 
320  switch (mode) {
321  case GFM_TOGGLE: want_folded = !(was_folded || overlap_was_folded); break;
322  case GFM_COLLAPSE: want_folded = true; break;
323  case GFM_EXPAND: want_folded = false; break;
324  default: error = "invalid collapse mode"; gs_assert(0); break;
325  }
326 
327  if (!error && want_folded != was_folded) {
328  error = set_folded(want_folded);
329  }
330  if (!error && want_folded != overlap_was_folded && knows_overlap && gb_overlap_group) {
331  error = set_overlap_folded(want_folded);
332  }
333 
334  return error;
335 }
336 
337 void ColumnWidths::track(int wName, int wReason, int nesting, int size, int marked, int clusID, double aid, bool keeled) {
338  seen_keeled = seen_keeled || keeled;
339 
340  // track max. width:
341  name = std::max(name, wName);
342  reason = std::max(reason, wReason);
343 
344  // track max. value:
345  max_nesting = std::max(max_nesting, nesting);
346  max_size = std::max(max_size, size);
347  max_marked = std::max(max_marked, marked);
348  max_marked_pc = std::max(max_marked_pc, percent(marked, size));
349  max_cluster_id = std::max(max_cluster_id, clusID);
350  max_aid = std::max(max_aid, int(aid));
351 }
353  gs_assert(knows_details());
354  widths.track(get_name_length(),
355  get_hit_reason().length(),
356  nesting,
357  size,
358  marked,
359  clusterID,
360  aid,
361  keeled);
362 }
363 
364 // ---------------------
365 // ParentCache
366 
367 class ParentCache : virtual Noncopyable {
368  typedef map<GBDATA*,GBDATA*> Cache;
369  Cache cache;
370 
371 public:
372  void defineParentOf(GBDATA *gb_child_group, GBDATA *gb_parent_group) {
373  // gb_parent_group may be NULp
374  gs_assert(gb_child_group);
375  cache[gb_child_group] = gb_parent_group;
376  }
377  GBDATA *lookupParent(GBDATA *gb_child_group) const {
378  Cache::const_iterator found = cache.find(gb_child_group);
379  return found == cache.end() ? NULp : found->second;
380  }
381 
382  void fix_deleted_groups(const GBDATAset& deleted_groups) {
383  ParentCache translate; // translation table: oldDelParent -> newExistingParent (or NULp at top-level)
384  for (GBDATAset::const_iterator del = deleted_groups.begin(); del != deleted_groups.end(); ++del) {
385  GBDATA *gb_remaining_father = lookupParent(*del);
386  if (gb_remaining_father) { // otherwise 'del' point to sth unkown (see comment in GroupSearchCommon)
387  while (gb_remaining_father) {
388  if (deleted_groups.find(gb_remaining_father) == deleted_groups.end()) {
389  break; // not deleted -> use as replacement
390  }
391  gb_remaining_father = lookupParent(gb_remaining_father);
392  }
393  translate.defineParentOf(*del, gb_remaining_father);
394  }
395  }
396 
397  // erase deleted nodes from cache
398  for (GBDATAset::const_iterator del = deleted_groups.begin(); del != deleted_groups.end(); ++del) {
399  cache.erase(*del);
400  }
401 
402  // translate remaining entries
403  for (Cache::iterator c = cache.begin(); c != cache.end(); ++c) {
404  GBDATA *gb_child = c->first;
405  GBDATA *gb_parent = c->second;
406  if (deleted_groups.find(gb_parent) != deleted_groups.end()) {
407  defineParentOf(gb_child, translate.lookupParent(gb_parent));
408  }
409  }
410  }
411 };
412 
413 // ---------------------------
414 // GroupSearchCommon
415 
416 #define TRIGGER_UPDATE_GROUP_RESULTS "/tmp/trigger/group_result_update"
417 
419  // controls and maintains validity of existing group-search-results
420 
421  typedef set<GroupSearch*> GroupSearchSet;
422 
423  GroupSearchSet searches; // all existing searches (normally only one)
424 
425  bool cbs_installed;
426  GBDATA *gb_trigger; // TRIGGER_UPDATE_GROUP_RESULTS (triggers ONCE for multiple DB changes)
427 
428  // The following two sets may also contain "node" entries from
429  // completely different parts of the DB -> do not make assumptions!
430  GBDATAset deleted_groups; // entries are "deleted", i.e. access is invalid! Only comparing pointers is defined!
431  GBDATAset modified_groups;
432 
433  ParentCache pcache;
434 
435  void add_callbacks(GBDATA *gb_main);
436  void remove_callbacks(GBDATA *gb_main);
437 
438  void trigger_group_search_update() { GB_touch(gb_trigger); }
439 
440 public:
442  cbs_installed(false),
443  gb_trigger(NULp)
444  {}
446  gs_assert(!cbs_installed);
447  }
448 
449  ParentCache& get_parent_cache() { return pcache; }
450 
451  void notify_deleted(GBDATA *gb_node) { deleted_groups.insert(gb_node); trigger_group_search_update(); }
452  void notify_modified(GBDATA *gb_node) { modified_groups.insert(gb_node); trigger_group_search_update(); }
453 
454  bool has_been_deleted(GBDATA *gb_node) { return deleted_groups.find(gb_node) != deleted_groups.end(); }
455  bool has_been_modified(GBDATA *gb_node) { return modified_groups.find(gb_node) != modified_groups.end(); }
456 
457  void add(GroupSearch *gs) {
458  if (empty()) {
459  GBDATA *gb_main = gs->get_gb_main();
460  add_callbacks(gb_main);
461  }
462  searches.insert(gs);
463  }
464  void remove(GroupSearch *gs) {
465  searches.erase(gs);
466  if (empty()) {
467  GBDATA *gb_main = gs->get_gb_main();
468  remove_callbacks(gb_main);
469  }
470  }
471  bool empty() const { return searches.empty(); }
472 
474  deleted_groups.clear();
475  modified_groups.clear();
476  }
478  return !(deleted_groups.empty() && modified_groups.empty());
479  }
480 
482  if (has_notifications()) {
483  pcache.fix_deleted_groups(deleted_groups);
484  for (GroupSearchSet::iterator gs = searches.begin(); gs != searches.end(); ++gs) {
485  GroupSearch *gr_search = *gs;
486  gr_search->refresh_results_after_DBchanges();
487  }
488  clear_notifications();
489  }
490  }
491 };
492 
494  bool mark_as_deleted = cbtype == GB_CB_DELETE;
495 
496  if (!mark_as_deleted) {
497  if (!GB_entry(gb_node, "group_name")) { // if group_name disappeared
498  mark_as_deleted = true;
499  }
500  }
501 
502  if (mark_as_deleted) {
503  common->notify_deleted(gb_node);
504  }
505  else {
506  common->notify_modified(gb_node);
507  }
508 }
509 static void group_name_changed_cb(GBDATA *gb_group_name, GroupSearchCommon *common) {
510  GBDATA *gb_node = GB_get_father(gb_group_name);
511  if (gb_node) {
512  common->notify_modified(gb_node);
513  }
514 }
515 static void result_update_cb(GBDATA*, GroupSearchCommon *common) {
516  // is called once after DB changes that might affect validity of group-search-results
517  common->refresh_all_results();
518 }
519 
520 void GroupSearchCommon::add_callbacks(GBDATA *gb_main) {
521  gs_assert(!cbs_installed);
522 
523  GB_transaction ta(gb_main);
524  gb_trigger = GB_search(gb_main, TRIGGER_UPDATE_GROUP_RESULTS, GB_INT);
525 
526  GB_ERROR error = GB_add_hierarchy_callback(gb_main, "node", GB_CB_CHANGED_OR_DELETED, makeDatabaseCallback(tree_node_deleted_cb, this));
527  if (!error) error = GB_add_hierarchy_callback(gb_main, "node/group_name", GB_CB_CHANGED, makeDatabaseCallback(group_name_changed_cb, this));
528  if (!error) error = GB_add_callback(gb_trigger, GB_CB_CHANGED, makeDatabaseCallback(result_update_cb, this));
529 
530  if (error) GBT_message(gb_main, GBS_global_string("Failed to bind callback (Reason: %s)", error));
531  else cbs_installed = true;
532 }
533 
534 void GroupSearchCommon::remove_callbacks(GBDATA *gb_main) {
535  if (cbs_installed) {
536  GB_transaction ta(gb_main);
537  GB_ERROR error = GB_remove_hierarchy_callback(gb_main, "node", GB_CB_CHANGED_OR_DELETED, makeDatabaseCallback(tree_node_deleted_cb, this));
538  if (!error) error = GB_remove_hierarchy_callback(gb_main, "node/group_name", GB_CB_CHANGED, makeDatabaseCallback(group_name_changed_cb, this));
539  GB_remove_callback(gb_trigger, GB_CB_CHANGED, makeDatabaseCallback(result_update_cb, this));
540 
541  if (error) GBT_message(gb_main, GBS_global_string("Failed to remove callback (Reason: %s)", error));
542  else cbs_installed = false;
543  }
544 }
545 
546 // ---------------------
547 // GroupSearch
548 
549 GroupSearchCommon *GroupSearch::common = NULp;
550 
551 GroupSearch::GroupSearch(GBDATA *gb_main_, const GroupSearchCallback& redisplay_results_cb) :
552  gb_main(gb_main_),
553  redisplay_cb(redisplay_results_cb),
554  sortedByOrder(false)
555 {
556  if (!common) common = new GroupSearchCommon;
557  common->add(this);
558 }
559 
561  common->remove(this);
562  if (common->empty()) {
563  delete common;
564  common = NULp;
565  }
566 }
567 
568 static void collect_searched_trees(GBDATA *gb_main, const TreeNameSet& trees_to_search, SearchedTreeContainer& searched_tree) {
569  ConstStrArray tree_names;
570  GBT_get_tree_names(tree_names, gb_main, false);
571 
572  {
573  bool search_all = trees_to_search.empty();
574  for (int t = 0; tree_names[t]; ++t) {
575  if (search_all || trees_to_search.find(tree_names[t]) != trees_to_search.end()) {
576  searched_tree.push_back(SearchedTree(tree_names[t], gb_main));
577  }
578  }
579  }
580 }
581 
582 class Candidate : public FoundGroup {
583  // candidate for a search result
584  // - able to retrieve values (have tree to examine)
586 
587 public:
588  Candidate(const FoundGroup& group_, GroupSearchTree *node_) :
589  FoundGroup(group_),
590  node(node_)
591  {}
592  Candidate(GBDATA *gb_group_, GroupSearchTree *node_) :
593  FoundGroup(gb_group_),
594  node(node_)
595  {}
596 
597  FoundGroup& get_group() { return *this; }
598  const FoundGroup& get_group() const { return *this; }
599 
600  GroupSearchTree *get_clade() { // return node where clade is shown (differs from get_node for keeled groups)
601  TreeNode *keeld = node->keelTarget();
602  return keeld ? DOWNCAST(GroupSearchTree*, keeld) : &*node;
603  }
604  const GroupSearchTree *get_clade() const {
605  return const_cast<Candidate*>(this)->get_clade();
606  }
607 
608  int get_keeledStateInfo() const { return node->keeledStateInfo(); }
609 
610  void inform_group(const GroupSearch& group_search, const string& hitReason) {
611  // retrieve/store all information needed later (e.g. for sorting):
612  hit_reason = hitReason;
613 
614  GroupSearchTree *clade = get_clade();
615 
616  if (nesting.needs_eval()) nesting = group_search.calc_nesting_level(get_pointer());
617  if (size.needs_eval()) size = clade->get_leaf_count();
618  if (marked.needs_eval()) marked = clade->get_marked_count();
619  if (aid.needs_eval()) aid = clade->get_average_ingroup_distance();
620 
621  if (keeled.needs_eval()) {
623 
624  // set info needed for clade-overlap
625  if (keeled) {
626  if (!clade->is_leaf() && clade->is_normal_group()) { // got overlap
627  gb_overlap_group = clade->gb_node;
629  }
630  }
631  else {
632  if (node->is_keeled_group()) { // got overlap
633  gb_overlap_group = node->father->gb_node;
635  }
636  }
637 
638  }
639 
641  }
642 };
643 
644 class TargetGroup: public QueryTarget, virtual Noncopyable {
645  // wrapper to use Candidate as QueryTarget
646  SmartPtr<Candidate> cand;
647 
648 public:
649  TargetGroup(GBDATA *gb_main_, const char *treename_) :
650  QueryTarget(gb_main_, treename_)
651  {}
653 
654  void aimTo(const Candidate& c) { cand = new Candidate(c); }
655  void unAim() { cand.setNull(); }
656 
657  const FoundGroup& get_group() const { gs_assert(cand.isSet()); return cand->get_group(); }
658  const GroupSearchTree *get_clade() const { gs_assert(cand.isSet() && cand->get_clade()); return cand->get_clade(); }
659 
660  const char *get_group_name() const { return get_group().get_name(); }
661  unsigned get_group_size() const { return get_clade()->get_leaf_count(); }
662  unsigned get_marked_count() const { return get_clade()->get_marked_count(); }
663  unsigned get_zombie_count() const { return get_clade()->get_zombie_count(); }
664  double get_average_ingroup_distance() const { return get_clade()->get_average_ingroup_distance(); }
665  int get_keeledStateInfo() const { gs_assert(cand.isSet()); return cand->get_keeledStateInfo(); }
666 
667  // virtual QueryTarget interface:
668  GBDATA *get_ACI_item() const { return get_group().get_pointer(); }
669 };
670 
671 typedef list<Candidate> CandidateList;
672 
673 #if defined(ASSERTION_USED)
674 inline bool isCorrectParent(TreeNode *node, GBDATA *gb_group, GBDATA *gb_parent_group) {
682  gs_assert(node && gb_group);
683 
684  TreeNode *pnode = node->find_parent_with_groupInfo(true);
685  if (pnode) {
686  if (node->gb_node == gb_group) { // = node is not keeled
687  gs_assert(node->is_normal_group());
688  return pnode->gb_node == gb_parent_group;
689  }
690 
691  gs_assert(node->is_keeled_group()); // node is keeled
692  gs_assert(pnode->keelTarget() == node); // pnode is node storing that keeled node
693  gs_assert(pnode->gb_node == gb_group); // groupdata is attached at pnode
694 
695  TreeNode *ppnode = pnode->find_parent_with_groupInfo(true); // continue with next parent
696  if (ppnode) {
697  return ppnode->gb_node == gb_parent_group;
698  }
699  }
700 #if defined(ASSERTION_USED)
701  else {
702  gs_assert(node->gb_node == gb_group);
703  }
704 #endif
705 
706  return gb_parent_group == NULp;
707 }
708 #endif
709 
710 double GroupSearchTree::weighted_branchlength_sum(int group_size) const {
711  int leafs = get_leaf_count();
712  double sum = father ? get_branchlength() * leafs * (group_size-leafs) : 0.0;
713 
714  if (!is_leaf()) {
715  sum += get_leftson()->weighted_branchlength_sum(group_size);
716  sum += get_rightson()->weighted_branchlength_sum(group_size);
717  }
718 
719  return sum;
720 }
721 
722 void GroupSearchTree::calc_average_ingroup_distance(int group_size) const {
723  long pairs = long(group_size)*(group_size-1)/2; // warning: int-overflow with SSURef_NR99_128_SILVA_07_09_16_opt.arb
724 
725  if (pairs) {
726  double wbranchsum = weighted_branchlength_sum(group_size);
727  aid = wbranchsum / pairs;
728 
729  gs_assert(aid>=0);
730  }
731  else {
732  aid = 0;
733  }
734 }
735 
737  typedef set< RefPtr<GBDATA> > ExistingHits;
738 
739  ExistingHits existing_hits;
740  if (mode & GSM_FORGET_EXISTING) forget_results(); // from last search
741  else {
742  for (FoundGroupCIter prev = found->begin(); prev != found->end(); ++prev) {
743  existing_hits.insert(prev->get_pointer());
744  }
745  }
746 
747  bool match_unlisted = mode&GSM_ADD;
748 
749  if (query_expr.isNull()) addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*"); // default
750 
751  if (mode&GSM_MISMATCH) {
752  query_expr->negate();
753  }
754 
755  GB_ERROR error = NULp;
756  {
757  GB_transaction ta(gb_main);
758  SearchedTreeContainer searched_tree;
759 
760  GroupSearchTree::set_species_data(GBT_get_species_data(gb_main));
761 
762  collect_searched_trees(gb_main, trees_to_search, searched_tree);
763 
764  // calc overall iteration count (for progress)
765  long overall_iter_count = 0;
766  for (SearchedTreeIter st = searched_tree.begin(); st != searched_tree.end(); ++st) { // LOOP_VECTORIZED[!<6.0]
767  overall_iter_count += st->get_edge_iteration_count();
768  }
769 
770  // iterate over all trees
771  arb_progress progress("Searching groups", overall_iter_count);
772 
773  bool load_failures = false;
774  for (SearchedTreeIter st = searched_tree.begin(); !error && st != searched_tree.end(); ++st) {
775  GroupSearchRoot *troot = st->get_tree_root();
776 
777  TargetGroup target_group(gb_main, st->get_name());
778 
779  if (!troot) {
780  GBT_message(gb_main, GBS_global_string("Tree skipped: %s", st->get_load_error()));
781  progress.inc_by(st->get_edge_iteration_count());
782  load_failures = true;
783  }
784  else {
785  CandidateList candidate;
786  {
787  // search candidate groups (and populate parent-group cache on-the-fly)
788 
789  GBDATA *gb_parent_group = NULp; // last traversed parent group
790  ParentCache& pcache = common->get_parent_cache();
791  ARB_edge start = rootEdge(troot);
792  ARB_edge e = start;
793 
794  do {
795  switch (e.get_type()) {
796  case ROOT_EDGE:
797  gb_parent_group = NULp;
798  // fall-through
799  case EDGE_TO_LEAF: { // descent (store parents; perform match)
800  TreeNode *node = e.dest();
801  // [Note: order of if-tests is important, when keeled and normal group fall to same location]
802  if (node->is_keeled_group()) {
803  TreeNode *parent = e.source();
804  gs_assert(parent == node->get_father());
805 
806  GBDATA *gb_group = parent->gb_node;
807  pcache.defineParentOf(gb_group, gb_parent_group);
808  gs_assert(isCorrectParent(node, gb_group, gb_parent_group));
809  gb_parent_group = gb_group;
810  }
811  if (!node->is_leaf() && node->has_group_info()) {
812  GBDATA *gb_group = node->gb_node;
813 
814  if (node->is_normal_group()) {
815  pcache.defineParentOf(gb_group, gb_parent_group);
816  gs_assert(isCorrectParent(node, gb_group, gb_parent_group));
817  gb_parent_group = gb_group;
818  }
819 
820  ExistingHits::iterator prev_hit = existing_hits.find(gb_group);
821 
822  bool was_listed = prev_hit != existing_hits.end();
823  bool test_match = !was_listed == match_unlisted;
824 
825  if (test_match) { // store candidates
826  candidate.push_back(Candidate(gb_group, DOWNCAST(GroupSearchTree*, node)));
827  }
828  }
829  break;
830  }
831  case EDGE_TO_ROOT: { // ascent (restore parents)
832  TreeNode *node = e.source();
833  // [Note: order of if-tests is important, when keeled and normal group fall to same location]
834  if (!node->is_leaf() && node->is_normal_group()) {
835  GBDATA *gb_group = node->gb_node;
836  gb_parent_group = pcache.lookupParent(gb_group); // restore parent group
837  gs_assert(isCorrectParent(node, gb_group, gb_parent_group));
838  }
839  if (node->is_keeled_group()) {
840  TreeNode *parent = e.dest();
841  gs_assert(parent == node->get_father());
842 
843  GBDATA *gb_group = parent->gb_node;
844  gb_parent_group = pcache.lookupParent(gb_group); // restore parent group
845  gs_assert(isCorrectParent(node, gb_group, gb_parent_group));
846  }
847  break;
848  }
849  }
850 
851  error = progress.inc_and_error_if_aborted();
852  e = e.next();
853  }
854  while (e != start && !error);
855  }
856 
857  // now run queries for all candidates:
858  bool was_listed = !match_unlisted;
859  for (CandidateList::iterator cand = candidate.begin(); !error && cand != candidate.end(); ++cand) {
860  target_group.aimTo(*cand);
861 
862  string hit_reason;
863  if (query_expr->matches(target_group, hit_reason)) {
864  if (!was_listed) {
865  found->add_candidate(*this, *cand, hit_reason);
866  }
867  }
868  else {
869  if (was_listed) {
870  ExistingHits::iterator prev_hit = existing_hits.find(cand->get_group().get_pointer());
871  gs_assert(prev_hit != existing_hits.end()); // internal logic error
872  existing_hits.erase(prev_hit);
873  }
874  }
875  }
876  target_group.unAim();
877  st->flush_loaded_tree();
878  }
879  }
880 
881  if (load_failures) {
882  // remove failed trees from 'searched_tree'
883  SearchedTreeContainer reduced;
884  for (unsigned t = 0; t<searched_tree.size(); ++t) {
885  if (!searched_tree[t].failed_to_load()) {
886  reduced.push_back(searched_tree[t]);
887  }
888  }
889  int failed_trees = searched_tree.size()-reduced.size();
890  GBT_message(gb_main, GBS_global_string("%i tree(s) failed to load (will operate on rest)", failed_trees));
891  swap(reduced, searched_tree);
892  }
893 
894  if (!match_unlisted && !error) { // keep only hits still listed in existing_hits
895  QueriedGroups *kept = new QueriedGroups;
896 
897  for (FoundGroupCIter prev = found->begin(); prev != found->end(); ++prev) {
898  if (existing_hits.find(prev->get_pointer()) != existing_hits.end()) {
899  kept->add_informed_group(*prev);
900  }
901  }
902  found = kept;
903  }
904  }
905 
906  if (dups.isSet() && !error) {
907  // if elements were kept from last search, they have an outdated clusterID -> reset
908  for (FoundGroupIter g = found->begin(); g != found->end(); ++g) g->forget_cluster_id();
909 
910  error = clusterDuplicates();
911  }
912 
913  if (error) {
914  GBT_message(gb_main, error);
915  found = new QueriedGroups; // clear results
916  }
917 
918  sortedByOrder = false;
919 }
920 
921 // -----------------------------------------
922 // code for dupe-cluster detection
923 
924 inline bool contains(const WordSet& ws, const string& w) { return ws.find(w) != ws.end(); }
925 inline bool contains(const WordSet& ws, const char *w) { string W(w); return contains(ws, W); }
926 
927 static void string2WordSet(const char *name, WordSet& words, const char *wordSeparators, const WordSet& ignored_words) {
928  char *namedup = strdup(name);
929 
930  gs_assert(wordSeparators);
931 
932  ConstStrArray w;
933  GBT_splitNdestroy_string(w, namedup, wordSeparators, true);
934  for (int i = 0; w[i]; ++i) {
935  if (!contains(ignored_words, w[i])) words.insert(w[i]);
936  }
937 }
938 inline void string_to_lower(string& s) {
939  for (string::iterator c = s.begin(); c != s.end(); ++c) {
940  *c = tolower(*c);
941  }
942 }
943 
944 struct GroupInfo { // helper class for Clusterer::calc_matches
945  string name; // groupname (lowercase if constructed with sens==GB_IGNORE_CASE)
947  SmartPtr<WordSet> words; // single words (if groupname consists of multiple words and 'prep_wordwise' was true)
948 
949  GroupInfo(const FoundGroup& g, bool prep_wordwise, GB_CASE sens, const char *wordSeparators, const WordSet& ignored_words) :
950  name(g.get_name()),
951  tree(g.get_tree_data())
952  {
953  if (sens == GB_IGNORE_CASE) string_to_lower(name);
954 
955  if (prep_wordwise) {
956  words = new WordSet;
957  string2WordSet(name.c_str(), *words, wordSeparators, ignored_words);
958  }
959  }
960 
961  size_t get_word_count() const {
962  // may return zero (if group name only contains ignored words!)
963  return words.isNull() ? 1 : words->size();
964  }
965 };
966 typedef vector<GroupInfo> GroupInfoVec;
967 
970  GB_CASE sens;
971 
972  int min_words; // only used by DNC_WORDWISE
973  WordSet ignored_words; // only used by DNC_WORDWISE
974 
975  string wordSeparators;
976 
977 public:
979  type(exact),
980  sens(sens_),
981  min_words(1)
982  {
983  gs_assert(exact == DNC_WHOLENAME);
984  }
985 
986  DupNameCriterion(DupNameCriterionType wordwise, GB_CASE sens_, int min_words_, const WordSet& ignored_words_, const char *wordSeparators_) :
987  type(wordwise),
988  sens(sens_),
989  min_words(min_words_),
990  wordSeparators(wordSeparators_)
991  {
992  gs_assert(wordwise == DNC_WORDWISE);
993  gs_assert(min_words>0);
994 
995  for (WordSet::const_iterator wi = ignored_words_.begin(); wi != ignored_words_.end(); ++wi) {
996  string word = *wi;
997  if (sens == GB_IGNORE_CASE) string_to_lower(word);
998  ignored_words.insert(word);
999  }
1000  }
1001 
1002  DupNameCriterionType get_name_type() const { return type; }
1003  bool wordwise_name_matching() const { return get_name_type() == DNC_WORDWISE; }
1004 
1005  GB_CASE get_sensitivity() const { return sens; }
1006  const char *get_word_separators() const { return wordSeparators.c_str(); }
1007 
1008  const WordSet& get_ignored_words() const { return ignored_words; }
1009 
1010  int get_min_wanted_words() const { return min_words; }
1011  void set_min_wanted_words(int words) { min_words = words; }
1012 
1013  int name_matches_wordwise(const GroupInfo& gi1, const GroupInfo& gi2) const {
1014  int max_possible_word_matches = min(gi1.get_word_count(), gi2.get_word_count());
1015  if (max_possible_word_matches<min_words) return false;
1016 
1017  if (gi1.words.isNull()) {
1018  if (gi2.words.isNull()) {
1019  gs_assert(min_words<=1);
1020  gs_assert(!contains(ignored_words, gi1.name));
1021  gs_assert(!contains(ignored_words, gi2.name));
1022  return gi1.name.compare(gi2.name) == 0;
1023  }
1024  return name_matches_wordwise(gi2, gi1);
1025  }
1026 
1027  if (gi2.words.isNull()) {
1028  gs_assert(min_words<=1);
1029  gs_assert(!contains(ignored_words, gi2.name));
1030  return contains(*gi1.words, gi2.name);
1031  }
1032 
1033  int matched_words = 0;
1034  for (WordSet::const_iterator wi = gi1.words->begin(); wi != gi1.words->end(); ++wi) {
1035  if (contains(*gi2.words, *wi)) ++matched_words;
1036  }
1037 
1038  return matched_words>=min_words ? matched_words : false;
1039  }
1040 
1041  int name_matches(const GroupInfo& gi1, const GroupInfo& gi2) const {
1042  return type == DNC_WHOLENAME
1043  ? gi1.name.compare(gi2.name) == 0
1044  : name_matches_wordwise(gi1, gi2);
1045  }
1046 };
1047 
1048 typedef set<int> GroupClusterSet;
1049 typedef GroupClusterSet::const_iterator GroupClusterCIter;
1050 
1052  GroupClusterSet members; // contains indices into Clusterer::groups
1053  int num_groups; // size of Clusterer::groups
1054 
1055  mutable vector<uint8_t> lookup; // when non-empty: contains true for members
1056 
1057  inline bool valid(int i) const { return i >= 0 && i<num_groups; }
1058  inline bool have_lookup() const { return !lookup.empty(); }
1059 
1060 public:
1061  GroupCluster(int num_of_groups)
1062  : num_groups(num_of_groups)
1063  {}
1065 
1066  GroupCluster(const GroupCluster& other) : // does NOT copy lookup table
1067  members(other.members),
1068  num_groups(other.num_groups)
1069  {}
1071 
1072  void allow_lookup() const { // create lookup table -> allows to run 'contains()'
1073  if (!have_lookup()) {
1074  lookup.resize(num_groups, int(false));
1075  for (GroupClusterCIter ci = begin(); ci != end(); ++ci) {
1076  lookup[*ci] = true;
1077  }
1078  gs_assert(have_lookup());
1079  }
1080  }
1081  void forget_lookup() const { lookup.clear(); }
1082 
1083  void clear() {
1084  if (have_lookup()) {
1085  for (GroupClusterCIter ci = begin(); ci != end(); ++ci) lookup[*ci] = false;
1086  }
1087  members.clear();
1088  }
1089 
1090  void insert(int i) {
1091  gs_assert(valid(i));
1092  members.insert(i);
1093  if (have_lookup()) lookup[i] = true;
1094  }
1095  void erase(int i) {
1096  gs_assert(valid(i));
1097  members.erase(i);
1098  if (have_lookup()) lookup[i] = false;
1099  }
1100 
1101  bool contains(int i) const {
1102  gs_assert(valid(i));
1103  gs_assert(have_lookup());
1104  return lookup[i];
1105  }
1106 
1107  bool empty() const { return members.empty(); }
1108  size_t size() const { return members.size(); }
1109 
1110  GroupClusterCIter begin() const { return members.begin(); }
1111  GroupClusterCIter end() const { return members.end(); }
1112 };
1113 
1114 
1116  bool listDups; // true->list duplicate groups; false->list "unique" groups (non-duplicate groups)
1117  DupTreeCriterionType ttype;
1118  int minSize; // minimum cluster size (for DLC_DIFF_TREE: minimum number of different trees per cluster)
1119 
1120 public:
1121  DupCriteria(bool listDups_, const DupNameCriterion& nameCrit_, DupTreeCriterionType ttype_, int minSize_) :
1122  DupNameCriterion(nameCrit_),
1123  listDups(listDups_),
1124  ttype(ttype_),
1125  minSize(minSize_)
1126  {
1127  gs_assert(minSize>=2);
1128  }
1129 
1130  DupTreeCriterionType get_tree_type() const { return ttype; }
1131  bool want_unique_groups() const { return !listDups; }
1132 
1133  bool is_inferable() const {
1134  // An inferable criteria has to allow the following deduction:
1135  // (A == B) and (B == C) -> (A == C)
1136  //
1137  // For comparing group names,
1138  // - whole name comparison is an inferable criteria
1139  // - wordwise comparison isnt!
1140 
1141  // Note: comparing trees for equality is inferable,
1142  // comparing trees for difference isnt.
1143 
1144  return !wordwise_name_matching();
1145  }
1146 
1147  bool tree_matches(const GBDATA *data1, const GBDATA *data2) const {
1148  bool did_match;
1149  switch (ttype) {
1150  case DLC_SAME_TREE:
1151  did_match = data1 == data2;
1152  break;
1153 
1154  case DLC_DIFF_TREE:
1155  did_match = data1 != data2;
1156  break;
1157 
1158  case DLC_ANYWHERE:
1159  did_match = true; // ignore tree membership
1160  break;
1161  }
1162  return did_match;
1163  }
1164 
1165  int min_cluster_size() const { return minSize; }
1166  bool big_enough(const GroupCluster& cluster) const { return !cluster.empty() && int(cluster.size())>=minSize; }
1167 };
1168 
1170  // maps matrix indices to linear indices and vv.
1171  //
1172  // For each x/y-pair of matrix indices the following assumptions are made:
1173  // - x!=y (i.e. never used)
1174  // - value(x,y)==value(y,x)
1175 
1176  int size; // matrix size (x and y)
1177  int lin_size;
1178 
1179  int *firstIndexOfRow;
1180  void init_firstIndexOfRow() {
1181  firstIndexOfRow[0] = 0;
1182  for (int y = 1; y<size; ++y) {
1183  firstIndexOfRow[y] = firstIndexOfRow[y-1]+(y-1);
1184  }
1185  }
1186 
1187 public:
1188  SymmetricMatrixMapper(int elements) :
1189  size(elements),
1190  lin_size(size*(size-1)/2),
1191  firstIndexOfRow(new int[size])
1192  {
1193  gs_assert(elements>=2); // smaller is useless
1194  init_firstIndexOfRow();
1195  }
1197  delete [] firstIndexOfRow;
1198  }
1199 
1200  int linear_size() const { return lin_size; }
1201  int linear_index(int x, int y) const {
1202  if (x>y) swap(x, y);
1203 
1204  gs_assert(x<y); // equal indices not allowed
1205  gs_assert(y<size);
1206  gs_assert(x>=0);
1207 
1208  return firstIndexOfRow[y]+x;
1209  }
1210 
1211 #if defined(UNIT_TESTS)
1212  void to_xy(int lin, int& x, int& y) const { // Note: only used in test-code
1213  for (y = 1; y<size && lin>=y; ++y) lin -= y; // if needed in production code: maybe use table for speedup
1214  x = lin;
1215  }
1216 #endif
1217 };
1218 
1219 class Clusterer {
1220  SmartPtr<QueriedGroups> groups;
1221  SmartPtr<DupCriteria> criteria;
1222  SymmetricMatrixMapper symmap;
1223 
1224  vector<uint8_t> name_matches;
1225  vector<bool> tree_matches;
1226 
1227  vector<uint8_t> words; // stores number of words for each group (indices into 'groups'; only valid when wordwise_name_matching)
1228 
1229  int next_id; // used for next cluster
1230  GroupCluster delivered; // stores indices (into 'groups') of all delivered groups
1231 
1232  int pairIdx(int i, int j) const { return symmap.linear_index(i, j); }
1233  void calc_matches(GBDATA *gb_main);
1234 
1235  int fits_into_cluster(int idx, const GroupCluster& cluster, bool strong_fit) const {
1236  const int min_words = criteria->get_min_wanted_words();
1237  bool enough_words = min_words<2 || words[idx] >= min_words;
1238 
1239  gs_assert(min_words>0);
1240 
1241  int fitting = 0;
1242  if (enough_words && !already_delivered(idx) && !cluster.contains(idx)) {
1243  bool fitsAll = true;
1244  bool weakFitAny = true;
1245 
1246  for (GroupClusterCIter ci = cluster.begin(); fitsAll && ci != cluster.end(); ++ci) {
1247  const int pi = pairIdx(idx, *ci);
1248  bool fitWeak = name_matches[pi] >= min_words;
1249 
1250  fitsAll = fitWeak && tree_matches[pi];
1251  weakFitAny = weakFitAny || fitWeak;
1252  }
1253 
1254  if (fitsAll) fitting = idx;
1255  else if (weakFitAny && !strong_fit) fitting = -idx;
1256  }
1257  return fitting;
1258  }
1259 
1260  int find_next_group_fitting_into(const GroupCluster& cluster, int behind_idx, bool strong_fit) const {
1261  // searches for the next group (with an index > 'behind_idx') fitting into 'cluster'.
1262  //
1263  // returns:
1264  // 0 = no such group found
1265  // >0 = index of first fitting group
1266  // <0 = index of candidate group (for cluster extension). not reported if 'strong_fit' is true
1267 
1268  gs_assert(!cluster.empty());
1269  gs_assert(behind_idx>=0);
1270 
1271  const int gcount = groups->size();
1272  int fitting = 0;
1273 
1274  for (int idx = behind_idx+1; idx<gcount && !fitting; ++idx) {
1275  fitting = fits_into_cluster(idx, cluster, strong_fit);
1276  }
1277 
1278  gs_assert(implicated(fitting>0, !cluster.contains(fitting)));
1279  gs_assert(implicated(strong_fit, fitting>=0));
1280 
1281  return fitting;
1282  }
1283 
1284  int find_next_candidate_group_fitting_into(const GroupCluster& cluster, const vector<int>& candidates, int& cand_idx, bool strong_fit) const {
1285  // similar to find_next_group_fitting_into(), but only considers indices listed in 'candidates' (instead of all)
1286  // (they can be retrieved using find_next_group_fitting_into before)
1287  //
1288  // additionally 'cand_idx' is set to the index corresponding with result
1289 
1290  gs_assert(!cluster.empty());
1291  gs_assert(cand_idx>=-1);
1292 
1293  const int cand_size = candidates.size();
1294  int fitting = 0;
1295 
1296  for (int cidx = cand_idx+1; cidx<cand_size; ++cidx) {
1297  int idx = candidates[cidx];
1298 
1299  fitting = fits_into_cluster(idx, cluster, strong_fit);
1300  if (fitting) {
1301  cand_idx = cidx;
1302  break;
1303  }
1304  }
1305 
1306  gs_assert(implicated(fitting>0, !cluster.contains(fitting)));
1307  gs_assert(implicated(strong_fit, fitting>=0));
1308 
1309  return fitting;
1310  }
1311 
1312  void extendClusterToBiggest(GroupCluster& curr, int next_idx, GroupCluster& best, arb_progress& progress_cluster, double done_low, double done_high);
1313 
1314 public:
1316  groups(groups_),
1317  criteria(criteria_),
1318  symmap(groups->size()),
1319  next_id(1),
1320  delivered(groups->size())
1321  {
1322  calc_matches(gb_main);
1323  }
1324 
1325  int max_cluster_start_index() const { return groups->size() - criteria->min_cluster_size(); }
1326 
1327  void buildInferableClusterStartingWith(int start_idx, GroupCluster& cluster);
1328  void findBestClusterBasedOnWords(int wanted_words, GroupCluster& best, arb_progress& progress_cluster, int& first_cluster_found_from_index);
1329 
1330  bool already_delivered(int idx) const { return delivered.contains(idx); }
1331  void deliverCluster(const GroupCluster& ofCluster, QueriedGroups& toResult) {
1332  int this_id = next_id++;
1333  for (GroupClusterCIter ci = ofCluster.begin(); ci != ofCluster.end(); ++ci) {
1334  int idx = *ci;
1335 
1336  // avoid duplication of groups in result list
1338  delivered.insert(idx);
1339 
1340  FoundGroup& g = (*groups)[idx];
1341  g.set_cluster_id(this_id);
1342  toResult.add_informed_group(g);
1343  }
1344  }
1345 
1346  void find_and_deliverTo(QueriedGroups& toResult);
1347  void deliverRest(QueriedGroups& toResult) {
1348  int idx = 0;
1349  for (FoundGroupCIter g = groups->begin(); g != groups->end(); ++g, ++idx) {
1350  if (!already_delivered(idx)) {
1351  toResult.add_informed_group(*g);
1352  }
1353  }
1354  }
1355 
1356  int calc_max_used_words(bool ignore_delivered) {
1357  gs_assert(criteria->wordwise_name_matching()); // otherwise words array contains nothing
1358 
1359  int maxWords = 0;
1360  const int maxidx = groups->size();
1361 
1362  for (int idx = 0; idx<maxidx; ++idx) {
1363  int thisWords = words[idx];
1364 
1365  if (thisWords>maxWords && (ignore_delivered ? !already_delivered(idx) : true)) {
1366  maxWords = thisWords;
1367  }
1368  }
1369 
1370  return maxWords;
1371  }
1372 
1373 };
1374 
1375 void Clusterer::calc_matches(GBDATA *gb_main) {
1376  const int gcount = groups->size();
1377  const int lin_range = symmap.linear_size();
1378  const long way_to_go = long(gcount) + lin_range;
1379 
1380  arb_progress progress(GBS_global_string("[pass 1/2: duplicity matrix (%s)]", GBS_readable_size(lin_range, "b")), way_to_go);
1381 
1382  name_matches.reserve(lin_range);
1383  tree_matches.reserve(lin_range);
1384 
1385  GroupInfoVec info;
1386  info.reserve(gcount);
1387 
1388  { // fetch info to speed up calculation below
1389  GB_transaction ta(gb_main);
1390 
1391  bool prep_wordwise = criteria->wordwise_name_matching();
1392  GB_CASE sens = criteria->get_sensitivity();
1393  const char *wordSeparators = criteria->get_word_separators();
1394  const WordSet& ignoredWords = criteria->get_ignored_words();
1395 
1396  for (FoundGroupCIter g = groups->begin(); g != groups->end() && !progress.aborted(); ++g) {
1397  info.push_back(GroupInfo(*g, prep_wordwise, sens, wordSeparators, ignoredWords));
1398  if (prep_wordwise) {
1399  const GroupInfo& ginfo = info.back();
1400  words.push_back(ginfo.get_word_count());
1401  }
1402  ++progress;
1403  }
1404  }
1405 
1406  for (int i1 = 0; i1<gcount && !progress.aborted(); ++i1) { // calculate pairwise group matches
1407  for (int i2 = i1+1; i2<gcount && !progress.aborted(); ++i2) {
1408  const int li = symmap.linear_index(i1, i2);
1409 
1410  name_matches[li] = criteria->name_matches(info[i1], info[i2]);
1411  tree_matches[li] = criteria->tree_matches(info[i1].tree, info[i2].tree);
1412 
1413  ++progress;
1414  }
1415  }
1416 }
1417 
1418 void Clusterer::buildInferableClusterStartingWith(const int start_idx, GroupCluster& cluster) {
1419  gs_assert(criteria->is_inferable()); // works only for inferable compare criteria
1420 
1421  int gcount = groups->size();
1422  arb_progress progress_build(long(gcount-start_idx-1));
1423 
1424  gs_assert(cluster.empty());
1425  gs_assert(!already_delivered(start_idx));
1426  cluster.insert(start_idx); // always add group at 'start_idx'
1427 
1428  GroupCluster weakCand(gcount); // collects non-strong, possible weak matches
1429 
1430  {
1431  int pcount = start_idx;
1432  int curr_idx = start_idx;
1433  while (!progress_build.aborted()) {
1434  const int addable = find_next_group_fitting_into(cluster, curr_idx, false);
1435  if (!addable) break;
1436 
1437  if (addable>0) { // found a strong match
1438  cluster.insert(addable);
1439  curr_idx = addable;
1440  }
1441  else {
1442  gs_assert(addable<0); // found a weak match
1443  weakCand.insert(-addable);
1444  curr_idx = -addable;
1445  }
1446 
1447  gs_assert(curr_idx>pcount);
1448  progress_build.inc_by(curr_idx-pcount);
1449  pcount = curr_idx;
1450  }
1451  }
1452 
1453  if (criteria->big_enough(cluster) && !progress_build.aborted()) {
1454  // extent cluster (by adding groups that match weak)
1455  // - e.g. add groups from same tree when searching for different trees
1456 
1457  if (!weakCand.empty()) {
1458  GroupCluster toAdd(gcount);
1459 
1460  if (criteria->get_tree_type() == DLC_DIFF_TREE) {
1461  for (GroupClusterCIter w = weakCand.begin(); w != weakCand.end(); ++w) {
1462  int nameFitsAll = true;
1463  for (GroupClusterCIter ci = cluster.begin(); nameFitsAll && ci != cluster.end(); ++ci) {
1464  int pi = pairIdx(*w, *ci);
1465  nameFitsAll = name_matches[pi];
1466  }
1467  if (nameFitsAll) toAdd.insert(*w);
1468  }
1469  }
1470  for (GroupClusterCIter a = toAdd.begin(); a != toAdd.end(); ++a) cluster.insert(*a);
1471  }
1472  }
1473  else { // forget if too small
1474  cluster.clear();
1475  }
1476 
1477  progress_build.done();
1478 
1479  gs_assert(contradicted(cluster.empty(), criteria->big_enough(cluster)));
1480 }
1481 
1482 inline unsigned long permutations(int elems) {
1483  return elems*elems/2-elems;
1484 }
1485 
1486 void Clusterer::extendClusterToBiggest(GroupCluster& curr, int next_idx, GroupCluster& best, arb_progress& progress_cluster, double done_low, double done_high) {
1487  // extends cluster 'curr' (using all possible combinations starting at 'next_idx' = index into 'groups')
1488  // stores best (=biggest) cluster in 'best'
1489 
1490  vector<int> candidates; // collect all possible groups
1491  {
1492  int idx = next_idx;
1493  while (1) {
1494  const int addable = find_next_group_fitting_into(curr, idx, true);
1495  if (!addable) break;
1496 
1497  candidates.push_back(addable);
1498  idx = addable;
1499  }
1500  }
1501 
1502  if ((candidates.size()+curr.size()) > best.size()) { // any chance to find bigger cluster?
1503  stack<int> previous; // previously added indices (into candidates)
1504  int curr_idx = -1; // last added (i.e. start with candidates[0])
1505 
1506  const int del_size = delivered.size();
1507  const unsigned long permutation_count = permutations(candidates.size());
1508 
1509  while (!progress_cluster.aborted()) {
1510  int addable = find_next_candidate_group_fitting_into(curr, candidates, curr_idx, true);
1511  gs_assert(addable>=0);
1512  if (addable) {
1513  curr.insert(addable);
1514  previous.push(curr_idx);
1515  }
1516  else {
1517  if (curr.size() > best.size() && criteria->big_enough(curr)) { // store 'curr' cluster if better
1518  best = curr;
1519 
1520  const unsigned long permutations_left = permutations(candidates.size()-best.size());
1521  const double done_percent = (permutation_count-permutations_left) / double(permutation_count);
1522  const double overall_done_percent = done_low + (done_high-done_low)*done_percent;
1523 
1524  progress_cluster.inc_to_avoid_overflow(del_size + best.size() * overall_done_percent); // @@@ calculation seems to be wrong (overflows)
1525  }
1526  if (previous.empty()) break; // end iteration
1527 
1528  const int last_cidx = previous.top();
1529  const int last_add = candidates[last_cidx];
1530 
1531  curr.erase(last_add);
1532  previous.pop();
1533  curr_idx = last_cidx;
1534 
1535  const int rest_cand = candidates.size() - (curr_idx+1);
1536  const size_t poss_size = rest_cand + curr.size();
1537  if (poss_size<best.size()) break; // end iteration (impossible to collect enough groups to form a bigger cluster)
1538  }
1539  }
1540 
1541  progress_cluster.inc_to_avoid_overflow(del_size + best.size() * done_high); // @@@ calculation seems to be wrong (overflows)
1542  }
1543 }
1544 
1545 void Clusterer::findBestClusterBasedOnWords(int wanted_words, GroupCluster& best, arb_progress& progress_cluster, int& first_cluster_found_from_index) {
1546  gs_assert(!criteria->is_inferable()); // thorough search not required
1547  gs_assert(best.empty());
1548 
1549  {
1550  const int old_min_words = criteria->get_min_wanted_words();
1551  criteria->set_min_wanted_words(wanted_words);
1552 
1553  const int gcount = groups->size();
1554  const int max_start_idx = gcount - criteria->min_cluster_size();
1555 
1556  GroupCluster curr(gcount);
1557  curr.allow_lookup();
1558 
1559  const int extension_count = 1+(wanted_words-1-old_min_words);
1560  const double done_per_extension = 1.0/extension_count;
1561 
1562  int first_index = 0;
1563 
1564  for (int start_idx = first_cluster_found_from_index; start_idx<max_start_idx && !progress_cluster.aborted(); ++start_idx) {
1565  if (words[start_idx]>=wanted_words && !already_delivered(start_idx)) {
1566  curr.clear();
1567  curr.insert(start_idx);
1568 
1569  extendClusterToBiggest(curr, start_idx, best, progress_cluster, 0.0, done_per_extension);
1570  if (!first_index && !best.empty()) {
1571  first_cluster_found_from_index = first_index = start_idx;
1572  }
1573  }
1574  }
1575 
1576  if (wanted_words>old_min_words && !best.empty() && !progress_cluster.aborted()) { // may less words be accepted?
1577  // extend cluster with "weaker" matches:
1578 
1579  int ext_done = 1;
1580  for (int fewer_words = wanted_words-1; fewer_words>=old_min_words && !progress_cluster.aborted(); --fewer_words, ++ext_done) {
1581  criteria->set_min_wanted_words(fewer_words);
1582 
1583  curr = best;
1584  curr.allow_lookup();
1585 
1586  const double done_start = ext_done*done_per_extension;
1587  extendClusterToBiggest(curr, 0, best, progress_cluster, done_start, done_start+done_per_extension);
1588  }
1589  }
1590 
1591  criteria->set_min_wanted_words(old_min_words);
1592  }
1593 
1594  gs_assert(contradicted(best.empty(), criteria->big_enough(best)));
1595 }
1596 
1597 
1599  int gcount = groups->size();
1600  GroupCluster curr(gcount);
1601 
1602  delivered.allow_lookup();
1603  curr.allow_lookup();
1604 
1605  if (criteria->is_inferable()) { // possible to use "fast" clustering?
1606  const int max_i = max_cluster_start_index();
1607  gs_assert(max_i>0);
1608 
1609  arb_progress progress_cluster("[pass 2/2: fast duplicate search]", long(max_i));
1610  for (int i = 0; i<max_i && !progress_cluster.aborted(); ++i) {
1611  if (!already_delivered(i)) {
1612  curr.clear();
1614  if (!curr.empty()) { // found a cluster
1615  deliverCluster(curr, toResult);
1616  }
1617  }
1618  ++progress_cluster;
1619  }
1620  }
1621  else { // use thorough cluster search
1622  int max_words = calc_max_used_words(true);
1623  const int min_words = criteria->get_min_wanted_words();
1624 
1625  long groups_with_min_words = 0;
1626  for (int gidx = 0; gidx<gcount; ++gidx) { // LOOP_VECTORIZED [!<5.0]
1627  if (words[gidx]>=min_words) ++groups_with_min_words;
1628  }
1629 
1630  arb_progress progress_cluster("[pass 2/2: thorough duplicate search]", groups_with_min_words);
1631 
1632  int first_cluster_found_from_index = 0;
1633  while (max_words >= min_words && !progress_cluster.aborted()) {
1634  curr.clear();
1635  findBestClusterBasedOnWords(max_words, curr, progress_cluster, first_cluster_found_from_index);
1636 
1637  if (curr.empty()) {
1638  --max_words;
1639  first_cluster_found_from_index = 0;
1640  }
1641  else {
1642  deliverCluster(curr, toResult);
1643  progress_cluster.inc_to(delivered.size());
1644  }
1645  }
1646  progress_cluster.done();
1647  }
1648 }
1649 
1650 GB_ERROR GroupSearch::clusterDuplicates() {
1651  GB_ERROR error = NULp;
1652  bool enough_hits = found->size()>=2;
1653 
1654  if (enough_hits) {
1655  arb_progress progress("Restricting to duplicate groups", 2L);
1656  Clusterer clusterer(gb_main, found, dups);
1657 
1658  if (clusterer.max_cluster_start_index()<0) {
1659  enough_hits = false; // e.g. 2 hits, but min. cluster-size==3
1660  progress.done();
1661  }
1662  else {
1663  found = new QueriedGroups; // clear result list
1664  clusterer.find_and_deliverTo(*found); // detect clusters of duplicates and add them to the result list
1665 
1666  if (dups->want_unique_groups() && !progress.aborted()) {
1667  QueriedGroups *nonDupGroups = new QueriedGroups;
1668 
1669  clusterer.deliverRest(*nonDupGroups);
1670  found = nonDupGroups;
1671  }
1672  }
1673 
1674  if (!error) error = progress.error_if_aborted();
1675  }
1676 
1677  if (!enough_hits && !error) {
1678  error = GBS_global_string("Not enough hits (%zu) to find duplicates", found->size());
1679  }
1680 
1681  return error;
1682 }
1683 
1685  if (found.isNull()) found = new QueriedGroups;
1686  if (!sortedByOrder) sort_results();
1687  return *found;
1688 }
1689 
1692  has_been_deleted(GroupSearchCommon *common_) : common(common_) {}
1693  bool operator()(const FoundGroup& g) { return common->has_been_deleted(g.get_pointer()); }
1694 };
1697  was_modified(GroupSearchCommon *common_) : common(common_) {}
1698  bool operator()(const FoundGroup& g) { return common->has_been_modified(g.get_pointer()); }
1699 };
1700 
1702  FoundGroupIter first_removed = remove_if(found.begin(), found.end(), has_been_deleted(common));
1703  bool erased = first_removed != found.end();
1704 
1705  found.erase(first_removed, found.end());
1706  invalidate_widths();
1707  return erased;
1708 }
1710  FoundGroupCIter modified = find_if(found.begin(), found.end(), was_modified(common));
1711  return modified != found.end();
1712 }
1713 
1716  compare_by_criteria(const SortCriteria& by_) : by(by_) {}
1717  bool operator()(const FoundGroup& g1, const FoundGroup& g2) const {
1718  int cmp = 0;
1719  bool last_was_modifier = false;
1720  bool reversed = false;
1721 
1722  SortCriteria::const_iterator crit = by.begin();
1723  while ((!cmp || last_was_modifier) && crit != by.end()) {
1724  last_was_modifier = (*crit == GSC_REVERSE);
1725  switch (*crit) {
1726  case GSC_NONE: gs_assert(0); break; // should not occur
1727  case GSC_REVERSE: reversed = !reversed; break;
1728 
1729  // alphabetically:
1730  case GSC_NAME: cmp = strcmp(g1.get_name(), g2.get_name()); break;
1731  case GSC_TREENAME: cmp = strcmp(g1.get_tree_name(), g2.get_tree_name()); break;
1732 
1733  case GSC_HIT_REASON: cmp = g1.get_hit_reason().compare(g2.get_hit_reason()); break;
1734 
1735  // small first:
1736  case GSC_TREEORDER: cmp = g1.get_tree_order() - g2.get_tree_order(); break;
1737  case GSC_NESTING: cmp = g1.get_nesting() - g2.get_nesting(); break;
1738  case GSC_CLUSTER: cmp = g1.get_cluster_id() - g2.get_cluster_id(); break;
1739  case GSC_AID: cmp = double_cmp(g1.get_aid(), g2.get_aid()); break;
1740 
1741  // big first:
1742  case GSC_SIZE: cmp = g2.get_size() - g1.get_size(); break;
1743  case GSC_MARKED: cmp = g2.get_marked() - g1.get_marked(); break;
1744  case GSC_MARKED_PC: cmp = g2.get_marked_pc() - g1.get_marked_pc(); break;
1745  case GSC_KEELED: cmp = g2.get_keeled() - g1.get_keeled(); break;
1746  }
1747  ++crit;
1748  }
1749  return reversed ? cmp>0 : cmp<0;
1750  }
1751 };
1752 
1754  stable_sort(found.begin(), found.end(), compare_by_criteria(by));
1755  sorted_by = &by;
1756 }
1757 
1758 void QueriedGroups::remove_hit(size_t idx) {
1759  if (idx<size()) {
1760  FoundGroupContainer::iterator del = found.begin();
1761  advance(del, idx);
1762  found.erase(del);
1763  invalidate_widths();
1764  }
1765 }
1766 
1768  if (widths.isNull()) {
1769  widths = new ColumnWidths;
1770  ColumnWidths& w = *widths;
1771  for (FoundGroupCIter g = begin(); g != end(); ++g) {
1772  g->track_max_widths(w);
1773  }
1774  }
1775  return *widths;
1776 }
1777 const char *QueriedGroups::get_group_display(const FoundGroup& g, bool show_tree_name) const {
1778  const ColumnWidths& width = get_column_widths(); // updates width information (if outdated)
1779 
1780  static GBS_strstruct display;
1781 
1782  display.erase();
1783 
1784  if (width.seen_keeled) display.put(g.get_keeled() ? '!' : ' ');
1785  display.nprintf(width.name+1, "%-*s", width.name, g.get_name()); // insert name as 1st column
1786 
1787  if (sorted_by) {
1788  // generate display-string depending on active SortCriteria:
1789  for (SortCriteria::const_iterator sc = sorted_by->begin(); sc != sorted_by->end(); ++sc) {
1790  switch (*sc) {
1791  case GSC_NONE: gs_assert(0); break; // invalid
1792 
1793  case GSC_TREENAME: // ignored (either already shown or only have one tree)
1794  case GSC_TREEORDER: // dito
1795  case GSC_REVERSE:
1796  case GSC_NAME:
1797  break; // ignored for display
1798 
1799  case GSC_HIT_REASON:
1800  display.nprintf(width.reason+1, " %-*s", width.reason, g.get_hit_reason().c_str());
1801  break;
1802 
1803  case GSC_NESTING: {
1804  int nesting_width = ColumnWidths::max2width(width.max_nesting);
1805  display.nprintf(nesting_width+1, " %*i", nesting_width, g.get_nesting());
1806  break;
1807  }
1808  case GSC_SIZE: {
1809  int size_width = ColumnWidths::max2width(width.max_size);
1810  display.nprintf(size_width+1, " %*i", size_width, g.get_size());
1811  break;
1812  }
1813  case GSC_MARKED: {
1814  int marked_width = ColumnWidths::max2width(width.max_marked);
1815  display.nprintf(marked_width+1, " %*i", marked_width, g.get_marked());
1816  break;
1817  }
1818  case GSC_MARKED_PC: {
1819  int marked_width = ColumnWidths::max2width(width.max_marked_pc);
1820  display.nprintf(marked_width+2, " %*i%%", marked_width, g.get_marked_pc());
1821  break;
1822  }
1823  case GSC_CLUSTER: {
1824  int cluster_width = ColumnWidths::max2width(width.max_cluster_id);
1825  display.nprintf(cluster_width+2, " %*ic", cluster_width, g.get_cluster_id());
1826  break;
1827  }
1828  case GSC_AID: {
1829  int aid_width = ColumnWidths::max2width(width.max_aid);
1830  display.nprintf(aid_width+6, " %*.4f", aid_width, g.get_aid());
1831  break;
1832  }
1833  case GSC_KEELED: {
1834  display.nprintf(2, " %i", g.get_keeled());
1835  break;
1836  }
1837  }
1838  }
1839  }
1840 
1841  if (show_tree_name) {
1842  display.put(' ');
1843  display.cat(g.get_tree_name());
1844  }
1845 
1846  return display.get_data();
1847 }
1848 
1849 void QueriedGroups::add_candidate(const GroupSearch& group_search, Candidate& cand, const std::string& hit_reason) {
1850  cand.inform_group(group_search, hit_reason);
1851  add_informed_group(cand.get_group());
1852 }
1853 
1854 
1856  if (!found.isNull() && !found->empty()) {
1857  bool erased = found->erase_deleted(common);
1858  bool changed = false;
1859  if (!erased) {
1860  changed = found->contains_changed(common);
1861  }
1862  if (erased || changed) {
1863  redisplay_cb(this);
1864  }
1865  }
1866 }
1867 
1873  if (gsc == GSC_NONE) {
1875  }
1876  else {
1877  bool add = true;
1878 
1879  if (!order.empty() && order.front() == gsc) {
1880  add = false;
1881  if (gsc == GSC_REVERSE) {
1882  order.pop_front(); // eliminate duplicate reverse
1883  sortedByOrder = false;
1884  }
1885  }
1886 
1887  if (add) {
1888  if (gsc != GSC_REVERSE) {
1889  // remove duplicated search criterion from order
1890  SortCriteria::iterator dup = find(order.begin(), order.end(), gsc);
1891  if (dup != order.end()) {
1892  SortCriteria::iterator pre = dup;
1893  do --pre; while (pre != order.end() && *pre == GSC_REVERSE);
1894 
1895  if (pre == order.end()) pre = order.begin(); // erase from start
1896  else ++pre; // step back to 1st GSC_REVERSE
1897 
1898  ++dup; // point behind duplicate
1899  order.erase(pre,dup);
1900  }
1901  }
1902 
1903  order.push_front(gsc);
1904  sortedByOrder = false;
1905  }
1906  }
1907 }
1908 
1909 void GroupSearch::sort_results() {
1910  if (!order.empty()) {
1911  GB_transaction ta(gb_main);
1912  found->sort_by(order);
1913  sortedByOrder = true;
1914  }
1915 }
1916 
1917 void GroupSearch::setDupCriteria(bool listDups, DupNameCriterionType ntype, GB_CASE sens, DupTreeCriterionType ttype, int min_cluster_size) {
1918  gs_assert(ntype != DNC_WORDWISE); // use flavor below
1919  dups = new DupCriteria(listDups, DupNameCriterion(ntype, sens), ttype, min_cluster_size);
1920 }
1921 void GroupSearch::setDupCriteria(bool listDups, DupNameCriterionType ntype, GB_CASE sens, int min_words, const WordSet& ignored_words, const char *wordSeparators, DupTreeCriterionType ttype, int min_cluster_size) {
1922  gs_assert(ntype == DNC_WORDWISE); // use flavor above
1923  dups = new DupCriteria(listDups, DupNameCriterion(ntype, sens, min_words, ignored_words, wordSeparators), ttype, min_cluster_size);
1924 }
1925 void GroupSearch::setDupCriteria(bool listDups, DupNameCriterionType ntype, GB_CASE sens, int min_words, const char *ignored_words, const char *wordSeparators, DupTreeCriterionType ttype, int min_cluster_size) {
1926  WordSet ignoredWordsSet;
1927  WordSet none; // no words ignored in ignoredWordsSet
1928  string2WordSet(ignored_words, ignoredWordsSet, wordSeparators, none);
1929  setDupCriteria(listDups, ntype, sens, min_words, ignoredWordsSet, wordSeparators, ttype, min_cluster_size);
1930 }
1931 
1932 
1934  dups.setNull();
1935 }
1936 
1938  if (idx<found->size()) return (*found)[idx].delete_from_DB();
1939  return "index out-of-bounds";
1940 }
1941 
1943  GB_ERROR error = NULp; // @@@ use ARB_ERROR instead (whole module + callers)
1944  if (has_results()) {
1945  GB_transaction ta(gb_main);
1946 
1947  for (FoundGroupIter group = found->begin(); !error && group != found->end(); ++group) {
1948  error = group->delete_from_DB();
1949  }
1950  error = ta.close(error);
1951  }
1952  return error;
1953 }
1954 
1955 // ------------------------------------------
1956 // ACI extension for group renaming
1957 
1958 using namespace GBL_IMPL;
1959 
1962  int hit_idx;
1963 
1964  GroupRename_callenv(const QueriedGroups& queried_, int hit_idx_, const GBL_env& env_) :
1965  GBL_call_env(NULp, env_),
1966  queried(queried_),
1967  hit_idx(hit_idx_)
1968  {}
1969 
1970  bool legal_hit_index() const { return hit_idx>=0 && unsigned(hit_idx)<queried.size(); }
1971 
1972  const FoundGroup *get_hit_group() const {
1973  if (legal_hit_index()) return &queried[hit_idx];
1974  return NULp;
1975  }
1976 };
1977 
1979  return DOWNCAST_REFERENCE(const GroupRename_callenv, args->get_callEnv());
1980 }
1981 
1984  GB_ERROR error = check_no_parameter(args);
1985  if (!error) {
1986  const GroupRename_callenv& callEnv = custom_env(args);
1987  if (callEnv.legal_hit_index()) {
1988  FORMAT_2_OUT(args, "%i", info2bio(callEnv.hit_idx));
1989  }
1990  else {
1991  error = "no hit";
1992  }
1993  }
1994 
1995  return error;
1996 }
1999  GB_ERROR error = check_no_parameter(args);
2000  if (!error) {
2001  const GroupRename_callenv& callEnv = custom_env(args);
2002  FORMAT_2_OUT(args, "%zu", callEnv.queried.size());
2003  }
2004  return error;
2005 }
2008  GB_ERROR error = check_no_parameter(args);
2009  if (!error) {
2010  const FoundGroup *hit = custom_env(args).get_hit_group();
2011  if (hit) {
2012  FORMAT_2_OUT(args, "%i", hit->get_size());
2013  }
2014  else {
2015  error = "no hit";
2016  }
2017  }
2018  return error;
2019 }
2022  GB_ERROR error = check_no_parameter(args);
2023  if (!error) {
2024  const FoundGroup *hit = custom_env(args).get_hit_group();
2025  if (hit) {
2026  FORMAT_2_OUT(args, "%i", hit->get_marked());
2027  }
2028  else {
2029  error = "no hit";
2030  }
2031  }
2032  return error;
2033 }
2036  GB_ERROR error = check_no_parameter(args);
2037  if (!error) {
2038  const FoundGroup *hit = custom_env(args).get_hit_group();
2039  if (hit) {
2040  FORMAT_2_OUT(args, "%f", hit->get_aid());
2041  }
2042  else {
2043  error = "no hit";
2044  }
2045  }
2046  return error;
2047 }
2050  GB_ERROR error = check_no_parameter(args);
2051  if (!error) {
2052  const FoundGroup *hit = custom_env(args).get_hit_group();
2053  if (hit) {
2054  FORMAT_2_OUT(args, "%i", hit->get_nesting());
2055  }
2056  else {
2057  error = "no hit";
2058  }
2059  }
2060  return error;
2061 }
2062 
2063 
2065  { "hitidx", grl_hitidx },
2066  { "hitcount", grl_hitcount },
2067  { "groupSize", grl_groupsize },
2068  { "markedInGroup", grl_markedingroup },
2069  { "aid", grl_aid },
2070  { "nesting", grl_nesting },
2071 
2072  { NULp, NULp }
2073 };
2074 
2076  static GBL_custom_command_lookup_table clt(groupRename_command_table,
2077  ARRAY_ELEMS(groupRename_command_table)-1,
2079  return clt;
2080 }
2081 
2082 char *GS_calc_resulting_groupname(GBDATA *gb_main, const QueriedGroups& queried, int hit_idx, const char *input_name, const char *acisrt, ARB_ERROR& error) {
2083  char *result = NULp;
2084  if (!input_name || !input_name[0]) {
2085  error = "Error: empty input groupname";
2086  }
2087  else {
2088  GB_transaction ta(gb_main);
2089  bool know_hit = hit_idx>=0 && unsigned(hit_idx)<queried.size();
2090  const FoundGroup *hit = know_hit ? &queried[hit_idx] : NULp;
2091 
2092  GBL_env env(gb_main, hit ? hit->get_tree_name() : NULp, get_GroupRename_customized_ACI_commands());
2093  GroupRename_callenv callEnv(queried, hit_idx, env);
2094 
2095  result = GB_command_interpreter_in_env(input_name, acisrt, callEnv);
2096  if (!result) {
2097  error = GBS_global_string("Error: %s", GB_await_error());
2098  }
2099  else {
2100  freeset(result, GBS_trim(result)); // trim whitespace
2101  }
2102  }
2103  return result;
2104 }
2105 
2106 ARB_ERROR GroupSearch::rename_group(size_t idx, const char *acisrt) {
2107  if (idx<found->size()) {
2108  return (*found)[idx].rename_by_ACI(acisrt, *found, idx);
2109  }
2110  return "index out-of-bounds";
2111 }
2112 
2114  ARB_ERROR error;
2115  if (has_results()) {
2116  GB_transaction ta(gb_main);
2117 
2118  int idx = 0;
2119  for (FoundGroupIter group = found->begin(); !error && group != found->end(); ++group, ++idx) {
2120  error = group->rename_by_ACI(acisrt, *found, idx);
2121  }
2122  error = ta.close(error);
2123  }
2124  return error;
2125 }
2126 
2128  if (idx<found->size()) {
2129  return (*found)[idx].change_folding(mode);
2130  }
2131  return "index out-of-bounds";
2132 }
2133 
2135  // works for groups which are members of one of the searched tree
2136  return common->get_parent_cache().lookupParent(gb_group);
2137 }
2138 
2140  int nesting = 0;
2141  while (gb_group) {
2142  gb_group = get_parent_group(gb_group);
2143  if (gb_group) ++nesting;
2144  }
2145  return nesting;
2146 }
2147 
2148 
2150  ARB_ERROR error;
2151  GB_transaction ta(gb_main);
2152 
2153  GBDATAset modifiedTrees;
2154 
2155  // create a set of affected groups
2156  GBDATAset targetGroups;
2157  for (FoundGroupCIter g = found->begin(); g != found->end(); ++g) {
2158  GBDATA *gb_group = g->get_pointer();
2159  targetGroups.insert(gb_group);
2160  }
2161 
2162  if (mode & GFM_RECURSE) { // also operate on parents
2163  GBDATAset testParentsOf = targetGroups;
2164  if (mode & GFM_PARENTS_ONLY) targetGroups.clear();
2165  while (!testParentsOf.empty()) { // redo until no more parents get added
2166  GBDATAset addedParents;
2167  for (GBDATAset::iterator t = testParentsOf.begin(); t != testParentsOf.end(); ++t) {
2168  GBDATA *gb_parent_group = get_parent_group(*t);
2169  if (gb_parent_group && targetGroups.find(gb_parent_group) == targetGroups.end()) {
2170  addedParents.insert(gb_parent_group);
2171  targetGroups.insert(gb_parent_group);
2172  }
2173  }
2174  testParentsOf = addedParents;
2175  }
2176  }
2177 
2179  for (GBDATAset::iterator n = targetGroups.begin(); n != targetGroups.end() && !error; ++n) {
2180  error = FoundGroup(*n).change_folding(basicMode);
2181  }
2182 
2183  if (!error && (mode & GFM_COLLAPSE_REST)) { // collapse everything else
2184  SearchedTreeContainer searched_tree;
2185  collect_searched_trees(gb_main, trees_to_search, searched_tree);
2186 
2187  for (SearchedTreeIter t = searched_tree.begin(); t != searched_tree.end() && !error; ++t) {
2188  GBDATA *gb_tree_data = t->get_tree_data();
2189  for (GBDATA *gb_node = GB_entry(gb_tree_data, "node"); gb_node && !error; gb_node = GB_nextEntry(gb_node)) {
2190  GBDATA *gb_name = GB_entry(gb_node, "group_name");
2191  if (gb_name) { // named node (aka group)
2192  if (targetGroups.find(gb_node) == targetGroups.end()) { // not already handled before
2193  error = FoundGroup(gb_node).change_folding(GFM_COLLAPSE);
2194  }
2195  }
2196  }
2197  }
2198  }
2199 
2200  return ta.close(error);
2201 }
2202 
2203 ARB_ERROR GroupSearch::collectSpecies(const QueriedGroups& groups, CollectMode cmode, SpeciesNames& species) {
2204  SearchedTreeContainer searched_tree;
2205  collect_searched_trees(gb_main, trees_to_search, searched_tree);
2206 
2207  ARB_ERROR error;
2208  for (SearchedTreeIter t = searched_tree.begin(); t != searched_tree.end() && !error; ++t) {
2209  GBDATAset groupsFoundInTree;
2210  for (FoundGroupCIter g = groups.begin(); g != groups.end(); ++g) {
2211  if (t->get_tree_data() == g->get_tree_data()) {
2212  groupsFoundInTree.insert(g->get_pointer());
2213  }
2214  }
2215 
2216  if (!groupsFoundInTree.empty()) {
2217  // iterate over tree and insert or intersect species from each group with set
2218  GroupSearchRoot *troot = t->get_tree_root();
2219 
2220  ARB_edge start = rootEdge(troot);
2221  ARB_edge e = start;
2222  do {
2223  if (e.is_inner_edge() && e.get_type() != EDGE_TO_ROOT) {
2224  TreeNode *node = e.dest();
2225  if (node->is_normal_group()) {
2226  if (groupsFoundInTree.find(node->gb_node) != groupsFoundInTree.end()) {
2227  // iterate all leafs in subtree and store in 'speciesInGroup'
2228  SpeciesNames speciesInGroup;
2229  ARB_edge sub = e;
2230  ARB_edge stop = sub.inverse();
2231 
2232  while (sub != stop) {
2233  if (sub.is_edge_to_leaf()) {
2234  TreeNode *leaf = sub.dest();
2235  if (leaf->name) speciesInGroup.insert(leaf->name);
2236  }
2237  sub = sub.next();
2238  }
2239 
2240  if (species.empty()) { // simply add first group
2241  gs_assert(!speciesInGroup.empty()); // tree broken?
2242  species = speciesInGroup;
2243  }
2244  else { // intersect or unite two groups
2245  SpeciesNames combined;
2246  if (cmode == INTERSECT) {
2247  set_intersection(
2248  speciesInGroup.begin(), speciesInGroup.end(),
2249  species.begin(), species.end(),
2250  // combined.begin()
2251  inserter(combined, combined.begin())
2252  );
2253 
2254  if (combined.empty()) {
2255  error = "No species is member of ALL groups";
2256  }
2257  }
2258  else {
2259  gs_assert(cmode == UNITE);
2260  set_union(
2261  speciesInGroup.begin(), speciesInGroup.end(),
2262  species.begin(), species.end(),
2263  // combined.begin()
2264  inserter(combined, combined.begin())
2265  );
2266  }
2267  species = combined;
2268  }
2269  }
2270  }
2271  }
2272  e = e.next();
2273  }
2274  while (e != start && !error);
2275  }
2276  }
2277  return error;
2278 }
2279 
2280 static void set_marks_of(const SpeciesNames& targetSpecies, GBDATA *gb_main, GroupMarkMode mode) {
2281  if (!targetSpecies.empty()) {
2282  size_t found = 0;
2283  for (GBDATA *gb_species = GBT_first_species(gb_main);
2284  gb_species;
2285  gb_species = GBT_next_species(gb_species))
2286  {
2287  const char *name = GBT_get_name_or_description(gb_species);
2288  if (targetSpecies.find(name) != targetSpecies.end()) {
2289  ++found;
2290  if (mode == GMM_INVERT) {
2291  UNCOVERED();
2292  GB_write_flag(gb_species, !GB_read_flag(gb_species));
2293  }
2294  else {
2295  UNCOVERED();
2296  GB_write_flag(gb_species, mode == GMM_MARK);
2297  }
2298  }
2299  }
2300  size_t targetted = targetSpecies.size();
2301  if (found<targetted) {
2302  size_t zombies = targetted-found;
2303  GBT_message(gb_main, GBS_global_string("Warning: Refused to touch %zu zombies", zombies));
2304  }
2305  }
2306 }
2307 
2309  ARB_ERROR error;
2310  if (idx<found->size()) {
2311  QueriedGroups groups;
2312  groups.add_informed_group((*found)[idx]);
2313 
2314  SpeciesNames targetSpecies;
2315  error = collectSpecies(groups, UNITE, targetSpecies);
2316  if (!error) set_marks_of(targetSpecies, gb_main, mode);
2317  }
2318  return error;
2319 }
2321  // intersect == true -> affect only species which are members of ALL found groups
2322  ARB_ERROR error;
2323  if (has_results()) {
2324  SpeciesNames targetSpecies;
2325  error = collectSpecies(*found, cmode, targetSpecies);
2326  if (!error) set_marks_of(targetSpecies, gb_main, mode);
2327  }
2328  return error;
2329 }
2330 
2332  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2333  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2334  return strdup(target_group.get_group_name()); // retrieve group name
2335  }
2336  const char *get_name() const OVERRIDE { return "name"; }
2337 };
2338 
2340  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2341  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2342  const FoundGroup& group = target_group.get_group();
2343 
2344  return GBS_global_string_copy("%i", int(group.is_folded()));
2345  }
2346  const char *get_name() const OVERRIDE { return "folded"; }
2347 };
2348 
2350  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2351  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2352  return GBS_global_string_copy("%e", target_group.get_average_ingroup_distance());
2353  }
2354  const char *get_name() const OVERRIDE { return "AID"; }
2355 };
2356 
2358  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2359  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2360  return GBS_global_string_copy("%u", target_group.get_group_size());
2361  }
2362  const char *get_name() const OVERRIDE { return "size"; }
2363 };
2365  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2366  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2367  return GBS_global_string_copy("%i", target_group.get_keeledStateInfo());
2368  }
2369  const char *get_name() const OVERRIDE { return "keeled"; }
2370 };
2372  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2373  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2374  return GBS_global_string_copy("%u", target_group.get_zombie_count());
2375  }
2376  const char *get_name() const OVERRIDE { return "zombies"; }
2377 };
2379  bool percent;
2380 public:
2381  GroupMarkedKey(bool percent_) :
2382  percent(percent_)
2383  {}
2384  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2385  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2386 
2387  int marked = target_group.get_marked_count();
2388  if (percent) {
2389  int size = target_group.get_group_size();
2390  double pc = 100.0*marked/size;
2391  return GBS_global_string_copy("%5.2f", pc);
2392  }
2393 
2394  return GBS_global_string_copy("%u", marked);
2395  }
2396  const char *get_name() const OVERRIDE { return "marked"; }
2397 };
2398 
2400  const GroupSearch& group_search;
2401 public:
2402  NestingLevelKey(const GroupSearch& group_search_) :
2403  group_search(group_search_)
2404  {}
2405  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2406  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2407  const FoundGroup& group = target_group.get_group();
2408 
2409  return GBS_global_string_copy("%i", group_search.calc_nesting_level(group.get_pointer()));
2410  }
2411  const char *get_name() const OVERRIDE { return "nesting"; }
2412 };
2413 
2415  const GroupSearch& group_search;
2416  bool directParentOnly; // true -> direct parent; false -> any parent (iterates)
2417 
2418  mutable GBDATA *gb_parent;
2419  mutable int distance; // 1=direct parent, 2=parent of direct parent, ...
2420 
2421  static inline query_key_type detectKeyType(CriterionType ctype) {
2422  query_key_type qkt;
2423  switch (ctype) {
2424  case CT_PARENT_DIRECT: qkt = QKEY_EXPLICIT; break;
2425  case CT_PARENT_ANY: qkt = QKEY_ANY; break;
2426  case CT_PARENT_ALL: qkt = QKEY_ALL; break;
2427  default: gs_assert(0); break;
2428  }
2429  return qkt;
2430  }
2431 
2432 public:
2433  ParentGroupNameQueryKey(const GroupSearch& group_search_, CriterionType ctype) :
2434  QueryKey(detectKeyType(ctype)),
2435  group_search(group_search_),
2436  directParentOnly(ctype == CT_PARENT_DIRECT),
2437  gb_parent(NULp),
2438  distance(0)
2439  {
2440  gs_assert(ctype == CT_PARENT_DIRECT || ctype == CT_PARENT_ANY || ctype == CT_PARENT_ALL);
2441  }
2443 
2444  char *get_target_data(const QueryTarget& target, GB_ERROR& /*error*/) const OVERRIDE {
2445  // retrieve name of parent group
2446  if (!gb_parent) { // search first (direct) parent
2447  const TargetGroup& target_group = DOWNCAST_REFERENCE(const TargetGroup, target);
2448  const FoundGroup& group = target_group.get_group();
2449 
2450  gb_parent = group_search.get_parent_group(group.get_pointer());
2451  ++distance;
2452  if (!gb_parent) return strdup(""); // does not match "*"
2453  }
2454 
2455  FoundGroup parent(gb_parent);
2456  return strdup(parent.get_name());
2457  }
2458  const char *get_name() const OVERRIDE {
2459  // name of target (e.g. for reports)
2460  if (get_type() == QKEY_EXPLICIT) { // direct parent
2461  return "parent-name";
2462  }
2463 
2464  return GBS_global_string("parent-%i-name", distance);
2465  }
2466  bool iterate() const OVERRIDE {
2467  // iterate key to next entry (not for QKEY_EXPLICIT)
2468  if (gb_parent && get_type() != QKEY_EXPLICIT) {
2469  gb_parent = group_search.get_parent_group(gb_parent);
2470  ++distance;
2471  return gb_parent;
2472  }
2473  return false;
2474  }
2475  void reset() const OVERRIDE {
2476  // reset iteration
2477  gb_parent = NULp;
2478  distance = 0;
2479  }
2480 
2481 };
2482 
2484  query_operator aqo = ILLEGAL;
2485 
2486  if (query_expr.isNull()) {
2487  aqo = OR; // first is always OR
2488  }
2489  else {
2490  switch (op) {
2491  case CO_AND: aqo = AND; break;
2492  case CO_OR: aqo = OR; break;
2493  case CO_IGNORE:
2494  return; // ignore this expression
2495  }
2496  }
2497 
2498  QueryKeyPtr key;
2499  switch (type) {
2500  case CT_NAME: key = new GroupNameQueryKey; break;
2501  case CT_FOLDED: key = new GroupFoldedKey; break;
2502  case CT_NESTING_LEVEL: key = new NestingLevelKey(*this); break;
2503  case CT_SIZE: key = new GroupSizeKey; break;
2504  case CT_MARKED: key = new GroupMarkedKey(false); break;
2505  case CT_MARKED_PC: key = new GroupMarkedKey(true); break;
2506  case CT_ZOMBIES: key = new GroupZombiesKey; break;
2507 
2508  case CT_PARENT_DIRECT:
2509  case CT_PARENT_ANY:
2510  case CT_PARENT_ALL: key = new ParentGroupNameQueryKey(*this, type); break;
2511 
2512  case CT_AID: key = new GroupAIDkey; break;
2513  case CT_KEELED: key = new GroupKeeledKey; break;
2514  }
2515 
2516  QueryExpr *qe = new QueryExpr(aqo, key, mtype == CM_MISMATCH, expression);
2517  if (query_expr.isNull()) { // store 1st
2518  query_expr = qe;
2519  }
2520  else { // append others
2521  query_expr->append(qe);
2522  }
2523 }
2525  query_expr.setNull();
2526 }
2527 
2528 
2529 // --------------------------------------------------------------------------------
2530 
2531 #ifdef UNIT_TESTS
2532 #ifndef TEST_UNIT_H
2533 #include <test_unit.h>
2534 #endif
2535 
2536 enum GroupListType {
2537  GLT_NAME,
2538  GLT_NAME_TREE,
2539  GLT_NAME_SIZE,
2540  GLT_NAME_AID,
2541  GLT_CLUST_NT, // cluster, name + tree
2542  GLT_NAME_FOLD, // shows foldings state
2543  GLT_NAME_AND_PARENT, // shows parent relation (using ParentCache)
2544  GLT_KNAME_NEST, // shows keeled state and nesting
2545 };
2546 
2547 static arb_test::match_expectation groupListingIs(const QueriedGroups& foundGroups, GroupListType type, const char *expected_entries) {
2548  using namespace arb_test;
2549 
2550  ParentCache& pcache = GroupSearch::get_common()->get_parent_cache();
2551 
2552  StrArray entries;
2553  for (FoundGroupCIter g = foundGroups.begin(); g != foundGroups.end(); ++g) {
2554  switch (type) {
2555  case GLT_NAME:
2556  entries.put(strdup(g->get_name()));
2557  break;
2558 
2559  case GLT_NAME_TREE:
2560  entries.put(GBS_global_string_copy("%s/%s", g->get_name(), g->get_tree_name()));
2561  break;
2562 
2563  case GLT_NAME_SIZE:
2564  entries.put(GBS_global_string_copy("%s(%i)", g->get_name(), g->get_size()));
2565  break;
2566 
2567  case GLT_NAME_AID:
2568  entries.put(GBS_global_string_copy("%s(%.4f)", g->get_name(), g->get_aid()));
2569  break;
2570 
2571  case GLT_CLUST_NT:
2572  entries.put(GBS_global_string_copy("%i/%s/%s", g->get_cluster_id(), g->get_name(), g->get_tree_name()));
2573  break;
2574 
2575  case GLT_NAME_FOLD: {
2576  const char *format = g->is_folded() ? "[%s]" : "%s";
2577  entries.put(GBS_global_string_copy(format, g->get_name()));
2578  break;
2579  }
2580  case GLT_NAME_AND_PARENT: {
2581  GBDATA *gb_parent = pcache.lookupParent(g->get_pointer());
2582  if (gb_parent) {
2583  entries.put(GBS_global_string_copy("%s<%s>", FoundGroup(gb_parent).get_name(), g->get_name()));
2584  }
2585  else {
2586  entries.put(strdup(g->get_name()));
2587  }
2588  break;
2589  }
2590  case GLT_KNAME_NEST: {
2591  int kstate = g->get_keeled();
2592  const char *kprefix = kstate ? (kstate == 1 ? "!" : "?") : "";
2593  entries.put(GBS_global_string_copy("%s%s(L%i)", kprefix, g->get_name(), g->get_nesting()));
2594  break;
2595  }
2596  }
2597  }
2598 
2599  SmartCharPtr found_entriesP = GBT_join_strings(entries, '*');
2600  const char *found_entries = &*found_entriesP;
2601  return that(found_entries).is_equal_to(expected_entries);
2602 }
2603 
2604 static arb_test::match_expectation speciesInGroupsAre(GroupSearch& gs, CollectMode cmode, const char *expected_species) {
2605  using namespace arb_test;
2606  expectation_group fulfilled;
2607 
2608  SpeciesNames species;
2609  {
2610  const QueriedGroups& groups = gs.get_results();
2611  ARB_ERROR error = gs.collectSpecies(groups, cmode, species);
2612  fulfilled.add(doesnt_report_error(error));
2613  }
2614 
2615  ConstStrArray entries;
2616  for (SpeciesNames::const_iterator n = species.begin(); n != species.end(); ++n) {
2617  entries.put(n->c_str());
2618  }
2619  entries.sort(GB_string_comparator, NULp);
2620 
2621  SmartCharPtr contained_speciesP = GBT_join_strings(entries, ',');
2622  const char *contained_species = &*contained_speciesP;
2623  fulfilled.add(that(contained_species).is_equal_to(expected_species));
2624 
2625  return all().ofgroup(fulfilled);
2626 }
2627 
2628 static arb_test::match_expectation resultListingIs(GroupSearch& gs, GroupListType type, const char *expected_entries) {
2629  using namespace arb_test;
2630 
2631  const QueriedGroups& results = gs.get_results();
2633 
2634  return groupListingIs(results, type, expected_entries);
2635 }
2636 
2637 static arb_test::match_expectation hasOrder(const GroupSearch& gs, const char *expected_order) {
2638  using namespace arb_test;
2639 
2640  const int MAX_ORDER = 20;
2641  char found_order[MAX_ORDER];
2642  int off = 0;
2643 
2644  const SortCriteria& order = gs.inspect_order();
2645  for (SortCriteria::const_iterator i = order.begin(); i != order.end(); ++i) {
2646  char c = '?';
2647  switch (*i) {
2648  case GSC_NONE: c = '_'; break;
2649  case GSC_NAME: c = 'N'; break;
2650  case GSC_TREENAME: c = 'T'; break;
2651  case GSC_TREEORDER: c = 'O'; break;
2652  case GSC_REVERSE: c = '!'; break;
2653  case GSC_HIT_REASON: c = 'R'; break; // @@@ untested
2654  case GSC_NESTING: c = 'G'; break; // --- dito ---
2655  case GSC_SIZE: c = 'S'; break; // --- dito ---
2656  case GSC_MARKED: c = 'M'; break; // --- dito ---
2657  case GSC_MARKED_PC: c = '%'; break; // --- dito ---
2658  case GSC_CLUSTER: c = 'C'; break;
2659  case GSC_AID: c = 'A'; break;
2660  case GSC_KEELED: c = 'k'; break;
2661  }
2662  found_order[off++] = c;
2663  }
2664  gs_assert(off<MAX_ORDER);
2665  found_order[off] = 0;
2666  return that(found_order).is_equal_to(expected_order);
2667 }
2668 
2669 static arb_test::match_expectation addingCriterionProduces(GroupSearch& gs, GroupSortCriterion crit, const char *expected_order, const char *expected_entries) {
2670  using namespace arb_test;
2671  expectation_group fulfilled;
2672 
2673  gs.addSortCriterion(crit);
2674 
2675  fulfilled.add(hasOrder(gs, expected_order));
2676  fulfilled.add(resultListingIs(gs, GLT_NAME_TREE, expected_entries));
2677 
2678  return all().ofgroup(fulfilled);
2679 }
2680 
2681 static int refreshes_traced = 0;
2682 static void trace_refresh_cb() { ++refreshes_traced; }
2683 
2684 void TEST_group_search() {
2685  GB_shell shell;
2686  GBDATA *gb_main = GB_open("../../demo.arb", "r");
2687 
2688  GroupSearchCallback traceRefresh_cb = makeGroupSearchCallback(trace_refresh_cb);
2689  refreshes_traced = 0;
2690 
2691  {
2692  GroupSearch allGroups(gb_main, traceRefresh_cb);
2693  TEST_EXPECT(allGroups.get_results().empty());
2694 
2695  allGroups.perform_search(GSM_FIND);
2696  TEST_EXPECT(!allGroups.get_results().empty());
2697  TEST_EXPECT_EQUAL(allGroups.get_results().size(), 28);
2698  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_TREE,
2699  "last/tree_test*another group/tree_test*outer/tree_test*inner/tree_test*test/tree_test*outer/tree_test*test/tree_test*xx/tree_test*"
2700  "outer/tree_tree2*g2/tree_tree2*xx/tree_tree2*test/tree_tree2*outer/tree_tree2*inner/tree_tree2*test/tree_tree2*"
2701  "zombsub/tree_zomb*zomb/tree_zomb*ZOMB/tree_zomb*dup/tree_zomb*inner outer group/tree_zomb*inner group/tree_zomb*outer group/tree_zomb*g4/tree_zomb*g3/tree_zomb*g2/tree_zomb*xx/tree_zomb*yy/tree_zomb*eee/tree_zomb"
2702  ));
2703 
2704  TEST_EXPECTATION(hasOrder(allGroups, ""));
2705  allGroups.addSortCriterion(GSC_NAME); // sort by name
2706  TEST_EXPECTATION(hasOrder(allGroups, "N"));
2707  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_TREE,
2708  "ZOMB/tree_zomb*" // @@@ should be sorted case insensitive
2709  "another group/tree_test*dup/tree_zomb*eee/tree_zomb*"
2710  "g2/tree_tree2*g2/tree_zomb*"
2711  "g3/tree_zomb*g4/tree_zomb*"
2712  "inner/tree_test*inner/tree_tree2*" // order is stable
2713  "inner group/tree_zomb*inner outer group/tree_zomb*last/tree_test*"
2714  "outer/tree_test*outer/tree_test*outer/tree_tree2*outer/tree_tree2*" // order is stable
2715  "outer group/tree_zomb*"
2716  "test/tree_test*test/tree_test*test/tree_tree2*test/tree_tree2*" // order is stable
2717  "xx/tree_test*xx/tree_tree2*xx/tree_zomb*" // order is stable
2718  "yy/tree_zomb*zomb/tree_zomb*zombsub/tree_zomb"
2719  ));
2720 
2721  // search only in tree_tree2
2722  TreeNameSet tree2;
2723  tree2.insert("tree_tree2");
2724  allGroups.setSearchRange(tree2);
2725  allGroups.perform_search(GSM_FIND);
2726  TEST_EXPECT_EQUAL(allGroups.get_results().size(), 7);
2727  TEST_EXPECTATION(hasOrder(allGroups, "N")); // results still sorted by name (sort criteria are not reset by new search)
2728  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_TREE, "g2/tree_tree2*inner/tree_tree2*outer/tree_tree2*outer/tree_tree2*test/tree_tree2*test/tree_tree2*xx/tree_tree2"));
2729  }
2730 
2731  {
2732  GroupSearch some(gb_main, traceRefresh_cb);
2733 
2734  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*ou*");
2735 
2736  some.perform_search(GSM_FIND);
2737  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "another group*outer*outer*outer*outer*inner outer group*inner group*outer group"));
2738  TEST_EXPECT_EQUAL(some.get_results().get_column_widths().name, 17);
2739 
2740  // test 2nd filter
2741  some.forgetQExpressions();
2742  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*er");
2743  some.perform_search(GSM_FIND);
2744  TEST_EXPECTATION(resultListingIs(some, GLT_NAME_TREE, "outer/tree_test*inner/tree_test*outer/tree_test*outer/tree_tree2*outer/tree_tree2*inner/tree_tree2"));
2745  TEST_EXPECT_EQUAL(some.get_results().get_column_widths().name, 5);
2746 
2747  {
2748  // test order
2749  const char *BY_NAME_FWD = "inner/tree_test*inner/tree_tree2*outer/tree_test*outer/tree_test*outer/tree_tree2*outer/tree_tree2";
2750  const char *BY_NAME_REV = "outer/tree_test*outer/tree_test*outer/tree_tree2*outer/tree_tree2*inner/tree_test*inner/tree_tree2";
2751 
2752  TEST_EXPECTATION(addingCriterionProduces(some, GSC_NAME, "N", BY_NAME_FWD));
2753  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "!N", BY_NAME_REV));
2754  TEST_EXPECTATION(addingCriterionProduces(some, GSC_NAME, "N", BY_NAME_FWD));
2755 
2756  // test multiple "reverse" criteria
2757  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "!N", BY_NAME_REV));
2758  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "N", BY_NAME_FWD));
2759  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "!N", BY_NAME_REV));
2760 
2761  // test sort by treename
2762  TEST_EXPECTATION(addingCriterionProduces(some, GSC_TREENAME, "T!N", "outer/tree_test*outer/tree_test*inner/tree_test*outer/tree_tree2*outer/tree_tree2*inner/tree_tree2"));
2763  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "!T!N", "inner/tree_tree2*outer/tree_tree2*outer/tree_tree2*inner/tree_test*outer/tree_test*outer/tree_test"));
2764 
2765  // test sort by tree-order (as specified in tree-admin)
2766  TEST_EXPECTATION(addingCriterionProduces(some, GSC_TREEORDER, "O!T!N", "inner/tree_test*outer/tree_test*outer/tree_test*inner/tree_tree2*outer/tree_tree2*outer/tree_tree2"));
2767  TEST_EXPECTATION(addingCriterionProduces(some, GSC_REVERSE, "!O!T!N", "outer/tree_tree2*outer/tree_tree2*inner/tree_tree2*outer/tree_test*outer/tree_test*inner/tree_test"));
2768 
2769  some.forgetSortCriteria();
2770  }
2771 
2772  // combine both filters (conjunction will only report 'outer')
2773  some.addQueryExpression(CO_AND, CT_NAME, CM_MATCH, "*ou*");
2774  some.perform_search(GSM_FIND);
2775  TEST_EXPECTATION(resultListingIs(some, GLT_NAME_TREE, "outer/tree_test*outer/tree_test*outer/tree_tree2*outer/tree_tree2"));
2776 
2777  // test adding results
2778  some.forgetQExpressions();
2779  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*xx*");
2780  some.perform_search(GSM_ADD);
2781  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "outer*outer*outer*outer*xx*xx*xx"));
2782 
2783  some.forgetQExpressions();
2784  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*er*");
2785  some.perform_search(GSM_ADD); // check no duplicates are reported (filter also matches 'outer')
2786  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "outer*outer*outer*outer*xx*xx*xx*another group*inner*inner*inner outer group*inner group*outer group"));
2787 
2788  // test removing a single result
2789  {
2790  some.addSortCriterion(GSC_TREEORDER); // first change order to make removal comprehensible
2791  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "outer*outer*xx*another group*inner*outer*outer*xx*inner*xx*inner outer group*inner group*outer group"));
2792 
2793  const char *FIRST_XX_REMOVED = "outer*outer*another group*inner*outer*outer*xx*inner*xx*inner outer group*inner group*outer group";
2794  some.remove_hit(2); // remove first 'xx'
2795  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, FIRST_XX_REMOVED));
2796  // test that out-of-bounds removals are NOOPs:
2797  some.remove_hit(-10); TEST_EXPECTATION(resultListingIs(some, GLT_NAME, FIRST_XX_REMOVED));
2798  some.remove_hit(100); TEST_EXPECTATION(resultListingIs(some, GLT_NAME, FIRST_XX_REMOVED));
2799  }
2800 
2801  // test keeping results
2802  some.forgetQExpressions();
2803  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*ou*");
2804  some.perform_search(GSM_KEEP);
2805  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "outer*outer*another group*outer*outer*inner outer group*inner group*outer group"));
2806 
2807  // test removing results (also tests "mismatch")
2808  some.forgetQExpressions();
2809  some.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "outer");
2810  some.perform_search(GSM_REMOVE);
2811  TEST_EXPECTATION(resultListingIs(some, GLT_NAME, "another group*inner outer group*inner group*outer group"));
2812  }
2813 
2814  // test different search keys
2815  {
2816  GroupSearch keyed(gb_main, traceRefresh_cb);
2817  const char *TOP_GROUPS = "last*another group*outer*test*outer*outer*zombsub*dup*inner outer group";
2818 
2819  // CT_PARENT_DIRECT (direct parent group name)
2820  keyed.addQueryExpression(CO_OR, CT_PARENT_DIRECT, CM_MATCH, ""); // direct parent w/o name (=no direct parent)
2821  keyed.perform_search(GSM_FIND);
2822  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, TOP_GROUPS)); // -> TOP_GROUPS
2823 
2824  keyed.forgetQExpressions();
2825  keyed.addQueryExpression(CO_OR, CT_PARENT_DIRECT, CM_MATCH, "/^[^ ]*ou[^ ]*$/"); // uses regular expression query
2826  keyed.perform_search(GSM_FIND);
2827  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "outer<inner>*outer<test>*outer<xx>*outer<g2>*outer<test>*outer<inner>*outer<test>"));
2828 
2829  // CT_PARENT_ANY
2830  keyed.forgetQExpressions();
2831  keyed.addQueryExpression(CO_OR, CT_PARENT_ANY, CM_MATCH, "|contains(\"ou\");contains(\" \")|equals(0)|minus");
2832  keyed.perform_search(GSM_FIND);
2833  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "outer<inner>*outer<test>*outer<xx>*outer<g2>*g2<xx>*outer<test>*test<outer>*outer<inner>*outer<test>"));
2834 
2835  // CT_PARENT_ALL
2836  keyed.forgetQExpressions();
2837  keyed.addQueryExpression(CO_OR, CT_PARENT_ALL, CM_MISMATCH, "/ou/"); // not inside group containing 'ou'
2838  keyed.addQueryExpression(CO_AND, CT_NAME, CM_MISMATCH, "/ou/"); // and not containing 'ou' itself
2839  keyed.perform_search(GSM_FIND);
2840  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "last*test*zombsub*zombsub<zomb>*zombsub<ZOMB>*dup"));
2841 
2842  // CT_NESTING_LEVEL
2843  keyed.forgetQExpressions();
2844  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, "<1"); // nesting level less than 1
2845  keyed.perform_search(GSM_FIND);
2846  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, TOP_GROUPS)); // -> TOP_GROUPS
2847 
2848  keyed.forgetQExpressions();
2849  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MISMATCH, ">0"); // nesting level not above 0
2850  keyed.perform_search(GSM_FIND);
2851  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, TOP_GROUPS)); // -> TOP_GROUPS
2852 
2853  keyed.forgetQExpressions();
2854  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, ">4"); // too high nesting level
2855  keyed.perform_search(GSM_FIND);
2856  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, ""));
2857 
2858  keyed.forgetQExpressions();
2859  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, ">3"); // highest occurring nesting level
2860  keyed.perform_search(GSM_FIND);
2861  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "yy<eee>")); // one group with nesting level 4
2862 
2863  keyed.forgetQExpressions();
2864  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, ">2");
2865  keyed.perform_search(GSM_FIND);
2866  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "outer<inner>*g2<xx>*g2<yy>*yy<eee>")); // 1xL4 + 3xL3
2867 
2868  keyed.forgetQExpressions();
2869  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, ">1");
2870  keyed.addQueryExpression(CO_AND, CT_NESTING_LEVEL, CM_MATCH, "<4");
2871  keyed.perform_search(GSM_FIND);
2872  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "g2<xx>*test<outer>*outer<inner>*outer group<g4>*outer group<g3>*outer group<g2>*g2<xx>*g2<yy>")); // 5x L2 + 3x L3
2873 
2874  keyed.forgetQExpressions();
2875  keyed.addQueryExpression(CO_OR, CT_NESTING_LEVEL, CM_MATCH, "2");
2876  keyed.perform_search(GSM_FIND);
2877  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, "g2<xx>*test<outer>*outer group<g4>*outer group<g3>*outer group<g2>")); // 5x L2
2878 
2879  // CT_FOLDED
2880  const char *EXPANDED_GROUPS = "last*outer*outer<inner>*outer*outer*zombsub";
2881  keyed.forgetQExpressions();
2882  keyed.addQueryExpression(CO_OR, CT_FOLDED, CM_MATCH, "0");
2883  keyed.perform_search(GSM_FIND);
2884  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, EXPANDED_GROUPS));
2885 
2886  keyed.forgetQExpressions();
2887  keyed.addQueryExpression(CO_OR, CT_NAME /*does not matter*/, CM_MISMATCH, "|readdb(grouped)|equals(1)"); // directly access field of group-container
2888  keyed.perform_search(GSM_FIND);
2889  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AND_PARENT, EXPANDED_GROUPS));
2890 
2891  // CT_SIZE
2892  keyed.forgetQExpressions();
2893  keyed.addQueryExpression(CO_OR, CT_SIZE, CM_MATCH, ">12"); // find bigger groups
2894  keyed.perform_search(GSM_FIND);
2895  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_SIZE, "another group(29)*outer(15)*outer(47)*zombsub(14)*inner outer group(19)*outer group(15)"));
2896  keyed.addQueryExpression(CO_AND, CT_SIZE, CM_MATCH, "|rest(2)|equals(0)"); // with even groupsize only
2897  keyed.perform_search(GSM_FIND);
2898  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_SIZE, "zombsub(14)")); // the only bigger group with an even number of members
2899 
2900  // CT_MARKED + CT_MARKED_PC
2901  keyed.forgetQExpressions();
2902  keyed.addQueryExpression(CO_OR, CT_MARKED, CM_MATCH, ">7"); // at least 8 marked species inside group
2903  keyed.perform_search(GSM_FIND);
2904  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME, "another group*outer*inner outer group*outer group"));
2905 
2906  const char *COMPLETELY_MARKED_GROUPS = "test*xx*xx*g4*xx*eee";
2907  keyed.forgetQExpressions();
2908  keyed.addQueryExpression(CO_OR, CT_MARKED_PC, CM_MATCH, ">99"); // completely marked groups (more than 99%)
2909  keyed.perform_search(GSM_FIND);
2910  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME, COMPLETELY_MARKED_GROUPS));
2911  keyed.forgetQExpressions();
2912  keyed.addQueryExpression(CO_OR, CT_MARKED_PC, CM_MISMATCH, "<100"); // completely marked groups (not less than 100%)
2913  keyed.perform_search(GSM_FIND);
2914  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME, COMPLETELY_MARKED_GROUPS));
2915  keyed.forgetQExpressions();
2916  keyed.addQueryExpression(CO_OR, CT_MARKED_PC, CM_MATCH, "100"); // completely marked groups (equal to 100%)
2917  keyed.perform_search(GSM_FIND);
2918  TEST_EXPECTATION__BROKEN(resultListingIs(keyed, GLT_NAME, COMPLETELY_MARKED_GROUPS), // @@@ matching % for equality does not work as expected
2919  resultListingIs(keyed, GLT_NAME, ""));
2920 
2921 
2922  keyed.forgetQExpressions();
2923  keyed.addQueryExpression(CO_OR, CT_MARKED, CM_MISMATCH, "0"); // groups with marked..
2924  keyed.addQueryExpression(CO_AND, CT_MARKED_PC, CM_MATCH, "<50"); // ..but less than 50%
2925  keyed.perform_search(GSM_FIND);
2926  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME, "outer*outer*test"));
2927 
2928  // CT_ZOMBIES
2929  keyed.forgetQExpressions();
2930  keyed.addQueryExpression(CO_OR, CT_ZOMBIES, CM_MISMATCH, "0"); // groups with zombies
2931  keyed.perform_search(GSM_FIND);
2932  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME, "zombsub*zomb*ZOMB"));
2933 
2934  // CT_AID
2935  keyed.forgetQExpressions();
2936  keyed.addQueryExpression(CO_OR, CT_AID, CM_MATCH, ">1"); // groups with high AID
2937  keyed.perform_search(GSM_FIND);
2938  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AID, "outer(1.0996)*outer(1.1605)"));
2939 
2940  keyed.forgetQExpressions();
2941  keyed.addQueryExpression(CO_OR, CT_AID, CM_MATCH, "<.1"); // groups with low AID
2942  keyed.perform_search(GSM_FIND);
2943  keyed.addSortCriterion(GSC_AID);
2944  keyed.addSortCriterion(GSC_REVERSE);
2945  TEST_EXPECTATION(resultListingIs(keyed, GLT_NAME_AID, "xx(0.0786)*xx(0.0786)*g3(0.0665)*dup(0.0399)*inner group(0.0259)"));
2946 
2947  // CT_KEELED is tested in TEST_keeled_group_search()
2948  }
2949 
2950  TEST_EXPECT_EQUAL(refreshes_traced, 0); // no refresh traced up to here
2951 
2952  // test group-actions:
2953 
2954  {
2955  refreshes_traced = 0;
2956 
2957  GroupSearch misc(gb_main, traceRefresh_cb);
2958 
2959  misc.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*e*");
2960  misc.addQueryExpression(CO_AND, CT_NAME, CM_MISMATCH, "* *");
2961  misc.perform_search(GSM_FIND);
2962  {
2963  const char *ACI_add_tag = "\"[TAG] \";dd";
2964 
2965  const char *BEFORE_RENAME = "outer*inner*test*outer*test*outer*test*outer*inner*test*eee";
2966  const char *OUTER_PREFIXED = "[TAG] outer*inner*test*outer*test*outer*test*outer*inner*test*eee";
2967 
2968  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, BEFORE_RENAME));
2969 
2970  // test renaming groups:
2971  TEST_EXPECT_NO_ERROR(misc.rename_group(0, ACI_add_tag)); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, OUTER_PREFIXED)); // prefix first 'outer'
2972  TEST_EXPECT_NO_ERROR(misc.rename_group(0, "\"\"")); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, OUTER_PREFIXED)); // test empty ACI-result does not rename anything
2973 
2974  TEST_EXPECT_NO_ERROR(misc.rename_found_groups("\"[X]\";dd;\" \"")); // prefix '[X]' to all found groups + suffix space (which are trimmed away afterwards)
2975  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "[X][TAG] outer*[X]inner*[X]test*[X]outer*[X]test*[X]outer*[X]test*[X]outer*[X]inner*[X]test*[X]eee"));
2976 
2977  // test errors get reported:
2978  TEST_EXPECT_ERROR_CONTAINS(misc.rename_group(0, ":x"), "no '=' found");
2979  TEST_EXPECT_ERROR_CONTAINS(misc.rename_found_groups(":x"), "no '=' found");
2980 
2981  TEST_EXPECT_NO_ERROR(misc.rename_found_groups("/\\[.*\\]//")); // remove any prefixes
2982 
2983  TEST_EXPECT_NO_ERROR(misc.rename_found_groups("dd;\"_\";hitidx;\"/\";hitcount")); // append "_index/hitcount" to groupname
2984  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "outer_1/11*inner_2/11*test_3/11*outer_4/11*test_5/11*outer_6/11*test_7/11*outer_8/11*inner_9/11*test_10/11*eee_11/11"));
2985 
2986  TEST_EXPECT_NO_ERROR(misc.rename_found_groups("command(\"/_.*$//\")|dd;\"_\";markedInGroup;\"/\";groupSize")); // replace suffix with "marked/size"
2987  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "outer_6/11*inner_4/5*test_7/7*outer_7/15*test_0/4*outer_20/47*test_6/12*outer_6/11*inner_4/5*test_2/6*eee_3/3"));
2988 
2989  TEST_EXPECT_NO_ERROR(misc.rename_found_groups(":_*=_L*(|nesting)\\=*(|aid)")); // replace suffix with nesting level and aid
2990  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "outer_L0=0.695293*inner_L1=0.269289*test_L0=0.160956*outer_L0=1.099650*test_L1=0.591923*outer_L0=1.160535*test_L1=0.726679*outer_L2=0.704352*inner_L3=0.265516*test_L1=0.303089*eee_L4=0.229693"));
2991 
2992  // undo renaming groups (to avoid need to change tests below)
2993  TEST_EXPECT_NO_ERROR(misc.rename_found_groups("/_.*$//")); // remove all behind '_'
2994  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, BEFORE_RENAME));
2995 
2996  TEST_EXPECT_EQUAL(refreshes_traced, 7); // amount of result-list refreshes that would happen (1 * rename_group() + 6 * rename_found_groups(); one rename_group did nothing!)
2997  refreshes_traced = 0;
2998  }
2999 
3000  {
3001  GroupSearch all(gb_main, traceRefresh_cb); // run a 2nd search
3002  GroupSearch none(gb_main, traceRefresh_cb); // run a 3rd search
3003  GroupSearch few(gb_main, traceRefresh_cb); // run a 4th search
3004 
3005  // test folding single groups
3006  TEST_EXPECTATION( resultListingIs(misc, GLT_NAME_FOLD, "outer*inner*[test]*outer*[test]*outer*[test]*[outer]*[inner]*[test]*[eee]")); // shows current folding state
3007  TEST_EXPECT_NO_ERROR(misc.fold_group(0, GFM_TOGGLE)); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_FOLD, "[outer]*inner*[test]*outer*[test]*outer*[test]*[outer]*[inner]*[test]*[eee]")); // fold 1st 'outer'
3008  TEST_EXPECT_NO_ERROR(misc.fold_group(0, GFM_TOGGLE)); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_FOLD, "outer*inner*[test]*outer*[test]*outer*[test]*[outer]*[inner]*[test]*[eee]")); // unfold 1st 'outer'
3009 
3010  TEST_EXPECT_EQUAL(refreshes_traced, 2); // 2 result-list refreshes would happen (one for each fold_group())
3011  refreshes_traced = 0;
3012 
3013  none.addQueryExpression(CO_OR, CT_NAME, CM_MISMATCH, "*"); // no such group
3014  all.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "*"); // matches all groups
3015  few.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "inner");
3016 
3017  none.perform_search(GSM_FIND);
3018  few.perform_search(GSM_FIND);
3019  all.perform_search(GSM_FIND);
3020 
3021  TEST_EXPECTATION(resultListingIs(none, GLT_NAME, "")); // shows no results
3022  TEST_EXPECTATION(resultListingIs(few, GLT_NAME_FOLD, "inner*[inner]")); // shows some results
3023  // shows current folding state (of all groups from all trees):
3024  TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "last*[another group]*outer*inner*[test]*outer*[test]*[xx]*outer*[g2]*[xx]*[test]*[outer]*[inner]*[test]*zombsub*[zomb]*[ZOMB]*[dup]*[inner outer group]*[inner group]*[outer group]*[g4]*[g3]*[g2]*[xx]*[yy]*[eee]"));
3025 
3026  TEST_EXPECT_EQUAL(refreshes_traced, 0);
3027 
3028  // test folding listed groups
3029  // (Note: that results used for folding and for test differ!)
3030  TEST_EXPECT_NO_ERROR( few.fold_found_groups(GFM_EXPANDREC)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "last*[another group]*outer*inner*[test]*outer*[test]*[xx]*" "outer*[g2]*[xx]*test*outer*inner*[test]*" "zombsub*[zomb]*[ZOMB]*[dup]*[inner outer group]*[inner group]*[outer group]*[g4]*[g3]*[g2]*[xx]*[yy]*[eee]")); // [A] only unfolds 2nd inner and 2 of its 3 parent groups
3031  TEST_EXPECT_NO_ERROR(misc.fold_found_groups(GFM_EXPANDREC)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "last*[another group]*outer*inner*test*outer*test*[xx]*" "outer*[g2]*[xx]*test*outer*inner*test*" "zombsub*[zomb]*[ZOMB]*[dup]*inner outer group*[inner group]*outer group*[g4]*[g3]*g2*[xx]*yy*eee")); // 'xx' and 'g2' remain folded
3032  TEST_EXPECT_NO_ERROR(misc.fold_found_groups(GFM_COLLAPSE)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "last*[another group]*[outer]*[inner]*[test]*[outer]*[test]*[xx]*" "[outer]*[g2]*[xx]*[test]*[outer]*[inner]*[test]*" "zombsub*[zomb]*[ZOMB]*[dup]*inner outer group*[inner group]*outer group*[g4]*[g3]*g2*[xx]*yy*[eee]")); // 'last' remains unfolded
3033  TEST_EXPECT_NO_ERROR( few.fold_found_groups(GFM_EXPANDREC_COLLREST)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "[last]*[another group]*outer*inner*[test]*[outer]*[test]*[xx]*" "outer*[g2]*[xx]*test*outer*inner*[test]*" "[zombsub]*[zomb]*[ZOMB]*[dup]*[inner outer group]*[inner group]*[outer group]*[g4]*[g3]*[g2]*[xx]*[yy]*[eee]")); // similar to line [A], but 'last' gets folded
3034  TEST_EXPECT_NO_ERROR(none.fold_found_groups(GFM_EXPANDREC_COLLREST)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "[last]*[another group]*[outer]*[inner]*[test]*[outer]*[test]*[xx]*" "[outer]*[g2]*[xx]*[test]*[outer]*[inner]*[test]*" "[zombsub]*[zomb]*[ZOMB]*[dup]*[inner outer group]*[inner group]*[outer group]*[g4]*[g3]*[g2]*[xx]*[yy]*[eee]")); // unfold none+collapse rest = fold all
3035  TEST_EXPECT_NO_ERROR(misc.fold_found_groups(GFM_EXPANDPARENTS)); TEST_EXPECTATION(resultListingIs(all, GLT_NAME_FOLD, "[last]*[another group]*outer*[inner]*[test]*outer*[test]*[xx]*" "outer*[g2]*[xx]*test*outer*[inner]*[test]*" "[zombsub]*[zomb]*[ZOMB]*[dup]*inner outer group*[inner group]*outer group*[g4]*[g3]*g2*[xx]*yy*[eee]")); // unfold all groups containing listed groups
3036 
3037  TEST_EXPECT_EQUAL(refreshes_traced, 16); // @@@ want less refreshes!
3038  refreshes_traced = 0;
3039 
3040  {
3041  GroupSearch group2(gb_main, traceRefresh_cb); // run a 5th search
3042  group2.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "g2"); // group 'g2' exists in 2 tree; species overlap, but are not identical
3043  group2.perform_search(GSM_FIND);
3044 
3045  GB_transaction ta(gb_main);
3046 
3047  // test retrieval of species contained in groups:
3048  TEST_EXPECTATION(speciesInGroupsAre(none, INTERSECT, ""));
3049 
3050  // groups 'inner' are identical in all trees:
3051  const char *INNER_SPECIES = "McpCapri,McpMyco2,McpMycoi,McpSpeci,SpiMelli";
3052  TEST_EXPECTATION(speciesInGroupsAre(few, UNITE, INNER_SPECIES));
3053  TEST_EXPECTATION(speciesInGroupsAre(few, INTERSECT, INNER_SPECIES));
3054 
3055  TEST_EXPECTATION(speciesInGroupsAre(group2, UNITE, "AnaAbact,BacMegat,BacPaste,CloTyro2,CloTyro4,CloTyrob,StaAureu,StaEpide"));
3056  TEST_EXPECTATION(speciesInGroupsAre(group2, INTERSECT, "AnaAbact,BacMegat,BacPaste," "CloTyro4,CloTyrob,StaAureu"));
3057  }
3058  }
3059 
3060  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_AND_PARENT, "outer*outer<inner>*test*outer*outer<test>*outer*outer<test>*test<outer>*outer<inner>*outer<test>*yy<eee>")); // format is "parent<child>"
3061 
3062  // test deleting groups:
3063  TEST_EXPECT_NO_ERROR(misc.delete_group(6)); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "outer*inner*test*outer*test*outer*outer*inner*test*eee")); // delete 1st 'test' from 'tree_test2' (DEL_TEST)
3064  TEST_EXPECT_NO_ERROR(misc.delete_group(3)); TEST_EXPECTATION(resultListingIs(misc, GLT_NAME, "outer*inner*test*test*outer*outer*inner*test*eee")); // delete 2nd 'outer' from 'tree_tree' (DEL_OUTER)
3065 
3066  // deleting invalid index only returns an error:
3067  TEST_EXPECT_ERROR_CONTAINS(misc.delete_group(100), "out-of-bounds");
3068  TEST_EXPECT_ERROR_CONTAINS(misc.delete_group(-1), "out-of-bounds");
3069 
3070  TEST_EXPECT_EQUAL(refreshes_traced, 2); // 2 result-list refreshes would happen (one for each delete_group())
3071  refreshes_traced = 0;
3072 
3073  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_AND_PARENT, "outer*outer<inner>*test*test*outer*outer<outer>*outer<inner>*outer<test>*yy<eee>")); // 'test' between 'outer<outer>' got removed
3074 
3075  // delete all (but one) groups named 'outer':
3076  misc.forgetQExpressions();
3077  misc.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "outer");
3078  misc.perform_search(GSM_FIND);
3079  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_TREE, "outer/tree_test*outer/tree_tree2*outer/tree_tree2")); // also tests that 'outer' was deleted from DB; see .@DEL_OUTER
3080 
3081  misc.remove_hit(1); // will not get deleted
3082  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_TREE, "outer/tree_test*outer/tree_tree2"));
3083 
3084  TEST_EXPECT_NO_ERROR(misc.delete_found_groups()); // now delete all listed groups
3085  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_TREE, "")); // result-list is empty now
3086 
3087  misc.perform_search(GSM_FIND); // search again
3088  TEST_EXPECTATION(resultListingIs(misc, GLT_NAME_TREE, "outer/tree_tree2")); // hit removed before deleting listed still exists in DB
3089 
3090  TEST_EXPECT_EQUAL(refreshes_traced, 1); // only one refresh triggered for deletion of all listed groups
3091  }
3092 
3093  {
3094  refreshes_traced = 0;
3095 
3096  GroupSearch outer(gb_main, traceRefresh_cb);
3097  outer.addQueryExpression(CO_OR, CT_NAME, CM_MATCH, "test");
3098  outer.perform_search(GSM_FIND);
3099  TEST_EXPECTATION(resultListingIs(outer, GLT_NAME_TREE, "test/tree_test*test/tree_test*test/tree_tree2")); // also tests that 'test' was deleted from DB; see .@DEL_TEST
3100 
3101  // test result-update callbacks (triggered by DB-changes)
3102  { // delete tree_tree2:
3103  GB_transaction ta(gb_main);
3104  GBDATA *gb_tree = GBT_find_tree(gb_main, "tree_tree2");
3105  TEST_REJECT_NULL(gb_tree);
3106  TEST_EXPECT_NO_ERROR(GB_delete(gb_tree));
3107  }
3108  TEST_EXPECT_EQUAL(refreshes_traced, 1); // one modifying TA => only one refresh callback triggered
3109  TEST_EXPECTATION(resultListingIs(outer, GLT_NAME_TREE, "test/tree_test*test/tree_test")); // all results referring 'tree_tree2' were removed
3110  }
3111 
3112 
3113  GB_close(gb_main);
3114 }
3115 
3116 void TEST_keeled_group_search() {
3117  GB_shell shell;
3118  GBDATA *gb_main = GB_open("TEST_trees.arb", "rw");
3119 
3120  GroupSearchCallback traceRefresh_cb = makeGroupSearchCallback(trace_refresh_cb);
3121  refreshes_traced = 0;
3122  {
3123  GB_transaction ta(gb_main);
3124 
3125  GroupSearch allGroups(gb_main, traceRefresh_cb);
3126  {
3127  GroupSearch keeledGroups(gb_main, traceRefresh_cb);
3128  GroupSearch normalGroups(gb_main, traceRefresh_cb);
3129 
3130  TEST_EXPECT(allGroups.get_results().empty());
3131  TEST_EXPECT(keeledGroups.get_results().empty());
3132  TEST_EXPECT(normalGroups.get_results().empty());
3133 
3134  // CT_KEELED:
3135  keeledGroups.addQueryExpression(CO_OR, CT_KEELED, CM_MISMATCH, "0"); // find keeled groups
3136  normalGroups.addQueryExpression(CO_OR, CT_KEELED, CM_MATCH, "0"); // find normal groups
3137 
3138  allGroups.perform_search(GSM_FIND);
3139  keeledGroups.perform_search(GSM_FIND);
3140  normalGroups.perform_search(GSM_FIND);
3141 
3142  TEST_EXPECT(!allGroups.get_results().empty());
3143  TEST_EXPECT(!keeledGroups.get_results().empty());
3144  TEST_EXPECT(!normalGroups.get_results().empty());
3145 
3146  TEST_EXPECT_EQUAL(allGroups.get_results().size(), 21);
3147  TEST_EXPECT_EQUAL(allGroups.get_results().size(),
3148  keeledGroups.get_results().size()+normalGroups.get_results().size());
3149  TEST_EXPECT_EQUAL(keeledGroups.get_results().size(), 6);
3150  TEST_EXPECT_EQUAL(normalGroups.get_results().size(), 15);
3151 
3152  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_TREE,
3153  "test/tree_test*"
3154  "outer/tree_tree2*g2/tree_tree2*"
3155  "outer/tree_removal*g2 [was: test]/tree_removal*"
3156  "lower/tree_groups*low2/tree_groups*twoleafs/tree_groups*low1/tree_groups*upper/tree_groups*"
3157  "twoleafs/tree_keeled*low2/tree_keeled*lower/tree_keeled*upper/tree_keeled*low1/tree_keeled*"
3158  "low2/tree_keeled_2*twoleafs/tree_keeled_2*lower/tree_keeled_2*upper/tree_keeled_2*low1/tree_keeled_2*allButOne/tree_keeled_2" // finds "keeled group at leaf" 'allButOne'; see also ../../ARBDB/adtree.cxx@HIDDEN_KEELED_GROUP
3159  ));
3160 
3161  TEST_EXPECTATION(resultListingIs(keeledGroups, GLT_KNAME_NEST,
3162  "!twoleafs(L0)*!low2(L1)*?lower(L2)*" // tree_keeled
3163  "!low2(L0)*?lower(L1)*!allButOne(L2)" // tree_keeled_2
3164  ));
3165  }
3166 
3167  TreeNameSet keeledTrees;
3168  keeledTrees.insert("tree_keeled");
3169  keeledTrees.insert("tree_keeled_2");
3170 
3171  allGroups.setSearchRange(keeledTrees);
3172  allGroups.perform_search(GSM_FIND);
3173 
3174  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_AND_PARENT,
3175  // tree_keeled:
3176  "twoleafs*twoleafs<low2>*low2<lower>*lower<upper>*"
3177  "low2<low1>*"
3178 
3179  // tree_keeled_2:
3180  "low2*"
3181  "twoleafs*"
3182  "low2<lower>*"
3183  "lower<upper>*" // keeled group 'lower' encloses 'upper'
3184  "low2<low1>*"
3185  "low1<allButOne>"
3186  ));
3187 
3188  // test folding of keeled groups:
3189  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_FOLD,
3190  "twoleafs*low2*lower*upper*low1*" // tree_keeled
3191  "low2*twoleafs*lower*upper*low1*allButOne" // tree_keeled_2
3192  ));
3193 
3194  TEST_EXPECT_NO_ERROR(allGroups.fold_group(0, GFM_TOGGLE)); // fold 'twoleafs'
3195  TEST_EXPECT_NO_ERROR(allGroups.fold_group(2, GFM_TOGGLE)); // fold 'lower' -> does as well fold 'upper' (overlayed groups)
3196 
3197  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_FOLD,
3198  "[twoleafs]*low2*[lower]*[upper]*low1*" // tree_keeled
3199  "low2*twoleafs*lower*upper*low1*allButOne" // tree_keeled_2
3200  ));
3201 
3202  TEST_EXPECT_NO_ERROR(allGroups.fold_group(3, GFM_TOGGLE)); // unfold 'upper' -> does as well unfold 'lower' (overlayed groups)
3203  TEST_EXPECT_NO_ERROR(allGroups.fold_group(10, GFM_TOGGLE));
3204 
3205  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_FOLD,
3206  "[twoleafs]*low2*lower*upper*low1*" // tree_keeled
3207  "low2*twoleafs*lower*upper*low1*[allButOne]" // tree_keeled_2
3208  ));
3209 
3210  TEST_EXPECT_NO_ERROR(allGroups.fold_group(0, GFM_TOGGLE));
3211  TEST_EXPECT_NO_ERROR(allGroups.fold_group(10, GFM_TOGGLE));
3212 
3213  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_FOLD,
3214  "twoleafs*low2*lower*upper*low1*" // tree_keeled
3215  "low2*twoleafs*lower*upper*low1*allButOne" // tree_keeled_2
3216  ));
3217 
3218  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_AID,
3219  // tree_keeled:
3220  "twoleafs(1.4310)*low2(1.4436)*lower(1.0288)*upper(1.0288)*low1(1.1200)*"
3221 
3222  // tree_keeled_2:
3223  "low2(1.4436)*twoleafs(0.0087)*lower(1.0288)*upper(1.0288)*low1(1.1200)*"
3224  "allButOne(0.0000)" // 1 member -> zero AID
3225  ));
3226 
3227  keeledTrees.insert("tree_groups");
3228  allGroups.setSearchRange(keeledTrees);
3229  allGroups.perform_search(GSM_FIND);
3230 
3231  TEST_EXPECTATION(resultListingIs(allGroups, GLT_KNAME_NEST,
3232  // tree_groups:
3233  "lower(L0)*low2(L1)*twoleafs(L2)*low1(L1)*upper(L0)*"
3234 
3235  // tree_keeled:
3236  "!twoleafs(L0)*!low2(L1)*?lower(L2)*upper(L3)*"
3237  "low1(L2)*"
3238 
3239  // tree_keeled_2:
3240  "!low2(L0)*"
3241  "twoleafs(L0)*"
3242  "?lower(L1)*upper(L2)*low1(L1)*!allButOne(L2)"
3243  ));
3244 
3245  TEST_EXPECTATION(resultListingIs(allGroups, GLT_NAME_SIZE,
3246  // tree_groups:
3247  "lower(10)*low2(3)*twoleafs(2)*low1(7)*upper(5)*"
3248 
3249  // tree_keeled:
3250  "twoleafs(13)*"
3251  "low2(12)*"
3252  "lower(5)*upper(5)*"
3253  "low1(7)*"
3254 
3255  // tree_keeled_2:
3256  "low2(12)*"
3257  "twoleafs(2)*"
3258  "lower(5)*"
3259  "upper(5)*low1(7)*"
3260  "allButOne(1)" // only 1 species!
3261  ));
3262 
3263  allGroups.addSortCriterion(GSC_KEELED);
3264  TEST_EXPECTATION(resultListingIs(allGroups, GLT_KNAME_NEST,
3265  "?lower(L2)*?lower(L1)*!twoleafs(L0)*!low2(L1)*!low2(L0)*!allButOne(L2)*lower(L0)*low2(L1)*twoleafs(L2)*low1(L1)*upper(L0)*upper(L3)*low1(L2)*twoleafs(L0)*upper(L2)*low1(L1)"
3266  ));
3267  }
3268 
3269  GB_close(gb_main);
3270 }
3271 
3272 
3273 
3274 static arb_test::match_expectation does_map_index(const SymmetricMatrixMapper& mm, int x, int y, int lin) {
3275  using namespace arb_test;
3276  expectation_group fulfilled;
3277 
3278  fulfilled.add(that(mm.linear_index(x, y)).is_equal_to(lin));
3279  fulfilled.add(that(mm.linear_index(y, x)).is_equal_to(lin));
3280 
3281  int rx, ry;
3282  mm.to_xy(lin, rx, ry);
3283  if (x>y) swap(x, y);
3284 
3285  fulfilled.add(that(rx).is_equal_to(x));
3286  fulfilled.add(that(ry).is_equal_to(y));
3287 
3288  return all().ofgroup(fulfilled);
3289 }
3290 
3291 void TEST_SymmetricMatrixMapper() {
3292  {
3293  SymmetricMatrixMapper m2(2);
3294  TEST_EXPECT_EQUAL(m2.linear_size(), 1);
3295  TEST_EXPECTATION(does_map_index(m2, 0, 1, 0));
3296  }
3297  {
3298  SymmetricMatrixMapper m3(3);
3299  TEST_EXPECT_EQUAL(m3.linear_size(), 3);
3300  TEST_EXPECTATION(does_map_index(m3, 0, 1, 0));
3301  TEST_EXPECTATION(does_map_index(m3, 2, 0, 1));
3302  TEST_EXPECTATION(does_map_index(m3, 2, 1, 2));
3303  }
3304  {
3305  SymmetricMatrixMapper m100(100);
3306  TEST_EXPECT_EQUAL(m100.linear_size(), 4950);
3307  TEST_EXPECTATION(does_map_index(m100, 0, 1, 0));
3308  TEST_EXPECTATION(does_map_index(m100, 49, 50, 1274));
3309  TEST_EXPECTATION(does_map_index(m100, 51, 50, 1274+51));
3310  TEST_EXPECTATION(does_map_index(m100, 99, 98, 4949));
3311  }
3312 }
3313 
3314 void TEST_group_duplicate_detection() {
3315  GB_shell shell;
3316  GBDATA *gb_main = GB_open("../../demo.arb", "r");
3317 
3318  GroupSearchCallback traceRefresh_cb = makeGroupSearchCallback(trace_refresh_cb);
3319 
3320  {
3321  refreshes_traced = 0;
3322 
3323  GroupSearch search(gb_main, traceRefresh_cb);
3324  search.addSortCriterion(GSC_NAME);
3325  search.addSortCriterion(GSC_TREENAME);
3326 
3327  search.setDupCriteria(true, DNC_WHOLENAME, GB_MIND_CASE, DLC_SAME_TREE, 2);
3328  search.perform_search(GSM_FIND);
3329  TEST_EXPECTATION(hasOrder(search, "TN")); // treename, groupname
3330  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3331  "1/outer/tree_test*"
3332  "1/outer/tree_test*"
3333  "2/test/tree_test*"
3334  "2/test/tree_test*"
3335  "3/outer/tree_tree2*"
3336  "3/outer/tree_tree2*"
3337  "4/test/tree_tree2*"
3338  "4/test/tree_tree2"
3339  ));
3340 
3341  search.addSortCriterion(GSC_REVERSE);
3342  search.addSortCriterion(GSC_CLUSTER);
3343  search.addSortCriterion(GSC_REVERSE);
3344 
3345  search.setDupCriteria(true, DNC_WHOLENAME, GB_MIND_CASE, DLC_ANYWHERE, 2);
3346  search.perform_search(GSM_FIND);
3347  TEST_EXPECTATION(hasOrder(search, "!C!TN")); // cluster(rev), treename, groupname
3348  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3349  "5/g2/tree_tree2*"
3350  "5/g2/tree_zomb*"
3351  "4/xx/tree_test*"
3352  "4/xx/tree_tree2*"
3353  "4/xx/tree_zomb*"
3354  "3/test/tree_test*"
3355  "3/test/tree_test*"
3356  "3/test/tree_tree2*"
3357  "3/test/tree_tree2*"
3358  "2/inner/tree_test*"
3359  "2/inner/tree_tree2*"
3360  "1/outer/tree_test*"
3361  "1/outer/tree_test*"
3362  "1/outer/tree_tree2*"
3363  "1/outer/tree_tree2"
3364  ));
3365 
3366  search.setDupCriteria(false, DNC_WHOLENAME, GB_MIND_CASE, DLC_ANYWHERE, 2); // search "unique" groups
3367  search.perform_search(GSM_FIND);
3368  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3369  "0/another group/tree_test*"
3370  "0/last/tree_test*"
3371  "0/ZOMB/tree_zomb*"
3372  "0/dup/tree_zomb*"
3373  "0/eee/tree_zomb*"
3374  "0/g3/tree_zomb*"
3375  "0/g4/tree_zomb*"
3376  "0/inner group/tree_zomb*"
3377  "0/inner outer group/tree_zomb*"
3378  "0/outer group/tree_zomb*"
3379  "0/yy/tree_zomb*"
3380  "0/zomb/tree_zomb*"
3381  "0/zombsub/tree_zomb"
3382  ));
3383 
3384  search.addSortCriterion(GSC_NAME);
3385  search.addSortCriterion(GSC_TREENAME);
3386  search.addSortCriterion(GSC_CLUSTER);
3387 
3388  search.setDupCriteria(true, DNC_WHOLENAME, GB_MIND_CASE, DLC_DIFF_TREE, 2);
3389  search.perform_search(GSM_FIND);
3390  TEST_EXPECTATION(hasOrder(search, "CTN")); // cluster, treename, groupname
3391  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3392  "1/outer/tree_test*"
3393  "1/outer/tree_test*"
3394  "1/outer/tree_tree2*"
3395  "1/outer/tree_tree2*"
3396  "2/inner/tree_test*"
3397  "2/inner/tree_tree2*"
3398  "3/test/tree_test*"
3399  "3/test/tree_test*"
3400  "3/test/tree_tree2*"
3401  "3/test/tree_tree2*"
3402  "4/xx/tree_test*"
3403  "4/xx/tree_tree2*"
3404  "4/xx/tree_zomb*"
3405  "5/g2/tree_tree2*"
3406  "5/g2/tree_zomb"
3407  ));
3408 
3409  search.setDupCriteria(true, DNC_WHOLENAME, GB_MIND_CASE, DLC_DIFF_TREE, 3); // expect hits in 3 diff. trees
3410  search.perform_search(GSM_FIND);
3411  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT, // Note: does not add 'outer' or 'test' (they occur 4 times, but only in 2 trees!)
3412  "1/xx/tree_test*"
3413  "1/xx/tree_tree2*"
3414  "1/xx/tree_zomb"
3415  ));
3416 
3417  // --------------------------------------------
3418  // test DNC_WORDWISE name comparison:
3419 
3420  const char *word_sep = " ";
3421  WordSet no_words_ignored;
3422  search.setDupCriteria(true, DNC_WORDWISE, GB_MIND_CASE, 1, no_words_ignored, word_sep, DLC_ANYWHERE, 2);
3423  search.perform_search(GSM_FIND);
3424  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3425  "1/another group/tree_test*"
3426  "1/inner group/tree_zomb*"
3427  "1/inner outer group/tree_zomb*"
3428  "1/outer group/tree_zomb*"
3429 
3430  "2/outer/tree_test*"
3431  "2/outer/tree_test*"
3432  "2/outer/tree_tree2*"
3433  "2/outer/tree_tree2*"
3434 
3435  "3/test/tree_test*"
3436  "3/test/tree_test*"
3437  "3/test/tree_tree2*"
3438  "3/test/tree_tree2*"
3439 
3440  "4/xx/tree_test*"
3441  "4/xx/tree_tree2*"
3442  "4/xx/tree_zomb*"
3443 
3444  "5/inner/tree_test*"
3445  "5/inner/tree_tree2*"
3446 
3447  "6/g2/tree_tree2*"
3448  "6/g2/tree_zomb"
3449  ));
3450 
3451  search.setDupCriteria(true, DNC_WORDWISE, GB_MIND_CASE, 2, no_words_ignored, word_sep, DLC_ANYWHERE, 2);
3452  search.perform_search(GSM_FIND);
3453  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3454  "1/inner group/tree_zomb*"
3455  "1/inner outer group/tree_zomb"
3456  ));
3457 
3458  // rename one group (spaces->commas) to test special word separators
3459  {
3460  GB_transaction ta(gb_main);
3461  TEST_EXPECT_NO_ERROR(search.rename_group(0, "/ /,/"));
3462  TEST_EXPECT_EQUAL(search.get_results()[0].get_name(), "inner,group");
3463  }
3464 
3465  search.setDupCriteria(true, DNC_WORDWISE, GB_MIND_CASE, 2, no_words_ignored, word_sep, DLC_ANYWHERE, 2);
3466  search.perform_search(GSM_FIND);
3467  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT, // rename of group causes a change of detected cluster
3468  "1/inner outer group/tree_zomb*"
3469  "1/outer group/tree_zomb"
3470  ));
3471 
3472 
3473  word_sep = ", "; // <<<------------------------------ commas separate words from now on!
3474 
3475  search.setDupCriteria(true, DNC_WORDWISE, GB_MIND_CASE, 2, no_words_ignored, word_sep, DLC_ANYWHERE, 2);
3476  search.perform_search(GSM_FIND);
3477  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3478  "1/inner outer group/tree_zomb*"
3479  "1/inner,group/tree_zomb"
3480  ));
3481 
3482  WordSet ignore_group;
3483  ignore_group.insert("Group");
3484 
3485  search.setDupCriteria(true, DNC_WORDWISE, GB_IGNORE_CASE, 1, ignore_group, word_sep, DLC_ANYWHERE, 2);
3486  search.perform_search(GSM_FIND);
3487  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3488  "1/outer/tree_test*"
3489  "1/outer/tree_test*"
3490  "1/outer/tree_tree2*"
3491  "1/outer/tree_tree2*"
3492  "1/inner outer group/tree_zomb*"
3493  "1/outer group/tree_zomb*"
3494 
3495  "2/test/tree_test*"
3496  "2/test/tree_test*"
3497  "2/test/tree_tree2*"
3498  "2/test/tree_tree2*"
3499 
3500  "3/inner/tree_test*"
3501  "3/inner/tree_tree2*"
3502  "3/inner,group/tree_zomb*"
3503 
3504  "4/xx/tree_test*"
3505  "4/xx/tree_tree2*"
3506  "4/xx/tree_zomb*"
3507 
3508  "5/g2/tree_tree2*"
3509  "5/g2/tree_zomb*"
3510 
3511  "6/ZOMB/tree_zomb*"
3512  "6/zomb/tree_zomb"
3513  ));
3514 
3515  search.setDupCriteria(true, DNC_WORDWISE, GB_IGNORE_CASE, 2, ignore_group, word_sep, DLC_ANYWHERE, 2);
3516  search.perform_search(GSM_FIND);
3517  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT, "")); // none
3518 
3519  search.setDupCriteria(true, DNC_WORDWISE, GB_IGNORE_CASE, 1, ignore_group, "", DLC_ANYWHERE, 2); // empty word separator -> uses whole names
3520  search.perform_search(GSM_FIND);
3521  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3522  "1/outer/tree_test*"
3523  "1/outer/tree_test*"
3524  "1/outer/tree_tree2*"
3525  "1/outer/tree_tree2*"
3526 
3527  "2/test/tree_test*"
3528  "2/test/tree_test*"
3529  "2/test/tree_tree2*"
3530  "2/test/tree_tree2*"
3531 
3532  "3/xx/tree_test*"
3533  "3/xx/tree_tree2*"
3534  "3/xx/tree_zomb*"
3535 
3536  "4/inner/tree_test*"
3537  "4/inner/tree_tree2*"
3538 
3539  "5/g2/tree_tree2*"
3540  "5/g2/tree_zomb*"
3541 
3542  "6/ZOMB/tree_zomb*"
3543  "6/zomb/tree_zomb"
3544  ));
3545 
3546  // rename more groups to test cluster-search based on 3 words and extension based on 2 words
3547  {
3548  GB_transaction ta(gb_main);
3549  TEST_EXPECT_NO_ERROR(search.rename_group(0, "/outer/group inner outer/"));
3550  TEST_EXPECT_NO_ERROR(search.rename_group(1, "/outer/group outer/"));
3551  TEST_EXPECT_NO_ERROR(search.rename_group(2, "/outer/outer group/"));
3552  TEST_EXPECT_EQUAL(search.get_results()[0].get_name(), "group inner outer");
3553  TEST_EXPECT_EQUAL(search.get_results()[1].get_name(), "group outer");
3554  TEST_EXPECT_EQUAL(search.get_results()[2].get_name(), "outer group");
3555  }
3556 
3557  search.setDupCriteria(true, DNC_WORDWISE, GB_IGNORE_CASE, 2, no_words_ignored, word_sep, DLC_ANYWHERE, 2);
3558  search.perform_search(GSM_FIND);
3559  TEST_EXPECTATION(resultListingIs(search, GLT_CLUST_NT,
3560  "1/group inner outer/tree_test*" // cluster based on 3 words gets extended by groups matching 2 of these words ("group" and "outer")
3561  "1/group outer/tree_test*" // (note that group containing 'inner' and 'group' is discarded, because resulting cluster would be smaller)
3562  "1/outer group/tree_tree2*"
3563  "1/inner outer group/tree_zomb*"
3564  "1/outer group/tree_zomb"
3565  ));
3566 
3567  TEST_EXPECT_EQUAL(refreshes_traced, 2); // 2 renames
3568  }
3569  GB_close(gb_main);
3570 }
3571 
3572 static double bruteForce_calc_average_ingroup_distance(GroupSearchTree *node) {
3573  unsigned leafs = node->get_leaf_count();
3574 
3575  if (leafs == 1) return 0.0; // single leaf -> zero distance
3576 
3577  ARB_edge last = parentEdge(node->get_leftson());
3578  ARB_edge start = parentEdge(node->get_rightson()).inverse();
3579 
3580  if (start == last) {
3581  gs_assert(start.get_type() == ROOT_EDGE);
3582  start = start.next();
3583  }
3584 
3585  unsigned pairs = 0;
3586  double dist_sum = 0.0;
3587 
3588  for (ARB_edge e1 = start; e1 != last; e1 = e1.next()) {
3589  if (e1.is_edge_to_leaf()) {
3590  for (ARB_edge e2 = e1.next(); e2 != last; e2 = e2.next()) {
3591  if (e2.is_edge_to_leaf()) {
3592  dist_sum += e1.dest()->intree_distance_to(e2.dest());
3593  ++pairs;
3594  }
3595  }
3596  }
3597  }
3598 
3599 #if defined(ASSERTION_USED)
3600  const unsigned calc_pairs = (leafs*(leafs-1))/2;
3601  gs_assert(pairs == calc_pairs);
3602 #endif
3603 
3604  return dist_sum/pairs;
3605 }
3606 
3607 #define TEST_EXPECT_PROPER_AID(node) do{ \
3608  const double EPSILON = 0.000001; \
3609  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(node), \
3610  (node)->get_average_ingroup_distance(), \
3611  EPSILON); \
3612  }while(0)
3613 
3614 void TEST_ingroup_distance() {
3615  GB_shell shell;
3616  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
3617 
3618  {
3619  GB_transaction ta(gb_main);
3620  SearchedTree stree("tree_test", gb_main);
3621 
3622  GroupSearchRoot *troot = stree.get_tree_root();
3623  TEST_REJECT(stree.failed_to_load());
3624 
3625  // get some specific nodes:
3626  GroupSearchTree *rootNode = troot->get_root_node();
3627  GroupSearchTree *leftSon = rootNode->get_leftson();
3628  GroupSearchTree *grandSon = leftSon->get_rightson();
3629 
3630  GroupSearchTree *someLeaf = grandSon->get_leftson();
3631  while (!someLeaf->is_leaf()) { // descent into bigger subtree => reaches subtree containing 2 leafs
3632  GroupSearchTree *L = someLeaf->get_leftson();
3633  GroupSearchTree *R = someLeaf->get_rightson();
3634 
3635  someLeaf = L->get_leaf_count() > R->get_leaf_count() ? L : R;
3636  }
3637 
3638  TEST_EXPECT_EQUAL(someLeaf->get_leaf_count(), 1);
3639 
3640  GroupSearchTree *minSubtree = someLeaf->get_father();
3641  TEST_EXPECT_EQUAL(minSubtree->get_leaf_count(), 2);
3642 
3643  // brute-force AID calculation:
3644  {
3645  const double EPSILON = 0.000001;
3646  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(someLeaf), 0.0, EPSILON);
3647  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(minSubtree), minSubtree->leftlen + minSubtree->rightlen, EPSILON);
3648  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(grandSon), 0.534927, EPSILON);
3649  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(leftSon), 0.976091, EPSILON);
3650  TEST_EXPECT_SIMILAR(bruteForce_calc_average_ingroup_distance(rootNode), 1.108438, EPSILON);
3651  }
3652 
3653  // calculate AID on-the-fly and compare with brute-force results
3654  TEST_EXPECT_PROPER_AID(someLeaf);
3655  TEST_EXPECT_PROPER_AID(minSubtree);
3656  TEST_EXPECT_PROPER_AID(grandSon);
3657  TEST_EXPECT_PROPER_AID(leftSon);
3658  TEST_EXPECT_PROPER_AID(rootNode);
3659 
3660  ARB_edge start = rootEdge(troot);
3661  for (ARB_edge e = start.next(); e != start; e = e.next()) {
3662  TEST_EXPECT_PROPER_AID(DOWNCAST(GroupSearchTree*, e.dest()));
3663  }
3664  }
3665  GB_close(gb_main);
3666 }
3667 
3668 #endif // UNIT_TESTS
3669 
3670 // --------------------------------------------------------------------------------
3671 
DupTreeCriterionType
Definition: group_search.h:303
const char * get_tree_name() const
void compute_tree() OVERRIDE
const char * GB_ERROR
Definition: arb_core.h:25
bool big_enough(const GroupCluster &cluster) const
static GB_ERROR grl_hitcount(GBL_command_arguments *args)
string result
FoundGroup & get_group()
GBDATA * GB_open(const char *path, const char *opent)
Definition: ad_load.cxx:1363
GB_TYPES type
const std::string & get_hit_reason() const
Definition: group_search.h:190
const char * get_group_display(const FoundGroup &g, bool show_tree_name) const
GroupSearchRoot * get_tree_root()
void inc_to_avoid_overflow(PINT x)
Definition: arb_progress.h:305
compare_by_criteria(const SortCriteria &by_)
void put(const char *elem)
Definition: arb_strarray.h:199
void forgetSortCriteria()
Definition: group_search.h:366
GroupClusterCIter begin() const
std::set< std::string > SpeciesNames
Definition: group_search.h:232
group_matcher all()
Definition: test_unit.h:1000
bool group_is_folded(GBDATA *gb_group)
int get_marked_pc() const
Definition: group_search.h:214
GBDATA * get_parent_group(GBDATA *gb_group) const
AliDataPtr format(AliDataPtr data, const size_t wanted_len, GB_ERROR &error)
Definition: insdel.cxx:615
unsigned get_leaf_count() const FINAL_OVERRIDE
#define TRIGGER_UPDATE_GROUP_RESULTS
Lazy< int,-1 > nesting
Definition: group_search.h:166
~GroupSearchRoot() FINAL_OVERRIDE
#define TEST_EXPECT_SIMILAR(expr, want, epsilon)
Definition: test_unit.h:1287
const SortCriteria & by
Definition: arbdb.h:65
long GB_read_int(GBDATA *gbd)
Definition: arbdb.cxx:699
bool empty() const
GBDATA * GB_child(GBDATA *father)
Definition: adquery.cxx:322
GB_ERROR GB_add_hierarchy_callback(GBDATA *gb_main, const char *db_path, GB_CB_TYPE type, const DatabaseCallback &dbcb)
Definition: ad_cb.cxx:432
#define implicated(hypothesis, conclusion)
Definition: arb_assert.h:289
static char * y[maxsp+1]
return string(buffer, length)
bool overlap_is_folded() const
GB_ERROR delete_group(size_t idx)
GBDATA * get_tree_data()
bool empty() const
Definition: group_search.h:266
const WordSet & get_ignored_words() const
NestingLevelKey(const GroupSearch &group_search_)
static void collect_searched_trees(GBDATA *gb_main, const TreeNameSet &trees_to_search, SearchedTreeContainer &searched_tree)
bool has_group_info() const
Definition: TreeNode.h:403
Definition: AP_filter.hxx:36
void addSortCriterion(GroupSortCriterion gsc)
GB_ERROR GB_add_callback(GBDATA *gbd, GB_CB_TYPE type, const DatabaseCallback &dbcb)
Definition: ad_cb.cxx:356
#define DOWNCAST_REFERENCE(totype, expr)
Definition: downcast.h:152
GroupSearchCommon * common
static void result_update_cb(GBDATA *, GroupSearchCommon *common)
void string_to_lower(string &s)
GB_ERROR delete_from_DB()
#define DEFINE_TREE_RELATIVES_ACCESSORS(TreeType)
Definition: TreeNode.h:572
void setDupCriteria(bool listDups, DupNameCriterionType ntype, GB_CASE sens, DupTreeCriterionType ttype, int min_cluster_size)
int get_tree_order() const
const FoundGroup * get_hit_group() const
GB_ERROR delete_found_groups()
match_expectation doesnt_report_error(const char *error)
Definition: test_unit.h:1094
const FoundGroup & get_group() const
GBDATA * GB_nextEntry(GBDATA *entry)
Definition: adquery.cxx:339
#define DEFINE_TREE_ROOT_ACCESSORS(RootType, TreeType)
Definition: TreeNode.h:569
const char * get_load_error() const
long
Definition: AW_awar.cxx:154
unsigned get_marked_count() const
bool contains_changed(GroupSearchCommon *common) const
void add(int v)
Definition: ClustalV.cxx:461
void inc_to(PINT x)
Definition: arb_progress.h:304
void find_and_deliverTo(QueriedGroups &toResult)
void buildInferableClusterStartingWith(int start_idx, GroupCluster &cluster)
ARB_edge_type get_type() const
Definition: TreeNode.h:725
const char * get_name() const OVERRIDE
ARB_ERROR set_marks_in_found_groups(GroupMarkMode mode, CollectMode cmode)
void allow_lookup() const
double get_average_ingroup_distance() const
TreeNode * GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot)
Definition: adtree.cxx:791
const char * get_name() const OVERRIDE
void inform_group(const GroupSearch &group_search, const string &hitReason)
bool isCorrectParent(TreeNode *node, GBDATA *gb_group, GBDATA *gb_parent_group)
static GB_ERROR grl_nesting(GBL_command_arguments *args)
int calc_nesting_level(GBDATA *gb_group) const
ARB_edge inverse() const
Definition: TreeNode.h:753
bool tree_matches(const GBDATA *data1, const GBDATA *data2) const
double get_average_ingroup_distance() const
const char * GBS_global_string(const char *templat,...)
Definition: arb_msg.cxx:204
const char * get_name() const OVERRIDE
void erase()
Definition: arb_strbuf.h:82
STL namespace.
void insert(int i)
int get_leaf_count() const
bool is_folded() const
SmartPtr< GroupSearchRoot > GroupSearchRootPtr
GroupSortCriterion
Definition: group_search.h:237
void cat(const char *from)
Definition: arb_strbuf.h:156
bool isNull() const
test if SmartPtr is NULp
Definition: smartptr.h:248
GroupRename_callenv(const QueriedGroups &queried_, int hit_idx_, const GBL_env &env_)
bool has_been_deleted(GBDATA *gb_node)
was_modified(GroupSearchCommon *common_)
void refresh_results_after_DBchanges()
const TreeNode * find_parent_with_groupInfo(bool skipKeeledBrothers=false) const
Definition: TreeNode.h:452
ARB_edge rootEdge(TreeRoot *root)
Definition: TreeNode.h:857
void findBestClusterBasedOnWords(int wanted_words, GroupCluster &best, arb_progress &progress_cluster, int &first_cluster_found_from_index)
bool already_delivered(int idx) const
CollectMode
Definition: group_search.h:72
GroupCluster(const GroupCluster &other)
static void set_marks_of(const SpeciesNames &targetSpecies, GBDATA *gb_main, GroupMarkMode mode)
#define ARRAY_ELEMS(array)
Definition: arb_defs.h:19
int name_matches(const GroupInfo &gi1, const GroupInfo &gi2) const
void setNull()
set SmartPtr to NULp
Definition: smartptr.h:251
Lazy< int,-1 > keeled
Definition: group_search.h:172
int max_cluster_start_index() const
GBDATA * GB_get_father(GBDATA *gbd)
Definition: arbdb.cxx:1696
const char * get_name() const OVERRIDE
GBDATA * get_gb_main() const
Definition: group_search.h:357
const GBL_call_env & get_callEnv() const
Definition: gb_aci.h:234
std::set< std::string > WordSet
Definition: group_search.h:309
int linear_index(int x, int y) const
GroupSearchTree(GroupSearchRoot *root)
#define DOWNCAST(totype, expr)
Definition: downcast.h:141
#define FINAL_OVERRIDE
Definition: cxxforward.h:95
ARB_ERROR fold_found_groups(GroupFoldingMode mode)
DupNameCriterionType get_name_type() const
GB_ERROR check_no_parameter(GBL_command_arguments *args)
Definition: gb_aci_impl.h:154
GB_ERROR GB_delete(GBDATA *&source)
Definition: arbdb.cxx:1880
int GB_string_comparator(const void *v0, const void *v1, void *)
Definition: arb_sort.cxx:47
ARB_edge next() const
Definition: TreeNode.h:763
static HelixNrInfo * start
ARB_edge parentEdge(TreeNode *son)
Definition: TreeNode.h:842
Lazy< int,-1 > marked
Definition: group_search.h:168
POS_TREE1 * father
Definition: probe_tree.h:39
unsigned long permutations(int elems)
GroupInfo(const FoundGroup &g, bool prep_wordwise, GB_CASE sens, const char *wordSeparators, const WordSet &ignored_words)
const double EPSILON
Definition: aw_position.hxx:73
GroupClusterCIter end() const
Lazy< int,-1 > size
Definition: group_search.h:167
GroupCluster(int num_of_groups)
size_t GB_read_string_count(GBDATA *gbd)
Definition: arbdb.cxx:886
GB_ERROR GB_await_error()
Definition: arb_msg.cxx:353
int get_keeledStateInfo() const
ARB_ERROR rename_by_ACI(const char *acisrt, const QueriedGroups &results, int hit_idx)
#define TEST_EXPECT(cond)
Definition: test_unit.h:1312
GroupSearchMode
Definition: group_search.h:320
static void set_species_data(GBDATA *gb_species_data_)
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
DupCriteria(bool listDups_, const DupNameCriterion &nameCrit_, DupTreeCriterionType ttype_, int minSize_)
std::set< GBDATA * > GBDATAset
Definition: group_search.h:229
const GroupSearchTree * get_clade() const
bool erase_deleted(GroupSearchCommon *common)
bool needs_eval() const
Definition: lazy.h:61
GB_CSTR GB_read_key_pntr(GBDATA *gbd)
Definition: arbdb.cxx:1630
const char * get_word_separators() const
const char * get_name() const OVERRIDE
bool isSet() const
test if SmartPtr is not NULp
Definition: smartptr.h:245
GBDATA * GB_create(GBDATA *father, const char *key, GB_TYPES type)
Definition: arbdb.cxx:1755
bool empty() const
GB_CASE get_sensitivity() const
GBDATA * gb_species_data
Definition: adname.cxx:34
bool aborted()
Definition: arb_progress.h:277
bool knows_details() const
Definition: group_search.h:199
list< Candidate > CandidateList
void addQueryExpression(CriterionOperator op, CriterionType type, CriterionMatch mtype, const char *expression)
static int group[MAXN+1]
Definition: ClustalV.cxx:65
vector< GroupInfo > GroupInfoVec
#define false
Definition: ureadseq.h:13
DupNameCriterionType
Definition: group_search.h:297
void forgetDupCriteria()
bool has_results() const
Definition: group_search.h:392
char * GBS_trim(const char *str)
Definition: adstring.cxx:961
GB_ERROR GBT_write_group_name(GBDATA *gb_group_name, const char *new_group_name, bool pedantic)
Definition: adtree.cxx:229
void deliverRest(QueriedGroups &toResult)
#define COMMAND_DROPS_INPUT_STREAMS(args)
Definition: gb_aci_impl.h:220
const char * GBS_readable_size(unsigned long long size, const char *unit_suffix)
Definition: arb_misc.cxx:23
LazyFloat< double > aid
Definition: group_search.h:170
#define TEST_REJECT(cond)
Definition: test_unit.h:1314
#define TEST_REJECT_NULL(n)
Definition: test_unit.h:1309
const QueriedGroups & queried
static void error(const char *msg)
Definition: mkptypes.cxx:96
std::set< std::string > TreeNameSet
Definition: group_search.h:318
unsigned get_group_size() const
GBDATA * GB_get_root(GBDATA *gbd)
Definition: arbdb.cxx:1714
GroupSearch(GBDATA *gb_main_, const GroupSearchCallback &redisplay_results_cb)
static void string2WordSet(const char *name, WordSet &words, const char *wordSeparators, const WordSet &ignored_words)
bool contains(int i) const
bool tree_is_loaded() const
query_key_type
Definition: query_expr.h:81
void GBT_splitNdestroy_string(ConstStrArray &names, char *&namelist, const char *separator, bool dropEmptyTokens)
bool operator()(const FoundGroup &g)
ARB_ERROR rename_group(size_t idx, const char *acisrt)
int get_nesting() const
Definition: group_search.h:211
expectation_group & add(const expectation &e)
Definition: test_unit.h:801
~TargetGroup() OVERRIDE
CONSTEXPR_INLINE_Cxx14 void swap(unsigned char &c1, unsigned char &c2)
Definition: ad_io_inline.h:19
has_been_deleted(GroupSearchCommon *common_)
size_t get_word_count() const
ASSERTING_CONSTEXPR_INLINE int info2bio(int infopos)
Definition: arb_defs.h:27
bool is_keeled_group() const
Definition: TreeNode.h:434
#define that(thing)
Definition: test_unit.h:1032
void track_max_widths(ColumnWidths &widths) const
const char * get_name() const
DupNameCriterion(DupNameCriterionType exact, GB_CASE sens_)
bool has_been_modified(GBDATA *gb_node)
set< int > GroupClusterSet
void notify_modified(GBDATA *gb_node)
int get_keeled() const
Definition: group_search.h:215
bool iterate() const OVERRIDE
FoundGroupCIter end() const
Definition: group_search.h:277
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
void deliverCluster(const GroupCluster &ofCluster, QueriedGroups &toResult)
GroupSearchTree * get_clade()
ARB_ERROR set_marks_in_group(size_t idx, GroupMarkMode mode)
bool wordwise_name_matching() const
#define cmp(h1, h2)
Definition: admap.cxx:50
GroupClusterSet::const_iterator GroupClusterCIter
GBQUARK GB_get_quark(GBDATA *gbd)
Definition: arbdb.cxx:1677
void fix_deleted_groups(const GBDATAset &deleted_groups)
int GB_read_flag(GBDATA *gbd)
Definition: arbdb.cxx:2760
GBDATA * GBT_find_species_rel_species_data(GBDATA *gb_species_data, const char *name)
Definition: aditem.cxx:133
void forgetQExpressions()
AP_tree_nlen * rootNode()
Definition: ap_main.hxx:54
bool contains(const WordSet &ws, const string &w)
void remove_hit(size_t idx)
void track(int wName, int wReason, int nesting, int size, int marked, int clusID, double aid, bool keeled)
Candidate(GBDATA *gb_group_, GroupSearchTree *node_)
void remove(GroupSearch *gs)
RefPtr< GBDATA > tree
ARB_ERROR group_set_folded(GBDATA *gb_group, bool folded)
static int max2width(const int &i)
Definition: group_search.h:131
char * GS_calc_resulting_groupname(GBDATA *gb_main, const QueriedGroups &queried, int hit_idx, const char *input_name, const char *acisrt, ARB_ERROR &error)
Definition: lazy.h:26
static GBL_command_definition groupRename_command_table[]
void sort_by(const SortCriteria &by)
GB_CASE
Definition: arb_core.h:30
Candidate(const FoundGroup &group_, GroupSearchTree *node_)
void append(QueryExpr *&tail)
Definition: query_expr.cxx:46
#define is_equal_to(val)
Definition: test_unit.h:1014
void erase(int i)
double get_aid() const
Definition: group_search.h:216
void add_informed_group(const FoundGroup &group)
Definition: group_search.h:268
group_matcher none()
Definition: test_unit.h:1001
FoundGroupContainer::const_iterator FoundGroupCIter
Definition: group_search.h:234
TYPE get_type() const
Definition: probe_tree.h:64
GB_ERROR inc_and_error_if_aborted()
Definition: arb_progress.h:269
static GB_ERROR grl_aid(GBL_command_arguments *args)
#define TEST_EXPECTATION(EXPCTN)
Definition: test_unit.h:1037
SearchedTreeContainer::iterator SearchedTreeIter
const FoundGroup & get_group() const
TreeNode * dest() const
Definition: TreeNode.h:727
int get_edge_iteration_count() const
char * GBT_join_strings(const CharPtrArray &strings, char separator)
static GB_ERROR grl_groupsize(GBL_command_arguments *args)
const char * get_name() const OVERRIDE
bool is_edge_to_leaf() const
Definition: TreeNode.h:823
int get_cluster_id() const
Definition: group_search.h:194
void set_cluster_id(int id)
Definition: group_search.h:192
bool is_leaf() const
Definition: TreeNode.h:171
GB_ERROR GB_remove_hierarchy_callback(GBDATA *gb_main, const char *db_path, GB_CB_TYPE type, const DatabaseCallback &dbcb)
Definition: ad_cb.cxx:440
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
DupTreeCriterionType get_tree_type() const
xml element
GB_ERROR close(GB_ERROR error)
Definition: arbdbpp.cxx:32
void GB_write_flag(GBDATA *gbd, long flag)
Definition: arbdb.cxx:2737
int min_cluster_size() const
#define FORMAT_2_OUT(args, fmt, value)
Definition: gb_aci_impl.h:24
bool operator()(const FoundGroup &g)
GBDATA * get_tree_data() const
bool is_inferable() const
void flush_loaded_tree()
#define TEST_EXPECTATION__BROKEN(WANTED, GOT)
Definition: test_unit.h:1040
FoundGroupContainer::iterator FoundGroupIter
Definition: group_search.h:235
#define OVERRIDE
Definition: cxxforward.h:93
static void tree_node_deleted_cb(GBDATA *gb_node, GroupSearchCommon *common, GB_CB_TYPE cbtype)
void GB_touch(GBDATA *gbd)
Definition: arbdb.cxx:2766
#define gs_assert(cond)
Definition: group_search.h:48
bool needs_eval() const
Definition: lazy.h:37
GBQUARK GB_find_existing_quark(GBDATA *gbd, const char *key)
Definition: arbdb.cxx:1664
Clusterer(GBDATA *gb_main, SmartPtr< QueriedGroups > groups_, SmartPtr< DupCriteria > criteria_)
char * name
Definition: TreeNode.h:134
void nprintf(size_t maxlen, const char *templat,...) __ATTR__FORMAT_MEMBER(2)
Definition: arb_strbuf.cxx:29
int GB_read_byte(GBDATA *gbd)
Definition: arbdb.cxx:704
bool matches(const QueryTarget &target, std::string &hit_reason) const
Definition: query_expr.cxx:277
void forget_lookup() const
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
static GB_ERROR grl_markedingroup(GBL_command_arguments *args)
GBDATA * lookupParent(GBDATA *gb_child_group) const
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
GBDATA * get_ACI_item() const
char * GB_read_string(GBDATA *gbd)
Definition: arbdb.cxx:879
GB_ERROR GB_write_byte(GBDATA *gbd, int i)
Definition: arbdb.cxx:1208
int name_matches_wordwise(const GroupInfo &gi1, const GroupInfo &gi2) const
bool want_unique_groups() const
CriterionMatch
Definition: group_search.h:82
void GB_remove_callback(GBDATA *gbd, GB_CB_TYPE type, const DatabaseCallback &dbcb)
Definition: ad_cb.cxx:360
~ParentGroupNameQueryKey() OVERRIDE
FoundGroupCIter begin() const
Definition: group_search.h:275
GBDATA * GBT_first_species(GBDATA *gb_main)
Definition: aditem.cxx:124
void GBT_get_tree_names(ConstStrArray &names, GBDATA *gb_main, bool sorted)
Definition: adtree.cxx:1136
void GBT_message(GBDATA *gb_main, const char *msg)
Definition: adtools.cxx:238
query_operator
Definition: query_expr.h:64
std::list< GroupSortCriterion > SortCriteria
Definition: group_search.h:253
unsigned get_marked_count() const
void negate()
Definition: query_expr.cxx:56
const char * get_name() const
#define TEST_EXPECT_NO_ERROR(call)
Definition: test_unit.h:1107
const char * get_group_name() const
GBDATA * get_pointer() const
Definition: group_search.h:184
int get_keeledStateInfo() const
DECLARE_ASSIGNMENT_OPERATOR(GroupCluster)
const ColumnWidths & get_column_widths() const
const GroupRename_callenv & custom_env(GBL_command_arguments *args)
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
const char * get_name() const OVERRIDE
CriterionType
Definition: group_search.h:86
DupNameCriterion(DupNameCriterionType wordwise, GB_CASE sens_, int min_words_, const WordSet &ignored_words_, const char *wordSeparators_)
void sort(CharPtrArray_compare_fun compare, void *client_data)
int get_marked() const
Definition: group_search.h:213
ARB_ERROR fold_group(size_t idx, GroupFoldingMode mode)
bool is_inner_edge() const
Definition: TreeNode.h:831
GBDATA * GBT_next_species(GBDATA *gb_species)
Definition: aditem.cxx:128
#define NULp
Definition: cxxforward.h:97
static const GBL_command_lookup_table & get_GroupRename_customized_ACI_commands()
void add(GroupSearch *gs)
size_t size() const
Definition: group_search.h:265
bool is_leaf() const
Definition: probe_tree.h:67
#define TEST_EXPECT_ERROR_CONTAINS(call, part)
Definition: test_unit.h:1103
vector< SearchedTree > SearchedTreeContainer
GroupFoldingMode
Definition: group_search.h:52
void add_candidate(const GroupSearch &group_search, Candidate &cand, const std::string &hit_reason)
const char * get_data() const
Definition: arb_strbuf.h:70
int get_min_wanted_words() const
RefPtr< GBDATA > gb_overlap_group
Definition: group_search.h:173
NOT4PERL char * GB_command_interpreter_in_env(const char *str, const char *commands, const GBL_call_env &callEnv)
Definition: gb_aci.cxx:361
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
void inc_by(PINT count)
Definition: arb_progress.h:303
GBDATA * GB_nextChild(GBDATA *child)
Definition: adquery.cxx:326
void notify_deleted(GBDATA *gb_node)
const char * get_name() const OVERRIDE
ParentCache & get_parent_cache()
TreeNode * keelTarget()
Definition: TreeNode.h:407
GBDATA * GBT_find_tree(GBDATA *gb_main, const char *tree_name)
Definition: adtree.cxx:947
GB_transaction ta(gb_var)
int calc_max_used_words(bool ignore_delivered)
const QueriedGroups & get_results()
void reset() const OVERRIDE
SymmetricMatrixMapper(int elements)
static void group_name_changed_cb(GBDATA *gb_group_name, GroupSearchCommon *common)
GB_CSTR GB_read_char_pntr(GBDATA *gbd)
Definition: arbdb.cxx:874
GBDATA * gb_node
Definition: TreeNode.h:133
GBDATA * gb_main
Definition: adname.cxx:33
TargetGroup(GBDATA *gb_main_, const char *treename_)
void forget_results()
Definition: group_search.h:394
ParentGroupNameQueryKey(const GroupSearch &group_search_, CriterionType ctype)
bool operator()(const FoundGroup &g1, const FoundGroup &g2) const
void defineParentOf(GBDATA *gb_child_group, GBDATA *gb_parent_group)
ARB_ERROR rename_found_groups(const char *acisrt)
GroupSearchCommon * common
GBDATA * GB_search(GBDATA *gbd, const char *fieldpath, GB_TYPES create)
Definition: adquery.cxx:531
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
void aimTo(const Candidate &c)
std::string hit_reason
Definition: group_search.h:165
GB_CSTR GBT_get_name_or_description(GBDATA *gb_item)
Definition: aditem.cxx:437
size_t length
GB_CB_TYPE
Definition: arbdb_base.h:46
ARB_ERROR change_folding(GroupFoldingMode mode)
int get_size() const
Definition: group_search.h:212
void perform_search(GroupSearchMode mode)
#define min(a, b)
Definition: f2c.h:153
char * get_target_data(const QueryTarget &target, GB_ERROR &) const OVERRIDE
static int info[maxsites+1]
CONSTEXPR_INLINE int double_cmp(const double d1, const double d2)
Definition: arbtools.h:182
static GB_ERROR grl_hitidx(GBL_command_arguments *args)
const GroupSearchTree * get_clade() const
GroupMarkMode
Definition: group_search.h:66
void set_min_wanted_words(int words)
unsigned get_zombie_count() const
SearchedTree(const char *name_, GBDATA *gb_main)
const char * get_name() const OVERRIDE
GroupMarkedKey(bool percent_)
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1283
const GBL_command_lookup_table & ACI_get_standard_commands()
Definition: adlang1.cxx:2724
SmartPtr< WordSet > words
bool failed_to_load() const
bool is_normal_group() const
Definition: TreeNode.h:429
GBDATA * GB_entry(GBDATA *father, const char *key)
Definition: adquery.cxx:334
bool legal_hit_index() const
li
Definition: AW_awar.cxx:154
char * GBS_global_string_copy(const char *templat,...)
Definition: arb_msg.cxx:195
void GB_close(GBDATA *gbd)
Definition: arbdb.cxx:625
TreeNode * source() const
Definition: TreeNode.h:726
unsigned get_zombie_count() const
CriterionOperator
Definition: group_search.h:77
size_t size() const
void put(char c)
Definition: arb_strbuf.h:138
static int iteration_count(int leafs_in_tree)
Definition: TreeNode.h:809
Definition: cache.h:31
#define UNCOVERED()
Definition: arb_assert.h:380
Definition: arbdb.h:66
GBDATA * GBT_get_species_data(GBDATA *gb_main)
Definition: aditem.cxx:105
GB_write_int const char s
Definition: AW_awar.cxx:156
#define max(a, b)
Definition: f2c.h:154