Program 1 Value-Oriented ADT (Abstract Data Type)

Description: A position-oriented ADT is an ADT where the user specifies the storage location for
data items. This is most often done by adding and removing data items by index. In a valueoriented ADT, the user does not specify where the items are to be placed. The data itself
determines how the data should be organized. The most basic example of a value-oriented
ADT is a sorted list. If the user determines where the items are to be placed in a sorted list, the
list is not likely to be sorted in general.
Templates (specifying the type of data items for the ADT): Use templates as discussed in class
to make your sorted list as generally useful as possible
Function Pointers: Requiring the items to be sorted suggests that we need some way to
determine the proper ordering between two data items. You can assume that any data type
substituted for T in your template will have the following two methods defined (do not use the
below in your SortedListArray)
• static int compare_items (T* item_one, T* item_two) //Used when inserting an item
• static int compare_keys (String* search_key, T* item) //Used to remove or retrieve an
item
In the first method, you are directly comparing two items of type T. An integer < 0 is returned if
one should come before two, an integer 0 is returned if two should come before one, and
zero is returned if the two items are equal. The method completely specifies how the two items
should be compared and is irrelevant to your sorted list. The CD class compares the CDs by
title, but your sorted list does not need to be aware of this detail. We need this method when
we are inserting items into the sorted list.
In the second method, you are comparing a particular search key with a data item. We will use
the convention that search keys will always be Strings (i.e. the title of the CD). We need this
method when removing or retrieving items from the sorted list
Header File (specifying the operations for the ADT): The public operations required by the ADT
are as follows:
• constructor that accepts the pointers to the two required functions described above
• default destructor
• bool isEmpty()
• int size()
• T* get (String* search_key)• void add (T* item)
• void remove (String* search_key
• ListArrayIterator<T* iterator()
You will need private data members and private methods as well
Sorted List Array: Implement (call your implementation SortedListArray), test and document a
sorted list using an array. The easiest way to do this is to use as much of the index-based array
list code as possible. However, you will need to compute the index rather than using a usersupplied index. Write methods that utilize a binary search to compute the index for add and
remove. This makes the get method as efficient as possible (but add and remove are still
inefficient). If there are two (or more) CDs with the same search key, make sure that these CDs
are together in the list.
You will need to allow your array to dynamically resize. When adding items, double the size of
the array if there is no more room available inside the array
Sorted List Array Driver: Write a driver (SortedListArrayDriver) to thoroughly test your
implementation. Part of your grade will depend on evidence of testing. Note that it is not
necessary to provide user interaction in your driver class for this program. Simply hard code
your (many) tests. In particular, try to remove items that are not present in the list. Make sure
to test sorting by artist (add methods to the CD class and rebuild the library)
Using Function Pointers: Insert the following function pointer declarations in the private data
section of SortedListArray
• int (*compare_items)(T* item_1, T* item_2)
• int (*compare_keys) (String* key, T* item)
Your constructor should then look like this (make sure to add the parameters in the class
definition as well)
template <class T
SortedListArray<T::SortedListArray(int (*comp_items)(T* item_1,
T* item_2), int (*comp_keys) (String* key, T* item))
{
max_list = 2;
items = new T*[max_list];
sze = 0;
//copy the memory address of the function into a private
instance variable
compare_items = comp_items;
compare_keys = comp_keys;
}To use the function pointers inside your binary search to compare two items or a key and an
item, use the following:
• int compare = (*compare_items)(item, test) //if compare <0 this indicates item is before
test
• int compare = (*compare_keys)(key, test)
Finally, to create your sorted list use the following
• SortedListArray<CD* sl = new SortedListArray<CD(&CD::compare_items,
&CD::compare_keys)
Starting Files: The starting files I am supplying for you on this program are in the “Common
Files” section of Piazza listed appropriately enough as “Program 1 Files”
Documentation: Fully document SortedListArray
• Preconditions and Postconditions