Heap Priority Queue for to-do list

[Lacy9265]

For this assignment I have to implement a class called HeapPriorityQueue. I have to create a Driver function that will have a to-do list of task with highest priority level. Which every one has the highest priority then the computer will tell the user which task they should do first. Right now I'm having trouble with calling on the ArrayMaxHeap functions to tell the user what task is important. I have included the ArrayMaxHeap.h, Driver.cpp, and the Common.h files.

// ArrayMaxHeap.h
 #ifndef ARRAY_MAX_HEAP_
#define ARRAY_MAX_HEAP_

#include "HeapInterface.h"
#include "PrecondViolatedExcept.h"

template<class ItemType>
class ArrayMaxHeap : public HeapInterface<ItemType>
{
private:
	static const int ROOT_INDEX = 0; // Helps with readibility 
	static const int DEFAULT_CAPACITY = 21; 
	ItemType* items; // Array of heap items
	int itemCount; // Current count of heap items 
	int maxItems; // Max capcity of the heap

	// Returns the array index of the left child
	int getLeftChildIndex(const int nodeIndex) const;

	// Returns the array index of the right child
	int getRightChildIndex(int nodeIndex) const;

	// Returns the array index of the parent node
	int getParentIndex(int nodeIndex) const;

	// Tests whether this node is a leaf
	bool isLeaf(int nodeIndex) const;

	// Converts the semiheap to a heap
	void heapRebuild(int nodeIndex);

	// Creates a heap from from unordered array
	void heapCreate();
public:
	ArrayMaxHeap();
	ArrayMaxHeap(const ItemType someArray[], const int arraySize);
	virtual ~ArrayMaxHeap();


	bool isEmpty() const;
	int getNumberOfNodes() const;
	int getHeight() const;
	ItemType peekTop() const throw(PrecondViolatedExcep);
	bool add(const ItemType& newData);
	bool remove();
	void clear();
};

template<class ItemType>
int ArrayMaxHeap<ItemType>::getLeftChildIndex(const int nodeIndex) const
{
    return (2 * nodeIndex) + 1;
}

template<class ItemType>
int ArrayMaxHeap<ItemType>::getRightChildIndex(const int nodeIndex) const
{
    return (2 * nodeIndex) + 2;
}

template<class ItemType>
int ArrayMaxHeap<ItemType>::getParentIndex(const int nodeIndex) const
{
    return (nodeIndex - 1) / 2;
}

template<class ItemType>
bool ArrayMaxHeap<ItemType>::isLeaf(const int nodeIndex) const
{
    return (getLeftChildIndex(nodeIndex) >= itemCount);
}

template<class ItemType>
void ArrayMaxHeap<ItemType>::heapRebuild(const int subTreeNodeIndex)
{
    if (!isLeaf(subTreeNodeIndex))
    {
        int leftChildIndex = getLeftChildIndex(subTreeNodeIndex);
        int largerChildIndex = leftChildIndex;
        int rightChildIndex = getRightChildIndex(subTreeNodeIndex);
        if (rightChildIndex < itemCount)
        {
            if (items[rightChildIndex].priorityValue > items[largerChildIndex].priorityValue)
                largerChildIndex = rightChildIndex;
        }
        if (items[subTreeNodeIndex].priorityValue < items[largerChildIndex].priorityValue)
        {
            swap(items[largerChildIndex], items[subTreeNodeIndex]);
            heapRebuild(largerChildIndex);
        }
    }
}

template<class ItemType>
void ArrayMaxHeap<ItemType>::heapCreate()
{
    for (int index = itemCount / 2; index >= 0; index--)
    {
        heapRebuild(index);
    }
}

template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap() :itemCount(0), maxItems(DEFAULT_CAPACITY)
{
    items = new ItemType[DEFAULT_CAPACITY];
}
template<class ItemType>
ArrayMaxHeap<ItemType>::ArrayMaxHeap(const ItemType someArray[], const int arraySize) :
    itemCount(arraySize), maxItems(2 * arraySize)
{

    // Allocate the array
    items = new ItemType[2 * arraySize];

    // Copy the given values into the array
    for (int i = 0; i < itemCount; i++)
        items[i] = someArray[i];

    // Reorganize the array into the heap
    heapCreate();
}
template<class ItemType>
ArrayMaxHeap<ItemType>::~ArrayMaxHeap()
{
    delete[] items;
}

template<class ItemType>
bool ArrayMaxHeap<ItemType>::isEmpty() const
{
    return itemCount == 0;
}
template<class ItemType>
int ArrayMaxHeap<ItemType>::getHeight() const
{
    double y = log(itemCount + 1) / log(2);
    return ceil(y);
}
template<class ItemType>
int ArrayMaxHeap<ItemType>::getNumberOfNodes() const
{
    return itemCount;
}

template<class ItemType>
void ArrayMaxHeap<ItemType>::clear()
{
    itemCount = 0;
}
template<class ItemType>
ItemType ArrayMaxHeap<ItemType>::peekTop() const throw(PrecondViolatedExcep)
{
    if (isEmpty())
        throw PrecondViolatedExcep("Attempted peek into an empty heap.");
    return items[0];
}
template<class ItemType>
bool ArrayMaxHeap<ItemType>::add(const ItemType& newData)
{
    // Returns false if the itemCount is equal to the maximum amount of item.
    if (itemCount == maxItems)
        return false;

    // Insert newData into the bottom of the tree
    items[itemCount] = newData;

    // Trickle new item up to the appropriate spot in the tree
    int newDataIndex = itemCount;
    bool inPlace = false;

    // Repeat the process as long as newDataIndex is greater than zero
    // and inPlace is false
    while (newDataIndex > 0 && !inPlace)
    {
        // Get the parent node's index
        int parentIndex = (newDataIndex - 1) / 2;

        // Item is in place if the priority value of the newData is
        // lesser or equal than the parent node's value
        if (items[newDataIndex] <= items[parentIndex])
            inPlace = true;
        else
        {
            // Otherwise, swap newDataIndex's value with the parentIndex
            swap(items[newDataIndex], items[parentIndex]);
            // set newDataIndex to the parentIndex to repeat the process
            newDataIndex = parentIndex;
        }
    }

    // Increase the itemCount
    itemCount++;

    // The process is done, returns true.
    return true;
}

template<class ItemType>
bool ArrayMaxHeap<ItemType>::remove()
{
    bool isSuccessful = false;
    if (!isEmpty())
    {
        items[ROOT_INDEX] = items[itemCount - 1];
        itemCount--;
        heapRebuild(ROOT_INDEX);
        bool isSuccessful = true;
    }
    return isSuccessful;
}



#endif


// Driver.cpp
#include "ArrayMaxHeap.h"
#include "Common.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
    ArrayMaxHeap pqPtr;
    item* p = new item[4];
    p[0].task = "Send a birthday card to Aunt Chris.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper for world history.";
    p[1].priorityValue = 4;
    p[2].task = "Finish reading Chapter 13 of Walls and Mirrors.";
    p[2].priorityValue = 3;
    p[3].task = "Make plans for Saturday Night.";
    p[3].priorityValue = 4;
    for (int i = 0; i < 4; i++)
    {
        bool success = pqPtr->add(p[i]);
        if (!success)
            cout << "Failed to add " << p[i].task << " to the priority queue." << endl;
    }
    for (int i = 0; i < 4; i++)
    {
        try
        {
            cout << "The item witht he largest priority: " >> pqPtr->peekTop().task << endl;
        }
        catch (PrecondViolatedExcep e)
        {
            cout << e.what() << endl;
        }
        cout << "Call remove function" << endl;
        pqPtr->remove();
    }
    system("pause");
    return 0;
}

// Common.h
#ifndef COMMON_H
#define COMMON_H
#include <string>

struct item
{
    int priorityValue;
    std::string task;
};
#endif 

[seeplus]

L239, 247, 254. pqPtr is not a pointer - it is an instantiation of the class ArrayMaxHeap

Shouldn't L227 be:

ArrayMaxHeap<item> pqPtr;

Then L239 becomes (not tried):

bool success = pqPtr.add(p[i]);

and similar for the other uses of pqPtr.

[Lacy9265]

I actually called on the wrong class for this code. I should have called on the HeapPriorityQueue class in the Driver.cpp instead of ArrayMaxQueue. Here is my code for the HeapPriorityQueue. How would I call on this class then. The code includes Heap priority queue cpp and h file.

// HeapPriorityQueue.cpp
#include "HeapPriorityQueue.h"
template<class ItemType>
HeapPriorityQueue<ItemType>::HeapPriorityQueue()
{
    ArrayMaxHeap<ItemType>();
}
template<class ItemType>
bool HeapPriorityQueue<ItemType>::isEmpty() const
{
    return ArrayMaxHeap::isEmpty();
}
template<class ItemType>
bool HeapPriorityQueue<ItemType>::enqueue(const ItemType& newEntry)
{
    return ArrayMaxHeap::add(newEntry);
}
template<class ItemType>
bool HeapPriorityQueue<ItemType>::dequeue()
{
    return ArrayMaxHeap::remove();
}
template<class ItemType>
ItemType HeapPriorityQueue<ItemType>::peekFront() const throw(PrecondViolatedExcep)
{
    try
    {
        return ArrayMaxHeap::peekTop();
    }
    catch (PrecondViolatedExcep e)
    {
        throw PrecondViolatedExcep("Attempted peek into an empty priority queue.");
    }
}

#ifndef HEAP_PRIORITY_QUEUE_
#define HEAP_PRIORITY_QUEUE_

#include <iostream>
#include "ArrayMaxHeap.h"
#include "PriorityQueueInterface.h"
#include "PrecondViolatedExcept.h"

template<class ItemType>
class HeapPriorityQueue : public PriorityQueueInterface<ItemType>,
    private ArrayMaxHeap<ItemType>
{
public:
    HeapPriorityQueue();
    bool isEmpty() const;
    bool enqueue(const ItemType& newEntry);
    bool dequeue();
    ItemType peekFront() const throw(PrecondViolatedExcep);
};

[Lacy9265]

Here is my new code for the Driver.cpp file.

#include "HeapPriorityQueue.h"
#include "Common.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
    HeapPriorityQueue<item> pqPtr;
    item* p = new item[4];
    p[0].task = "Send a birthday card to Aunt Chris.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper for world history.";
    p[1].priorityValue = 4;
    p[2].task = "Finish reading Chapter 13 of Walls and Mirrors.";
    p[2].priorityValue = 3;
    p[3].task = "Make plans for Saturday Night.";
    p[3].priorityValue = 4;
    for (int i = 0; i < 4; i++)
    {

        bool success = pqPtr.enqueue(p[i]);
        if (!success)
            cout << "Failed to add " << p[i].task << " to the priority queue." << endl;
    }
    for (int i = 0; i < 4; i++)
    {
        try
        {
            cout << "The item witht he largest priority: " << pqPtr.peekFront().task << endl;
        }
        catch (PrecondViolatedExcep e)
        {
            cout << e.what() << endl;
        }
        cout << "Call remove function" << endl;
        pqPtr.dequeue();
    }
    system("pause");
    return 0;
}

UPDATE: I have changed all the methods called so they match the ones in HeapPriorityQueue. However I get an error on L8 saying Severity
Error (active) E0322 object of abstract class type "HeapPriorityQueue<item>" is not allowed

[seeplus]

HeapPriorityQueue is derived from PriorityQueueInterface. The error means that the base class has at least one function marked as pure virtual (=0) which hasn't been defined as part of the derived class.

Have a look through the class definition for PriorityQuqueInterface() and make sure that all functions marked as =0 are defined as part of HeapPriorityQueue.

[Lacy9265]

All the functions is PriorityQueueInterface are all marked with =0

#ifndef PRIORITY_QUEUE_INTERFACE_
#define PRIORITY_QUEUE_INTERFACE_

template<class ItemType>
class PriorityQueueInterface
{
public:
	virtual bool isEmpty() const = 0;
	virtual bool add(const ItemType& newEntry) = 0;
	virtual bool remove() = 0;
	virtual ItemType peek() const = 0;
};
#endif

However, still getting the same issue

[seeplus]

As HeapPriorityQueue is derived from the abstract class PriorityQueueInterface, then HeapPriorityQueue has to implement these 4 functions.

Of these 4, only isEmpty() seems to be implemented. Hence HeapPriorityQueue has to implement the remaining 3 virtual functions:

virtual bool add(const ItemType& newEntry) = 0;
virtual bool remove() = 0;
virtual ItemType peek() const = 0;

[Lacy9265]

So what do I do to fix this issue then.

[seeplus]

Implement those 3 functions in HeapPriorityQueue.

[Lacy9265]

Is their another way I've fixing the issue because I have to have the same exact code in HeapPriorityQueue header and cpp file that my book has.

[Lacy9265]

Could I do something like this in the Driver.cpp file

PriorityQueueInterface * pqPtr = new HeapPriorityQueue();

[Lacy9265]

Here is my Driver.cpp file now.

#include "HeapPriorityQueue.h"
#include "Common.h"
#include <iostream>
#include <string>

int main()
{
    PriorityQueueInterface<item> pqPtr = new HeapPriorityQueue<item>();
    item* p = new item[4];
    p[0].task = "Do coding assignment.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper.";
    p[1].priorityValue = 4;
    p[2].task = "Go to the gorcery store.";
    p[2].priorityValue = 4;
    p[3].task = "Watch a movie.";
    p[3].priorityValue = 2;
    for (int i = 0; i < 4; i++)
    {

        bool success = pqPtr.add(p[i]);
        if (!success)
            std::cout << "Failed to add " << p[i].task << " to the priority queue." << std::endl;
    }
    for (int i = 0; i < 4; i++)
    {
        try
        {
            std::cout << "The item witht he largest priority: " << pqPtr.peek().task << std::endl;
        }
        catch (PrecondViolatedExcep e)
        {
            std::cout << e.what() << std::endl;
        }
        std::cout << "Call remove function" << std::endl;
        pqPtr.remove();
    }
    system("pause");
    return 0;
}

On L8 I get there errors.

E0322 object of abstract class type "PriorityQueueInterface<item>" is not allowed:

E0322 object of abstract class type "HeapPriorityQueue<item>" is not allowed:

C2955 'PriorityQueueInterface': use of class template requires template argument list

C2514 'HeapPriorityQueue': class template cannot be constructed

[seeplus]

Is their another way I've fixing the issue

You have to provide overrides for all the pure virtual functions defined in the base class.

If your driver code doesn't use them - then they can be 'dummy' functions which take the required arg(s) and return the required type but doesn't do anything (perhaps a message or something).

Possibly (not tried):

template<class ItemType>
class HeapPriorityQueue : public PriorityQueueInterface<ItemType>,
    private ArrayMaxHeap<ItemType>
{
public:
    HeapPriorityQueue();
    bool isEmpty() const;
    bool enqueue(const ItemType& newEntry);
    bool dequeue();
    ItemType peekFront() const throw(PrecondViolatedExcep);

    // Dummy functions to enable compilation. Replace if needed
    bool add(const ItemType& newEntry) override {return false;}
    bool remove() override {return false;}
    ItemType peek() const override {return {};}

};

[Lacy9265]

Have done what you said @seeplus. Thank you for your help. Now that error has gone away. I'm now getting an error where on L1 of the driver.cpp file it says

LNK2019 unresolved external symbol "public: __thiscall HeapPriorityQueue<struct item>::HeapPriorityQueue<struct item>(void)" (??0?$HeapPriorityQueue@Uitem@@@@QAE@XZ) referenced in function _main

#include "HeapPriorityQueue.h"
#include "Common.h"
#include <iostream>
#include <string>

int main()
{
    HeapPriorityQueue<item> pqPtr;
    item* p = new item[4];
    p[0].task = "Do coding assignment.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper.";
    p[1].priorityValue = 4;
    p[2].task = "Go to the gorcery store.";
    p[2].priorityValue = 4;
    p[3].task = "Watch a movie.";
    p[3].priorityValue = 2;
    for (int i = 0; i < 4; i++)
    {

        bool success = pqPtr.add(p[i]);
        if (!success)
            std::cout << "Failed to add " << p[i].task << " to the priority queue." << std::endl;
    }
    for (int i = 0; i < 4; i++)
    {
        try
        {
            std::cout << "The item witht he largest priority: " << pqPtr.peek().task << std::endl;
        }
        catch (PrecondViolatedExcep e)
        {
            std::cout << e.what() << std::endl;
        }
        std::cout << "Call remove function" << std::endl;
        pqPtr.remove();
    }
    system("pause");
    return 0;
}

Here is my new code for the Driver.cpp

[dutch]

Hurry up, seaman!
Write her code for her old man!

[seeplus]

@lacy9265. I've lost off what is the current state of the code. If you post all of the code that is needed to compile, I'll have a look at it. It's probably something simple that's been missed.

PS You do know that HeapPriorityQueue.cpp can't be a separate compilable unit as it is templated code? Normally templated code is in one file. If you have
HeapPriorityQueue.h and HeapPriorityQueue.cpp then HeapPriorityQueue.h needs to have #include HeapPriorityQueue.cpp at the end (just before the final #endif) - and HeapPriorityQueue.cpp doesn't have #include HeapPriorityQueue.h.

But it's much easier to combine HeapProrityQueue.h and HeapPriorityQueue.cpp into one file (say HeapPriorityQueue.hpp) which is then used in driver.cpp

[Lacy9265]

Okay since my code is too long I'm going to post it in multiple post.

[Lacy9265]

//Driver.cpp
#include "HeapPriorityQueue.h"
#include "Common.h"
#include <iostream>
#include <string>

int main()
{
    
    HeapPriorityQueue<item> pqPtr;
    item* p = new item[4];

    // Set task and priority values to a number 
    p[0].task = "Do coding assignment.";
    p[0].priorityValue = 5;
    p[1].task = "Start the research paper.";
    p[1].priorityValue = 5;
    p[2].task = "Go to the gorcery store.";
    p[2].priorityValue = 3;
    p[3].task = "Watch a movie.";
    p[3].priorityValue = 2;

    // Add task and priority values to queue
    for (int i = 0; i < 4; i++)
    {

        bool success = pqPtr.add(p[i]);
        if (!success)
            std::cout << "Failed to add " << p[i].task << " to the priority queue." << std::endl;
    }

    // Find the task with the largest priority
    for (int i = 0; i < 4; i++)
    {
        try
        {
            std::cout << "The item witht the largest priority: " << pqPtr.peek().task << std::endl;
        }
        catch (PrecondViolatedExcep e)
        {
            std::cout << e.what() << std::endl;
        }

        // Remove funtion with largest priority
        std::cout << "Call remove function" << std::endl; 
        pqPtr.remove();
    }
    system("pause");
    return 0;
}

// HeapPriorityQueue.cpp
//#include "HeapPriorityQueue.h"

template<class ItemType>
inline HeapPriorityQueue<ItemType>::HeapPriorityQueue()
{
    ArrayMaxHeap<ItemType>();
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::isEmpty() const
{
    return ArrayMaxHeap::isEmpty();
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::enqueue(const ItemType& newEntry)
{
    return ArrayMaxHeap::add(newEntry);
}
template<class ItemType>
inline bool HeapPriorityQueue<ItemType>::dequeue()
{
    return ArrayMaxHeap::remove();
}
template<class ItemType>
inline ItemType HeapPriorityQueue<ItemType>::peekFront() const throw(PrecondViolatedExcep)
{
    try
    {
        return ArrayMaxHeap::peekTop();
    }
    catch (PrecondViolatedExcep e)
    {
        throw PrecondViolatedExcep("Attempted peek into an empty priority queue.");
    }
}

[Lacy9265]

//HeapPriorityQueue.h
#ifndef HEAP_PRIORITY_QUEUE_
#define HEAP_PRIORITY_QUEUE_

#include <iostream>
#include "ArrayMaxHeap.h"
#include "PriorityQueueInterface.h"
#include "PrecondViolatedExcept.h"

template<class ItemType>
class HeapPriorityQueue : public PriorityQueueInterface<ItemType>,
    private ArrayMaxHeap<ItemType>
{
public:
    HeapPriorityQueue();
    bool isEmpty() const;
    bool enqueue(const ItemType& newEntry);
    bool dequeue();
    ItemType peekFront() const throw(PrecondViolatedExcep);

    bool add(const ItemType& newEntry) override { return false; }
    bool remove() override { return false; }
    ItemType peek() const override { return {}; }

};

#include "HeapPriorityQueue.cpp"
#endif

//PriorityQueueInterface.h
#ifndef PRIORITY_QUEUE_INTERFACE_
#define PRIORITY_QUEUE_INTERFACE_

template<class ItemType>
class PriorityQueueInterface
{
public:
	virtual bool isEmpty() const = 0;
	virtual bool add(const ItemType& newEntry) = 0;
	virtual bool remove() = 0;
	virtual ItemType peek() const = 0;
};
#endif


//PrecondViolatedException.h
#ifndef PRECOND_VIOLATED_EXCEP_
#define PRECOND_VIOLATED_EXCEP_

#include <stdexcept>
#include <string>

class PrecondViolatedExcep : public std::logic_error
{
public:
	PrecondViolatedExcep(const std::string& message = "")
		: std::logic_error("Precondition Violated Exception: " + message)
	{
	}
}; // end PrecondViolatedExcep 
#endif

//HeapInterface.h
#ifndef HEAP_iNTERFACE_
#define HEAP_INTERFACE_

#include <iostream>

template<class ItemType>
class HeapInterface
{
public:
	// See if the heap is empty
	virtual bool isEmpty() const = 0;

	// Gets the number of nodes in this heap
	virtual int getNumberOfNodes() const = 0;

	// Gets the height of the nodes
	virtual int getHeight() const = 0;

	// Gets the data that is in the top of this heap
	// For the maxHeap the data is the largest value in the heap
	// For the minHeap the data is the smmallest value in the heap
	virtual ItemType peekTop() const = 0;

	// Adds new data to the heap
	virtual bool add(const ItemType& newData) = 0;

	// Removes the data that is at the top of the heap
	virtual bool remove() = 0;

	// Removes all data from the heap
	virtual void clear() = 0;

	// Destroys this heap and frees its assigned memory
	virtual ~HeapInterface() { }
};
#endif 

[seeplus]

See my PS above!