4 Your Task Download the archive assignment4code.tar.gz from the course website. This archive contains a number of classes which you will have to implement. The comments in the code describe how each function should be implemented. You are not allowed to modify the header files - these will be overwritten by Fitchfork when you submit code for marking.

You are provided with the following classes:

4.1 LinearStructure This class is an interface to which linear structure implementations conform. DynamicArray and LinkedList inherit from this class.

4.2 Node A doubly-linked node class to be used for the linked list implementation.

2 4.3 DynamicArray (20 marks) This class encapsulates a dynamic array. The array grows as more space is needed. See dynamicArray.h for details. Compress and upload your dynamicArray.cpp to the correct upload slot when done. For this task and all the following tasks, your archive must not contain any folders or subfolders. Test the class thoroughly before uploading!

4.4 LinkedList (30 marks) A circular doubly-linked list class. See linkedList.h for details. Compress and upload your linkedList.cpp to the correct upload slot when done. Test the class thoroughly before uploading!

4.5 OrderedContainer This class provides an interface for all types of ordered containers. An ordered container may be implemented in a variety of ways. As an example, a stack may be implemented as either a linked list or an array. The ordered container is given an implementation object (either a linked list or a dynamic array), and data elements are stored in the specified structure. The subclasses (stack, queue, etc.) will have to manipulate their underlying implementations to produce the correct results.

4.6 Stack (15 marks) A stack is a linear structure which does not allow access to arbitrary elements stored in it. The top of the stack is the only entry point of a stack structure, and when an element is added to a stack, it must be stored on top of the stack. When an element is read from the stack, only the top element can be accessed. Removal of elements can also only be applied to the top element. Because of this property, stacks are known as LIFO (last-in-first-out) structures. Compress and upload all your source (.cpp) files to the correct upload slot when done. Both linear data structures (DynamicArray and LinkedList) will be used to test your stack.

4.7 Queue (20 marks) A queue is also a linear structure which does not allow access to arbitrary elements stored in it. A queue has two entry points: front and rear. When an element is added, it is always added at the rear end. When an element is read or removed, it is always read/removed from the front of the queue. Queues are also known as FIFO (first-in-first-out) structures, which means that elements are removed and returned from a queue in the order in which they were inserted. Compress and upload all your source (.cpp) files to the correct upload slot when done. Both linear data structures (DynamicArray and LinkedList) will be used to test your queue.

4.8 PriorityQueue (15 marks) PriorityQueue inherits from Queue. Priority queues recognize the fact that some elements might be more important than others, and return elements with the highest importance first, regardless of the order in which the elements were inserted. For this assignment, you will have to 3 implement your priority queue such that there is a choice between whether the smallest element or the largest element in the queue will be returned. See the comments in the code for more details. Compress and upload all your source (.cpp) files to the correct upload slot when done. Both linear data structures (DynamicArray and LinkedList) will be used to test your priority queue. 5 Implementation Details You are not allowed to change the header files. You will notice that the linear structures have a very limited interface. You will have to think carefully on how you can use this interface to manipulate the structures appropriately in your container classes. You may make the following assumptions for any T: Any T will have at least a default constructor, a copy constructor, an overloaded assignment operator and a destructor. All of the relational operators (==, <, >, <=, etc) will be overloaded for any T. A note on templates: You will notice that the source files (.cpp) are included in the provided header files. This is one way to make linking easier with templates. Your source files must not include the headers remember that template classes are only compiled for concrete types. To test your template classes, all you need to include in your main is the corresponding header.

Given Code:

dynamicArray.h:

#ifndef DYNAMICARRAY_H

#define DYNAMICARRAY_H

#include "linearStructure.h"

template

class DynamicArray;

template

ostream& operator<<(ostream&,DynamicArray&);

/*

Dynamic array.

*/

template

class DynamicArray : public LinearStructure

{

public:

/*The overloaded stream operator for the DynamicArray class. If

an array object is printed that contains the elements a,c,b and m,

with element 'a' at index 0 and element 'm' at index 3 (first to last),

the output MUST be in the following format:

[a,c,b,m]

with no white space or new lines.

It is possible that some of the elements might be null. If this is the

case then the null elements should be indicated with asterisks.

If the array contains the elements a and m,

with element 'a' at index 0 and element 'm' at index 3 (first to last),

the output MUST be in the following format:

[a,*,*,m]

NOTE: if all elements are null, output asterisks. If the array is of size 4,

but containts no elements yet, the output MUST be in the following format:

[*,*,*,*]

*/

friend ostream& operator<< (ostream&,DynamicArray&);

/*

The constructor accepts the initial size of the array.

All elements in the array are initialized to null.

If a size <= 0 is provided, throw an exception message "Invalid size provided"

*/

DynamicArray(int s);

/*

The copy constructor.

*/

DynamicArray(const DynamicArray& other);

/*

The overloaded assignment operator.

*/

DynamicArray& operator=(const DynamicArray& other);

/*

Creates a dynamically allocated deep copy of the object and returns

a pointer to it

*/

virtual DynamicArray* clone();

/*

The destructor.

*/

virtual ~DynamicArray();

/*

Inserts an element at the given index in the array. If

the index is larger than the size of the array, grow

the array to accomodate the index.

Any index >= 0 is valid. For an invalid index, throw an exception message "invalid index".

NOTE: a value can only be inserted at a given index if the

given index does not store a value yet. If the index position

is occupied, all elements from the given index onwards

are shifted one position forward to free the requested position.

Eg: Array object stores [a,c,b,m]. A request is made to insert 'j'

at location '1'. Currently, 'c' is stored there. All elements are shifted

forward: [a,*,c,b,m], and 'j' is put in the now open position '1':

[a,j,c,b,m]. Note that the array had to be resized to accomodate the insertion.

*/

virtual void insert(int index, T element);

/*

Removes and returns the element at the index passed in

as a parameter. All elements from the removed index onwards

are shifted one position backward. Array is not resized. If an element is null,

throw the string "No element found".

*/

virtual T remove(int index);

/*

Returns the element at the index passed in as a parameter.

The element is not removed from the data structure. If an element

is null, throw the string "No element found".

*/

virtual T get(int index) const;

/*

Returns the first non-null element in the structure.

If all elements are null, throw the string "No element found".

*/

virtual const T& getFirst() const;

/*

Returns the last non-null element in the structure.

If all elements are null, throw the string "No element found".

*/

virtual const T& getLast() const;

/*

Returns the index of the first non-null element in the structure.

If all elements are null, throw the string "No element found".

*/

virtual int getIndexFirst() const;

/*

Returns the index of the last non-null element in the structure.

If all elements are null, throw the string "No element found".

*/

virtual int getIndexLast() const;

/*

Returns true if the array contains no elements and

false otherwise.

*/

virtual bool isEmpty();

/*

Removes all of the elements from the array. After this function has

been called on a DynamicArray object, the the array must be empty

(i.e. all elements in the array must be null). The array's current

size remains unchanged.

*/

virtual void clear();

/*

Removes empty spaces between elements by moving all elements to the front.

For example, suppose the following array is given: [*,2,3,*,*,*,0]

After invoking shiftToFront(), all non-null elements should be moved to

the front of the array as follows: [2,3,0,*,*,*,*]

The array's current size must remain unchanged.

The order of the elements must remain unchanged.

*/

void shiftToFront();

protected:

ostream& print(ostream& os);

private:

/*

Use this function to resize the array.

*/

void resize(int newSize); // will not be tested by Fitchfork, but will be useful to you!

/*

An array of pointers to objects of type T.

The elements should be stored in this array.

*/

T ** elements;

/*

The current size of the array. It should be initialized

appropriately in the constructor.

*/

int size;

/*

The number of elements currently contained in the array.

*/

int numElements;

};

#include "dynamicArray.cpp"

#endif

linearStructure.h:

#ifndef LINEARSTRUCTURE_H

#define LINEARSTRUCTURE_H

#include

using namespace std;

template

class LinearStructure;

template

ostream& operator<<(ostream&,LinearStructure&);

template

class LinearStructure

{

public:

/*

Calls print() function to print the data

*/

friend ostream& operator<< (ostream& os,LinearStructure& l);

/*

Creates a dynamically allocated deep copy of the object and returns

a pointer to it.

*/

virtual LinearStructure* clone() = 0;

/*

Virtual destructor

*/

virtual ~LinearStructure(){}

/*

Inserts an element at the given index.

See subclasses for more details.

*/

virtual void insert(int index, T element) = 0;

/*

Removes and returns an element from the index passed

as a parameter. See subclasses for more details.

*/

virtual T remove(int index) = 0;

/*

Returns an element from the index passed

as a parameter. See subclasses for more details.

*/

virtual T get(int index) const = 0;

/*

Returns the first element from the structure.

See subclasses for more details.

*/

virtual const T& getFirst() const = 0;

/*

Returns the last element from the structure.

See subclasses for more details.

*/

virtual const T& getLast() const = 0;

/*

Returns the index of the first element in the structure.

See subclasses for more details.

*/

virtual int getIndexFirst() const = 0;

/*

Returns the index of the last element in the structure.

See subclasses for more details.

*/

virtual int getIndexLast() const = 0;

/*

Returns true if the structure is empty, and false

otherwise.

*/

virtual bool isEmpty() = 0;

/*

Empties out the structure. See subclasses for more details.

*/

virtual void clear() = 0;

protected:

/*

Stream operators are not members of a class and are

therefore not inherited and cannot be overridden as

subclass members. See the implementation of this

class' stream operator below. The print function

in each subclass should be implemented as you would

an overloaded stream operator.

*/

virtual ostream& print(ostream& os) = 0;

};

template

ostream& operator<<(ostream& os,LinearStructure& l)

{l.print(os); return os;}

#endif

main.cpp for testing:

#include

#include "dynamicArray.h"

/*#include "linkedList.h"

#include "stack.h"

#include "queue.h"

#include "priorityQueue.h"*/

using namespace std;

int main() {

// Test your implementation here

cout << " ..::[ Dynamic Array Testing ]::.. " << endl;

DynamicArray arr1(5);

DynamicArray arr2(arr1);

DynamicArray arr3(3);

arr3 = arr2;

arr1.insert(0,1);

arr2.insert(1,2);

arr3.insert(2,3);

cout << arr1 << endl;

cout << arr2 << endl;

cout << arr3 << endl;

cout << "First in arr2: " << arr2.getFirst() << endl;

cout << "Last in arr2: " << arr2.getLast() << endl;

int val = arr1.remove(0);

cout << val << endl;

cout << arr1 << endl;

if(arr1.isEmpty()) cout << "Empty!" << endl;

else cout << "Failure!" << endl;

try { val = arr1.remove(0); }

catch( char const * e ) { cout << e << endl; }

arr3.clear();

if(arr3.isEmpty()) cout << "Empty!" << endl;

else cout << "Failure!" << endl;

cout << arr3 << endl;

for(int i = 0; i < 10; i++)

arr3.insert(i,i);

cout << arr3 << endl;

arr3.insert(15,15);

cout << arr3 << endl;

DynamicArray * aPtr = arr3.clone();

cout << *aPtr << endl;

cout << aPtr->get(15) << endl;

cout << *aPtr << endl;

aPtr->insert(3,-1);

cout << *aPtr << endl;

cout << "First: " << aPtr->getFirst() << endl;

cout << "Last: " << aPtr->getLast() << endl;

aPtr->remove(aPtr->getIndexFirst());

aPtr->remove(aPtr->getIndexLast());

cout << *aPtr << endl;

cout << "First: " << aPtr->getFirst() << endl;

cout << "Last: " << aPtr->getLast() << endl;

delete aPtr;

cout << arr3 << endl;

arr3.shiftToFront();

cout << arr3 << endl;

/////////////////////////////////////////////////////////

cout << " ..::[ Linked List Testing ]::.. " << endl;

/*LinkedList list;

cout << list << endl;

list.insert(0,1);

cout << list << endl;

list.remove(0);

cout << list << endl;

list.insert(0,1);

cout << list << endl;

list.insert(1,2);

cout << list << endl;

list.insert(2,3);

cout << list << endl;

list.insert(1,7);

cout << list << endl;

list.insert(0,7);

cout << list << endl;

list.insert(5,7);

cout << list << endl;

list.remove(2);

cout << list << endl;

list.remove(0);

cout << list << endl;

list.remove(3);

cout << list << endl;

LinkedList list2(list);

LinkedList list3;

list3 = list2;

list.clear();

cout << "Copies: " << endl;

cout << list << endl;

cout << list2 << endl;

cout << list3 << endl;

if(list.isEmpty()) cout << "Yes" << endl;

else cout << "No" << endl;

if(list3.isEmpty()) cout << "No" << endl;

else cout << "Yes" << endl;

Node * node = list3.getLeader();

node->data = 55;

node->prev->data = 33;

cout << "Circular + doubly: " << endl;

cout << list3 << endl;

LinkedList * lPtr = list3.clone();

cout << *lPtr << endl;

cout << lPtr->get(1) << endl;

cout << *lPtr << endl;

delete lPtr;

try {

list3.insert(20, 10);

} catch (const char * e) {

cout << e << endl;

}

try {

list3.remove(10);

} catch (const char * e) {

cout << e << endl;

}

////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////

cout << " ..::[ Stack Testing ]::.. " << endl;

LinkedList ll;

DynamicArray arr(1);

Stack s1(&ll);

Stack s2(&arr);

for(int i = 1; i < 10; i+= 2) {

try {

s1.insert(i);

s2.insert(i*i);

} catch (char const * e) { cout << e << endl;}

}

cout << "LinkedList stack: " << *(s1.getImplementation()) << endl;

cout << "DynamicArray stack: " << *(s2.getImplementation()) << endl;

cout << "LinkedList stack - next: " << s1.next() << endl;

cout << "DynamicArray stack - next: " << s2.next() << endl;

s1.reverse();

s2.reverse();

cout << "Reversed: " << endl;

cout << *(s1.getImplementation()) << endl;

cout << *(s2.getImplementation()) << endl;

cout << "Empty the linkedList stack: " << endl;

while(!s1.isEmpty()) {

cout << s1.remove() << endl;

cout << *(s1.getImplementation()) << endl;

}

cout << "Empty the dynamicArray stack: " << endl;

while(!s2.isEmpty()) {

cout << s2.remove() << endl;

cout << *(s2.getImplementation()) << endl;

}

//////////////////////////////////////////////////////////////

cout << " ..::[ Queue Testing ]::.. " << endl;

Queue q1(&ll);

Queue q2(&arr);

for(int i = 1; i < 10; i+= 2) {

q1.insert(i);

q2.insert(i*i);

}

cout << "LinkedList queue: " << *(q1.getImplementation()) << endl;

cout << "DynamicArray queue: " << *(q2.getImplementation()) << endl;

cout << "LinkedList queue - next: " << q1.next() << endl;

cout << "DynamicArray queue - next: " << q2.next() << endl;

q1.reverse();

q2.reverse();

cout << "Reversed: " << endl;

cout << *(q1.getImplementation()) << endl;

cout << *(q2.getImplementation()) << endl;

cout << "Empty the linkedList queue: " << endl;

while(!q1.isEmpty()) {

cout << q1.remove() << endl;

cout << *(q1.getImplementation()) << endl;

}

cout << "Empty the dynamicArray queue: " << endl;

while(!q2.isEmpty()) {

cout << q2.remove() << endl;

cout << *(q2.getImplementation()) << endl;

}

//////////////////////////////////////////////////////////////

cout << " ..::[ Priority Queue Testing ]::.. " << endl;

PriorityQueue pq1(&ll);

PriorityQueue pq2(&arr);

pq1.insert(9);

pq1.insert(19);

pq1.insert(3);

pq1.insert(6);

pq1.insert(8);

pq1.insert(2);

pq1.insert(5);

cout << "LinkedList priority queue: " << *(pq1.getImplementation()) << endl;

pq2.insert(9);

pq2.insert(19);

pq2.insert(3);

pq2.insert(6);

pq2.insert(8);

pq2.insert(2);

pq2.insert(5);

cout << "DynamicArray priority queue: " << *(pq2.getImplementation()) << endl;

cout << "LinkedList priority queue - next: " << pq1.next() << endl;

cout << "DynamicArray priority queue - next: " << pq2.next() << endl;

pq1.reverse();

pq2.reverse();

cout << "Reversed: " << endl;

cout << "LinkedList priority queue - next: " << pq1.next() << endl;

cout << "DynamicArray priority queue - next: " << pq2.next() << endl;

cout << *(pq1.getImplementation()) << endl;

cout << *(pq2.getImplementation()) << endl;

pq1.insert(99);

pq1.insert(1);

pq2.insert(99);

pq2.insert(1);

cout << "LinkedList priority queue - next: " << pq1.next() << endl;

cout << "DynamicArray priority queue - next: " << pq2.next() << endl;

pq1.reverse();

pq2.reverse();

cout << "Reversed: " << endl;

cout << "LinkedList priority queue - next: " << pq1.next() << endl;

cout << "DynamicArray priority queue - next: " << pq2.next() << endl;

cout << "Empty the linkedList priority queue: " << endl;

while(!pq1.isEmpty()) {

cout << pq1.remove() << endl;

cout << *(pq1.getImplementation()) << endl;

}

cout << "Empty the dynamicArray priority queue: " << endl;

while(!pq2.isEmpty()) {

cout << pq2.remove() << endl;

cout << *(pq2.getImplementation()) << endl;

}*/

return 0;

}