sdsl/include/sdsl/louds_tree.hpp

Go to the documentation of this file.

/* sdsl - succinct data structures library
    Copyright (C) 2012 Simon Gog
*/
#ifndef INCLUDED_SDSL_LOUDS_TREE
#define INCLUDED_SDSL_LOUDS_TREE

#include "int_vector.hpp"
#include "util.hpp"
#include <ostream>

namespace sdsl
{

class louds_node
{
    public:
        typedef bit_vector::size_type size_type;
    private:
        size_type m_nr;         // node number
        size_type m_pos;  // position in the LOUDS
    public:
        const size_type& nr;
        const size_type& pos;

        louds_node(size_type f_nr=0, size_type f_pos=0):m_nr(f_nr), m_pos(f_pos),nr(m_nr),pos(m_pos) {}

        bool operator==(const louds_node& v)const {
            return m_nr == v.m_nr and m_pos ==v.m_pos;
        }

        bool operator!=(const louds_node& v)const {
            return !(v==*this);
        }
};

std::ostream& operator<<(std::ostream& os, const louds_node& v);


template<class BitVector = bit_vector, class SelectSupport1 = typename BitVector::select_1_type, class SelectSupport0 = typename BitVector::select_0_type>
class louds_tree
{
    public:
        typedef bit_vector::size_type   size_type;
        typedef louds_node                              node_type;
        typedef BitVector                               bit_vector_type;
        typedef SelectSupport1                  select_1_type;
        typedef SelectSupport0                  select_0_type;

    private:
        bit_vector_type m_bv;                   // bit vector for the LOUDS sequence
        select_1_type   m_bv_select1;   // select support for 1-bits on m_bv
        select_0_type   m_bv_select0;   // select support for 0-bits on m_bv
    public:
        const bit_vector_type& bv;      // const reference to the LOUDS sequence

        template<class Cst, class CstBfsIterator>
        louds_tree(const Cst& cst, const CstBfsIterator begin, const CstBfsIterator end):m_bv(), m_bv_select1(), m_bv_select0(), bv(m_bv) {
            bit_vector tmp_bv(4*cst.leaves_in_the_subtree(*begin) , 0); // resize the bit_vector to the maximal
            // possible size 2*2*#leaves in the tree
            size_type pos = 0;
            for (CstBfsIterator it = begin; it != end;) {
                tmp_bv[pos++] = 1;
                size_type size = it.size();
                ++it;
                pos += it.size()+1-size;
            }
            tmp_bv.resize(pos);
            util::assign(m_bv, tmp_bv);
            util::init_support(m_bv_select1, &m_bv);
            util::init_support(m_bv_select0, &m_bv);
        }

        node_type root() const {
            return louds_node(0, 0);
        }

        size_type nodes()const {
            return m_bv.size()/2;
        }


        bool is_leaf(const node_type& v) const {
            // node is the last leaf        or  has no children, so m_bv[v.pos]==1
            return (v.pos+1 == m_bv.size()) or m_bv[v.pos+1];
        }


        size_type degree(const node_type& v) const {
            if (is_leaf(v)) {  // handles boundary cases
                return 0;
            }
            // position of the next node  - node position - 1
            return m_bv_select1(v.nr+2) - v.pos - 1;
        }


        node_type child(const node_type& v, size_type i)const {
            size_type pos   = v.pos+i; // go to the position of the child's zero
            // (#bits = pos+1) - (#1-bits = v.nr+1)
            size_type zeros = pos+1 - (v.nr+1);
            return louds_node(zeros, m_bv_select1(zeros+1));
        }

        node_type parent(const node_type& v)const {
            if (v == root()) {
                return root();
            }
            size_type zero_pos   = m_bv_select0(v.nr);
            size_type parent_nr  = (zero_pos+1) - v.nr - 1;
            return node_type(parent_nr, m_bv_select1(parent_nr+1));
        }

        size_type id(const node_type& v)const {
            return v.nr;
        }
};

}// end namespace sdsl

#endif // end file