mosesdecoder/moses2/InMemoryTrie/InMemoryTrie.h

#pragma once

#include <vector>
#include "Node.h"

namespace Moses2
{

template<class KeyClass, class ValueClass>
class InMemoryTrie
{
public:
  InMemoryTrie() {
  }
  Node<KeyClass, ValueClass>* insert(const std::vector<KeyClass>& word,
                                     const ValueClass& value);
  const Node<KeyClass, ValueClass>* getNode(
    const std::vector<KeyClass>& words) const;
  const Node<KeyClass, ValueClass> &getNode(const std::vector<KeyClass>& words,
      size_t &stoppedAtInd) const;
  std::vector<const Node<KeyClass, ValueClass>*> getNodes(
    const std::vector<KeyClass>& words, size_t &stoppedAtInd) const;
private:
  Node<KeyClass, ValueClass> root;
};

template<class KeyClass, class ValueClass>
Node<KeyClass, ValueClass>* InMemoryTrie<KeyClass, ValueClass>::insert(
  const std::vector<KeyClass>& word, const ValueClass& value)
{
  Node<KeyClass, ValueClass>* cNode = &root;
  for (size_t i = 0; i < word.size(); ++i) {
    KeyClass cKey = word[i];
    cNode = cNode->addSubnode(cKey);
  }
  cNode->setValue(value);
  return cNode;
}

template<class KeyClass, class ValueClass>
const Node<KeyClass, ValueClass>* InMemoryTrie<KeyClass, ValueClass>::getNode(
  const std::vector<KeyClass>& words) const
{
  size_t stoppedAtInd;
  const Node<KeyClass, ValueClass> &ret = getNode(words, stoppedAtInd);
  if (stoppedAtInd < words.size()) {
    return NULL;
  }
  return &ret;
}

template<class KeyClass, class ValueClass>
const Node<KeyClass, ValueClass> &InMemoryTrie<KeyClass, ValueClass>::getNode(
  const std::vector<KeyClass>& words, size_t &stoppedAtInd) const
{
  const Node<KeyClass, ValueClass> *prevNode = &root, *newNode;
  for (size_t i = 0; i < words.size(); ++i) {
    const KeyClass &cKey = words[i];
    newNode = prevNode->findSub(cKey);
    if (newNode == NULL) {
      stoppedAtInd = i;
      return *prevNode;
    }
    prevNode = newNode;
  }

  stoppedAtInd = words.size();
  return *newNode;
}

template<class KeyClass, class ValueClass>
std::vector<const Node<KeyClass, ValueClass>*> InMemoryTrie<KeyClass, ValueClass>::getNodes(
  const std::vector<KeyClass>& words, size_t &stoppedAtInd) const
{
  std::vector<const Node<KeyClass, ValueClass>*> ret;
  const Node<KeyClass, ValueClass> *prevNode = &root, *newNode;
  ret.push_back(prevNode);

  for (size_t i = 0; i < words.size(); ++i) {
    const KeyClass &cKey = words[i];
    newNode = prevNode->findSub(cKey);
    if (newNode == NULL) {
      stoppedAtInd = i;
      return ret;
    } else {
      ret.push_back(newNode);
    }
    prevNode = newNode;
  }

  stoppedAtInd = words.size();
  return ret;
}

}