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