I am creating a Heap type priority queue using a dynamically sized array. I am aware that vectors would be simpler to implement, but this is a learning exercise for me. Everything works great, but I am having issues only when attempting some Unit testing in visual studio '13. I'm experiencing this error
Here is the source file where I attempt to run the Unit tests:
//Prog1Test.cpp
#include "UnitTest.h"
#include <iostream>
int main()
{
PriorityQueue Q = PriorityQueue();
UnitTest::test1(Q);
UnitTest::test2(Q);
UnitTest::test3(Q);
UnitTest::test4(Q);
return 0;
}
Here is the UnitTest.cpp:
//UnitTest.cpp
#include "UnitTest.h"
#include <cassert>
void UnitTest::test1(PriorityQueue Q)
{
Q.clear();
Q.append('a');
Q.append('b');
assert(Q.size() == 2);
assert(Q.check() == true);
}
void UnitTest::test2(PriorityQueue Q)
{
Q.clear();
Q.append('b');
Q.append('a');
assert(Q.size() == 2);
assert(Q.check() == false);
}
void UnitTest::test3(PriorityQueue Q)
{
Q.clear();
Q.insert('a');
Q.insert('b');
assert(Q.size() == 2);
assert(Q.check() == true);
assert(Q.remove() == 'a');
assert(Q.size() == 1);
}
void UnitTest::test4(PriorityQueue Q)
{
Q.clear();
Q.insert('b');
Q.insert('a');
assert(Q.size() == 2);
assert(Q.check() == true);
assert(Q.remove() == 'a');
assert(Q.size() == 1);
}
Here is the UnitTest header file:
//UnitTest.h
#ifndef UnitTest_H
#define UnitTest_H
#include "PriorityQueue.h"
class UnitTest
{
public:
void test1(PriorityQueue Q);
void test2(PriorityQueue Q);
void test3(PriorityQueue Q);
void test4(PriorityQueue Q);
};
#endif
Here is the PriorityQueue class header:
#ifndef PriorityQueue_H
#define PriorityQueue_H
class PriorityQueue
{
private:
char *pq;
int length;
int nextIndex;
char root;
public:
PriorityQueue();
~PriorityQueue();
char& operator[](int index);
void append(char val);
int size();
void clear();
void heapify();
bool check();
void insert(char val);
char remove();
friend class UnitTest;
};
#endif
here is the priorityqueue.cpp file:
#include<math.h>
#include "PriorityQueue.h"
PriorityQueue::PriorityQueue()
{
pq = new char[0];
this->length = 0;
this->nextIndex = 0;
}
PriorityQueue::~PriorityQueue() {
delete[] pq;
}
char& PriorityQueue::operator[](int index) {
char *pnewa;
if (index >= this->length) {
pnewa = new char[index + 1];
for (int i = 0; i < this->nextIndex; i++)
pnewa[i] = pq[i];
for (int j = this->nextIndex; j < index + 1; j++)
pnewa[j] = 0;
this->length = index + 1;
delete[] pq;
pq = pnewa;
}
if (index > this->nextIndex)
this->nextIndex = index + 1;
return *(pq + index);
}
void PriorityQueue::append(char val) {
char *pnewa;
if (this->nextIndex == this->length) {
this->length = this->length + 1;
pnewa = new char[this->length];
for (int i = 0; i < this->nextIndex; i++)
pnewa[i] = pq[i];
for (int j = this->nextIndex; j < this->length; j++)
pnewa[j] = 0;
delete[] pq;
pq = pnewa;
}
pq[this->nextIndex++] = val;
}
int PriorityQueue::size() {
return this->length;
}
void PriorityQueue::clear() {
delete[] pq;
pq = new char[0];
this->length = 0;
this->nextIndex = 0;
}
void PriorityQueue::heapify() {
char parent;
char root;
char temp;
for (double i = this->length - 1; i >= 0; i--)
{
root = pq[0];
int parentindex = floor((i - 1) / 2);
int leftchildindex = 2 * i + 1;
int rightchildindex = 2 * i + 2;
if (pq[(int)i] <= pq[leftchildindex] && pq[(int)i] <= pq[rightchildindex])
{
pq[(int)i] = pq[(int)i];
}
else if (rightchildindex < this->length && pq[(int)i] > pq[rightchildindex])
{
temp = pq[(int)i];
pq[(int)i] = pq[rightchildindex];
pq[rightchildindex] = temp;
heapify();
}
else if (leftchildindex < this->length && pq[(int)i] > pq[leftchildindex])
{
temp = pq[(int)i];
pq[(int)i] = pq[leftchildindex];
pq[leftchildindex] = temp;
heapify();
}
}
}
void PriorityQueue::insert(char val) {
char *pnewa;
if (this->nextIndex == this->length) {
this->length = this->length + 1;
pnewa = new char[this->length];
for (int i = 0; i < this->nextIndex; i++)
pnewa[i] = pq[i];
for (int j = this->nextIndex; j < this->length; j++)
pnewa[j] = 0;
delete[] pq;
pq = pnewa;
}
pq[this->nextIndex++] = val;
PriorityQueue::heapify();
}
bool PriorityQueue::check() {
char root;
root = pq[0];
for (int i = this->length - 1; i >= 0; i--)
{
if ((int)pq[i]< (int)root)
return false;
}
return true;
}
char PriorityQueue::remove() {
char root = pq[0];
char *qminus;
qminus = new char[this->length];
for (int i = 1; i<this->length; i++)
qminus[i - 1] = pq[i];
pq = qminus;
this->length -= 1;
PriorityQueue::heapify();
return root;
}
Aucun commentaire:
Enregistrer un commentaire