cpp-trie/trie_impl.hpp

//
//  trie_impl.hpp
//  trie
//
//  Created by Sam Jaffe on 6/16/17.
//

#pragma once

#include "trie.hpp"
#include "trie_iterator.hpp"

// n := total elements
// d := average depth
// Stack: O(1)
// Operations: O(n)
template <typename K, typename V, typename C>
trie<K, V, C>::trie(trie const & other) : value_(other.value_) {
  iterator current{this};
  for (const_iterator it = ++other.begin(), end = other.end(); it != end; ++it) {
    while (current.keys.size() >= it.keys.size()) { current.pop(); }
    auto tmp = current.stk.top()->insert(it.keys.back(), *it).first;
    current.push(tmp.iters.top());
  }
}

template <typename K, typename V, typename C>
auto trie<K, V, C>::operator=(mapped_type const & value) -> self_t & {
  value_ = value;
  return *this;
}

template <typename K, typename V, typename C>
auto trie<K, V, C>::operator=(trie const & other) -> self_t & {
  trie tmp{other};
  swap(*this, tmp);
  return *this;
}

template <typename K, typename V, typename C>
auto trie<K, V, C>::operator=(trie && other) -> self_t & {
  swap(*this, other);
  return *this;
}

// n := total elements
// d := average depth
// Operations: O(log(n)/d)
template <typename K, typename V, typename C>
template <typename... Args>
void trie<K, V, C>::insert_impl(std::pair<iterator, bool> & out, key_type const & key, Args &&... args) {
  auto it = impl_.lower_bound(key);
  if ( it == impl_.end() || key_compare()(key, it->first) ) {
    out.second = true;
    it = impl_.emplace_hint(it, key, make_value<self_t>(std::forward<Args>(args)...));
  }
  out.first.push(make_end_aware_iterator(it, impl_.end()));
}

// n := total elements
// d := average depth
// Operations: O(log(n))
template <typename K, typename V, typename C>
template <typename KS>
auto trie<K, V, C>::insert(KS const & keys, mapped_type const & value) -> std::pair<iterator, bool> {
  std::pair<iterator, bool> rval{this, false};
  for ( key_type const & key : keys ) {
    rval.first.stk.top()->insert_impl(rval, key);
  }
  if (rval.second) { *rval.first.stk.top() = value; }
  return rval;
}

// n := total elements
// d := average depth
// Operations: O(log(n))
template <typename K, typename V, typename C>
template <typename KS, typename... Args>
auto trie<K, V, C>::emplace(KS const & keys, Args &&... args) -> std::pair<iterator, bool> {
  std::pair<iterator, bool> rval{this, false};
  for ( key_type const & key : keys ) {
    rval.first.stk.top()->insert_impl(rval, key);
  }
  if (rval.second) { rval.first.stk.top()->value() = {std::forward<Args>(args)...}; }
  return rval;
}

template <typename K, typename V, typename C>
template <typename KS>
auto trie<K, V, C>::find(KS const & keys) -> iterator {
  iterator rval{this};
  for (auto & key : keys) {
    auto & top = rval.stk.top()->impl_;
    auto it = top.find(key), end = top.end();
    if ( it == end ) { return {}; }
    rval.push({it, end});
  }
  return rval;
}

template <typename K, typename V, typename C>
auto trie<K, V, C>::find(key_type const & key) -> iterator {
  auto it = impl_.find(key), end = impl_.end();
  if ( it == end ) { return {}; }
  iterator rval{this};
  rval.push({it, end});
  return rval;
}

// n := total elements
// d := average depth
// Stack: O(1)
// Operations: O(n)
template <typename K, typename V, typename C>
void trie<K, V, C>::clear() {
  for (reverse_iterator it = rbegin(), end = rend(); it != end && !it.iters.empty(); ++it) {
    auto ptr = std::move(it.iters.top()->second);
    ptr->impl_.clear();
  }
  value_ = mapped_type{};
  impl_.clear();
}

template <typename K, typename V, typename C>
void trie<K, V, C>::drop(iterator it) {
  if (it == end()) return;
  it.stk.top()->clear();
  if (!it.iters.empty()) {
    auto to_erase = it.iters.top().current();
    it.pop();
    it.stk.top()->impl_.erase(to_erase);
  }
}