[Snippet] Priority Queue

Level 31
Joined
Jul 10, 2007
Messages
6,306
Good Tutorial on Binary Heaps and Priority Queues

JASS:
library PQ /* v1.0.0.2
*************************************************************************************
*
*   Priority Queue
*
*       i.e.
*           struct Test extends array
*               implement PQ
*
*               //code
*
*           endstruct
*
************************************************************************************
*
*   */uses/*
*
*       */ Table /*       hiveworkshop.com/forums/jass-functions-413/snippet-new-table-188084/
*       */ BH /*          hiveworkshop.com/forums/submissions-414/snippet-minimum-binary-heap-199353/
*
************************************************************************************
*
*   static readonly thistype floor
*       -   The node with the floor value (max or min)
*
*   static method add takes integer value returns thistype
*       -   Adds a new value and returns the node that has it.
*   static method remove takes nothing returns nothing
*       -   Removes the floor value node
*
************************************************************************************/
    module PQ
        implement BH
        
        private static thistype array n     //next
        private static thistype array l     //last
        private static Table t              //table
        private static method onInit takes nothing returns nothing
            set t=Table.create()
        endmethod
        static method operator floor takes nothing returns thistype
            return n[thistype(1).node]
        endmethod
        static method add takes integer v returns thistype
            local thistype i=t[v]
            local thistype m=allocate(v)
            set n[m]=0
            if (0==i) then
                set i=insert(v)
                set t[v]=i
                set l[i]=i
            endif
            set n[l[i]]=m
            set l[i]=m
            return m
        endmethod
        static method remove takes nothing returns nothing
            local thistype m
            local thistype k
            if (0<size) then
                set m=thistype(1).node
                set k=n[m]
                set n[m]=n[k]
                call k.deallocate()
                if 0==n[m] then
                    call t.remove(m.value)
                    call delete(1)
                endif
            endif
        endmethod
    endmodule
endlibrary
 
Last edited:
Top