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

#include <iostream>
#include <assert.h>


#ifndef __TLLIST
#define __TLLIST

//
// Node definition
//
template <class itemListType>
class Node {

 public:
  itemListType data;
  Node<itemListType>* next;
};

//
// Linked List class definition
//
template <class itemListType>
class LinkedList {

  int Size;
  Node<itemListType>* Head;

 public:

  // Constructor 
  LinkedList () : Head (NULL), Size (0)
    {

    }

  // Copy constructor
  LinkedList (const LinkedList& l) : Size (l.Size)
    {
      if (l.Head == NULL)
        this->Head = NULL;
      else
        {
          assert (this->Head = new (Node<itemListType>));
          // this->Head->data = l.Head->data;
          this->Head->data = * new itemListType (l.Head->data);
          Node<itemListType>* tmpRef = this->Head;
          for (Node<itemListType>* orgRef = l.Head->next; 
                                    orgRef; orgRef = orgRef->next)
            {
              assert (tmpRef->next = new (Node<itemListType>));
              tmpRef = tmpRef->next;
              // tmpRef->data = orgRef->data; 
              tmpRef->data = * new itemListType (orgRef->data);
            }
          tmpRef->next = NULL;
        }
    }

  // Destructor
  virtual ~LinkedList ()
    {
      Node<itemListType>* tmpRef = this->Head, *nxtRef;

      while (tmpRef != NULL)
        {
          nxtRef = tmpRef->next;
           delete tmpRef;
          tmpRef = nxtRef;
        }
    }

  // Empty
  virtual bool
  Empty ()
    {
      Node<itemListType>* tmpRef = this->Head;

      while (tmpRef != NULL)
        {
          tmpRef = tmpRef->next;
          delete this->Head;
          this->Head = tmpRef;
        }
      this->Size = 0;
      this->Head = NULL;
      return true;
    }

  virtual int
  Length () { return Size; }

 private:

  // Find previous (private method)
  Node<itemListType>*
  FindPrev (int Position) const
    {
      Node<itemListType>* tmpRef = this->Head;

      for (; tmpRef && (Position > 2); Position--)
        tmpRef = tmpRef->next;
      return tmpRef;
    }

 public:

  // Return position of the specified element
  virtual int
  Find (itemListType& item) const
    {
      int pos = -1, i = 1;
      Node<itemListType>* tmpRef;

      for (tmpRef = this->Head; tmpRef != NULL; tmpRef = tmpRef->next, i++)
        if (item == tmpRef->data)
          pos = i;
      return pos;
    }

  // Insert new item 
  virtual bool 
  Insert (itemListType newItem, int Position)
    {
      Node<itemListType>* newNode, *prevNode;

      if ((Position > this->Size + 1) || (Position < 1))
        return false;

      assert (newNode = new (Node<itemListType>));
      // newNode->data = newItem; 
      newNode->data = * new itemListType (newItem);
      if (Position == 1)
        { 
          newNode->next = this->Head; 
          this->Head = newNode;  
        }
      else
        { 
          assert (prevNode = FindPrev (Position)); 
          newNode->next = prevNode->next; 
          prevNode->next = newNode; 
        }
      this->Size++;
      return true;
  }

  // Insert new item (reference)
  virtual bool
  Insert (itemListType* newItem, int Position)
    {
      return Insert (*newItem, Position);
    }

  // Delete specified item
  virtual bool 
  Delete (itemListType& Item, int Position)
    {
      Node<itemListType>* prevNode, *tmpRef;

      if ((Position > this->Size) || (Position < 1))
        return false;

      if (Position == 1)
        {  
          tmpRef = this->Head;
          this->Head = this->Head->next;
        }
      else
        {
          assert (prevNode = FindPrev (Position));
          tmpRef = prevNode->next;
          prevNode->next = tmpRef->next;
        }
      Item = tmpRef->data;
      delete tmpRef; 
      this->Size--;
      return true;
  }

  // Find an element by position
  virtual bool
  Retrieve (itemListType& item, int Position)
    {
      Node<itemListType>* 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
  virtual bool
  Traverse (bool (*act) (itemListType))
    {
      Node<itemListType>* tmpRef = this->Head;

      while (tmpRef)
        {
          if (act (tmpRef->data) == false) 
            return false;
          tmpRef = tmpRef->next;
        }
      return true;
  }

  // Print list content
  virtual bool
  Print (ostream& out)
    {
      Node<itemListType>* tmpRef = this->Head;

      while (tmpRef != NULL)
        { 
          cout << tmpRef->data << " ";
          tmpRef = tmpRef->next;
        }
      cout << endl;
      return true;
    }

  // Operator for easier handling
  friend ostream& 
  operator << (ostream& out, LinkedList<itemListType>& obj)
    {
      obj.Print (out); 
      return out;
    }

  // Operator for easier handling
  bool
  operator == (LinkedList<itemListType> obj) const
    {
      return false;
    }

};

#endif