tudocomp
– The TU Dortmund Compression Framework
HashTrie.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <tudocomp/Algorithm.hpp>
4 #include <tudocomp/util/Hash.hpp>
8 
9 namespace tdc {
10 namespace lz78 {
11 
12 
13 template<class HashFunction = MixHasher, class HashProber = LinearProber, class HashManager = SizeManagerPow2>
14 class HashTrie : public Algorithm, public LZ78Trie<> {
16 
17 public:
18  inline static Meta meta() {
19  Meta m("lz78trie", "hash", "Hash Trie");
20  m.option("hash_function").templated<HashFunction, MixHasher>("hash_function");
21  m.option("hash_prober").templated<HashProber, LinearProber>("hash_prober");
22  m.option("hash_manager").templated<HashManager, SizeManagerPow2>("hash_manager");
23  m.option("load_factor").dynamic(30);
24  return m;
25  }
26 
27  inline HashTrie(Env&& env, const size_t n, const size_t& remaining_characters, factorid_t reserve = 0)
28  : Algorithm(std::move(env))
29  , LZ78Trie(n,remaining_characters)
30  , m_table(this->env(),n,remaining_characters)
31  {
32  m_table.max_load_factor(this->env().option("load_factor").as_integer()/100.0f );
33  if(reserve > 0) {
34  m_table.reserve(reserve);
35  }
36  }
37 
38  IF_STATS(
39  MoveGuard m_guard;
40  inline ~HashTrie() {
41  if (m_guard) {
42  m_table.collect_stats(env());
43  }
44  }
45  )
46  HashTrie(HashTrie&& other) = default;
47  HashTrie& operator=(HashTrie&& other) = default;
48 
50  m_table.insert(
51  std::make_pair<squeeze_node_t,factorid_t>(
52  create_node(0, c),
53  size()
54  )
55  );
56  return node_t(size() - 1, true);
57  }
58 
59  inline node_t get_rootnode(uliteral_t c) const {
60  return node_t(c, false);
61  }
62 
63  inline void clear() {
64 // table.clear();
65 
66  }
67 
68  inline node_t find_or_insert(const node_t& parent_w, uliteral_t c) {
69  auto parent = parent_w.id();
70  const factorid_t newleaf_id = size();
71 
72  auto ret = m_table.insert(
73  std::make_pair(
74  create_node(parent,c),
75  newleaf_id
76  )
77  );
78  if(ret.second) return node_t(newleaf_id, true); // added a new node
79  return node_t(ret.first.value(), false);
80  }
81 
82  inline size_t size() const {
83  return m_table.entries();
84  }
85 };
86 
87 }} //ns
88 
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
Provides meta information about an Algorithm.
Definition: Meta.hpp:34
LZ78TrieNode node_t
Definition: LZ78Trie.hpp:43
size_t size() const
Definition: HashTrie.hpp:82
uint8_t uliteral_t
Type to represent signed single literals.
Definition: def.hpp:131
std::pair< Iterator, bool > insert(std::pair< key_t, value_t > &&value)
Definition: Hash.hpp:518
void reserve(len_t hint)
Definition: Hash.hpp:461
node_t add_rootnode(uliteral_t c)
Definition: HashTrie.hpp:49
HashTrie & operator=(HashTrie &&other)=default
Env & env()
Provides access to the environment that the algorithm works in.
Definition: Algorithm.hpp:51
factorid_t id() const
Definition: LZ78Trie.hpp:32
Default return type of find_or_insert.
Definition: LZ78Trie.hpp:22
void templated(const std::string &accepted_type)
Declares that this option accepts values of the specified Algorithm type T.
Definition: Meta.hpp:93
static Meta meta()
Definition: HashTrie.hpp:18
uint32_t factorid_t
Type for the factor indices, bounded by the number of LZ78 trie nodes.
Definition: LZ78Trie.hpp:11
node_t find_or_insert(const node_t &parent_w, uliteral_t c)
Definition: HashTrie.hpp:68
squeeze_node_t create_node(factorid_t id, uliteral_t c)
IF_STATS(MoveGuard m_guard;inline ~HashTrie() { if(m_guard) { m_table.collect_stats(env());} }) HashTrie(HashTrie &&other)=default
OptionBuilder option(const std::string &name)
Declares an accepted option for this algorithm.
Definition: Meta.hpp:216
float max_load_factor() const noexcept
Definition: Hash.hpp:409
Local environment for a compression/encoding/decompression call.
len_t entries() const
Definition: Hash.hpp:514
Interface for algorithms.
Definition: Algorithm.hpp:15
void dynamic()
Declares that this option accepts values of a simple type that can be parsed from a string (e...
Definition: Meta.hpp:150
HashTrie(Env &&env, const size_t n, const size_t &remaining_characters, factorid_t reserve=0)
Definition: HashTrie.hpp:27
node_t get_rootnode(uliteral_t c) const
Definition: HashTrie.hpp:59