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_) {
  impl_iterator current{this};
  for (const_iterator it = ++const_iterator{&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 Key>
void trie<K, V, C>::insert_impl(impl_iterator & out, bool & create, Key && key) {
  auto it = impl_.lower_bound(key);
  if ( it == impl_.end() || key_compare()(key, it->first) ) {
    create = true;
    it = impl_.emplace_hint(it, key, make_value<self_t>());
  }
  out.push({ it, impl_.end() });
}

// 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_impl(KS && keys, Args &&... args) -> std::pair<impl_iterator, bool> {
  impl_iterator it{this};
  bool create{false};
  for ( auto && key : keys ) {
    it.stk.top()->insert_impl(it, create, std::forward<decltype(key)>(key));
  }
  if (create) {
    it.stk.top()->value_ = { std::forward<Args>(args)... };
  }
  return { std::move(it) , create };
}

// 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);
  }
}

namespace detail {
  template <typename Iter, typename Trie, typename KS>
  Iter find_impl(Trie * tr, KS const & keys) {
    Iter rval{tr};
    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>
void swap(trie<K, V, C> & lhs, trie<K, V, C> & rhs) {
  using std::swap;
  swap(lhs.value_, rhs.value_);
  swap(lhs.impl_, rhs.impl_);
}