16 std::vector<factorid_t> m_first_child;
17 std::vector<factorid_t> m_next_sibling;
18 std::vector<uliteral_t> m_literal;
22 size_t m_specialresizes = 0;
25 inline static Meta meta() {
26 Meta m(
"lz78trie",
"binary",
"Lempel-Ziv 78 Binary Trie");
35 m_first_child.reserve(reserve);
36 m_next_sibling.reserve(reserve);
37 m_literal.reserve(reserve);
48 StatPhase::log(
"load ratio", m_first_child.size()*100/m_first_child.capacity());
59 m_literal.push_back(c);
68 m_first_child.clear();
69 m_next_sibling.clear();
74 auto parent = parent_w.
id();
77 DCHECK_LT(parent, size());
80 if(m_first_child[parent] ==
undef_id) {
81 m_first_child[parent] = newleaf_id;
85 if(c == m_literal[node])
return node_t(node,
false);
86 if(m_next_sibling[node] ==
undef_id) {
87 m_next_sibling[node] = newleaf_id;
90 node = m_next_sibling[node];
93 if(m_first_child.capacity() == m_first_child.size()) {
95 if(newbound < m_first_child.size()*2 ) {
96 m_first_child.reserve (newbound);
97 m_next_sibling.reserve (newbound);
98 m_literal.reserve (newbound);
99 IF_STATS(++m_specialresizes);
101 IF_STATS(++m_resizes);
105 m_literal.push_back(c);
106 return node_t(size() - 1,
true);
109 inline size_t size()
const {
110 return m_first_child.size();
Contains the text compression and encoding framework.
uint8_t uliteral_t
Type to represent signed single literals.
Algorithm(Algorithm const &)=default
LZ78Trie(const size_t n, const size_t &remaining_characters)
Env & env()
Provides access to the environment that the algorithm works in.
Default return type of find_or_insert.
static void log(const char *key, const T &value)
Logs a user statistic for the current phase.
uint32_t factorid_t
Type for the factor indices, bounded by the number of LZ78 trie nodes.
constexpr factorid_t undef_id
Id that can be used for a non-existing factor.
Local environment for a compression/encoding/decompression call.
Interface for algorithms.
size_t expected_number_of_remaining_elements(const size_t z) const