Project A3 20141 - OOP344
Contents
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.
- SANITY NOTE
- You will be writing a number of classes and functions. Please remember to sanitize your code as you go along.
- What is code sanity?
- The idea behind code sanity is to keep the code clean and the logic strong at all times. This has 2 main advantages.
- If your code is logically correct at all times then you can be sure that if there is a problem, it has been caused by the latest set of alterations.
- It makes debugging much much easier both for yourself and for anyone helping you
- So how do I keep my code sane?
- By following these simple steps:
- Keep the code nicely formatted at all times. This makes it easy to see the logical structure of your program at a glance and to follow the logic of it. Experienced programmers do NOT look for lines of code, they look for blocks denoted by indents. Train yourself to do the same.
NOTE: If you are using an editor or environment that makes this hard for you, start by getting a better environment!
Windows and visual studio are an excellent combination and provided for free by Seneca. On Linux, your options are netbeans and sublime. The debugging experience is simpler on Windows for our assignments however.
Also note, on visual studio, you can have the editor automatically format your code nicely by pressing the following combinations in sequence:
CTRL-K, CTRL-D - Do not begin writing the next feature before the last feature is working! This is of paramount importance! By ensuring that your code is working (use the tests, specs, and your common sense!), you can save versions of your assignment at specific points in time and know that if a problem arises, it must be caused by your latest set of changes!
- Use a consistent naming convention for all member variables and another convention for local variables.
This makes it easy for you and for anyone helping you to tell at a glance (ie WITHOUT looking at your header) which variables are local, member, etc...
Too often I see conventions either not used, not used consistently, or mixed. Of the three cases, the third is the worst.
Aim to ALWAYS use consistent naming conventions, whatever they may be.
An easy set of conventions is as follows:- Private/Protected Member Variable/Function
- _underscoreCamelCase
- Public Member Variable/Function
- regularCamelCase
- Local Variable/Function Parameter/Global Function
- regularCamelCase
- Public #Define (ie should be used by external code)
- SCREAMING_CAPS
- Private #Define (ie should only be internally used)
- _UNDERSCORE_SCREAMING_CAPS
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
An IntList is the actual integer linked list class. It manages a sequence of IntListNode. Because it needs to be able to set the next pointer on IntListNode objects, this class may need to be a friend of the IntListNode class (this depends on how you implement these classes).
The exact specs follow:
Internal Variables
- IntListNode* _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
- IntList()
- Default constructor. Should set size to 0 and head to NULL.
- IntList(const IntList& 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! - IntList& operator=(const IntList& src)
- Assignment operator. Should behave similarly to the copy constructor. ADDITIONALLY: Should do NOTHING in the case of self-assignment (ie IntList 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.
- IntListNode* head() const
- Head getter. Returns the current value of the head pointer.
- void push(int 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.
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.