I have this header file and I need the implementation for several functions: ret

Question

I have this header file and I need the implementation for several functions: retrieve, merge and isSubset. Thank you.

class OrderedList : public List<DataType>

{

public:

static const int DEFAULT_MAX_LIST_SIZE = 10;

// Constructor

OrderedList ( int maxNumber = DEFAULT_MAX_LIST_SIZE );

// Modified (or new) list manipulation operations

virtual void insert ( const DataType &newDataItem ) throw ( logic_error );

virtual void replace ( const DataType &newDataItem ) throw ( logic_error );

bool retrieve ( const KeyType& searchKey, DataType &searchDataItem );

// Output the list structure -- used in testing/debugging

void showStructure () const;

// In-lab operations

void merge ( const OrderedList<DataType,KeyType> &other ) throw ( logic_error );

bool isSubset ( const OrderedList<DataType,KeyType> &other );

// Inheritance using templates is somewhat ugly in C++. It feels like you

// should be able to access base class member functions and data without the

// scope resolution operator. Sadly, you cannot when using templates.

// See http://www.parashift.com/c++-faq-lite/templates.html#faq-35.19

// Tell compiler to use these base class methods.

using List<DataType>::remove;

using List<DataType>::clear;

using List<DataType>::isEmpty;

using List<DataType>::isFull;

using List<DataType>::gotoBeginning;

using List<DataType>::gotoEnd;

using List<DataType>::gotoNext;

using List<DataType>::gotoPrior;

private:

// Locates an element (or where it should be) based on its key

bool binarySearch ( KeyType searchKey, int &index );

{

// Tell compiler to use these base class data members

using List<DataType>::maxSize;

using List<DataType>::cursor;

using List<DataType>::size;

using List<DataType>::dataItems;

};

Explanation / Answer

//--------------------------------------------------------------------
//                                         ordlist.cpp
//
// Array implementation of the Ordered List ADT
//
//--------------------------------------------------------------------

#ifndef ORDEREDLIST_CPP
#define ORDEREDLIST_CPP

using namespace std;

#include "OrderedList.h"

//--------------------------------------------------------------------
template < typename DataType, typename KeyType >
OrderedList<DataType,KeyType>:: OrderedList ( int maxNumber )

// Creates an empty list by calling the List ADT constructor.
   :List(maxNumber)
{

}

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

template < typename DataType, typename KeyType >
void OrderedList<DataType,KeyType>:: insert ( const DataType &newDataItem ) throw ( logic_error )

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

{
   if (isFull())
   {
       throw logic_error("The list is full");
   }
   if (binarySearch(newDataItem.getKey(), cursor))
   {
       dataItems[cursor] = newDataItem;
   }
   else
   {
       List<DataType>::insert(newDataItem);
   }
}

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

template < typename DataType, typename KeyType >
bool OrderedList<DataType,KeyType>:: retrieve ( const KeyType& searchKey, DataType &searchDataItem )

// Searches a list for the data item with key searchKey. If the
// data item is found, then moves the cursor to the data item,
// copies the data item to searchDataItem, and returns true.
// Otherwise, returns false without moving the cursor and with
// searchDataItems undefined.

{
   if (binarySearch(searchKey, cursor) == true)
   {
       searchDataItem = dataItems[cursor];
       return true;
   }
   else
   {
       return false;
   }
}

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

template < typename DataType, typename KeyType >
void OrderedList<DataType,KeyType>:: replace ( const DataType &newDataItem )
    throw ( logic_error )

// Replaces the data item marked by the cursor with newData and
// moves the cursor to newData.

{
   if (isEmpty())
   {
       throw logic_error("List is empty");
   }
   if (binarySearch(newDataItem.getKey(), cursor) == true)
   {
       dataItems[cursor] = newDataItem;
   }
}

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

template < typename DataType, typename KeyType >
void OrderedList<DataType,KeyType>:: showStructure () const

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

{
   if (size == 0)
       cout << "Empty list" << endl;
   else
   {
       cout << "size = " << size
           << "   cursor = " << cursor << endl;
       for (int j = 0; j < maxSize; ++j)
           cout << j << " ";
       cout << endl;
       for (int j = 0; j < size; ++j) {
           if (j == cursor) {
               cout << "[" << dataItems[j].getKey() << "] ";
           }
           else {
               cout << dataItems[j].getKey() << " ";
           }
       }
       cout << endl;
   }
}

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

template < typename DataType, typename KeyType >
bool OrderedList<DataType,KeyType>:: binarySearch ( KeyType searchKey, int &index )

// Binary search routine. Searches a list for the data item with
// key searchKey. If the data item is found, then returns true with
// index returning the array index of the entry containing searchKey.
// Otherwise, returns false 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
   bool result;            // Result returned

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

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

   return result;
}

template < typename DataType, typename KeyType >
void OrderedList<DataType,KeyType>:: merge ( const OrderedList<DataType,KeyType>& fromL ) throw ( logic_error )

// Merges the data items in list fromL into a list. Assumes that
// none of the data items in fromL occur in L already. The merge
// is done in a single pass through both lists.

{
  
   for (int i = 0; i < fromL.size; i++)
   {
       insert(fromL.dataItems[i]);
   }
}

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

template < typename DataType, typename KeyType >
bool OrderedList<DataType,KeyType>:: isSubset ( const OrderedList<DataType,KeyType> &subList )

// Returns true if every key in list subList also occurs in a list --
// that is, if the keys in subList are a subset of the keys in the list.
// Otherwise, returns false.

{

   int temp;
   for (int i = 0; i < subList.size; i++)
   {
       if (!binarySearch(subList.dataItems[i].getKey(), temp))
       {
           return false;
       }
   }
   return true;
}

#endif // #IFNDEF ORDEREDLIST_CPP

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects