template class Queue ...inherits from a base list class (with iter's and isort)

[David]

An interesting C++ student queue problem that illustrates inheritance from a template class list  ... ( also an insertion sort of a short queue/list ... and iterators via template class Iter )

Code: [Select]

// classQueue_test2.cpp //

// an interesting C++ student 'queue' problem that illustrates inheritance from
// a template class list  ... ( and insertion sort of a short queue/list ... and
// ... iterators via template class Iter )

/*
    A student has an assignment to create a Queue class that uses inheritance,
    given the base class as a supplied starting point ... a template
    LinkedList class and Node class...
   
    Your Queue class, aa all the other classes, are to be template classes.

    Your test program first creates a queue object to hold customer names that
    are waiting in line for service.
   
    Comment your code where appropriate, paying particular attention to any
    functions called in the test program.

(1) Display a heading like ...
        Author: Your Name
        Program title: Your Program Title
(2) Prompt and accept user input for customer names to be placed in the queue:
    "Jane", "Bob", "Nancy", "Tom", "Julie", "Joe"
(3) Display the names of the customers waiting in line;
(4) Identify and process the next three people in line; i.e. display and remove
    the first three names in the queue ... (using the Linked List member
    functions that were inherited from the base class)
(5) Add the following names to the end of the queue
        Lara
        Andrew
(6) Add/insert "Wendy" as the 3rd node in the queue/list
(7) Display the new queue/list from head to tail ... same as (3) above.
(8) Display the name of the next customer in line to be served.

*/

#include <iostream>
#include <string>
using namespace std;


// set to '2 'or '1' and recompile to use LinkedList_iter.h or LinkedList.h
#define use_given_h 2


#if( use_given_h == 2 )
  #define text "linkedlist_iter.h"
  #include text
#else
  #define text "linkedlist.h"
  #include text
#endif


#ifndef QUEUE_H
#define QUEUE_H

template< typename T >
class Queue : public List< T >
{
public:
    Queue() : List< T >() { cout << "Queue ctor called ...\n"; } // call list default ctor
     ~Queue() { cout << "Queue dtor called ...\n"; } // dtor ...

    T dequeue(); // pop list ...
    void enqueue( T element ); // push_back list ...
    void show() const;
    void show( int n ) const;
};

template< typename T >
void Queue< T >::enqueue( T element ) { push_back( element ); }

template< typename T >
T Queue< T >::dequeue() { return this->pop_front(); }

template< typename T >
void Queue< T >::show() const
{
#if( use_given_h < 2 )
    Node< T >* cur = this->head;
    for( int i = 0; cur != NULL; cur = cur->next )
        cout << ++i << ": " << cur->element << endl;
#else
    Iter< T > it;
    int i = 0;
    for( it = this->begin(); it != this->end(); ++it )
        cout << ++i << ": " << *it << endl;
#endif
}

template< typename T >
void Queue< T >::show( int n ) const
{
#if( use_given_h < 2 )
    Node< T >* cur = this->head;
    int i;
    for( i = 0; cur != NULL && i < n; cur = cur->next )
        cout << ++i << ": " << cur->element << endl;
    if( cur == NULL && i < n ) cout << "Only " << i << " in queue ...\n";
#else
    Iter< T > it;
    int i = 0;
    for( it = this->begin(); it != this->end() && i < n; ++it )
        cout << ++i << ": " << *it << endl;
    if( it == this->end() && i < n ) cout << "Only " << i << " in queue ...\n";
#endif
}

#endif // #ifndef QUEUE_H

void wait( const string& prompt )
{
    cout << prompt << flush;
    string dummy;
    getline( cin, dummy );
}

void testItOut()
{
    // construct an empty Queue object ...
    Queue < string > q;
    wait( "\nPress 'Enter' to continue ... " );
   
    // for this simple test program, initial names supplied via an array of names
    const string ary[] = { "Jane", "Bob", "Nancy", "Tom", "Julie", "Joe" };
    for( size_t i = 0; i < sizeof ary/sizeof ary[0]; ++i )
    {
        //cout << "Enter name " << i+1: << ": " << flush;
        //string tmp;
        //getline( cin, tmp );
        //q.enqueue( tmp );
        q.enqueue( ary[i] ); // add names to end of queue ... (end of list)
    }
   
    cout << "Author : Name" << endl;
    cout << "Title  : Queue and Linked List Test Program" << endl;
    cout << "===========================================" << endl;

    cout << "Showing initial queue ...\n";
    q.show();

    cout << "Removing/showing first 3 from queue now ...\n";
    int i = 0, count = 3;
    while( count-- && q.get_size() )
        cout << "Remove " << ++i << ": " << q.pop_front() << endl;

    q.push_back( "Lara" ); // adding at end ... (i.e. ... push_back)
    q.push_back( "Andrew" );

    q.insert( 3, "Wendy" ); // insert at position 3 ...
    cout << "After 2 push_back's & inserting 'Wendy' at 3rd position, the queue is ...\n";
    q.show();

    cout << "Showing the next customer to be served ...\n";
    cout << q.get_front();
    wait( "\n\nPress 'Enter' to continue ... " );

    // added ...

    cout << "\nShowing the next 10 customers to be served ...\n";
    q.show( 10 );
    wait( "\nPress 'Enter' to continue ... " );
    cout << endl;

    cout << "Showing the next customers to be served in sorted order ...\n";
    q.isort();
    q.show();
    //wait( "\nPress 'Enter' to continue ... " );
    q.insert_sorted( "Mariam" );
    cout << "\nShowing added customer 'Mariam' to be served in sorted order ...\n";
    q.show();
    wait( "\nPress 'Enter' to continue ... " );
    q.insert_sorted( "Adam" );
    cout << "\nShowing added customer 'Adam' to be served in sorted order ...\n";
    cout << "The first in queue now is: " << q.get_front() << endl
         << "The last  in queue now is: " << q.get_back() << endl;
    q.insert_sorted( "Zoe" );
    cout << "\nShowing added customer 'Zoe' to be served in sorted order ...\n";
    cout << "The first in queue now is: " << q.get_front() << endl
         << "The last  in queue now is: " << q.get_back() << endl;
    wait( "\nPress 'Enter' to continue ... " );
   
    cout << "\nTraversing queue with Node pointer ... \n";
    Node< string >* p  = q.get_head();
    for( ; p != NULL; p = p->get_next() )
        cout << p->get_element() << " ";
    cout << endl << endl;
#if ( use_given_h == 2 )
    cout << "Traversing queue with Iter ...\n";
    Iter< string > it = q.begin();
    for( ; it != q.end(); ++it )
        cout << *it << " ";
    cout << "\n\nIn sorted order now ... ";
#endif

    cout << "Serving the last " << q.get_size() << " customers ... \n";
    i = 0;
    while( q.get_size() )
        cout << "Remove " << ++i << ": " << q.pop_front() << endl;
    wait( "\nAll done!  Press 'Enter' to continue ... " );
}

int main()
{
    cout << "Using ... " << text << endl << endl;
   
    testItOut();

    wait( "\nPress 'Enter' to exit ... " );
}


[David]

These next 2 files are used by the above demo program, that tests out class Queue ...

Code: [Select]

// linkedlist.h //

#ifndef LIST_H
#define LIST_H
#include <stdexcept>


// forward declarations here so can be recognized in template class Node
// and given friend class status there ...
template < typename T > class List;
template < typename T > class Queue;


template<typename T>
class Node
{
    friend class List < T >; // give List access to all of class Node
    friend class Queue< T >; // give Queue access to all of class Node
public:
    Node() : element(T(0)), next(NULL) {} // No-arg (default) ctor
    Node( T element ) : element(element), next(NULL) {} // 1-arg ctor
    Node< T >* get_next() { return next; }
    T get_element() { return element; }
private:
    T element;
    Node< T >* next;
};


template < typename T >
class List // fixed up and trimmed to members applicable here ...
{
public:
    List() : head(NULL), tail(NULL), size(0) { cout << "List ctor called ...\n"; }
    virtual ~List() { clear(); cout << "List dtor called ... all clear now.\n"; }

    List( const List< T >& obj ) // copy ctor ...
    {
        head = tail = NULL;
        size = 0;
        for( Node< T >* p = obj.head; p != NULL; p = p->next )
            push_back( p->element );
    }
    List& operator= ( const List< T >& obj ) // overloaded assignment operator
    {
        if( this != &obj )
        {
            clear();
            for( Node< T >* p = obj.head; p != NULL; p = p->next )
                push_back( p->element );
        }
        return *this;
    }

    void push_front( T );
    void push_back( T );
    void insert( int, T ); // at int position 1..n (Note: not using index 0..n-1)
    void clear();
    int get_size() const { return size; }
    T get_front() const;
    T get_back() const;
    T pop_front();
    T pop_back();
   
    Node< T >* get_head() { return head;}

    void insert_sorted( T );
    void isort();

protected:
    Node < T >* head;
    Node < T >* tail;
    int size;
};

// definitions ...

template < typename T >
void List < T >::push_front( T element )
{
    Node < T > * newNode = new Node < T > ( element );
    newNode->next = head;
    head = newNode;
    ++size;
    if( tail == NULL ) tail = head;
}

template < typename T >
void List < T >::push_back( T element )
{
    if( tail != NULL )
    {
        tail->next = new Node < T > ( element );
        tail = tail->next;
    }
    else head = tail = new Node < T > ( element );
    ++size;
}

template < typename T >
T List < T >::get_front() const
{
    if( size ) return head->element;
    else throw runtime_error("Index out of range");
}

template < typename T >
T List < T >::get_back() const
{
    if( size ) return tail->element;
    // else
    throw runtime_error("Index out of range");
}

template < typename T >
T List < T >::pop_front()
{
    if( size ) // handle most likely cases first ...
    {
        Node < T > * tmp = head;
        head = head->next;
        if (head == NULL) tail = NULL;
        size--;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    // else
    throw runtime_error("No elements in the list");
}

template < typename T >
T List < T >::pop_back()
{
    if( size > 1 ) // handle most likely cases first ...
    {
        Node < T > * current = head;
        for( int i = 0; i < size - 2; ++i ) current = current->next;

        Node < T > * tmp = tail;
        tail = current;
        tail->next = NULL;
        size--;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    //else
    if( size == 1 )
    {
        Node < T > * tmp = head;
        head = tail = NULL;
        size = 0;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    // else
    throw runtime_error("No elements in the list");
}

template < typename T >
void List < T >::insert( int position, T element )
{
    if( position > 1 && position <= size ) // handle most likely cases first ...
    {
        Node < T > * current = head;
        for( int i = 2; i < position; ++i ) current = current->next;
       
        Node < T > * tmp = current->next;
        current->next = new Node < T > ( element );
        current->next->next = tmp;
        ++size;
    }
    else if( position > size ) push_back( element );
    else push_front( element );
    // or could thow runtime_error("position not in valid insert range");
}

template < typename T >
void List < T >::clear()
{
    for( Node < T >* cur = head; cur != NULL; head = cur )
    {
        cur = cur->next;
        delete head;
    }
    tail = NULL;
    size = 0;
}

// pass in the address of the Clist and the new element to insert ...
template < typename T >
void List < T >::insert_sorted( T e )
{
    Node< T >* nNode = new Node< T > ( e );
    // firstly, we handle most common case where 'n' is NOT the first Node
    if( head != NULL && e >= head->element ) /* NEED >= */
    {
        // so search the linked list for the right location
        Node< T >* cur = head;
        while( cur->next != NULL && cur->next->element <= e )
            cur = cur->next;
           
        if( cur == tail ) tail = nNode;
        nNode->next = cur->next;
        cur->next = nNode;
        // head unchanged
        ++ size;
    }
    else // if we reach here, this IS the first node ...
    {
        nNode->next = head;     // so set this node in first position
        head = nNode;
        ++ size;
        if( size == 1 ) tail = nNode;
    }
}
/*
template < typename T >
void List < T >::isort()
{
    List< T > nList;
    for( Node< T >* cur = head; cur != NULL; cur = cur->next )
        nList.insert_sorted( cur->element );
    // now ... update old list with new ...
    *this = nList;
}
*/
template < typename T >
void List < T >::isort()
{
    Node< T >* nHead = NULL, * tmp; // , * nTail = NULL;
    for( Node< T >* i = head; i != NULL; i = tmp ) // traverse old list ...
    {
        tmp = i->next; // get copy of next address in old list ...

        // handle most common case first, i.e. element *NOT* at head of new list
        if( nHead != NULL && i->element >= nHead->element ) /* NEED >= */
        {
            // so search the new sorted list for the right location to insert ...
            Node< T >* cur = nHead;
            while( cur->next != NULL && cur->next->element <= i->element )
                cur = cur->next;

            //if( cur == nTail ) nTail = i;
            i->next = cur->next;
            cur->next = i;
            // head unchanged
            //++ size;
        }
        else // if we reach here, this IS the first node ...
        {
            i->next = nHead;     // so set this node in first position
            nHead = i;
            //++ size;
            //if( nTail == NULL ) nTail = i;
        }

    }
    // now ... update old  with new ... ( size is unchanged )
    tail = head = nHead;
    if( tail != NULL ) while( tail->next != NULL ) tail = tail->next;
}

#endif


[David]

This version users iterators to traverse the queue/list ...

Code: [Select]

// linkedlist_iter.h //

#ifndef LIST_ITER_H
#define LIST_ITER_H
#include <stdexcept>


// forward declarations here so can be recognized in template class Node
// and given friend class status there ...
template < typename T > class List;
template < typename T > class Iter;

template< typename T >
class Node
{
    friend class List < T >; // give List access to all of class Node
    friend class Iter < T >;
public:
    Node() : element(T(0)), next(NULL) {} // No-arg (default) ctor
    Node( T element ) : element(element), next(NULL) {} // 1-arg ctor
    Node< T >* get_next() { return next; }
    T get_element() { return element; }
private:
    T element;
    Node< T >* next;
};

// an Iter 'points' to a Node's position in a list ... or a 'NULL' i.e. end()
// (i.e. ... past the end of the list)
template< typename T >
class Iter
{
    friend class List< T >;
public:
    Iter( Node< T >* n = NULL ) : cur( n ) {}

    // return T value at Node of this Iter  ...
    T operator * () const
    {
        if( cur == NULL) throw runtime_error( "Iter operator * cannot return NULL (1)" );
        return cur->element;
    }
    // pre ++ ...
    Iter& operator ++ ()
    {
        if( cur == NULL) throw runtime_error( "Iter operator ++ cannot ++ NULL (2)" );
        cur = cur->next;
        return *this;
    }
    // post ++ ...
    Iter& operator ++ ( int anIntDummyHereToIndicatePostPP )
    {
        if( cur == NULL) throw runtime_error( "Iter operator ++ cannot ++ NULL (3)" );
        cur = cur->next;
        return *this;
    }

    bool operator == ( Iter< T > it ) const { return cur == it.cur; }
    bool operator != ( Iter< T > it ) const { return cur != it.cur; }

private:
    Node< T >* cur;
};


template < typename T >
class List // fixed up / upgraded / and trimmed to members applicable here ...
{
public:
    List() : head(NULL), tail(NULL), size(0) { cout << "List ctor called ...\n"; }
    virtual ~List() { clear(); cout << "List dtor called ... all clear now.\n"; }

    List( const List< T >& obj ) // copy ctor ...
    {
        head = tail = NULL;
        size = 0;
        for( Node< T >* p = obj.head; p != NULL; p = p->next )
            push_back( p->element );
    }
    List& operator= ( const List< T >& obj ) // overloaded assignment operator
    {
        if( this != &obj )
        {
            clear();
            for( Node< T >* p = obj.head; p != NULL; p = p->next )
                push_back( p->element );
        }
        return *this;
    }

    void push_front( T );
    void push_back( T );
    void insert( int, T ); // at int position 1..n (Note: not using index 0..n-1)
    void clear();
    int get_size() const { return size; }
    T get_front() const;
    T get_back() const;
    T pop_front();
    T pop_back();
   
    Node< T >* get_head() const { return head;}
   
    Iter< T > begin() const
    {
        Iter< T > itr( head );
        //itr.cur = head;
        return itr;
    }
    Iter< T > end() const
    {
        Iter< T > itr( NULL );
        //itr.cur = NULL;
        return itr;
    }

    void insert_sorted( T );
    void isort();

protected:
    Node < T >* head;
    Node < T >* tail;
    int size;
};

// definitions ...

template < typename T >
void List < T >::push_front( T element )
{
    Node < T > * newNode = new Node < T > ( element );
    newNode->next = head;
    head = newNode;
    ++size;
    if( tail == NULL ) tail = head;
}

template < typename T >
void List < T >::push_back( T element )
{
    if( tail != NULL )
    {
        tail->next = new Node < T > ( element );
        tail = tail->next;
    }
    else head = tail = new Node < T > ( element );
    ++size;
}

template < typename T >
T List < T >::get_front() const
{
    if( size ) return head->element;
    else throw runtime_error("Index out of range");
}

template < typename T >
T List < T >::get_back() const
{
    if( size ) return tail->element;
    // else
    throw runtime_error("Index out of range");
}

template < typename T >
T List < T >::pop_front()
{
    if( size ) // handle most likely cases first ...
    {
        Node < T > * tmp = head;
        head = head->next;
        if (head == NULL) tail = NULL;
        size--;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    // else
    throw runtime_error("No elements in the list");
}

template < typename T >
T List < T >::pop_back()
{
    if( size > 1 ) // handle most likely cases first ...
    {
        Node < T > * current = head;
        for( int i = 0; i < size - 2; ++i ) current = current->next;

        Node < T > * tmp = tail;
        tail = current;
        tail->next = NULL;
        size--;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    //else
    if( size == 1 )
    {
        Node < T > * tmp = head;
        head = tail = NULL;
        size = 0;
        T element = tmp->element;
        delete tmp;
        return element;
    }
    // else
    throw runtime_error("No elements in the list");
}

template < typename T >
void List < T >::insert( int position, T element )
{
    if( position > 1 && position <= size ) // handle most likely cases first ...
    {
        Node < T > * current = head;
        for( int i = 2; i < position; ++i ) current = current->next;
       
        Node < T > * tmp = current->next;
        current->next = new Node < T > ( element );
        current->next->next = tmp;
        ++size;
    }
    else if( position > size ) push_back( element );
    else push_front( element );
    // or could thow runtime_error("position not in valid insert range");
}

template < typename T >
void List < T >::clear()
{
    for( Node < T >* cur = head; cur != NULL; head = cur )
    {
        cur = cur->next;
        delete head;
    }
    tail = NULL;
    size = 0;
}

// pass in the address of the Clist and the new element to insert ...
template < typename T >
void List < T >::insert_sorted( T e )
{
    Node< T >* nNode = new Node< T > ( e );
    // firstly, we handle most common case where 'n' is NOT the first Node
    if( head != NULL && e >= head->element ) /* NEED >= */
    {
        // so search the linked list for the right location
        Node< T >* cur = head;
        while( cur->next != NULL && cur->next->element <= e )
            cur = cur->next;
           
        if( cur == tail ) tail = nNode;
        nNode->next = cur->next;
        cur->next = nNode;
        // head unchanged
        ++ size;
    }
    else // if we reach here, this IS the first node ...
    {
        nNode->next = head;     // so set this node in first position
        head = nNode;
        ++ size;
        if( size == 1 ) tail = nNode;
    }
}
/*
template < typename T >
void List < T >::isort()
{
    List< T > nList;
    for( Node< T >* cur = head; cur != NULL; cur = cur->next )
        nList.insert_sorted( cur->element );
    // now ... update old list with new ...
    *this = nList;
}
*/
template < typename T >
void List < T >::isort()
{
    Node< T >* nHead = NULL, * tmp; // , * nTail = NULL;
    for( Node< T >* i = head; i != NULL; i = tmp ) // traverse old list ...
    {
        tmp = i->next; // get copy of next address in old list ...

        // handle most common case first, i.e. element *NOT* at head of new list
        if( nHead != NULL && i->element >= nHead->element ) /* NEED >= */
        {
            // so search the new sorted list for the right location to insert ...
            Node< T >* cur = nHead;
            while( cur->next != NULL && cur->next->element <= i->element )
                cur = cur->next;

            //if( cur == nTail ) nTail = i;
            i->next = cur->next;
            cur->next = i;
            // head unchanged
            //++ size;
        }
        else // if we reach here, this IS the first node ...
        {
            i->next = nHead;     // so set this node in first position
            nHead = i;
            //++ size;
            //if( nTail == NULL ) nTail = i;
        }

    }
    // now ... update old  with new ... ( size is unchanged )
    tail = head = nHead;
    if( tail != NULL ) while( tail->next != NULL ) tail = tail->next;
}

#endif