Assignment: 13_07_iterated

One major problem with our simple list class is the fact that functions in the list class give up pointers to nodes within the list. This is an abomination. It goes against every principle of abstraction and encapsulation.

Iterators:

Iterators are classes that encapsulate pointers. We wrap a pointer we want protected in an Iterator and in doing so, we control how the pointer will be used and in what context and we decide what to allow and disallow in the use of this pointer.

Once the Iterator is in place, we will not be thinking of pointers, only Iterators. Iterators allow you to traverse data structures (such as linked lists) safely and without worrying about the calling function altering the nodes because they only get an iterator, and not a pointer.

Nested Classes:

The Iterator Class:

The Iterator class is a nested class within our List class. It provides a constructor, an increment, insertion, dereference and member access operators.

The List Class:

Just like the simple list class, a node pointer called head (head_ptr would be better) points to the first node in the list.

The list class provides all the functions that the simple list provided, but it will wrap all node pointers (passed as arguments, or returned from the functions) in an Iterator object:

NOTE: Define all your Iterator functions INLINE: Inside the Iterator class itself.

template <class ITEM_TYPE>
class List
{
public:
    class Iterator{
    public:
        friend class List;                              //give access to list to access _ptr
        Iterator();                                     //default ctor
        Iterator(node<ITEM_TYPE>* p);                   //Point Iterator to where p is pointing to
        operator bool();                                //casting operator: true if _ptr not NULL
                                                        //      this turned out to be a pain!


        ITEM_TYPE& operator *();                        //dereference operator
        ITEM_TYPE* operator ->();                       //member access operator

        bool is_null();                                 //true if _ptr is NULL

        friend bool operator !=(const Iterator& left,
                                const Iterator& right); //true if left != right

        friend bool operator ==(const Iterator& left,
                                const Iterator& right); //true if left == right

        Iterator& operator++();                         //member operator: ++it; or ++it = new_value

        friend Iterator operator++(Iterator& it,
                                   int unused);         //friend operator: it++

    private:
        node<ITEM_TYPE>* _ptr;                          //pointer being encapsulated
    };      List();                                                     //CTOR
                                                                //BIG 3:
    ~List();
    List(const List<ITEM_TYPE> &copyThis);
    List& operator =(const List& RHS);

    //int size();
    Iterator insert_head(ITEM_TYPE i);                           //insert at the head of list
    Iterator insert_after(ITEM_TYPE i,
                                          Iterator iMarker);    //insert after marker
    Iterator insert_before(ITEM_TYPE i,
                                           Iterator iMarker);   //insert before marker
    Iterator insert_sorted(ITEM_TYPE i);                         //insert in a sorted list

    ITEM_TYPE Delete(List<ITEM_TYPE>::Iterator iMarker);        //delete node pointed to by marker
    void Print() const;
    Iterator search(const ITEM_TYPE &key);                      //return Iterator to node [key]
    Iterator prev(Iterator iMarker);                            //previous node to marker

    ITEM_TYPE& operator[](int index);                           //return item at position index
    Iterator begin() const;                                     //Iterator to the head node
    Iterator end() const;                                       //Iterator to NULL
    Iterator last_node() const;                                  //Iterator to the last node
    bool empty()const {return _head_ptr == NULL;}
    template <class U>                                          //Note the template arg U
    friend ostream& operator <<(ostream& outs, const List<U>& l);
    int size()const { return _size; }

private:
    node<ITEM_TYPE>* _head_ptr;
    int _size;
}

An Interactive Test Application

You will create an interactive application that will create a list with five random numbers, show it, and present the following menu to the user:

The user will be able to add a random number after the current position (marked by braces), insert a number before or after the current position, delete the node at the current position, search for an item that may be in the list, or navigate the current position to the next or previous node, or to go to the home position, or the end of the list. (I will be so proud of you if you simply copy the test function from your Simple List assignment and paste and use it here. Very few modifications: just change the class to list_iterated and change your cursor and other pointers to Iterators of the iterated_list class. The reset will remain the same.)

Note: The cursor position is maintained in the test function and NOT in the List class. The posiiton of the cursor is shown by a pair of braces '{ }' and it will be adjusted appropriately as operations are executed. Deleting a node will cause the cursor position to be set to the beginning of the list. (Why is that?)

Sample Run:

I will not put these comments for this run since you have seen them all in the Simple List assignment. In fact this will be a very minimal run. But be sure to test this class thoroughly.

Iterated List

Iterators:

Nested Classes:

The Iterator Class:

The List Class:

An Interactive Test Application

Sample Run: