C++ Stacks and Queues and Lists
			   Worth: 2 points
				   
I. Introduction

This project will give you experience implementing a templated
container class---the double-ended, doubly-linked list.

II. The Double-Ended List

The double-ended list, or Dlist, is a templated container.  It
supports the following operational methods:

    * isEmpty: a predicate that returns true if the list is empty,
               false otherwise

    * insertFront/insertBack: insert an object at the front/back of
                              the list, respectively

    * removeFront/removeBack: remove an object from the front/back of
                              a non-empty list, respectively; throws
                              an exception if the list is empty.


Note that while this list is templated across the contained type, T,
it inserts and removes only pointers-to-T, not instances of T.  This
ensures that the Dlist implementation knows that it owns inserted
objects, is responsible for copying them if the list is copied, and
destroying them if the list is destroyed.

The complete interface of the Dlist class is provided in dlist.h.  The
code is replicated here for your convenience.  You may not modify
dlist.h in any way.

--------------------------------------------------------------
#ifndef __DLIST_H__
#define __DLIST_H__

class emptyList {
    // OVERVIEW: an exception class
};

template <typename T>
class Dlist {
    // OVERVIEW: contains a double-ended list of Objects

 public:

    // Operational methods

    bool isEmpty();
    // EFFECTS: returns true if list is empy, false otherwise

    void insertFront(T *o);
    // MODIFIES this
    // EFFECTS inserts o at the front of the list
    
    void insertBack(T *o);
    // MODIFIES this
    // EFFECTS inserts o at the back of the list

    T *removeFront();
    // MODIFIES this
    // EFFECTS removes and returns first object from non-empty list
    //         throws an instance of emptyList if empty

    T *removeBack();
    // MODIFIES this
    // EFFECTS removes and returns last object from non-empty list
    //         throws an instance of emptyList if empty

    // Maintenance methods
    Dlist();                                   // ctor
    Dlist(const Dlist &l);                     // copy ctor
    Dlist &operator=(const Dlist &l);          // assignment
    ~Dlist();                                  // dtor

 private:
    // A private type
    struct node {
	node   *next;
	node   *prev;
	T      *o;
    };

    node   *first; // The pointer to the 1st node (NULL if none)
    node   *last;  // The pointer to the last node (NULL if none)

    // Utility methods

    void makeEmpty();
    // EFFECT: called by constructors/operator= to establish empty
    // list invariant
    
    void removeAll();
    // EFFECT: called by destructor/operator= to remove and destroy
    // all list elements

    void copyAll(const Dlist &l);
    // EFFECT: called by copy constructor/operator= to copy elements
    // from a source instance l to this instance
};

/*
Note: this is here *only* because the gnu compiler needs to see the
"templatized" versions of your methods.  This is the *only* instance
in which it is acceptable to #include a cc file.
*/

#include "dlist.cc"

#endif /* __DLIST_H__ */
--------------------------------------------------------------

The definition of "node", the private type for elements of the
container list, is given in the private section of class Dlist.  This
is so that clients of the class cannot use the type.

In addition to the five operational methods, there are the usual four
maintenance methods: default constructor, copy constructor, assignment
operator, and destructor.  Be sure that your copy constructor and
assignment operator do *full* deep copies---including making copies
of T's owned by the list.

Finally, the class defines three private utility methods in which to
place code common to two or more of the maintenance methods.

You are to provide an implementation for each Dlist method in a file
called dlist.cc, to be handed in with this project.  We will test
your Dlist implementation separately from the other components of this
project, so it must work independently of the application.

Note that dlist.h includes dlist.cc; this is because of the way that
template types work in the GNU C++ compiler.  To instantate a Dlist of
pointers-to-int, for example, you would declare the list:

     Dlist<int>  il;

This instructs the compiler to instantiate a version of Dlist that
contains pointers-to-int, and the compiler *at that point* compiles a
version of the Dlist template that contains such pointers-to-int.

Note also that we use the "template <typename T>" syntax rather than
the "template <class T>" syntax in dlist.h.  The two are equivalent,
but we believe that typename makes a bit more sense to the reader.

To compile a program that uses Dlists, you need only include
"dlist.h".  You do not need to name dlist.cc on the compiler command
line, because dlist.h includes it.  As an example, consider the
following simple test program, called testl.cc:

--------------------------------------------------------------
#include <iostream>
#include "dlist.h"

using namespace std;

int main()
{
    Dlist<int> ilist;
    int *ip = new int(3);
    ilist.insertFront(ip);

    ip = ilist.removeFront();
    cout << *ip << endl;

    return 0;
}
--------------------------------------------------------------

To build it:

   g++ -Wall -Werror -o testl testl.cc

You will use a similar command line to build the other test cases you
write for yourself.

III. RPN Calculator

One test application is a simple Reverse-Polish Notation calculator.
An RPN calculator is one in which the operators appear *after* their
respective operands, rather than in between them.  So, instead of
computing the following:

  (2 + 3) * 5

an RPN calculator would compute this equivalent expression:

   2 3 + 5 *

RPN notation is convenient for several reasons.  First, no parentheses
are necessary---the computation is always unambiguous.  Second, such a
calculator is easy to implement given a stack.  This is particularly
useful, because it is possible to use the DList as a stack.

The calculator is invoked with no arguments, and starts out with an
empty stack.  It takes its input from the standard input stream, and
writes its output to the standard output stream.  Here are the
commands your calculator must respond to:

     <some number>   a number has the form: one or more digits [0--9]
                     optionally followed by a decimal point and one or
                     more digits.  For example, 3 4.56 and 0.12 are
                     all numbers, but -2, 1., and abc are not.  A
                     number, when entered, is pushed on the stack.
                     Always valid.

      +              pop the top two numbers from the stack, add them
                     together, and push the result.  Requires a stack
                     with at least two operands.

      -              pop the top two numbers from the stack, subtract
                     the first popped number from the second, and push
                     the result.  Requires a stack with at least two
                     operands.

      *              pop the top two numbers from the stack, multiply
                     them together, and push the result.  Requires a
                     stack with at least two operands.

      /              pop the top two numbers from the stack, divide
                     the second popped number by the first, and push
                     the result.  Requires a stack with at least two
                     operands. 

      n              negate: pop the top item, multiply it by -1, and
                     push the result on the stack.  Requires a stack
                     with at least one operand.

      d              duplicate: pop the top item and push two copies
                     of it. Requires a stack with at least one
                     operand. 

      r              reverse: pop the top two items, push the first
                     popped item, then the second.  Requires a stack
                     with at least two operands.

      p              print: print the top item to standard output,
                     followed by a newline.  Requires a stack 
                     with at least one operand.  Leaves the stack
                     unchanged.

      c              clear: pop all items from the stack.  Always
                     valid. 

      a              print-all: print all items from the stack in one
                     line, from top-most to bottom-most, each
                     separated by a single space, followed by a
                     newline.  Always valid.  Leaves the stack
                     unchanged.

      q              quit: exit the calculator.  Always valid.


Each command is on a separate line.

You may not assume that user input is always correct.  There are three
error messages to report.

   1) If a user enters something other than one of the commands above,
      leave the stack unchanged, advance to the next line,
      and print the following message:

  	    cout << "Bad input\n";

   2) If a user enters a command that requires more operands than are
      present, leave the stack unchanged, advance to the next
      line, and print the following message:

	    cout << "Not enough operands\n";

   3) If a user enters the divide command with a zero on the top of
      the stack, leave the stack unchanged, advance to the next
      line, and print the following message:

	    cout << "Divide by zero\n";

Note that the phrase "leave the stack unchanged" is not to be taken
literally.  It is okay to pop the top two operands for division; if
the divisor is zero, be sure push them back before reading the next
command.

You may assume that the user will not type EOF before quitting.  Here
is a short example:

	[ 23 ] clip p5 -: ./calc
	2
	3
	4
	+
	*
	p
	14
	+
	Not enough operands
	d
	+
	p
	28
        q


Implement your calculator in a file called calc.cc, to be handed in
when the project is due.  It must work correctly with any valid
implementation of DList.


IV. General Requirements

You must use the Dlist container to implement your stack in the
calculator.  You may use any type you see fit as the templated type in
each application---however, remember that you only insert and remove
pointers-to-objects.  You should only insert dynamic objects into your
Dlist. 

You may not leak memory in any way.  To help you see if you are
leaking memory, you may wish to #include <altnew.h> and link against
altnew.cc.  This file replaces the new and delete operators (plain
and array versions) with an allocator that counts the number of bytes
allocated.  

NOTE: this reports bytes allocated by *anything* in your program OR
anything your program *uses*.  For example, if you print output to
cout, and it is buffered, the library that implements cout will
allocate memory via altnew, and those bytes will be recorded in the
total.  Thus, it is perfectly acceptable for your program to exit with
non-zero allocated memory.  But if, for example, altnew reports that
memory alloacted grows each time you insert an object and then remove
it, you probably have a leak.

As a side effect, this allocator will also complain about
double-frees, as well as freeing a block that was not allocated by new
or has been corrupted since then.  These mechanisms are not foolproof,
but they will catch many mistakes.  To the best of our knowledge,
altnew is portable, but we make no guarantees.

Please note that tools like purify or valgrind will be terribly
offended by the sleazy tricks played by the alternate allocator.  If
you mix these tools, one or both will be very confused.

You must fully implement the Dlist ADT.  Note that the obvious
implementations of the calculator do not exercise all of a Dlist's
functionality.

Your two files---dlist.cc and calc.cc---will be tested
independently.  Be sure that they can be compiled separately, with no
cross-file dependencies.

You may #include <iostream>, <string>, <cstdlib>, and <cassert>. No
other system header files may be included, and you may not make any
call to any function in any other library (even if your IDE allows you
to call the function without including the appropriate header file).

Input and/or output should only be done where it is specified.

As usual, you may not use goto, nor may you use any global variables
that are not const.

V. Files

All files for this project live in "./projects/0" on the course web, e.g.,
http://www.cs.duke.edu/courses/fall09/cps110/projects/0/proj0.tar.gz. 
The following are provided:

       altnew.h:   interface for the alternate allocator
       altnew.cc: its implementation
       dlist.h:    the Dlist class declaration
       testl.cc:  a *very* simple list test case
              

VI. Grading

Use the /usr/project/courses/cps110/bin/submit110 program to submit
the following files in project 0:

        dlist.cc        Your Dlist implementation
	calc.cc         Your calculator

The auto-grader will use seven test cases to evaluate your solutions.
The first four (0-3) will test your calculator using the solution
dlist.  Thus, any error in those tests mean that you have a buggy
calulator.  The final three tests (4-6) will test your dlist
implementation.  Errors in these test cases indicate a buggy dlist
implementation.  

You may submit your program as many times as you like.  However, only
the first submission of each day will be graded and mailed back to
you.  Later submissions on that day will be graded and cataloged, but
the results will not be mailed back to you.  See the FAQ for why we
use this policy.

In addition to this one-per-day policy, you will be given 3 bonus
submissions that also provide feedback.  These will be used
automatically--any submission you make after the first one of that day
will use one of your bonus submissions.  After your 3 bonus
submissions are used up, the system will continue to provide 1
feedback per day.