Computer Science II Project 8 Solution

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 <cstring> 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,

const ArrayList & arrayList);


//(i)

public:

ArrayList();

ArrayList(size_t count, const DataType & value);

ArrayList(const ArrayList & other);

//(1)
//(2)

//(3)

~ArrayList();

//(4)

ArrayList & operator= (const ArrayList & rhs);

//(5)


DataType * front();


//(6)

DataType * back();

//(7)

DataType * find(const DataType & target,

DataType * & previous,

const DataType * start = NULL);

//(8)

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); const DataType & operator[] (size_t position)



const;


//(12a)

//(12b)

size_t size() const;
bool empty() const;

void clear();

//(13)
//(14)

//(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_maxsize-m_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) front 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) back 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 target’s 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 element’s 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 it’s 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 it’s 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 it’s 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,

const NodeList & nodeList);


//(i)

public:

NodeList();

NodeList(size_t count, const DataType & value);

NodeList(const NodeList & other);

~NodeList();

//(1)

//(2)

//(3)

//(4)

NodeList & operator= (const NodeList & rhs);

//(5)

Node * front();

Node * back();

//(6)

//(7)

Node* find(const DataType & target,
Node * & previous,

const Node * start = NULL);

//(8)

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); const DataType & operator[] (size_t position)



const;


//(12a)

//(12b)

size_t size() const;

bool empty() const;

void clear();

//(13)

//(14)

//(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) front returns a pointer to the first element (Node) of the list, or NULL if the list is empty.

    • (7) back 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 Node’s 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 element’s 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 it’s 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 it’s 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 it’s 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 list’s 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 proj8.cpp which will be a test driver for your classes.

Do not forget to initialize pointers and/or set them to NULL appropriately where needed. Do not forget to perform allocation, dellocation, dellocation-&-reallocation of dynamic memory when needed! Memory accesssing without proper allocation will cause Segmentation Faults. Forgetting to deallocate memory will cause Memory Leaks!

The completed project should have the following properties:
    • Written, compiled and tested using Linux.

    • It must compile successfully on the department machines using Makefile(s), which will be invoking the g++ compiler.

    • The code must be commented and indented properly.

Header comments are required on all files and recommended for the rest of the program. Descriptions of functions commented properly.

    • A one page (minimum) typed sheet documenting your code. This should include the overall purpose of the program, your design, problems (if any), and any changes you would make given more time.

Turn in: Compressed Header & Source files, Makefile(s), and project documentation.

Submission Instructions:
    • You will submit your work via WebCampus

    • Name your code file proj8.cpp

    • If you have header file, name it proj8.h

    • If you have class header and source files, name them as the respective class (ArrayList.h ArrayList.cpp NodeList.h NodeList.cpp) This source code structure is not mandatory, but advised.

    • Compress your:

        1. Source code

        2. Makefile(s)

        3. Documentation

    • Name the compressed folder: PA#_Lastname_Firstname.zip Ex: PA8_Smith_John.zip


Verify: After you upload your .zip file, re-download it from WebCampus. Extract it, compile it and verify that it compiles and runs on the ECC systems.

    • Code that does not compile will be heavily penalized –may even cost you your entire grade–. Executables that do not work 100% will receive partial grade points.

    • It is better to hand in code that compiles and performs partial functionality, rather than broken code. You may use your Documentation file to mention what you could not get to work exactly as you wanted in the given timeframe of the Project.

Late Submission:

A project submission is "late" if any of the submitted files are time-stamped after the due date and time. Projects will be accepted up to 24 hours late, with 20% penalty.