sdsl/include/sdsl/rmq_succinct_sada.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_RMQ_SUCCINCT_SADA
#define INCLUDED_SDSL_RMQ_SUCCINCT_SADA

#include "rmq_support.hpp"
#include "int_vector.hpp"
#include "algorithms_for_compressed_suffix_trees.hpp"
#include "bp_support_sada.hpp"
#include "rank_support_v.hpp"
#include "select_support_mcl.hpp"
#include "util.hpp"

namespace sdsl
{


template<bool Minimum = true, class Bp_support = bp_support_sada<256, 32, rank_support_v5<>, select_support_dummy>, 
             class Rank_support10 = rank_support_v<10,2>, class Select_support10 = select_support_mcl<10,2> >
class rmq_succinct_sada;

template<class Bp_support = bp_support_sada<256, 32, rank_support_v5<>, select_support_dummy>, 
             class Rank_support10 = rank_support_v<10,2>, class Select_support10 = select_support_mcl<10,2> >
struct range_maximum_support_sada {
    typedef rmq_succinct_sada<false, Bp_support, Rank_support10, Select_support10> type;
};


template<bool Minimum, class Bp_support, class Rank_support10, class Select_support10>
class rmq_succinct_sada
{
        bit_vector                                      m_ect_bp;                       
        Bp_support                                      m_ect_bp_support;       
        Rank_support10                          m_ect_bp_rank10;                
        Select_support10                        m_ect_bp_select10;      

    public:
        typedef typename bit_vector::size_type size_type;
        typedef typename bit_vector::size_type value_type;

        typedef Bp_support                      bp_support_type;
        typedef Rank_support10          rank_support10_type;
        typedef Select_support10        select_support10_type;

        const bit_vector&                ect_bp;
        const Bp_support&                ect_bp_support;
        const Rank_support10&   ect_bp_rank10;
        const Select_support10& ect_bp_select10;

    private:

        typedef rmq_succinct_sct<Minimum> rmq_construct_helper_type;

        void _construct_bp_of_extended_cartesian_tree(size_type l, size_type r, size_type& bp_cnt, const rmq_construct_helper_type& rmq_helper) {
            if (r==(size_type)-1 or l > r)
                return;
            m_ect_bp[bp_cnt++] = 1; // write beginning of inner node
            size_type m = rmq_helper(l, r);
            _construct_bp_of_extended_cartesian_tree(l, m-1, bp_cnt, rmq_helper);
            m_ect_bp[bp_cnt++] = 1; // write leaf
            m_ect_bp[bp_cnt++] = 0;
            _construct_bp_of_extended_cartesian_tree(m+1, r, bp_cnt, rmq_helper);
            m_ect_bp[bp_cnt++] = 0; // write end of inner node
            assert(bp_cnt <= m_ect_bp.size());
        }

                template<class RandomAccessContainer>
        void construct(const RandomAccessContainer* v) {
            if (v == NULL) {
                m_ect_bp = bit_vector(0); m_ect_bp_support = Bp_support();
                m_ect_bp_rank10 = Rank_support10(); m_ect_bp_select10 = Select_support10();
            } else {
                rmq_construct_helper_type rmq_helper(v);
                m_ect_bp.resize(4*v->size());
                size_type bp_cnt=0;
                _construct_bp_of_extended_cartesian_tree((size_type)0, v->size()-1, bp_cnt, rmq_helper);
                assert(bp_cnt == 4*v->size());
                m_ect_bp_support = Bp_support(&m_ect_bp);
                util::init_support(m_ect_bp_rank10, &m_ect_bp);
                util::init_support(m_ect_bp_select10, &m_ect_bp);
            }
        }

        void copy(const rmq_succinct_sada& rm) {
            m_ect_bp = rm.m_ect_bp;
            m_ect_bp_support = rm.m_ect_bp_support;
            m_ect_bp_support.set_vector(&m_ect_bp);
            m_ect_bp_rank10 = rm.m_ect_bp_rank10;
            m_ect_bp_rank10.set_vector(&m_ect_bp);
            m_ect_bp_select10 = rm.m_ect_bp_select10;
            m_ect_bp_select10.set_vector(&m_ect_bp);
        }

    public:
        rmq_succinct_sada():ect_bp(m_ect_bp), ect_bp_support(m_ect_bp_support), ect_bp_rank10(m_ect_bp_rank10), ect_bp_select10(m_ect_bp_select10) {}

                template<class RandomAccessContainer>
        rmq_succinct_sada(const RandomAccessContainer* v=NULL):ect_bp(m_ect_bp), ect_bp_support(m_ect_bp_support), ect_bp_rank10(m_ect_bp_rank10), ect_bp_select10(m_ect_bp_select10) {
            construct(v);
        }

        rmq_succinct_sada(const rmq_succinct_sada& rm):ect_bp(m_ect_bp), ect_bp_support(m_ect_bp_support), ect_bp_rank10(m_ect_bp_rank10), ect_bp_select10(m_ect_bp_select10) {
            if (this != &rm) { // if v is not the same object
                copy(rm);
            }
        }

        ~rmq_succinct_sada() { }

        rmq_succinct_sada& operator=(const rmq_succinct_sada& rm) {
            if (this != &rm) {
                copy(rm);
            }
            return *this;
        }

        void swap(const rmq_succinct_sada& rm) {
            m_ect_bp.swap(rm.m_ect_bp);
                        util::swap_support(m_ect_bp_support, rm.m_ect_bp_support, 
                                                  &m_ect_bp, &(rm.m_ect_bp));
                        util::swap_support(m_ect_bp_rank10, rm.m_ect_bp_rank10, 
                                                  &m_ect_bp, &(rm.m_ect_bp));
                        util::swap_support(m_ect_bp_select10, rm.m_ect_bp_select10,
                                                  &m_ect_bp, &(rm.m_ect_bp));
        }


        size_type operator()(const size_type l, const size_type r)const {
            assert(l <= r); assert(r < size());
            if (l==r)
                return l;
            size_type x         = m_ect_bp_select10(l+1);
            size_type y         = m_ect_bp_select10(r+1);
            size_type z         = m_ect_bp_support.rmq(x, y);
            size_type f         = z + 1 - 2*(m_ect_bp[z]);
            return m_ect_bp_rank10(f-1);
        }

        size_type size()const {
            return m_ect_bp.size()/4;
        }

        size_type serialize(std::ostream& out, structure_tree_node* v=NULL, std::string name="")const {
                structure_tree_node* child = structure_tree::add_child(v, name, util::class_name(*this));
            size_type written_bytes = 0;
            written_bytes += m_ect_bp.serialize(out, child, "ect_bp");
            written_bytes += m_ect_bp_support.serialize(out, child, "ect_bp_support");
            written_bytes += m_ect_bp_rank10.serialize(out, child, "ect_bp_rank10");
            written_bytes += m_ect_bp_select10.serialize(out, child, "ect_bp_select10");
                structure_tree::add_size(child, written_bytes);
            return written_bytes;
        }

        void load(std::istream& in) {
            m_ect_bp.load(in);
            m_ect_bp_support.load(in, &m_ect_bp);
            m_ect_bp_rank10.load(in, &m_ect_bp);
            m_ect_bp_select10.load(in, &m_ect_bp);
        }
};


}


#endif