SortedLinkedList.cpp - VTC C++ Sorted Linked List

/**
 * [SortedLinkedList.cpp]
 * The SortedLinkedList class definition/implementation.
 */

#include "SortedLinkedList.h"


/**
 * SortedLinkedList CLASS CONSTRUCTOR(s):
 */
SortedLinkedList::SortedLinkedList()
{
    length = 0;
    data = 0;
}


/**
 * SortedLinkedList CLASS ACCESSORS:
 */
float SortedLinkedList::GetNextItem(void)
{
        if(currentPos == 0)     // if the current position is null...
            currentPos = data;  // ...the next item will be the head
        else
            currentPos = currentPos->next; // move to the next item after the current position

    return currentPos->element;
}


/**
 * SortedLinkedList CLASS MUTATORS:
 */
void SortedLinkedList::InsertItem(float item)
{
    /**
     * NOTE:
     * The idea in inserting an item into a sorted linked list, is to, first, find the location where
     * the item is to be added, through finding the one before and the one after it, then insert the
     * item in between them, if the location is in the middle.
     *
     * If the location is at the end, the item will be inserted between an item and null.  If the
     * location is at the beginning, the item will be inserted between null and an item.  If the list
     * is empty, a new item will be created in the list.
     *
     * To achieve this, the list must be traversed, keeping track of the predecessor and successor
     * of the position where the item is to be deleted, and then add the item.
     */
    Node    *newNode;   // holds the item to be added
    Node    *predLoc;   // the predecessor of the item to be added
    Node    *location;  // used to traverse the list to find the location where the item will be added

    location = data;    // points to the head (the beginning of the list)
    predLoc = 0;        // the predecessor of the head of the list is null

        /**
         * While the location is not null (the end of the list is not reached), and the element part
         * of the location is still smaller than the item to be added...
         */
        while(location != 0 && location->element < item)
        {
            predLoc = location;         // ...more the predecessor location to the current location
            location = location->next;  // ...move the location to point the next item
        }

    newNode = new Node();               // allocate memory for the node that will hold the item to be inserted...
    newNode->element = item;            // ...add the item to be added to the element part of the node

        if(predLoc == 0)        // if the list is empty (the item is being added to the head of the list)
        {
            newNode->next = data;       // the new node points to data (the head)
            data = newNode;             // data becomes the new node
        }
        else                    // if the list is not empty
        {
            newNode->next = location;   // the new node points to the successor of the item to be added
            predLoc->next = newNode;    // the next part of the predecessor location points to the new node (containing the item to be added)
        }

    length++;                           // increment the length of the list to reflect the new addition of the item
}

void SortedLinkedList::DeleteItem(float item)
{
    /**
     * NOTE:
     *
     * Method for deleting an item:
     * i. Find the item to be deleted.
     * ii. Keep the item in a temporary pointer.
     * iii. Link the item before it to the item after it.
     * iv. It this point the item can/will be deleted.
     *
     * The point here is not to lose the linkage between items if one is being deleted.  Therefore,
     * there must be implementations to make sure the list is still linked.
     *
     * To achieve this goal, two pointers will be needed; one to keep a temporary item, and the other
     * will facilitate going through the list.
     */

    Node    *location;

        /**
         * NOTE:
         * The item to be deleted might exist in the list as duplicates.  In such a case, the list
         * should be recursed until all duplicates of the provided item are deleted.
         */
        for(int i = 0; i < length; i++) //fix
        {
            Node    *pTemp;     // will hold the temporary item

            location = data;    // points to the beginning/head of the list

                /**
                 * In the event of deleting an item from a an sorted linked list, one of two
                 * scenarios will exist:
                 *
                 * If the item to be deleted is at the head of the list, the head can simply be moved
                 * to the item after that one, then it will be safe to get rid of the node.
                 */
                if(item == data->element || length == 1)
                {
                    pTemp = location;

                        /**
                         * NOTE:
                         * If the list contains only one item, it will simply be set to null (0), or
                         * setting it to the next item would be impossible, hence crashing the program.
                         */
                        (length == 1) ? data = 0 : data = data->next;

                    length--;       //fix
                }
                /**
                 * If the item to be deleted is not at the head of the list:
                 */
                else
                {
                        /**
                         * While going through the list, the code must keep track of the item before
                         * the one to be deleted.  Also, the end of the list must not be passed.
                         */
                        while(!(item == (location->next)->element) && (location->next)->next != 0)  // location will always store the item before the one to be deleted
                        {
                            location = location->next;  // move location to the one next to it until it is found
                        }

                        /**
                         * NOTE:
                         * If the item to be deleted is actually found, the following block of code
                         * will be executed.
                         *
                         * The condition is used to safeguard against an attempt to delete a provided
                         * item that is not on the list.
                         */
                        if(location->next->element == item)
                        {
                            pTemp = location->next; // store the item to be deleted in the temporary pointer

                            length--; // decrement the list length to reflect the item deletion

                            location->next = (location->next)->next; // link the item before the one to be deleted to the one after it
                        }
                }

            delete pTemp; // delete the item/unused pointer in either case
        }
}


/**
 * SortedLinkedList CLASS GENERAL USE FUNCTIONS:
 */
bool SortedLinkedList::IsEmpty(void)
{
    if(length == 0)
        return true;
    else
        return false;
}

bool SortedLinkedList::IsFull(void)
{
    Node    *pNode = new Node();    // attempts to allocate memory for another element

        if(pNode == 0)              // if the memory allocation attempt failed...
            return true;            // ...the list is full
        else
        {
            delete pNode;

            return false;
        }
}

void SortedLinkedList::ResetList(void)
{
    currentPos = 0;
}

void SortedLinkedList::MakeEmpty(void)
{
    Node    *pTempNode = new Node();    // allocates memory for a temporary node

        while(data != 0)
        {
            pTempNode = data;           // stores an element of the list in the temporary pointer

            data = data->next;          // points to the next item in the list (move to the next one)

            delete pTempNode;           // delete the temporary pointer
        }

    length = 0;                         // sets the length of the list to 0, reflecting its items deletion
}

int SortedLinkedList::LengthIs(void)
{
    return length;
}

bool SortedLinkedList::IsInTheList(float item)
{
    Node    *location = new Node();     // the current location in the list

    location = data;                    // starting from the beginning of the list


     bool   found = false;

        while(location != 0 && !found)
        {
            /**
             * NOTE:
             * Location is a node, that has the element, which is the value being added...
             */
            if(item == location->element)
                found = true;
            else
                /**
                 * ...it also contains a pointer to the next node, through the next variable.
                 */
                location = location->next;  // move to the next item if the item is not found
        }

    return found;
}

void SortedLinkedList::Print(void)
{
    Node    *location = new Node();

    location = data;    // points to the head

        while(location != 0)    // while the end of the list is not reached
        {
            std::cout << location->element << std::endl; // ...print the element part of each node

            location = location->next;  // ...move to the next item
        }
}