Sorted List

Overview:

This is yet another class that gives a special type of access to the underlying linked list structure. This time, we make sure the list is sorted and remains sorted. This means, no more inserting before, or after a marker. and no more inserting at the head of the list. There will be one insert function that will insert the items in a sorted manner into the list.

How to start:

Make a copy of your Iterated list and get rid of all the unnecessary functions.

The insert functions needs to be re-written, but thankfully, we already have everything we need in the lower level functions.

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

The list_sorted class:

template <class T>

class List
{
public:
    class Iterator{
    public:
        friend class List;                          //give access to list to
                                                    //          access _ptr
        Iterator(){_ptr = NULL;}                    //default ctor
        Iterator(node<T>* p);
                                                    //Point Iterator to where p
                                                    //  is pointing to
        T &operator*();                             //dereference operator

        T *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<T>* _ptr;                          //pointer being encapsulated
    };

    List(bool order=true, bool unique=false);           //CTOR: default args
                                                        //BIG 3:
    ~List();
    List(const List<T> &copyThis);
    List& operator =(const List& RHS);

    Iterator insert(const T& i);                        //Insert i
    Iterator insert_and_add(const T& i);                //Insert i

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

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

private:
    node<T>* _head_ptr;
    bool _order;
    bool _unique;
    int _size;
};

Note:

A few extras: this class has an _order and a _unique member variable which are initialized via the class constructor. These will have grave effects on the Insert function.

Insert:

There are two things to consider:

1. _order: will the list be sorted in ascending (default) or the descending order?
2. Is the list _unique? If not a unique list, duplicates are allowed. If this is a unique test, we will ADD the new item to the existing one. Obviously, this does not make sence for integer lists. Adding 4 to the existing 4 in the list (and getting an 8) is not reasonable, but with with lists of some other entities, this makes life easier. We'll explore some more flexible ways of dealing with duplicates at a later time
3. Use InsertSorted, or InsertSorted_and_add linked list functions.

_where_this_goes linkedlist function, a review:

_where_this_goes give you the node BEFRORE an item should be inserted in a sorted list depending on whether the list is sorted in ascending or descending order. This function will return a NULL if the item will be inserted at the head of the list.

_insert_sorted linkedlist function, a review:

_insert_sorted will call _where_this_goes and inserts the item either at the head of the list or after the marker returned by the _where_this_goes function.

_insert_sorted_and_add linkedlist function, a review:

This function does the same task as _insert_sorted, except if the marker from _where_this_goes points to a node with the same _item as the item being inserted, the item will be added to the existing _item

Testing:

An Interactive Test Application

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

{73}->[67]->[2]->[16]->[92]->|||
[R]andom [A]fter  [B]efore [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd 

The user will be able to add a random number, choose to add any number, 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.

Sample Run:

Look for 

/*
 * [C]omments like this: (these are added after the program was run)
 */

for explanations on activities in the sample run:

=======================================

{98}->[74]->[60]->[44]->[20]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd r

/*
 * [R]andom inserts a random number to the sorted list and places the cursor on it
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[98]->{94}->[74]->[60]->[44]->[20]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[98]->[94]->[74]->[60]->{52}->[44]->[20]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[98]->[94]->[74]->[60]->[52]->[44]->[20]->{18}->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[98]->[94]->[74]->[60]->[52]->[44]->[20]->[18]->{13}->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd r

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
[98]->[94]->{85}->[74]->[60]->[52]->[44]->[20]->[18]->[13]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd i 45

/*
 * [I]nsert inserts any number to the sorted list and places the cursor on it
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: [98]->[94]->[85]->[74]->[60]->[52]->{45}->[44]->[20]->[18]->[13]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd i 100

/*
 * [I]nsert numbers for edge cases: The head and tail of the list
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: {100}->[98]->[94]->[85]->[74]->[60]->[52]->[45]->[44]->[20]->[18]->[13]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd i3

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: [100]->[98]->[94]->[85]->[74]->[60]->[52]->[45]->[44]->[20]->[18]->[13]->{3}->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd s45

/*
 * [S]earch, as always, places the cursor on the key found in the list or 
 *						leaves the cursor unchanged if key was not found.
 */
..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
: [100]->[98]->[94]->[85]->[74]->[60]->[52]->{45}->[44]->[20]->[18]->[13]->[3]->|||
[R]andom [I]nsert [D]elete [S]earch [P] Previous  [N] Next  [H]ome  [E]nd x

..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..   ..
---------- END ----------------



=======================================
Press <RETURN> to close this window...
 

NOTE:

Please test your class with both ascending and descending order.

You cannot really test your class for the _unique argument yet, but that can wait.