#ifndef _LIST_CPP_
#define _LIST_CPP_

#include "list.h"
#include <stddef.h>
#include <assert.h>

template < class listItemType > struct listNode {
    listItemType Item;		// a data item on the list
    struct listNode <listItemType > *Next;	// pointer to next node
};

template < class listItemType > List < listItemType >::List():Size(0),
head(NULL)
{
}

template < class listItemType >
    List < listItemType >::List(const List & L):Size(L.Size)
{
    if (L.head == NULL)
	head = NULL;		// original list is empty
    else {
	// copy first node
	head = new listNode < listItemType >;
	assert(head != NULL);	// check allocation
	head->Item = L.head->Item;

	// copy rest of list
	listItemType *NewPtr = head;	// new list pointer

	// NewPtr points to last node in new list 
	// OrigPtr points to nodes in original list
	for (listItemType * OrigPtr = L.head->Next; OrigPtr != NULL;
	     OrigPtr = OrigPtr->Next) {
	    NewPtr->Next = new listNode < listItemType >;
	    assert(NewPtr->Next != NULL);
	    NewPtr = NewPtr->Next;
	    NewPtr->Item = OrigPtr->Item;
	}

	NewPtr->Next = NULL;
    }
}

template < class listItemType > List < listItemType >::~List()
{
    while (!isEmpty())
	listDelete(1);
}

template < class listItemType > bool List < listItemType >::isEmpty() const
{
    return bool(Size == 0);
}

template < class listItemType > int List < listItemType >::listLength() const
{
    return Size;
}

template < class listItemType >
    struct listNode <listItemType > *List <
    listItemType >::ptrTo(int position) const
{
    if ((position < 1) || (position > listLength()))
	return NULL;
    else {
	struct listNode <listItemType > *Cur = head;
	for (int Skip = 1; Skip < position; ++Skip)
	    Cur = Cur->Next;

	return Cur;
    }
}

template < class listItemType >
    void List < listItemType >::listRetrieve(int position,
					     listItemType & dataItem) const
{
    bool Success = bool((position >= 1) && (position <= listLength()));

    if (Success) {
	struct listNode <listItemType > *Cur = ptrTo(position);
	dataItem = Cur->Item;
    }
}

template < class listItemType >
    void List < listItemType >::listReplace(int position,
					    listItemType & dataItem) const
{
    bool Success = bool((position >= 1) && (position <= listLength()));

    if (Success) {
	struct listNode <listItemType > *Cur = ptrTo(position);
	Cur->Item = dataItem;
    }
}

template < class listItemType >
    void List < listItemType >::listInsert(int newPosition,
					   listItemType newItem)
{
    int NewlistLength = listLength() + 1;

    bool Success = bool((newPosition >= 1)
			&& (newPosition <= NewlistLength));

    if (Success) {		// create new node and place newItem in it
	struct listNode <listItemType > *NewPtr =
	    new listNode < listItemType >;
	Success = bool(NewPtr != NULL);
	if (Success) {
	    Size = NewlistLength;
	    NewPtr->Item = newItem;

	    // attach new node to list
	    if (newPosition == 1) {	// insert new node at beginning of list
		NewPtr->Next = head;
		head = NewPtr;
	    } else {
		struct listNode <listItemType > *Prev =
		    ptrTo(newPosition - 1);
		// insert new node after node 
		// to which Prev points
		NewPtr->Next = Prev->Next;
		Prev->Next = NewPtr;
	    }
	}
    }
}

template < class listItemType >
    void List < listItemType >::listDelete(int position)
{
    struct listNode <listItemType > *Cur;

    bool Success = bool((position >= 1) && (position <= listLength()));

    if (Success) {
	--Size;
	if (position == 1) {
	    Cur = head;
	    head = head->Next;
	} else {
	    struct listNode <listItemType > *Prev = ptrTo(position - 1);
	    Cur = Prev->Next;
	    Prev->Next = Cur->Next;
	}

	Cur->Next = NULL;
	delete Cur;
	Cur = NULL;
    }
}

#endif