// Doubly Linked List with templates and inheritance example
// Steve J. Hodges, CS19, Spring 2006
// NOT FOR DISTRIBUTION, DO NOT DUPLICATE


#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>


// forward class definition
template <class T>
class List;


// LinkNode helper class for List
// internal connection for List class
template <class T>
class LinkNode{
  friend class List<T>;
 public:
  LinkNode(){next = prev = 0; data=0;}
  ~LinkNode(){ if (data){ delete data; data=0;} }
 private:
  T *data;
  LinkNode *next;
  LinkNode *prev;
};



// Linked List class with Templates
// insert - pointer to T - insert at front of List
// delete - pointer to T - delete first object in list that matches
// print -- prints all items in the list
template <class T>
class List{
 public:
  List(){ first = last = 0; } 
  ~List(); 
  void insertFront( T *);
  void insertRear( T *);
  T *removeFront();
  T *removeRear();
  void print(); 
  void printR();
 private:
  LinkNode<T> *first;
  LinkNode<T> *last;
};


template <class T>
List<T>::~List(){
  LinkNode<T> *link = first;

  while (first){
    link = first;
    first = first-> next;
    if (link->data){
      delete link->data;
      link->data=0;
    }
    delete link;
  }
}

template <class T>
void List<T>::insertFront(T *d){
  LinkNode<T> *link = new LinkNode<T>();
  T *nd = new T();
  *nd = *d;  // default memberwise copy or overloaded assignment
  link->data = nd;  // attach data
  // link->prev stays at 0 no change

  if(first == 0){
    first = last = link;
    return;
  }

  link->next = first;
  first->prev = link;
  first = link;
}



template <class T>
T *List<T>::removeFront(){
  T *temp=0;
  if (first == 0) return 0;

  // splice out data node
  temp = first->data;
  first->data = 0;

  if (first == last){
    delete first;
    first = last = 0;
    return temp;
  }

  Linknode<T> *link = first;
  first->next->prev = 0;
  first=first->next;
  delete link;
  return temp;
}




template <class T>
void List<T>::insertRear(T *d){
  LinkNode<T> *link = new LinkNode<T>();
  T *nd = new T();
  *nd = *d;  // default memberwise copy or overloaded assignment
  link->data = nd;  // attach data
  // link->prev stays at 0 no change


  if(first == 0){
    first = last = link;
    return;
  }
  last->next = link;
  link->prev = last;
  last = link;
}

template <class T>
T *List<T>::removeRear(){
  T *temp=0;
  if (last == 0) return 0;

  // splice out data node
  temp = last->data;
  last->data = 0;

  if (first == last){
    delete last;
    first = last = 0;
    return temp;
  }
  LinkNode<T> *todel = last;
  last->prev->next = 0;
  last = last->prev;
  delete todel;  // delete node that was formerly last
  return temp;
}


template <class T>
void List<T>::print(){
  LinkNode<T> *link = first;
  while(link){
    std::cout << *(link->data) << " ";
    link = link->next;
  }
  std::cout << endl;
}

template <class T>
void List<T>::printR(){
  LinkNode<T> *link = last;
  while(link){
    std::cout << *(link->data) << " ";
    link = link->prev;
  }
  std::cout << endl;
}


// -------------------------------------------------------------------

template <class T>
class Stack : public List<T>{
 public:
  void push(T *d){ insertFront(d); }
  T *pop(){ return removeFront(); }
};


// -------------------------------------------------------------------


template <class T>
class Queue : public List<T>{
 public:
  void enque(T *d){ insertRear(d); }
  T *deque(){ return removeFront(); }
};



#endif