Project A3 20141 - OOP344

Introduction

Our third assignment will have you construct an integer holding linked list, adapt it into a templated linked list, then create an object editor utilizing the list. You will use the testing package linked here(Updated March 26 2014) to test your assignment. The linked lists have automated tests; the rest of the assignment has some automated tests and some visual tests. Please note the filename and test number conveniently provided in the section headers for each required class/function.

Please read this note on code SANITY.

When you are finished the assignment, you will have created the following files:

• intlist.h
• intlist.cpp
• list.h

Part 1: Integer Linked List

Build the classes IntList and IntListNode. Place the headers in intlist.h and the implementation in intlist.cpp. These classes form an integer linked list.

Class: IntListNode, Files: [intlist.h, intlist.cpp], Test: 0

Integer linked list node. Node is considered last in the list if its next pointer is NULL. Note the public and protected sections below. You may need to make IntList a friend of this class.

Recommended Members

• An integer member to hold the node's value.
• A pointer to the next node in the list.

Protected Functions

next

Setter for this node's next member. Accepts a pointer to a node. Does not return anything.

Public Functions

Constructor

Accepts two arguments:

• Integer to initialize node's value. Defaults to a default constructed int.
• Pointer to next node in list. Defaults to NULL.

Copy Constructor

Initializes internal value as a copy of the source's internal value. Sets this object's next to NULL.

Standard Assignment Operator

Assigns source's internal value to the current object's internal value. Sets this object's next to NULL. Does not alter the object in the case of self-assignment. Returns a reference to the current object.

val

Val getter. Const function. Does not accept parameters. Returns internal value.

val

Val setter. Receives an int. Sets internal value to received int. Does not return anything.

next

Next getter. Const function. Does not accept parameters. Returns pointer to the next node.

Class: IntList, Files [intlist.h, intlist.cpp], Test: 0

Integer linked list. Uses IntListNode as a node class.

Recommended members

• Pointer to head node in list
• Current size (number of nodes) of list

Public Functions

size

Size getter. Const function. Does not receive parameters. Should return number of nodes in list.

head

Head getter. Const function. Returns pointer to head node in list.

push

Adds a new node to the end of the list. I'll say that again, END OF THE LIST. Receives an int parameter. The new node's value should be set to the received int.

pop

Destroys the last node in the list. I'll say that again, LAST NODE IN THE LIST. Does not receive any arguments. Does not return anything.

clear

Removes all nodes in the list. Has no effect if the list is empty. Does not accept parameters. Does not return anything.

Constructor

Does not accept parameters. Initializes list to safe empty state.

Standard Assignment Operator

Clears this list of all nodes. Then, refills list with the same number of nodes as in the source list. Value of each new node should equal the value of corresponding node in source list. Should not alter object in the case of self-assignment. Should return a reference to the current object.

Copy Constructor

Initializes object to safe state then copies source list into current list. Similar to assignment operator.

Part 2: Templated Linked List

NOTE: Do NOT start working on this part before finishing part 1 and making sure that it passes all tests!

For this part, you will build the classes List<T> and ListNode in the file list.h. These two classes compose a templated linked list. A lot of the code for these classes is very similar to the code you already wrote for the IntListNode and IntList classes, except that the code is now templated. Therefore, it is suggested that you copy the code that you wrote for those classes and paste it into the list.h file, updating the references to IntListNode and IntList and generally adjusting the code as required.

NOTE: The function signature for ListNode::ListNode, ListNode::val setter, and List::push are different from their IntListNode and IntList counterparts!

Class: ListNode<T>, Files: [list.h], Test: 1

Templated ListNode class. Similar to IntListNode but templated to hold any type.

It is expected that class declaration and definition lie in list.h.

In most implementations, you will need to make the class List<T> a friend of this class to access the protected next setter.

TIP: The syntax for prototyping a templated class is:

 template <typename T> SomeClass;

The exact specs follow and assume that the template:

Internal Variables

T _val

Held value.

ListNode<T>* _next

Pointer to the next node in the list.

Protected Functions

void next(ListNode<T>*)

Next setter. Sets the internally held next pointer to the incoming pointer.

Public Functions

ListNode(const T& v = T(), ListNode<T>* n = NULL)

Constructor. Note the default values. Initializes the internally held value to v and the next pointer to n.

ListNode(const ListNode<T>& src)

Copy constructor. Should initialize the internally held value to src's internally held value. Should initialize next to NULL.

ListNode& operator=(const ListNode<T>& src)

Assignment operator. Should set the internally held value to src's internally held value. Should set next to NULL. Should do NOTHING in the case of self-assignment (ie ListNode<T> x; x = x;). Returns a reference to the current object.

~ListNode()

Destructor. As this node does not allocate any memory, this function can remain empty.

T val() const

Val getter. Returns the value internally held.

void val(const T&)

Val setter. Sets the internally held value to the incoming value.

ListNode<T>* next() const

Next getter. Returns the internally held next pointer.

Class: List<T>, Files [list.h], Test: 1

A templated linked list class. Similar to IntList. Similarly to IntList, because it needs to be able to set the next pointer on ListNode<T> objects, this class may need to be a friend of the ListNode<T> class (this depends on how you implement these classes).

The exact specs follow:

Internal Variables

ListNode<T>* _head

The head of the list. Should be NULL when the list is empty.

int _size

The number of elements currently in the list.

Public Functions

List()

Default constructor. Should set size to 0 and head to NULL.

List(const List<T>& src)

Copy constructor. Should copy the list of nodes managed by src. This means that an entirely new list of nodes must be created, one node for each node managed by src, and the value held by each of those nodes must equal the value held by the corresponding node managed by src. When this constructor is finished, the size of the current list should be the same as the size of src.

TIP: After initializing the current object to a safe and empty state, don't forget that you may call any member function that the current list has!

List<T>& operator=(const List<T>& src)

Assignment operator. Should behave similarly to the copy constructor. ADDITIONALLY: Should do NOTHING in the case of self-assignment (ie List<int> x; x = x;). If taking action, should clear the list of all nodes before creating new ones (make sure that you do NOT leak memory!). Should return a reference to the current object.

int size() const

Size getter. Returns the current value of the size member.

ListNode<T>* head() const

Head getter. Returns the current value of the head pointer.

void push(const T& v)

Adds a new node to the end of the list holding the value v. Should increment size.

void pop()

Destroys the last node in the list. Should do NOTHING if the list is currently empty. Should decrement size if a node was destroyed. NOTE: If a node was destroyed, make sure that ANY POINTERS POINTING TO IT, that your code has access to, are set to NULL.

void clear()

Destroys all nodes in the list. Has no effect if the list is currently empty. When this function is finished, head should point to NULL and size should be 0.

Submission

Please only submit ONCE YOUR CODE SUCCESSFULLY PASSES ALL TESTS! This includes the COMMON SENSE TEST which is the test that you perform yourself on your own code to ensure that it matches with what is required in the spec. Please see your instructor's specific instructions on how to submit.