// list.cpp
// sorted link list implementation 
// modified unsorted to call SelSort( ) when insert item

#include "list3.h"

typedef NodeType* NodePtr;

struct NodeType
{
    ItemType info;
    NodePtr  link;
};


ListType ::ListType   ()           // Class constructor
{
    length = 0;
    head = NULL;
}

ListType ::ListType   (const ListType& list)           // Class copy constructor
{
        NodePtr tempPtr;
        NodePtr listPtr;
        length = list.length;
        tempPtr = list.head;
        if (tempPtr != NULL)
        {
                listPtr = new NodeType;
                listPtr->info = tempPtr->info;
                head = listPtr;
                tempPtr = tempPtr->link;
        }
        else
        {
                head = NULL;
                return;
        }
        while (tempPtr != NULL)
        {
                listPtr->link = new NodeType;
                listPtr = listPtr->link;
                listPtr->info = tempPtr->info;
                tempPtr = tempPtr->link;
        }
        listPtr->link = NULL;
}

ListType ::~ListType   ()       // Class destructor
// Post: List is empty; all items have been deallocated.
{
    NodePtr tempPtr;

    while (head != NULL)
    {
        tempPtr = head;
        head = head->link;
        delete tempPtr;
    }
    length = 0;
}

ListType& ListType::operator=(const ListType& other) // Assignment
{
        NodeType*tempPtr, *otherPtr;

        if (this == &other) return *this; //don't copy into self!

        MakeEmpty();
        length = other.length;
        tempPtr = other.head;
        if (tempPtr != NULL)
        {
                otherPtr = new NodeType;
                otherPtr->info = tempPtr->info;
                head = otherPtr;
                tempPtr = tempPtr->link;
        }
        else
                return *this;
        while (tempPtr != NULL)
        {
                otherPtr->link = new NodeType;
                otherPtr = otherPtr->link;
                otherPtr->info = tempPtr->info;
                tempPtr = tempPtr->link;
        }
        otherPtr->link = NULL;
        return *this;
}



bool ListType ::IsEmpty() const
// Returns true if list is Empty;
// false otherwise.
{

    return (head == NULL);
}


int ListType ::Length() const
// Post: Number of items in the list is returned.
{
    return length;
}


void ListType ::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
    NodePtr tempPtr;

    while (head != NULL)
    {
        tempPtr = head;
        head = head->link;
        delete tempPtr;
    }
    length = 0;
}


bool ListType::Insert (const ItemType& item)
{
    NodePtr newNode;  // pointer to node being inserted
    newNode = new NodeType;
    if (newNode != NULL)
    {
        newNode->info = item;
        newNode->link = head;
        head = newNode;
        length++;
    SelSort( );
        return true;
    }
    else
        return false;
    
}


bool ListType ::Delete(const ItemType& item)
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: First occurrence of item is deleted.
{
    NodePtr delNode;  // pointer to node being deleted
    NodePtr predLoc;    // trailing pointer
    NodePtr location; // traveling pointer
    bool moreToSearch;

    location = head;
    delNode = NULL;
    predLoc = NULL;
    moreToSearch = (location != NULL);

    // Find node to delete
    while (moreToSearch)
    {
        if (location->info !=item)
        {
           predLoc = location;
           location = location->link;
           moreToSearch = (location != NULL);
        }
        else if (location->info == item)
        {
            delNode = location;
            moreToSearch = false;
        }
    }

    if (delNode != NULL)
    {
            if (predLoc == NULL)       // delete first
      {
        head = delNode->link;
      }
      else
      {
        predLoc->link = delNode->link;
      }
      length--;
      delete delNode;
      return true;
    }
    else
        return false;

}

bool ListType::Retrieve (ItemType& item) const
{
    bool moreToSearch;
    NodePtr location;

    location = head;
    bool found = false;
    moreToSearch = (location != NULL);

    while (moreToSearch && !found)
    {
        if (location->info !=item)
        {
            location = location->link;
            moreToSearch = (location != NULL);
        }
        else if (item == location->info)
        {
            found = true;
            item = location->info;
        }
    }

        return found;
}



bool ListType::IsPresent (const ItemType& item) const
{
    bool moreToSearch;
    NodePtr location;

    location = head;
    bool found = false;
    moreToSearch = (location != NULL);

    while (moreToSearch && !found)
    {
        if (location->info !=item)
        {
            location = location->link;
            moreToSearch = (location != NULL);
        }
        else if (item == location->info)
        {
            found = true;
        }
    }

        return found;
}



void ListType::SelSort()
{
        ItemType item;
        int passCount;
        int searchIndx;
        int minIndx;
        NodePtr passNode;
        NodePtr minNode;
        NodePtr searchNode;

        
        for ((passNode = head,passCount = 0); 
	         passCount < length-1; 
                (passCount++, passNode = passNode->link))
        {
                minNode = passNode;
                for (searchNode = passNode->link; searchNode!= NULL; searchNode = searchNode->link)
                        if (searchNode->info < minNode->info)
                                minNode= searchNode;
                item = minNode->info;
                minNode->info = passNode->info;
                passNode->info = item;
        }
}



void ListType::Print( ) const
{
    NodePtr tempPtr= head;

    while (tempPtr != NULL)
    {
                cout<<tempPtr->info<<endl;
        tempPtr = tempPtr->link;
    }

}


void ListType:: ResetList()
{
    currentPos = head;
}


void ListType ::GetNextItem(ItemType& item)
{
    if (currentPos != NULL)
    {    item = currentPos->info;
         currentPos = currentPos->link;
    }
    if (currentPos == NULL)
        currentPos = head;

}