Implementation of Trie in C++

Combo inputs are quite useful and much used in today's gaming models. However, most gaming engines do not have a inbuilt support for Combo input system...

While I researched for a plausible solution, it occurs a 'Trie' (https://en.wikipedia.org/wiki/Trie) is the most suited structure to handle such sequential input! Almost all the articles I found spoke of keeping a list of alphabets with every node, where each item in the list was a node to the children. The downside of this approach is that lists are enumerated as string an string comparison can be hefty especially when there is a plethora of combo inputs that need to be compared in each game iteration.

A Trie on the hand is a slimmer structure so one does not have to iterate through all of them and increasing the complexity of the data structure as the sizeof alphabets increased so we have a linked list instead of the array, a basic vanilla linked list, no std::vectors required.

And of all I wanted to have recursion do the heavy lifting for me not for loops. I could not really find samples using recursion to process a Trie.

Some other links i found did not support double characters. Imagine a combo "XYYXX". Using a Trie helps circumvent this limitation

Hope this helps others wanting to do similar stuff

/** ComboTrieNode.h **/


#pragma once

class ComboTrieNode {
public:
    ComboTrieNode(char key);
    ~ComboTrieNode();
    char key;  //this will be tested
 bool isComplete;  //this is where the combo gets completed


 ComboTrieNode* parent;
 ComboTrieNode* child;
 ComboTrieNode* next;
 ComboTrieNode* prev;

 ComboTrieNode* AddChild(char*);
 ComboTrieNode* FindChild(char);
 ComboTrieNode* Search(char*);
};

/** ComboTrieNode.cpp **/


#include "ComboTrieNode.h"
#include

ComboTrieNode::ComboTrieNode(char key)
{
 this->key = key;
 this->isComplete = false;

 this->next = this->;prev = this-> = this->child = 0;
}


ComboTrieNode::~ComboTrieNode(void)
{
}

ComboTrieNode* ComboTrieNode::AddChild(char* key){
 int length = strlen(key);
 if(length == 0){
  isComplete = true; //this is a full word
  return 0;  //exit condition
 }

 ComboTrieNode* newNode = 0;
 newNode = new ComboTrieNode(key[0]);
 char* suffix = (char*) malloc((length + 1) * sizeof(char));
 memset(suffix, 0, length + 1);
 suffix[length] ='\0';
 strncpy(suffix, key + 1, length);

 /** setup the pointers **/

 if(child == 0){ /** if there are no chidren already, this is going to be a child **/
  child = newNode;
  newNode->parent = this;
 } else {
  /** look for a matchin child **/
  ComboTrieNode* matchingChild= 0;
  matchingChild= FindChild(key[0]);
  if(matchingChild == 0){
   /** go to the end **/
   ComboTrieNode* currentChild = child;
   while(currentChild->next != 0){
    currentChild = currentChild->next;
   }
   currentChild->next = newNode;
   newNode->prev = currentChild;
  } else {
   newNode= matchingChild; /** there was a mathicn child found make that the one from where you want further addition **/
  }
 }
 newNode->AddChild(suffix);



 return newNode;
}

ComboTrieNode* ComboTrieNode::FindChild(char key){
 ComboTrieNode* currentChild = child;
 while(currentChild!= 0){
  if(currentChild->key == key)
   return currentChild;
  currentChild = currentChild->next;
 }
 return currentChild;
}

ComboTrieNode* ComboTrieNode::Search (char* key){
 int length = strlen(key);
 if(length == 0){
  //tokenization
 } else
 {
  ComboTrieNode* found = FindChild(key[0]);
  if(found){
   if(found->isComplete)
    return found;
   else{
    int length = strlen(key);
    char* suffix = (char*) malloc((length + 1) * sizeof(char));
    memset(suffix, 0, length + 1);
    suffix[length] ='\0';
    strncpy(suffix, key + 1, length);
    return found->Search(suffix);
   }
  } else {
   return 0; 
  }
 }
}


/** ComboTrie.h **/


#pragma once
#include "ComboTrieNode.h"
class ComboTrie
{
public:
 ComboTrieNode* pRoot;
 ComboTrie(void);
 ~ComboTrie(void);

 void Insert(char* combo);
 ComboTrieNode* Search(char* combo);
};


/** ComboTrie.cpp **/




#include "ComboTrieNode.h"

ComboTrie::ComboTrie(void) {
 pRoot = new ComboTrieNode('_'); //root node

}


ComboTrie::~ComboTrie(void) {
}

void ComboTrie::Insert(char* combo){
 pRoot->AddChild(combo);
}

ComboTrieNode* ComboTrie::Search(char* combo){
 return pRoot->Search(combo);
}


/** main.cpp **/


#include "ComboTrie.h"
#include "ComboTrieNode.h"

int main(){

 ComboTrie* trie = new ComboTrie();

 /** create a list of combos **/

 trie->Insert("hello");
 trie->Insert("help");
 trie->Insert("be");
 trie->Insert("helpless");
 trie->Insert("helper");

 ComboTrieNode* found =  trie->Search("hadd");

 return 0;

}