Computer Science II Lab 5
                  Lists, Stacks, and Deep Pondering


  Introduction
  ============
  Now that you've had some fun writing a game, let's continue the
  challenge by using data structures to solve complex problems.  In
  this lab, we'll take a look at a linked list, class templates, and
  doubly linked lists.  Finally, we will create a stack class which
  you will then use to solve a complex computer science problem.


  Crafting your Data Structures (Guided) 
  ======================================
  Many problems are best solved using the proper data structures.  In
  this section, we will take a simple linked list and turn it into a
  doubly linked list.   The first step will be to copy the list.h file
  from the gopher directory.  This is a simple singly linked list with
  an iterator.  For convenience, I am listing the list.h file here,
  but you can go ahead and copy my file.

  --begin list.h--
     1	/*
     2	 * File: list.h
     3	 * Purpose:  Just a small linked list class
     4	 */
     5	#ifndef LIST_H
     6	#define LIST_H
     7	
     8	class List {
     9	private:
    10	  class Node;
    11	  
    12	public:
    13	  // Constructor and destructor 
    14	  List() {
    15	    head = tail = 0x00;
    16	  }
    17	
    18	  
    19	  ~List() {
    20	    Node *cur;
    21	
    22	    //start at the head
    23	    cur = head;
    24	
    25	    //kill all the things!
    26	    while(cur) {
    27	      cur = cur->next;
    28	      delete head;
    29	      head = cur;
    30	    }
    31	  }
    32	
    33	  
    34	  //high level operations
    35	  void append(int data) {
    36	    Node *node = createNode(data);
    37	    
    38	    //special case, empty list!
    39	    if(isEmpty()) {
    40	      head = tail = node;
    41	      return;
    42	    }
    43	
    44	    tail->next = node;
    45	    tail = node;
    46	  }
    47	  
    48	  void prepend(int data) {
    49	    Node *node = createNode(data);
    50	
    51	    //special case, empty list!
    52	    if(isEmpty()) {
    53	      head = tail= node;
    54	      return;
    55	    }
    56	
    57	    node->next = head;
    58	    head=node;
    59	  }
    60	
    61	  
    62	  bool isEmpty() {
    63	    return !head;
    64	  }
    65	  
    66	
    67	  //iterator
    68	  class iterator {
    69	  public:
    70	    //dereference
    71	    int operator*() {
    72	      return node->data;
    73	    }
    74	
    75	    //comparison
    76	    bool operator==(const iterator &rhs) {
    77	      return node == rhs.node;
    78	    }
    79	
    80	    bool operator!=(const iterator &rhs) {
    81	      return node != rhs.node;
    82	    }
    83	
    84	    //movement
    85	    iterator &operator++() {
    86	      if(node) node=node->next;
    87	      return *this;
    88	    }
    89	    
    90	    iterator operator++(int) {
    91	      iterator itr(*this);
    92	
    93	      if(node) node=node->next;
    94	      return itr;
    95	    }
    96	
    97	    iterator &operator--() {
    98	      node=l.findPrevious(node);
    99	      return *this;
   100	    }
   101	
   102	    iterator operator--(int) {
   103	      iterator itr(*this);
   104	      
   105	      node=l.findPrevious(node);
   106	
   107	      return itr;
   108	    }
   109	    
   110	  private:
   111	    //current node
   112	    Node *node;
   113	    List &l;
   114	
   115	    //private constructor
   116	    iterator(Node *node, List &lst): l(lst) { this->node = node; }
   117	
   118	
   119	    //we have but one friend
   120	    friend class List;
   121	
   122	  };
   123	
   124	  //iterator creation
   125	  iterator begin() {
   126	    return iterator(head, *this);
   127	  }
   128	
   129	  
   130	  iterator end() {
   131	    return iterator(0x00, *this);
   132	  }
   133	
   134	
   135	  //iterator action
   136	  void insertAfter(iterator &itr, int data) {
   137	    //special case, insertion at the tail
   138	    if(!itr.node || itr.node==tail) {
   139	      append(data);
   140	      return;
   141	    }
   142	
   143	        
   144	    //insert after the iterator node
   145	    Node *node = createNode(data);
   146	    node->next = itr.node->next;
   147	    itr.node->next = node;
   148	  }
   149	  
   150	
   151	  
   152	private:
   153	  //inner type for storage of information
   154	  class Node {
   155	  public:
   156	    int data;     //the payload
   157	    Node *next;   //the link
   158	
   159	    Node() { next=0x00; }
   160	  };
   161	
   162	  //private data elements
   163	  Node *head;
   164	  Node *tail;
   165	
   166	  //private helpers
   167	  Node * createNode(int data) {
   168	    Node *node = new Node();
   169	    node->data = data;
   170	    return node;
   171	  }
   172	
   173	  
   174	  Node * findPrevious(Node *node) {
   175	    Node * cur = head;
   176	
   177	    while(cur) {
   178	      if(cur->next == node)
   179	        return cur;
   180	      cur = cur->next;
   181	    }
   182	  }
   183	};
   184	
   185	#endif
  --end list.h--

  Review your notes about this list class and look it over.  Make sure
  you understand everything in the file before proceeding.  Now we are
  going to convert list.h into a doubly linked list.  Recall that a
  doubly linked list contains pointers in both directions.  The first
  step is to add this previous pointer to our internal node class.
  Modify your node class so that it looks like this:

  class Node {
  public:
    int data;     //the payload
    Node *next;   //the link
    Node *prev;   // the previous node
    Node() { next=0x00; }
  };


  Now that we have the previous link established, we have to make a
  few changes in the functions dealing with the links. Modify your
  append function so that it looks like this:

  //high level operations
  void append(int data) {
    Node *node = createNode(data);
    
    //special case, empty list!
    if(isEmpty()) {
      head = tail = node;
      return;
    }

    node->prev = tail;
    tail->next = node;
    tail = node;
  }


  Prepend must also be modified:

  void prepend(int data) {
    Node *node = createNode(data);

    //special case, empty list!
    if(isEmpty()) {
      head = tail= node;
      return;
    }

    node->prev = 0x00;
    node->next = head;
    head=node;
  }

  The decrement operators in the iterator class must also change:

    iterator &operator--() {
      if(node) 
        node=node->prev;
      else
        node=l.tail;

      return *this;
    }

    iterator operator--(int) {
      iterator itr(*this);

      if(node) 
        node=node->prev;
      else
        node=l.tail;

      return itr;
    }

  Let's add 1 more operator to the iterator, to make things a little
  easier later on:

    iterator & operator=(const iterator &itr) {
      this->node = itr.node;
      return *this;
    }

  Next we need to modify insertAfter:

  //iterator action
  void insertAfter(iterator &itr, int data) {
    //special case, insertion at the tail
    if(!itr.node || itr.node==tail) {
      append(data);
      return;
    }

        
    //insert after the iterator node
    Node *node = createNode(data);
    node->next = itr.node->next;
    itr.node->next = node;
  }

  Now that deletion is easy, we'll add  a new function:

   void remove(iterator &itr) {
    Node * node=itr.node;

    //update the iterator
    itr--;

    //handle the head node
    if(node==head) {
      head = node->next;
    }

    //handle the tail node
    if(node == tail) {
      tail = tail->prev;
    }

    //unlink
    if(node->prev)
      node->prev->next = node->next;
    if(node->next)
      node->next->prev = node->prev;

    //remove the node
    delete node;
  }

  
  Finally, we no longer need the private function "findPrevious" so go
  ahead and remove it.

  Now, before we continue, look over your modified list.h and take
  think about how the whole thing works.  Make sure you can get a
  clear mental image of how your linked list now works!

  Now, let's test our doubly linked list.  Enter and compile the
  following program.  If it works, it should display 1 and 2 on
  separate lines:

  --begin listTest.cpp--
     1	#include <iostream>
     2	#include "list.h"
     3	
     4	using namespace std;
     5	
     6	int main(void) {
     7	  List lst;
     8	  List::iterator itr = lst.end();
     9	  int i;
    10	
    11	
    12	  lst.append(1);
    13	  lst.append(2);
    14	  lst.append(3);
    15	
    16	  itr = lst.begin();
    17	  itr++;
    18	  ++itr;
    19	  lst.remove(itr);
    20	
    21	  for(itr=lst.begin(); itr!=lst.end(); itr++)
    22	    cout << *itr << endl;
    23	  
    24	  return 0;
    25	
    26	}
  --end listTest.cpp--

  Make sure this program works properly, and that you fully understand
  what it is doing before you proceed!

  Now, we have a really awesome container which can store as many
  integers as we want.  The problem is, there are more things in
  heaven and earth than are dreamt of by whole numbers!  So, let's
  generalize our class!

  We are going to modify our list by turning it into a template.
  Basically, the only thing that has to change each time we want to
  store a new type is the declared type of the data element.  This is
  such a trivial change that we can leave that to the compiler.
  Basically, the compiler will generate a new version of the class for
  each data type we want to store.  

  The first step is to tell the compiler that the list class is not
  really a class, but it is a template class.  To do this, add the
  following before the class List definition:

    template <typename T>

  Now, we have the ability to pass in a type name as a template
  variable.  For instance, to make a list of integers, we could do:

    List<int> lst;

  Now, all that remains is to modify the class so it uses the template
  type instead of int.  This involves modifying 6 lines of code.  The
  modified versions of these lines appears as follows:

    void append(T data) {
    void prepend(T data) {
    T &operator*() {
    void insertAfter(iterator &itr, T data) {
    T data;       //the payload
    Node * createNode(T data) {

  I'm not going to tell you where they are though.  Finding them will
  be a good learning experience for you!

  Now, the last order of business before we move on to more
  interesting data structures is to get your listTest.cpp working with
  the template list.  There is a hint on how to do this earlier in
  this section.  You'll have to make a couple of changes, just let the
  compiler be your guide!


  All right!  Now that you have a templated list, let's make a stack
  out of it.  As we discussed in class, a stack is just a special kind
  of list, but we do not want to expose all the list functions to the
  users of the stack.  For this reason, we use the (admittedly
  controversial) private inheritance feature of C++.  The template
  stack.h file is listed below:

  --begin stack.h--
     1	/*
     2	 * File: Stack.h
     3	 * Purpose: Template linked list implementation of stack
     4	 */
     5	#ifndef STACK_H
     6	#define STACK_H
     7	
     8	#include "list.h"
     9	
    10	template<typename T>
    11	class Stack : private List<T>{
    12	  public:
    13	
    14	  //stack operations
    15	  void push(T data) {
    16	    this->prepend(data);
    17	  }
    18	
    19	  //pop the stack
    20	  T pop() {
    21	    T result;
    22	    typename List<T>::iterator itr = this->begin();
    23	    
    24	    result = *itr;
    25	    this->remove(itr);
    26	    
    27	    return result;
    28	  }
    29	  
    30	
    31	  T peek() {
    32	    return *(this->begin());
    33	  }
    34	
    35	  bool isEmpty(){
    36	    return List<T>::isEmpty();
    37	  }
    38	  
    39	};
    40	#endif
  --end stack.h--

  And let's wrap up the handholding with a nice little stack test
  file:

  --begin stackTest.cpp--
     1	#include <iostream>
     2	#include "stack.h"
     3	
     4	using namespace std;
     5	
     6	int main(void) {
     7	  Stack<int> s;
     8	
     9	  s.push(1);
    10	  s.push(2);
    11	  s.push(3);
    12	
    13	  while(!s.isEmpty())
    14	    cout << s.pop() << endl;
    15	
    16	  return 0;
    17	}
    18	    
  --end stackTest.cpp--


  That's it!  Verify that your stackTest works, and then you're on
  your own!



  Solving Difficult Problems with Stacks (Challenge)
  ==================================================
  That's a nice stack class you have there!  Let's see if you can put
  it to good use.  Remember that you can use stacks to simulate
  recursion, do back tracking, and directly solve inherently stack
  based problems.  Take a look at our examples section on gopher to
  get a good feel for how that works.  After you have done that, pick
  one of the problems from below and solve it using our stack class!


  Problems (choose one)
  ---------------------
  1.)  Write a program which can solve sudoku puzzles.  Sudoku puzzles
       are a 9x9 grid where each row and column contains each number
       1-9 only once.  Also, each 3x3 segment of the grid can only
       contain each number once.  Write your program so that it can
       take in a file containing a sudoku representation and prints
       out the completed puzzle.


  2.) Write a program which can solve the N-queens problem.  The
      N-queens puzzle is to place N queens on an NxN chess board so
      the queens do not attack each other.  Keep in mind that a queen
      can move any number of squares in a straight line or in a
      diagonal line.  Your program should take in the number of queens
      and print out a representation of the chess board with your
      queens in position.

  3.) Write a program which solves the knight's tour problem.  The
      knight's tour is a puzzle where a knight is placed on a chess
      board and then moved, using only legal knight moves, so that it
      visits each square exactly once.  It's OK for the knight to pass
      over a visited square, but it must not land on a visited
      square.  The program should take as input a letter and number
      indicating the initial position on a chess board.  It should
      then print out a series of squares that the knight lands on.
      
      It should print out 63 squares, with no revisited squares.

  4.) Write a program which can convert between RPN and fully
      parenthesized expressions.  The program should ask the user
      which they intend to enter, and then convert the input into the
      other type of expression.

  5.) Write a program which can solve those triangle peg puzzles
      featured at certain country themed restaurants.  The basic idea
      is this.  You start out with a triangle of pegs:
          0
         * *
        * * *
       * * * *
      * * * * *

      Where a * is a peg and 0 is an empty space.  The goal is to
      remove pegs by jumping them with other pegs and end up with only
      1 peg remaining.  You can only jump along the diagonal paths in
      the puzzle.  

      For added challenge, let's make the program so that you can
      enter the location of the hole.  Your program should display
      what the puzzle looks like after each jump.


  Extra Credit
  ============
  You get full credit for solving just one of these problems.  I will
  give you 25 points extra credit for other solutions.  So if you do
  all 5, you will get a 200 on the lab!

  Good luck!