Trie WIP

trie.cpp

#include "trie.h"

template <typename T> Trie<T>::Node&
Trie<T>::Node::operator [](char const* aString)
{
  Node* node;
  
  unsigned long s, e, i, n;
  unsigned char r, l, c, d;
  
  s = this->mOffset;
  e = this->mOffset + this->mLength;
  
  i = s / 8, r = s % 8;
  n = e / 8, l = e % 8, l = 8 - l;
  
  for (c = aString[i] & 0xFF >> r; i <= n; c = aString[++i]) {
    if (i == n) { c >>= l, c <<= l; }
    if (d = c ^ this->mPrefix[i]) {
      this->Fork(i, d);
      
      e = this->mOffset + this->mLength;
      n = e / 8, l = e % 8, l = 8 - l, l %= 8;
    }
  }
  
  if (c = aString[n], c == '\0') {
    return *this;
  }
  
  node = this->mNodes[c >> l - 1 & 0x01];
  node = node != 0 ? node : new Node(*this);
  
  return (*node)[aString + n];
}

#if 0 /* Matching Only */
template <typename T> bool
Trie<T>::Node::Match(char const* aString)
{
  unsigned long i, n, s;
  unsigned char m, l, r;
  
  s = this->mDepth / 8;
  r = this->mDepth % 8;
  m = 0xFF >> r;
  
  /* this->mLock.AcquireRead() */
  
  n = this->mLength / 8;
  l = this->mLength % 8, l = 8 - r - l;
  
  for (i = 0; i <= n; i++) {
    if (i == n) { m <<= l; }
    if (aString[s + i] & m != this->mPrefix[i] & m) {
      /* this->mLock.Release() */
      
      return false;
    }
  }
  
  /* this->mLock.Release() */
  
  return true;
}
#endif

trie.h

#pragma once
#ifndef trie_h_
#define trie_h_

template <typename T>
class Trie
{
  TrieNode mRoot;
  
private:
  typedef T Type;
  
private:
  class Node
  {
    unsigned char*      mPrefix;
    unsigned long       mLength;
    unsigned long const mDepth;
    
    Node* mParent; /* I may put this inside of mNodes... */
    Node* mNodes[2];
    Type* mValue;
    
  private:
    friend class Trie;
    
  private:
    Node(void);
    Node(Node const&);
    
  private:
    virtual ~Node(void);
    
  private:
    Node& operator [](char const* aString);
  }
  
public:
  Trie(void);
  
public:
  virtual ~Trie(void);
  
public:
  Type& operator [](char const*);
};

#endif/*trie_h_*/