sdsl/include/sdsl/cst_iterators.hpp

Go to the documentation of this file.

/* sdsl - succinct data structures library
    Copyright (C) 2009 Simon Gog

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses/ .
*/
#ifndef INCLUDED_SDSL_CST_ITERATORS
#define INCLUDED_SDSL_CST_ITERATORS

namespace sdsl
{


// TODO: implement operator--
template<class Cst, uint32_t cache_size=128>
class cst_dfs_const_forward_iterator: public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
{
    public:
        typedef typename Cst::node_type value_type;
        typedef const value_type const_reference;
        typedef typename Cst::size_type size_type;
        typedef cst_dfs_const_forward_iterator<Cst> iterator;
        typedef typename Cst::node_type node_type;
    private:
        const Cst* m_cst;
        node_type m_v;
        bool     m_visited;
        bool     m_valid;
        node_type* m_stack_cache;
        uint32_t m_stack_size;


        inline node_type parent() {
            --m_stack_size; // decrease stack size
            if (m_stack_cache != NULL and m_stack_size < cache_size) {
                return m_stack_cache[m_stack_size];
            } else
                return m_cst->parent(m_v);
        }

        inline node_type first_child() {
            if (m_stack_cache != NULL and m_stack_size < cache_size)   // push node to the stack
                m_stack_cache[ m_stack_size ] = m_v;
            m_stack_size++;
            return m_cst->ith_child(m_v, 1);
        }

    public:

        cst_dfs_const_forward_iterator():m_cst(NULL),m_visited(false),m_valid(false), m_stack_cache(NULL)
        {}

        cst_dfs_const_forward_iterator(const Cst* cst, const value_type node, bool visited=false, bool valid=true):m_visited(visited), m_valid(valid), m_stack_cache(NULL) {
            m_cst = cst;
            m_v = node;
            if (m_cst == NULL) {
                m_valid = false;
            } else if (node == m_cst->root() and !visited and valid) { // if the iterator equal cst.begin()
                m_stack_cache = new node_type[cache_size];
                m_stack_size  = 0;
//                      std::cerr<<"#creating stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
            }
        }

//      cst_dfs_const_forward_iterator(const cst_dfs_const_forward_iterator &it):m_cst(it.cst),m_v(it.m_v),m_valid(m_valid), m_stack_cache(NULL),m_stack_size(0){
//      }

        ~cst_dfs_const_forward_iterator() {
            if (m_stack_cache != NULL) {
//                      std::cerr<<"#deleting stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
                delete [] m_stack_cache;
            }
        }

        uint8_t visit()const {
            return 1+(uint8_t)m_visited;
        }

        void skip_subtree() {
            if (m_valid) {
                if (!m_visited) {
                    m_visited = true;
                }
            }
        }

        const_reference operator*()const {
            return m_v;
        }

        iterator& operator++() {
            if (!m_valid)
                return *this;
            if (m_v == m_cst->root() and m_visited) {
                m_valid = false;
                return *this;
            }
            value_type w;
            if (!m_visited) { // go down, if possible
                if (m_cst->is_leaf(m_v)) {
                    w = m_cst->sibling(m_v);  // determine sibling of leaf v
                    if (w == m_cst->root()) { // if there exists no right sibling of the leaf v
//                                      w = m_cst->parent(m_v);
                        w = parent();
                        m_visited = true; // go up
                    }
                } else { // v is not a leaf => go down the tree
                    w = first_child();
                }
            } else { //
                w = m_cst->sibling(m_v);
                if (w == m_cst->root()) {   // if there exists no rigth sibling
                    w = parent();
                } else {
                    m_visited = false;
                }
            }
            m_v = w;
            return *this;
        }

        void operator++(int x) {
            ++(*this);
        }

        bool operator==(const iterator& it)const {
            return (it.m_visited == m_visited) // visited status is equal
                   and (it.m_valid == m_valid) // valid status is equal => for end() iterator
                   and (it.m_v == m_v)    // nodes are equal
                   and (it.m_cst == m_cst);  // iterator belongs to the same cst
        }

        bool operator!=(const iterator& it)const {
            return !(*this==it);
        }

};

template<class Cst>
class cst_bottom_up_const_forward_iterator: public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
{
    public:
        typedef typename Cst::node_type value_type;
        typedef const value_type const_reference;
        typedef typename Cst::size_type size_type;
        typedef cst_bottom_up_const_forward_iterator<Cst> iterator;
    private:
        const Cst* m_cst;
        typename Cst::node_type m_v;
        bool     m_valid;
    public:

        cst_bottom_up_const_forward_iterator():m_cst(NULL),m_valid(false) {}

        cst_bottom_up_const_forward_iterator(const Cst* cst, const value_type node, bool valid=true):m_valid(valid) {
            m_cst = cst;
            m_v = node;
            if (m_cst == NULL)
                m_valid = false;
        }

        const_reference operator*()const {
            return m_v;
        }

        iterator& operator++() {
            if (!m_valid)
                return *this;
            if (m_v == m_cst->root()) {
                m_valid = false;
                return *this;
            }
            value_type w = m_cst->sibling(m_v);
            if (w == m_cst->root()) {   // if no next right sibling exist
                m_v = m_cst->parent(m_v);    // go to parent
            } else { // if next right sibling exist
                m_v = m_cst->leftmost_leaf_in_the_subtree(w);   // go to leaftmost leaf in the subtree of w
            }
            return *this;
        }

        iterator operator++(int x) {
            iterator it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const iterator& it)const {
            return (it.m_valid == m_valid) // valid status is equal => for end() iterator
                   and (it.m_v == m_v)    // nodes are equal
                   and (it.m_cst == m_cst);  // iterator belongs to the same cst
        }

        bool operator!=(const iterator& it)const {
            return !(*this==it);
        }

};


template<class Cst, class Queue = std::queue<typename Cst::node_type> >
class cst_bfs_iterator: public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
{
    public:
        typedef typename Cst::node_type                 value_type;
        typedef const value_type                                const_reference;
        typedef typename Cst::size_type                 size_type;
        typedef cst_bfs_iterator<Cst, Queue>    iterator;
        typedef Queue                                                   queue_type;
    private:
        const Cst*      m_cst;   // Pointer to the cst.
        queue_type      m_queue; //
        bool            m_valid; // State of the iterator.

    public:


        cst_bfs_iterator(const Cst* cst, const value_type node, bool valid=true, bool end_it=false) {
            m_cst = cst;
            m_valid = valid;
            if (m_cst != NULL and !end_it) {
                m_queue.push(node);
            }
        }

        size_type size()const {
            return m_queue.size();
        }

        const_reference operator*()const {
            return m_queue.front();
        }

        iterator& operator++() {
            if (!m_valid)
                return *this;
            if (m_queue.empty()) {
                m_valid = false;
                return *this;
            }
            value_type v = m_queue.front();
            m_queue.pop();
            value_type child = m_cst->ith_child(v, 1);
            while (m_cst->root() != child) {
                m_queue.push(child);
                child = m_cst->sibling(child);
            }
            return *this;
        }

        iterator operator++(int x) {
            iterator it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const iterator& it)const {
            if (m_queue.size() != it.m_queue.size()) {   // if the queue size is different
                return false;                            // the state of the to iterator are different
            }
            if (m_queue.empty()) {  // if the queue is empty, we have to check if they are valid and
                return it.m_valid == m_valid and it.m_cst == m_cst; // belong to the same cst
            }
            return (it.m_valid == m_valid) // valid status is equal => for end() iterator
                   and (it.m_cst == m_cst) // iterator belongs to the same cst
                   and (it.m_queue.front() == m_queue.front())  // front element and
                   and (it.m_queue.back() == m_queue.back());  //  back element are the same.
        }

        bool operator!=(const iterator& it)const {
            return !(*this==it);
        }

};


} // end namespace sdsl

#endif