source: tags/ms_r16q3/NTREE/NT_taxonomy.cxx

Last change on this file was 15306, checked in by westram, 8 years ago
  • derive TREE_canvas from AWT_canvas
    • move awar_tree → TREE_canvas
    • use TREE_canvas where required
    • remove dummy-param from AWT_canvas-ctor
  • rename NT_canvas_registry → TREE_canvas_registry
  • remove unused param from AP_user_push_cb
File size: 13.6 KB
Line 
1// =========================================================== //
2//                                                             //
3//   File      : NT_taxonomy.cxx                               //
4//   Purpose   : Compare two trees by taxonomy                 //
5//                                                             //
6//   Coded by Ralf Westram (coder@reallysoft.de) in May 2015   //
7//   http://www.arb-home.de/                                   //
8//                                                             //
9// =========================================================== //
10
11#include "ad_trees.h"
12#include "NT_local.h"
13
14#include <aw_window.hxx>
15#include <aw_root.hxx>
16#include <aw_awar.hxx>
17#include <aw_msg.hxx>
18
19#include <awt_sel_boxes.hxx>
20#include <TreeCallbacks.hxx>
21
22#include <arb_progress.h>
23#include <arb_global_defs.h>
24#include <item_sel_list.h>
25
26#include <set>
27#include <map>
28
29#define TREE_COMPARE_PREFIX     "ad_tree/compare/"
30#define TREE_COMPARE_PREFIX_TMP "tmp/" TREE_COMPARE_PREFIX
31
32#define AWAR_TREE_COMPARE_LEFT   TREE_COMPARE_PREFIX_TMP "left"
33#define AWAR_TREE_COMPARE_RIGHT  TREE_COMPARE_PREFIX_TMP "right"
34
35#define AWAR_TREE_COMPARE_ACTION         TREE_COMPARE_PREFIX "action"
36#define AWAR_TREE_COMPARE_MIN_TAX_LEVELS TREE_COMPARE_PREFIX "taxdist"
37#define AWAR_TREE_COMPARE_WRITE_FIELD    TREE_COMPARE_PREFIX "field"
38
39enum Action { // uses same values as NT_mark_all_cb; see ../SL/TREEDISP/TreeCallbacks.cxx@MARK_MODE_LOWER_BITS
40    UNMARK = 0,
41    MARK   = 1,
42    INVERT = 2,
43};
44
45enum Target {
46    ALL,
47    TAX,
48    COMMON,
49    MISSING_LEFT,
50    MISSING_RIGHT,
51};
52
53static TreeNode *findParentGroup(TreeNode *node) {
54    TreeNode *parent_group = NULL;
55
56    while (!parent_group && node->father) {
57        node = node->father;
58        if (node->is_named_group()) {
59            parent_group = node;
60        }
61    }
62
63    return parent_group;
64}
65
66static int countTaxLevel(TreeNode *node) {
67    int       taxlevel     = node->is_leaf ? 0 : node->is_named_group();
68    TreeNode *parent_group = findParentGroup(node);
69    while (parent_group) {
70        ++taxlevel;
71        parent_group = findParentGroup(parent_group);
72    }
73    return taxlevel;
74}
75
76static int calcTaxDifference(TreeNode *g1, TreeNode *g2) {
77    // returns difference in taxonomy-levels
78    //
79    // difference defined such that:
80    //   diff("/A/B", "/A/B") == 0
81    //   diff("/A/B", "/A"  ) == 1
82    //   diff("/A/B", "/A/C") == 2
83    //   diff("/A/B/C", "/A/D/E") == 4
84    //   diff("/A/B/C", "/A/D/C") == 4
85    //   diff("/A/B/C", "/A/C") == 3
86
87    nt_assert(g1->is_named_group() && g2->is_named_group()); // has to be called with root-nodes of groups!
88
89    TreeNode *p1 = findParentGroup(g1);
90    TreeNode *p2 = findParentGroup(g2);
91
92    int taxdiff = 0;
93    if (p1) {
94        if (p2) {
95            int pdiff  = calcTaxDifference(p1, p2);
96            int p1diff = calcTaxDifference(p1, g2) + 1;
97            int p2diff = calcTaxDifference(g1, p2) + 1;
98
99            if (pdiff || strcmp(g1->name, g2->name) != 0) {
100                // if parent-taxonomy differs -> ignore names of g1/g2 -> diff=2
101                // if parent-taxonomy matches -> if names of g1 and g2 match -> no diff
102                //                               if names of g1 and g2 differ -> diff=2
103                pdiff += 2;
104            }
105
106            taxdiff = std::min(pdiff, std::min(p1diff, p2diff));
107        }
108        else {
109            taxdiff = calcTaxDifference(p1, g2) + 1;
110        }
111    }
112    else {
113        if (p2) {
114            taxdiff = calcTaxDifference(g1, p2) + 1;
115        }
116        else {
117            if (strcmp(g1->name, g2->name) != 0) { // logic similar to (p1 && p2) above
118                taxdiff = 2;
119            }
120        }
121    }
122
123    return taxdiff;
124}
125
126class SpeciesInTwoTrees {
127    TreeNode *tree1;
128    TreeNode *tree2;
129
130public:
131    SpeciesInTwoTrees()
132        : tree1(NULL),
133          tree2(NULL)
134    {}
135
136    void setSpecies(TreeNode *species, bool first) {
137        nt_assert(species->is_leaf);
138        if (first) {
139            nt_assert(!tree1);
140            tree1 = species;
141        }
142        else {
143            nt_assert(!tree2);
144            tree2 = species;
145        }
146    }
147
148    bool occursInBothTrees() const { return tree1 && tree2; }
149    int calcTaxDiffLevel() const {
150        TreeNode *parent_group1 = findParentGroup(tree1);
151        TreeNode *parent_group2 = findParentGroup(tree2);
152
153        int taxdiff = 0;
154
155        if (parent_group1) {
156            if (parent_group2) {
157                taxdiff = calcTaxDifference(parent_group1, parent_group2);
158            }
159            else {
160                taxdiff = countTaxLevel(parent_group1);
161            }
162        }
163        else {
164            if (parent_group2) {
165                taxdiff = countTaxLevel(parent_group2);
166            }
167            // else -> both outside any group -> no diff
168        }
169
170        return taxdiff;
171    }
172};
173
174typedef std::set<const char *, charpLess> NameSet;
175typedef std::map<const char *, SpeciesInTwoTrees, charpLess> TwoTreeMap;
176
177static void mapTree(TreeNode *node, TwoTreeMap& tmap, bool first) {
178    if (node->is_leaf) {
179        nt_assert(node->name);
180        tmap[node->name].setSpecies(node, first);
181    }
182    else {
183        mapTree(node->leftson, tmap, first);
184        mapTree(node->rightson, tmap, first);
185    }
186}
187
188static void mark_action(AW_window *aws, TREE_canvas *ntw, Target target) {
189    AW_root *aw_root = aws->get_root();
190
191    Action action = Action(aw_root->awar(AWAR_TREE_COMPARE_ACTION)->read_int());
192
193    arb_progress progress("Mark species");
194    if (target == ALL) {
195        NT_mark_all_cb(NULL, ntw, action);
196    }
197    else {
198        progress.subtitle("Loading trees");
199
200        const char *treename_left  = aw_root->awar(AWAR_TREE_COMPARE_LEFT)->read_char_pntr();
201        const char *treename_right = aw_root->awar(AWAR_TREE_COMPARE_RIGHT)->read_char_pntr();
202
203        GBDATA         *gb_main = ntw->gb_main;
204        GB_transaction  ta(gb_main);
205
206        GBDATA *gb_species_data = GBT_get_species_data(gb_main);
207
208        TreeNode *tree_left  = GBT_read_tree(gb_main, treename_left,  new SimpleRoot);
209        TreeNode *tree_right = GBT_read_tree(gb_main, treename_right, new SimpleRoot);
210
211        size_t missing   = 0;
212        size_t targetted = 0;
213        bool   had_error = false;
214
215        if (target == TAX) {
216            int min_tax_levels = atoi(aw_root->awar(AWAR_TREE_COMPARE_MIN_TAX_LEVELS)->read_char_pntr());
217
218            TwoTreeMap tmap;
219            mapTree(tree_left,  tmap, true);
220            mapTree(tree_right, tmap, false);
221
222            size_t commonSpeciesCount = 0;
223            for (TwoTreeMap::iterator s = tmap.begin(); s != tmap.end(); ++s) {
224                if (s->second.occursInBothTrees()) commonSpeciesCount++;
225            }
226
227            const char *fieldName    = prepare_and_get_selected_itemfield(aw_root, AWAR_TREE_COMPARE_WRITE_FIELD, gb_main, SPECIES_get_selector(), FIF_ALLOW_NONE);
228            bool        writeToField = fieldName;
229            GB_ERROR    error        = GB_incur_error();
230
231            if (!error) {
232                arb_progress subprogress("Comparing taxonomy info", commonSpeciesCount);
233                for (TwoTreeMap::iterator s = tmap.begin(); s != tmap.end() && !error; ++s) {
234                    const SpeciesInTwoTrees& species = s->second;
235
236                    if (species.occursInBothTrees()) {
237                        int taxDiffLevel = species.calcTaxDiffLevel();
238                        if (taxDiffLevel>min_tax_levels) {
239                            ++targetted;
240                            GBDATA *gb_species = GBT_find_species_rel_species_data(gb_species_data, s->first);
241                            if (!gb_species) {
242                                ++missing;
243                            }
244                            else {
245                                switch (action) {
246                                    case UNMARK: GB_write_flag(gb_species, 0);                         break;
247                                    case MARK:   GB_write_flag(gb_species, 1);                         break;
248                                    case INVERT: GB_write_flag(gb_species, !GB_read_flag(gb_species)); break;
249                                }
250                                if (writeToField) {
251                                    GBDATA *gb_field     = GBT_searchOrCreate_itemfield_according_to_changekey(gb_species, fieldName, SPECIES_get_selector().change_key_path);
252                                    if (!gb_field) error = GB_await_error();
253                                    if (!error) error    = GB_write_lossless_int(gb_field, taxDiffLevel);
254                                }
255                            }
256                        }
257                        subprogress.inc_and_check_user_abort(error);
258                    }
259                }
260            }
261            aw_message_if(error);
262            had_error = error;
263        }
264        else {
265            progress.subtitle("Intersecting tree members");
266
267            NameSet in_left;
268            NameSet in_right;
269            {
270                size_t   count_left, count_right;
271                GB_CSTR *names_left  = GBT_get_names_of_species_in_tree(tree_left,  &count_left);
272                GB_CSTR *names_right = GBT_get_names_of_species_in_tree(tree_right, &count_right);
273
274                for(size_t i= 0; i<count_left;  ++i) in_left .insert(names_left[i]);
275                for(size_t i= 0; i<count_right; ++i) in_right.insert(names_right[i]);
276
277                free(names_right);
278                free(names_left);
279            }
280
281            {
282                NameSet& in_one   = target == MISSING_LEFT ? in_right : in_left;
283                NameSet& in_other = target == MISSING_LEFT ? in_left : in_right;
284
285                for (NameSet::const_iterator i = in_one.begin(); i != in_one.end(); ++i) {
286                    bool is_in_other = in_other.find(*i) != in_other.end();
287                    bool is_target   = is_in_other == (target == COMMON);
288
289                    if (is_target) {
290                        ++targetted;
291                        GBDATA *gb_species = GBT_find_species_rel_species_data(gb_species_data, *i);
292                        if (!gb_species) {
293                            ++missing;
294                        }
295                        else {
296                            switch (action) {
297                                case UNMARK: GB_write_flag(gb_species, 0);                         break;
298                                case MARK:   GB_write_flag(gb_species, 1);                         break;
299                                case INVERT: GB_write_flag(gb_species, !GB_read_flag(gb_species)); break;
300                            }
301                        }
302                    }
303                }
304            }
305        }
306
307        if (!had_error) {
308            if (!targetted) {
309                aw_message("Warning: no species targetted");
310            }
311            else if (missing) {
312                aw_message(GBS_global_string("Warning: %zu targeted species could not be found\n"
313                                             "(might be caused by zombies in your trees)", missing));
314            }
315        }
316
317        destroy(tree_right);
318        destroy(tree_left);
319    }
320}
321
322void NT_create_compare_taxonomy_awars(AW_root *aw_root, AW_default props) {
323    char *currTree = aw_root->awar(AWAR_TREE_NAME)->read_string();
324
325    aw_root->awar_string(AWAR_TREE_COMPARE_LEFT,           currTree,          props);
326    aw_root->awar_string(AWAR_TREE_COMPARE_RIGHT,          currTree,          props);
327    aw_root->awar_int   (AWAR_TREE_COMPARE_ACTION,         MARK,              props);
328    aw_root->awar_string(AWAR_TREE_COMPARE_MIN_TAX_LEVELS, "0",               props);
329    aw_root->awar_string(AWAR_TREE_COMPARE_WRITE_FIELD,    NO_FIELD_SELECTED, props);
330
331    free(currTree);
332}
333
334AW_window *NT_create_compare_taxonomy_window(AW_root *aw_root, TREE_canvas *ntw) {
335    AW_window_simple *aws = new AW_window_simple;
336    aws->init(aw_root, "COMPARE_TAXONOMY", "Compare taxonomy");
337    aws->load_xfig("compare_taxonomy.fig");
338
339    aws->at("close");
340    aws->callback(AW_POPDOWN);
341    aws->create_button("CLOSE", "CLOSE", "C");
342
343    aws->at("help");
344    aws->callback(makeHelpCallback("compare_taxonomy.hlp"));
345    aws->create_button("HELP", "HELP", "H");
346
347    aws->at("action");
348    aws->create_toggle_field(AWAR_TREE_COMPARE_ACTION, NULL, "");
349    aws->insert_default_toggle("mark",   "m", MARK);
350    aws->insert_toggle        ("unmark", "u", UNMARK);
351    aws->insert_toggle        ("invert", "i", INVERT);
352    aws->update_toggle_field();
353
354    aws->at("all");       aws->callback(makeWindowCallback(mark_action, ntw, ALL));           aws->create_autosize_button("all",       "all species");
355    aws->at("tax");       aws->callback(makeWindowCallback(mark_action, ntw, TAX));           aws->create_autosize_button("tax",       "species with taxonomy changed");
356    aws->at("common");    aws->callback(makeWindowCallback(mark_action, ntw, COMMON));        aws->create_autosize_button("common",    "common species");
357    aws->at("missleft");  aws->callback(makeWindowCallback(mark_action, ntw, MISSING_LEFT));  aws->create_autosize_button("missleft",  "species missing in left tree");
358    aws->at("missright"); aws->callback(makeWindowCallback(mark_action, ntw, MISSING_RIGHT)); aws->create_autosize_button("missright", "species missing in right tree");
359
360    aws->at("levels");
361    aws->create_input_field(AWAR_TREE_COMPARE_MIN_TAX_LEVELS, 5);
362
363    create_itemfield_selection_button(aws, FieldSelDef(AWAR_TREE_COMPARE_WRITE_FIELD, ntw->gb_main, SPECIES_get_selector(), FIELD_FILTER_INT_WRITEABLE, "taxdiff-field", SF_ALLOW_NEW), "field");
364
365    aws->at("left");
366    awt_create_TREE_selection_list(ntw->gb_main, aws, AWAR_TREE_COMPARE_LEFT, true);
367
368    aws->at("right");
369    awt_create_TREE_selection_list(ntw->gb_main, aws, AWAR_TREE_COMPARE_RIGHT, true);
370
371    return aws;
372}
373
374
Note: See TracBrowser for help on using the repository browser.