// Linked List with templates example codes
// 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=0; data=0;}
  ~LinkNode(){ if (data){ delete data; data=0;} }
 private:
  T *data;
  LinkNode *next;
};



// 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 = 0; }
  ~List();
  void insert( T *);
  void remove( T *);
  void print();
 private:
  LinkNode<T> *first;

};

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>::insert(T *d){
  LinkNode<T> *link = new LinkNode<T>();
  T *nd = new T();
  *nd = *d;  // default memberwise copy or overloaded assignment
  link->next = first;
  first = link;
  link->data = nd;  // attach data
}


template <class T>
void List<T>::remove(T *d){
  LinkNode<T> *temp = first;

  if(!first) return;

  if( *(first->data) == *d ){
    first = first->next;
    delete temp->data; temp->data = 0;
    delete temp;
    return;
  }

  temp = first->next;
  LinkNode<T> *prev = first;
  while(temp){
    if( *(temp->data) == *d ){
      prev->next = temp->next;
      delete temp->data; temp->data = 0;
      delete temp;
      return;
    }
    prev = temp;
    temp = temp->next;
  }
}

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

#endif