static_assert(Lower <= Upper, "symbol_range: invalid bounds");

/// Underlying symbol type

using value_type = CharT;

/// Full amount of symbols in range

constexpr static size_t length = Upper - Lower + 1ULL;

constexpr static value_type lower = Lower; // begin-of-range character

constexpr static value_type upper = Upper; // end-of-range character

using io_value_type = typename IODict::value_type;

using pack_value_type = typename PackDict::value_type;

using phrase_t = phrase_template <io_value_type>;

using encode_dict_t = encode_dict_template <io_value_type>;

using decode_dict_t = decode_dict_template <io_value_type>;

/// Allowed bits amount to encode single packed symbol

constexpr static size_t bit_capacity = log2_floor(PackDict::length);

static_assert(bit_capacity <= CHAR_BIT * sizeof(size_t),

"lzw_codec: PackDict is too large to be packed by size_t codes");

static_assert(PackDict::length >= log2_ceil(IODict::length),

"lzw_codec: PackDict is too small even for default IODict encoding");

/// @returns cached copy of encoding dictionary

static encode_dict_t encode_dict() {

static const encode_dict_t d_ = []{

encode_dict_t dict;

for(size_t code = 0; code < IODict::length; ++code)

dict.emplace(std::piecewise_construct,

std::forward_as_tuple(1, IODict::symbol_by_index(code)),

std::forward_as_tuple(code));

return dict;

}();

return d_;

}

/// @returns cached copy of decoding dictionary

static decode_dict_t decode_dict() {

static const decode_dict_t d_ = []{

decode_dict_t dict; dict.reserve(IODict::length);

for(size_t code = 0; code < IODict::length; ++code)

dict.emplace_back(1, IODict::symbol_by_index(code));

return dict;

}();

return d_;

}

/// @pre: bit_depth <= log2(size_t)

/// @pre: bit_depth <= 2^bit_capacity

template<class OutputIt>

static OutputIt pack_bits(codes_vec const& src, OutputIt d_first, size_t bit_depth) {

const size_t bits_needed = bit_depth*src.size();

const size_t output_symbols = (bits_needed - 1)/bit_capacity + 1; // ceil rounding

const size_t dead_bits = output_symbols*bit_capacity - bits_needed; // padding bits

*d_first++ = PackDict::symbol_by_index(bit_depth);

*d_first++ = PackDict::symbol_by_index(dead_bits);

size_t symbol_done = 0; // filled bits of future symbol index

size_t symbol_acc = 0; // bitmask of future packed symbol index

// Example, depth=11:

// [11111111][11122222][222222..][........][........][........][........]

// [11111111][11122222][22222233][........][........][........][........]

// [11111111][11122222][22222233][33333333][........][........][........]

// [11111111][11122222][22222233][33333333][3.......][........][........]

// cycle over codes

for(auto code : src) {

// cycle over code bits

for(size_t code_done = 0; code_done < bit_depth;) {

size_t symbol_left = bit_capacity - symbol_done;

size_t code_left = bit_depth - code_done;

size_t bits_to_write = std::min(symbol_left, code_left);

size_t mask = (code >> code_done); // abcd|ef => abcd

mask &= (1ULL << bits_to_write) - 1ULL; // abcd => 00cd

mask <<= symbol_done; // 00cd => 00cd0000

symbol_acc = symbol_acc | mask;

code_done += bits_to_write;

symbol_done += bits_to_write;

// output symbol ready, push it

if(symbol_done == bit_capacity) {

*d_first++ = PackDict::symbol_by_index(symbol_acc);

symbol_done = symbol_acc = 0;

}

}

}

// no codes left, but last symbol isn't saved

if(symbol_done != 0)

*d_first++ = PackDict::symbol_by_index(symbol_acc);

return d_first;

}

template <class InputIt>

static void unpack_bits(InputIt first, InputIt last, codes_vec& dst) {

if(first == last) return;

const size_t bit_depth = PackDict::index_of_symbol(*first++);

if(first == last) throw std::logic_error{"lzw_codec: bad data 1"};

const size_t dead_bits = PackDict::index_of_symbol(*first++);

if(first == last) throw std::logic_error{"lzw_codec: bad data 2"};

const size_t input_length = distance_advice(first, last);

const size_t payload_bits = bit_capacity*input_length;

const size_t out_length = (payload_bits - dead_bits)/bit_depth;

// output preparing

dst.clear(); dst.reserve(out_length + 1);

auto d_first = std::back_inserter(dst);

bool done = false; // stop condition

size_t symbol_done = 0; // read bits of symbol index

// first chunk of data

size_t chunk = PackDict::index_of_symbol(*first++);

// cycle over codes

do {

size_t code_acc = 0;

size_t code_done = 0;

// cycle over code bits

while(code_done < bit_depth) {

size_t symbol_left = bit_capacity - symbol_done;

size_t code_left = bit_depth - code_done;

// previously processed code may be the last

if(symbol_left == dead_bits && code_done == 0 && first == last) {

done = true; break; }

size_t bits_to_read = std::min(symbol_left, code_left);

size_t data = chunk;

data >>= symbol_done; // abcde|fg => abcde

data &= (1ULL << bits_to_read) - 1ULL; // abcde => 00cde

data <<= code_done; // 00cde => 00cde000

code_acc |= data;

code_done += bits_to_read;

symbol_done += bits_to_read;

// the whole symbol has been processed, move to next

if(symbol_done == bit_capacity) {

if(first == last) {

done = true; break; }

chunk = PackDict::index_of_symbol(*first++);

symbol_done = 0;

}

}

// no symbols left, but last code isn't saved

if(code_done > 0)

*d_first++ = code_acc;

} while(!done);

}

public:

/// Compresses and encodes input range [first, last).

/// @param first - begin input iterator,

/// @param last - end input iterator,

/// @param d_first - begin output iterator,

/// @returns output iterator, one past the last element copied.

template <class InputIt, class OutputIt>

static OutputIt encode(InputIt first, InputIt last, OutputIt d_first) {

if(first == last) return d_first;

auto dict = encode_dict();

size_t next_code = dict.size();

size_t max_code = next_code - 1;

codes_vec codes;

codes.reserve(distance_advice(first, last)*3/2);

phrase_t phrase(1, *first++);

phrase_t tmp;

/// Single emplace step

auto emplace_code = [&dict, &phrase, &max_code, &codes]{

auto code = dict.at(phrase);

max_code = std::max(max_code, code);

codes.emplace_back(code); };

while(first != last) {

auto curr_symbol = *first++;

tmp = phrase;

tmp.push_back(curr_symbol);

// already exists, no insertion

if(!dict.emplace(tmp, next_code).second) {

phrase = tmp;

// not exists, inserted

} else {

++next_code;

emplace_code();

phrase.assign(1, curr_symbol);

}

}

// last step

emplace_code();

// values_num == max_code + 1

auto bit_depth = log2_ceil(max_code + 1);

// resulting dictionary is too big for size_t codes

if(bit_depth > CHAR_BIT * sizeof(size_t))

throw std::logic_error{"lzw_codec: bit_depth > log2(size_t)"};

// resulting dictionary is too big to be packed with PackDict

if(bit_depth >= PackDict::length)

throw std::logic_error{"lzw_codec: bit_depth > PackDict::length"};

return pack_bits(codes, d_first, bit_depth);

}

/// Decodes and decompress input range [first, last).

/// @param first - begin input iterator,

/// @param last - end input iterator,

/// @param d_first - begin output iterator,

/// @returns output iterator, one past the last element copied.

template <class InputIt, class OutputIt>

static OutputIt decode(InputIt first, InputIt last, OutputIt d_first) {

if(first == last) return d_first;

// Binary unpacking

codes_vec codes;

unpack_bits(first, last, codes);

auto rdict = decode_dict();

size_t code = codes[0];

size_t old = code;

phrase_t tmp = rdict[code];

d_first = std::copy(tmp.begin(), tmp.end(), d_first);

for(size_t i = 1, sz = codes.size(); i < sz; ++i) {

code = codes[i];

tmp = rdict[old];

if(code < rdict.size()) {

auto const& entry = rdict[code];

tmp.push_back(entry[0]);

d_first = std::copy(entry.begin(), entry.end(), d_first);

rdict.emplace_back(std::move(tmp));

} else {

tmp.push_back(tmp[0]);

d_first = std::copy(tmp.begin(), tmp.end(), d_first);

rdict.emplace_back(std::move(tmp));

}

old = code;

}

return d_first;

}

using Input_dictionary = IODict;

using Pack_dictionary = PackDict;