// ============================================================= //
//                                                               //
//   File      : GroupIterator.hxx                               //
//   Purpose   : Iterate over all groups of a tree               //
//                                                               //
//   Coded by Ralf Westram (coder@reallysoft.de) in March 2017   //
//   http://www.arb-home.de/                                     //
//                                                               //
// ============================================================= //

#ifndef GROUPITERATOR_HXX
#define GROUPITERATOR_HXX

#ifndef TREENODE_H
#include <TreeNode.h>
#endif

class GroupIterator {
    // This iterates over all clades shown in a tree.
    // i.e. if a normal and a keeled group fall together, the iterator only stops once!
    //
    // Bug?: does not stop at keeled leaf groups
    // (better leave as is: currently only stops at inner nodes)

    ARB_edge edge;
    bool     reverse;

    inline bool at_group() const {
        return
            edge.get_type() != EDGE_TO_ROOT &&
            !edge.dest()->is_leaf() &&
            edge.dest()->is_clade();
    }

    void inc() {
        ARB_edge start(edge);
        do edge = edge.counter_previous();
        while (!at_group() && start != edge);
    }
    void dec() {
        ARB_edge start(edge);
        do edge = edge.counter_next();
        while (!at_group() && start != edge);
    }

public:
    // forward iterator
    // * starts with topmost and "rootmost" groups (i.e. child groups follow parent groups)
    //
    // reverse iterator
    // * start with lowermost and "leafmost" groups (i.e. parent groups follow child groups)
    //
    // if 'start' node is a group => iterator will point to that group (after construction).
    // Otherwise the iterator automatically increments to the "next" group.

    GroupIterator(AP_tree *start, bool forward = true) :
        edge(start->father
             ? parentEdge(start).inverse()
             : ARB_edge(start->get_rightson(), start->get_leftson(), ROOT_EDGE)),
        reverse(!forward)
    {
        td_assert(implicated(!start->is_leaf() && start->is_clade(),
                             at_group() && node() == start));
        if (!at_group()) next();
    }

    GroupIterator& next() { reverse ? inc() : dec(); return *this; }
    GroupIterator& previous() { reverse ? dec() : inc(); return *this; }

    bool valid() const { return at_group(); } // false if GroupIterator created on tree w/o groups

    AP_tree *node() const {
        td_assert(valid());
        return DOWNCAST(AP_tree*, edge.dest());
    }

    int get_clade_level() const {
        td_assert(valid());
        return node()->calc_clade_level(); // brute-force (maintain inside GroupIterator?)
    }
};


#else
#error GroupIterator.hxx included twice
#endif // GROUPITERATOR_HXX