Developers Heaven Forum
Desktop Programming => C/C++ & Visual C++ => Topic started by: David on March 31, 2011, 02:07:44 AM
-
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 )
// 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 ... " );
}
-
These next 2 files are used by the above demo program, that tests out class Queue ...
// 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
-
This version users iterators to traverse the queue/list ...
// 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