//////////////////////////////////////////////////////////////////
//
//  simple_list.h 
//
//  this is the simplest (and the most inefficient) implementation
//  of the singly linked list idea.
//
//  Implement the following member functions:
//
//        T  List<T>::at( int index )  
//      void List<T>::add_back( const T& new_elt )
//      void List<T>::remove( int index )
//      bool List<T>::includes( const T& value )   
//      void List<T>::insert( int index, const T& new_elt )  

#include <stdlib.h>

template< class T >
struct Node {
  T data;
  Node<T> * next;

  // Notice:  there is no default constructor, 
  //          so smth like  Node<int> anode;  won't compile. 
  //           A  Node<T>  can only be created with actual data item and 
  //           the "next" pointer
    
  Node( const T& d, Node<T>* n) :
    data( d ), next( n ) {
      cout << "Node with data item " << data << " created\n"; 
  }

  ~Node() {
    cout << "Node with data item " << data << " destroyed\n";
  }
};

template< class T >
class List {
private:
  Node<T> * first;
  Node<T> * last;             // will be  needed for add_back
  List( const List<T>& );     // copy constr. not allowed
  void operator= ( const List<T>& ); // not allowed 

public:
  List() : first(NULL), last(NULL) {};
  ~List();                    // the destructor is non-trivial -- 
                              // it must de-allocate the entire chain!
  void add_front( const T& new_elt );

  // implement these guys:

  T    at( int i );                    // return value at i-th position 
   
  void add_back( const T& new_elt );   // adds to the back of the list; 
                                       //   use Node<T> * last for efficiency
  bool remove( int index );            // removes k-th element, 
                                       //    returns true if successful,
                                       //    returns false is  k-th element 
                                       //      doesn't exist
  bool includes( const T& elt );       // true if elt is in the list, 
                                       //    false otherwise
  void insert( int index, const T& new_elt );   // insert new_elt at position 
                                                //   index, or at the tail.

  void display();
};

template< class T >
List<T>::~List(){
  Node<T> * ptr = first;
  Node<T> * doomed;
  while( ptr != NULL ){
    doomed = ptr;
    ptr = ptr->next;
    delete doomed;
  }
}

template< class T >
void List<T>::add_front( const T& new_elt ){

  Node<T> * new_node_ptr = new Node<T>( new_elt, first );
  first = new_node_ptr;
}

template< class T >
void List<T>::display(){
  Node<T> * ptr = first;
  while( ptr != NULL ){
    cout << ptr->data << " "; 
    ptr = ptr->next;
  }
  cout << endl;
} 
  
///////////////////////////////////////////////////////////////////////////
//   
//  simple_list_test.cc
//
//  Implement (in simple_list.h) and test in a similar fashion the following 
//  functions:
//      at, add_back, includes, remove, insert 
//       

#include <iostream.h>
#include <string>
#include <stdlib.h>

// #include "simple_list.h"

int main(){
   
  List<int> l1;

  for( int i=0; i < 10; i++ )
    l1.add_front( i );

  l1.display();

  List<string> l2;
  
  l2.add_front( "be" );
  l2.add_front( "to" );
  l2.add_front( "not" );
  l2.add_front( "or" );
  l2.add_front( "be" );
  l2.add_front( "to" );

  l2.display();

  return 0; 

  // now the lists are destroyed -- make sure all nodes get destroyed
};