//////////////////////////////////////////////////////////////////
// File: "LList.h"
//
// Purpose: A doubly linked templated list and iterator.
//
//////////////////////////////////////////////////////////////////

#if !defined(AFX_LLIST_H__1BE8D7C8_7710_45EC_A59E_99BAC77CDCA7__INCLUDED_)
#define AFX_LLIST_H__1BE8D7C8_7710_45EC_A59E_99BAC77CDCA7__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <windows.h>

// forward declaration to allow the LinkedList
// to know about LinkedListIterator.
template <typename Type> class LinkedListIterator;

template <typename Type>
class LList
{
// Protected so we can derive a stack or queue
protected:

	// create a friend class declaration
	// the iterator is a friend.
	friend class LinkedListIterator<Type>;

	// A Node structure. We store the templated data
	// and pointers to the next and previous nodes.
	struct Node
	{
		Node *next;
		Node *prev;

		Type Data;
	};

	// Head and tail pointers. These allow us quick access
	// to the beginning and end of the list.
	Node *head;
	Node *tail;

	// The number of nodes in the list
	int ListSize;

	// Internal functions used for insertion and deletion
	bool Delete(Node** node);
	bool Insert(Node *node, Type data);

public:

	// Constructor
	LList();

	// Destructor
	~LList();
};


/******************************/
/* Linked List Iterator Class */
/******************************/


// LinkedListIterator
// used to handle for-looping and accessing our list.
template <typename Type>
class LinkedListIterator
{
   private:

      // our iterator keeps track of the 'current'
      // element that it is looking at.
      LList<Type> *list;
      LList<Type>::Node *currentNode;

   public:

      // Ctr.
      // the constructor has to know which
      // list to work with.
      LinkedListIterator (LList<Type> *theList);

      // initialize the iterator to start at the beginning
      void setToHead () { currentNode = list->head; }
	  
	  // initialize the iterator to end 
	  void setToTail() { currentNode = list->tail; }

      // a function to check to see if we are finished.
      bool finished () { return (currentNode == NULL); }
	  
	  // check if were at the beginning
	  bool atStart() { return (currentNode == list->head->prev); }

      // a way to increment the iterator.
      LinkedListIterator<Type> &operator++ ();
	  
	  // decrement the iterator
	  LinkedListIterator<Type> &operator--();

      // get access to the current item
      Type current () { return currentNode->Data; }
};

// constructor
//IN: theList  the list to iterate
template <typename Type>
LinkedListIterator<Type>::LinkedListIterator (LList<Type> *theList)
{
   list = theList; // store the list.
   // initialize the currentNode.  
   currentNode = NULL;
}

// increment the iterator
template <typename Type>
LinkedListIterator<Type> &LinkedListIterator<Type>::operator++ ()
{
   if (currentNode != NULL) // currentNode already at end?
   {
      currentNode = currentNode->next;
   }
  
   return *this;
}

// decrement the iterator
template <typename Type>
LinkedListIterator<Type> &LinkedListIterator<Type>::operator--()
{	
	// same as ++ only move to the previous node
	if (currentNode != NULL)
	{
		currentNode = currentNode->prev;
	}

	return *this;
}

#endif // !defined(AFX_LLIST_H__1BE8D7C8_7710_45EC_A59E_99BAC77CDCA7__INCLUDED_)