//--------------------------------------------------------------------
//
//  Laboratory 9                                         listord.cpp
//
//  Array implementation of the Ordered List ADT
//
//--------------------------------------------------------------------

#include <assert.h>
#include "listord.h"

//--------------------------------------------------------------------

template < class LE, class KF >
OrdList<LE,KF>:: OrdList ( int maxNumber = defMaxListSize )

// Creates an empty list by calling the List ADT constructor.

  : List<LE>(maxNumber)

{}

//--------------------------------------------------------------------

template < class LE, class KF >
void OrdList<LE,KF>:: insert ( const LE &newElement )

// Inserts newElement in its appropriate location within an ordered
// list. If an element with the same key as newElement already exists
// in the list, then updates that element's data with newElement's
// data. Moves the cursor to newElement.

{
    int j;    // Loop counter

    assert ( size < maxSize );    // Requires that list is not full

    if ( binarySearch(newElement.key(),cursor) )
       element[cursor] = newElement;              // Update
    else
    {                                             // Insert
       for ( j = size-1 ; j > cursor ; j-- )
           element[j+1] = element[j];
       element[++cursor] = newElement;
       size++;
    }
}

//--------------------------------------------------------------------

template < class LE, class KF >
int OrdList<LE,KF>:: retrieve ( KF searchKey, LE &searchElement )

// Searches a list for the element with key searchKey. If the
// element is found, then moves the cursor to the element, copies the
// element to searchElement, and returns 1. Otherwise, returns 0
// without moving the cursor and with searchElement undefined.

{
    int holdCursor = cursor,  // Stores the cursor index in case the
                              //   element is not found
        result;               // Result returned

    if ( binarySearch(searchKey,cursor) )
    {
       searchElement = element[cursor];
       result = 1;
    }
    else
    {
       cursor = holdCursor;
       result = 0;
    }

    return result;
}

//--------------------------------------------------------------------

template < class LE, class KF >
void OrdList<LE,KF>:: replace ( const LE &newElement )

// Replaces the element marked by the cursor with newElement and moves
// the cursor to newElement.

{
    assert ( size != 0 );       // Requires that the list is not empty

    if ( newElement.key() == element[cursor].key() )
       element[cursor] = newElement;
    else
    {
       remove();
       insert(newElement);
    }
}

//--------------------------------------------------------------------

template < class LE, class KF >
void OrdList<LE,KF>:: showStructure () const

// Outputs the keys of the elements in a list. If the list is empty,
// outputs "Empty list". This operation is intended for testing and
// debugging purposes only.

{
    int j;   // Loop counter

    if ( size == 0 )
       cout << "Empty list" << endl;
    else
    {
       cout << "size = " << size
            <<  "   cursor = " << cursor << endl;
       for ( j = 0 ; j < maxSize ; j++ )
           cout << j << "\t";
       cout << endl;
       for ( j = 0 ; j < size ; j++ )
           cout << element[j].key() << "\t";
       cout << endl;
    }
}

//--------------------------------------------------------------------
//
//  Facilitator function
//

template < class LE, class KF >
int OrdList<LE,KF>:: binarySearch ( KF searchKey, int &index )

// Binary search routine. Searches a list for the element with key
// searchKey. If the element is found, then returns 1 with index
// returning the array index of the entry containing searchKey.
// Otherwise, returns 0 with index returning the array index of the
// entry containing the largest key that is smaller than searchKey
// (or -1 if there is no such key).

{
    int low  = 0,           // Low index of current search range
        high = size - 1,    // High index of current search range
        result;             // Result returned

    while ( low <= high )
    {
        index = ( low + high ) / 2;               // Compute midpoint
        if ( searchKey < element[index].key() )
           high = index - 1;                      // Search lower half
        else if ( searchKey > element[index].key() )
           low = index + 1;                       // Search upper half
        else
           break;                                 // searchKey found
    }

    if ( low <= high )
       result = 1;       // searchKey found
    else
    {
       index = high;     // searchKey not found, adjust index
       result = 0;
    }

    return result;
}