In C++

Ordered Priority Que (cpp file, that I need help with) should be implemented by calling methods from the OrderedArrayList.cpp (provided below).

Priority Queue. For this ADT, removal operations always return the object in the queue of highest priority that has been in the queue the longest. That is, no object of a given priority is ever removed as long as the queue contains one or more object of a higher priority. Within a given priority First-In-First-Out (FIFO) order must be preserved.

OrderedArrayList.cpp, The implementation.

PriorityQueue.h, (header file, the declaration for Priority Queue.)

OrderedPQ.h, (Ordered priority queue, A class prototype defined in OrderedPQ.h. A subclass of the pure virtual PriorityQueue class defined in its header file)

-I need help with C++ code for OrderedPQ.cpp - implementation for Ordered Priority Queue.

-Write code for the required public functions in OrderedPQ.h.

-This should be implemented by calling the methods from OrderedArrayList.cpp list class - (provided). Please show explanations/comments for the answers, so I will learn. Thanks.

TEXT FORMAT;

AbstractList.h (header file, the declaration for Abstract list).

#ifndef ABS_LIST_H

#define ABS_LIST_H

/**

* Pure virtual abstract class

*/

#include

class AbstractList

{

public:

/**

* Appends the specified data to the end of this list

* param int data element to insert

* return bool 1 success

*/

virtual bool add(int) = 0;

/**

* Appends the specified data to the list at the

* specified index. Valid indexes are 0 to size.

* @param int index position to insert data

* @param data element to insert

* @return bool success

*/

virtual bool add(int index, int data) = 0;

/**

* Removes all of the Objects from this list leaving

* capacity the same.

*/

virtual void clear() = 0;

/**

* Returns true if this list contains the specified Object

* @param data

* @return bool 1 success

*/

virtual bool contains(int data) = 0;

/**

* Returns the Object at the specified position in this list

* @param index

* @return Object

* @throws invalid_argument if index out of range

*/

virtual int get(int index) = 0;

/**

* Returns the Object at the specified position in this list and

* deletes it from the list

* @param index element to remove

* @throws invalid_argument if index out of range

*/

virtual int remove(int index) = 0;

/**

* Removes all occurences of the Object in this list

* @param data element(s) to remove

* @return 1 success

*/

virtual bool removeAll(int data) = 0;

/**

* Returns the index of the first occurrence of the

* specified Object in this list, or -1 if this list

* does not contain the Object

* @param data element to search for

* @return int position of data if found, else -1

*/

virtual int indexOf(int data) = 0;

/**

* Returns true if this list contains no Objects

* @return bool

*/

virtual bool isEmpty() = 0;

/**

* Returns the number of Objects in this list

* @return int

*/

virtual int size() = 0;

/**

* Trims the capacity of this instance to be the list's

* current size. An application can use this

* operation to minimize the storage of an instance.

*/

virtual void trimToSize() = 0;

//virtual int getCapacity() = 0;

protected:

int currentSize;

};

#endif

------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------------------------------------------------------

OrderedArrayList.h, class prototype defined in OrderedArrayList.h. A subclass of the pure virtual AbstractList class defined in its header file.

#ifndef ORD_ARRLIST_H

#define ORD_ARRLIST_H

#include "AbstractList.h"

class OrderedArrayList : public AbstractList {

private:

int* array;

int capacity;

int currentPos;

void resize() ;

void shiftUp(int index) ;

int getInsertionIndex(int data) ;

void isValidIndex(int index) ;

public:

OrderedArrayList();

OrderedArrayList(int initialCapacity) ;

virtual bool add(int data) ;

virtual bool add(int index, int data) ;

virtual void clear() ;

virtual bool contains(int data) ;

virtual int get(int index) ;

virtual int indexOf(int data) ;

virtual bool isEmpty() ;

virtual int remove(int index) ;

virtual bool removeAll(int data) ;

virtual int size() ;

virtual void trimToSize() ;

// Debug

//virtual int getCapacity() ;

//void print () ;

};

#endif

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

OrderedArrayList.cpp, The implementation.

#include "OrderedArrayList.h"

#include

//#include // Use with debug code

OrderedArrayList::OrderedArrayList() {

currentSize = 0;

currentPos = 0;

array = new int[10];

capacity = 10;

}

OrderedArrayList::OrderedArrayList(int initialCapacity) {

currentSize = 0;

currentPos = 0;

array = new int[initialCapacity];

capacity = initialCapacity;

}

bool OrderedArrayList::add(int data) {

if(currentSize == capacity ) {

resize();

}

int index = getInsertionIndex(data);

// shift down

int pos = currentSize;

while (pos > index) {

array[pos] = array[pos-1];

pos--;

}

array[index] = data;

currentSize++;

return 1;

}

bool OrderedArrayList::add(int index, int data) {

return 0; // return false to not corrupt list

}

void OrderedArrayList::clear() {

currentSize = 0;

}

bool OrderedArrayList::contains(int data) {

return indexOf(data) == -1 ? 0 : 1;

}

int OrderedArrayList::get(int index) {

isValidIndex(index);

return array[index];

}

// Debug code

//int OrderedArrayList::getCapacity() { return capacity; }

int OrderedArrayList::getInsertionIndex(int data) {

// Handle quick cases

if (currentSize == 0) return 0;

if (currentSize == 1) return data

// Linear search : TODO replace with binary search

int index = 0;

while (index = array[index])

index++;

return index;

}

int OrderedArrayList::indexOf(int data) {

bool found = 0;

int index = 0;

while (!found && index

if (array[index] == data) {

found = 1;

break;

}

index++;

}

return found ? index : -1;

}

bool OrderedArrayList::isEmpty() {

return currentSize == 0;

}

void OrderedArrayList::isValidIndex(int index) {

if(index = currentSize) {

throw std::invalid_argument("Index out of range:"+index);

}

}

//Debug code

/*

void OrderedArrayList::print () {

std::cout

for (int i = 0; i

std::cout

}

std::cout

}

*/

int OrderedArrayList::remove(int index) {

isValidIndex(index);

int data = array[index];

shiftUp(index);

currentSize--;

return data;

}

bool OrderedArrayList::removeAll(int data) {

//TODO Find first occurence and last, then shift at once

for (int i = 0; i

if (array[i] == data) {

remove(i);

i--;

}

}

return 1;

}

void OrderedArrayList::resize() {

int *tmp = nullptr;

capacity *= 2;

tmp = new int [capacity];

int i;

for (i = 0 ; i

tmp[i] = array[i];

}

// explicitly initialize remainder

for ( ; i

tmp[i] = 0;

}

// free old array

delete [] array;

array = tmp;

}

void OrderedArrayList::shiftUp(int index) {

isValidIndex(index);

for(int pos = index; pos

array[pos] = array[pos+1];

}

}

int OrderedArrayList::size() {

return currentSize;

}

void OrderedArrayList::trimToSize() {

int *tmp = new int[currentSize];

capacity = currentSize;

for (int i = 0; i

tmp[i] = array[i];

}

delete[] array;

array = tmp;

}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PriorityQueue.h, (header file, the declaration for Priority Queue.)

#ifndef PRIORITY_QUEUE_H

#define PRIORITY_QUEUE_H

/* The PriorityQueue ADT may store objects in any order. However,

removal of objects from the PQ must follow specific criteria.

The object of highest priority that has been in the PQ longest

must be the object returned by the remove() method. FIFO return

order must be preserved for objects of identical priority.

Ranking of objects by priority is determined by natural order.

For this implementation, the lowest number has the highest priority.

All objects inserted into the PQ must implement this interface.

*/

class PriorityQueue

{

protected:

const int DEFAULT_MAX_CAPACITY = 1000;

public:

// Inserts a new object into the priority queue. Returns true if

// the insertion is successful. If the PQ is full, the insertion

// is aborted, and the method returns false.

virtual bool insert(int object) = 0;

// Removes the object of highest priority that has been in the

// PQ the longest, and returns it.

// Throws invalid_argument if the PQ is empty.

// exception error message: "Cannot remove from empty queue"

virtual int remove() = 0;

// Deletes all instances of the parameter obj from the PQ if found, and

// returns true. Returns false if no match to the parameter obj is found.

virtual bool deleteAll(int obj) = 0;

// Returns the object of highest priority that has been in the

// PQ the longest, but does NOT remove it.

// Throws invalid_argument if the PQ is empty.

// exception error message: "Cannot peek from empty queue"

virtual int peek() = 0;

// Returns true if the priority queue contains the specified element

// false otherwise.

virtual bool contains(int obj) = 0;

// Returns the number of objects currently in the PQ.

virtual int size() = 0;

// Returns the PQ to an empty state.

virtual void clear() = 0;

// Returns true if the PQ is empty, otherwise false

virtual bool isEmpty() = 0;

// Returns true if the PQ is full, otherwise false. List based

// implementations should always return false.

virtual bool isFull() = 0;

};

#endif

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

OrderedPQ.h, (Ordered priority queue, A class prototype defined in OrderedPQ.h. A subclass of the pure virtual PriorityQueue class defined in its header file)

#ifndef ORD_PQ_H

#define ORD_PQ_H

#include "PriorityQueue.h"

#include "OrderedArrayList.h"

class OrderedPQ : public PriorityQueue

{

private:

OrderedArrayList *pq;

int findMinIndex() ;

public:

OrderedPQ() ;

OrderedPQ(int capacity) ;

// Inserts a new object into the priority queue. Returns true if

// the insertion is successful. List-based priority queues are

// never full. Other implementations: If the PQ is full, the

// insertion is aborted, and the method returns false.

virtual bool insert(int object) ;

// Removes the object of highest priority that has been in the

// PQ the longest, and returns it.

// Throws invalid_argument if the PQ is empty.

// exception error message: "Cannot remove from empty queue"

virtual int remove() ;

// Deletes all instances of the parameter obj from the PQ if found, and

// returns true. Returns false if no match to the parameter obj is found.

virtual bool deleteAll(int obj) ;

// Returns the object of highest priority that has been in the

// PQ the longest, but does NOT remove it.

// Throws invalid_argument if the PQ is empty.

// exception error message: "Cannot peek from empty queue"

virtual int peek() ;

// Returns true if the priority queue contains the specified element

// false otherwise.

virtual bool contains(int obj) ;

// Returns the number of objects currently in the PQ.

virtual int size() ;

// Returns the PQ to an empty state.

virtual void clear() ;

// Returns true if the PQ is empty, otherwise false

virtual bool isEmpty() ;

// Returns true if the PQ is full, otherwise false. List based

// implementations should always return false.

virtual bool isFull() ;

};

#endif

-I need help with C++ code for OrderedPQ.cpp - implementation for Ordered Priority Queue.

-Write code for the required public functions in OrderedPQ.h.

-This should be implemented by calling the methods from OrderedArrayList.cpp list class - (provided). Please show explanations/comments for the answers, so I will learn. Thanks.

\} void OrderedArraylist: :trimToSize() \{ int *tmp = new int[currentSize]; capacity=currentSize;for(inti=0;i