Lab 6: Linked List Iterator

Objectives

Linked List Class

• The list class has a dummy head and tail: that is, the first node and last node do not hold meaningful data. Instead, they hold the address of the first and last actual nodes.
• The list class has an embedded node class. The node class has simply a public next, prev, and element.
• The list class has an embedded iterator class.
  • The iterator class has a pointer to the list it is working on.
  • The iterator class has a pointer to the current node.
  • Because iterator is embedded, it can access any private data in the linked list class.
  • The iterator can be forward and start after the dummy head or reverse and start before the dummy tail.

Assignment

iterator class

1. Write both const iterator& operator--(int); and const iterator& operator--(int); functions. The int parameter is simply to specify that this is the post increment function. If the direction of the iterator is forward, you should go to next. Otherwise go to prev. Don't allow incrementing past the head or tail.
2. Once you have the above forward iterators completed, provide two additional iterator classes:

           class const_reverse_iterator : public const_iterator
   	{
   	...
   	}
           class reverse_iterator : public const_iterator
   	{
   	...
   	}
   	

   These are reverse iterators, meaning that they start at the node just before the end() node, and when incremented, they go backwards...the reverse of the forward iterators.
3. Provide the following iterator functions:

           iterator               begin();			// first node mutator
           const_iterator         begin() const;           // first node accessor
           iterator               end();			// tail node mutator
           const_iterator         end() const;		// tail node accessor
           
           reverse_iterator       rbegin();                // last node mutator
           const_reverse_iterator rbegin() const;          // last node accessor
           reverse_iterator       rend();                  // head node mutator
           const_reverse_iterator rend() const;            // head node accessor
   
           iterator        insert(iterator, const T&);	// before iterator
           iterator        erase(iterator);		// at iterator
           iterator        erase(iterator, iterator);	// iterator range
   	

list class

1. Provide the following list_t public member functions:

           int             size() const;			// size of list
           bool            empty() const;			// list empty?
           void            clear();			// nuke all elements
   
           T&              front();                        // front data mutator
           const T&        front() const;                  // front data accessor
           T&              back();                         // back data mutator
           const T&        back() const;                   // back data accessor
           iterator        push_front(const T& o);         // insert at front
           iterator        push_back(const T& o);          // insert at end
           iterator        pop_front();                    // nuke front node
           iterator        pop_back();                     // nuke back node
   	

main.cpp driver

1. Your program should produce the sample output with the following driver program:

   #include <iostream>
   #include <cstdlib>
   #include <sys/time.h>
   
   #include "list.h"
   #include "pairs.h"
   
   int        main();
   void       insert(list_t<pairs_t>& plist, pairs_t pair);
   
   int main()
   {
           int                             num;
           list_t<int>                     list;
           list_t<int>::iterator           itr;
           list_t<int>::reverse_iterator   ritr;
           list_t<pairs_t>                 plist;
   
           struct timeval                  tp;
   
     // get time of day
     gettimeofday(&tp,NULL);
   
     // use microseconds as the seed
   //srand((unsigned int)tp.tv_usec);
     srand((unsigned int)1337);
   
     // sort while inserting, thus maintaining list as priority queue
     std::cout << "Inserting:" << std::endl;
     for(int i=0;i<10;i++) {
       num = static_cast<int>((float)rand()/(float)RAND_MAX*100.0);
       std::cout << num << " ";
       for(itr = list.begin(); itr != list.end() && num > *itr; ++itr);
       list.insert(itr,num);
     }
     std::cout << std::endl;
   
     std::cout << "list_t (front to back):" << std::endl;
     for(list_t<int>::iterator itr = list.begin(); itr != list.end(); ++itr)
       std::cout << *itr << " ";
     std::cout << std::endl;
   
     std::cout << "list_t (back to front, using operator--):" << std::endl;
     for(list_t<int>::iterator itr = --list.end(); itr != --list.begin(); --itr)
       std::cout << *itr << " ";
     std::cout << std::endl;
   
     std::cout << "list_t (back to front, using reverse_iterator):" << std::endl;
     for(ritr = list.rbegin(); ritr != list.rend(); ++ritr)
       std::cout << *ritr << " ";
     std::cout << std::endl;
   
     ///////////
   
     insert(plist,pairs_t(45.0,'b'));
     insert(plist,pairs_t(37.2,'c'));
     insert(plist,pairs_t(42.6,'a'));
     insert(plist,pairs_t(53.7,'d'));
   
     std::cout << "list_t (front to back):" << std::endl;
     for(list_t<pairs_t>::iterator pitr = plist.begin(); pitr != plist.end(); ++pitr)
       std::cout << *pitr << " ";
     std::cout << std::endl;
   
     std::cout << "list_t (back to front):" << std::endl;
     for(list_t<pairs_t>::reverse_iterator pitr = plist.rbegin(); pitr != plist.rend(); ++pitr)
       std::cout << *pitr << " ";
     std::cout << std::endl;
   }
   
   void insert(list_t<pairs_t>& plist, pairs_t pair)
   {
           list_t<pairs_t>::iterator        pitr;
   
     // sort while inserting, thus maintaining list as priority queue
     std::cout << "Inserting: " << pair << std::endl;
     for(pitr = plist.begin(); pitr != plist.end() && pair > *pitr; ++pitr);
       plist.insert(pitr,pair);
   }
   

sample output

Inserting:
1 86 24 21 30 74 89 64 21 68 
list_t (front to back):
1 21 21 24 30 64 68 74 86 89 
list_t (back to front, using operator--):
89 86 74 68 64 30 24 21 21 1 
list_t (back to front, using reverse_iterator):
89 86 74 68 64 30 24 21 21 1 
Inserting: ('b',45)
Inserting: ('c',37.2)
Inserting: ('a',42.6)
Inserting: ('d',53.7)
list_t (front to back):
('a',42.6) ('b',45) ('c',37.2) ('d',53.7) 
list_t (back to front):
('d',53.7) ('c',37.2) ('b',45) ('a',42.6) 

Turn in

1. A README file containing
   1. Course id--section no
   2. Name
   3. Lab description
   4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
   5. Lessons learned, identified interesting features of your program
   6. Any special usage instructions
2. Makefile
3. source code (.h headers and .cpp source)
4. object code (do a make clean before tar)

How to hand in