Hybrid ADT Problem

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.

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;
}

---

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.

nobody has worked with this ADT before?