This is a C++ problem that I have tried to complete, but there are
many areas that I'm unsure on. I will be as detailed as possible.
The goal is to convert a container class into a template class. I will
include the definition(.h), implementation(.tem), and two test
files(.cpp). Please note that implementation of functions is fine,
only the syntax for conversion to template must be adjusted.
DEFINITION FILE
// FILE: list2template.h
// CLASS PROVIDED: List (a template class for a List of items,
// where each List may have a designated item called the current item)
//
// List::DEFAULT_CAPACITY is the initial capacity of a List that
is
// created by the default constructor.
//
//
//
// CONSTRUCTOR for the List class:
// List(size_t initial_capacity = DEFAULT_CAPACITY)
// Postcondition: The List has been initialized as an empty List.
// The insert/attach functions will work efficiently (without
allocating
// new memory) until this capacity is reached.
//
// MODIFICATION MEMBER FUNCTIONS for the List class:
// void resize(size_t new_capacity)
// Postcondition: The List's current capacity is changed to the
// new_capacity (but not less that the number of items already on
the
// list). The insert/attach functions will work efficiently
(without
// allocating new memory) until this new capacity is reached.
//
// void start( )
// Postcondition: The first item on the List becomes the current
item
// (but if the List is empty, then there is no current item).
//
// void advance( )
// Precondition: is_item returns true.
// Postcondition: If the current item was already the last item on
the
// List, then there is no longer any current item. Otherwise, the
new
// current item is the item immediately after the original current
item.
//
// void insert(const Item& entry)
// Postcondition: A new copy of entry has been inserted in the
List before
// the current item. If there was no current item, then the new
entry has
// been inserted at the front of the List. In either case, the
newly
// inserted item is now the current item of the List.
//
// void attach(const Item& entry)
// Postcondition: A new copy of entry has been inserted in the
List after
// the current item. If there was no current item, then the new
entry has
// been attached to the end of the List. In either case, the newly
// inserted item is now the current item of the List.
//
// void remove_current( )
// Precondition: is_item returns true.
// Postcondition: The current item has been removed from the List,
and the
// item after this (if there is one) is now the new current item.
//
// CONSTANT MEMBER FUNCTIONS for the List class:
// size_t size( ) const
// Postcondition: The return value is the number of items on the
List.
//
// bool is_item( ) const
// Postcondition: A true return value indicates that there is a
valid
// "current" item that may be retrieved by activating the current
// member function (listed below). A false return value indicates
that
// there is no valid current item.
//
// List::Item current( ) const
// Precondition: is_item( ) returns true.
// Postcondition: The item returned is the current item on the
List.
//
// VALUE SEMANTICS for the List class:
// Assignments and the copy constructor may be used with List
objects.
//
// DYNAMIC MEMORY USAGE by the List
// If there is insufficient dynamic memory, then the following
functions
// call new_handler: The constructors, insert, attach.
#ifndef LIST2_H
#define LIST2_H
#include <cstdlib> // Provides size_t
namespace Paul_List2{
class List
{
public:
// TYPEDEF and MEMBER CONSTANTS
enum{ DEFAULT_CAPACITY = 30};
typedef Item value_type;
// CONSTRUCTORS and DESTRUCTOR
List(size_t initial_capacity = DEFAULT_CAPACITY);
List(const List& source);
~List( );
// MODIFICATION MEMBER FUNCTIONS
void start( );
void advance( );
void insert(const Item& entry);
void attach(const Item& entry);
void remove_current( );
void resize(size_t new_capacity);
void operator =(const List& source);
// CONSTANT MEMBER FUNCTIONS
size_t size( ) const;
bool is_item( ) const;
Item current( ) const;
private:
Item *data;
size_t used;
size_t current_index;
size_t capacity;
};
}
#include"list2.tem"
#endif
IMPLEMENTATION FILE
// FILE: list2.tem
// CLASS IMPLEMENTED: list2 (See list2template.h for documentation)
// INVARIANT for the List ADT (i.e. verbalization of rules governing
// private member function behavior):
// 1. The number of items in the List is in the member variable used
// (i.e. used = 0 means the List is empty).
// 2. For an empty List, we do not care what is stored in any of the
// array data. For a non-empty List, the items in the List are
// stored in strictly maintained order in data[0] through
// data[used]. We don't care what's in the rest of data (so
don't
// need to initialize data in the constructor).
// 3. To maintain strict order, current_index is used to keep track
// of current location in data; when current_index is used-1,
// we're at the last place in the array. Also whenever
current_index
// is greater than or equal to used, there is no current item.
// 4. capacity keeps track of the current capacity of the array
pointed
// to by data; capacity starts out with the value
initial_capacity
// and is changed by resize as needed (whenever used is greater
than
// or equal to capacity).
#include <assert.h> // Provides assert
#include "list2template.h"
namespace Paul_List2{
template <class Item>
List<Item>::List(size_t initial_capacity) // the main
constructor
// Library facilities used: stdlib.h (included in the file list2.h)
{
data = new Item[initial_capacity];
capacity = initial_capacity;
used = 0;
current_index = 0;
}
template <class Item>
List<Item>::List(const List<Item>& source) // the copy
constructor
// Library facilities used: stdlib.h
{
size_t i;
data = new item[source.capacity];
capacity = source.capacity;
used = source.used;
current_index = source.current_index;
for(i = 0; i < used; i++)
data[i] = source.data[i];
}
template<class Item>
List<Item>::~List<Item>() // the destructor
{
delete [ ] data;
}
template <class Item>
void List<Item>::start()
{
current_index = 0;
}
template <class Item>
void List<Item>::advance()
// Library facilities used: assert.h
{
assert(is_item());
current_index++;
}
template <class Item>
void List<Item>::insert(const Item& entry)
// Library facilities used: stdlib.h
{
size_t i;
if (used >= capacity)
resize (1 + used + used/10); // Increase by 10%
if (!is_item())
current_index = 0;
for(i = used; i > current_index; i--)
data[i] = data[i-1];
data[current_index] = entry;
used++;
}
template <class Item>
void List<Item>::attach(const Item& entry)
// Library facilities used: stdlib.h
{
size_t i;
if (used >= capacity)
resize (1 + used + used/10); // Increase by 10%
if (!is_item())
{
current_index = used;
data[current_index] = entry;
used++;
}
else
{
for(i = used; i > (current_index + 1); i--)
data[i] = data[i-1];
data[current_index + 1] = entry;
used++;
current_index++;
}
}
template <class Item>
void List<Item>::remove_current()
// Library facilities used: assert.h, stdlib.h
{
size_t i;
assert(is_item());
for(i = current_index; i < used-1; i++)
data[i] = data[i+1];
used--;
}
template <class Item>
void List<Item>::resize(size_t new_capacity)
// Library facilities used: stdlib.h
{
// This is from the text, p. 174.
size_t i;
Item *larger_array; //was value_type
if (new_capacity == capacity)
return; // The allocated memory is already the right size.
if (new_capacity < used)
new_capacity = used; // Can't allocate less than we are
using.
larger_array = new Item[new_capacity]; //was value_type
for(i = 0; i < used; i++ )
larger_array[i] = data[i];
delete [ ] data;
data = larger_array;
capacity = new_capacity;
}
template <class Item>
void List<Item>::operator =(const List<Item>& source)
// Library facilities used: stdlib.h
{
size_t i;
Item *new_data; //Was value type
if (capacity != source.capacity)
{
new_data = new value_type[source.capacity];
delete [] data;
data = new_data;
capacity = source.capacity;
}
used = source.used;
current_index = source.current_index;
for(i = 0; i < used; i++)
data[i] = source.data[i];
}
template <class Item>
size_t List<Item>::size() const
// Library facilities used: stdlib.h
{
return used;
}
template <class Item>
bool List<Item>::is_item() const
{
return (current_index < used);
}
template <class Item>
List<Item>::Item List::current() const //second Item was value_type
// Library facilities used: assert.h
{
assert(is_item());
return data[current_index];
}
}
FIRST TEST PROGRAM
// FILE: listex2.cpp
// Non-interactive test program for the List class using a dynamic
array,
// with improved test for heap leaks.
//
// DESCRIPTION:
// Each function of this program tests part of the List class,
returning
// some number of points to indicate how much of the test was passed.
// A description and result of each test is printed to cout.
// Maximum number of points awarded by this program is determined by
the
// constants POINTS[1], POINTS[2]...
//
// WHAT'S NEW:
// This new version of the test program includes an improved test for
heap
// leaks by overriding the new and delete operators. Users should
consider
// placing these new and delete operators into a separate cpp file,
but
// I have included everything in one file for easier distribution.
#include <iostream> // Provides cout.
#include <string> // Provides memcpy.
#include <cstdlib> // Provides size_t.
#include "list2template.h" // Provides the List class with double
items.
using namespace std;
using namespace Paul_List2;
// Descriptions and points for each of the tests:
const size_t MANY_TESTS = 8;
const List<int> POINTS[MANY_TESTS+1] = {
100, // Total points for all tests.
20, // Test 1 points
15, // Test 2 points
15, // Test 3 points
10, // Test 4 points
10, // Test 5 points
10, // Test 6 points
10, // Test 7 points
10 // Test 8 points
};
const List<char> DESCRIPTION[MANY_TESTS+1][256] = {
"tests for List Class with a dynamic array",
"Testing insert, attach, and the constant member functions",
"Testing situations where the cursor goes off the list",
"Testing remove_current",
"Testing the resize member function",
"Testing the copy constructor",
"Testing the assignment operator",
"Testing insert/attach when current DEFAULT_CAPACITY exceeded",
"Testing for possible heap leaks"
};
// **************************************************************************
// Replacements for new and delete:
// The next two functions replace the new and delete operators. Any
code
// that is linked with this .cxx file will use these replacements
instead
// of the standard new and delete. The replacements provide three
features:
// 1. The global variable memory_used_now keeps track of how much
memory has
// been allocated by calls to new. (The global variable is static
so that
// it cannot be accessed outside of this .cxx file.)
// 2. The new operator fills all newly allocated memory with a GARBAGE
char.
// 3. Each block of newly allocated memory is preceeded and followed
by a
// border of BORDER_SIZE characters. The first part of the front
border
// contains a copy of the size of the allocated memory. The rest of
the
// border contains a BORDER char.
// During any delete operation, the border characters are checked. If
any
// border character has been changed from BORDER to something else,
then an
// error message is printed and the program is halted. This stops most
// cases of writing beyond the ends of the allocated memory.
// **************************************************************************
const size_t BORDER_SIZE = 2*sizeof(double);
const List<char> GARBAGE = 'g';
const List<char> BORDER = 'b';
static size_t memory_used_now = 0;
template <class Item>
void* operator new(size_t size)
{
List<char> *whole_block; // Pointer to the entire block that
we get from heap
size_t *size_spot; // Spot in the block where to store a copy
of size
List<char> *front_border; // The border bytes in front of the
user's memory
List<char> *middle; // The memory to be given to the
calling program
List<char> *back_border; // The border bytes at the back of
the user's memory
size_t i; // Loop control variable
// Allocate the block of memory for the user and for the two
borders.
whole_block = (List<char> *) malloc(2*BORDER_SIZE + size);
if (whole_block == NULL)
return NULL;
// Figure out the start points of the various pieces of the block.
size_spot = (size_t *) whole_block;
front_border = (List<char> *) (whole_block + sizeof(size_t));
middle = (List<char> *) (whole_block + BORDER_SIZE);
back_border = middle + size;
// Put a copy of the size at the start of the block.
*size_spot = size;
// Fill the borders and the middle section.
for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)
front_border[i] = BORDER;
for (i = 0; i < size; i++)
middle[i] = GARBAGE;
for (i = 0; i < BORDER_SIZE; i++)
back_border[i] = BORDER;
// Update the global static variable showing how much memory is
now used.
memory_used_now += size;
return middle;
}
template <class Item>
void operator delete(void* p)
{
List<char> *whole_block; // Pointer to the entire block that
we get from heap
size_t *size_spot; // Spot in the block where to store a copy
of size
List<char> *front_border; // The border bytes in front of the
user's memory
List<char> *middle; // The memory to be given to the
calling program
List<char> *back_border; // The border bytes at the back of
the user's memory
size_t i; // Loop control variable
size_t size; // Size of the block being returned
bool corrupt; // Set to true if the border was corrupted
// Figure out the start of the pieces of the block, and the size.
whole_block = ((List<char> *) (p)) - BORDER_SIZE;
size_spot = (size_t *) whole_block;
size = *size_spot;
front_border = (List<char> *) (whole_block + sizeof(size_t));
middle = (List<char> *) (whole_block + BORDER_SIZE);
back_border = middle + size;
// Check the borders for the BORDER character.
corrupt = false;
for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)
if (front_border[i] != BORDER)
corrupt = true;
for (i = 0; i < BORDER_SIZE; i++)
if (back_border[i] != BORDER)
corrupt = true;
if (corrupt)
{
cout << "The delete operator has detected that the program wrote\n";
cout << "beyond the ends of a block of memory that was allocated\n";
cout << "by the new operator. Program will be halted." << endl;
exit(0);
}
else
{
// Fill memory with garbage in case program tries to use it
// even after the delete.
for (i = 0; i < size + 2*BORDER_SIZE; i++)
whole_block[i] = GARBAGE;
free(whole_block);
memory_used_now -= size;
}
}
// **************************************************************************
// bool test_basic(const List& test, size_t s, bool has_cursor)
// Postcondition: A return value of true indicates:
// a. test.size() is s, and
// b. test.is_item() is has_cursor.
// Otherwise the return value is false.
// In either case, a description of the test result is printed to
cout.
// **************************************************************************
template<class Item>
bool test_basic(const List<Item>& test, size_t s, bool has_cursor)
{
bool answer;
cout << "Testing that size() returns " << s << " ... ";
cout.flush( );
answer = (test.size( ) == s);
cout << (answer ? "Passed." : "Failed.") << endl;
if (answer)
{
cout << "Testing that is_item() returns ";
cout << (has_cursor ? "true" : "false") << " ... ";
cout.flush( );
answer = (test.is_item( ) == has_cursor);
cout << (answer ? "Passed." : "Failed.") << endl;
}
return answer;
}
// **************************************************************************
// bool test_items(List& test, size_t s, size_t i, double items[])
// The function determines if the test list has the correct items
// Precondition: The size of the items array is at least s.
// Postcondition: A return value of true indicates that
test.current()
// is equal to items[i], and after test.advance() the result of
// test.current() is items[i+1], and so on through items[s-1].
// At this point, one more advance takes the cursor off the list.
// If any of this fails, the return value is false.
// NOTE: The test list has been changed by advancing its cursor.
// **************************************************************************
template <class Item>
bool test_items(List<Item>& test, size_t s, size_t i, List<double>
items[])
{
bool answer = true;
cout << "The cursor should be at item [" << i << "]" << " of the
List\n";
cout << "(counting the first item as [0]). I will advance the
cursor\n";
cout << "to the end of the List, checking that each item is
correct...";
cout.flush( );
while ((i < s) && test.is_item( ) && (test.current( ) ==
items[i]))
{
i++;
test.advance( );
}
if ((i != s) && !test.is_item( ))
{ // The test.is_item( ) function returns false too soon.
cout << "\n Cursor fell off the list too soon." << endl;
answer = false;
}
else if (i != s)
{ // The test.current( ) function returned a wrong value.
cout << "\n The item [" << i << "] should be " << items[i] <<
",\n";
cout << " but it was " << test.current( ) << " instead.\n";
answer = false;
}
else if (test.is_item( ))
{ // The test.is_item( ) function returns true after moving off
the List.
cout << "\n The cursor was moved off the list,";
cout << " but is_item still returns true." << endl;
answer = false;
}
cout << (answer ? "Passed." : "Failed.") << endl;
return answer;
}
// **************************************************************************
// bool correct(List& test, size_t s, size_t cursor_spot, double
items[])
// This function determines if the List (test) is "correct"
according to
// these requirements:
// a. it has exactly s items.
// b. the items (starting at the front) are equal to
// items[0] ... items[s-1]
// c. if cursor_spot < s, then test's cursor must be at
// the location given by cursor_spot.
// d. if cursor_spot >= s, then test must not have a cursor.
// NOTE: The function also moves the cursor off the List.
// **************************************************************************
template <class Item>
bool correct(List<Item>& test, size_t size, size_t cursor_spot,
List<double> items[])
{
bool has_cursor = (cursor_spot < size);
// Check the List's size and whether it has a cursor.
if (!test_basic(test, size, has_cursor))
{
cout << "Basic test of size() or is_item() failed." << endl << endl;
return false;
}
// If there is a cursor, check the items from cursor to end of the
list.
if (has_cursor && !test_items(test, size, cursor_spot, items))
{
cout << "Test of the list's items failed." << endl << endl;
return false;
}
// Restart the cursor at the front of the list and test items
again.
cout << "I'll call start() and look at the items one more time..."
<< endl;
test.start( );
if (has_cursor && !test_items(test, size, 0, items))
{
cout << "Test of the list's items failed." << endl << endl;
return false;
}
// If the code reaches here, then all tests have been passed.
cout << "All tests passed for this list." << endl << endl;
return true;
}
// **************************************************************************
// int test1( )
// Performs some basic tests of insert, attach, and the constant
member
// functions. Returns POINTS[1] if the tests are passed. Otherwise
returns 0.
// **************************************************************************
template <class Item>
int test1( )
{
List<Item> empty; // An empty list
List<Item> test; // A list to add
items to
List<double> items1[4] = { 5, 10, 20, 30 }; // These 4 items are
put in a list
List<double> items2[4] = { 10, 15, 20, 30 }; // These are put in
another list
// Test that the empty list is really empty
cout << "Starting with an empty List." << endl;
if (!correct(empty, 0, 0, items1)) return 0;
// Test the attach function to add something to an empty list
cout << "I am now using attach to put 10 into an empty List." <<
endl;
test.attach(10);
if (!correct(test, 1, 0, items2)) return 0;
// Test the insert function to add something to an empty list
cout << "I am now using insert to put 10 into an empty List." <<
endl;
test = empty;
test.insert(10);
if (!correct(test, 1, 0, items2)) return 0;
// Test the insert function to add an item at the front of a list
cout << "I am now using attach to put 10,20,30 in an empty
List.\n";
cout << "Then I move the cursor to the start and insert 5." <<
endl;
test = empty;
test.attach(10);
test.attach(20);
test.attach(30);
test.start( );
test.insert(5);
if (!correct(test, 4, 0, items1)) return 0;
// Test the insert function to add an item in the middle of a list
cout << "I am now using attach to put 10,20,30 in an empty
List.\n";
cout << "Then I move the cursor to the start, advance once, ";
cout << "and insert 15." << endl;
test = empty;
test.attach(10);
test.attach(20);
test.attach(30);
test.start( );
test.advance( );
test.insert(15);
if (!correct(test, 4, 1, items2)) return 0;
// Test the attach function to add an item in the middle of a list
cout << "I am now using attach to put 10,20,30 in an empty
List.\n";
cout << "Then I move the cursor to the start and attach 15 ";
cout << "after the 10." << endl;
test = empty;
test.attach(10);
test.attach(20);
test.attach(30);
test.start( );
test.attach(15);
if (!correct(test, 4, 1, items2)) return 0;
// All tests have been passed
cout << "All tests of this first function have been passed." <<
endl;
return POINTS[1];
}
// **************************************************************************
// int test2( )
// Performs a test to ensure that the cursor can correctly be run
off the end
// of the list. Also tests that attach/insert work correctly when
there is
// no cursor. Returns POINTS[2] if the tests are passed. Otherwise
returns 0.
// **************************************************************************
template <class Item>
int test2( )
{
List<Item> test;
size_t i;
// Put three items in the list
cout << "Using attach to put 20 and 30 in the List, and then
calling\n";
cout << "advance, so that is_item should return false ... ";
cout.flush( );
test.attach(20);
test.attach(30);
test.advance( );
if (test.is_item( ))
{
cout << "failed." << endl;
return 0;
}
cout << "passed." << endl;
// Insert 10 at the front and run the cursor off the end again
cout << "Inserting 10, which should go at the List's front." <<
endl;
cout << "Then calling advance three times to run cursor off the
list ...";
cout.flush( );
test.insert(10);
test.advance( ); // advance to the 20
test.advance( ); // advance to the 30
test.advance( ); // advance right off the list
if (test.is_item( ))
{
cout << " failed." << endl;
return false;
}
cout << " passed." << endl;
// Attach more items until the list becomes full.
// Note that the first attach should attach to the end of the
list.
cout << "Calling attach to put the numbers 40, 50, 60 ...";
cout << test.DEFAULT_CAPACITY*10 << " at the List's end." << endl;
for (i = 4; i <= test.DEFAULT_CAPACITY; i++)
test.attach(i*10);
// Test that the list is correctly filled.
cout << "Now I will test that the list has 10, 20, 30, ...";
cout << test.DEFAULT_CAPACITY*10 << "." << endl;
test.start( );
for (i = 1; i <= test.DEFAULT_CAPACITY; i++)
{
if ((!test.is_item( )) || test.current( ) != i*10)
{
cout << " Test failed to find " << i*10 << endl;
return 0;
}
test.advance( );
}
if (test.is_item( ))
{
cout << " There are too many items on the List." << endl;
return false;
}
// All tests passed
cout << "All tests of this second function have been passed." <<
endl;
return POINTS[2];
}
// **************************************************************************
// int test3( )
// Performs basic tests for the remove_current function.
// Returns POINTS[3] if the tests are passed. Returns POINTS[3] / 4
if almost
// all the tests are passed. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test3( )
{
// In the next declarations, I am declaring a List called test.
// Both before and after the List, I declare a small array of
characters,
// and I put the character 'x' into each spot of these arrays.
// Later, if I notice that one of the x's has been changed, or if
// I notice an 'x' inside of the List, then the most
// likely reason was that one of the List's member functions
accessed
// the List's array outside of its legal indexes.
char prefix[4] = {'x', 'x', 'x', 'x'};
List<Item> test;
char suffix[4] = {'x', 'x', 'x', 'x'};
// Within this function, I create several different Lists using
the
// items in these arrays:
List<double> items1[1] = { 30 };
List<double> items2[2] = { 10, 30 };
List<double> items3[3] = { 10, 20, 30 };
size_t i; // for-loop control variable
List<char> *char_ptr; // Variable to loop at each character in a
List's memory
// Build a list with three items 10, 20, 30, and remove the
middle,
// and last and then first.
cout << "Using attach to build a list with 10,30." << endl;
test.attach(10);
test.attach(30);
cout << "Insert a 20 before the 30, so entire List is 10,20,30."
<< endl;
test.insert(20);
if (!correct(test, 3, 1, items3)) return 0;
cout << "Remove the 20, so entire List is now 10,30." << endl;
test.start( );
test.advance( );
test.remove_current( );
if (!correct(test, 2, 1, items2)) return 0;
cout << "Remove the 30, so entire List is now just 10 with no
cursor.";
cout << endl;
test.start( );
test.advance( );
test.remove_current( );
if (!correct(test, 1, 1, items2)) return 0;
cout << "Set the cursor to the start and remove the 10." << endl;
test.start( );
test.remove_current( );
if (!correct(test, 0, 0, items2)) return 0;
// Build a list with three items 10, 20, 30, and remove the
middle,
// and then first and then last.
cout << "Using attach to build another list with 10,30." << endl;
test.attach(10);
test.attach(30);
cout << "Insert a 20 before the 30, so entire List is 10,20,30."
<< endl;
test.insert(20);
if (!correct(test, 3, 1, items3)) return 0;
cout << "Remove the 20, so entire List is now 10,30." << endl;
test.start( );
test.advance( );
test.remove_current( );
if (!correct(test, 2, 1, items2)) return 0;
cout << "Set the cursor to the start and remove the 10," << endl;
cout << "so the List should now contain just 30." << endl;
test.start( );
test.remove_current( );
if (!correct(test, 1, 0, items1)) return 0;
cout << "Remove the 30 from the List, resulting in an empty List."
<< endl;
test.start( );
test.remove_current( );
if (!correct(test, 0, 0, items1)) return 0;
// Build a list with three items 10, 20, 30, and remove the first.
cout << "Build a new List by inserting 30, 10, 20 (so the List\n";
cout << "is 20, then 10, then 30). Then remove the 20." << endl;
test.insert(30);
test.insert(10);
test.insert(20);
test.remove_current( );
if (!correct(test, 2, 0, items2)) return 0;
test.start( );
test.remove_current( );
test.remove_current( );
// Just for fun, fill up the List, and empty it!
cout << "Just for fun, I'll empty the List then fill it up,
then\n";
cout << "empty it again. During this process, I'll try to
determine\n";
cout << "whether any of the List's member functions access the\n";
cout << "array outside of its legal indexes." << endl;
for (i = 0; i < test.DEFAULT_CAPACITY; i++)
test.insert(0);
for (i = 0; i < test.DEFAULT_CAPACITY; i++)
test.remove_current( );
// Make sure that the character 'x' didn't somehow get into the
list,
// as that would indicate that the List member functions are
// copying data from before or after the list into the list.
char_ptr = (char *) &test;
for (i = 0; i < sizeof(List); i++)
if (char_ptr[i] == 'x')
{
cout << "Illegal array access detected." << endl;
return POINTS[3] / 4;
}
// Make sure that the prefix and suffix arrays still have four
// x's each. Otherwise one of the List operations wrote outside of
// the legal boundaries of its array.
for (i = 0; i < 4; i++)
if ((suffix[i] != 'x') || (prefix[i] != 'x'))
{
cout << "Illegal array access detected." << endl;
return POINTS[3] / 4;
}
// All tests passed
cout << "All tests of this third function have been passed." <<
endl;
return POINTS[3];
}
// **************************************************************************
// int test4( )
// Performs some tests of resize.
// Returns POINTS[4] if the tests are passed. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test4( )
{
List<Item> test;
size_t i;
List<char> bytes[sizeof(List<Item>)];
List<char> newbytes[sizeof(List<Item>)];
size_t mismatches;
cout << "I will now resize a List to a larger capacity, and
then\n";
cout << "attach that many items. The List should NOT need to\n";
cout << "resize itself under this situation." << endl;
test.resize(2*test.DEFAULT_CAPACITY);
test.attach(0);
memcpy(bytes, (List<char> *) &test, sizeof(List));
// At this point, I should be able to insert 2*DEFAULT_CAPACITY-1
// more items without calling resize again. Therefore, at most 1
byte
// of the object will change (the least significant byte of used).
for (i = 1; i < 2*test.DEFAULT_CAPACITY; i++)
test.attach(i);
test.start( );
memcpy(newbytes, (List<char> *) &test, sizeof(List<Item>));
for (i = 0; i < 2*test.DEFAULT_CAPACITY; i++)
{
if (test.current( ) != i)
{
cout << " List does not contain correct items." << endl;
return 0;
}
test.advance( );
}
test.start( );
mismatches = 0;
for (i = 0; i < sizeof(List<Item>); i++)
if (bytes[i] != newbytes[i])
mismatches++;
if (mismatches > 1)
{
cout << " List was resized when it should not be." << endl;
return 0;
}
else
cout << " Test passed." << endl;
cout << "Now I will call resize(1) for the List, but the
actual\n";
cout << "List should not change because the List already has \n";
cout << test.DEFAULT_CAPACITY*2 << " items." << endl;
memcpy(bytes, (List<char> *) &test, sizeof(List<Item>));
test.resize(1);
mismatches = 0;
for (i = 0; i < sizeof(List<Item>); i++)
if (bytes[i] != newbytes[i])
mismatches++;
if (mismatches > 0)
{
cout << " List was resized when it should not be." << endl;
return 0;
}
else
cout << " Test passed." << endl;
// All tests passed
cout << "All tests of this fourth function have been passed." <<
endl;
return POINTS[4];
}
// **************************************************************************
// int test5( )
// Performs some tests of the copy constructor.
// Returns POINTS[5] if the tests are passed. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test5( )
{
List<Item> original; // A list that we'll copy.
List<double> items[2*original.DEFAULT_CAPACITY];
size_t i;
// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;
// Test copying of an empty list. After the copying, we change the
original.
cout << "Copy constructor test: for an empty list." << endl;
List<Item> copy1(original);
original.attach(1); // Changes the original list, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;
// Test copying of a list with current item at the tail.
cout << "Copy constructor test: for a list with cursor at tail."
<< endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
List<Item> copy2(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY, 2*original.DEFAULT_CAPACITY-1,
items)
)
return 0;
// Test copying of a list with cursor near the middle.
cout << "Copy constructor test: for a list with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
List<Item> copy3(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;
// Test copying of a list with cursor at the front.
cout << "Copy constructor test: for a list with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
List<Item> copy4(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;
// Test copying of a list with no current item.
cout << "Copy constructor test: for a list with no current item."
<< endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
List<Item> copy5(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY, 2*original.DEFAULT_CAPACITY,
items)
)
return 0;
// All tests passed
cout << "All tests of this fifth function have been passed." <<
endl;
return POINTS[5];
}
// **************************************************************************
// int test6( )
// Performs some tests of the assignment operator.
// Returns POINTS[6] if the tests are passed. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test6( )
{
List<Item> original; // A list that we'll copy.
List<double> items[2*original.DEFAULT_CAPACITY];
size_t i;
// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;
// Test copying of an empty list. After the copying, we change the
original.
cout << "Assignment operator test: for an empty list." << endl;
List<Item> copy1;
copy1 = original;
original.attach(1); // Changes the original list, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;
// Test copying of a list with current item at the tail.
cout << "Assignment operator test: for a list with cursor at
tail." << endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
List<Item> copy2;
copy2 = original;
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY, 2*original.DEFAULT_CAPACITY-1,
items)
)
return 0;
// Test copying of a list with cursor near the middle.
cout << "Assignment operator test: for a list with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
List<Item> copy3;
copy3 = original;
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;
// Test copying of a list with cursor at the front.
cout << "Assignment operator test: for a list with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
List<Item> copy4;
copy4 = original;
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;
// Test copying of a list with no current item.
cout << "Assignment operator test: for a list with no current
item." << endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
List<Item> copy5;
copy5 = original;
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but
not the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY, 2*original.DEFAULT_CAPACITY,
items)
)
return 0;
cout << "Checking correctness of a self-assignment x = x;" <<
endl;
original.insert(2);
original = original;
if (!correct
(original, 2*original.DEFAULT_CAPACITY, 1, items)
)
return 0;
// All tests passed
cout << "All tests of this sixth function have been passed." <<
endl;
return POINTS[6];
}
// **************************************************************************
// int test7( )
// Performs some basic tests of insert and attach for the case where
the
// current capacity has been reached.
// Returns POINTS[7] if the tests are passed. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test7( )
{
List<Item> testa, testi;
List<double> items[2*testa.DEFAULT_CAPACITY];
size_t i;
// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*testa.DEFAULT_CAPACITY; i++)
items[i-1] = i;
cout << "Testing to see that attach works correctly when the\n";
cout << "current capacity is exceeded." << endl;
for (i = 1; i <= 2*testa.DEFAULT_CAPACITY; i++)
testa.attach(i);
if (!correct
(testa, 2*testa.DEFAULT_CAPACITY, 2*testa.DEFAULT_CAPACITY-1, items)
)
return 0;
cout << "Testing to see that insert works correctly when the\n";
cout << "current capacity is exceeded." << endl;
for (i = 2*testi.DEFAULT_CAPACITY; i >= 1; i--)
testi.insert(i);
if (!correct
(testi, 2*testi.DEFAULT_CAPACITY, 0, items)
)
return 0;
// All tests passed
cout << "All tests of this seventh function have been passed." <<
endl;
return POINTS[7];
}
// **************************************************************************
// int test8( )
// Tries to find a heap leak in resize, the assignment operator or
the
// destructor.
// Returns POINTS[7] if no leaks are found. Otherwise returns 0.
// **************************************************************************
template <class Item>
int test8( )
{
List<Item> test_list;
List<Item> empty;
List<Item>* list_ptr;
size_t base_usage;
cout << "Checking for possible heap leak." << endl;
cout << "This could occur if your List does not release memory\n";
cout << "during a resize, or if the assignment operator does
not\n";
cout << "correctly release memory, or if the destructor does not
release\n";
cout << "the memory of the dynamic array." << endl;
cout << "An error will also occur if resize is not allowed to
reduce the\n";
cout << "size of the array. For example, if the current capacity
is 1000\n";
cout << "and the List has only 10 items, then resize(100)
should\n";
cout << "reduce the current capacity down to 100.\n";
// Test resize for a heap leak
base_usage = memory_used_now;
test_list.resize(10000);
test_list.resize(test_list.DEFAULT_CAPACITY);
if (memory_used_now != base_usage)
{
cout << " Test failed. Resize cannot be used to reduce capacity."
<< endl;
return 0;
}
// Test assignment for a heap leak
test_list.resize(10000);
test_list = empty;
if (memory_used_now != base_usage)
{
cout << " Test failed. Possible heap leak in assignment operator."
<< endl;
return 0;
}
// Test the destructor for a heap leak
list_ptr = new List<Item>;
list_ptr->resize(10000);
delete list_ptr;
if (memory_used_now != base_usage)
{
cout << " Test failed. Possible heap leak in destructor." << endl;
return 0;
}
cout << "No heap leak found." << endl;
return POINTS[8];
}
template <class Item>
int run_a_test(List<int> number, const List<char> message[], List<int>
test_function( ), List<int> max)
{
List<int> result;
cout << endl << "START OF TEST " << number << ":" << endl;
cout << message << " (" << max << " points)." << endl;
result = test_function( );
if (result > 0)
{
cout << "Test " << number << " got " << result << " points";
cout << " out of a possible " << max << "." << endl;
}
else
cout << "Test " << number << " failed." << endl;
cout << "END OF TEST " << number << "." << endl << endl;
return result;
}
// **************************************************************************
// int main( )
// The main program calls all tests and prints the sum of all points
// earned from the tests.
// **************************************************************************
template <class Item>
List<int> main( )
{
List<int> sum = 0;
cout << "Running " << DESCRIPTION[0] << endl;
sum += run_a_test(1, DESCRIPTION[1], test1, POINTS[1]);
sum += run_a_test(2, DESCRIPTION[2], test2, POINTS[2]);
sum += run_a_test(3, DESCRIPTION[3], test3, POINTS[3]);
sum += run_a_test(4, DESCRIPTION[4], test4, POINTS[4]);
sum += run_a_test(5, DESCRIPTION[5], test5, POINTS[5]);
sum += run_a_test(6, DESCRIPTION[6], test6, POINTS[6]);
sum += run_a_test(7, DESCRIPTION[7], test7, POINTS[7]);
sum += run_a_test(8, DESCRIPTION[8], test8, POINTS[8]);
cout << "You score ";
cout << sum << " points out of the " << POINTS[0];
cout << " points from this examination program.\n";
return EXIT_SUCCESS;
}
SECOND TEST PROGRAM
// FILE: listtest.cpp
// An interactive test program for the new List ADT.
#include <cctype> // Provides toupper
#include <iostream> // Provides cout and cin
#include <cstdlib> // Provides EXIT_SUCCESS and size_t
#include "list2template.h" // With Item defined as double
using namespace std;
using namespace Paul_List2;
// PROTOTYPES for functions used by this test program:
void print_menu( );
// Postcondition: A menu of choices for this program has been written
to cout.
List<char> get_user_command( );
// Postcondition: The user has been prompted to enter a one character
command.
// The next character has been read (skipping blanks and newline
characters),
// and this character has been returned.
void show_list(List<Item> display);
// Postcondition: The items on display have been printed to cout (one
per line).
List<double> get_number( );
// Postcondition: The user has been prompted to enter a real number.
The
// number has been read, echoed to the screen, and returned by the
function.
List<int> main( )
{
List<Item> test; // A List that we'll perform tests on
List<char> choice; // A command character entered by the user
cout << "I have initialized an empty List of real numbers." <<
endl;
do
{
print_menu( );
choice = toupper(get_user_command( ));
switch (choice)
{
case '!': test.start( );
break;
case '+': test.advance( );
break;
case '?': if (test.is_item( ))
cout << "There is an item." << endl;
else
cout << "There is no current item." << endl;
break;
case 'C': if (test.is_item( ))
cout << "Current item is: " <<
test.current( ) << endl;
else
cout << "There is no current item." << endl;
break;
case 'P': show_list(test);
break;
case 'S': cout << "The List size is " << test.size( ) <<
endl;
break;
case 'I': test.insert(get_number( ));
break;
case 'A': test.attach(get_number( ));
break;
case 'R': test.remove_current( );
cout << "The current item has been removed" <<
endl;
break;
case 'Q': cout << "Ridicule is the best test of truth." <<
endl;
break;
default: cout << choice << " is invalid. Sorry." << endl;
}
}
while (cin && (choice != 'Q'));
if (!cin)
cerr << "Bad input character." << endl;
return EXIT_SUCCESS;
}
template <class Item>
void print_menu( )
// Library facilities used: iostream.h
{
cout << endl; // Print blank line before the menu
cout << "The following choices are available: " << endl;
cout << " ! Activate the start( ) function" << endl;
cout << " + Activate the advance( ) function" << endl;
cout << " ? Print the result from the is_item( ) function" <<
endl;
cout << " C Print the result from the current( ) function" <<
endl;
cout << " P Print a copy of the entire List" << endl;
cout << " S Print the result from the size( ) function" << endl;
cout << " I Insert a new number with the insert(...) function"
<< endl;
cout << " A Attach a new number with the attach(...) function"
<< endl;
cout << " R Activate the remove_current( ) function" << endl;
cout << " Q Quit this test program" << endl;
}
template <class Item>
List<char> get_user_command( )
// Library facilities used: iostream.h
{
List<char> command;
cout << "Enter choice: ";
cin >> command; // Input of characters skips blanks and newline
character
return command;
}
template <class Item>
void show_list(List<Item> display)
// Library facilities used: iostream.h
{
for (display.start( ); display.is_item( ); display.advance( ))
cout << display.current( ) << endl;
}
template <class Item>
List<double> get_number( )
// Library facilities used: iostream.h
{
List<double> result;
cout << "Please enter a real number for the List: ";
cin >> result;
cout << result << " has been read." << endl;
return result;
}
Please troubleshoot these files for template conversion. |
