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"

template <typename K, typename V, typename C>
trie<K, V, C>::trie(mapped_type const & value)
: value_(value) {
  
}

// 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>
trie<K, V, C>::~trie() {
  clear();
}

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

// n := total elements
// d := average depth
// Operations: O(d*log(n/d))
template <typename K, typename V, typename C>
template <typename KS, typename>
auto trie<K, V, C>::operator[](KS const & keys) -> self_t & {
  self_t * rec = this;
  for ( key_type const & key : keys ) {
    rec = &(*rec)[key];
  }
  return *rec;
}

// n := total elements
// d := average depth
// Operations: O(log(n))
template <typename K, typename V, typename C>
auto trie<K, V, C>::operator[](key_type const & key) -> self_t & {
  auto it = impl_.lower_bound(key);
  if ( it == impl_.end() || key_compare()(key, it->first) ) {
    it = impl_.emplace_hint(it, key, make_value<self_t>());
  }
  return *(it->second);
}

// n := total elements
// d := average depth
// Operations: O(d*log(n/d))
template <typename K, typename V, typename C>
auto trie<K, V, C>::operator[](std::initializer_list<key_type> keys) -> self_t & {
  self_t * rec = this;
  for ( key_type const & key : keys ) {
    rec = &(*rec)[key];
  }
  return *rec;
}

template <typename K, typename V, typename C>
template <typename KS>
auto trie<K, V, C>::insert(KS const & keys, mapped_type const & value) -> void {
  operator[](keys) = value;
}

template <typename K, typename V, typename C>
auto trie<K, V, C>::insert(std::initializer_list<key_type> keys, mapped_type const & value) -> void {
  operator[](keys) = value;
}

// n := total elements
// d := average depth
// Operations: O(log(n))
template <typename K, typename V, typename C>
auto trie<K, V, C>::insert(key_type const & key, mapped_type const & value) -> std::pair<iterator, bool> {
  std::pair<iterator, bool> rval{this, false};
  auto it = impl_.lower_bound(key);
  if ( it == impl_.end() || key_compare()(key, it->first) ) {
    rval.second = true;
    it = impl_.emplace_hint(it, key, make_value<self_t>(value));
  }
  rval.first.push(make_end_aware_iterator(it, impl_.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();
}