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 = ++other.begin(), end = {}; it != end; ++it) {
    while (current.keys.size() >= it.keys.size()) {
      current.pop();
    }
    auto tmp = current.root().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.root().insert_impl(it, create, std::forward<decltype(key)>(key));
  }
  if (create) { it.root().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.root().clear();
  if (!it.iters.empty()) {
    auto to_erase = it.iters.top().current();
    it.pop();
    it.root().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.root().impl_;
      auto it = top.find(key), end = top.end();
      if (it == end) { return {}; }
      rval.push({it, end});
    }
    return rval;
  }
}