[snippet] [Needs work] Priority List

[Nestharus]

Good Tutorial on Binary Heaps and Priority Queues

library PL /* v1.0.0.1
*************************************************************************************
*
*   Priority List
*
*       i.e.
*           struct Test extends array
*               implement PL
*
*               //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.
*   method remove takes nothing returns nothing
*       -   Removes the node
*
************************************************************************************/
    module PL
        implement BH
        
        private static thistype array n     //next
        private static thistype array p     //previous
        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 n[i]=i
                set p[i]=i
            endif
            set n[p[i]]=m
            set p[m]=p[i]
            set n[m]=i
            set p[i]=m
            return m
        endmethod
        method remove takes nothing returns nothing
            if (0<size) then
                call deallocate()
                if n[this]==p[this] then
                    call t.remove(n[this].value)
                    call delete(n[this].heap)
                else
                    set p[n[this]]=p[this]
                    set n[p[this]]=n[this]
                endif
            endif
        endmethod
    endmodule
endlibrary

 

[Nestharus]

Updated

 

[Bribe]

I recommend shifting these binary structures into the Small Code Snippets
thread. I can do it for you if you want.

 

[Nestharus]

Sure thanks =)

 

[Magtheridon96]

~Opened.

Nes, are you planning on updating this, or are you okay with it in it's current state?
The code looks fine to me and the documentation is okay, so I guess it /can/ be approved.

Or, we can do what you guys were planning on doing over a year ago and move this to the Small Code Snippets section x)

 

[Nestharus]

Graveyard this ; p

This is relatively useless, let's not flood the JASS section with common basic data structures and the many, many flavors of them. A priority list, queue, and stack are very easy to implement using a Binary Heap.