//******************************************************************
// IMPLEMENTATION FILE (SortedList.cpp)
// This file implements the SortedList class member functions
// SortedList representation: a one-dimensional array and a length
// variable
// To save space, we omit from each function the precondition 
// comments that document the assumptions made about valid input 
// parameter data. These would be included in a program intended 
// for actual use.                                                                          
//******************************************************************
#include "SortedList.h"
#include <iostream>

using namespace std;

// Private members of class:
//    int      length;           Length of the SortedList
//    ItemType data[MAX_LENGTH]; Array holding the SortedList items
//    int      currentPos;     Position of next item to be accessed
//    void     BinSearch( ItemType, bool&, int& ) const;   Helper
//                                                         function

//******************************************************************

SortedList::SortedList()

// Constructor

// Postcondition:
//     length == 0

{
    length = 0;
}

//******************************************************************

bool SortedList::IsEmpty() const

// Reports whether SortedList is empty

// Postcondition:
//     Return value == true, if length == 0
//                    == false, otherwise

{
    return (length == 0);
}

//******************************************************************

bool SortedList::IsFull() const

// Reports whether SortedList is full

// Postcondition:
//     Return value == true, if length == MAX_LENGTH
//                  == false, otherwise

{
    return (length == MAX_LENGTH);
}

//******************************************************************

int SortedList::Length() const

// Returns current length of SortedList

// Postcondition:
//     Return value == length

{
    return length;
}

//******************************************************************

void SortedList::Insert( /* in */ ItemType& item )
 
// Inserts item into the SortedList
 
// Precondition:
//     length < MAX_LENGTH
//  && data[0..lengthÐ1] are in ascending order
// Postcondition:
//     item is in the SortedList
//  && length == length@entry + 1
//  && data[0..lengthÐ1] are in ascending order
 
{
    int index;    // Index and loop control variable
    index = length - 1;
    while (index >= 0 && item < (data[index]))
    {
        data[index+1] = data[index];
        index--;
    }
    data[index+1] = item;          // Insert item
    length++;
}

//******************************************************************

void SortedList::Reset()

// Postcondition:
//     Iteration is initialized

{
    currentPos = 0;
}
            
//******************************************************************
         
ItemType SortedList::GetNextItem()

// Precondition:
//     Iteration has been initialized by call to Reset;
//     No transformers have been invoked since last call
// Postcondition:
//     Returns item at the current position in the SortedList and
//     resets current to next position or first position if
//     last item is returned

{
     ItemType item;
     item = data[currentPos];
     if (currentPos == length - 1)
         currentPos = 0;
     else
         currentPos++;
     return item;    
  }     
              
//******************************************************************

void SortedList::BinSearch(
      /* in */  ItemType item,              // Item to be found
      /* out */ bool&    found,             // True if item is found
      /* out */ int&     position ) const   // Location if found

// Searches list for item, returning the indexof item if item was found.

// Precondition:
//     length <= INT_MAX / 2
//  && data[0..length-1] are in ascending order
// Postcondition:
//     IF item is in the list
//         found == true  &&  data[position] contains item
//     ELSE
//         found == false  &&  position is undefined

{
    int first = 0;            // Lower bound on list
    int last = length - 1;    // Upper bound on list
    int middle;               // Middle index

    found = false;
    while (last >= first && !found)
    {
        middle = (first + last) / 2;
        if (item < (data[middle]))
            // Assert: item is not in data[middle..last]
            last = middle - 1;
        else if (data[middle] < (item))
            // Assert: item is not in data[first..middle]
            first = middle + 1;
        else
            // Assert: item == data[middle]
            found = true;
    }
    if (found)
        position = middle;
}

//******************************************************************

void SortedList::Delete( /* in */ ItemType item )

// Deletes item from the list, if it is there

// Precondition:
//     0 < length <= INT_MAX/2
//  && data[0..length-1] are in ascending order
// Postcondition:
//     IF item is in data array at entry
//           First occurrence of item is no longer in array
//        && length == length@entry - 1
//        && data[0..length-1] are in ascending order
//     ELSE
//           length and data array are unchanged

{
    bool found;      // True if item is found
    int position;    // Position of item, if found
    int index;       // Index and loop control variable

    BinSearch(item, found, position);
    if (found)
    {
        // Shift data[position..length-1] up one position

        for (index = position; index < length - 1; index++)
            data[index] = data[index+1];
        length--;
    }
}

//******************************************************************

bool SortedList::IsPresent( /* in */ ItemType item ) const

// Searches the list for item, reporting whether it was found

// Precondition:
//     length <= INT_MAX / 2
//  && data[0..length-1] are in ascending order
//  && item is assigned
// Postcondition:
//     Return value == true, if item is in data[0..length-1]
//                  == false, otherwise

{
    bool found;      // True if item is found
    int position;    // Required (but unused) argument for
                     //   the call to BinSearch

    BinSearch(item, found, position);
    return found;
}