#ifndef INCLUDED_PERMUTED_LCP_HPP
#define INCLUDED_PERMUTED_LCP_HPP

#include "definitions.hpp"
#include "sparse_sd_vector.hpp"


namespace bri {

template<class sparse_bitvector_t = sparse_sd_vector>
class permuted_lcp 
{
public:
    permuted_lcp() {}

    /*
     * constructor with cache_config.
     * assume text and SA and ISA are cached by the config.
     */
    permuted_lcp(sdsl::cache_config& cc)
    {
        // construct ISA
        //sdsl::int_vector_buffer<> isa(sdsl::cache_file_name(sdsl::conf::KEY_ISA, cc));
        sdsl::int_vector<> isa;
        sdsl::load_from_file(isa, sdsl::cache_file_name(sdsl::conf::KEY_ISA, cc));

        // construct LCP
        sdsl::construct_lcp_kasai<8>(cc);
        //sdsl::int_vector_buffer<> lcp(sdsl::cache_file_name(sdsl::conf::KEY_LCP, cc));
        
        sdsl::int_vector<> lcp;
        sdsl::load_from_file(lcp, sdsl::cache_file_name(sdsl::conf::KEY_LCP, cc));
       
        n = isa.size();

        std::vector<bool> S(2*n+1,false);
        S[0] = true;

        ulint isa_val = isa[0];
        ulint lcp_prev = lcp[isa_val];
        ulint lcp_now;
        ulint pos = lcp_prev + 1;

        for (ulint i = 1; i < n; ++i)
        {
            S[pos] = true;
            isa_val = isa[i];
            lcp_now = lcp[isa_val];
            pos += lcp_now + 2;
            pos -= lcp_prev;
            lcp_prev = lcp_now;
        }
        S[pos] = true;

        u = pos + 1;
        std::vector<bool> ones_bv(u,false);
        std::vector<bool> zeros_bv(u,false);

        // generate run length encoding ones&zeros from S
        // S: unary encoding of j + PLCP[j]
        {
            bool bit_1 = true; // tell if we are counting 1 bits
            ulint cont_1 = 0, cont_0 = 0; // continuous number of 1 bits & 0 bits

            for (ulint i = 0; i < u; ++i)
            {
                if (S[i])
                {
                    if (bit_1)
                    {
                        cont_1++;
                    } else {
                        bit_1 = true;
                        cont_1++;
                        zeros_bv[cont_0-1] = true;
                    }
                } 
                else 
                {
                    if (bit_1)
                    {
                        bit_1 = false;
                        cont_0++;
                        ones_bv[cont_1-1] = true;
                    } else {
                        cont_0++;
                    }
                }
            }
            if (bit_1) ones_bv[cont_1-1] = true;
            else zeros_bv[cont_0-1] = true;
        }

        ones = sparse_bitvector_t(ones_bv);
        zeros = sparse_bitvector_t(zeros_bv);

        sdsl::remove(sdsl::cache_file_name(sdsl::conf::KEY_LCP, cc));

    }

    /*
     * get PLCP[i]
     */
    ulint operator[](size_t i)
    {
        assert(i < n);
        ulint rank_0 = ones.rank(i+1);
        if (rank_0 > 0)
        {
            size_t res = zeros.select(rank_0-1) - i + 1;
            return res;
        }
        return 0;
    }

    ulint get_value(size_t i)
    {
        return operator[](i);
    }

    /*
     * serialize PLCP to the ostream
     */
    ulint serialize(std::ostream& out)
    {
        ulint w_bytes = 0;

        out.write((char*)&n,sizeof(n));
        out.write((char*)&u,sizeof(u));

        w_bytes += sizeof(n) + sizeof(u);

        if (n == 0) return w_bytes;

        w_bytes += ones.serialize(out);
        w_bytes += zeros.serialize(out);

        return w_bytes;
    }

    /*
     * load PLCP from the istream
     */
    void load(std::istream& in)
    {
        in.read((char*)&n, sizeof(n));
        in.read((char*)&u, sizeof(u));

        if (n == 0) return;

        ones.load(in);
        zeros.load(in);
    }

    ulint print_space()
    {
        ulint tot_bytes = 0;

        std::ofstream out("/dev/null");
        std::cout << "space for permuted_lcp:" << std::endl;

        auto bytes = ones.serialize(out);
        tot_bytes += bytes;
        std::cout << "- bitvector ones: " << bytes << " bytes" << std::endl;

        bytes = zeros.serialize(out);
        tot_bytes += bytes;
        std::cout << "- bitvector zeros: " << bytes << " bytes" << std::endl;

        return tot_bytes;
    }

    ulint get_space()
    {
        ulint tot_bytes = 0;

        std::ofstream out("/dev/null");

        tot_bytes += ones.serialize(out);
        tot_bytes += zeros.serialize(out);

        return tot_bytes;
    }

    ulint size()
    {
        return n;
    }

private:

    // length of LCP
    ulint n = 0;

    // length of ones & zeros
    ulint u = 0;

    // run length encoded PLCP representation
    sparse_bitvector_t ones;
    sparse_bitvector_t zeros;

};

};

#endif /* INCLUDED_PERMUTED_LCP_HPP */