2.2 Task 2 Priority Queue

Given the behaviour of the queue, (first in, first out), a

priority schema would disrupt the normal sequence of the list given that it should be able

to be reordered such that the priority of events in the queue is reected in the order of

the nodes.

In this task, you will implement p_Queue and eventNode which will produce a priority

queue.

eventNode

-eventIssuer: string

-eventType: string

-issuerPriority: int

-typePriority: int

-eventPriority: int

+next: eventNode*

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

+eventNode(eventIssuer: string, eventType: string, iP: int, tP:int)

+~eventNode()

+getEventIssuer():string

+setEventIssuer(s:string):void

+getEventType():string

+getEventPriority():int

+setEventType(s:string):void

+getIssuerPriority():int

+setIssuerPriority(a:int):void

+getTypePriority():int

+setTypePriority(a:int):void

+print():void

+calculatePriority():void

The class variables are:

eventIssuer: This is an ID for the issuer of the event. There are a number of possible

event Issuers. These are: NPC, PLAYER, ENEMY, AOE. Each reects a particular

type of event that happens in the sequence of play.

eventType: This variable describes the type of event that has to be scheduled.

There are a number of possible types that every kind of issuer can issue. These are:

MOVEMENT, ATTACK, FLEE, UPDATE, CAST, HEAL. These describe a wide

variety of events that can be called into existence through the actions of players,

NPCS, persistent spells and the enemies of the game.

issuerPriority: This is an int describing the priority of the issuer. Dierent types of

issuers have dierent inherent priorities. Obviously this is so that a hierarchy can

be established between the various types of agents in the game world. The base

priority of the issuers are:

-AOE: 4

-PLAYER: 6

-ENEMY: 8

-NPC: 10

typePriority: This is an int describing the priority of the event types. Dierent types

of event have dierent inherent priorities. Obviously this is so that a hierarchy can

be established between the various types of events in the game world. The base

priority of the event types are:

{ MOVEMENT: 1

{ ATTACK: 3

{ FLEE: 5

{ UPDATE: 7

{ CAST: 9

{ HEAL: 11

eventPriority: The nal priority of the event. This is calculated as by multiplying

the issuer priority by the type priority. The lower the number, the higher the

priority of the node, forming a minimum priority queue. Importantly, priority of

the individual characteristics can change, such as certain game modiers external

to this implementation.

next: This is a pointer to the next node in the priority queue.

The class has the following methods:

eventNode: A constructor for the node. It receives a number of arguments that is

used to instantiate a new event.

eventNode: The destructor for the class.

getters and setters: Each of the class variables except for next has a getter and a

setter.

print: A print function for each of the nodes. When called it should print out all of

the node information. The format of which is given below:

Issuer: NPC

Type: FLEE

Issuer Priority: 4

Type Priority: 5

Event Priority: 20

Remember to add newlines after every line and the appropriate spacing between

each word.

calculatePriority: This function updates the event priority of the node based on the

description above.

p_Queue

-front:eventNode *

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

+p_Queue()

+~p_Queue()

+getFront() const: eventNode*

+priorityInsert(eventIssuer: string, eventType: string, iP: int, tP:int):void

+peek():eventNode *

+popFromFront():eventNode *

+printQueue():void

The class has the following variables:

front: A pointer to the front of the priority queue.

The class has the following methods:

p Queue: The class constructor. It initialises a blank queue.

p Queue: The class destructor. It will deallocate all of the nodes left in the queue.

After deleting, it should print out the following message: "Number of nodes deleted:

X" without quotation marks where X indicates the number of nodes deleted in the

process. Be sure to add a newline at the end of this output.

priorityInsert: This is a special type of insert into the queue. It does not merely

insert into the front of the queue. Rather, this will insert into the queue based on

the priority of the node that is being inserted via the arguments passed in. You will

need to determine the priority of the the node being passed in, and then insert it

into the queue based on what its priority is. Keep in mind that the priority queue is

such that the higher priority nodes are kept towards the front and the lower priority

nodes are ordered towards the end. The eect of this, is that the queue is sorted

from highest priority to lowest priority and this is maintained on each insert.

peek: This returns the front of the queue but without modifying the queue in any

way. In this way, it lets us see what the next item removed from the queue will be

without actually modifying the queue.

popFromFront: This removes the node at the front of the queue from the queue and

returns it. Note that this node is not destroyed; merely returned and unlinked.

printQueue: When used, it should be used to print out a number of pertinent details

of the queue: the size, the highest priority and the lowest priority. If the queue is

empty, print "EMPTY QUEUE" with an endline at the end and no quotation marks.

The format of which is as follows:

Number of Nodes: 5

Max Priority: 50

Min Priority: 8

getFront: This returns the front of the queue as a pointer.

For this task, you are only allowed the use of the following libraries: string and iostream.

Also remember that for each slot you must provide a main.cpp, p_Queue.h, p_Queue.cpp, eventNode.h, eventNode.cpp