map.h

/*
 * Copyright (c) 2017 Olle Liljenzin
 */

#ifndef CONFLUENT_MAP_H_INCLUDED
#define CONFLUENT_MAP_H_INCLUDED

#include <stdexcept>

#include "set.h"

namespace confluent {


template <class Key,
          class T,
          class Compare,
          class Hash,
          class Equal,
          class MappedHash,
          class MappedEqual>
class map_provider;

template <class Key,
          class T,
          class Compare,
          class Hash,
          class Equal,
          class MappedHash,
          class MappedEqual>
class map;

namespace internal {

inline size_t hash_combine(size_t h1, size_t h2, size_t h3, size_t h4) {
  return hash_combine(hash_combine(h1, h2), hash_combine(h3, h4));
}

struct map_tag {};

template <class Traits>
node_ptr<Traits> make_node(const env<Traits, map_tag>& env,
                           const typename Traits::value_type& value,
                           node_ptr<typename Traits::key_set_traits> key_node,
                           node_ptr<Traits> left,
                           node_ptr<Traits> right) {
  return node<Traits>::create(env, value, std::move(key_node), std::move(left),
                              std::move(right), env.hash(value.second));
}

template <class Traits>
node_ptr<Traits> make_node(const env<Traits, map_tag>& env,
                           const typename Traits::value_type& value,
                           node_ptr<Traits> left = nullptr,
                           node_ptr<Traits> right = nullptr) {
  node_ptr<typename Traits::key_set_traits> key_node = make_node(
      env.key_set_env_, value.first, left ? left->key_node() : nullptr,
      right ? right->key_node() : nullptr);
  return make_node(env, value, std::move(key_node), std::move(left),
                   std::move(right));
}

template <class Traits>
node_ptr<Traits> make_node(const env<Traits, map_tag>& env,
                           const node<Traits>& parent,
                           node_ptr<Traits> left,
                           node_ptr<Traits> right) {
  node_ptr<typename Traits::key_set_traits> key_node = make_node(
      env.key_set_env_, *parent.key_node(), left ? left->key_node() : nullptr,
      right ? right->key_node() : nullptr);
  return make_node(env, parent.value(), std::move(key_node), std::move(left),
                   std::move(right));
}

template <class Traits, class Left, class Right>
node_ptr<Traits> set_intersection(const env<Traits>& env,
                                  Left&& left,
                                  Right&& right) {
  if (!left || !right)
    return nullptr;
  if (left->key_node() == right)
    return std::forward<Left>(left);
  switch (rank(env.key_set_env_, *left->key_node(), *right)) {
    case ranking::LEFT: {
      auto s = split(env.key_set_env_, std::forward<Right>(right), left->key());
      return join(env, set_intersection(env, left->left_, std::move(s.first)),
                  set_intersection(env, left->right_, std::move(s.second)));
    }
    case ranking::RIGHT: {
      auto s = split(env, std::forward<Left>(left), right->key());
      return join(env, set_intersection(env, std::move(s.first), right->left_),
                  set_intersection(env, std::move(s.second), right->right_));
    }
    default: {
      return make_node(env, *left,
                       set_intersection(env, left->left_, right->left_),
                       set_intersection(env, left->right_, right->right_));
    }
  }
}

template <class Traits, class Left, class Right>
node_ptr<Traits> set_difference(const env<Traits>& env,
                                Left&& left,
                                Right&& right) {
  if (!left || left->key_node() == right)
    return nullptr;
  if (!right)
    return std::forward<Left>(left);
  switch (rank(env.key_set_env_, *left->key_node(), *right)) {
    case ranking::LEFT: {
      auto s = split(env.key_set_env_, std::forward<Right>(right), left->key());
      return make_node(env, *left,
                       set_difference(env, left->left_, std::move(s.first)),
                       set_difference(env, left->right_, std::move(s.second)));
    }
    case ranking::RIGHT: {
      auto s = split(env, std::forward<Left>(left), right->key());
      return join(env, set_difference(env, std::move(s.first), right->left_),
                  set_difference(env, std::move(s.second), right->right_));
    }
    default: {
      return join(env, set_difference(env, left->left_, right->left_),
                  set_difference(env, left->right_, right->right_));
    }
  }
}

template <class Traits, class NodePtr>
size_t update(const env<Traits>& env, node_ptr<Traits>* p, NodePtr&& q) {
  size_t n = size(*p);
  *p = set_union(env, std::forward<NodePtr>(q), *p);
  return size(*p) - n;
}

template <class Traits, class NodePtr>
size_t diff(const env<Traits>& env, node_ptr<Traits>* p, NodePtr&& q) {
  size_t n = size(*p);
  *p = set_difference(env, *p, std::forward<NodePtr>(q));
  return n - size(*p);
}

template <class Traits, class NodePtr>
size_t intersect(const env<Traits>& env, node_ptr<Traits>* p, NodePtr&& q) {
  size_t n = size(*p);
  *p = set_intersection(env, *p, std::forward<NodePtr>(q));
  return n - size(*p);
}

template <class Traits>
size_t insert_or_assign(const env<Traits>& env,
                        node_ptr<Traits>* p,
                        const typename Traits::value_type& value) {
  return update(env, p, make_node(env, value));
}

template <class Traits, class InputIterator>
size_t insert_or_assign(const env<Traits>& env,
                        node_ptr<Traits>* p,
                        InputIterator first,
                        InputIterator last) {
  return update(env, p, make_node(env, first, last));
}

template <class Key,
          class T,
          class Compare,
          class Hash,
          class Equal,
          class MappedHash,
          class MappedEqual>
struct map_traits {
  typedef map_tag category;
  typedef Key key_type;
  typedef T mapped_type;
  typedef std::pair<Key, T> value_type;
  typedef map_provider<Key, T, Compare, Hash, Equal, MappedHash, MappedEqual>
      provider;
  typedef map<Key, T, Compare, Hash, Equal, MappedHash, MappedEqual> container;
  typedef set_traits<Key, Compare, Hash, Equal> key_set_traits;
};

template <class Traits>
struct node<Traits, map_tag> {
  typedef node_ptr<Traits> ptr_type;
  typedef typename Traits::key_type key_type;
  typedef typename Traits::mapped_type mapped_type;
  typedef typename Traits::value_type value_type;
  typedef node_ptr<typename Traits::key_set_traits> key_node_ptr;
  typedef env<Traits> env_type;

  node(const value_type& value,
       key_node_ptr key_node,
       ptr_type left,
       ptr_type right,
       size_t hash)
      : reference_count_(1),
        value_(value),
        key_node_(std::move(key_node)),
        hash_(hash),
        left_(std::move(left)),
        right_(std::move(right)) {}

  static ptr_type create(const env_type& env,
                         const value_type& value,
                         key_node_ptr key_node,
                         ptr_type left,
                         ptr_type right,
                         size_t mapped_hash) {
    size_t hash = hash_combine(internal::hash(left), internal::hash(right),
                               mapped_hash, key_node->hash_);
    std::unique_ptr<node> p(new node(value, std::move(key_node),
                                     std::move(left), std::move(right), hash));
    return get_unique_node(env, std::move(p));
  }

  const key_type& key() const { return value_.first; }
  const mapped_type& mapped() const { return value_.second; }
  const value_type& value() const { return value_; }
  size_t priority() const { return key_node_->priority(); }
  size_t size() const { return key_node_->size(); }
  const key_node_ptr& key_node() const { return key_node_; }

  std::atomic<size_t> reference_count_;
  node* next_;
  value_type value_;
  key_node_ptr key_node_;
  const size_t hash_;
  const ptr_type left_;
  const ptr_type right_;
};

template <class Traits>
struct env<Traits, map_tag> : env_base<Traits> {
  typedef typename Traits::provider provider_type;
  typedef typename Traits::key_type key_type;
  typedef typename Traits::mapped_type mapped_type;
  typedef typename Traits::value_type value_type;
  typedef typename Traits::key_set_traits key_set_traits;
  typedef env<key_set_traits> key_set_env_type;

  using env_base<Traits>::provider_;

  env(provider_type* provider)
      : env_base<Traits>(provider),
        key_set_env_(provider->set_provider().get()) {}

  static bool compare(const key_type& lhs, const key_type& rhs) {
    return key_set_env_type::compare(lhs, rhs);
  }

  static bool compare(const value_type& lhs, const key_type& rhs) {
    return key_set_env_type::compare(lhs.first, rhs);
  }

  static bool compare(const value_type& lhs, const value_type& rhs) {
    return compare(lhs.first, rhs.first);
  }

  static bool equal(const mapped_type& lhs, const mapped_type& rhs) {
    return provider_->mapped_eq()(lhs, rhs);
  }

  static bool equal(const value_type& lhs, const key_type& rhs) {
    return key_set_env_type::equal(lhs.first, rhs);
  }

  static bool equal(const value_type& lhs, const value_type& rhs) {
    return key_set_env_type::equal(lhs.first, rhs.first) &&
           provider_->mapped_eq()(lhs.second, rhs.second);
  }

  static size_t hash(const mapped_type& mapped) {
    return provider_->mapped_hash()(mapped);
  }

  const key_set_env_type key_set_env_;
};

}  // namespace internal


template <class Key,
          class T,
          class Compare = std::less<Key>,
          class Hash = std::hash<Key>,
          class Equal = std::equal_to<Key>,
          class MappedHash = std::hash<T>,
          class MappedEqual = std::equal_to<T>>
class map_provider {
  typedef internal::
      map_traits<Key, T, Compare, Hash, Equal, MappedHash, MappedEqual>
          traits;

  friend struct internal::env_base<traits>;

 public:
  typedef confluent::set_provider<Key, Compare, Hash, Equal> set_provider_type;

  map_provider(const MappedHash& mapped_hash = MappedHash(),
               const MappedEqual& mapped_equal = MappedEqual(),
               const std::shared_ptr<set_provider_type>& set_provider =
                   set_provider_type::default_provider())
      : mapped_hash_(mapped_hash),
        mapped_equal_(mapped_equal),
        set_provider_(set_provider) {
    assert(set_provider_);
  }

  map_provider(const map_provider&) = delete;

  ~map_provider() { assert(size() == 0); }

  const MappedHash& mapped_hash() const { return mapped_hash_; }

  const MappedEqual& mapped_eq() const { return mapped_equal_; }

  const std::shared_ptr<set_provider_type>& set_provider() const {
    return set_provider_;
  }

  size_t size() const {
    std::lock_guard<std::mutex> lock(hash_table_.mutex_);
    return hash_table_.size_;
  }

  static const std::shared_ptr<map_provider>& default_provider() {
    static const std::shared_ptr<map_provider> provider =
        std::make_shared<map_provider>();
    return provider;
  }

 private:
  const MappedHash mapped_hash_;
  const MappedEqual mapped_equal_;
  const std::shared_ptr<set_provider_type> set_provider_;
  internal::hash_table<traits> hash_table_;
};

template <class Key,
          class T,
          class Compare = std::less<Key>,
          class Hash = std::hash<Key>,
          class Equal = std::equal_to<Key>,
          class MappedHash = std::hash<T>,
          class MappedEqual = std::equal_to<T>>
class map {
  typedef internal::
      map_traits<Key, T, Compare, Hash, Equal, MappedHash, MappedEqual>
          traits;
  typedef internal::set_traits<Key, Compare, Hash, Equal> key_set_traits;
  typedef internal::env<traits> env_type;

 public:
  typedef Key key_type;
  typedef T mapped_type;
  typedef std::pair<Key, T> value_type;
  typedef set<Key, Compare, Hash, Equal> key_set_type;
  typedef map_provider<Key, T, Compare, Hash, Equal, MappedHash, MappedEqual>
      provider_type;
  typedef std::shared_ptr<provider_type> provider_ptr;
  typedef confluent::iterator<traits> iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;

 private:
  typedef typename key_set_type::provider_type set_provider_type;
  typedef typename internal::node<traits> node_type;
  typedef typename internal::node<key_set_traits> key_node_type;

  friend struct confluent::iterator<traits>;

 public:
  map(provider_ptr provider = provider_type::default_provider())
      : provider_(std::move(provider)) {}

  template <class InputIterator>
  map(InputIterator first,
      InputIterator last,
      provider_ptr provider = provider_type::default_provider())
      : provider_(std::move(provider)) {
    insert(first, last);
  }

  map(std::initializer_list<value_type> ilist,
      provider_ptr provider = provider_type::default_provider())
      : provider_(std::move(provider)) {
    insert(ilist);
  }

  map(iterator first, iterator last) : map(*first.container_) {
    retain(first, last);
  }

  map(const map& other) : provider_(other.provider_), node_(other.node_) {}

  map(map&& other)
      : provider_(std::move(other.provider_)), node_(std::move(other.node_)) {}

  ~map() { clear(); }

  size_t insert(const value_type& value) {
    return internal::insert(env(), &node_, value);
  }

  template <class InputIterator>
  size_t insert(InputIterator first, InputIterator last) {
    return internal::insert(env(), &node_, first, last);
  }

  size_t insert(std::initializer_list<value_type> ilist) {
    return internal::insert(env(), &node_, ilist.begin(), ilist.end());
  }

  size_t insert(const map& other) {
    check(other);
    return internal::add(env(), &node_, other.node_);
  }

  size_t insert_or_assign(const value_type& value) {
    return internal::insert_or_assign(env(), &node_, value);
  }

  template <class InputIterator>
  size_t insert_or_assign(InputIterator first, InputIterator last) {
    return internal::insert_or_assign(env(), &node_, first, last);
  }

  size_t insert_or_assign(std::initializer_list<value_type> ilist) {
    return internal::insert_or_assign(env(), &node_, ilist.begin(),
                                      ilist.end());
  }

  size_t insert_or_assign(const map& other) {
    check(other);
    return internal::update(env(), &node_, other.node_);
  }

  size_t erase(const key_type& key) {
    return internal::erase(env(), &node_, key);
  }

  size_t erase(const value_type& value) {
    return internal::erase(env(), &node_, value);
  }

  size_t erase(iterator first, iterator last) {
    check(first, last);
    return internal::erase(env(), &node_, first.pos_, last.pos_);
  }

  size_t erase(const key_set_type& other) {
    check(other);
    return internal::diff(env(), &node_, other.node_);
  }

  size_t erase(const map& other) {
    check(other);
    return internal::diff(env(), &rank, &node_, other.node_);
  }

  size_t retain(iterator first, iterator last) {
    check(first, last);
    return internal::retain(env(), &node_, first.pos_, last.pos_);
  }

  size_t retain(const key_set_type& other) {
    check(other);
    return internal::intersect(env(), &node_, other.node_);
  }

  size_t retain(const map& other) {
    check(other);
    return internal::intersect(env(), &rank, &node_, other.node_);
  }

  void clear() {
    if (node_)
      reset(env(), &node_);
  }

  void swap(map& other) {
    provider_.swap(other.provider_);
    node_.swap(other.node_);
  }

  map& operator=(const map& other) {
    clear();
    provider_ = other.provider_;
    node_ = other.node_;
    return *this;
  }

  map& operator=(map&& other) {
    swap(other);
    return *this;
  }

  map& operator=(std::initializer_list<value_type> ilist) {
    internal::assign(env(), &node_, ilist.begin(), ilist.end());
    return *this;
  }

  map operator|(const map& rhs) const {
    check(rhs);
    return map(provider_, set_union(env(), node_, rhs.node_));
  }

  map& operator|=(const map& rhs) {
    check(rhs);
    insert(rhs);
    return *this;
  }

  map operator&(const map& rhs) const {
    check(rhs);
    return map(provider_, set_intersection(env(), &rank, node_, rhs.node_));
  }

  map operator&(const key_set_type& rhs) const {
    check(rhs);
    return map(provider_, set_intersection(env(), node_, rhs.node_));
  }

  map& operator&=(const map& rhs) {
    check(rhs);
    retain(rhs);
    return *this;
  }

  map& operator&=(const key_set_type& rhs) {
    check(rhs);
    retain(rhs);
    return *this;
  }

  map operator-(const map& rhs) const {
    check(rhs);
    return map(provider_, set_difference(env(), &rank, node_, rhs.node_));
  }

  map operator-(const key_set_type& rhs) const {
    check(rhs);
    return map(provider_, set_difference(env(), node_, rhs.node_));
  }

  map& operator-=(const map& rhs) {
    check(rhs);
    erase(rhs);
    return *this;
  }

  map& operator-=(const key_set_type& rhs) {
    check(rhs);
    erase(rhs);
    return *this;
  }

  iterator begin() const { return iterator(this, 0); }

  iterator end() const { return iterator(this, size()); }

  iterator cbegin() const { return begin(); }

  iterator cend() const { return end(); }

  reverse_iterator rbegin() const { return reverse_iterator(end()); }

  reverse_iterator rend() const { return reverse_iterator(begin()); }

  iterator find(const key_type& key) const {
    std::pair<const node_type*, size_t> bound = internal::lower_bound(
        node_.get(),
        [&](const node_type& p) { return key_comp(p.key(), key); });
    if (bound.first && key_eq(bound.first->key(), key))
      return iterator(this, bound);
    else
      return end();
  }

  iterator lower_bound(const key_type& key) const {
    return iterator(this,
                    internal::lower_bound(node_.get(), [&](const node_type& p) {
                      return key_comp(p.key(), key);
                    }));
  }

  iterator upper_bound(const key_type& key) const {
    return iterator(this,
                    internal::lower_bound(node_.get(), [&](const node_type& p) {
                      return !key_comp(key, p.key());
                    }));
  }

  std::pair<iterator, iterator> equal_range(const key_type& key) const {
    return {lower_bound(key), upper_bound(key)};
  }

  const mapped_type& at(const key_type& key) const {
    const node_type* p =
        internal::lower_bound(node_.get(), [&](const node_type& p) {
          return key_comp(p.key(), key);
        }).first;
    if (!p || !key_eq(p->key(), key))
      throw std::out_of_range("key not found");
    return p->mapped();
  }

  const value_type& at_index(size_t k) const {
    return internal::at_index(node_.get(), k)->value();
  }

  size_t count(const key_type& key) const {
    const key_node_type* p =
        internal::lower_bound(
            node_ ? node_->key_node().get() : nullptr,
            [&](const key_node_type& p) { return key_comp(p.key(), key); })
            .first;
    return p && key_eq(p->key(), key) ? 1 : 0;
  }

  size_t count(const key_type& key, const mapped_type& mapped) const {
    const node_type* p =
        internal::lower_bound(node_.get(), [&](const node_type& p) {
          return key_comp(p.key(), key);
        }).first;
    return p && key_eq(p->key(), key) && mapped_eq(p->mapped(), mapped) ? 1 : 0;
  }

  bool includes(const map& other) const {
    check(other);
    return internal::includes(env(), &map::rank, node_, other.node_);
  }

  key_set_type key_set() const {
    return key_set_type(provider_->set_provider(),
                        node_ ? node_->key_node() : nullptr);
  }

  const provider_ptr& provider() const { return provider_; }

  bool empty() const { return !node_; }

  size_t size() const { return internal::size(node_); }

  size_t hash() const { return internal::hash(node_); }

  bool operator==(const map& other) const { return node_ == other.node_; }

  bool operator!=(const map& other) const { return node_ != other.node_; }

 private:
  typedef typename internal::node_ptr<traits> node_ptr;

  map(provider_ptr provider, node_ptr node)
      : provider_(std::move(provider)), node_(std::move(node)) {}

  void check(const map& other) const { assert(provider_ == other.provider_); }

  void check(const key_set_type& other) const {
    assert(provider_->set_provider() == other.provider_);
  }

  void check(const iterator& first, const iterator& last) const {
    assert(provider_ == first.container_->provider_);
    assert(provider_ == last.container_->provider_);
    assert(first.pos_ <= last.pos_);
    assert(last.pos_ <= size());
  }

  bool key_comp(const key_type& lhs, const key_type& rhs) const {
    return provider_->set_provider()->key_comp()(lhs, rhs);
  }

  bool value_comp(const value_type& lhs, const value_type& rhs) const {
    return key_comp(lhs.first, rhs.first);
  }

  bool key_eq(const key_type& lhs, const key_type& rhs) const {
    return provider_->set_provider()->key_eq()(lhs, rhs);
  }

  bool mapped_eq(const mapped_type& lhs, const mapped_type& rhs) const {
    return provider_->mapped_eq()(lhs, rhs);
  }

  bool value_eq(const value_type& lhs, const value_type& rhs) const {
    return key_eq(lhs.first, rhs.first) && value_eq(lhs.second, rhs.second);
  }

  static internal::ranking rank(const env_type& e,
                                const node_type& left,
                                const node_type& right) {
    internal::ranking r = internal::rank(e, left, right);
    if (r == internal::ranking::SAME && !e.equal(left.mapped(), right.mapped()))
      return internal::ranking::NOT_SAME;
    return r;
  }

  env_type env() const { return {provider_.get()}; }

  provider_ptr provider_;
  node_ptr node_;
};

template <class T,
          class Compare,
          class Hash,
          class Equal,
          class MappedHash,
          class MappedEqual>
void swap(map<T, Compare, Hash, Equal, MappedHash, MappedEqual>& x,
          map<T, Compare, Hash, Equal, MappedHash, MappedEqual>& y) {
  x.swap(y);
}

template <class T,
          class Compare,
          class Hash,
          class Equal,
          class MappedHash,
          class MappedEqual>
size_t hash(const map<T, Compare, Hash, Equal, MappedHash, MappedEqual>& x) {
  return x.hash();
}

}  // namespace confluent

#endif  // CONFLUENT_MAP_H_INCLUDED