Need to override '++' for Linked List

Discussion in 'OT Technology' started by Pudge, Nov 11, 2009.

  1. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    Same code as before :o, I just need to know how to properly override the ++ and -- operators for a linked list iterator. Whenever I run the test code, test case #4, I get 146976 for every element instead of 0~29. Maybe thats an address or something? I missed the class that went over that. The code that is involved is in the bold: ListIterator Class, InsertBefore and InsertAfter in List class, and Test #4 in main class
    Code:
    #include <iostream>
    using std::cout;
    using std::endl;
    
    // forward declaration of List class, so ListElement can make 
    // it a friend.  NOTE: If List is a friend of ListElement, that
    // means that the List class has access to the private members
    // of the ListElement class, but no one else does (besides ListElement
    // itself). 
    
    class List;
    class ListIterator;
    
    class ListElement {
     friend class List;
     friend class ListIterator;
     public:
     ListElement(): next(this), prev(this), isHeader(true) {}
     ListElement(int i): item(i), isHeader(false) {}
     ~ListElement() {}  // default destructor
     private:
      int item;
      ListElement *next;    
      ListElement *prev;    
      bool isHeader;
    };
    
    class ListIterator {
     friend class List;
     public:
      ListIterator() : currentPtr(NULL) { }
     [SIZE=3][B] ListIterator operator++(){
                   currentPtr->prev=currentPtr;
                   currentPtr=currentPtr->next;
               currentPtr->next=currentPtr->next->next;              
                   return *this;
                   }  
      ListIterator operator--(){
                   currentPtr->next=currentPtr;
                   currentPtr=currentPtr->prev;
                   currentPtr->prev=currentPtr->prev->prev;
                   return *this;
                   }  
      ListIterator operator++(int){
                   currentPtr->prev=currentPtr;
                   currentPtr=currentPtr->next;                currentPtr->next=currentPtr->next->next;              
                   return *this;
                   }  
      ListIterator operator--(int){
                  currentPtr->next=currentPtr;
                   currentPtr=currentPtr->prev;
                   currentPtr->prev=currentPtr->prev->prev;
                   return *this;
                   }  // advance iterator to the previous list node; return value is iterator *before* advancing[/B][/SIZE]
      int operator*(){
           if(currentPtr->isHeader){
                    printf("error\n");
                    exit(1); 
                    }
            return currentPtr->item;                
          } // return contents pointed to by iterator; print "error\n"
            // and terminate program if iterator refers to header node
     private:
      ListElement *currentPtr;
    };
    
    class List {
      public:
        List(){
               head=new ListElement();
               listSize=0;
               }   // creates an empty list
        ~List(){
        ListIterator *nodePtr, *nextNodePtr;
           nodePtr=new ListIterator();
           nextNodePtr=new ListIterator();
        nodePtr->currentPtr = head;
        while (nodePtr->currentPtr->next != head)
        {
        nextNodePtr->currentPtr = nodePtr->currentPtr->next;
        delete(nodePtr);
        nodePtr = nextNodePtr;
           listSize--;
        }      
                }  // *must* deallocate the entire list
        List(const List &L){
        head=new ListElement();
           ListIterator p;         
           p.currentPtr=L.head;    
           while(p.currentPtr->next!=L.head){
                   p.currentPtr=p.currentPtr->next;
                   this->Append(*p); 
                   }          
                   }  // copy constructor (*must* be a deep copy)
        List & operator =(List &L){
            if(this!= &L){
            head=new ListElement();
                  ListIterator p;         
                  p.currentPtr=L.head;    
                  while(p.currentPtr->next!=L.head){
                   p.currentPtr=p.currentPtr->next;
                   this->Append(*p); 
                   } 
                   }          
                  return *this;      
             }  // *must* (deep) copy list, and must avoid memory leak
    
        // these are functions to set and test the list iterator
        void SetStartList(ListIterator &p) {p.currentPtr = head->next;}
        void SetEndList(ListIterator &p) {p.currentPtr = head->prev;}
        bool IsUndefined(ListIterator p) {return (p.currentPtr == head);}
        bool AtEndList(ListIterator p) {return (p.currentPtr == head);}
        bool AtStartList(ListIterator p) {return (p.currentPtr == head);}
        bool AtFirstNode(ListIterator p) {return (p.currentPtr == head->next);}
        bool AtLastNode(ListIterator p) {return (p.currentPtr == head->prev);}
        // Insert integer at the beginning of the list  
        void Prepend(int it){
             ListIterator p;    
          p.currentPtr=this->head;         
             ListElement *temp= new ListElement(it);  
                  if(this->IsEmpty()){
                                this->head->next=temp;
                    this->head->prev=temp;
                    temp->next=this->head;
                    temp->prev=this->head;   
                                   }   
                else{
                        temp->prev=p.currentPtr;
                        temp->next=p.currentPtr->next;
                        p.currentPtr->next->prev=temp;
                        p.currentPtr->next=temp;
                        p.currentPtr=temp;
                        }
    
                     listSize++;
    }
        // Insert integer at the end of the list
        void Append(int it){
                ListIterator p;
                p.currentPtr=this->head;
             ListElement *temp= new ListElement(it);  
            if(this->IsEmpty()){
                                head->next=temp;
                    head->prev=temp;
                    temp->next=this->head;
                    temp->prev=this->head;   
                                   }         
                else{ 
                        temp->next=p.currentPtr;
                        temp->prev=p.currentPtr->prev;
                        p.currentPtr->prev->next=temp;
                        p.currentPtr->prev=temp;
                        p.currentPtr=temp;
                        }
                     listSize++;
    }
        // Remove first integer from list, return through first parameter.
        // Success is set to true if original list is nonempty, false if empty
        void Pop(int &it, bool &success){
              if(IsEmpty()){
                                 success=false;         
                       }  
              else{
                   success=true;
                   ListElement *temp= new ListElement(); 
                   temp=this->head->next;
                   it=temp->item;
                   temp->next->prev=this->head;
                   this->head->next=temp->next;
                   temp->prev=NULL;
                   temp->next=NULL;
                   }         
            listSize--;
              }    
        // Remove last integer from list, return through first parameter.
        // Success is set to true if original list is nonempty, false if empty
        void Pull(int &it, bool &success){
              if(IsEmpty()){
                                 success=false;         
                       }  
              else{
                   success=true;
                   ListElement *temp= new ListElement(); 
                   temp=this->head->prev;
                   it=temp->item;
                   temp->prev->next=this->head;
                   this->head->prev=temp->prev;
                   temp->prev=NULL;
                temp->next=NULL;
                   } 
            listSize--;        
              }      
        // Get first integer on list, return through first parameter
        // Success is set to true if original list is nonempty, false if empty
        void First(int &it, bool &success){
                       if(IsEmpty()){
                                 success=false;         
                       }       
                       else{    
                       success=true;          
                       ListElement *temp= new ListElement();
                       temp=head->next;
                       it=temp->item;        
                       }
    }
        // Get last integer on list, return through first parameter
        // Success is set to true if original list is nonempty, false if empty
        void Last(int &it, bool &success){
                if(IsEmpty()){
                                 success=false;         
                       }       
                       else{    
                       success=true;          
                       ListElement *temp= new ListElement();
                       temp=head->prev;
                       it=temp->item;        
                       }
    }
        // insert integer before list element referred to by p
        [SIZE=3][B]void InsertBefore(int it, ListIterator p){ //may need to check if 'p' is NULL
             ListElement *temp= new ListElement(it);  
             if(p.currentPtr->prev==head){
                    temp->prev=head;
                    head->next=temp;
                    
                    }   
             else{      
                   temp->next=p.currentPtr->next;
                   
                   temp->prev=p.currentPtr;
                   
             }
             listSize++;
    }
        // insert integer after list element referred to by p
        void InsertAfter(int it, ListIterator p){ //may need to check if 'p' is NULL
             ListElement *temp= new ListElement(it);  
             if(p.currentPtr->next==head){
                    temp->next=head;
                    head->prev=temp;
                    temp->prev=p.currentPtr;
                    p.currentPtr->next=temp;
                    }   
             else{        
                    p.currentPtr->next->prev=temp;
                    temp->next=p.currentPtr->next;
                    p.currentPtr->next=temp;
                    temp->prev=p.currentPtr;
             }
             listSize++;
    }[/B][/SIZE]
        // delete list element referred to by p; print "error\n"
        // and exit if p refers to the header node
        // p is undefined after this function
        void Delete(ListIterator p){
                if(p.currentPtr==head){
                      printf("error\n");
                      exit(1);
                      }                             
                if(p.currentPtr->prev==head){
                     p.currentPtr->next->prev=head;
                     head->next=p.currentPtr->next;
                     p.currentPtr->next=NULL;
                     p.currentPtr->prev=NULL;
                }
                else if (p.currentPtr->next==head){
                     p.currentPtr->prev->next=head;
                     head->prev=p.currentPtr->prev;
                     p.currentPtr->prev=NULL;
                     p.currentPtr->next=NULL;
        }
        else
        {
        p.currentPtr->prev->next=p.currentPtr->next;
        p.currentPtr->next->prev=p.currentPtr->prev;
        p.currentPtr->next=NULL;
        p.currentPtr->prev=NULL;
        }
        listSize--;
        }
        // apply function "func" to each element on the list
        void MapFunction(void (*func)(int &)){
             ListIterator *p= new ListIterator();         
             p->currentPtr=head->next;
             for(int i=0;i<listSize;i++){
               int &value=p->currentPtr->item;
                     func(value);
                     p->currentPtr=p->currentPtr->next;
                     }
    }     
        // returns true if list empty, false otherwise
        bool IsEmpty(){
             if(listSize==0){
             return true;
             }
             return false;
    }
        int GetSize() {return listSize;}
    
        // must print out list elements, one per line
        void Print(){
             ListIterator p;
             p.currentPtr=this->head->next;         
             for(int i=0;i<listSize;i++){
                     cout << p.currentPtr->item << endl;
                     p.currentPtr=p.currentPtr->next;
                     }
    }
      private:
        ListElement *head;
        int listSize;
    };
    void square (int &x);
    
    int main(){
        int i;
        List list;
    
        // Test Case #1
        // Constructor
        // Append
        // Operator =
        // Deconstructor
        // Print
        cout << "Test Case #1."<<endl;
        
        cout << "Constructor"<<endl;
        List *plist = new List();
        
        cout << "Append"<<endl;
        for (i=0;i<30;i++){
            (*plist).Append(i);
        }
        (*plist).Print();    // 0~29
    
        cout << "Operator ="<<endl;
        list = *plist;
        list.Print();        // 0~29
    
        cout << "Deconstructor"<<endl;
        plist->~List();
        (*plist).Print();    // nothing
        list.Print();        // 0~29
    
    
        // Test Case #2
        // Prepend
        // Copy Constructor
        cout << "Test Case #2.\n";
    
        cout << "Prepend"<<endl;
        for (i=0;i<30;i++){
            list.Prepend(i);
        }
        list.Print();    // 29~0 0~29
    
        cout << "Copy Constructor"<<endl;
        List clist(list);
        clist.Print();    // 29~0 0~29
    // Test Case #3
        // First
        // Last
        // Pop
        // Pull
        cout << "Test Case #3."<<endl;
        int item;
        bool success;
        List nlist;
    
        cout << "First"<<endl;
        item = -1;
        success = false;
        list.First(item,success);
        cout << success << endl << item << endl;
        item = -1;
        success = false;
        nlist.First(item,success);
        cout << success << endl << item << endl;
    
        cout << "Last"<<endl;
        item = -1;
        success = false;
        list.Last(item,success);
        cout << success << endl << item << endl;
        item = -1;
        success = false;
        nlist.Last(item,success);
        cout << success << endl << item << endl;
       
        cout << "Pop"<<endl;
        item = -1;
        success = false;
        while (item != 0){
            list.Pop(item,success);
            if (success)cout << item <<endl;
        }
           
        cout << "Pull"<<endl;
        item = -1;
        success = false;
        while (item != 0){
            list.Pull(item,success);
            if (success)cout << item <<endl;
        }
        list.Print();    // nothing;
           // Test Case #4
        // Iterator Operations ++ -- ++(int) --(int)
        // InsertBefore
        // InsertAfter
        // Delete
    
        [SIZE=3][B]cout << "Test Case #4."<<endl;
        ListIterator itr;
    
        cout << "Iterator Operation --"<<endl;
        cout << "InsertBefore"<<endl;
        list.SetStartList(itr);
        for (i=0;i<30;i++){
            list.InsertBefore(i,itr);
            --itr;
        }
        list.Print();    // 29~0
    
        cout << "Iterator Operation ++"<<endl;
        cout << "InsertAfter"<<endl;
        list.SetEndList(itr);
        for (i=0;i<30;i++){
            list.InsertAfter(i,itr);
            
        }
        list.Print();    // 29~0 0~29
    
        cout << "Iterator Operation ++(int)"<<endl;
        cout << "Delete"<<endl;
        list.SetStartList(itr);
        for (i=0;i<30;i++){
            list.Delete(itr++);
        }
    
        list.Print();    // 0~29
    
        cout << "Iterator Operation --(int)"<<endl;
        cout << "Delete"<<endl;
        list.SetEndList(itr);
        for (i=0;i<30;i++){
            list.Delete(itr);
        }
    
        list.Print();    // nothing;[/B][/SIZE]
    // Test Case #5
        // IsEmpty
        // GetSize
        // MapFunction
    
        cout << "Test Case #5."<<endl;
    
        cout << "IsEmpty"<<endl;
        cout << list.IsEmpty()<<endl;
    
        cout << "GetSize"<<endl;
        for (i=0;i<30;i++){
            list.Append(i);
        }
        cout << list.GetSize()<<endl;
    
        cout << "MapFunction"<<endl;
        list.MapFunction(&square);
        list.Print();    // square of 0~29
    /*
        // Test Case #6
        // Iterator Operation *
        cout << "Test Case #6."<<endl;
        
        cout << "Iterator Operation *"<<endl;
        list.SetStartList(itr);
        i = 0;
        while (i < 50){
            cout << *(itr++) <<endl;    // should exit when visit through the list
            i++;
        }
        cout << i << endl;    // should never be accessed
    */
    
    
    }
    /**
     * Function for Mapping Test
     */
    void square(int &x){
        x = x * x;
    }
    
    
     
  2. Krakerjak

    Krakerjak Active Member

    Joined:
    Jul 7, 2003
    Messages:
    8,288
    Likes Received:
    0
    Location:
    Edmonton eh
    That code gives me
    Code:
    First-chance exception at 0x00ec2756 in testit.exe: 0xC0000005: Access violation reading location 0xfeeefef2.
    Unhandled exception at 0x00ec2756 in testit.exe: 0xC0000005: Access violation reading location 0xfeeefef2.
    
    at line 80

    Code:
    class List {
      public:
        List(){
               head=new ListElement();
               listSize=0;
               }   // creates an empty list
        ~List(){
        ListIterator *nodePtr, *nextNodePtr;
           nodePtr=new ListIterator();
           nextNodePtr=new ListIterator();
        nodePtr->currentPtr = head;
        while (nodePtr->currentPtr->next != head)            // line 80 *********
        {
        nextNodePtr->currentPtr = nodePtr->currentPtr->next;
        delete(nodePtr);
        nodePtr = nextNodePtr;
           listSize--;
        }      
                }  // *must* deallocate the entire list
        List(const List &L){
        head=new ListElement();
           ListIterator p;         
           p.currentPtr=L.head;    
           while(p.currentPtr->next!=L.head){
                   p.currentPtr=p.currentPtr->next;
                   this->Append(*p); 
                   }          
                   }  // copy constructor (*must* be a deep copy)
        List & operator =(List &L){
            if(this!= &L){
            head=new ListElement();
                  ListIterator p;         
                  p.currentPtr=L.head;    
                  while(p.currentPtr->next!=L.head){
                   p.currentPtr=p.currentPtr->next;
                   this->Append(*p); 
                   } 
                   }          
                  return *this;      
             }  // *must* (deep) copy list, and must avoid memory leak
    
    
     
  3. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    I'm assuming ListIterator is encapsulating a pointer to a list element and some pointer functionality, and you intend ++ and -- to operate like they do on an array pointer, i.e. "increment" or "decrement" the pointer so it points to the next or previous element in the list.

    If that's the case, why are those operators rearranging the prev and next pointers? Don't you simply want to set currentPtr to currentPtr->next or prev?
     
  4. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    yeah i looked it up and I changed the code to:
    Code:
    ListIterator operator++(){
                   this->currentPtr=this->currentPtr->next;             
                   return *this;
                  
                   }  // advance iterator to the next list node; return value is iterator *after* advancing  
      ListIterator operator--(){
                   this->currentPtr=this->currentPtr->prev;
             return *this;
                   }  // advance iterator to the previous list node; return value is iterator *after* advancing
      ListIterator operator++(int){ 
             ListIterator p=*this;
             p.currentPtr=currentPtr;
                   this->currentPtr=this->currentPtr->next;             
                   return p;
                   }  // advance iterator to the next list node; return value is iterator *before* advancing
      ListIterator operator--(int){
             ListIterator p=*this;
             p.currentPtr=currentPtr;
                   this->currentPtr=this->currentPtr->prev;             
                   return p;
    

    does that look right? I am having some other area I need to debug, but for incrementing and decrementing through a linked list should that work?
     
  5. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    I never had that error. Is it unstable code?
     

Share This Page