C++

Forum

 
Heap and Priority Queue (Array not storing digit)

Shuruki (56)
This assignment is about Heap and PQ's to sort out jobs inside a printer. I'm far from finishing the assignment but the most important part isn't working. My issue is that nothing is getting stored inside the array. I keep getting crashes and at this point I'm not sure what to do. I notice that my destructor runs right after my "addJob" Function finishes, which is destroying the memory. Which might be why nothing gets stored inside OR I think my implementation of Heap/PQ is wrong.

Functions inside my test.cpp aren't properly done, they are made just to see if something is stored inside.

1. Please check if I created the array correctly [PQtype.cpp / Heap.h/ PQType.h]
2. Am I even using/storing into the array. [Test.cpp "addJob" Function]
3. I'm also new to working with Class Templates, so this adds on to my confusion.



PQType.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
template<class ItemType>
class PQType
{
public:
	PQType(int);
	PQType(const PQType&); // I plan to do a copy constructor but I have no idea how to implement it.
	~PQType();
	void MakeEmpty();
	bool IsEmpty();
	bool IsFull();
	void Enqueue(ItemType newItem);
	void Dequeue(ItemType&);
	

private:
	int length;
	HeapType<ItemType> items;
	int maxItems;
};

#include "pqtype.cpp"



PQType.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
template<class ItemType>
PQType<ItemType>::PQType(int max)
{
	maxItems = max;
	items.elements = new ItemType[maxItems]; //I assume this is correct?
	length = 0;
}

template<class ItemType>
PQType<ItemType>::~PQType()
{
	delete[] items.elements;
}

template<class ItemType>
void PQType<ItemType>::MakeEmpty()
{
	length = 0;
}

template<class ItemType>
bool PQType<ItemType>::IsEmpty()
{
	return (length == 0);
}

template<class ItemType>
bool PQType<ItemType>::IsFull()
{
	return (length == maxItems);
}

template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
	length++;
	items.elements[length - 1] = newItem;
	items.ReheapUp(0, length - 1);
}

template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
	item = items.elements[0];
	items.elements[0] = items.elements[length - 1];
	length--;
	items.ReheapDown(0, length - 1);
}





Heap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
 

template< class  ItemType >
struct  HeapType
{
	void   ReheapDown(int  root, int  bottom);
	void   ReheapUp(int  root, int  bottom);
	void   Swap(ItemType&, ItemType&);

	ItemType* elements; //array to be allocated dynamically

	
};
#include "heap.cpp"



Heap.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 



template< class  ItemType >
void   HeapType<ItemType>::Swap(ItemType& a, ItemType& b)
{
	ItemType temp;
	temp = a;
	a = b;
	b = temp;
}

template< class  ItemType >
void   HeapType<ItemType>::ReheapDown(int root, int  bottom)


{
	int  maxChild;
	int  rightChild;
	int  leftChild;

	leftChild = root * 2 + 1;
	rightChild = root * 2 + 2;
	if (leftChild <= bottom)
	{
		if (leftChild == bottom)
			maxChild = leftChild;
		else
		{
			if (elements[leftChild] <= elements[rightChild])
				maxChild = rightChild;
			else
				maxChild = leftChild;
		}
		if (elements[root] < elements[maxChild])
		{
			Swap(elements[root], elements[maxChild]);
			ReheapDown(maxChild, bottom);
		}
	}
}

template< class  ItemType >
void   HeapType<ItemType>::ReheapUp(int  root, int  bottom)

{
	int  parent;

	if (bottom  > root)
	{
		parent = (bottom - 1) / 2;
		if (elements[parent]  <  elements[bottom])
		{
			Swap(elements[parent], elements[bottom]);
			ReheapUp(root, parent);
		}
	}
}






test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
#include <iostream>
using namespace std;
#include "Heap.h"
#include "PQtype.h"

//enum position { student, ta, instructor };
int showMenu();
void addJob(PQType<int>);
void printJob(PQType<int>&);
void viewJob(PQType<int>);

int main()
{
	int choice;
	PQType<int> j(50);



	do
	{
		choice = showMenu();
		switch (choice)
		{
		case 1: addJob(j);
			break;

		case 2:	printJob(j);
			break;

		case 3: viewJob(j);
			break;
		}
	} while (choice != 4);




	return 0;
}

int showMenu()
{
	int select;

	cout << "Menu\n";
	cout << "========\n";
	cout << "1. Add Job\n";
	cout << "2. Print Job\n";
	cout << "3. View Job\n";
	cout << "4. Exit\n";
	cout << "Enter choice: ";
	cin >> select;
	return select;
}

void addJob(PQType<int> j)
{
	

	if (j.IsFull())
	{
		cout << "There is no more room for new jobs" << endl;
	}

	else
	{
		char selection;
		int jobID;
		cout << "Instructor (I or i), TA (T or t), or Student (S or s)? ";
		cin >> selection;

		if (selection == 's' || selection == 'S')
		{
			jobID = 1;
			j.Enqueue(jobID);
			
		}
		else if (selection == 't' || selection == 'T')
		{
			jobID = 2;
			j.Enqueue(jobID);
			
		}
		else if (selection == 'i' || selection == 'I')
		{
			jobID = 3;
			j.Enqueue(jobID);
			
		}


	}

}

void printJob(PQType<int>& j)
{
	if (j.IsEmpty())
	{
		cout << "There are no jobs to print out" << endl;
	}
	else
	{
		int jobID;
		char job[20];

		j.Dequeue(jobID);

		if (jobID == 1)
		{
			strcpy_s(job, "Student");
		}
		else if (jobID == 2)
		{
			strcpy_s(job, "TA");
		}
		else if (jobID == 3)
		{
			strcpy_s(job, "Instructor");
		}

		cout << "Printing " << job << endl;


	}

}

void viewJob(PQType<int> j)
{
	
	if (j.IsEmpty())
	{
		cout << "There is no more room for new jobs" << endl;
	}

	else
	{
		int jobID;
		char job[20];
		j.Dequeue(jobID);
		if (jobID == 1)
		{
			strcpy_s(job, "Student");
		}
		else if (jobID == 2)
		{
			strcpy_s(job, "TA");
		}
		else if (jobID == 3)
		{
			strcpy_s(job, "Instructor");
		}
		cout << "\nJob #" << job << endl;
	}
}


Last edited on
ne555 (10692)
- make your headers self contained. PQType uses HeadType, so it must include its headers
- use headers guards http://www.cplusplus.com/forum/articles/10627/
- using *.cpp for the template implementation may give you issues with automagic tools
- because you haven't provided the code for PQType copy constructor, it doesn't build correctly
- provide an example input

> I plan to do a copy constructor but I have no idea how to implement it
as you do with any other function, ¿what's your issue?
this would be a requirement as you have a custom destructor. You probably need to make a deep copy.

all may be avoided if you use std::vector instead of raw pointers.
Shuruki (56)
- Thanks for the tip, will be putting them in when I finish the assignment.
-Gotcha
-Not sure what you mean by this, but will definitely keep this in mind
-Got the Copy constructor to work, and so far the program runs pretty nicely but I'm now on my final step.
- Will be posting one on this post
-About the Vectors, you're totally right. A friend in my class used vectors and it worked nicely but I decided not to because I would need to change some stuff inside my Heap/PQ implementations.


---------Outputs--------
Printer queue
=========
1. Add job
2. Print job
3. View jobs
4. Exit
Enter choice: 3

No print jobs in queue.

[menu output]
Enter choice: 2

No print jobs in queue.

[menu output]
Enter choice: 1

Instructor (I or i), TA (T or t), or Student (S or s)? s

[menu output]
Enter choice: 3

job #1: Student

[menu output]
Enter choice: 1

Instructor (I or i), TA (T or t), or Student (S or s)? i

[menu output]
Enter choice: 3

job #2: Instructor
job #1: Student

[menu output]
Enter choice: 1

Instructor (I or i), TA (T or t), or Student (S or s)? t

[menu output]
Enter choice: 3

job #2: Instructor
job #3: TA
job #1: Student

[menu output]
Enter choice: 1

Instructor (I or i), TA (T or t), or Student (S or s)? i

[menu output]
Enter choice: 3

job #2: Instructor
job #4: Instructor
job #3: TA
job #1: Student

[menu output]
Enter choice: 2

Now printing job #2: Instructor

---------------End--------------------------



My issue now is outputting the Job "#" . I noticed the Job "#" is simply the location in the Array where the Job is stored inside. So I decided to make another struct and made two integers. So the best place I could think of to keep track of the Length is inside enqueue but then I ran into a problem.

1
2
3
4
5
6
 
struct Job
{
	int position; // position in the array.
	int jobNum; // Job number

};


1
2
3
4
5
6
7
 
void PQType<ItemType>::Enqueue(ItemType newItem)
{
	length++;
//I want to pass the value of Length onto "position" inside my struct.
	items.elements[length - 1] = newItem;
	items.ReheapUp(0, length - 1);
}


this was my first attempt but it didn't work, was this a proper way?

1
2
3
4
5
6
7
8
 
void PQType<ItemType>::Enqueue(ItemType newItem)
{
//     Job j;
	length++;
//      j.position = length;
	items.elements[length - 1] = newItem;
	items.ReheapUp(0, length - 1);
}


sadly, it kept outputting garbage.
Last edited on
Shuruki (56)
This is an Update. I've now been able to output a reasonable number this time. Can't seem to sort them out properly with their Job "#" though . These are the things I've added.

Note: I am now using a structure array.


1
2
3
4
5
6
 
struct Job
{
	int position; // position in the array.
	int jobNum; // Job number

};




enqueue
1
2
3
4
5
6
7
8
9
 
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
	
	length++;
	items.elements[length - 1].position = length; //I've added this
	items.elements[length - 1].jobNum = newItem;
	items.ReheapUp(0, length - 1);
}



copy constructor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class ItemType>
PQType<ItemType>::PQType(const PQType& cpy)
{

	length = cpy.length;

	items.elements = new Job[maxItems];

	for (int i = 0; i < length; i++)
	{
		items.elements[i].jobNum = cpy.items.elements[i].jobNum; //Job number (1,2,3)
		items.elements[i].position = cpy.items.elements[i].position; // position in array
	}
}



Portion of viewJob function in test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
while (!j.IsEmpty())
		{
			jobID.jobNum = j.Front();
			jobID.position = j.getCount(); //grabbing the count
			

			if (jobID.jobNum == 1)
			{
				strcpy_s(job, "Student");
			}
			else if (jobID.jobNum == 2)
			{
				strcpy_s(job, "TA");
			}
			else if (jobID.jobNum == 3)
			{
				strcpy_s(job, "Instructor");
			}
			cout << "\nJob #" << jobID.position << " " << job << endl;


			j.Dequeue(jobID.jobNum);
		}

Last edited on
ne555 (10692)
> My issue now is outputting the Job "#" .
> I noticed the Job "#" is simply the location in the Array where the Job is stored inside.
¿and what it should be?


¿why is PQType a template if it would store Jobs?

About the copy constructor. The default provided by the compiler would be good enough if you coded a copy-constructor, assignment operator and destructor for HeapType.

> Can't seem to sort them out properly with their Job "#" though
I suppose that you have changed the Reheap functions in HeadType to handle Jobs
Topic archived. No new replies allowed.