Snippet DataStructures

[SerraAvenger]

What's this?

Implementations for two real basic datastructures, the ringbuffer (fifo) and the stack (lifo)

Needs?
JassPack NewGen (or just the JassHelper parser)

How to import?
Just copy and paste this into a Custom Script section.

How to use?
There are two textmacros, Stack and RingBuffer that both take the four arguments VISIBILITY, NAME, TYPE and SIZE.
For linked implementations, use LinkedStack and LinkedRingBuffer, respectively. Note that they have "unlimited" size per instance, which is why the SIZE parameter is ommitted.

• VISIBILITY - The "visibility" of the structure outside of the scope you're currently in. Possible arguments: "public" (needs the scope prefix to use); "private" (only useable within the scope)
• NAME - The name of the default structure and the structure's name (string)
• TYPE - What needs to be saved in the structure (type)
• SIZE - How much data can be saved in the structure (integer)

Stack methods:

• NAME_struct.create() -> NAME_struct
• push( TYPE ) -> nothing
• pop() -> TYPE
  Returns and removes the last pushed value
• get() -> TYPE
  Returns the last pushed value, but doesn't remove it
• used -> integer
  The number of entries in the structrure.

RingBuffer methods:

• NAME_struct.create() -> NAME_struct
• write( TYPE ) -> nothing
• read() -> TYPE
  Returns and removes the last written value
• get() -> TYPE
  Returns the last written value, but doesn't remove it
• used -> integer
  The number of entries in the structrure.

When you're trying to read from an empty structure / write into a full structure, it will return the "null" type (0 for ints, 0.0 for reals, null for handles). In debug mode, the Normal version will also spit out an error message.

Here's an example:

scope TestLinked initializer INIT

//! runtextmacro LinkedStack( "private", "ExampleStack", "integer" )
//! runtextmacro LinkedRingBuffer( "private", "ExampleRingbuffer", "integer" )

private function INIT takes nothing returns nothing
    local ExampleStack_struct test2 // NAME_struct
    local integer i = 0
    set test2 = ExampleStack_struct.create() // creates a new ExampleStack instance.
    loop
        exitwhen i == 10
        call ExampleStack.push( i )           // pushes i into the default stack
        call test2.push( ExampleStack.pop() ) // gets and removes the last value of the default stack, then pushes it into the test2 stack
        call ExampleRingbuffer.write( i + 4 ) // writes i+4 into the default ringbuffer
        set i = i + 1
    endloop
    call test2.pop() // simply removes the last value out of the stack
    call BJDebugMsg( "Linked: " + I2S( test2.get() ) + " + " + I2S( ExampleRingbuffer.get() ) + " = " + I2S( test2.get() + ExampleRingbuffer.get() ) )
    // get() doesn't remove the values.

endfunction
endscope
scope TestNonlinked initializer INIT

//! runtextmacro Stack( "private", "ExampleStack", "integer", "10" )
//! runtextmacro RingBuffer( "private", "ExampleRingbuffer", "integer","10" )

private function INIT takes nothing returns nothing
    local ExampleStack_struct test2 // NAME_struct
    local integer i = 0
    set test2 = ExampleStack_struct.create() // creates a new ExampleStack instance.
    loop
        exitwhen i == 10
        call ExampleStack.push( i )           // pushes i into the default stack
        call test2.push( ExampleStack.pop() ) // gets and removes the last value of the default stack, then pushes it into the test2 stack
        call ExampleRingbuffer.write( i + 4 ) // writes i+4 into the default ringbuffer
        set i = i + 1
    endloop
    call test2.pop() // simply removes the last value out of the stack
    call BJDebugMsg( "Nonlinked: " + I2S( test2.get() ) + " + " + I2S( ExampleRingbuffer.get() ) + " = " + I2S( test2.get() + ExampleRingbuffer.get() ) )
    // get() doesn't remove the values.

endfunction
endscope

The Code

// Array implementations
//! textmacro Stack takes VISIBILITY, NAME, TYPE, SIZE

$VISIBILITY$ keyword $NAME$_struct

globals
    $VISIBILITY$ $NAME$_struct $NAME$
endglobals

$VISIBILITY$ struct $NAME$_struct
    private $TYPE$ array data[ $SIZE$ ]
    static constant integer size = $SIZE$
    readonly integer used = 0
    
    method get takes nothing returns $TYPE$
        return .data[ .used ]
    endmethod
    
    method push takes $TYPE$ value returns nothing
        set .used = .used + 1
        set .data[ .used ] = value
        set value = .data[ 0 ]
    endmethod
    
    method pop takes nothing returns $TYPE$
        if .used > 0 then
            set .used = .used - 1
            return .data[ .used + 1 ]
        endif
        return .data[ 0 ]
    endmethod
    
    static method onInit takes nothing returns nothing
        set $NAME$ = thistype.create()
    endmethod
endstruct
//! endtextmacro



//! textmacro RingBuffer takes VISIBILITY, NAME, TYPE, SIZE

$VISIBILITY$ keyword $NAME$_struct

globals
    $VISIBILITY$ $NAME$_struct $NAME$
endglobals
    
$VISIBILITY$ struct $NAME$_struct
    private $TYPE$ array data[ $SIZE$ ]
    static constant integer size = $SIZE$
    readonly integer readIndex = 1
    readonly integer writeIndex = 1
    private boolean mayRead  = true
    private boolean mayWrite = true
    
    method get takes nothing returns $TYPE$
        return .data[ .readIndex ]
    endmethod
    
    method write takes $TYPE$ value returns nothing      
        
        if .writeIndex != .readIndex or .mayWrite then
            set .data[ .writeIndex ] = value
            
            if .writeIndex == $SIZE$ then
                set .writeIndex = 1
            else
                set .writeIndex = .writeIndex + 1
            endif
            
            set .mayRead  = .writeIndex == .readIndex
            set .mayWrite = false
        else
            debug call BJDebugMsg( "$NAME$ #"+I2S( this )+": Insufficient ring size!" )
        endif
        
        set value = .data[ 0 ]
    endmethod
    
    method read takes nothing returns $TYPE$
        local $TYPE$ value = .data[ 0 ]
        if .readIndex != .writeIndex or .mayRead then
            set value = .data[ .readIndex ]
            
            if .readIndex == $SIZE$ then
                set .readIndex = 1
            else
                set .readIndex = .readIndex + 1
            endif
            
            set .mayWrite = .writeIndex == .readIndex
            set .mayRead  = false
        else
            debug call BJDebugMsg( "$NAME$ #"+I2S( this )+": Trying to access empty field '" +I2S( .readIndex ) + "'!" )
        endif
        return value
    endmethod

    static method onInit takes nothing returns nothing
        set $NAME$ = $NAME$_struct.create()
    endmethod
    
endstruct

//! endtextmacro

//Linked Implementations

//! textmacro LinkedStack takes VISIBILITY, NAME, TYPE

$VISIBILITY$ keyword $NAME$_struct

globals
    $VISIBILITY$ $NAME$_struct $NAME$
endglobals

    private struct $NAME$_struct_chain
        thistype last  = 0
        $TYPE$   value
        integer  used  = 0

        method operator nextChain= takes $TYPE$ value returns thistype
            local thistype new = .allocate()
            set new.last = this
            set new.value = value
            set new.used = .used + 1
            return new
        endmethod
        
        method get takes nothing returns $TYPE$
            return .value
        endmethod
        
        method getNextChain takes nothing returns thistype
            call .destroy()
            return .last
        endmethod
    endstruct

$VISIBILITY$ struct $NAME$_struct
    readonly delegate $NAME$_struct_chain chain
    
    static method onInit takes nothing returns nothing
        set $NAME$ = thistype.create()
    endmethod
    
    static method create takes nothing returns thistype
        local thistype new = .allocate()
        set new.chain = 0
        return new
    endmethod
    
    method push takes $TYPE$ value returns nothing
        set .chain.nextChain = value
    endmethod
    
    method pop takes nothing returns $TYPE$
        local $TYPE$ val = .get()
        if .chain != 0 then
            set .chain = .chain.getNextChain()
        endif
        return val
    endmethod
endstruct
    
//! endtextmacro



//! textmacro LinkedRingBuffer takes VISIBILITY, NAME, TYPE

$VISIBILITY$ keyword $NAME$_struct

globals
    $VISIBILITY$ $NAME$_struct $NAME$
endglobals
    
private struct $NAME$_struct_chain
    thistype next = 0
    $TYPE$   value
    
    method get takes nothing returns $TYPE$
        return .value
    endmethod
    
    method operator nextChain= takes $TYPE$ value returns thistype
        local thistype new = .allocate()
        set .next = new
        set new.value = value
        return new
    endmethod
    
    method getNextChain takes nothing returns thistype
        call .destroy()
        return .next
    endmethod
endstruct

$VISIBILITY$ struct $NAME$_struct
    readonly delegate $NAME$_struct_chain chainRead
    readonly $NAME$_struct_chain chainWrite
    integer  used  = 0
    
    method write takes $TYPE$ value returns nothing      
        set .chainWrite.nextChain = value
        set .used = .used + 1
        if .chainRead == 0 then
            set .chainRead = .chainWrite
        endif
    endmethod
    
    method read takes nothing returns $TYPE$
        local $TYPE$ value = .get()
        set .chainRead = .chainRead.getNextChain()
        set .used = .used - 1
        return value
    endmethod

    static method onInit takes nothing returns nothing
        set $NAME$ = $NAME$_struct.create()
    endmethod
    
endstruct

//! endtextmacro

 

[Jesus4Lyf]

Sorry, SerraAvenger, this is bad.

You've done the whole thing with arrays instead of linked lists, which are the proper way to implement these. And I don't see why you made a RingBuffer (which I've never heard of) instead of a Queue.

To me the point of these data structures in Warcraft III is unknown size. =/

My personal Queue struct (unreleased):

Spoiler

private struct Queue//QueueNode // Do not destroy Queues which are not empty.
    private Queue first//value
    private Queue last//next
    // Method are for Queue only.
    static method create takes nothing returns Queue
        local Queue this=Queue.allocate()
        set this.first=0
        set this.last=0
    endmethod
    method enqueue takes integer i returns nothing
        set this.last.last=Queue.allocate() //this.last.next=QueueNode.create()
        set this.last=this.last.last //this.last.next
        if this.first==0 then
            set this.first=this.last
        endif
        set this.last.last=0 //set this.last.next=0
        set this.last.first=i //set this.last.value=i
    endmethod
    method dequeue takes nothing returns integer
        local Queue n=this.first //local QueueNode n=this.first
        set this.first=n.last //set this.first=this.first.next basically.
        if this.first==0 then
            set this.last=0
        endif
        call n.destroy()
        return n.first //return n.value - yes, after destruction.
    endmethod
    method isEmpty takes nothing returns boolean
        return this.first==0
    endmethod
endstruct

My personal Stack struct (currently used in DTS):

Spoiler

private struct stack // Doesn't require destroy, just must be empty.
    private stack next
    private integer data
    static method create takes nothing returns stack
        return 0
    endmethod
    method operator push= takes integer i returns stack
        local stack new=stack.allocate()
        set new.data=i
        set new.next=this
        return new
    endmethod
    method pop takes nothing returns stack
        call this.destroy()
        return this.next
    endmethod
    method operator val takes nothing returns integer
        return this.data
    endmethod
    method operator empty takes nothing returns boolean
        return this==0
    endmethod
endstruct

Their use is a little ambiguous and inconsistent, but fun. Just my experimenting with ways of doing things.

I was going to say you beat me to it, but then I realised you haven't written them appropriately. I recommend you try rewriting Stack and Queue with linked lists.

 

[TheDamien]

There is no "correct" way to implement a queue or a stack. Buffers and linked lists are just the popular implementations.

 

[Jesus4Lyf]

>There is no "correct" way
It was based on the following statement.
>To me the point of these data structures in Warcraft III is unknown size.

The other thing is although there's no "correct" way, there's ways which are advantageous to users, and linked lists is one such way because it requires no size definition, and it ultimately allows more instances because blank slots in the struct arrays are filled.

 

[SerraAvenger]

Strange implementations you use there oO
The idea was too allow .used, but I already have an Idea on how to fix that.
I shall upload linked versions soon.

 

[Gwypaas]

Linked lists is totally useless for stacks in JASS since what you're doing there is just mimicing an array, that then in the background uses an array.

I've actully already released a "stack" system, but it got forgotten waaay back.

http://www.thehelper.net/forums/showthread.php?t=124723

 

[Jesus4Lyf]

You are so very wrong. It allows dynamic size allocation, which I just said a moment ago is half the point in many situations. What if you want structs with stack members?

See "Event" for an example of this. And tell me how you could implement this with arrays without reducing the instance limit by a fixed factor.

 

[SerraAvenger]

bump. Now with linked datastructures, too.