I'm trying to make a Trie data structure (school work) and I'm using a list which I've also made myself and works fine (tested) to store the N-nodes in the Trie.
Anyway, the problem is, every node is supposed to store a list of nodes so I can make my N-ary tree/trie but I've hit a snag...
When I'm debugging and going through the for loop, I can see that the currentNode is getting deeper into my tree just fine. However, when I look at it from the perspective of the root, my root only has one linked list containing the first node made in the first iteration of the loop. The consecutive iterations don't register in the NODE in the BRANCH of the ROOT NODE... but it's working in the currentNode, as if they are separate copies even though the currentNode is a pointer to the correct (I hope) node.
Is there something wrong with my code?!? Am I misunderstanding how pointers work?? Help! Thanks.
My node struct.
struct Node {
char letter;
ItemType item;
List<Node> * branches;
};
Node * root;
int size;
My put function.
ItemType put(KeyType newKey, ItemType newItem) {
Node * currentNode = root;
if (isEmpty()) {
//So build a new key
for (int levelIndex = 1; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode->branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode->branches->add(*tempNode);
currentNode = tempNode;
}
//Store
currentNode->item = newItem;
++size;
return NULL; //The former item.
} else {
//Begin
return puttanesca(newKey, newItem, *(currentNode->branches), 1, 1);
}
}
Edit: Oh sorrry, I forgot to pention that puttanesca is a recursive function I'm using to do the traversing and placing of the nodes and stuff. But I haven't really gotten to test that yet, I'm stuck here just trying to add the first key into my empty Trie because of this problem...
More Edits:
Here is puttanesca, I don't think it has anything to do with the problem though but... this is it anyway.
I'm in the midst of changing the List pointer in the Node struct to just an object so some of this stuff might look wrong or it might just be wrong to begin with because I'm not very good with C++ and I've still got problems here but the general concept/algorithm can be seen... Oh and I'm using typedef string KeyType for my key just for some future proofing and a template for ItemType.
ItemType puttanesca(KeyType newKey, ItemType newItem, List<Node> & tempList, int listIndex, int levelIndex) {
Node currentNode = tempList.get(listIndex);
//Am I at the right node? (searching)
if (newKey.at(levelIndex - 1) == currentNode.letter) { //Yes, I am.
//Is this a leaf node?
if (currentNode.branches == NULL) {
//Key does not already exist
if (newKey.length() != levelIndex) {
//So build a new key
for (; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode.branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
}
//Store
currentNode.item = newItem;
++size;
return NULL; //The former item.
} else { //Key matched!
//Replace with new item
ItemType currentItem = currentNode.item;
currentNode.item = newItem;
return currentItem; //which is actually the now old item after the previous statement
}
} else { //Not a leaf, keep going
//Go to the next level and start from the first index
ItemType currentItem = puttanesca(newKey, newItem, currentNode.branches, 1, levelIndex + 1);
if (currentItem == NULL) {
//Key found to be inexistant
//So build a new key - create new sibling
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
//Continue building key - extend sibling
for (++levelIndex; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode.branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
}
//Store
currentNode.item = newItem;
++size;
return NULL; //The former item
} else {
return currentItem; //The former item;
}
}
} else { //Wrong node
if (tempList.getLength() > listIndex) {
return puttanesca(newKey, newItem, tempList, ++listIndex, levelIndex);
} else {//End of the line, chump
return NULL; //Tell parent you failed
}
}
}