sdsl/include/sdsl/csa_uncompressed.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_CSA_UNCOMPRESSED
#define INCLUDED_SDSL_CSA_UNCOMPRESSED

#include "sdsl_concepts.hpp"
#include "suffixarray_helper.hpp"
#include "int_vector.hpp"
#include "algorithms.hpp"
#include "iterators.hpp"
#include "util.hpp"
#include "testutils.hpp"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring> // for strlen
#include <iomanip>
#include <iterator>


namespace sdsl
{


class csa_uncompressed
{
    public:
        typedef uint64_t                                                                                         value_type;    // STL Container requirement
        typedef random_access_const_iterator<csa_uncompressed>           const_iterator;// STL Container requirement
        typedef const_iterator                                                                           iterator;              // STL Container requirement
        typedef const value_type                                                                         const_reference;
        typedef const_reference                                                                          reference;
        typedef const_reference*                                                                         pointer;
        typedef const pointer                                                                            const_pointer;
        typedef int_vector<>::size_type                                                          size_type;             // STL Container requirement
        typedef size_type                                                                                        csa_size_type;
        typedef ptrdiff_t                                                                                        difference_type; // STL Container requirement
        typedef psi_of_sa_and_isa<csa_uncompressed>                                      psi_type;
        typedef bwt_of_csa_psi<csa_uncompressed>                                         bwt_type;
        typedef const unsigned char*                                                             pattern_type;
        typedef unsigned char                                                                            char_type;
        typedef int_vector<>                                                                             sa_sample_type;
        typedef int_vector<>                                                                             isa_sample_type;

        typedef csa_tag                                                                                         index_category;

        enum { sa_sample_dens = 1,
               isa_sample_dens = 1
             };

        friend class psi_of_sa_and_isa<csa_uncompressed>;
        friend class bwt_of_csa_psi<csa_uncompressed>;
    private:
        sa_sample_type  m_sa;  // vector for suffix array values
        isa_sample_type m_isa; // vector for inverse suffix array values
        psi_type                m_psi; // wrapper class for psi function values
        bwt_type                m_bwt; // wrapper class for the BWT
        int_vector<8>   m_char2comp;
        int_vector<8>   m_comp2char;
        int_vector<64>  m_C;
        uint16_t                m_sigma;

        void construct();
        void copy(const csa_uncompressed& csa);
    public:
        const int_vector<8>& char2comp;
        const int_vector<8>& comp2char;
        const int_vector<64>& C;
        const uint16_t& sigma;
        const psi_type& psi;
        const bwt_type& bwt;
        const sa_sample_type& sa_sample;
        const isa_sample_type& isa_sample;

        csa_uncompressed():char2comp(m_char2comp), comp2char(m_comp2char), C(m_C), sigma(m_sigma) ,psi(m_psi), bwt(m_bwt), sa_sample(m_sa), isa_sample(m_isa) {
            util::assign(m_C, int_vector<64>(257));
            util::assign(m_char2comp, int_vector<8>(256));
            util::assign(m_comp2char, int_vector<8>(256));
        }
        ~csa_uncompressed() {}
        csa_uncompressed(const csa_uncompressed& csa):char2comp(m_char2comp), comp2char(m_comp2char), C(m_C), sigma(m_sigma), psi(m_psi), bwt(m_bwt), sa_sample(m_sa), isa_sample(m_isa) {
            copy(csa);
        }

        template<typename RandomAccessContainer>
        csa_uncompressed(const RandomAccessContainer& sa, const unsigned char* str);


        csa_uncompressed(const unsigned char* str);

        template<uint8_t int_width, class size_type_class, class size_type_class_1>
        csa_uncompressed(int_vector_file_buffer<8, size_type_class>& text_buf,
                         int_vector_file_buffer<int_width, size_type_class_1>& sa_buf):char2comp(m_char2comp),
            comp2char(m_comp2char), C(m_C), sigma(m_sigma) ,psi(m_psi), bwt(m_bwt), sa_sample(m_sa), isa_sample(m_isa) {
            text_buf.reset(); sa_buf.reset();
            size_type n = text_buf.int_vector_size;
            algorithm::set_text<csa_uncompressed>(text_buf, n, m_C, m_char2comp, m_comp2char, m_sigma);
            algorithm::set_sa_and_isa_samples<csa_uncompressed>(sa_buf, m_sa, m_isa);
            m_psi = psi_type(this);
            m_bwt = bwt_type(this);
        }

        csa_uncompressed(tMSS& file_map, const std::string& dir, const std::string& id):char2comp(m_char2comp),
            comp2char(m_comp2char), C(m_C), sigma(m_sigma), psi(m_psi), bwt(m_bwt), sa_sample(m_sa), isa_sample(m_isa) {
            construct(file_map, dir, id);
        }


        void construct(tMSS& file_map, const std::string& dir, const std::string& id) {
            int_vector_file_buffer<8> text_buf(file_map["text"].c_str());
            int_vector_file_buffer<>  sa_buf(file_map["sa"].c_str());
            size_type n = text_buf.int_vector_size;
            algorithm::set_text<csa_uncompressed>(text_buf, n, m_C, m_char2comp, m_comp2char, m_sigma);
            algorithm::set_sa_and_isa_samples<csa_uncompressed>(sa_buf, m_sa, m_isa);
            m_psi = psi_type(this);
            m_bwt = bwt_type(this);
            write_R_output("csa", "store ISA","begin",1,0);
            if (!util::store_to_file(m_isa, (dir+"isa_"+id).c_str(), true)) {
                throw std::ios_base::failure("#csa_uncompressed: Cannot store ISA to file system!");
            } else {
                file_map["isa"] = dir+"isa_"+id;
            }
            write_R_output("csa", "store ISA","end",1,0);
        }



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


        static size_type max_size() {
            return int_vector<>::max_size();
        }


        bool empty()const {
            return m_sa.empty();
        }


        void swap(csa_uncompressed& csa);


        const_iterator begin()const;


        const_iterator end()const;


        inline value_type operator[](size_type i)const {
            return m_sa[i];
        }


        inline value_type operator()(size_type i)const {
            return m_isa[i];
        }


        csa_uncompressed& operator=(const csa_uncompressed& csa);


        bool operator==(const csa_uncompressed& csa)const;


        bool operator!=(const csa_uncompressed& csa)const;


        size_type serialize(std::ostream& out) const;


        void load(std::istream& in);

        size_type get_sample_dens()const {
            return 1;
        }


        size_type rank_bwt(size_type i, const unsigned char c) const;


        size_type select_bwt(size_type i, const unsigned char c) const;
};


template<typename RandomAccessContainer>
csa_uncompressed::csa_uncompressed(const RandomAccessContainer& sa, const unsigned char* str):char2comp(m_char2comp), comp2char(m_comp2char),C(m_C), sigma(m_sigma), psi(m_psi), bwt(m_bwt), sa_sample(m_sa), isa_sample(m_isa)
{
    size_type n = 1;
    if (str != NULL) {
        n = strlen((const char*)str);
    }
    algorithm::set_text<csa_uncompressed>(str, n+1, m_C, m_char2comp, m_comp2char, m_sigma);
//      assert(sa.size() == n+1);
    m_sa = int_vector<>(n+1, 0, bit_magic::l1BP(n+1)+1);
    for (size_type i=0; i<n+1; ++i)
        m_sa[i] = sa[i];
    construct();
    if (n+1 > 0 and n+1 != size())
        throw std::logic_error(util::demangle(typeid(this).name())+": text size differ with sa size!");
}


} // end namespace sdsl

#endif