//
// LinkedList implementation
// Pointer-based using templates
//

#include <iostream>

#ifndef __LLIST
#define __LLIST


// Additional defintions
template <class T>
class __ListNode {
 public:
  T data;
  __ListNode<T>* next;
};

// Linked List class definition
template <class T>
class List {
  // Private Members
  int Size;
  __ListNode<T>* Head;

  __ListNode<T>* dup (const __ListNode<T>*);

 public:
  // Constructor 
  List () : Head (NULL), Size (0) { }
  List (const List& l) { this->Head = dup (l.Head); }
  virtual ~List ();
  
  // List Methods (Interface)
  virtual int Length () const { return Size; }
  virtual bool Empty ();
  virtual int Find (T& item) const;
  virtual bool Insert (T&, int);
  virtual bool Insert (T* n, int P) { return Insert (*n, P); }
  virtual bool Delete (T&, int);
  virtual bool Retrieve (T&, int) const;
  virtual bool Traverse (bool (*) (T&)) const;
  virtual bool Print (bool (*) (T&)) const;

  friend ostream& operator << <> (ostream&, List<T>&);
  void operator = (List<T>& l) { this->Head = dup (l.Head); }
  
 private:
  __ListNode<T>* FindPrev (int) const;

};

// Copy constructor
template <class T>
__ListNode<T>* List<T>::dup (const __ListNode<T>* l) // : Size (l.Size)
{
  __ListNode<T>* n = NULL;

  if (l != NULL)
    {
      n = new (__ListNode<T>);
      n->data = ldata;
      __ListNode<T>* tmpRef = n;
      for (__ListNode<T>* orgRef = l->next; orgRef; orgRef = orgRef->next)
	{
	  tmpRef->next = new (__ListNode<T>);
	  tmpRef = tmpRef->next;
	  tmpRef->data = orgRef->data; 
	}
      tmpRef->next = NULL;
    }
  return n;
}

// Destructor
template <class T>
List<T>::~List ()
{
  __ListNode<T>* tmpRef = this->Head, *nxtRef;
  
  while (tmpRef != NULL)
    {
      nxtRef = tmpRef->next;
      delete tmpRef;
      tmpRef = nxtRef;
    }
}

// Empty
template <class T>
bool List<T>::Empty ()
{
  __ListNode<T>* tmpRef = this->Head;
  
  while (tmpRef != NULL)
    {
      tmpRef = tmpRef->next;
      delete this->Head;
      this->Head = tmpRef;
    }
  this->Size = 0;
  this->Head = NULL;
  return true;
}


// Find previous (private method)
template <class T>
__ListNode<T>* List<T>::FindPrev (int Position) const
{
  __ListNode<T>* tmpRef = this->Head;
  
  for (; tmpRef && (Position > 2); Position--)
    tmpRef = tmpRef->next;
  return tmpRef;
}

// Return position of the specified element
template <class T>
int List<T>::Find (T& item) const
{
  int pos = -1, i = 1;
  __ListNode<T>* tmpRef;
  
  for (tmpRef = this->Head; tmpRef != NULL; tmpRef = tmpRef->next, i++)
    if (item == tmpRef->data)
      pos = i;
  return pos;
}

// Insert new item 
template <class T>
bool List<T>::Insert (T& newItem, int Position)
{
  __ListNode<T>* newNode, *prevNode;
  
  if ((Position > this->Size + 1) || (Position < 1))
    return false;
  
  newNode = new (__ListNode<T>);
  newNode->data = newItem; 
  if (Position == 1)
    { 
      newNode->next = this->Head; 
      this->Head = newNode;  
    }
  else
    { 
      prevNode = FindPrev (Position); 
      newNode->next = prevNode->next; 
      prevNode->next = newNode; 
    }
  this->Size++;
  return true;
}

// Delete specified item
template <class T>
bool List<T>::Delete (T& Item, int Position)
{
  __ListNode<T>* prevNode, *tmpRef;
  
  if ((Position > this->Size) || (Position < 1))
    return false;
  
  if (Position == 1)
    {  
      tmpRef = this->Head;
      this->Head = this->Head->next;
    }
  else
    {
      prevNode = FindPrev (Position);
      tmpRef = prevNode->next;
      prevNode->next = tmpRef->next;
    }
  Item = tmpRef->data;
  delete tmpRef; 
  this->Size--;
  return true;
}

// Find an element by position
template <class T>
bool List<T>::Retrieve (T& item, int Position) const
{
  __ListNode<T>* tmpRef;
  
  if ((Position > this->Size) || (Position < 1))
    return false;
  
  tmpRef = FindPrev (Position + 1);
  item = tmpRef->data;
  return true;
}

// Execute specified function for each item in current list
template <class T>
bool List<T>::Traverse (bool (*act) (T&)) const
{
  __ListNode<T>* tmpRef = this->Head;
  
  while (tmpRef)
    {
      if (act (tmpRef->data) == false) 
	return false;
      tmpRef = tmpRef->next;
    }
  return true;
}

// Print list content
template <class T>
bool List<T>::Print (bool (*p) (T&)) const
{
  __ListNode<T>* tmpRef;
  
  for (tmpRef = Head; tmpRef && p (tmpRef->data); tmpRef = tmpRef->next);
  return true;
}

// Operator for easier handling
template <class T>
ostream& operator << (ostream& out, List<T>& obj)
{
  __ListNode<T>* tmpRef;

  for (tmpRef = Head; tmpRef; tmpRef = tmpRef->next)
    out << tmpRef->data << " ";
  out << endl;
  return out;
}

#endif // __LLIST