deque.h

/***********************************************************************
* Header:
*    Deque
* Summary:
*    This class contains the notion of a deque: a bucket to hold
*    data for the user. This is just a starting-point for more advanced
*    constainers such as the vector, set, stack, queue, deque, and map
*    which we will build later this semester.
*
*    This will contain the class definition of:
*        Deque         : A class that holds stuff
* Author
*    Br. Helfrich
************************************************************************/

#ifndef DEQUE_H
#define DEQUE_H

#include<iostream>
#include <cassert>
#include <cstdlib>
using namespace std;
/************************************************
 * DEQUE
 * Double-ended queue
 ***********************************************/
template <class T>
class Deque
{
public:
   // default constructor : empty and kinda useless
  Deque() : numItems(0), myCapacity(0), data(NULL),
      myFront(0), myBack(0) {}

   // copy constructor : copy it
   Deque(const Deque & rhs) throw (const char *);
   
   // non-default constructor : pre-allocate
   Deque(int capacity) throw (const char *);
   
   // destructor : free everything
   ~Deque()        { if (myCapacity) delete [] data; }
   
   // is the deque currently empty
   bool empty() const  { return numItems == 0;         }

   // how many items are currently in the deque?
   int size() const    { return numItems;              }
   
   // To allocate more space in deque 
   void resize();
	
   // how many items can the deque currently hold?
   int capacity()      { return myCapacity;            }
	
   // remove all the items from the deque
   void clear()        { numItems = 0;                 }

   // add an item to the back of the deque
   void push_back(const T & t) throw (const char *);

   // add an item the front of the queue
   void push_front(const T & t) throw (const char *);

   // take an item off the back of the deque
   void pop_back() throw (const char *);

   // take an item off of the front of the deque
   void pop_front() throw (const char *);

   // getting the items from the front and the back
   T & front() throw (const char *)
   {
      if (numItems == 0)
         throw "ERROR: attempting to access an item in an empty deque";
      else
         return data[myFront];
   }
   
   T & back()  throw (const char *)
   {
      if (numItems == 0)
         throw "ERROR: attempting to access an item in an empty deque";
      else
         return data[myBack];
   }
   
   Deque <T> & operator = (const Deque <T> & rhs) throw (const char *)
   {
      assert(rhs.myCapacity >= 0);
      
      if (this == &rhs)
         return *this;
      
      if (rhs.myCapacity == 0)
      {
         myFront = 0;
         myBack = 0;
         myCapacity = 0; 
         numItems = 0;
         data = NULL;
         return *this;
      }

      // attempt to allocate
         try
      {
         data = new T[rhs.myCapacity];
      }
      
      catch (std::bad_alloc)
      {
         throw "ERROR: Unable to allocate a new buffer for deque";
      }

      // copy over the storage and size
      assert(rhs.numItems >= 0 && rhs.numItems <= rhs.myCapacity);
      numItems = rhs.numItems;
      myCapacity = rhs.myCapacity;

      // copy the items over one at a time using the assignment operator
      for (int i = 0; i < numItems; i++)
         data[i] = rhs.data[i];

      // the rest needs to be filled with the default value for T
      //for (int i = numItems; i < myCapacity; i++)
       //  data[i] = T();
      return *this;
   }
   
private:
   T * data;        // dynamically allocated array of T
   int numItems;      // how many items are currently in the deque?
   int myCapacity;      // how many items can I put on the deque before full?
   int myFront;
   int myBack;
};

/********************************************
* Resize function to allocate more space
*********************************************/
template <class T>
void Deque<T> :: resize()
{
   // creates a bigger array and deletes the old one
   T * newData = new T[myCapacity *= 2];
   //for (int i = myFront; i == myBack; i = (i + 1) % myCapacity)
    for(int i = 0; i<numItems; i++)
      newData[i] = data[i];
   delete [] data;
   data = newData;
}

/*******************************************
 * DEQUE :: COPY CONSTRUCTOR
 *******************************************/
template <class T>
Deque <T> :: Deque(const Deque <T> & rhs) throw (const char *)
{
   assert(rhs.myCapacity >= 0);
      
   // do nothing if there is nothing to do
   if (rhs.myCapacity == 0)
   {
      myFront = 0;
      myBack = 0;
      myCapacity = 0; 
      numItems = 0;
      data = 0x00000000;
      return;
   }

   // attempt to allocate
   try
   {
      data = new T[rhs.myCapacity];
   }
   catch (std::bad_alloc)
   {
      throw "ERROR: Unable to allocate a new buffer for deque";
   }
   
   // copy over the capacity and size
   assert(rhs.numItems >= 0 && rhs.numItems <= rhs.myCapacity);
   myCapacity = rhs.myCapacity;
   numItems = rhs.numItems;

   // copy the items over one at a time using the assignment operator
   for (int i = 0; i < numItems; i++)
      data[i] = rhs.data[i];

    //the rest needs to be filled with the default value for T
   for (int i = numItems; i < myCapacity; i++)
      data[i] = T();
}

/**********************************************
 * DEQUE : NON-DEFAULT CONSTRUCTOR
 * Preallocate the deque to "capacity"
 **********************************************/
template <class T>
Deque <T> :: Deque(int capacity) throw (const char *)
{
   assert(capacity >= 0);
   
   // do nothing if there is nothing to do
   if (capacity == 0)
   {
      myFront = 0;
      myBack = 0;
      myCapacity = numItems = 0;
      data = 0x00000000;
      return;
   }

   // attempt to allocate
   try
   {
      data = new T[capacity];
   }
   catch (std::bad_alloc)
   {
      throw "ERROR: Unable to allocate a new buffer for deque";
   }

      
   // copy over the stuff
   myCapacity = capacity;
   numItems = 0;

   // initialize the deque by calling the default constructor
   for (int i = 0; i < capacity; i++)
      data[i] = T();
}

/***************************************************
 * DEQUE :: PUSH_BACK
 * push an item on the end of the deque
 **************************************************/
template <class T>
void Deque <T> :: push_back(const T & t) throw(const char *)
   {
      if (myCapacity < 1)
      {
         //better allocate some memory if we don't have any
         myCapacity = 1;
        
        // if (!data)
         try
         {
            data = new T[myCapacity];
         }
         catch(std::bad_alloc)
         {
         throw "Unable to allocate a new buffer for Stack";
         }       
      }
      // if full create a bigger array
      if (numItems == myCapacity)
         resize();
     
       // = (myBack + 1) % myCapacity;  
      data[myBack] = t;
      
      myBack++;
      
      numItems++;
   }


/***************************************************
 * DEQUE :: PUSH_FRONT
 * push an item on the front of the deque
 *************************************************/
template <class T>
void Deque <T> :: push_front(const T & t) throw(const char *)
   {
      if (myCapacity < 1)
      {
         //better allocate some memory if we don't have any
         myCapacity = 1;
         // if (!data)
         //data = new T[capacity];
         try
         {
            data = new T[myCapacity];
         }
         catch(std::bad_alloc)
         {
         throw "Unable to allocate a new buffer for Stack";
         }       
      }
      // if full create a bigger array
      if (numItems == myCapacity)
         resize();
      myFront = (myFront - 1) % myCapacity;   
      data[myFront] = t;
      numItems++;   
   }
 
/*************************************************************
 * Deque::pop_front(): Take an item off the front of the deque
 *************************************************************/
template <class T>
void Deque<T> :: pop_front() throw (const char *)
{
   
   // Check to see if we can abrogate the front of the deque
   myFront = (myFront + 1) % myCapacity;
   //cout << data[myFront];
   numItems--;
   //cout << myFront;
}

/***********************************************************
 * Deque::pop_back(): Take an item off the back of the deque
 ***********************************************************/
template <class T>
void Deque<T> :: pop_back() throw (const char *)
{
   // Check to see if we can abrogate the front of the deque
   myBack = (myBack - 1) % myCapacity;
   numItems--;
}



#endif // DEQUE_H

makefile

###############################################################
# Program:
#     Week 04, DEQUE
#     Brother JonesL, CS235
# Author:
#     Levi Stum, Kim Dean, Ted McDaniel, 
# Summary:
#     <put a description here>
# Time:
#     <how long did it take to complete this program>?
###############################################################

##############################################################
# The main rule
##############################################################
a.out: deque.h week04.o nowServing.o
	g++ -o a.out week04.o nowServing.o
	tar -cf week04.tar *.h *.cpp makefile

##############################################################
# The individual components
#      week04.o       : the driver program
#      nowServing.o   : the logic for the now serving program
##############################################################
week04.o: deque.h week04.cpp
	g++ -c week04.cpp

nowServing.o: nowServing.h nowServing.cpp deque.h
	g++ -c nowServing.cpp

nowServing.cpp

#include "nowServing.h"
/*******************************************
 * Please Ignore, 
 * This is a placeholder so makefile will work
 *******************************************/

nowServing.h

#include <iostream>
/*******************************************
 * Please Ignore, 
 * This is a placeholder so makefile will work
 *******************************************/

week04.cpp

/***********************************************************************
* Program:
*    Week 04, DEQUE
*    Brother Helfrich, CS 235
* Author:
*    Br. Helfrich
* Summary: 
*    This is a driver program to exercise the Deque class.  When you
*    submit your program, this should not be changed in any way.  That being
*    said, you may need to modify this once or twice to get it to work.
************************************************************************/

#include <iostream>     // for CIN and COUT
#include <string>       // for the String class
#include <cassert>      // for ASSERT
#include "deque.h"      // your Deque class should be in deque.h
//#include "nowServing.h" // your nowServing() function
using namespace std;


// prototypes for our four test functions
void testSimple();
void testPushPopFront();
void testWrapping();
void testErrors();
//void nowServing();

// To get your program to compile, you might need to comment out a few
// of these. The idea is to help you avoid too many compile errors at once.
// I suggest first commenting out all of these tests, then try to use only
// TEST1.  Then, when TEST1 works, try TEST2 and so on.
#define TEST1   // for testSimple()
#define TEST2   // for testPushPopFront()
//#define TEST3   // for testWrapping()
//#define TEST4   // for testErrors()

/**********************************************************************
 * MAIN
 * This is just a simple menu to launch a collection of tests
 ***********************************************************************/
int main()
{
   // menu
   cout << "Select the test you want to run:\n";
   cout << "\t1. Just create and destroy a Deque\n";
   cout << "\t2. The above plus push, pop, top\n";
   cout << "\t3. The above plus test implementation of wrapping\n";
   cout << "\t4. The above plus exercise the error Deque\n";
   cout << "\ta. Now Serving\n";

   // select
   char choice;
   cout << "> ";
   cin  >> choice;
   switch (choice)
   {
      case 'a':
         // nowServing();
         break;
      case '1':
         testSimple();
         cout << "Test 1 complete\n";
         break;
      case '2':
         testPushPopFront();
         cout << "Test 2 complete\n";
         break;
      case '3':
         testWrapping();
         cout << "Test 3 complete\n";
         break;
      case '4':
         testErrors();
         cout << "Test 4 complete\n";
         break;
      default:
         cout << "Unrecognized command, exiting...\n";
   }

   return 0;
}

/*******************************************
 * TEST SIMPLE
 * Very simple test for a Deque: create and destroy
 ******************************************/
void testSimple()
{
#ifdef TEST1
   try
   {
      // Test 1.a: bool Deque with default constructor
      cout << "Create a bool Deque using default constructor\n";
      Deque <bool> d1;
      cout << "\tSize:     " << d1.size()                   << endl;
      cout << "\tCapacity: " << d1.capacity()               << endl;
      cout << "\tEmpty?    " << (d1.empty() ? "Yes" : "No") << endl;

      // Test 1.b: double Deque with non-default constructor
      cout << "Create a double Deque using the non-default constructor\n";
      Deque <double> d2(10 /*capacity*/);
      cout << "\tSize:     " << d2.size()                   << endl;
      cout << "\tCapacity: " << d2.capacity()               << endl;
      cout << "\tEmpty?    " << (d2.empty() ? "Yes" : "No") << endl;

      // Test 1.c: copy the Deque using the copy constructor
      {
         cout << "Create a double Deque using the copy constructor\n";
         Deque <double> d3(d2);
         cout << "\tSize:     " << d3.size()                   << endl;
         cout << "\tCapacity: " << d3.capacity()               << endl;
         cout << "\tEmpty?    " << (d3.empty() ? "Yes" : "No") << endl;
      }

      // Test 1.d: copy the Deque using the assignment operator
      cout << "Copy a double Deque using the assignment operator\n";
      Deque <double> d4(2);
      d4 = d2;
      cout << "\tSize:     " << d4.size()                   << endl;
      cout << "\tCapacity: " << d4.capacity()               << endl;
      cout << "\tEmpty?    " << (d4.empty() ? "Yes" : "No") << endl;
   }
   catch (const char * error)
   {
      cout << error << endl;
   }
   
#endif //TEST1
}

#ifdef TEST2
/******************************************
 * DISPLAY
 * Display the contents of the deque
 ******************************************/
template <class T>
ostream & operator << (ostream & out, Deque <T> d)
{

   out << "{ ";
   while (!d.empty())
   {
      out << d.front() << ' ';
      d.pop_front();
   }
   out << '}';

   return out;
}
#endif // TEST2


/*******************************************
 * TEST PUSH POP FRONT
 * Add a whole bunch of items to the Deque.  This will
 * test the Deque growing algorithm
 *****************************************/
void testPushPopFront()
{
#ifdef TEST2
   try
   {
      // create
      Deque <int> d1;

      // fill
      cout << "Enter integer values, type 0 when done\n";
      int value;
      do
      {
         cout << "\t" << d1 << " > ";
         cin  >> value;
         if (value)
         {
            d1.push_back(value);
         }
      }
      while (value);

      // display how big it is
      cout << "\tSize:     " << d1.size()                   << endl;
      cout << "\tEmpty?    " << (d1.empty() ? "Yes" : "No") << endl;
      cout << "\tCapacity: " << d1.capacity()               << endl;

      // make a copy of it using the assignment operator and copy constructor
      Deque <int> d2(2);
      d2 = d1;
      Deque <int> d3(d1);

      // destroy the old copy
      d1.clear();

      // display the two copies
      cout << "\td1 = " << d1 << endl;
      cout << "\td2 = " << d2 << endl;
      cout << "\td3 = " << d3 << endl;
   }
   catch (const char * error)
   {
      cout << error << endl;
   }   
#endif // TEST2   
}

/*******************************************
 * TEST WRAPPING
 * We will test pop_front(), pop_back(),
 * push_front(), and push_back() to make
 * sure the Deque looks the way we expect
 * it to look.
 ******************************************/
void testWrapping()
{
#ifdef TEST3
   // create
   Deque <string> d(4);

   // instructions
   cout << "instructions:\n"
        << "\t+f dog   pushes dog onto the front\n"
        << "\t+b cat   pushes cat onto the back\n"
        << "\t-f       pops off the front\n"
        << "\t-b       pops off the back\n"
        << "\t*        clear the deque\n"
        << "\t?        shows the statistics of the deque\n"
        << "\t!        quit\n";

   string command;
   string text;
   do
   {
      cout << d << " > ";
      cin  >> command;

      try
      {
         if (command == "+f")
         {
            cin >> text;
            d.push_front(text);
         }
         else if (command == "+b")
         {
            cin >> text;
            d.push_back(text);
         }
         else if (command == "-f")
         {
            cout << "\tpop: " << d.front() << endl;
            d.pop_front();
         }
         else if (command == "-b")
         {
            cout << "\tpop: " << d.back() << endl;
            d.pop_back();
         }
         else if (command == "?")
         {
            cout << "\tSize:     " << d.size()     << endl;
            cout << "\tCapacity: " << d.capacity() << endl;
         }
         else if (command == "*")
         {
            d.clear();
         }
         else if (command != "!")
         {
            cout << "Unknown command\n";
            cin.ignore(256, '\n');
         }      
      }
      catch (const char * e)
      {
         cout << '\t' << e << endl;
      }
   }
   while (command != "!");
#endif // TEST3
}

/*******************************************
 * TEST ERRORS
 * Numerous error conditions will be tested
 * here, including bogus popping and the such
 *******************************************/
void testErrors()
{
#ifdef TEST4
   // create
   Deque <char> d;

   // test using front() with an empty deque
   try
   {
      d.front();
      cout << "BUG! We should not be able to front() with an empty deque!\n";
   }
   catch (const char * error)
   {
      cout << "\tDeque::front() error message correctly caught.\n"
           << "\t\"" << error << "\"\n";
   }

   // test using back() with an empty deque
   try
   {
      d.back();
      cout << "BUG! We should not be able to back() with an empty deque!\n";
   }
   catch (const char * error)
   {
      cout << "\tDeque::back() error message correctly caught.\n"
           << "\t\"" << error << "\"\n";
   }

   // test using pop_front() with an empty deque
   try
   {
      d.pop_front();
      cout << "BUG! We should not be able to pop_front() "
           << "with an empty deque!\n";
   }
   catch (const char * error)
   {
      cout << "\tDeque::pop_front() error message correctly caught.\n"
           << "\t\"" << error << "\"\n";
   }      

   // test using pop_back() with an empty deque
   try
   {
      d.pop_back();
      cout << "BUG! We should not be able to pop_back() "
           << "with an empty deque!\n";
   }
   catch (const char * error)
   {
      cout << "\tDeque::pop_back() error message correctly caught.\n"
           << "\t\"" << error << "\"\n";
   }      

#endif // TEST4
}