Priority Queue

[praxiiz]

I'm new to these forums, and thought I would make an attempt to post something useful.

Code: Select all

|********************************************************************|
| Module: PriorityQueue  v0.7  by Praxiiz Spectreon                  |
|********************************************************************|
|                                                                    |
| Purpose: This module implements a priority queue for use in        |
|          processing commands.  It is intended for use in a bot     |
|          that needs to react to commands based firstly on priority | 
|          and secondly on the order that the commands were received.|
|                                                                    |
|          Each command shall have five properties: command (string),|
|          target (string), priority (integer), mana requirement     |
|          (integer), and health requirement (integer).              |
|                                                                    |
| To Do:   qRemove, find a generic way to declare multiple queues    |
|                                                                    |
| Notes:   A plugin would be more efficient and appropriate, however,|
|          this was made primarily for an eqemulator server that has |
|          a very tight list of approved plugins.                    |
|                                                                    |
| Usage:  To use this queue in your code please keep in mind the     |
|         following:                                                 |
|         (1) An include statement is needed with the filename used  |
|             to save this code. For example:                        |
|             #include pQueue.inc                                    |
|                                                                    |
|         (2) The queue must be initialized before using it.  This   |
|             is accomplished with the following command:            |
|             /call qInit                                            |
|                                                                    |
|         (3) The following commands are legal:                      |
|                                                                    |
|             qSearch(command, target)                               |
|             qAdd(pItem, pTarget, priority, mana, health)           |
|             qClear                                                 |
|             qPop                                                   |
|             qPeak                                                  |
|                                                                    |
|         (4) When a qPop or qPeak is called, the resulting command  |
|             is placed in the following variables:                  |
|                                                                    |
|              rCommand                                              |
|              rTarget                                               |
|              rPriority                                             |
|              rMana                                                 |
|              rHealth                                               |
|                                                                    |
|********************************************************************|

#define QUEUE_MAX_SIZE 10

|********************************************************************|
| Function: qInit                                                    |
| Purpose:  Initializes the queue and prepares it for use.           |
|                                                                    |
|********************************************************************|
Sub qInit(pItem, pTarget, int pPriority, int pMana, int pHealth)

   |** arrays used as memory for the linked list **|
   /declare nextQueue[QUEUE_MAX_SIZE] int outer 0 
   /declare prevQueue[QUEUE_MAX_SIZE] int outer 0 
   /declare cmdQueue[QUEUE_MAX_SIZE] string outer 
   /declare priorityQueue[QUEUE_MAX_SIZE] int outer 0 
   /declare targetQueue[QUEUE_MAX_SIZE] string outer 
   /declare manaQueue[QUEUE_MAX_SIZE] int outer 0 
   /declare healthQueue[QUEUE_MAX_SIZE] int outer 0

   /declare queueSize int outer 0
 
   |** Linked List Header **|
   /declare listHead int outer 0


   |** Resulting command will be placed in the following variables **|
   /declare rCommand string outer 
   /declare rTarget string outer
   /declare rPriority int outer 0
   /declare rMana int outer 0
   /declare rHealth int outer 0

   /call qClear

/return

|********************************************************************|
| Function: qAdd                                                     |
| Purpose:  Adds an item to the queue, increases queue size and      |
|           adjusts queue pointers.                                  |
|                                                                    |
|********************************************************************|
Sub qAdd(pItem, pTarget, int pPriority, int pMana, int pHealth)
   /if (${queueSize} < QUEUE_MAX_SIZE) {
      /if (${queueSize} > 0) {

         /declare emptySpace int local 0
         |** find some empty space **|
         /declare i int local 1  
         /for i 1 to QUEUE_MAX_SIZE      
            /if (${nextQueue[${i}]} == 0) {
               /varset emptySpace ${i} 
            } else {
               /next i
            }

         |** find the end of the list **|
         /declare endOfList int local 1
         /varset endOfList ${listHead}
         :Link_Loop      
            /if (${nextQueue[${endOfList}]} > 0) {
               /varset endOfList ${nextQueue[${endOfList}]}
               /goto :Link_Loop
            }

         /varset nextQueue[${i}] -1
         /varset nextQueue[${endOfList}] ${i}
         /varset prevQueue[${i}] ${endOfList} 
         /varcalc queueSize ${queueSize}+1 
         /varset cmdQueue[${i}] ${pItem}
         /varset targetQueue[${i}] ${pTarget}
         /varset priorityQueue[${i}] ${pPriority}
         /varset manaQueue[${i}] ${pMana}
         /varset healthQueue[${i}] ${pHealth}

      } else {
      |** Queue is empty, begin at element 1 **|
         /varset listHead 1
         /varset nextQueue[1] -1
         /varset prevQueue[1] -1 
         /varset queueSize 1
         /varset cmdQueue[1] ${pItem}
         /varset targetQueue[1] ${pTarget}
         /varset priorityQueue[1] ${pPriority}
         /varset manaQueue[1] ${pMana}
         /varset healthQueue[1] ${pHealth}
      }
   }

/return

|********************************************************************|
| Function: qClear                                                   |
| Purpose:  Clears the queue by setting the size to 0 and resetting  |
|           queue pointers                                           |
|********************************************************************|
sub qClear

   /declare i int local 1 
   /for i 1 to QUEUE_MAX_SIZE
      /varset nextQueue[${i}] 0       
   /next i
   /varset queueSize 0
   /return

|********************************************************************|
| Function: qPop                                                     |
| Purpose:  Pops an element from the queue, first by priority and    |
|           then by order closest to the front of the queue.         |
|********************************************************************|
Sub qPop
   /if (${queueSize} == 1) {
      /varset rCommand ${cmdQueue[${listHead}]}
      /varset rTarget  ${targetQueue[${listHead}]}
      /varset rPriority ${priorityQueue[${listHead}]}
      /varset rMana ${manaQueue[${listHead}]}
      /varset rHealth ${healthQueue[${listHead}]}
      /varset nextQueue[${listHead}] 0
      /varset queueSize 0 
      /varset listHead 0 
   } else { 
      /if (${queueSize} > 0) {     
            /declare qIterator int local 1
            /declare highestPriority int local 0
            /declare highestPriorityIdx int local 0
            /varset qIterator ${listHead}

            :qPop_List
               /if (${priorityQueue[${qIterator}]} > ${highestPriority}) {
                     /varset highestPriorityIdx ${qIterator}
                     /varset highestPriority ${priorityQueue[${qIterator}]}   
               }     
               /if (${nextQueue[${qIterator}]} > 0) {
                  /varset qIterator ${nextQueue[${qIterator}]}
                  /goto :qPop_List
               }
      
            /varset rCommand ${cmdQueue[${highestPriorityIdx}]}
            /varset rTarget  ${targetQueue[${highestPriorityIdx}]}
            /varset rPriority ${priorityQueue[${highestPriorityIdx}]}
            /varset rMana ${manaQueue[${highestPriorityIdx}]}
            /varset rHealth ${healthQueue[${highestPriorityIdx}]}

            /if (${prevQueue[${highestPriorityIdx}]} > 0) {
               /varset nextQueue[${prevQueue[${highestPriorityIdx}]}] ${nextQueue[${highestPriorityIdx}]}   
            } else {
               /varset listHead ${nextQueue[${highestPriorityIdx}]}
            }
      
            /if (${nextQueue[${highestPriorityIdx}]} > 0) {
                  /varset prevQueue[${nextQueue[${highestPriorityIdx}]}] ${prevQueue[${highestPriorityIdx}]}   
               }
  
            /varset nextQueue[${highestPriorityIdx}] 0
            /varcalc queueSize ${queueSize}-1 
      }
   }
/return

|********************************************************************|
| Function: qPeak                                                    |
| Purpose:  Sets the return variables for an element from the queue, |
|           first by priority and then by order closest to the front |
|           of the queue. Does not remove the item from the queue.   |
|                                                                    |
|********************************************************************|
Sub qPeak
   /if (${queueSize} == 1) {
      /varset rCommand ${cmdQueue[${listHead}]}
      /varset rTarget  ${targetQueue[${listHead}]}
      /varset rPriority ${priorityQueue[${listHead}]}
      /varset rMana ${manaQueue[${listHead}]}
      /varset rHealth ${healthQueue[${listHead}]}
   } else { 
      /if (${queueSize} > 0) {     
            /declare qIterator int local 1
            /declare highestPriority int local 0
            /declare highestPriorityIdx int local 0
            /varset qIterator ${listHead}

            :qPop_List
               /if (${priorityQueue[${qIterator}]} > ${highestPriority}) {
                     /varset highestPriorityIdx ${qIterator}
                     /varset highestPriority ${priorityQueue[${qIterator}]}   
               }     
               /if (${nextQueue[${qIterator}]} > 0) {
                  /varset qIterator ${nextQueue[${qIterator}]}
                  /goto :qPop_List
               }
      
            /varset rCommand ${cmdQueue[${highestPriorityIdx}]}
            /varset rTarget  ${targetQueue[${highestPriorityIdx}]}
            /varset rPriority ${priorityQueue[${highestPriorityIdx}]}
            /varset rMana ${manaQueue[${highestPriorityIdx}]}
            /varset rHealth ${healthQueue[${highestPriorityIdx}]}
      }
   }
/return

|********************************************************************|
| Function: qSearch                                                  |
| Purpose:  Searches for a command based on command string, and      |
|           the target string. Returns 0 if the command was not      |
|           found, 1 if successfully found.                          |
|********************************************************************|
Sub qSearch(pCommand, pTarget)
   /declare resultVal int local 0
   /declare qIterator int local ${listHead}

   :qSearch_list
      /if (${cmdQueue[${qIterator}].Equal[${pCommand}]}) {
         /if (${targetQueue[${qIterator}].Equal[${pTarget}]}) {
            /varset resultVal 1
         }

      }     
      /if (${nextQueue} > 0) {
         /if (${resultVal]} < 1) {
            /varset qIterator ${nextQueue[${qIterator}]}
            /goto :qSearch_List
         }
      }

/return ${resultVal}

[dewey2461]

Would you care to post some general guide lines on how your code would be used?

[praxiiz]

This data structure can be used to hold a queue (or list of sorts) for commands. There are many things that it can be used for, but the purpose that I specifically had in mind when I wrote it is to go along with a loop that processes commands.

The priority queue has several commands:

qAdd command target priority mana health

Adds a command to the queue.

Parameters:
command - A string to hold a command.
target - a string to hold a target
priority - an integer to hold the priority of the command. Higher priority commands should have a higher number here and it is upto you to decide what range of numbers to use. If all commands have the same priority, then this data structure acts like a normal queue.
mana - This is for convenience. Its an integer that you can use to store anything, but it was intended to be used as a way to specify if a command needed a certain amount of mana. (I.E. Spells)
health - This is also for convenience. It is intended to store a health requirement for a command. (For example, cannibalize)

qPeak - this command places the elements of the top priority command in the result variables: rCommand, rTarget, rPriority, rMana, rHealth

qPop - This is the main function to get and remove a command from the queue. This command places the elements of the top priority
command in the result variables: rCommand, rTarget, rPriority, rMana, rHealth. It then removes the command from the queue.

qSearch - Searches for a command in the queue given the command string and target. Returns 0 if the command was not found. Returns 1 if it was found.

qClear - Clears the queue of all commands.

For example:

|** call this once before using the queue **|
/call init

|** add some commands to the queue **|
/call qAdd Cast_Daring MainTank 5 100 0
/call qAdd Superior_Heal MainTank 10 150 0
/call qAdd SOW MainTank 5 150 0
/call qAdd HOT secondaryTank 9 100 0



|** This would place the top command in the result variables: It would not remove the command from the queue. **|
/call qPeak

/echo ${rCommand}

Superior_Heal

/echo ${rTarget}

MainTank

/echo ${rPriority}

10

/echo ${rMana}

150

/echo ${rHealth}
0



|** This place the same command in the result variables, but also
remove it from the queue **|

/call qPop

|** a subsequent call to qPop would place the next highest priority command in the queue:
rCommand HOT
rTarget secondaryTank
rPriority 9
rMana 100
rHealth 0
**|
/call qPop


|** This would check to see if a command was in the queue before sending it to the queue **|

/call qSearch Superior_Heal MainTank
/if (${Macro.Return} < 1) {
/call qAdd Superior_Heal MainTank 10 150 0
}

Here is one use for the priority queue:
The event system of MQ2 uses the /doevents command to process events. It uses a queue, which means that if you call it without specifying an individual event, it will process all queued events in a first-come-first-serve (FCFS) order. If you need a specific event-subroutine called out of order, you would call the /doevents command specifying that event, and you would call it before the regular /doevents command.

The priority queue is an easy way to introduce priorities for events. Instead of having each event-subroutine execute the code for the event, you could have the event-subroutine simply add a command to the priority queue, and return.

The main loop of the bot would then call an appropriate subroutine based on the command. The advantage to this is that the commands are processed in order of priority first, and then FCFS order.

For example, a shaman bot could have an event to buff party members when they send the bot a tell. Sending the bot a tell would trigger an event when the /doevents is executed in the main loop. The event would then add several commands to the queue, one for each buff. If the bot was processing those commands and the main tank needed healing, a heal command that had higher priority than a buff would be added to the queue and it would be the next command processed by the main loop.

[xyilla]

Влад

[xyilla]

242.2

[xyilla]

Bett

[xyilla]

Bett

[xyilla]

McBa

[xyilla]

Deco

[xyilla]

спец

[xyilla]

Falc

[xyilla]

хала

[xyilla]

студ

[xyilla]

клей

[xyilla]

Кедр