trie.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef TRIE_H
#define TRIE_H
 
#include "tdecl.h"
 
#if KBLIB_USE_CXX17
 
#  include "sort.h"
#  include "traits.h"
 
#  include <array>
#  include <bitset>
#  include <vector>
 
namespace KBLIB_NS {
 
enum class extractor_policy {
   forward_iteration,
   random_access,
};
 
template <typename Container>
struct iterator_extractor {
   using value_type =
       typename std::remove_cv<typename std::remove_reference<decltype(
           *begin(std::declval<Container&>()))>::type>::type;
};
 
template <typename Container>
struct indexer_extractor : iterator_extractor<Container> {
   using value_type =
       typename std::remove_cv<typename std::remove_reference<decltype(
           std::declval<Container&>()[0])>::type>::type;
 
   template <typename index_type>
   KBLIB_NODISCARD constexpr static auto subscript(
       Container&& c, index_type index) noexcept(noexcept(c[index]))
       -> decltype(auto) {
      return c[index];
   }
};
 
template <typename Container, typename = void>
struct extractor_policy_for {
   constexpr static extractor_policy value
       = extractor_policy::forward_iteration;
};
 
template <typename Container>
struct extractor_policy_for<Container,
                            void_t<decltype(std::declval<Container>()[0])>> {
   constexpr static extractor_policy value = extractor_policy::random_access;
};
 
template <typename Container>
using default_extractor_t = typename std::conditional<
    extractor_policy_for<Container>::value == extractor_policy::random_access,
    indexer_extractor<Container>, iterator_extractor<Container>>::type;
 
namespace detail {
 
   template <typename Elem, typename Value>
   struct node {};
 
} // namespace detail
 
template <typename Key, typename T,
          typename Extractor = default_extractor_t<Key>,
          bool = kblib::is_linear_container<Key>::value>
class trie {
 public:
   using key_type = Key;
   using mapped_type = T;
   using value_type = std::pair<key_type, mapped_type>;
   using extractor = Extractor;
   using node_type = detail::node<typename extractor::value_type, value_type>;
 
   using size_type = std::size_t;
   using difference_type = std::ptrdiff_t;
   using reference = T&;
   using const_reference = const T&;
   using pointer = T*;
   using const_pointer = const T*;
 
   using iterator = void;
   using const_iterator = void;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
 private:
   std::unique_ptr<node_type> root;
 
 public:
};
 
template <typename KeyElem, typename T, typename Extractor>
class trie<KeyElem, T, Extractor, false> {};
 
template <typename KeyElem, typename T, typename Extractor>
class trie<KeyElem[], T, Extractor, false> {};
 
// Array-mapped tries are better for denser sets
// Tree-based tries are better for sparser sets
 
// trie_map and trie_set are mostly API compatible with std::map, std::set
// trie_qmap and trie_qset use proxy iterators to avoid having to store Keys
// (saves memory, less compatible with stdlib)
 
template <typename Key, typename = void>
struct default_extract;
 
template <typename Key>
struct default_extract<Key, void_if_t<is_linear_container_v<Key>>> {
   using value_type = typename Key::value_type;
   static_assert(static_cast<value_type>(max) < static_cast<std::size_t>(max),
                 "Key too large to index array");
   // won't overflow because of above assertion
   KBLIB_CONSTANT_M std::size_t key_cardinality
       = static_cast<value_type>(max) + std::size_t{1};
   static_assert(std::is_integral<value_type>::value,
                 "Key elements must be integral");
 
   KBLIB_NODISCARD static constexpr auto begin(Key& key) noexcept(
       noexcept(key.begin())) -> decltype(auto) {
      return key.begin();
   }
   KBLIB_NODISCARD static constexpr auto end(Key& key) noexcept(
       noexcept(key.end())) -> decltype(auto) {
      return key.end();
   }
   KBLIB_NODISCARD static constexpr auto index(
       Key& key, std::size_t idx) noexcept(noexcept(key[idx]))
       -> decltype(auto) {
      return key[idx];
   }
};
 
template <typename KeyElem>
struct default_extract<KeyElem[], void_if_t<std::is_integral_v<KeyElem>>> {
   using value_type = KeyElem;
   static_assert(static_cast<value_type>(max) < static_cast<std::size_t>(max),
                 "Key too large to index array");
   // won't overflow because of above assertion
   KBLIB_CONSTANT_M std::size_t key_cardinality
       = static_cast<value_type>(max) + std::size_t{1};
   static_assert(std::is_integral<value_type>::value,
                 "Key elements must be integral");
 
   template <std::size_t Size>
   KBLIB_NODISCARD static constexpr auto begin(KeyElem (&key)[Size]) noexcept(
       noexcept(std::begin(key))) -> decltype(auto) {
      return std::begin(key);
   }
   template <std::size_t Size>
   KBLIB_NODISCARD static constexpr auto end(KeyElem (&key)[Size]) noexcept(
       noexcept(std::end(key))) -> decltype(auto) {
      return std::end(key);
   }
   template <std::size_t Size>
   KBLIB_NODISCARD static constexpr auto index(
       KeyElem (&key)[Size], std::size_t idx) noexcept(noexcept(key[idx]))
       -> decltype(auto) {
      return key[idx];
   }
};
 
template <typename Key>
struct default_extract<Key, void_if_t<is_radix_sortable_v<Key>>>;
 
// qset: does not store Keys (generates them on-demand)
// Key: the type used for lookup
// Extractor: controls how lookup is performed from the key
// offset_type: used to represent jumps in the internal array. Must be a signed
// integral type
template <typename Key, typename Extractor = default_extract<Key>,
          typename offset_type = std::ptrdiff_t>
class trie_qset {
 public:
   using key_type = Key;
   using value_type = Key;
   using size_type = std::size_t;
   using difference_type = std::ptrdiff_t;
 
   using reference = value_type&;
   using const_reference = const value_type&;
   using pointer = value_type*;
   using const_pointer = const value_type*;
 
   using extractor = Extractor;
   using key_elem = typename extractor::value_type;
   KBLIB_CONSTANT_M std::size_t key_elem_cardinality
       = extractor::key_cardinality;
 
 private:
   // Bitset stores leaf status, array holds jumps, 0 represents no jump (leaf
   // or no entry)
   using row_type = std::pair<std::bitset<key_elem_cardinality>,
                              std::array<offset_type, key_elem_cardinality>>;
   std::vector<row_type> data_;
};
 
template <typename Key, typename Extractor = default_extract<Key>,
          typename offset_type = std::ptrdiff_t>
class trie_set {
 public:
   using key_type = Key;
   using value_type = Key;
   using size_type = std::size_t;
   using difference_type = std::ptrdiff_t;
 
   using reference = value_type&;
   using const_reference = const value_type&;
   using pointer = value_type*;
   using const_pointer = const value_type*;
 
   using extractor = Extractor;
   using key_elem = typename extractor::value_type;
   KBLIB_CONSTANT_M std::size_t key_elem_cardinality
       = extractor::key_cardinality;
 
 private:
   // offset 0 represents no jump (leaf or no entry)
   using row_type = std::array<std::pair<std::optional<Key>, offset_type>,
                               key_elem_cardinality>;
   std::vector<row_type> data_;
};
 
template <typename Key, typename Value,
          typename Extractor = default_extract<Key>,
          typename offset_type = std::ptrdiff_t,
          template <typename> typename SequenceContainer = std::vector>
class trie_map {};
template <typename Key, typename Value,
          typename Extractor = default_extract<Key>,
          typename offset_type = std::ptrdiff_t,
          template <typename> typename SequenceContainer = std::vector>
class trie_qmap {};
 
template <typename Key, typename Extractor = default_extract<Key>>
class sparse_trie_set {};
 
template <typename Key, typename Value,
          typename Extractor = default_extract<Key>>
class sparse_trie_map {};
 
} // namespace KBLIB_NS
 
#endif // KBLIB_USE_CXX17
 
#endif // TRIE_H