Bit Trie WIP (Old)

trie.cpp

template <typename T>
class Node
{
  unsigned char*  mPrefix;
  unsigned long   mPrefixBits;
  
  Node* mNodes[2];
  T*    mValue;
  
public:
  Node(void);
  
public:
  Node* FindNode(char const*, unsigned long);
};

Node::Node(void)
: mPrefix(NULL), mPrefixBits(0), mValue(NULL)
{
  this->mNodes[0] = NULL;
  this->mNodes[1] = NULL;
}

Node*
Node::FindNode(char const* aString, unsigned long aDepth)
{
  Node* node;
  
  unsigned long i, l, r;
  unsigned char mask, lShift, rShift;
  
  i = 0;
  l = aDepth + this->mPrefixBits;
  r = 8 - aDepth % 8 - this->mPrefixBits % 8;
  
  for (i = 0; aDepth <= l; i++) {
    lShift = aDepth % 8;
    rShift = aDepth < l - r ? 0 : r;
    aDepth = aDepth + lShift - rShift;
    
    mask = 0xFF >> lShift << rShift;
    
    if (aString[i] & mask != this->mPrefix[i] & mask) {
      return NULL;
    }
  }
  
  if (r == 0) { i++;
    lShift = 7;
    mask = 0x80;
    node = this->mNodes[(aString[i] & mask) >> lShift];
  } else {
    lShift = r - 1;
    mask = 0x01 << lShift;
    node = this->mNodes[(aString[i] & mask) >> lShift];
  }
  
  if (r == 1) { i++; }
  if (node == NULL) {
    return NULL;
  }
  
  return node->FindNode(aString + i, aDepth + 1);
}