Snippet QueueQueue

[Nestharus]

A tutorial for understanding the QueueQueue

library QueueQueue /* v2.2.6.5
*******************************************************************
*
*   To best understand this data structure, think of a list and then
*   imagine that every node on that list can have a list inside of it
*   and so on. It's also pretty much a tree.
*
*******************************************************************
*
*   API
*
*******************************************************************
*
*   module QueueQueue
*       readonly thistype parent
*       readonly boolean pointer
*       boolean skips
*
*       static method allocate takes nothing returns thistype
*       method deallocate takes nothing returns nothing
*
*       method add takes nothing returns thistype
*       method point takes integer head returns thistype
*       method operator next takes nothing returns thistype
*       method operator in takes nothing returns thistype
*
*   Loop macros
*       //! textmacro QUEUE_QUEUE_HEADER takes STRUCT
*       //! textmacro QUEUE_QUEUE_START_LOOP takes THIS
*       //! textmacro QUEUE_QUEUE_END_LOOP
*       //! textmacro QUEUE_QUEUE_HEADER_B takes STRUCT
*       //! textmacro QUEUE_QUEUE_START_LOOP_B takes THIS
*       //! textmacro QUEUE_QUEUE_END_LOOP_B
*
*   module QueueQueueLoop
*       readonly thistype get
*       readonly thistype skip
*       readonly thistype depthPointer
*       readonly thistype depthNode
*       integer id
*       method start takes nothing returns thistype
*       method end takes nothing returns nothing
*
*******************************************************************
*
*   module QueueQueue
*
*******************************************************************
*
*   readonly thistype next
*       -   Next node
*   readonly thistype in
*       -   Inner node (any given node can have nodes inside of it)
*   readonly thistype parent
*       -   The node that the node is contained inside of.
*   readonly boolean pointer
*       -   This determines whether the node is a pointer or not. Pointers are
*       -   the first node on the QueueQueue (a special pointer called a head, only
*       -   generated with allocate) and nodes made through the point method. Pointers
*       -   are automatically skipped, however their skip option can be set with the
*       -   skips property.
*   boolean skips
*       -   This determines whether or not to skip a pointer. Pointers that are skipped
*       -   are not looped over in loops. This is useful for systems that want to read
*       -   values inside of pointers to see if a pointer's contents should be skipped
*       -   over or not.
*
*   static method allocate takes nothing returns thistype
*       -   Returns the head for the entire object.
*   method deallocate takes nothing returns nothing
*       -   Destroys the entire structure given the head
*
*   method add takes nothing returns thistype
*       -   Adds a cell to the cell. Cells generated in this fashion
*       -   are entirely local to the QueueQueue they were added to, meaninng
*       -   that they can't be pointed to.
*   method point takes integer head returns thistype
*       -   Points a node to a head. Any node allocated with the allocate
*       -   method is a head. Pointers can't point to anything other than the head.
*
********************************************************************
*
*   Loop macros
*
*       A loop macro used for looping through a QueueQueue.
*
*******************************************************************
*
*   Regular loop (looped in right order)
*       //! textmacro QUEUE_QUEUE_HEADER takes STRUCT
*           -   Place at top of the method/function.
*           -
*           -   STRUCT:             Refers to the struct type to loop for.
*       //! textmacro QUEUE_QUEUE_START_LOOP takes THIS
*           -   Place where the loop should start
*           -
*           -   THIS:               Refers to where to start the loop from and also
*           -                       used to store current node inside of for reading.
*           -                       THIS must be a variable, and it is not recommended
*           -                       that the this variable be used.
*       //! textmacro QUEUE_QUEUE_END_LOOP
*           -   Place where the loop should end
*
*   Deep first postorder loop macros (inner before outer, backwards)
*       //! textmacro QUEUE_QUEUE_HEADER_B takes STRUCT
*       //! textmacro QUEUE_QUEUE_START_LOOP_B takes THIS
*       //! textmacro QUEUE_QUEUE_END_LOOP_B
*
*   ---------------------------------------------------------------------
*   -                     
*   -   Example       
*   -                     
*   -   //both are used the same way
*   -   function Test takes QueueQueue q returns nothing
*   -       //header
*   -       //! runtextmacro QUEUE_QUEUE_HEADER("QueueQueue")
*   -
*   -       local QueueQueue node = q      //make a copy
*   -
*   -       //loop
*   -       //! runtextmacro QUEUE_QUEUE_START_LOOP("node")
*   -           //code
*   -           call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, I2S(node))
*   -       //endloop
*   -       //! runtextmacro QUEUE_QUEUE_END_LOOP
*   -   endfunction
*   -
*   ---------------------------------------------------------------------
*
*********************************************************************
*
*   module QueueQueueLoop
*
*       A module that provides methods for looping through a 
*       QueueQueue given an instanced looper.
*
*******************************************************************
*
*   readonly thistype get
*       -   Retrieves the next value in the QueueQueue given a looper.
*   readonly thistype skip
*       -   Skips inner values of the current node and returns next node.
*   readonly thistype depthPointer
*       -   Returns pointer of current depth of loop that stores node. Depth
*       -   pointers are a stack, so depthPointer.depthPointer would go up one.
*   readonly thistype depthNode
*       -   Returns the node stored within the depth pointer.
*   integer id
*       -   For referencing a depth pointer to something. Depth pointers can be recycled
*       -   en masse w/o the user's knowledge, meaning that depth pointers should not be used
*       -   as references for values. It is best to reference the id of a depth pointer.
*
*   method start takes nothing returns thistype
*       -   Creates a new looper for the QueueQueue.
*   method end takes nothing returns nothing
*       -   Destroys a looper for a QueueQueue. Only used when not looping
*       -   through the entire QueueQueue. The looper is automatically destroyed
*       -   if the entire QueueQueue is looped through. This could be useful for value
*       -   searches where looping through the rest of the QueueQueue is pointles.
*
*   ---------------------------------------------------------------------
*   -                     
*   -   Example       
*   -            
*   -   function Test takes QueueQueue q returns nothing
*   -       local QueueQueue looper = q.start()     //create a new looper
*   -       local QueueQueue node
*   -
*   -       loop
*   -           set node = looper.get       //get the next node
*   -           exitwhen node == 0          //exitwhen the node is null
*   -
*   -           //code
*   -           call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, I2S(node))
*   -       endloop
*   -   endfunction
*   -
*   ---------------------------------------------------------------------
*
*******************************************************************/
    module QueueQueue
        private static integer array nc         //next column
        private static integer array nr         //next row
        private static integer array lr         //last row
        private static integer ic=0             //column count
        private static integer array rc         //position recycler
        debug private static boolean array a    //is node allocated
        debug private static integer array rs   //references
        private static boolean array h
        readonly boolean pointer
        readonly thistype parent
        private boolean z
        method operator skips takes nothing returns boolean
            return z
        endmethod
        method operator skips= takes boolean b returns nothing
            debug if (pointer) then
                set z=b
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPTED TO MANIPULATE SKIP OPTION FOR NON POINTER")
            debug endif
        endmethod
        //can only add rows to current object
        static method allocate takes nothing returns thistype
            local thistype this
            //allocate
            if (0==rc[0]) then
                set this=ic+1
                set ic=this
            else
                set this=rc[0]
                set rc[0]=rc[this]
            endif
            debug set a[this]=true
            set nc[this]=0          //next column is 0
            set nr[this]=0          //next row is 0
            set pointer=true        //is a pointer
            set z=true
            set parent=0
            //is head
            debug set h[this]=true
            return this
        endmethod
        method add takes nothing returns thistype
            local thistype n
            debug if (a[this] and (not pointer or h[this])) then
                //allocate
                if (0==rc[0]) then
                    set n=ic+1
                    set ic=n
                else
                    set n=rc[0]
                    set rc[0]=rc[n]
                endif
                debug set a[n]=true
                if (0==nc[this]) then
                    //if nothing to the right, expand
                    set nc[this]=n
                    set lr[this]=n
                else
                    //otherwise, add
                    set nr[lr[this]]=n
                    set lr[this]=n
                endif
                set nr[n]=0         //next row is 0
                set nc[n]=0         //next column is 0
                set n.parent=this
                return n
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPTED TO MANIPULATE NULL NODE")
            debug endif
            debug return 0
        endmethod
        //special add that adds an existing cell
        method point takes integer p returns thistype
            local thistype n
            //if allocated and not a shadowed pointer (hidden)
            debug if (a[this] and (not pointer or h[this]) and h[p]) then
                //allocate
                if (0==rc[0]) then
                    set n=ic+1
                    set ic=n
                else
                    set n=rc[0]
                    set rc[0]=rc[n]
                endif
                debug set a[n]=true
                //add
                if (0==nc[this]) then
                    //if nothing to the right, expand
                    set nc[this]=n
                    set lr[this]=n
                else
                    //otherwise, add
                    set nr[lr[this]] = n
                    set lr[this] = n
                endif
                //expand and point to p
                set nc[n]=p
                set nr[n]=0
                set n.pointer=true
                set n.z=true
                set n.parent=this
                debug if (h[p]) then
                    debug set rs[p]=rs[p]+1
                debug endif
                return n
            debug else
                debug if (not h[p]) then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPTED TO POINT TO NON HEAD")
                debug elseif (a[this]) then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPTED TO MANIPULATE NON HEAD POINTER")
                debug else
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPTED TO MANIPULATE NULL NODE")
                debug endif
            debug endif
            return 0
        endmethod
        method operator next takes nothing returns thistype
            return nr[this]
        endmethod
        method operator in takes nothing returns thistype
            return nc[this]
        endmethod
        method deallocate takes nothing returns nothing
            local thistype array r  //first row on column
            local thistype c = -1   //column
            local thistype n = this //node
            local boolean p = false
            debug if (h[n] and 0==rs[n]) then
                debug set h[n]=false
                debug set a[n]=false
                set rc[n]=rc[0]
                set rc[0]=n
                set pointer=false
                set z=false
                loop
                    if (p) then
                        debug if (h[nc[n]]) then
                            debug set rs[nc[n]]=rs[nc[n]]-1
                        debug endif
                        set n.pointer=false
                        set n.z=false
                        loop
                            //go left until can go down or all the way left
                            exitwhen 0!=nr[n] or 0==c
                            set c=c-1
                            set n=r[c]
                        endloop
                        set n=nr[n]
                        set r[c]=n
                    else
                        if (0==nc[n]) then
                            //if there is nothing to the right, then go down
                            loop
                                //go left until can go down or all the way left
                                exitwhen 0!=nr[n] or 0==c
                                set c=c-1
                                set n=r[c]
                            endloop
                            set n=nr[n]
                            set r[c]=n
                        else
                            //go right
                            set c=c+1       //go to next column
                            set n=nc[n]
                            set r[c]=n      //update next column
                        endif
                    endif
                    exitwhen 0==n
                    set p=n.pointer
                    debug set a[n]=false
                    //destroy
                    set rc[n]=rc[0]
                    set rc[0]=n
                endloop
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE ERROR: ATTEMPT TO DESTROY NON HEAD "+I2S(n))
            debug endif
        endmethod
    endmodule
    //! textmacro QUEUE_QUEUE_HEADER_B takes STRUCT
        local boolean array d_1
        local $STRUCT$ array r_1
        local $STRUCT$ c_1
        local $STRUCT$ n_1
    //! endtextmacro
    //! textmacro QUEUE_QUEUE_START_LOOP_B takes THIS
        set n_1=$THIS$
        set c_1=0
        if (0!=n_1.in) then
            loop
                //go to lowest position
                loop
                    exitwhen d_1[c_1] or (0==n_1.next and 0==n_1.in)
                    set d_1[c_1]=true
                    //first go down, then right
                    if (0!=n_1.in) then
                        set c_1=c_1+1
                        set r_1[c_1]=n_1
                        if (0!=n_1.next) then
                            set c_1=c_1+1
                            set r_1[c_1]=n_1.in
                            set n_1=n_1.next
                        else
                            set n_1=n_1.in
                        endif
                    elseif (0!=n_1.next) then
                        set c_1=c_1+1
                        set r_1[c_1]=n_1
                        set n_1=n_1.next
                    endif
                endloop
                if (not n_1.skips) then
                    set $THIS$=n_1
    //! endtextmacro
    
    //! textmacro QUEUE_QUEUE_END_LOOP_B
                endif
                //go up 1
                set d_1[c_1]=false
                set n_1=r_1[c_1]
                set c_1=c_1-1
                exitwhen 0==n_1
            endloop
        endif
    //! endtextmacro
    //! textmacro QUEUE_QUEUE_HEADER takes STRUCT
        local $STRUCT$ array r_1
        local $STRUCT$ c_1
        local $STRUCT$ n_1
    //! endtextmacro
    //! textmacro QUEUE_QUEUE_START_LOOP takes THIS
        set n_1=$THIS$
        set c_1=-1
        loop
            if (not n_1.skips) then
                set $THIS$=n_1
    //! endtextmacro
    
    //! textmacro QUEUE_QUEUE_END_LOOP
            endif
            if (0==n_1.in) then
                //if there is nothing to the right, then go down
                loop
                    //go left until can go down or all the way left
                    exitwhen 0!=n_1.next or 0==c_1
                    set c_1=c_1-1
                    set n_1=r_1[c_1]
                endloop
                set n_1=n_1.next
                set r_1[c_1]=n_1
            else
                //go right
                set c_1=c_1+1       //go to next column
                set n_1=n_1.in
                set r_1[c_1]=n_1    //update next column
            endif
            exitwhen 0==n_1
        endloop
    //! endtextmacro
    module QueueQueueLoop
        private thistype c
        private thistype n
        private boolean e
        private boolean s
        integer id
        debug private boolean o
        private static thistype array rr //recyler
        private static thistype rc=0    //instance count
        method operator depthNode takes nothing returns thistype
            return n
        endmethod
        method operator depthPointer takes nothing returns thistype
            local thistype h=c
            loop
                exitwhen not h.n.skips
                set h=h.c
            endloop
            if (h==this) then
                return 0
            endif
            return h
        endmethod
        method operator skip takes nothing returns thistype
            local thistype n=c.n
            debug if (o) then
                //first, skip the node
                loop
                    //go left until can go down or all the way left
                    exitwhen 0!=n.next or c.e
                    //destroy
                    set rr[c]=rr[0]
                    set rr[0]=c
                    set c=c.c
                    set n=c.n
                endloop
                set n=n.next
                set c.n=n
                //then find a node that doesn't skip
                loop
                    exitwhen not n.skips
                    if (0==n.in) then
                        //if there is nothing to the right, then go down
                        loop
                            //go left until can go down or all the way left
                            exitwhen 0!=n.next or c.e
                            //destroy
                            set rr[c]=rr[0]
                            set rr[0]=c
                            set c=c.c
                            set n=c.n
                        endloop
                        set n=n.next
                        set c.n=n
                    else
                        //go right
                        if (0==rr[0]) then
                            set rc=rc+1
                            set rc.c=c
                            set c=rc
                        else
                            set rr[0].c=c
                            set c=rr[0]
                            set rr[0]=rr[c]
                        endif
                        set c.id=0
                        set n=n.in
                        set c.n=n
                    endif
                endloop
                if (0==n) then
                    debug set o=false
                    set s=false
                    set e=false
                    set rr[this]=rr[0]
                    set rr[0]=this
                else
                    set c.id=0
                endif
                return n
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE LOOP ERROR: LOOP NOT OPEN")
            debug endif
            debug return 0
        endmethod
        method operator get takes nothing returns thistype
            local thistype n=c.n
            local string es=""
            debug if (o) then
                if (s) then
                    set s=false
                    if (not n.skips) then
                        return n
                    endif
                endif
                loop
                    if (0==n.in) then
                        //if there is nothing to the right, then go down
                        loop
                            //go left until can go down or all the way left
                            exitwhen 0!=n.next or c.e
                            //destroy
                            set rr[c]=rr[0]
                            set rr[0]=c
                            set c=c.c
                            set n=c.n
                        endloop
                        set n=n.next
                        set c.n=n
                    else
                        //go right
                        if (0==rr[0]) then
                            set rc=rc+1
                            set rc.c=c
                            set c=rc
                        else
                            set rr[0].c=c
                            set c=rr[0]
                            set rr[0]=rr[c]
                        endif
                        set c.id=0
                        set n=n.in
                        set c.n=n
                    endif
                    exitwhen not n.skips
                endloop
                if (0==n) then
                    debug set o=false
                    set s=false
                    set e=false
                    set rr[this]=rr[0]
                    set rr[0]=this
                else
                    set c.id=0
                endif
                return n
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE LOOP ERROR: LOOP NOT OPEN")
            debug endif
            debug return 0
        endmethod
        method start takes nothing returns thistype
            local thistype t
            if (0==rr[0]) then
                set rc=rc+1
                set t=rc
            else
                set t=rr[0]
                set rr[0]=rr[t]
            endif
            set t.id=0
            set t.s=true
            set t.c=t
            set t.e=true
            set t.n=this
            debug set t.o=true
            return t
        endmethod
        method end takes nothing returns nothing
            local thistype c=this.c
            debug if (o) then
                debug set o=false
                loop
                    exitwhen c.e
                    set rr[c]=rr[0]
                    set rr[0]=c
                    set c=c.c
                endloop
                set s=false
                set e=false
                set rr[c]=rr[0]
                set rr[0]=c
            debug else
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"QUEUE QUEUE LOOP ERROR: LOOP NOT OPEN")
            debug endif
        endmethod
    endmodule
endlibrary

Textmacro Demo

scope ttt

//remove the _B to see loop forward and add the _B to see loop backward
private module HeadLoop
    //! runtextmacro QUEUE_QUEUE_HEADER_B("thistype")
endmodule
private module StartLoop
    //! runtextmacro QUEUE_QUEUE_START_LOOP_B("node")
endmodule
private module EndLoop
    //! runtextmacro QUEUE_QUEUE_END_LOOP_B()
endmodule
private struct ttt extends array
    //the first node on the QueueQueue does not actually have to be a head
    //as only the entire QueueQueue structure can be destroyed.
    //
    //keep in mind that only heads can be pointed to*
    private static constant boolean SHOW_HEAD = true

    implement QueueQueue
    string v        //represent values in node, shows positioning
    integer id      //depth for spacing
    
    private method test takes nothing returns nothing
        local thistype node = this
        local string s = ""
        local integer i = 0
        //first create the header. The header takes the struct type
        implement HeadLoop
        //next, start the loop. Pass node in to the loop (this)
        //node is overwritten, so don't actually pass in this unless you
        //don't need it
        implement StartLoop
            set s = ""
            //mumbo jumbo for spacing
            //notice that I am just reading the node variable here as it's automatically set
            //by the macro
            if (SHOW_HEAD) then
                set i = node.id-1
            else
                set i = node.id-2
            endif
            loop
                exitwhen i == 0
                set s = s + "            "
                set i = i - 1
            endloop
            set s = s + node.v
            call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, s)
        //end the loop
        implement EndLoop
    endmethod
    
    /****************************************
    *
    *   Looping Forwards
    *
    *****************************************
    *
    *   1
    *       1.1
    *       1.2
    *           1.2.1
    *               1.2.1.1
    *           1.2.2
    *           1.2.3
    *       1.3
    *       1.4
    *   2
    *       2.1
    *       2.2
    *           2.2.1
    *               2.2.1.1
    *           2.2.2
    *           2.2.3
    *       2.3
    *       2.4
    *
    ****************************************/
    
    /****************************************
    *
    *   Looping Backwards
    *
    *****************************************
    *
    *   	2.4
	*       2.3	
    *           2.2.3
    *           2.2.2	
    *               2.2.1.1
    *           2.2.1
	*       2.2
	*       2.1
    *   2	
	*       1.4
	*       1.3	
    *           1.2.3
    *           1.2.2	
    *               1.2.1.1
    *           1.2.1
	*       1.2
	*       1.1
    *   1
    *
    ****************************************/
    private static method run takes nothing returns nothing
        local thistype this = thistype.allocate()
        local thistype r1 = add()
        local thistype r1_r1 = r1.add()
        local thistype r1_r2 = r1.add()
        local thistype r1_r2_r1 = r1_r2.add()
        local thistype r1_r2_r1_r1 = r1_r2_r1.add()
        local thistype r1_r2_r2 = r1_r2.add()
        local thistype r1_r2_r3 = r1_r2.add()
        local thistype r1_r3 = r1.add()
        local thistype r1_r4 = r1.add()
        local thistype r2 = add()
        local thistype r2_r1 = r2.add()
        local thistype r2_r2 = r2.add()
        local thistype r2_r2_r1 = r2_r2.add()
        local thistype r2_r2_r1_r1 = r2_r2_r1.add()
        local thistype r2_r2_r2 = r2_r2.add()
        local thistype r2_r2_r3 = r2_r2.add()
        local thistype r2_r3 = r2.add()
        local thistype r2_r4 = r2.add()
        
        set skips = not SHOW_HEAD
        set id = 1
        set v = "head"
        
        set r1.id = 2
        set r1_r1.id = 3
        set r1_r2.id = 3
        set r1_r2_r1.id = 4
        set r1_r2_r1_r1.id = 5
        set r1_r2_r2.id = 4
        set r1_r2_r3.id = 4
        set r1_r3.id = 3
        set r1_r4.id = 3
        set r2.id = 2
        set r2_r1.id = 3
        set r2_r2.id = 3
        set r2_r2_r1.id = 4
        set r2_r2_r1_r1.id = 5
        set r2_r2_r2.id = 4
        set r2_r2_r3.id = 4
        set r2_r3.id = 3
        set r2_r4.id = 3
        
        set r1.v = "1"
        set r1_r4.v = "1.4"
        set r1_r3.v = "1.3"
        set r1_r2.v = "1.2"
        set r1_r2_r3.v = "1.2.3"
        set r1_r2_r2.v = "1.2.2"
        set r1_r2_r1_r1.v = "1.2.1.1"
        set r1_r2_r1.v = "1.2.1"
        set r1_r1.v = "1.1"
        set r2.v = "2"
        set r2_r4.v = "2.4"
        set r2_r3.v = "2.3"
        set r2_r2.v = "2.2"
        set r2_r2_r3.v = "2.2.3"
        set r2_r2_r2.v = "2.2.2"
        set r2_r2_r1_r1.v = "2.2.1.1"
        set r2_r2_r1.v = "2.2.1"
        set r2_r1.v = "2.1"

        call test()
        call deallocate()
        
        call DestroyTimer(GetExpiredTimer())
    endmethod
    
    private static method onInit takes nothing returns nothing
        call TimerStart(CreateTimer(), 0, false, function thistype.run)
    endmethod
endstruct

endscope

Module Demo

scope ttt

private module HeadLoop
    local thistype looper = start()
    loop
endmodule
private module StartLoop
        set node = looper.get
        exitwhen node == 0
endmodule
private module EndLoop
    endloop
endmodule
private struct ttt extends array
    //the first node on the QueueQueue does not actually have to be a head
    //as only the entire QueueQueue structure can be destroyed.
    //
    //keep in mind that only heads can be pointed to*
    private static constant boolean SHOW_HEAD = false

    implement QueueQueue
    implement QueueQueueLoop
    string v        //represent values in node, shows positioning
    integer id      //depth for spacing
    
    private method test takes nothing returns nothing
        local thistype node = this
        local string s = ""
        local integer i = 0
        //first create the header. The header takes the struct type
        implement HeadLoop
        //next, start the loop. Pass node in to the loop (this)
        //node is overwritten, so don't actually pass in this unless you
        //don't need it
        implement StartLoop
            set s = ""
            //mumbo jumbo for spacing
            //notice that I am just reading the node variable here as it's automatically set
            //by the macro
            if (SHOW_HEAD) then
                set i = node.id-1
            else
                set i = node.id-2
            endif
            loop
                exitwhen i == 0
                set s = s + "            "
                set i = i - 1
            endloop
            set s = s + node.v
            call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, s)
        //end the loop
        implement EndLoop
    endmethod
    
    /****************************************
    *
    *   Looping Forwards
    *
    *****************************************
    *
    *   1
    *       1.1
    *       1.2
    *           1.2.1
    *               1.2.1.1
    *           1.2.2
    *           1.2.3
    *       1.3
    *       1.4
    *   2
    *       2.1
    *       2.2
    *           2.2.1
    *               2.2.1.1
    *           2.2.2
    *           2.2.3
    *       2.3
    *       2.4
    *
    ****************************************/
    
    /****************************************
    *
    *   Looping Backwards
    *
    *****************************************
    *
    *   	2.4
	*       2.3	
    *           2.2.3
    *           2.2.2	
    *               2.2.1.1
    *           2.2.1
	*       2.2
	*       2.1
    *   2	
	*       1.4
	*       1.3	
    *           1.2.3
    *           1.2.2	
    *               1.2.1.1
    *           1.2.1
	*       1.2
	*       1.1
    *   1
    *
    ****************************************/
    private static method run takes nothing returns nothing
        local thistype this = thistype.allocate()
        local thistype r1 = add()
        local thistype r1_r1 = r1.add()
        local thistype r1_r2 = r1.add()
        local thistype r1_r2_r1 = r1_r2.add()
        local thistype r1_r2_r1_r1 = r1_r2_r1.add()
        local thistype r1_r2_r2 = r1_r2.add()
        local thistype r1_r2_r3 = r1_r2.add()
        local thistype r1_r3 = r1.add()
        local thistype r1_r4 = r1.add()
        local thistype r2 = add()
        local thistype r2_r1 = r2.add()
        local thistype r2_r2 = r2.add()
        local thistype r2_r2_r1 = r2_r2.add()
        local thistype r2_r2_r1_r1 = r2_r2_r1.add()
        local thistype r2_r2_r2 = r2_r2.add()
        local thistype r2_r2_r3 = r2_r2.add()
        local thistype r2_r3 = r2.add()
        local thistype r2_r4 = r2.add()
        
        set skips = not SHOW_HEAD
        set id = 1
        set v = "head"
        
        set r1.id = 2
        set r1_r1.id = 3
        set r1_r2.id = 3
        set r1_r2_r1.id = 4
        set r1_r2_r1_r1.id = 5
        set r1_r2_r2.id = 4
        set r1_r2_r3.id = 4
        set r1_r3.id = 3
        set r1_r4.id = 3
        set r2.id = 2
        set r2_r1.id = 3
        set r2_r2.id = 3
        set r2_r2_r1.id = 4
        set r2_r2_r1_r1.id = 5
        set r2_r2_r2.id = 4
        set r2_r2_r3.id = 4
        set r2_r3.id = 3
        set r2_r4.id = 3
        
        set r1.v = "1"
        set r1_r4.v = "1.4"
        set r1_r3.v = "1.3"
        set r1_r2.v = "1.2"
        set r1_r2_r3.v = "1.2.3"
        set r1_r2_r2.v = "1.2.2"
        set r1_r2_r1_r1.v = "1.2.1.1"
        set r1_r2_r1.v = "1.2.1"
        set r1_r1.v = "1.1"
        set r2.v = "2"
        set r2_r4.v = "2.4"
        set r2_r3.v = "2.3"
        set r2_r2.v = "2.2"
        set r2_r2_r3.v = "2.2.3"
        set r2_r2_r2.v = "2.2.2"
        set r2_r2_r1_r1.v = "2.2.1.1"
        set r2_r2_r1.v = "2.2.1"
        set r2_r1.v = "2.1"

        call test()
        call deallocate()
        
        call DestroyTimer(GetExpiredTimer())
    endmethod
    
    private static method onInit takes nothing returns nothing
        call TimerStart(CreateTimer(), 0, false, function thistype.run)
    endmethod
endstruct
endscope

Data

1
1.1
1.2
1.2.1
1.2.1.1
1.2.2
1.2.3
1.3
1.4
2
2.1
2.2
2.2.1
2.2.1.1
2.2.2
2.2.3
2.3
2.4

Looped over forwards

1
	1.1
	1.2
		1.2.1
			1.2.1.1
		1.2.2
		1.2.3
	1.3
	1.4
2
	2.1
	2.2
		2.2.1
			2.2.1.1
		2.2.2
		2.2.3
	2.3
	2.4

Looped over backwards

	2.4
	2.3	
		2.2.3
		2.2.2	
			2.2.1.1
		2.2.1
	2.2
	2.1
2	
	1.4
	1.3	1.2.3
		1.2.2	
			1.2.1.1
		1.2.1
	1.2
	1.1
1

 

[Nestharus]

Tutorial

Spoiler

Given the complexity of what can be done and how to work with the QueueQueue structure, a tutorial is necessary.

A QueueQueue is like a multi dimensional queue. Rather than always having to add a node to the end of it, a node can be added anywhere, but nodes aren't added to the current queue but an inner queue.

If you were to have a set of nodes on a queue-

1
2
3
4
5

Each node could point to another set of nodes.

1
    6,7,8,9,10
2
    11,12,13,14,15
3
    16,17,18,19,20
4
    21,22,23,24,25
5
    26,27,28,29,30

So, the first queue (vertical) would be the nodes 1-5. Node 1 would contain 6-10, node 2 would contain 11-15, etc.

1,2,3,4,5

1: 6,7,8,9,10
2: 11,12,13,14,15
3: 16,17,18,19,20
4: 21,22,23,24,25
5: 26,27,28,29,30

Remember that any node can contain further nodes, so the data structure could get rather complex.

1,2,3,4,5

1: 6,7,8,9,10
2: 11,12,13,14,15
3: 16,17,18,19,20
4: 21,22,23,24,25
5: 26,27,28,29,30

6: 31,32,33
7: 34,35,36
8: 37,38,39,40
9: 41,42
10: 43,44,45,46

etc, etc

Example

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

In reality, the first 5 nodes would be contained in a special node called a head.

6 (head)
    1
    2
    3
    4
    5

This data structure is interpreted as a list of inner nodes of an outer node being the properties of that outer node. For example

hero
    inventory
        item1
        item2
        item3
        item4
        item5
        item6
    location
        x
        y
    facing
    states
        life
        mana
    level

The properties of the hero would be inventory, location, facing, states, and level. The hero node itself has no value, it just points to other things.

hero
    inventory
    location
    facing
    states

The other properties listed are not properties of the hero, but rather properties of whatever their parent node is. For example, the properties of an inventory are the 6 items it can have.

inventory
    item1
    item2
    item3
    item4
    item5
    item6

And from here, items can have many properties of their own like charges and gold cost.

If a hero has an inventory and that inventory can have 6 items, then that hero can have 6 items.

When looping through this structure (getting all of the values in the right order), you first read the object, then its inner properties.

So for example, the hero would be read like this-

hero
inventory
item1
item2
item3
item4
item5
item6
location
x
y
facing
states
life
mana
level

Not like this

hero
inventory
location
facing
states

And keep in mind that the actual nodes directly inside of the hero are

inventory
location
facing
states

So, this means that when moving on from a node, you go right before you go down.

read hero, go right (inventory), go right (item1), go down.

hero->inventory->item1
                 item2
                 item3
                 item4
                 item5
                 item6

At item6, you can't go down anymore, so you have to go left. None of them items point back to the inventory and the inventory only points to item1, so you have to actually store row positions into an array of columns.

In the above example-

hero        inventory        item1
                             item2
                             item3
                             item4
                             item5
                             item6

So, for column 1, hero would be stored. For column 2, inventory would be stored. Column 3 would have item 6 stored at the end, but you wouldn't go beyond column 3.

To go left, if using an array, you just subtract one from the current column.

//go right
set column[currentColumn] = node        //store the node
set currentColumn = currentColumn + 1 //go right

So going right from the hero would store the hero node and then go right.

Because a node in a QueueQueue can have anything inside of it, it can also point to other nodes. Keep in mind that other nodes point down and right, and only the node plus whatever is right of it would be wanted, so for simplicity, only heads should be pointed to.

So for example, adding hero to player.

player
    heroPointer
        hero

The reason for the seemingly useless pointer (heroPointer) is because any node has a list inside of it. If hero were to be stored into player directly, then something else pointing to hero would also point to everything underneath that hero (in this case, other properties of the player).

For example-

player
    hero
    resource
        gold
        lumber

commander
    hero

In the player list, hero points both right and down. Underneath hero is the resource property. This means that when commander points to hero, it'll end up looping through the hero and all of its properties and then* everything underneath hero. Furthermore, if commander were to have properties under hero, it'd end up breaking because hero can't point downwards to 2 different things.

player
    hero
    resource
        gold
        lumber

commander
    hero
    power

This attempts to make hero point down to both resource and power. Given commander is linked afterwards, it'll break the player and make the structures look more like this.

player
    hero
    power

commander
    hero
    power

A pointer can't point to multiple things*.


In the end, looping through a QueueQueue will turn out like this.

//remember that the rows, column, and node need to be stored
local thistype array r    //first row on column
local thistype c = 0      //column
local thistype n = this   //node
loop
    //remember to first go right, then down*
    //when down, go left
    if (n.in == 0) then
        //if there is nothing to the right, then go down
        loop
            //go left until can go down or all the way left
            exitwhen n.next != 0 or c == 0
            set c = c - 1
            set n = r[c]
        endloop
        set n = n.next
        set r[c] = n
    else
        //go right
        set c = c + 1   //go to next column
        set n = n.in
        set r[c] = n    //update next column
    endif

    //exit when the current node is null
    exitwhen n == 0

    //remember that pointers don't have values! skip them.
    if (not n.pointer) then
        //code
    endif
endloop

QueueQueue contains macros and modules to help make looping through the structure easier.


A QueueQueue is primarily useful for creating dynamic objects or frames for objects. In a save/load code for example, every little piece that can be put into that code refers to an object. Most save/load codes don't do this, rather just taking a set of maximal values. However, taking a set of maximal values is a bad practice because the overall data sets can change.

Recall that items have different maximums. If a save/load code were to have 6 positions for items and were to save the charges of those items, how on earth would it know the maximum charge for each item without just making a generic charge for all items?

With dynamic objects come dynamic codes, where the maximums for every given item are known.

Given 6 items and a biggest item charge of 300

Item type 1: 60 charges max
Item type 2: 0 charges max
Item type 4: 30 charges max
Item type 5: 45 charges max
Item type 6: 0 charges max

A static save/load code would make enough space to store 300 charges, which bloats the code up in almost all cases (notice item 2 and 6 have maxes of 0 charges).

A dynamic save/load code, which is possible with this structure, would know the maximum charges of each item and be able to read them out.

Recall that save/load codes have a static list. Your common save/load code stores the hero and resources, which turns into the 6 items, gold, lumber, etc mess. With a QueueQueue, it'd turn into literally Hero and Resources (all of the properties, some of them being dynamic, would be within the Hero and Resources).

If every single possible property was stored for a set of data, then the save/load code can pick and choose what it wants. Later, the data can be interpreted based on the objects.

For example, if there were 10 different items all with varying charges, you'd only pick the 6 items and their properties for the save/load code.

1   
2   (pick)
3   
4   (pick)
5   (pick)
6   
7   (pick)
8   
9   (pick)
10  (pick)

So notice that the QueueQueue object has 10 objects in it with different properties. A new object is generated from the base objects based on the values passed in. In this case, a 2, 4, 5, 7, 9, and 10 were passed in, so only those objects were taken out of the first and put into the second.

2
4
5
7
9
10

When reading out of the code, the 2,4,5,7,9, and 10 would be read out. Remember that QueueQueue goes right before it goes left, so it'd read the 2, then it'd read all properties inside* of that 2. This leads to dynamic save/load codes that store a static set of objects rather than a static set of data, and keep in mind that most data in a save/load code is inside of a hero, so almost all of the data for these types of save/load codes can be entirely dynamic (one hero might have pets, another might have an inventory of 4 items, and etc).

 

[tooltiperror]

name a realistic wc3 scenario of me using this.

 

[Nestharus]

save/load system ;P

This is looping through the QueueQueue and writing it into a save/load code

	2.4
	2.3	
		2.2.3
		2.2.2	
			2.2.1.1
		2.2.1
	2.2
	2.1
2	
	1.4
	1.3	1.2.3
		1.2.2	
			1.2.1.1
		1.2.1
	1.2
	1.1
1

And this is reading it out and writing it into a stack

1
	1.1
	1.2
		1.2.1
			1.2.1.1
		1.2.2
		1.2.3
	1.3
	1.4
2
	2.1
	2.2
		2.2.1
			2.2.1.1
		2.2.2
		2.2.3
	2.3
	2.4

Actually, if you initially had a QueueQueue (looping forward and collecting relevant data), then you could immediately linearize that into a stack (data written backwards). From here, you could write the stack into the encoder and then read it out to another stack. Either way, you'd still need both loops ;P.

The QueueQueue actually came out of this theory.

Let's say that you have a megalithic QueueQueue with every single possible object in your game. The branches in the QueueQueue could be represented as holes. If your data fits through the hole it can go inside. If it can't, it has to skip it (only for going right***).

For example-

Hero
    1-5 (first 5 heroes)
        item1
        item2
        item3
        item4
    6-max (rest of heroes
        item1
        item2
        item3
        item4
        item5
        item6

In this case, if you had a hero between 1 and 5, you'd only be able to save 4 items (perhaps they only have an inventory size of 4?). If you had any other hero, you could save 6 items.

So this is the output stack for a hero id of 3-
item4, item3, item2, item1, heroid

And for a hero id of 9
item6,item5,item4,item3,item2,item1,heroid

And this would be the output QueueQueue of the hero id of 9

    heroid
        item1
        item2
        item3
        item4
        item5
        item6

Reading it into a save/load code would require it be looped backwards.




Reading it back out, it'd first read the hero, then it'd know exactly how many items to load out of the code (remember that it has access to that huge megalithic QueueQueue). If the hero id was 3, it'd know to load out 4 items.

I'll probably be doing a snippet that'll be able to do this for you =P.




I first came up with the idea when I was saving item charges in the Encoder demo map. As you know, items have many different max charges, and most items have a max charge of 0. If you want to save item charges without massively bloating up the code, the only feasible option would be to use a QueueQueue.


Encoder 2.0.0.0 will run on QueueQueues, meaning that it will be far superior to any save/load system ever created for wc3. You can be sure that I will be pushing for every single save/load system on THW, TH, and wc3c to be graveyarded and replaced with Encoder when that day comes ;P.

 

[Sim]

> Encoder 2.0.0.0 will run on QueueQueues, meaning that it will be far superior to any save/load system ever created for wc3.

Is that done yet?

 

[Nestharus]

Is that done yet?

ETA next week some time between Tuesday and Thursday. I still have a 1 resource left to code that it and the demo map will be using.

It is the resource for doing the ranges with the QueueQueue outlined in post #4.


Some people have been asking for ways to catalog abilities on heroes, so I might be doing a resource for that since the only current AbilityEvent script is kind kind of broken and outdated, but that'll be for after Encoder 2.0.0.0.



There are also new thoughts on how catalogs may be used with Encoder 2.0.0.0 to shrink save/load codes even further by making class specific item catalogs.

 

[Nestharus]

Made it so that loop macros and module support whether or not to skip pointers. Before, it always skipped pointers. The skip method in the module is really only useful when not automatically skipping over pointer nodes as skipping an entire pointer is normally determined by the data in the pointer node.

There is currently no way to skip over specific pointers (everything it points to and etc) in the macro.

edit
Updated to probably the final version.

Added much more control over whether or not to skip pointers by adding a skips property (pointers only).

 

[Nestharus]

Added depth support to the loop macro. Now depthPointer and depthNode can be used for ultimate traversal.

Example of retrieving current parent
[ljass]set parent = looper.depthPointer.depthPointer.depthNode[/ljass]

Example of retrieving current parent given custom pointers

set parent = looper.depthPointer
loop
    exitwhen not pointer[parent.depthNode]
    set parent = parent.depthPointer
endloop

Also added id integer field to the loop macro so that instances can be associated with depth pointers. Remember that nodes may be linked to multiple times, so nodes can't be used as a reference, but depth pointers are entirely unique, so they can be used.

The id is reset to 0 properly, so no worries about reading possibly wrong values.

 

[Nestharus]

Fixed a bug in the Queue Queue module loop skip method.