LZ78Trie.hpp

Go to the documentation of this file.

#pragma once

#include <limits>
#include <cstddef>
#include <cstdint>
#include <tudocomp/def.hpp>
namespace tdc {
namespace lz78 {

using factorid_t = uint32_t;

constexpr factorid_t undef_id = std::numeric_limits<factorid_t>::max();

constexpr size_t DMS_MAX = std::numeric_limits<factorid_t>::max();

// NB: Also update the Lz78 chapter in the docs in case of changes to this file

class LZ78TrieNode {
    factorid_t m_id;
    bool m_is_new;
public:
    inline LZ78TrieNode(factorid_t id, bool is_new):
        m_id(id), m_is_new(is_new) {}
    inline LZ78TrieNode():
        LZ78TrieNode(0, false) {}

    inline bool is_new() const { return m_is_new; }
    inline factorid_t id() const { return m_id; }
};

#define LZ78_DICT_SIZE_DESC \
            "`dict_size` has to either be 0 (unlimited), or a positive integer,\n" \
            "and determines the maximum size of the backing storage of\n" \
            "the dictionary before it gets reset."

template<typename _node_t = LZ78TrieNode>
class LZ78Trie {
public:
    using node_t = _node_t;
private:
    const size_t m_n;
    const size_t& m_remaining_characters;
protected:
    LZ78Trie(const size_t n, const size_t& remaining_characters)
        : m_n(n), m_remaining_characters(remaining_characters) {}

    inline size_t expected_number_of_remaining_elements(const size_t z) const {
        return lz78_expected_number_of_remaining_elements(z, m_n, m_remaining_characters);
    }

    inline node_t add_rootnode(uliteral_t c) {
        CHECK(false) << "This needs to be implemented by a inheriting class";
        return 0;
    }

    inline node_t get_rootnode(uliteral_t c) const {
        CHECK(false) << "This needs to be implemented by a inheriting class";
        return 0;
    }

    inline void clear() {
        CHECK(false) << "This needs to be implemented by a inheriting class";
    }

    inline node_t find_or_insert(const node_t& parent, uliteral_t c) {
        CHECK(false) << "This needs to be implemented by a inheriting class";
        return 0;
    }

    inline size_t size() const {
        CHECK(false) << "This needs to be implemented by a inheriting class";
        return 0;
    }

};


}}//ns