Thread: Hybrid ADT Problem

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    12

    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.

  2. #2
    Registered User
    Join Date
    Nov 2005
    Posts
    12
    nobody has worked with this ADT before?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM