SortedList.cpp - VTC C++ Data Structures Sorted List

/**
 * [SortedList.cpp]
 * The SortedList class definition/implementation.
 *
 * The sorted list is similar to the Sorted one.  The only difference is, the sorted one is in
 * order.
 */

#include "SortedList.h"

/**
 * SortedList CLASS CONSTRUCTOR(s):
 */
SortedList::SortedList()
{
    length = 0;
    currentPos = -1;
}


/**
 * SortedList CLASS ACCESSORS:
 */
float SortedList::GetNextItem()
{
    currentPos++;

    return data[currentPos];
}

float SortedList::GetPrevItem()
{
    currentPos--;

    return data[currentPos];
}

float SortedList::RetrieveItem(int position)
{
    return data[position];
}


/**
 * SortedList CLASS MUTATORS:
 */
void SortedList::InsertItem(float item)
{
    int location = 0;

        /**
         * While location is smaller than length (before the end of the list is reached), and the
         * the item in the current location is smaller than the item being inserted...
         */
        while(location < length && data[location] < item)
            location++; // ...keep incrementing the location by 1

        /**
         * After the location is found, start shifting all the items, after it, to the right.
         *
         * Starting at the end of the list, while the index is greater than the location (because
         * it's the items after that location that are being shifted), decrement the index.
         */
        for(int index = length; index > location; index--)
            data[index] = data[index - 1]; // move each item in the list one place to the right

    data[location] = item; // insert the item at the assigned location
    length++; // increase the length of the list to reflect the insertion
}

void SortedList::DeleteItem(float item)
{
    /**
     * Starting from the beginning (visiting all items on the list), while the index is smaller than
     * the length of the list, increment the index.
     */
    for(int index = 0; index < length; index++)
        /**
         * If the item being deleted is equal to the item at the current index...
         */
        if(item == data[index])
        {
                /**
                 * ...using a sub-index (starting at the current index (the item being deleted)),
                 * while the sub-index is less than the length of the list, increment the sub-index.
                 */
                for(int subIndex = index; subIndex < length; subIndex++)
                {
                    /**
                     * Shift all of the items (after the current item being deleted), one place to
                     * the left (replacing the item being deleted).
                     */
                    data[subIndex] = data[subIndex + 1];

                    /**
                     * Decrement the index to accordingly, to point to the same item as it was,
                     * before the item was deleted (while the sub-for loop is still recursing).
                     * (The index, in this case, is analogous with a stack pointer.)
                     *
                     * NOTE:
                     * This decrement is detrimental where the same values occur more than once in
                     * the list.
                     */
                    index--;
                }

            length--; // decrease the length of the list to reflect the deletion
        }
}


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

bool SortedList::IsFull()
{
    if(length == MAX_LENGTH_Sorted_List)
        return true;
    else
        return false;
}

void SortedList::ResetList()
{
    currentPos = -1;
}

int SortedList::LengthIs()
{
    return length;
}

bool SortedList::IsInTheList(float item)
{
    for(int i = 0; i < length; i++)
        if(data[i] == item)
            return true;
        else
            return false;
}

void SortedList::Print()
{
    for(int i = 0; i < length; i++)
        std::cout << "Item " << i << ": " << data[i] << std::endl;
}