table.hpp

#include <cassert>
#include <iterator>
#include <optional>
#include <variant>
 
#include "cplib/hash/wyhash.hpp"
 
namespace cplib {
 
namespace impl {
 
template <typename T>
struct HashCell {
  enum State { EMPTY, PHANTOM, SENTINEL };
 
  std::variant<State, T> inner;
 
  HashCell() : inner(State::EMPTY) {}
 
  bool empty() const { return inner.index() == 0 && std::get<0>(inner) == State::EMPTY; }
 
  bool occupied() const { return inner.index() == 1; }
 
  bool phantom() const { return inner.index() == 0 && std::get<0>(inner) == State::PHANTOM; }
 
  bool sentinel() const { return inner.index() == 0 && std::get<0>(inner) == State::SENTINEL; }
 
  void insert(const T& val) { inner = val; }
 
  void insert(T&& val) { inner = std::move(val); }
 
  const T& value() const { return std::get<1>(inner); }
 
  T& value() { return std::get<1>(inner); }
 
  void erase() { inner = State::PHANTOM; }
};
 
}  // namespace impl
 
template <typename T, typename Hash = WyHash<T>, typename Eq = std::equal_to<T>>
class HashTable {
 public:
  using size_type = std::size_t;
  using value_type = T;
  using cell_iterator = typename std::vector<impl::HashCell<T>>::iterator;
 
  HashTable() : nonempty(0), occupied(0), disable_shrink(false) { _allocate_cells(4); }
 
  template <typename InputIt>
  HashTable(InputIt first, InputIt last) : nonempty(0), occupied(0), disable_shrink(false) {
    size_type cap = 4;
    if (std::is_base_of_v<std::random_access_iterator_tag, std::iterator_traits<InputIt>::iterator_category>) {
      auto dist = std::distance(first, last);
      while (dist > (cap >> 1)) {
        cap <<= 1;
      }
    }
    _allocate_cells(cap);
    for (; first != last; ++first) {
      insert(*first);
    }
  }
 
  size_type size() const { return occupied; }
 
  bool empty() const { return occupied == 0; }
 
  size_type capacity() const { return cap_mask + 1; }
 
  cell_iterator cell_begin() { return cells.begin(); }
 
  cell_iterator cell_end() { return --cells.end(); }
 
  template <bool Revive = false>
  cell_iterator find_cell(const T& x) {
    size_type loc = hash(x) & cap_mask;
    std::optional<cell_iterator> phantom;
    while (!cells[loc].empty()) {
      if (cells[loc].occupied() && eq(x, cells[loc].value())) {
        return cells.begin() + loc;
      }
      if (Revive && cells[loc].phantom()) {
        phantom = cells.begin() + loc;
      }
      loc = (loc + 1) & cap_mask;
    }
    if (Revive && phantom) {
      return *phantom;
    } else {
      return cells.begin() + loc;
    }
  }
 
  bool contains(const T& x) const { return !const_cast<HashTable*>(this)->find_cell(x)->empty(); }
 
  template <bool Replace = false>
  bool insert(const T& x) {
    cell_iterator cell = find_cell<true>(x);
    bool do_insert = true;
    if (!cell->occupied()) {
      ++occupied;
      if (cell->empty()) {
        ++nonempty;
      }
      cell->insert(x);
      _check_rehash();
    } else if (Replace) {
      cell->insert(x);
    } else {
      do_insert = false;
    }
    return do_insert;
  }
 
  template <bool Replace = false>
  bool insert(T&& x) {
    cell_iterator cell = find_cell<true>(x);
    bool do_insert = true;
    if (!cell->occupied()) {
      ++occupied;
      if (cell->empty()) {
        ++nonempty;
      }
      cell->insert(std::move(x));
      _check_rehash();
    } else if (Replace) {
      cell->insert(std::move(x));
    } else {
      do_insert = false;
    }
    return do_insert;
  }
 
  bool erase(const T& x) {
    cell_iterator cell = find_cell(x);
    bool do_erase = !cell->empty();
    if (do_erase) {
      cell->erase();
      --occupied;
      _check_rehash();
    }
    return do_erase;
  }
 
  void rehash(size_type new_cap) {
    assert(new_cap >= 4 && (new_cap & (new_cap - 1)) == 0);
    std::vector<impl::HashCell<T>> old_cells = std::move(cells);
    size_type old_cap = cap_mask + 1;
    _allocate_cells(new_cap);
    nonempty = occupied;
    for (size_type i = 0; i < old_cap; ++i) {
      if (old_cells[i].occupied()) {
        size_type loc = hash(old_cells[i].value()) & cap_mask;
        while (!cells[loc].empty()) {
          loc = (loc + 1) & cap_mask;
        }
        cells[loc] = std::move(old_cells[i]);
      }
    }
  }
 
  void reserve(size_type new_size) {
    size_type new_cap = capacity();
    while (new_size > (new_cap >> 1)) {
      new_cap <<= 1;
    }
    if (new_cap > capacity()) {
      rehash(new_cap);
      disable_shrink = true;
    }
  }
 
 private:
  std::vector<impl::HashCell<T>> cells;
  size_type nonempty, occupied, cap_mask;
  bool disable_shrink;
  Hash hash;
  Eq eq;
 
  // Allocate a new array of cells, set sentinel and cap_mask.
  void _allocate_cells(size_type cap) {
    cells = std::vector<impl::HashCell<T>>(cap + 1);
    cells.back().inner = impl::HashCell<T>::State::SENTINEL;
    cap_mask = cap - 1;
  }
 
  // See class documentation for rehashing policy.
  void _check_rehash() {
    size_type cap = capacity();
    if (!disable_shrink && occupied < (cap >> 3)) {
      do {
        cap >>= 1;
      } while (occupied < (cap >> 3));
      rehash(cap);
    } else if (nonempty > (cap >> 1)) {
      disable_shrink = false;
      if (occupied > (cap >> 2)) {
        cap <<= 1;
      }
      rehash(cap);
    }
  }
};
 
}  // namespace cplib