Objectives: The main objectives of this project are to test your ability to create and use list-based

dynamic data structures. A review of your knowledge to manipulate dynamic memory, classes,

pointers and iostream to all extents, is also included. You may from now on freely use square

bracket-indexing, pointers, references, all operators, the library, and the

std::string type as you deem proper.

Description:

For this project you will create List classes. There will have to be two separate List-based

implementations, one Array-based, and the other Node-based.

Array-based List:

The following header file extract is used to explain the required specifications for the class (the

actual header ArrayList.h file is provided and accompanies the Project description):

class ArrayList{

friend std::ostream& operator<<(std::ostream& os, //(i)

const ArrayList& arrayList);

public:

ArrayList(); //(1)

ArrayList(size_t count, const DataType& value); //(2)

ArrayList(const ArrayList& other); //(3)

~ArrayList(); //(4)

ArrayList& operator= (const ArrayList& rhs); //(5)

DataType* First(); //(6)

DataType* Last(); //(7)

DataType* Find(const DataType & target, //(8)

DataType * & previous,

const DataType * start = NULL);

DataType* InsertAfter(const DataType& target, //(9)

const DataType& value);

DataType* InsertBefore(const DataType& target, //(10)

const DataType& value);

DataType* Erase(const DataType& target); //(11)

DataType& operator[] (size_t position); //(12)

size_t size() const; //(13)

bool empty() const; //(14)

void clear(); //(15)

private:

void resize(size_t count); //(16)

DataType * m_array;

size_t m_size;

size_t m_maxsize;

};

The ArrayList Class will contain the following private data members:

m_array, a DataType class type Pointer, pointing to the Dynamically Allocated Array data.

It is the container for the ArrayList data, and will have to be resized (reallocated) whenever it

needs to grow to accommodate more data than it can fit, and possibly whenever it should

trim down when it takes up too much space.

m_size, a size_t, keeps track of how many DataType elements are currently stored &

considered valid inside m_array. Note: this has to be properly initialized and updated each

time the dynamically allocated memory is changed.

m_maxsize, a size_t, denoting how many DataType type objects can fit in total in the

currently allocated memory of the m_array. Note: this has to be properly initialized and

updated each time the dynamically allocated memory is changed, and that generally m_size

m_maxsize.

, will have the following private helper methods:

(16) resize will deallocate the dynamic memory pointed to by m_array and then allocate

enough total memory to fit the size_t count number of elements. Also, the original

m_array data should be carried (copied) over to the newly allocated one.

Note A: When enlarging the m_array container, only the valid ArrayList elements (m_size in

total) should be copied over, and the rest (m_maxsize-m_size in total) should have the

DataType Default ctor value.

Note B: When shrinking down the m_array container, in case the new m_maxsize cannot fit

all the m_size elements of the ArrayList, then the last ones are just discarded. If it can, then

it copies over only the valid ArrayList elements (m_size in total), and the rest (m_maxsizem_size

n total) should have the DataType Default ctor value.

, and will have the following public member functions:

(1) Default Constructor will instantiate a new list object with no valid data. Note: What

needs to be initialized in this case?

(2) Parametrized Constructor will instantiate a new list object, which will hold size_t

count number of elements in total, all of them initialized to have the same value as the

DataType value parameter. Note: Has to properly handle allocation.

(3) Copy Constructor will instantiate a new ArrayList object which will be a separate copy

of the data of the other ArrayList object which is getting copied. Note: Remember Deep and

Shallow object copies.

(4) Destructor will destroy the instance of the ArrayList object. Note: Any allocated

memory pointed-to by m_array has to be deallocated in here.

(5) operator= will assign a new value to the calling ArrayList object, which will be an exact

copy of the rhs ArrayList object. Returns a reference to the calling object to be used for

cascading operator= as per standard practice. Note: Think what needs to happen before

allocating new memory for the new data to be held by the calling object.

(6) First returns a pointer to the first (valid) element of m_array, or NULL if it fails. Note: A

reason for failing can be that the list is empty.

(7) Last returns a pointer to the last (valid) element of m_array, or NULL if it fails. Note: A

reason for failing can be that the list is empty.

(8) Find returns a pointer to the first (valid) element of m_array, which is found to have the

same value as the passed parameter DataType target (the equality operator== as overloaded

in class DataType should be used to check that). If it fails (it does not find the value it

searched for), it returns NULL. Also, it takes in By-Reference a DataType Pointer

parameter, and sets it to the Address of the targets predecessor element. If the search fails,

or if the target element is found to be the first and has no predecessor, previous should be

set to NULL.

(Extra Functionality (not required for 100pt grade): The method also takes in a

DataType Pointer named start, which indicates where it should start searching in the list. If

this is passed as NULL, it denotes to start searching from the first element. Otherwise, this

can be used to start a recursive search in case an element exists twice (otherwise Find will

always return the first elements address).

(9) InsertAfter first finds the DataType element target, and then inserts after it in the list a

new element of the value DataType value. Returns DataType Pointer to the element it just

inserted (or NULL if it failed). Note: Try to think through what you are doing, and sketch out

how its going to work. Think of all possible cases, e.g. inserting in the middle, at the end, in

the start, what happens if m_array already has a size that fits the element, or if it should be

resized to fit the new element, etc.

(10) InsertBefore first finds the DataType element target, and then inserts before it in the

list a new element of the value DataType value. Returns DataType Pointer to the element it

inserted (or NULL if it failed). Note: Try to think through what you are doing, and sketch out

how its going to work. Think of all possible cases, e.g. inserting in the middle, at the end, in

the start, what happens if m_array already has a size that fits the element, or if it should be

resized to fit the new element, etc.

(11) Erase first finds the DataType element target, and then removes it from the list.

Returns a DataType Pointer to the element right after the one it just removed (if the last it

removed was the last in the list, it should return NULL). Note: Try to think through what you

are doing, and sketch out how its going to work. Think of all possible cases, e.g. removing

in the middle, the first element, the last element.

(12) operator[] will allow by-reference accessing of a specific DataType object at index int

position within the allocated m_array. Note: Should not care if the position requested is more

than the m_array size.

(15) size will return the size of the current list. Note: This is the m_size of m_array and not

its m_maxsize, i.e. it is the number of valid DataType entries inside it.

(16) empty will return a bool, true if the list is empty, and false otherwise.

(17) clear will clear the contents of the list, so after its call it will be an empty list object.

Note: Does this need to perform memory deallocation?

as well as a friend function:

(i) operator<< will output (to terminal or file depending on the type of ostream& os object

passed as a parameter to it) the content of the calling ArrayList object. Note: it will do so by

traversing the list and calling the insertion operator<< on the valid DataType elements

contained within it.

Node-based List:

The following header file extract is used to explain the required specifications for the class (the

actual header NodeList.h file is provided and accompanies the Project description):

class NodeList{

friend std::ostream& operator<<(std::ostream& os, //(i)

const NodeList& nodeList);

public:

NodeList(); //(1)

NodeList(size_t count, const DataType& value); //(2)

NodeList(const NodeList& other); //(3)

~NodeList(); //(4)

NodeList& operator= (const NodeList& rhs); //(5)

Node* First(); //(6)

Node* Last(); //(7)

Node* Find(const DataType & target, //(8)

Node * & previous,

const Node * start = NULL);

Node* InsertAfter(const DataType& target, //(9)

const DataType& value);

Node* InsertBefore(const DataType& target, //(10)

const DataType& value);

Node* Erase(const DataType& target); //(11)

DataType& operator[] (size_t position); //(12a)

const DataType& operator[] (size_t position) const; //(12b)

size_t size() const; //(13)

bool empty() const; //(14)

void clear(); //(15)

private:

Node * m_head;

};

The NodeList Class will contain the following private data members:

m_head, a Node class type Pointer, pointing to the Dynamically Allocated Node object

considered as the first element of the list. Note: If the list is empty m_head should be NULL.

,and will have the following public member functions:

(1) Default Constructor will instantiate a new list object with no data (no Nodes). Note:

What needs to be initialized in this case?

(2) Parametrized Constructor will instantiate a new list object, which will hold size_t

count number of elements (Nodes) in total, all of them initialized to hold the same value as

the DataType value parameter. Note: Has to properly handle allocation.

(3) Copy Constructor will instantiate a new list object which will be a separate copy of

the data of the other NodeList object which is getting copied. Note: Remember Deep and

Shallow object copies.

(4) Destructor will destroy the instance of the NodeList object. Note: Any allocated

memory taken up by elements (Nodes) belonging to the list has to be deallocated in here.

(5) operator= will assign a new value to the calling NodeList object, which will be an exact

copy of the rhs NodeList object. Returns a reference to the calling object to be used for

cascading operator= as per standard practice. Note: Think what needs to happen before

allocating new memory for the new data to be held by the calling object.

(6) First returns a pointer to the first element (Node) of the list, or NULL if the list is

empty.

(7) Last returns a Pointer to the last element (Node) of the list, or NULL if the list is

empty.

(8) Find returns a pointer to the first element (Node) of the list, that holds the same value as

passed parameter DataType target (the equality operator== as overloaded in class DataType

should be used to check that). If it fails (it does not find the value it searched for inside a

Node), it returns NULL. Also, it takes in By-Reference a Node Pointer parameter named

previous, and sets it to the Address of the target Nodes predecessor element (also a Node).

If the search fails, or if the target element is found within the first Node of the list and has

no predecessor, previous should be set to NULL.

(Extra Functionality (not required for 100pt grade): The method also takes in a Node

Pointer named start, which indicates where it should start searching in the list. If this is

passed as NULL, it denotes to start searching from the first element (Node). Otherwise, this

can be used to start a recursive search in case an element exists twice (otherwise Find will

always return the first elements address).

(9) InsertAfter first finds the element (a Node) that contains DataType target, and then

inserts after it a new element (a Node) that holds the value DataType value. Returns a Node

Pointer to the element (a Node) it inserted (or NULL if it failed). Note: Try to think through

what you are doing, and sketch out how its going to work. Think of all possible cases, e.g.

inserting in the middle, at the end, in the start, etc.

(10) InsertBefore first finds the element (a Node) that contains DataType target, and then

inserts before it a new element (a Node) that holds the value DataType value. Returns a

Node Pointer to the element (a Node) it inserted (or NULL if it failed). Note: Try to think

through what you are doing, and sketch out how its going to work. Think of all possible

cases, e.g. inserting in the middle, at the end, in the start, etc.

(11) Erase first finds the element (a Node) that contains DataType target, and then removes

it from the list. Returns a Node Pointer to the element (a Node) right after the one it just

removed (if the last it removed was the last Node in the list, it should return NULL). Note:

Try to think through what you are doing, and sketch out how its going to work. Think of all

possible cases, e.g. removing in the middle, the first element, the last element.

(12a,12b) operator[] (const and non-const qualified) will allow by-Reference accessing of a

specific DataType object within a Node at an index size_t position within the list. Note: Since

this is not an Array-based implementation, the size_t position index is a fake index, just an

incremental value such that position=0 corresponds to the first element (a Node) in the list

and each subsequent element corresponds to ++position.

(15) size will return the size of the current list. Note: Since this is not an Array-based

implementation, the function has to traverse the list to find how many elements (Nodes) are

contained within it.

(16) empty will return a bool, true if the list is empty, and false otherwise.

(17) clear will clear the contents of the list, so after its call it will be an empty list object.

Note: Does this need to perform memory deallocation?

as well as a friend function:

(i) operator<< will output (to terminal or file depending on the type of ostream& os object

passed as a parameter to it) the content of the calling NodeList object. Note: it will do so by

traversing the list and calling the insertion operator<< on the valid DataType elements

contained within the lists elements (Nodes).

The DataType.h and DataType.cpp files are provided fully implemented. Also, the ArrayList.h and

NodeList.h header files are provided, and NodeList.h provides a class Node implementation in it as

well. You will create the necessary ArrayList.cpp and NodeList.cpp source files to implement the

range of required functionalities You should also create a source file proj6.cpp which will be a test

driver for your classes