<![CDATA[//******************************************************************
// IMPLEMENTATION FILE (slist.cpp)
// This file implements the SortedList class member functions
// List representation: a one-dimensional array and a length
// variable
//******************************************************************
#include "slist.h"
#include <iostream>
using namespace std;
// Private members of class:
// int length; Length of the list
// ItemType data[MAX_LENGTH]; Array holding the list
// void BinSearch( ItemType, bool&, int& ) const; Helper
// function
//******************************************************************
SortedList::SortedList()
// Constructor
// Postcondition:
// length == 0
{
length = 0;
}
//******************************************************************
bool SortedList::IsEmpty() const
// Reports whether list is empty
// Postcondition:
// Function value == true, if length == 0
// == false, otherwise
{
return (length == 0);
}
//******************************************************************
bool SortedList::IsFull() const
// Reports whether list is full
// Postcondition:
// Function value == true, if length == MAX_LENGTH
// == false, otherwise
{
return (length == MAX_LENGTH);
}
//******************************************************************
int SortedList::Length() const
// Returns current length of list
// Postcondition:
// Function value == length
{
return length;
}
//******************************************************************
void SortedList::Insert( /* in */ ItemType item )
// Inserts item into the list
// Precondition:
// length < MAX_LENGTH
// && data[0..length-1] are in ascending order
// && item is assigned
// Postcondition:
// item is in the list
// && 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::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 index
// of item if item was found.
// Precondition:
// length <= INT_MAX / 2
// && data[0..length-1] are in ascending order
// && item is assigned
// 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 (item > data[middle])
// 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
// && item is assigned
// 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:
// Function 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;
}
//******************************************************************
void SortedList::Print() const
// Prints the list
// Postcondition:
// Contents of data[0..length-1] have been output
{
int index; // Loop control and index variable
for (index = 0; index < length; index++)
cout << data[index] << endl;
}
]]>