I'm working on a project that uses hybrid trie ADT and I'm trying to finish the function Delete and Erase.
Delete is going to delete the d-tuple [x1,x2,x3,x4] from the Set S and Erase will clear all the sets in the Trie trieset[10].
Here is the entire source to get a feel for the program and specifically the functions I"m talking about are towards the bottom.
If anyone could lend me a hand that would be awesome, as you can see this is a very extensive program and these are only beginner functions. If you guys have any suggestions or ideas on improving the current functions that would also be apperciated. Thank you in advanced.Code:#include <iostream> #include <string> #include <math.h> using namespace std; class Trie; class TrieNode; // Global Variables int d; int SA2SL, SL2SA; TrieNode* term; int sw; // CLASS DataNode class DataNode{ private: int value; TrieNode* ptrTrieNode; public: DataNode(int, TrieNode*); int GetValue() {return value;} TrieNode* GetTrieNodePtr() {return ptrTrieNode;} void SetValue(int x) {value = x;} void SetTrieNodePtr(TrieNode* p) {ptrTrieNode = p;} }; DataNode::DataNode(int x = 0, TrieNode* p = 0){ value = x; ptrTrieNode = p; } // CLASS SortedArray class SortedArray { private: int ArraySize; int NumberOfEntries; DataNode* array; public: SortedArray(); ~SortedArray(); bool IsLessQuarterFull(); bool IsFull(); bool IsIn(int& x); void Add(DataNode y); TrieNode* GetTrieNodePtr(int& x); }; SortedArray::SortedArray(){ array = new DataNode[20]; ArraySize = 20; NumberOfEntries = 0; } SortedArray::~SortedArray(){ delete [] array; } bool SortedArray::IsLessQuarterFull() {return ((4*NumberOfEntries) < ArraySize);} bool SortedArray::IsFull() {return ( NumberOfEntries == ArraySize);} bool SortedArray::IsIn(int& x) {int i; for(i=0; i<NumberOfEntries; i++) { if (x <= array[i].GetValue()) if (x == array[i].GetValue()) return true; else return false; } return false; } void SortedArray::Add(DataNode y){ // Works only when adding larger value. array[NumberOfEntries]=y; // Your code should work for all cases. NumberOfEntries++; } TrieNode* SortedArray::GetTrieNodePtr(int& x){ int i; for(i=0; i<NumberOfEntries; i++) { if (x <= array[i].GetValue()) if (x == array[i].GetValue()) return array[i].GetTrieNodePtr(); else return 0; } return 0; } // CLASS SkipNode class SkipNode { private: DataNode element; SkipNode **next; public: SkipNode(DataNode DN, int xsize) {element=DN; next = new SkipNode* [xsize]; } ~SkipNode() { delete [] next; } SkipNode* GetNext(int i) {return next[i];} void SetNext(SkipNode* x, int i) {next[i]=x;} DataNode GetElement() {return element;}; void SetElement(DataNode x) {element=x;}; }; // CLASS SkipList class SkipList { public: SkipList(int largeKey = 10000, int maxElem = 10000, float prob = 0.5); ~SkipList(); int size() {return dSize;} SkipNode* find(int&); bool IsIn(int& x) {if (find(x)== 0) return false; else return true;} void erase(int&); void insert(DataNode&); TrieNode* GetTrieNodePtr(int& x) {if ( IsIn(x) ) return find(x)->GetElement().GetTrieNodePtr(); else return 0;} private: float cutOff; // used to decide level number int level(); // generate a random level number int levels; // max current nonempty chain int dSize; // number of entries in SkipList int maxLevel; // max permissible chain level DataNode tailKey; // a largest possible key SkipNode* search(int x); // search saving last nodes seen // search is more involved than find // search leaves footprint in array last SkipNode* headerNode; // header node pointer SkipNode* tailNode; // tail node pointer SkipNode** last; // last[i] = last node seen on level i }; SkipList::SkipList(int largeKey, int maxElems, float prob) {// Constructor for skip lists with keys smaller than largeKey and // size at most maxElems. 0 < prob < 1. cutOff = prob * RAND_MAX; maxLevel = (int) ceil(logf((float) maxElems) / logf(1/prob)) - 1; levels = 0; // initial number of levels dSize = 0; tailKey.SetValue(largeKey); tailKey.SetTrieNodePtr(0); // create header & tail nodes and last array headerNode = new SkipNode (tailKey, maxLevel + 1); tailNode = new SkipNode (tailKey, 0); last = new SkipNode* [maxLevel+1]; // header points to tail at all levels as lists are empty for (int i = 0; i <= maxLevel; i++) headerNode->SetNext(tailNode,i); } SkipList::~SkipList() { // Delete all nodes and array last. SkipNode *nextNode; // delete all nodes by following level 0 chain while (headerNode != tailNode) {nextNode = headerNode->GetNext(0); delete headerNode; headerNode = nextNode; } delete tailNode; delete [] last; } SkipNode* SkipList::find(int& theKey) {// Return pointer to matching DataNode. // Return NULL if no matching DataNode. if (theKey >= tailKey.GetValue()) return 0; // no matching DataNode possible // position beforeNode just before possible node with theKey SkipNode* beforeNode = headerNode; for (int i = levels; i >= 0; i--) // go down levels // follow level i pointers while (beforeNode->GetNext(i)->GetElement().GetValue() < theKey) beforeNode = beforeNode->GetNext(i); // check if next node has theKey if (beforeNode->GetNext(0)->GetElement().GetValue() == theKey) return beforeNode->GetNext(0); return 0; // no matching DataNode } int SkipList::level() //Should remain unchanged {// Return a random level number <= maxLevel. int lev = 0; while (rand() <= cutOff) lev++; return (lev <= maxLevel) ? lev : maxLevel; } SkipNode* SkipList::search(int theKey) {// Search for theKey saving last nodes seen at each // level in the array last // Return node that might contain theKey. // position beforeNode just before possible node with theKey SkipNode* beforeNode = headerNode; for (int i = levels; i >= 0; i--) { while (beforeNode->GetNext(i)->GetElement().GetValue() < theKey) beforeNode = beforeNode->GetNext(i); last[i] = beforeNode; // last level i node seen } return beforeNode->GetNext(0); } void SkipList::insert(DataNode& theDN) {// Insert theDN into the SkipList. Do nothing // if there is an entry with same key, or key too large. if (theDN.GetValue() >= tailKey.GetValue()) return; // key too large // see if pair with theKey already present SkipNode* theNode = search(theDN.GetValue()); if (theNode->GetElement().GetValue() == theDN.GetValue()) return; // not present, determine level for new node int theLevel = level(); // level of new node // fix theLevel to be <= levels + 1 if (theLevel > levels) { theLevel = ++levels; last[theLevel] = headerNode; } // get and insert new node just after theNode SkipNode* newNode = new SkipNode(theDN, theLevel + 1); for (int i = 0; i <= theLevel; i++) {// insert into level i chain newNode->SetNext(last[i]->GetNext(i),i); last[i]->SetNext(newNode,i); } dSize++; return; } void SkipList::erase(int& theKey) {// Delete the DataNode, if any, whose key equals theKey. if (theKey >= tailKey.GetValue()) // too large return; // see if matching DataNode present SkipNode* theNode = search(theKey); if (theNode->GetElement().GetValue() != theKey) // not present return; // delete node from skip list for (int i = 0; i <= levels && last[i]->GetNext(i) == theNode; i++) last[i]->SetNext(theNode->GetNext(i),i); // update levels while (levels > 0 && headerNode->GetNext(levels) == tailNode) levels--; delete theNode; dSize--; } // CLASS TrieNode class TrieNode { private: int Count; //Count has not been used consistently //in this sample code. Though, in your //code you must set it correctly. public: virtual bool IsIn(int x) = 0; virtual TrieNode* GetNextTrieNode(int x) = 0; virtual void Setsit(int x, TrieNode* p) = 0; virtual int WhatAmI() = 0; int GetCount() {return Count;} int SetCount(int i) {Count=i;} void IncCount() {Count++;} }; class SortedArrayTrieNode: public TrieNode { private: SortedArray* PtrSA; TrieNode* GetNextTrieNode(int x) { return PtrSA->GetTrieNodePtr(x); }; void Setsit(int x, TrieNode* p) { DataNode DN; DN.SetValue(x); DN.SetTrieNodePtr(p); PtrSA->Add(DN); }; bool IsIn(int x) { return PtrSA->IsIn(x); }; int WhatAmI() {return 0;}; public: SortedArrayTrieNode() { SetCount(0); PtrSA = new SortedArray; }; }; class SkipListTrieNode: public TrieNode { private: SkipList* PtrSL; TrieNode* GetNextTrieNode(int x) { return PtrSL->GetTrieNodePtr(x); }; void Setsit(int x, TrieNode* p) { DataNode DN; DN.SetValue(x); DN.SetTrieNodePtr(p); PtrSL->insert(DN); }; bool IsIn(int x) { return PtrSL->IsIn(x); }; int WhatAmI() {return 1;}; public: SkipListTrieNode() { SetCount(0); PtrSL = new SkipList; }; }; class TinyTrieNode: public TrieNode { private: TrieNode* GetNextTrieNode(int x) {return 0;}; void Setsit(int x, TrieNode* p) {return;}; bool IsIn(int x) {return false;}; int WhatAmI() {return 2;}; public: TinyTrieNode() { SetCount(1);}; // This count is set correctly }; // CLASS Trie class Trie { public: Trie() { ctr = 0; tiny = new TinyTrieNode; root = tiny; }; void Init(int a); void Fill(int a); bool Member(int x[]); private: TrieNode *root; TrieNode *tiny; int ctr; }; void Trie::Init(int a){ switch (a) { case 0 : { root = new SortedArrayTrieNode; break; } case 1 : { root = new SkipListTrieNode; break; } case 2 : { if (sw == 1) {root= new SortedArrayTrieNode; sw = 0;} else {root= new SkipListTrieNode; sw = 1;} break; } } root->SetCount(0); }; void Trie::Fill(int a){ TrieNode* cur; int numelem, x[d]; cout << endl; cout << "num of input vectors" << endl; cin >> numelem; for ( int j = 1 ; j <= numelem ; j = j + 1 ) { cout << "Input Test Vector" << endl; cin >> x[0] >> x[1] >> x[2] >> x[3] ; cout << x[0] << " " << x[1] << " " << x[2] << " " << x[3] << endl; cur = root; for(int i=0; i<d; i++) {if (cur->IsIn(x[i])) { cur = cur->GetNextTrieNode(x[i]);} else { if (i != d-1) { TrieNode* r; switch (a) {case 0 : r = new SortedArrayTrieNode; break; case 1 : r = new SkipListTrieNode; break; case 2 : {//sw is used for testing this sample // code. In your code the decision of the // type of node to be used depends on SL2SA // and SA2Sl. if (sw == 1) {r = new SortedArrayTrieNode; sw = 0;} else {r = new SkipListTrieNode; sw = 1;} break;} } cur->Setsit(x[i],r); cur = r; } else { cur->Setsit(x[i],term); cur = term; } } } } } bool Trie::Member(int x[]) { TrieNode *current = root; for(int i = 0; i<d; i++) { if ( current->IsIn(x[i]) ) current = current->GetNextTrieNode(x[i]); else return false; } return true ; } /* Delete Function */ void Trie::Delete(int x[]) { TrieNode *current = root; if(Delete(x,0,current)) { if(root->Count == 1) { delete root; root = tiny; } } else cout << "Error with 1st Delete" << endl; } bool Trie::Delete(int x[], int dept, TrieNode *current) { if(current->GetNextTrieNode(x[dept]) != NULL) { if(current->GetNextTrieNode(x[dept]) == tiny) { if(x[dept+1] == '\0') { current->Setsit(x[dept],tiny); return true; } } } else cout << "Error with 2nd Delete" << endl; } /* Erase Function */ void Trie::Erase(int x[]) { TrieNode *current = root; for(int i = 0; i < d; i++) { if((current->IsIn(x[i])) && (current->GetNextTrieNode(x[i+1])) != NULL) current = current->GetNextTrieNode(x[i]); else if(!(current->IsIn(x[i]))) break; else delete current; } ctr--; root = tiny; }
