PROBLEM DESCRIPTION: This assignment calls for an implementation file for the SortedList class . The implementation will use a dummy-headed circular singly-linked list using dynamically allocated nodes to store the list items. For your code to be considered correct, it must provide to any client program the services contracted by the SortedList class specification. The specification for this SortedList is given formally in the DLL.h header

Several member functions (or methods) in DLL.cpp are incomplete; you must supply code to complete them. Be sure to

-Use deep copy semantics in your copyList() implementation

-Properly implement the private method locateNode()

-Use the private method locateNode() appropriately in implementing your Insert()

-Use the private method locateNode() appropriately in implementing your Remove()

DLL.cpp

#include using namespace std; #include "DLL.h" // Constructors and Destructor: SortedList::SortedList() : size(0) { head = new tNode; head->next = head; } // end Constructor SortedList::SortedList(const SortedList& sList) { size = sList.size; copyList(sList.head, head); } // end Copy Constructor SortedList::~SortedList() { // *** ... substitute your code for this comment ... *** } // end Destructor // Overloaded Operator: SortedList& SortedList::operator=(const SortedList& sList) { tNodePtr future, cur; // Is there any work to be done? Check if target same as sList. if ( this != &sList ) { // Deallocate anything the assignment target might have allocated. // *** ... substitute your code for this comment ... *** // Now "copy" the object size = sList.size; copyList(sList.head, head); } return *this; } // end operator= // List Operations: bool SortedList::IsEmpty() const { return (size == 0); } // end IsEmpty int SortedList::Length() const { return size; } // end Length // *** ... place Insert and Remove code here ... *** int SortedList::Find(ItemType anItem) const // IN { tNodePtr prev; // Pointer to predecessor of found node int position; // Item's list position bool isPresent = locateNode(anItem, prev, position); return (isPresent) ? position : -1; } // end Find // *** ... place Retrieve code here ... *** // Private functions: void SortedList::copyList(const tNodePtr& original, tNodePtr& duplicate) // IN OUT { // *** ... substitute your code for this comment ... *** } // end copyList bool SortedList::locateNode (ItemType anItem, tNodePtr& previous, int& position) const // IN OUT OUT { // *** ... substitute your code for this comment ... *** } // end locateNode // End of implementation file. 

DLL.h

#ifndef DLL_h_ // To prevent problems from multiple inclusions #define DLL_h_ typedef int ItemType; // data type of list items class SortedList { public: // Constructors and Destructor: SortedList(); // (default) constructor SortedList(const SortedList& sList); // copy constructor ~SortedList(); // destructor // Overloaded Operator: SortedList& operator=(const SortedList& sList); // assignment // List Operations: bool IsEmpty() const; // Determines whether a sorted list is empty. // Pre: None. // Post: Returns true if list is empty, otherwise returns false. int Length() const; // Returns the number of items that are in a sorted list. // Pre: None. // Post: Returns the number of items currently on the list. void Insert(ItemType newItem, bool& success); // IN OUT // Inserts newItem into its proper sorted position in a sorted // list. Duplicates are not allowed and attempts to insert // duplicates should be unsuccessful. The success flag indicates // whether the insertion was successful. // Pre: newItem is defined. // Post: If insertion is successful, newItem is in its proper // sorted position in the list and success is true; otherwise // success is false. void Remove(ItemType anItem, bool& success); // IN OUT // Deletes anItem from a sorted list. The success flag indicates // whether the deletion was successful. // Pre: anItem is defined. // Post: If anItem was in the sorted list, it is removed and // success is true; otherwise success is false. int Find(ItemType anItem) const; // IN // Returns the position (in the range 1<= position<= Length()) where // anItem exists in a sorted list or -1 if anItem is not in the list. // Pre: anItem is defined. // Post: Returns the position in the sorted list where anItem resides // or -1 if anItem is not in the sorted list. // The item anItem and the list are unchanged. void Retrieve(int position, ItemType& dataItem, bool& success) const; // IN OUT OUT // Sets dataItem to the item at "position" of the sorted list. // The success flag indicates whether the retrieval was successful. // Pre: position is defined and is the number of the item to be retrieved. // Post: If 1 <= position <= Length(), then dataItem is the value // of the desired item and success is true; otherwise success is // false. The list is left unchanged by this operation. private: struct tNode; typedef tNode* tNodePtr; // pointer to list node struct tNode { ItemType item; tNodePtr next; }; void copyList(const tNodePtr& original, tNodePtr& duplicate); // IN OUT // Make a deep copy of a list. // Pre: original points to an existing list. // Post: duplicate points to a duplicate copy of the "original" list. bool locateNode(ItemType anItem, tNodePtr& previous, int& position) const; // IN OUT OUT // Returns true if anItem exists in the list, a pointer to the previous // (i.e., predecessor) node in the list and and anItem's list position. // Returns false if anItem is not in the list and a pointer to what would // have been the previous node if anItem had been in the list; the value // of position is that of what anItem's would have been if it were in the // list. // Pre: anItem is defined. // Post: See above. Note that the value of position lies in the range // 1 <= position <= Length()+1. The pointer "previous" points to // the last node on the list whose value was less than that of // anItem or to the dummy node if the position==1. int size; // number of items on list. tNodePtr head; // pointer to the dummy node of the // dummy headed circular singly-linked list. }; // end SortedList class #endif 

SLC.cpp

#include "SLC.h"

// Constructors and Destructor:

SortedList::SortedList() : size(0)

{

} // end (default) constructor

SortedList::SortedList(const SortedList& aList): size(aList.size)

// IN

{

// NOTE: The array implementation of SortedList does not require

// a user-defined copy constructor, but the system-supplied copy

// constructor would not be as efficient.

for (int pos = 1; pos <= aList.size; pos++)

list[pos-1] = aList.list[pos-1];

} // end copy constructor

SortedList::~SortedList()

{

// NOTE: This is just "placeholder" code. The array implementation

// of SortedList does not really need a destructor.

} // end destructor

// List Operations:

bool SortedList::IsEmpty() const

{

return (size == 0);

} // end IsEmpty

int SortedList::Length() const

{

return size;

} // end Length

void SortedList::Insert(ItemType newItem, bool& success)

// IN OUT

{

bool isPresent;

int desiredPosition = locatePosition(newItem, isPresent);

if (isPresent || size>=MAX_LIST)

success = false;

else

{

// Make room for new item by shifting all items at

// positions >= desiredPosition toward the end of the

// list (no shift if desiredPosition == size+1)

for (int pos = size; pos >= desiredPosition; pos--)

list[pos] = list[pos-1];

// Insert new item.

list[desiredPosition-1] = newItem;

size++;

success = true;

}

} // end Insert

void SortedList::Remove(ItemType anItem, bool& success)

// IN OUT

{

int lastPosition = Length();

int deletePosition = locatePosition(anItem, success);

if (success)

{

// Delete item by shifting all items at

// positions > deletePosition toward the beginning of the list.

// (No shift if deletePosition == lastPosition.)

for (int pos = deletePosition+1; pos <= lastPosition; pos++)

list[pos-2] = list[pos-1];

size--;

}

} // end Remove

int SortedList::Find(ItemType anItem) const

// IN

{

bool isPresent;

int position = locatePosition(anItem, isPresent);

return (isPresent) ? position : -1;

} // end Find

void SortedList::Retrieve(

int position, ItemType& dataItem, bool& success) const

// IN OUT OUT

{

success = position>=1 && position<=Length();

if (success)

dataItem = list[position-1];

} // end Retrieve

int SortedList::locatePosition(ItemType anItem, bool& isPresent) const

// IN OUT

{

int position; // position index

isPresent = false;

for (position = 1; position <= size; position++)

{

if (list[position-1] >= anItem)

{

if (list[position-1] == anItem)

isPresent = true;

break;

}

}

return position;

} // end locatePosition

// End of implementation file.

SLC.h

#ifndef SLC_h_ // To prevent problems from multiple inclusions #define SLC_h_ typedef int ItemType; // data type of list items class SortedList { public: // Constructors and Destructor: SortedList(); // (default) constructor SortedList(const SortedList& sList); // copy constructor ~SortedList(); // destructor // List Operations: bool IsEmpty() const; // Determines whether a sorted list is empty. // Pre: None. // Post: Returns true if list is empty, otherwise returns false. int Length() const; // Returns the number of items that are in a sorted list. // Pre: None. // Post: Returns the number of items currently on the list. void Insert(ItemType newItem, bool& success); // IN OUT // Inserts newItem into its proper sorted position in a sorted // list. Duplicates are not allowed and attempts to insert // duplicates should be unsuccessful. The success flag indicates // whether the insertion was successful. // Pre: newItem is defined. // Post: If insertion is successful, newItem is in its proper // sorted position in the list and success is true; otherwise // success is false. void Remove(ItemType anItem, bool& success); // IN OUT // Deletes anItem from a sorted list. The success flag indicates // whether the deletion was successful. // Pre: anItem is defined. // Post: If anItem was in the sorted list, it is removed and // success is true; otherwise success is false. int Find(ItemType anItem) const; // IN // Returns the position (in the range 1<= position<= Length()) where // anItem exists in a sorted list or -1 if anItem is not in the list. // Pre: anItem is defined. // Post: Returns the position in the sorted list where anItem resides // or -1 if anItem is not in the sorted list. // The item anItem and the list are unchanged. void Retrieve(int position, ItemType& dataItem, bool& success) const; // IN OUT OUT // Sets dataItem to the item at "position" of the sorted list. // The success flag indicates whether the retrieval was successful. // Pre: position is defined and is the number of the item to be retrieved. // Post: If 1 <= position <= Length(), then dataItem is the value // of the desired item and success is true; otherwise success is // false. The list is left unchanged by this operation. private: const static int MAX_LIST = 20; // maximum length of list ItemType list[MAX_LIST]; // array of list items int size; // number of items on list int locatePosition(ItemType anItem, bool& isPresent) const; // IN OUT // Returns the position where anItem belongs or exists in a sorted // list. The isPresent flag indicates whether anItem is currently // in the list. // Pre: anItem is defined. // Post: Returns the position in the sorted list where anItem resides // or, if anItem is not in the sorted list, where it would be if // inserted into the list; the position lies in the range // 1 <= position <= Length()+1. If anItem exists // in the list, isPresent is true; otherwise isPresent is false. // The item anItem and the list are unchanged. }; // end SortedList class #endif 

SortedListTester.cpp

#include

using namespace std;

#define MAXLOOP 50 // Maximum loop iterations terminator

#if defined DLL

#include "DLL.h" // Dynamic dummy-headed circular linked list

#define OLA "olaDLL"

#elif defined ALL

#include "ALL.h" // Array storage dummy-headed linked list

#define OLA "olaALL"

#elif defined SLC

#include "SLC.h" // Simple array-based sorted list

#define OLA "olaSLC"

#else // Default to "SLC":

#include "SLC.h" // Simple array-based sorted list

#define OLA "olaSLC"

#endif

void DisplayList(SortedList List);

int main()

{

SortedList L, LL, LLL;

ItemType dataItem;

bool success;

int position;

cerr << endl << "Starting " << OLA << " testing:" << endl;

// Assign empty list L to empty list LL, thereby checking assignment

// and "deep copy" semantics; this assignment does not appear in

// the publicly-available SortedListClient.cc code

LL = L;

// Check initial status of list L.

if ( L.IsEmpty() )

cerr << "OKAY: List is initially empty." << endl;

else

cerr << "ERROR: IsEmpty() returning bad value." << endl;

// See what happens when you try to insert one item.

dataItem = 50;

L.Insert(dataItem, success);

if (success)

cerr << "OKAY: Insert operation (seemingly) succeeded." << endl;

else

cerr << "ERROR: Insert operation failed." << endl;

if ( L.IsEmpty() )

cerr << "ERROR: IsEmpty() returning bad value." << endl;

else

cerr << "OKAY: List is not empty anymore." << endl;

cerr << "Length of list = " << L.Length() << endl;

// See what happens when you try ...

// ...these extra instructor-supplied tests for grading

// Check initial status of list LL.

if ( LL.IsEmpty() )

cerr << "OKAY: List LL is initially empty." << endl;

else

cerr << "ERROR: LL.IsEmpty() returning bad value." << endl;

// Check initial status of list LLL.

if ( LLL.IsEmpty() )

cerr << "OKAY: List LLL is initially empty." << endl;

else

cerr << "ERROR: LLL.IsEmpty() returning bad value." << endl;

// See what happens when you try to retrieve an item.

L.Retrieve(1, dataItem, success);

if (success)

{

if (dataItem == 50)

cerr << "OKAY: List item #" << 1 << " is: " << dataItem << endl;

else

cerr << "ERROR: List item #" << 1 << " is: " << dataItem << endl;

}

else

cerr << "ERROR: Retrieve operation failed." << endl;

L.Retrieve(0, dataItem, success);

if (success)

cerr << "ERROR: Retrieve operation failed." << endl;

L.Retrieve(2, dataItem, success);

if (success)

cerr << "ERROR: Retrieve operation failed." << endl;

// Fill list L with a bunch of numbers.

L.Insert(25, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert(80, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert(10, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert( 5, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert(35, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert(15, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

L.Insert(15, success);

if (success)

cerr << "ERROR: Invalid insert of duplicate succeeded." << endl;

for (int i = 1; i <= 9; i++)

{

L.Insert(i+100, success);

if (!success)

cerr << "ERROR: Insert operation failed." << endl;

}

// Display the items on the list L.

cerr << endl;

cerr << "DisplayList( L ): should list 16 items "

<< "(starting with 5 and ending with 109):" << endl;

DisplayList( L );

cerr << endl;

// See what happens when you try to delete an item.

L.Remove(25, success);

if (!success)

cerr << "ERROR: Remove operation failed." << endl;

position = L.Find(5);

if (position!=1)

cerr << "ERROR: Find failed. Remove() error?" << endl;

position = L.Find(109);

if (position!=15)

cerr << "ERROR: Find failed. Remove() error?" << endl;

// Delete the first item.

L.Remove(5, success);

if (!success)

cerr << "ERROR: Remove operation failed." << endl;

// Delete the last item.

L.Remove(109, success);

if (!success)

cerr << "ERROR: Remove operation failed." << endl;

// Check that really gone.

position = L.Find(5);

if (position!=-1)

cerr << "ERROR: Find operation failed." << endl;

position = L.Find(109);

if (position!=-1)

cerr << "ERROR: Find operation failed." << endl;

// Check what happens with duplicates.

L.Remove(15, success);

if (!success)

cerr << "ERROR: Remove operation failed." << endl;

position = L.Find(15);

if (position!=-1)

cerr << "ERROR: Find found a duplicate." << endl;

L.Remove(15, success);

if (success)

cerr << "ERROR: Remove operation should have failed." << endl;

L.Remove(100, success);

if (success)

cerr << "ERROR: Remove operation should have failed." << endl;

{SortedList M;

M = L;

LLL = M;

// Display the items on the list M.

cerr << "DisplayList( M ): should list 12 items " <<

"(10, 35, 50, 80, 101, ..., 108):" << endl;

DisplayList( M );

cerr << endl;

}

// Display the items on the list L.

cerr << "DisplayList( L ): should list 12 items " <<

"(10, 35, 50, 80, 101, ..., 108):" << endl;

DisplayList( L );

cerr << endl;

// See what happens when you try to delete ALL items.

cerr << "Should go from List Length = 11 down to 0:" << endl;

for ( int maxLoop=MAXLOOP; ! L.IsEmpty() && maxLoop>0; maxLoop--)

{

L.Retrieve(1,dataItem,success);

if (!success)

{

cerr << "ERROR: Retrieve operation failed." << endl;

break;

}

else

{

L.Remove(dataItem,success);

if (!success)

cerr << "ERROR: Delete operation failed." << endl;

cerr << "List Length = " << L.Length() << endl;

}

}

// Display the items on the list LLL.

cerr << endl;

cerr << "DisplayList( LLL ): should list 12 items " <<

"(10, 35, 50, 80, 101, ..., 108):" << endl;

DisplayList( LLL );

// ...end extra instructor-supplied tests for grading

// Display the items on the list L.

cerr << endl << "Next line of output should say: End " << OLA << endl;

DisplayList( L );

cerr << "End " << OLA << endl;

return 0;

} // end main

void DisplayList(SortedList list)

// IN

{

ItemType dataItem;

bool success;

// Display the items on the list.

int maxLoop=MAXLOOP;

for (int pos = 1; pos <= list.Length(); pos++)

{

list.Retrieve(pos, dataItem, success);

if (success)

cerr << "List item #" << pos << " is: " << dataItem << endl;

else

cerr << "ERROR: Retrieve operation failed." << endl;

if (--maxLoop==0)

{

cerr << "ERROR: Length() failed." << endl;

break;

}

}

} // end DisplayList