#include "Sorted.h"
#ifndef _SORTED_LINKED_CPP_
#define _SORTED_LINKED_CPP_

template <class ItemType> SortedType<ItemType>::SortedType()
{
	listData = NULL;
    currentPos = NULL;
}

template <class ItemType>
void SortedType<ItemType>::MakeEmpty()
{
	NodeType<ItemType>* tempPtr;

	while(listData)// != NULL)
	{
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
}

template <class ItemType>
bool SortedType<ItemType>::IsFull ( )  const
{
	NodeType<ItemType>* location;
	try
	{
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch(bad_alloc exception)
	{
		return true;
	}
}

template <class ItemType>
int SortedType<ItemType>::LengthIs ( )  const
{
	NodeType<ItemType>* location = listData;
    int count = 0;

	while (location)
	{
		count++;
		location = location->next;
	}
	return count;
}

template <class ItemType>
void  SortedType<ItemType>::RetrieveItem( ItemType& item, bool& found )
{
	bool MoreToSearch;
	NodeType<ItemType>* location;
	
	location = listData;
	found = false;
	MoreToSearch = (location != NULL);
	
	
	while(MoreToSearch && !found)
	{
		if(location->info.key < item.key)
		{
			location = location -> next;
			MoreToSearch = (location != NULL);
		}

		else if(item.key == location -> info.key)
		{
			found = true;
			item.key = location -> info.key;
		}
		
		else
			MoreToSearch = false;
	}
}

template <class ItemType> NodeType<ItemType>* SortedType<ItemType>::GetCurPointer()
{
    return currentPos;
}


template <class ItemType>
void  SortedType<ItemType> :: InsertItem ( ItemType  item)
{
   bool  moreToSearch ;
	NodeType<ItemType>*  newNode;
	NodeType<ItemType>*  predLoc = NULL;
	NodeType<ItemType>*  location = listData;
	moreToSearch = ( location  !=  NULL ) ;
	while ( moreToSearch ) 
	{       
		if ( location->info.key < item.key )
		{
			predLoc = location;
			location = location->next;
			moreToSearch = ( location  !=  NULL ) ;
		}
		else
			moreToSearch = false ;
	}
	newNode = new NodeType<ItemType>;
	newNode->info = item;
	if (predLoc == NULL)
	{
		newNode->next = listData;
		listData = newNode;
	}
	else
	{
		newNode->next = location;
		predLoc->next = newNode;
	}

}


template <class ItemType>
void SortedType<ItemType>::DeleteItem ( ItemType item )
{
    NodeType<ItemType>*  location = listData ;
	NodeType<ItemType>*  tempLocation ;

    if (item == listData->info) {
        tempLocation = location;
        listData = listData->next;
    }
    else {
        while (item != location->next->info)    location = location->next;
        tempLocation = location->next;
        location->next = (location->next)->next;
    }

    delete tempLocation;
}

template <class ItemType>
void SortedType<ItemType>::ResetList ( )
{
    currentPos = NULL;
}

template <class ItemType>
void  SortedType<ItemType>::GetNextItem (ItemType& item)
{
	if(currentPos == NULL)
		currentPos = listData;
	else
		currentPos = currentPos -> next;

	item = currentPos -> info;
}

template <class ItemType> SortedType<ItemType>::~SortedType()
{
//    MakeEmpty();
}

#endif