[Snippet] List Optimum Speed

Nestharus · Sep 30, 2009

Every single thing includes complete demonstrations. The highest layers are at the bottom.

Malloc
Stacks
Dequeues

Malloc

JASS:

/*
    MALLOC_FIELDS takes NAMESPACE
*/

//malloc
//! textmacro MALLOC_FIELDS takes NAMESPACE
    //refers to current index of malloc
    public static integer mallocIndex$NAMESPACE$ = 1
    //refers to number of deallocated elements in the malloc
    public static integer mallocDeallocatedCount$NAMESPACE$ = 0
    //refers deallocated elements in the malloc
    public static integer array mallocDeallocated$NAMESPACE$
//! endtextmacro

/*
MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
    //code
else
    MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
    //code
endif
//code
*/

//try to get element from deallocated area
//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
    if $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ > 0 then //check for freed elements in the malloc
        //set memory reference to the last deallocated element and remove that element from the malloc
        set $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ = $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ - 1
        set $MEMORY_REF$ = $MEMORY_REF$.mallocDeallocated$NAMESPACE$[$MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$]
//! endtextmacro

//try to make a new element if no freed element
//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
    set $MEMORY_REF$ = $MEMORY_REF$.mallocIndex$NAMESPACE$
    set $MEMORY_REF$.mallocIndex$NAMESPACE$ = $MEMORY_REF$.mallocIndex$NAMESPACE$ + 1
//! endtextmacro

/*
MALLOC_DEALLOCATED takes NAMESPACE, MEMORY_REF
*/

//free an allocated element
//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF
    set $MEMORY_REF$.mallocDeallocated$NAMESPACE$[$MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$] = $MEMORY_REF$
    set $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ = $MEMORY_REF$.mallocDeallocatedCount$NAMESPACE$ + 1
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        //! runtextmacro MALLOC_DEALLOCATE("", "this")
    endmethod
endstruct
*/

module MallocFields
    //! runtextmacro MALLOC_FIELDS("")
endmodule

module MallocAllocateFreed
    local thistype this
    //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
endmodule

module MallocAllocateNew
    else
        //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
endmodule

module MallocDeallocate
    //! runtextmacro MALLOC_DEALLOCATE("", "this")
endmodule

/*
struct Test extends array
    implement MallocFields
    
    public static method allocate takes nothing returns thistype
        implement MallocAllocateFreed
        implement MallocAllocateNew
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        implement MallocDeallocate
    endmethod
endstruct
*/

module MallocStruct
    implement MallocFields
    
    public static method allocate takes nothing returns thistype
        implement MallocAllocateFreed
        implement MallocAllocateNew
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        implement MallocDeallocate
    endmethod
endmodule

/*
struct Test extends array
    implement MallocStruct
endstruct
*/

DMalloc

JASS:

globals
    boolean dNewMalloc = false
    integer dMallocAllocated
endglobals

/*
    D_MALLOC_FIELDS takes NAMESPACE
*/

//malloc
//! textmacro D_MALLOC_FIELDS takes NAMESPACE
    //refers to current index of malloc
    public static thistype dMallocIndex$NAMESPACE$ = 0
    //refers to the last deallocated element
    public static thistype dMallocDeallocated$NAMESPACE$ = 0
//! endtextmacro

//! textmacro D_MALLOC_ALLOCATE_S takes NAMESPACE, MEMORY_REF
    if $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ != 0 then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
        set $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$.previous$NAMESPACE$
    else
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
    endif
//! endtextmacro

//returns circular dequeue
//! textmacro D_MALLOC_ALLOCATE takes NAMESPACE, MEMORY_REF, COUNT
    if $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ != 0 then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
        set $COUNT$ = $COUNT$ - 1
        
        loop
            exitwhen $MEMORY_REF$.previous$NAMESPACE$ == 0 or $COUNT$ == 0
            set $MEMORY_REF$ = $MEMORY_REF$.previous$NAMESPACE$
            set $COUNT$ = $COUNT$ - 1
        endloop
        
        set $MEMORY_REF$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF$.previous$NAMESPACE$
        set dMallocAllocated = $MEMORY_REF$.dMallocDeallocated$NAMESPACE$
    else
        set $MEMORY_REF$ = 0
        set dMallocAllocated = 0
    endif
    
    if $COUNT$ != 0 then
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        
        if dMallocAllocated == 0 then
            set dMallocAllocated = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        endif
        
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF$
        set $MEMORY_REF$.previous$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        
        set $COUNT$ = $COUNT$ - 1
        
        set dNewMalloc = true
    endif
    
    loop
        exitwhen $COUNT$ == 0
        set dMallocIndex$NAMESPACE$.previous$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$+1
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ + 1
        set $MEMORY_REF$.dMallocIndex$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$ - 1
        
        set $COUNT$ = $COUNT$ - 1
    endloop
    
    if dNewMalloc then
        set $MEMORY_REF$ = $MEMORY_REF$.dMallocIndex$NAMESPACE$
        set dNewMalloc = false
    endif
    
    set $MEMORY_REF$.previous$NAMESPACE$ = dMallocAllocated
    
    set dMallocAllocated = $MEMORY_REF$
    set $MEMORY_REF$ = dMallocAllocated
    
    set $MEMORY_REF$.next$NAMESPACE$ = dMallocAllocated
//! endtextmacro

/*
MALLOC_DEALLOCATED takes NAMESPACE, MEMORY_REF
*/

//free an allocated element
//! textmacro D_MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF_1, MEMORY_REF_2
    set $MEMORY_REF_1$.previous$NAMESPACE$ = $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$
    set $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$.next$NAMESPACE$ = $MEMORY_REF_1$
    set $MEMORY_REF_2$.next$NAMESPACE$ = 0
    set $MEMORY_REF_1$.dMallocDeallocated$NAMESPACE$ = $MEMORY_REF_2$
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro D_MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        local thistype this
        //! runtextmacro D_MALLOC_ALLOCATE("", "this", "count")
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
    endmethod
endstruct
*/

module DMallocFields
    //! runtextmacro D_MALLOC_FIELDS("")
endmodule

module DMallocAllocateS
    local thistype this
    //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
endmodule

module DMallocAllocate
    local thistype this
    //! runtextmacro D_MALLOC_ALLOCATE("", "this", "count")
endmodule

module DMallocDeallocate
    //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
endmodule

/*
struct Test extends array
    implement DMallocFields
    
    public static method allocate takes nothing returns thistype
        implement DMallocAllocateS
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        implement DMallocAllocate
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        implement DMallocDeallocate
    endmethod
endstruct
*/

module DMallocStruct
    implement DMallocFields
    
    public static method allocate takes nothing returns thistype
        implement DMallocAllocateS
        return this
    endmethod
    
    public static method allocateCount takes integer count returns thistype
        implement DMallocAllocate
        return this
    endmethod
    
    public static method deallocate takes thistype node1, thistype node2 returns nothing
        implement DMallocDeallocate
    endmethod
endmodule

/*
struct Test extends array
    implement DMallocStruct
    
    implement DequeueFields
endstruct
*/

Stack

JASS:

//memory for stack
//! textmacro STACK_FIELDS takes NAMESPACE
    public thistype next$NAMESPACE$
//! endtextmacro

//move node1 through node2 to in front of node3
//! textmacro STACK_MOVE takes NAMESPACE, NODE1, NODE2, NODE3
    set $NODE2$.next$NAMESPACE$ = $NODE3$.next$NAMESPACE$
    set $NODE3$.next$NAMESPACE$ = $NODE1$
//! endtextmacro

//! textmacro STACK_LINK takes NAMESPACE, NODE1, NODE2
    set $NODE1$.next$NAMESPACE$ = $NODE2$
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    //! runtextmacro STACK_FIELDS("")
    
    public method push takes thistype node returns nothing
        //! runtextmacro STACK_MOVE("", "node", "node", "this")
    endmethod
    
    public method pop takes nothing returns thistype
        local thistype node = next
        //! runtextmacro STACK_LINK("", "this", "node.next")
        
        return node
    endmethod
    
    //moves node1 through node2 to after node3
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        //! runtextmacro STACK_MOVE("", "node1", "node2", "node3")
    endmethod
    
    //links up node1 with node2
    public static method link takes thistype node1, thistype node2 returns nothing
        //! runtextmacro STACK_LINK("", "node1", "node2")
    endmethod
    
    //deallocates a range of nodes from node1 through node2
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        loop
            //! runtextmacro MALLOC_DEALLOCATE("", "node1")
            exitwhen node1 == node2
            set node1 = node1.next
        endloop
    endmethod
endstruct
*/

module StackFields
    //! runtextmacro STACK_FIELDS("")
endmodule

module StackPush
    //! runtextmacro STACK_MOVE("", "node", "node", "this")
endmodule

module StackPop
    local thistype node = next
    //! runtextmacro STACK_LINK("", "this", "node.next")
endmodule

module StackMove
    //! runtextmacro STACK_MOVE("", "node1", "node2", "node3")
endmodule

module StackLink
    //! runtextmacro STACK_LINK("", "node1", "node2")
endmodule

module StackDestroyRangeStart
    loop
        //! runtextmacro MALLOC_DEALLOCATE("", "node1")
endmodule

module StackDestroyRangeEnd
        exitwhen node1 == node2
        set node1 = node1.next
    endloop
endmodule

/*
struct Test extends array
    implement MallocStruct
    implement StackFields
    
    public method push takes thistype node returns nothing
        implement StackPush
    endmethod
    
    public method pop takes nothing returns thistype
        implement StackPop
        return node
    endmethod
    
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        implement StackMove
    endmethod
    
    public static method link takes thistype node1, thistype node2 returns nothing
        implement StackLink
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement StackDestroyRangeStart
        implement StackDestroyRangeEnd
    endmethod
endstruct
*/

module StackStruct
    implement MallocStruct
    implement StackFields
    
    public method push takes thistype node returns nothing
        implement StackPush
    endmethod
    
    public method pop takes nothing returns thistype
        implement StackPop
        return node
    endmethod
    
    public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
        implement StackMove
    endmethod
    
    public static method link takes thistype node1, thistype node2 returns nothing
        implement StackLink
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement StackDestroyRangeStart
        implement StackDestroyRangeEnd
    endmethod
endmodule

/*
struct Test extends array
    implement StackStruct
endstruct
*/

Dequeue

JASS:

//fields for temporary storage
module ListTempFields
    public static thistype nextTemp
    public static thistype previousTemp
endmodule

//dequeue fields
//! textmacro DEQUEUE_FIELDS takes NAMESPACE
    implement ListTempFields //temporary storage fields of thistype
    
    public thistype previous$NAMESPACE$ //<- previous | next ->
    public thistype next$NAMESPACE$ //<- previous | next ->
//! endtextmacro

//links up two nodes. Can be used for removing nodes or creating lists or moving nodes
//! textmacro DEQUEUE_LINK takes NAMESPACE, NODE_HEAD, NODE_REF_1, NODE_REF_2
    //this can result if head.next == head.previous, in cases where there is only one node
    //without doing this, this type of link would result in an infinite list in which the
    //node pointed to itself.
    
    //cases of 0, 0 are not dangerous
    if $NODE_REF_1$ == 0 or $NODE_REF_1$ != $NODE_REF_2$ then
        //if node ref 1 is null, link head.next to node ref 2
        if $NODE_REF_1$ == 0 then
            set $NODE_HEAD$.next$NAMESPACE$ = $NODE_REF_2$
        else //otherwise normal link
            set $NODE_REF_1$.next$NAMESPACE$ = $NODE_REF_2$
        endif
        
        //if node ref 2 is null, link head.previous to node ref 1
        if $NODE_REF_2$ == 0 then
            set $NODE_HEAD$.previous$NAMESPACE$  = $NODE_REF_1$
        else //otherwise normal link
            set $NODE_REF_2$.previous$NAMESPACE$ = $NODE_REF_1$
        endif
    endif
//! endtextmacro

//used for temporarily copying 2 nodes. Useful for swapping operations
//! textmacro DEQUEUE_TMP_COPY takes NODE_REF_1, NODE_REF_2
    set $NODE_REF_1$.previousTemp = $NODE_REF_1$
    set $NODE_REF_1$.nextTemp = $NODE_REF_2$
//! endtextmacro

//ini dequeue head
//! textmacro DEQUEUE_INI_HEAD takes NAMESPACE, HEAD
    set $HEAD$.previous$NAMESPACE$ = 0 //head.previous = 0
    set $HEAD$.next$NAMESPACE$ = 0 //head.next = 0
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    //! runtextmacro DEQUEUE_FIELDS("")
    
    //toList.move(args)
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        //toNode1 <-> node1 <-> ...
        //! runtextmacro DEQUEUE_LINK("", "this", "toNode1", "node1")
        //... <-> node2 <-> toNode2
        //! runtextmacro DEQUEUE_LINK("", "this", "node2", "toNode2")
    endmethod
    
    //linking nodes allows for destruction, clearing, adding, moving, and swapping
    //the move operation is actually 2 links
    public method link takes thistype node1, thistype node2 returns nothing
        //node1 <-> node2
        //! runtextmacro DEQUEUE_LINK("", "this", "node1", "node2")
    endmethod
    
    //creates a head and sets it's next and previous to 0
    public static method create takes nothing returns thistype
        local thistype this
        
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        
        //! runtextmacro DEQUEUE_INI_HEAD("", "this")
        
        return this
    endmethod
    
    //deallocates a range of nodes
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        loop
            //! runtextmacro MALLOC_DEALLOCATE("", "node1")
            exitwhen node1 == node2
            set node1 = node1.next
        endloop
    endmethod
    
    //swap node1 and node2 part of head with toNode1 and toNode2 part of toHead
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        //cpy node1_1.previous to previousTemp
        //cpy node1_2.next to nextTemp
        //! runtextmacro DEQUEUE_TMP_COPY("node1.previous", "node2.next")
        
        //node2_1.previous <-> node1_1 <-> node1_2 <-> node2_2.next
        //! runtextmacro DEQUEUE_LINK("", "toHead", "toNode1.previous.next", "node1")
        //! runtextmacro DEQUEUE_LINK("", "toHead", "node2", "toNode2.next.previous")
        
        //previousTemp <-> node2_1 <-> node2_2 <-> nextTemp
        //! runtextmacro DEQUEUE_LINK("", "head", "previousTemp", "toNode1")
        //! runtextmacro DEQUEUE_LINK("", "head", "toNode2", "nextTemp")
    endmethod
endstruct
*/

module DequeueFields
    //! runtextmacro DEQUEUE_FIELDS("")
endmodule

module DequeueMove
    //toNode1 <-> node1 <-> ...
    //! runtextmacro DEQUEUE_LINK("", "this", "toNode1", "node1")
    //... <-> node2 <-> toNode2
    //! runtextmacro DEQUEUE_LINK("", "this", "node2", "toNode2")
endmodule

module DequeueLink
    //node1 <-> node2
    //! runtextmacro DEQUEUE_LINK("", "this", "node1", "node2")
endmodule

module DequeueAllocateIni
    //! runtextmacro DEQUEUE_INI_HEAD("", "this")
endmodule

module DestroyRange
    //! runtextmacro D_MALLOC_DEALLOCATE("", "node1", "node2")
endmodule

module DequeueSwap
    //cpy node1_1.previous to previousTemp
    //cpy node1_2.next to nextTemp
    //! runtextmacro DEQUEUE_TMP_COPY("node1.previous", "node2.next")
    
    //node2_1.previous <-> node1_1 <-> node1_2 <-> node2_2.next
    //! runtextmacro DEQUEUE_LINK("", "toHead", "toNode1.previous.next", "node1")
    //! runtextmacro DEQUEUE_LINK("", "toHead", "node2", "toNode2.next.previous")
    
    //previousTemp <-> node2_1 <-> node2_2 <-> nextTemp
    //! runtextmacro DEQUEUE_LINK("", "head", "previousTemp", "toNode1")
    //! runtextmacro DEQUEUE_LINK("", "head", "toNode2", "nextTemp")
endmodule

/*
struct Test extends array
    implement MallocStruct
    implement DequeueFields
    
    public method link takes thistype node1, thistype node2 returns nothing
        implement DequeueLink
    endmethod
    
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueMove
    endmethod
    
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueSwap
    endmethod
    
    public static method create takes nothing returns thistype
        implement DequeueAllocateFreed
            //code to do when getting a freed index, one that's been previous used
        implement DequeueAllocateNew
            //what to do when getting a brand new index, never used
        implement DequeueAllocateIni
        
        //what to always do
        
        return this
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement DestroyRangeStart
        implement DestroyRangeEnd
    endmethod
endstruct
*/

module DequeueStruct
    implement DMallocStruct
    implement DequeueFields
    
    public method push takes thistype node returns nothing
        set .previous.next = node
        set node.previous = .previous
        set node.next = 0
        set .previous = node
        
        if .next == 0 then
            set .next = node
        endif
    endmethod
    
    public method pop takes nothing returns thistype
        local thistype node = .previous
        
        set .previous = node.previous
        set .previous.next = 0
        
        if .next == node then
            set .next = 0
        endif
        
        return node
    endmethod
    
    public method unshift takes thistype node returns nothing
        set .next.previous = node
        set node.next = .next
        set node.previous = 0
        set .next = node
        
        if .previous == 0 then
            set .previous = node
        endif
    endmethod
    
    public method shift takes nothing returns thistype
        local thistype node = .next
        
        set .next = node.next
        set .next.previous = 0
        
        if .previous == node then
            set .previous = 0
        endif
        
        return node
    endmethod
    
    public method link takes thistype node1, thistype node2 returns nothing
        implement DequeueLink
    endmethod
    
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueMove
    endmethod
    
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        implement DequeueSwap
    endmethod
    
    public static method create takes nothing returns thistype
        local thistype this
        
        //! runtextmacro D_MALLOC_ALLOCATE_S("", "this")
        
        implement DequeueAllocateIni
        
        return this
    endmethod
    
    public static method destroyRange takes thistype node1, thistype node2 returns nothing
        implement DestroyRange
    endmethod
endmodule

/*
struct Test extends array
    implement DequeueStruct
endstruct
*/

Coding With This Framework
Each portion of the framework has 3 layers that range in simplicity and power.
Layer 1- macro based and pretty hardcore
Layer 2- module based and semi hardcore
Layer 3- module based and very simple

Coding With Malloc

Layer 1-
-----------------------------------------------------------------------------------------------------
Malloc at layer 1 uses the allocate and deallocate methods to provide automatic memory allocation for structs that extend arrays.

JASS:

public static method allocate takes nothing returns thistype
public method deallocate takes nothing returns nothing

The module containing everything is

JASS:

module MallocStruct

To use it, simply make a struct that extends an array and implement the module

JASS:

struct Test extends array
    implement MallocStruct
endstruct

And making instances is just like normal-

JASS:

Test test = Test.allocate()
call test.deallocate()

Layer 2
-----------------------------------------------------------------------------------------------------

The stuff in layer 2 are macros geared to making the allocate and deallocate methods-

MallocFields
MallocAllocateFreed
MallocAllocateNew
MallocDeallocate

MallocFields simply implements the fields needed for malloc to work.
implement MallocFields

MallocAllocateFreed attempts to get freed memory for malloc
MallocAllocateNew gets new memory for malloc

JASS:

public static method allocate takes nothing returns thistype
    //declare locals

    implement MallocAllocateFreed
        //code to do when getting a freed index
    implement MallocAllocateNew
        //code to do when getting a new index
    endif

    //code to always do on allocation

    return this
endmethod

MallocDeallocate frees memory for malloc

JASS:

public method deallocate takes nothing returns nothing
    //declare locals

    implement MallocDeallocate

    //code to always do on deallocation
endmethod

Layer 3
-----------------------------------------------------------------------------------------------------

JASS:

//! textmacro MALLOC_FIELDS takes NAMESPACE
//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF
//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF
//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF

NAMESPACE is much like a scope. With all portions of the framework, the collections and malloc styles may be declared in varying namespaces so that one struct may have a multitude of collections.

These operate much the same way as their corresponding modules on layer 2 but they have no variable declarations. Looking at the modules they are implemented in will give a great idea of how they operate.

//! textmacro MALLOC_FIELDS takes NAMESPACE

JASS:

module MallocFields
    //! runtextmacro MALLOC_FIELDS("")
endmodule

//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF

JASS:

module MallocAllocateFreed
     local thistype this
    //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
endmodule

//! textmacro MALLOC_ALLOCATE_NEW takes NAMESPACE, MEMORY_REF

JASS:

module MallocAllocateNew
    else
        //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
endmodule

//! textmacro MALLOC_DEALLOCATE takes NAMESPACE, MEMORY_REF

JASS:

module MallocDeallocate
    //! runtextmacro MALLOC_DEALLOCATE("", "this")
endmodule

And for a complete struct example-

JASS:

struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    
    public static method allocate takes nothing returns thistype
        local thistype this
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        return this
    endmethod
    
    public method deallocate takes nothing returns nothing
        //! runtextmacro MALLOC_DEALLOCATE("", "this")
    endmethod
endstruct

So why is an else required after
//! textmacro MALLOC_ALLOCATE_FREED takes NAMESPACE, MEMORY_REF?

The reason is that MALLOC_ALLOCATE_FREED starts off with an if statement but has no endif or else

if freed > 0 then

In essence it checks to see if there is any freed memory. If there is, it goes on to unfree it and store it in the variable you specify. The reason there is no else or endif is so that users can write code specifically for freed memory. Let's say 5 variables needed to be set whenever a brand new struct was instanced, but only 1 variable needed to be set when that struct got reused later on. This could very well happen when dealing with parallel collections or when permanently assigning a handle like a timer to a struct. Sometimes variables need to be set when the struct is used for the first time, sometimes others need to be set when a struct is reused, and sometimes stuff needs to be set every time.

Coding With DMalloc

DMalloc is a special type of memory allocation geared for dequeues.

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of DMalloc is simply a module that contains 3 methods

public static method allocate takes nothing returns thistype
Allocates a single node. Normal operation count per node (3).

public static method allocateCount takes integer count returns thistype
Allocates a circular list of nodes. Performs around 4.5*x+12 give or take a few. Standard performs 7*x+2 (3+4 where 4 = links). This is better than standard allocate when dealing with between 4+ and 7+ nodes depending on the circumstances.

Essentially, if 10 nodes were to be allocated, the list might look like
10<->1<->2<->3<->4<->5<->6<->7<->8<->9<->10

Adding to a list might be

JASS:

list.move(10.previous, 10, 0, 0)

public static method deallocate takes thistype node1, thistype node2 returns nothing
Deallocates a range of nodes. Normal deallocation operations for a range of nodes are x*2 where x is the number of nodes between and including node1 and node2. The number of operations for this special deallocate is 4 regardless. This means that standard deallocation would perform 600 operations on 300 nodes where this one would perform 4.

JASS:

list.deallocate(1, 10) //4 operations instead of 20

To use it, simply use the DMalloc module in accordance with a Dequeue or use the DequeueStruct as it auto implements DMalloc

JASS:

struct Test extends array
    implement DequeueStruct
endstruct

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

Coding With Stack

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of Stack is simply a module that contains 7 methods, 2 being from Malloc and 5 being from Stack
Malloc

JASS:

public static method allocate takes nothing returns thistype
public method deallocate takes nothing returns nothing

Stack
public method push takes thistype node returns nothing
Same as standard push

stack.push(node)

public method pop takes nothing returns thistype
Same as standard pop but does not reset the pointer of the returned node.

node = stack.pop()

public static method link takes thistype node1, thistype node2 returns nothing
Links two nodes together. Can be used for removing nodes, simple node link, or w/e.

Given 1, 2
link(1, 2)
1->2

public static method move takes thistype node1, thistype node2, thistype node3 returns nothing
Moves node1 through node2 to after node3

Given 1->2->3->4->5->6->7->8->9
link(2, 6)
3->4->5,
1->2->6->7->8->9

move(3, 5, 9)
1->2->6->7->8->9->3->4->5

public static method destroyRange takes thistype node1, thistype node2 returns nothing
Deallocates a range of nodes. Does not delink them!

Given 1->2->3->4->5->6->7

If you wanted to remove and deallocate nodes 3 through 5

link(2, 6)
3->4->5,
1->2->6->7

deallocate(3, 5)
1->2->6->7

In the background, there is still 3->4->5 as they are not delinked, so keep this in mind if a new node is allocated and for some reason it is linked up with a bundle of other nodes. Resetting a link to 0 if not linking it with something immediately is typically a good idea.

The module containing everything is

JASS:

module StackStruct

To use it

JASS:

struct Test extends array
    implement StackStruct
endstruct

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

Coding With Dequeue

0 is treated as null with dequeues. Using 0 is a great way to clear out the entire list or to add to the front/end.

Layer 1-
-----------------------------------------------------------------------------------------------------
The first layer of Dequeue is simply a module that contains 10 methods, 3 being from DMalloc and 9 being from Dequeue

DMalloc

JASS:

public static method allocate takes nothing returns thistype
public static method allocateCount takes integer count returns thistype
public static method deallocate takes thistype node1, thistype node2 returns nothing

Dequeue
public method push takes thistype node returns nothing
Standard push

public method pop takes nothing returns thistype
Standard pop

public method unshift takes thistype node returns nothing
Standard unshift (see Perl arrays)

public method shift takes nothing returns thistype
Standard shift (see Perl arrays)

public method link takes thistype node1, thistype node2 returns nothing
Links two nodes together. Can be used for removing nodes, adding nodes, or w/e.

JASS:

//Given 1, 2
list.link(1, 2)
//1<->2

//Given 1
//link at front
list.link(1, list.next)
list.link(0, 1)

//or
list.link(list.previous, 1)
list.link(1, 0) //link at back
//or
list.link(0, 0) //clear entire list

Same Node Linkage

JASS:
Linking a node to itself (excluding 0) will result in nothing happening. This is to ensure that infinitely linked lists do not occur.

This is a prime example

JASS:

//given 1 and an empty list //a single node list.link(1, 0) list.link(0, 1) list.link(list.next, list.previous) //link 1 to 1

public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
Moves node1 through node2 to between toNode1 and toNode2. The list used to call move is toList, or the list the nodes are moving to.

Given 1<->2<->3<->4<->5<->6, 7<->8<->9

list2.move(3, 5, 7, 9)

List 1
a. 1<->2->3<->4<->5<->9
b. 5<-6

List 2
7<->3<->4<->5<->9

Node 8
7<-8->9

This interesting scenario essentially removes 8 from the second list and totally screws up the first list.

A simple list.link(2, 6) could fix up the breaks in list1 and a deallocate(8) could fix up 8, but what if we wanted to move 8 into 3, 4, 5's old position?

list.move(8, 8, 2, 6)
1<->2<->8<->6
7<->3<->4<->5<->9

So what happened? 8 and 3, 4, 5 swapped positions. With 2 moves like this, a swap occurs.

public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing

Swap swaps node1 through node2 on head with toNode1 through toNode2 on toHead. Essentially 2 moves.

Given 1<->2<->3<->4<->5<->6<->7<->8<->9

swap(head, 2, 5, toHead, 6, 8)
1<->6<->7<->8<->2<->3<->4<->5<->9

public static method create takes nothing returns thistype
Creates a node and sets it's next and previous to 0 so that it can be used as a head. The head node should never be manipulated or used, it's simply there to point to the dequeue. It's previous is the last node and it's next is the first node on the dequeue.

0<-head->0

When adding new nodes, the nodes are essentially added after and between the head by using 0 (null). They can also be added in between other nodes, like 1 and 5.

All dequeues must have a head.

The method returns the head.
dequeue = Dequeue.create()

public static method destroyRange takes thistype node1, thistype node2 returns nothing
Destroys a range of nodes. Does not delink the nodes, so removing them before deallocation is important. Can also be used to deallocate the head and tail nodes (destroying an entire list).

Given 1<->2<->3<->4<->5<->6<->7<->8<->9

list.link(2, 7)
1<->2<->7<->8<->9
2<-3<->4<->5<->6->7

Dequeue.destroyRange(3, 6)
1<->2<->7<->8<->9

The module containing everything is

JASS:

module DequeuStruct

To use it

JASS:

struct Test extends array
    implement DequeueStruct
endstruct

How to iterate through a dequeue
Iterating through a dequeue typically starts at the beginning of it or the end of it.

list.next is the first node
list.previous is the last node

Iteration ends when the node is 0.

JASS:

Node node = list //start at list, just let the loop do the rest to save on 1 iteration
loop
    set node = node.next //move to next node
    exitwhen node == 0 //exit when node is null
    call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, I2S(node))
endloop

Layer 2-
-----------------------------------------------------------------------------------------------------

Layer 3-
-----------------------------------------------------------------------------------------------------

aznricepuff · Sep 30, 2009

Ok, a Linked List is used for three things:

stacks
queues
deques

This means linked lists need to be able to do four things:

addFirst() for front-end enqueing (deques)
removeFirst() for front-end dequeing (queues and deques)
addLast() for tail-end enqueing (queues and deques) and pushing (stacks)
removeLast() for tail-end dequeing (deques) and popping (stacks)

If I have to do:

JASS:

    local integer lastIndex = list.getLastIndex()
    local integer element = list[lastIndex]
    call list.remove(lastIndex)

just to pop from a stack or:

JASS:

    local integer firstIndex = list.getFirstIndex()
    local integer element = list[firstIndex]
    call list.remove(firstIndex)

just to front-end dequeue something it kind of defeats the purpose of using a linked list (and by the way I cant even implement a deque using this because there's no way to do front-end enqueues).

Nestharus · Sep 30, 2009

It'd actually be-

JASS:

call list.remove(list.getFirstIndex())
call list.remove(list.getLastIndex())

getFirst and getLast are inlined as they are one liners.

Now, as for add, it always kind of puts it at the very back of the queue, but it would not be at all hard to put it in the front =P.

I guess I'll add 4 methods and rename one-
shift
unshift
push
pop (current add)

add (takes an index)

From here, I can also make it so that last automatically adds on new indexes if they don't exist.

I can also do purge, remove instance of element from list, and so on : \. None of this would inhibit the speed of the linked list at all : p.

I'll get right on it : ).

Lambdadelta · Oct 1, 2009

I see some very 'good' comments on TheHelper

Can I post them here as quotes?

Jesus4Lyf said:
Most of what you've said appears to be BS.

>It's about 6x slower than a plain hashtable.
How is it comparable?

Do not even try to tell me your ".next" method, the most used method in a list, is in any way faster than this.

You compared to a bunch of wc3c systems. Do I need to say why that's silly?

Graveyarded due to being slow and named "List Optimum Speed". If you prove me wrong by giving a "getNext" method that is faster or at least the same speed as the Linked List Module, I will ungraveyard (unless new reasons arise for this to remain graveyarded).

JASS:

public method next takes nothing returns integer set .listMethod = .currentIndex[this] if .listMethod == .finalIndex[this] then if .nextIndexQueueIndex > 0 then set .nextIndexQueueIndex = .nextIndexQueueIndex - 1 set .currentIndex[this] = .nextIndexQueue[.nextIndexQueueIndex] else set .currentIndex[this] = .nextIndexIndex set .nextIndexIndex = .nextIndexIndex + 1 endif set .lastIndex[.currentIndex[this]] = .listMethod set .nextIndex[.lastIndex[.currentIndex[this]]] = .currentIndex[this] set .finalIndex[this] = .currentIndex[this] set .size[this] = .size[this] + 1 else set .lastIndex[.listMethod] = .listMethod set .currentIndex[this] = .nextIndex[.listMethod] endif return .currentIndex[this] endmethod

VS

JASS:

method getNext takes nothing returns thistype return this.next endmethod

Nestharus · Oct 1, 2009

Mind if I post too?

Speed isn't everything. Perhaps functionality is worth more.

That's Jesus4Lyf saying he realizes I wasn't bsing him about speed =).

aznricepuff · Oct 1, 2009

JASS:
It'd actually be-

JASS:

call list.remove(list.getFirstIndex()) call list.remove(list.getLastIndex())

Um...no. The point of dequeue and pop is that they return whatever you removed since usually you don't just randomly remove something from a list and then forget about it.

I would really love to this test system's speed: populating, iteration, removal, search (if it is even implemented), set, destroy, against List here in the JASS forum and against my LinkedList. Both of them provide more functionality than this, and I'm pretty sure List is as fast if not faster than yours at most of these operations (though I wouldn't be surprised if both this and List blew mine out of the water in terms of speed...I was going for maximal functionality and not extreme efficiency with mine). However, I can't right now because I have an exam tomorrow that I would rather not fail. But I'll get around to it...eventually.

Deaod · Oct 1, 2009

Looks like someone has been updating silently.

Where do those benchmarks come from?

Nestharus · Oct 1, 2009

Look at the version number. That's 4 versions in one day =P.

I generally update code silently because if I didn't, the post would be filled with mass replies on update, update, update : d.

lol

I used to include a date of the update on the post so you'd quickly know if I updated or not, but now I just include a version number at top of code =P.

Oh yea, and I posted the benchmark test code.

My list hasn't been fully updated because i ran out of time when I was working on it yesterday. I got a huge assignment due tomorrow for my SQL/Database Design class, so I gotta do that first before I can finish updating this : o. The API is out of date =P.

This was also tested against a super fast list on that was helped out with by jesus4lyf. This has the same speed iteration as that list, but it populates a load faster and creates a load faster =). Everything in this is very highly optimized and every method does not call any other method, so when you call something there are 0 internal calls. That is why this is so fast =).

Also azn, does your list have join and split?

aznricepuff · Oct 1, 2009

LinkedList API (part of it):

Code:

Instance Methods
================

Inherited From List:
-method addAll takes <TYPE_NAME>Collection collection returns nothing
-method enum takes <TYPE_NAME>_Enum enum, integer data returns nothing
-method isEmpty takes nothing returns boolean
-method iterator takes nothing returns <TYPE_NAME>Iterator
-method listIterator takes nothing returns <TYPE_NAME>ListTypeIterator
-method listIteratorByIndex takes integer index returns <TYPE_NAME>ListTypeIterator
-method removeAll takes <TYPE_NAME>Collection collection returns nothing
-method retainAll takes <TYPE_NAME>Collection collection returns nothing
-method size takes nothing returns integer
-method toArray takes nothing returns <TYPE_NAME>Array

------
method add takes <TYPE> toAdd returns boolean
------
Attempts to add an element to the end of this List. Returns true if the element was successfully 
added. This method is guaranteed to run in constant time.

Parameters:
-<TYPE> toAdd - the element to add to this List.

Returns:
true if the element was successfully added; false otherwise.

------
method addByIndex takes integer index, <TYPE> toAdd returns nothing
------
Attempts to add an element to this List at the specified index. The previous element at that 
index, if there is one, and any elements to the right will be shifted to the right (their 
indices are incremented up by one). This method does nothing if the index is out of bounds 
(index < 0 or index > List.size()). This method runs in O(n/2) time.

Parameters:
-integer index - the index at which to add the new element.
-<TYPE> toAdd - the element to add to this List.

------
method addFirst takes <TYPE> toAdd returns nothing
------
Adds the specified element to the beginning of this List. This method is guaranteed to run in 
constant time.

Parameters:
-<TYPE> toAdd - the element to add to the beginning of this List.

------
method addLast takes <TYPE> toAdd returns nothing
------
Adds the specified element to the end of this List. This method is guaranteed to run in constant 
time.

Parameters:
-<TYPE> toAdd - the element to add to the end of this List.

------
method clear takes nothing returns nothing
------
Removes all elements from this List. This method runs in O(n) time.

------
method contains takes <TYPE> element returns boolean
------
Checks if a certain element occurs at least once in this List. This method runs in O(n) time.

Parameters:
-<TYPE> element - the element for which to search in this List.

Returns:
true if the specified element is in this List; false otherwise.

------
method getByIndex takes integer index returns <TYPE>
------
Returns the element at the specified index. Returns 0 if there is no element at the index or 
if the index is out of bounds (index < 0 or index >= .size()). This method runs in O(n/2) time.

Parameters:
-integer index - the index of this List to access.

Returns:
The element at the specified index, or 0 if there is no element at that index or if the index is 
out of bounds.

------
method indexOf takes <TYPE> element returns integer
------
Returns the index of the first ocurrence of a certain element in this List. In other 
words, returns the lowest-valued integer i such that List.getByIndex(i) == element would be 
true. Returns -1 if there are no ocurrences of the specified element in this List. This method 
runs in O(n) time.

Parameters:
-<TYPE> element - the element for which to search in this List.

Returns:
The index of the first ocurrence of the specified element in this List, or -1 if there are 
no ocurrences of the specified element.

------
method lastIndexOf takes <TYPE> element returns integer
------
Returns the index of the last occurrance of the specified element in this List. In other words, 
returns the highest-valued integer i such that List.getByIndex(i) == element would return true. 
This method returns -1 if there are no occurrances of the specified element in this List. This 
method runs in O(n) time.

Parameters:
-<TYPE> element - the element for which to search in this List.

Returns:
The index of the last ocurrence of the specified element in this List, or -1 if there are 
no ocurrences of the specified element in this List.

------
method remove takes <TYPE> toRemove returns boolean
------
Attempts to remove the first ocurrence (the one with the lowest-valued index) of the specified 
element from this List. Returns true if the element was succesfully removed. Returns false if 
this list does not contain any ocurrences of the specified element. This method runs in O(n) 
time.

Parameters:
-<TYPE> toRemove - the element to remove from this List.

Returns:
true if the element was successfully removed; false otherwise.

------
method removeByIndex takes integer index returns $TYPE$
------
Attempts to remove and return the element at the specified index from this List. All elements 
to the right will be shifted to the left (their indices are decremented by one). This method 
returns 0 if there is no element at the specified index or if the index is out of bounds
(index < 0 or index >= .size()). This method runs in O(n/2) time.

Parameters:
-integer index - the index of the element to be removed.

Returns:
The element that was removed from this List, or 0 if no element was removed.

------
method setByIndex takes integer index, <TYPE> toSet returns <TYPE>
------
Replaces the element at the specified index in this List to the specified element. Returns the 
element previously located at the specified index. This method does nothing and returns 0 if the 
index is out of bounds (index < 0 or index >= .size()). This method runs in O(n/2) time.

Parameters:
-integer index - the index at which the replacement is to occur.
-<TYPE> toSet - the new element to be placed in the List.

Returns:
The element previously located at the specified index, or 0 if there was no such element or 
if the index is out of bounds.

------
method swap takes integer index1, integer index2 returns nothing
------
Swaps the elements located at two given indices. This method does nothing if either index is 
out of bounds (index < 0 or index >= .size()). This method runs in O(n) time.

Parameters:
-integer index1 - the index of the first element to be swapped
-integer index2 - the index of the second element to be swapped

Nestharus · Oct 1, 2009

What my List API will have-

JASS:

module List
    public static method new takes nothing returns List
    public method next takes nothing returns integer
    public method previous takes nothing returns integer
    public method push takes nothing returns integer
    public method unshift takes nothing returns integer
    public method pop takes nothing returns integer
    public method shift takes nothing returns integer
    public method remove takes thistype list returns nothing
    public method addPush takes thistype list returns integer
    public method addUnshift takes thistype list returns integer
    public method getFirst takes nothing returns integer
    public method getLast takes nothing returns integer
    public method clean takes nothing returns nothing
    
module RelateList
    public static method join takes List list1, List list2 returns List
    public method split takes integer index returns List

//! textmacro Iterate takes $name$, $type$
    public $type$ $name$
    public method count$name$ takes $type$ data returns integer
    public method purge$name$ takes $type$ data returns nothing
    public method has$name$ takes $type$ data returns boolean

There is no size because it'd only slow it down and no real need for size in my opinion. There's also no empty because a list is never empty O-o, it always has at least one element. You can also do hasNext to see if it has more than one element in it =P.

I tried to include all required methods and data for any list in the List Module, add practice join and split for the RelateList module, and practical iteration in the iteration macro. I split it into three so that you wouldn't have any extra code and could have exactly what you needed =).

Every method is self explanatory =). The parameters are self explanatory (you should know what they take) and the return is self explanatory (you should know what they return).

I'm not going to write any documentation on any of the methods. No need.

aznricepuff · Oct 2, 2009

There is no size because it'd only slow it down and no real need for size in my opinion.

Bounded stacks and queues....

There's also no empty because a list is never empty O-o, it always has at least one element

How is this at all true? When I create a new list, I expect there to be zero elements in it. (If you're talking about sentinel nodes, then first of all a linked list always has two of those, not one, and second of all those aren't public so they shouldn't affect the outside world's perception of the list being empty or not).

By the way, I'm writing code to benchmark this stuff. And I've noticed that there is no way I can iterate through your list, and therefore I cannot benchmark it. Also, I can't benchmark dequeues (front or back) because of a lack of a .size() method that tells me when to stop trying to dequeue things.

Nestharus · Oct 2, 2009

Bounded stacks and queues....

getNext == 0
getPrevious == 0

No need for size...

How is this at all true? When I create a new list, I expect there to be zero elements in it. (If you're talking about sentinel nodes, then first of all a linked list always has two of those, not one, and second of all those aren't public so they shouldn't affect the outside world's perception of the list being empty or not).

The first element is itself.. a list is its own list item... lol

By the way, I'm writing code to benchmark this stuff. And I've noticed that there is no way I can iterate through your list, and therefore I cannot benchmark it. Also, I can't benchmark dequeues (front or back) because of a lack of a .size() method that tells me when to stop trying to dequeue things.

You can iterate through the list just fine.
You can also do shift, unshift, pop, and push... you don't need a .size, that's a complete waste ><.

As for benchmarking, I don't think it's possible to get faster than my List thing =P. The iteration is 100% as fast as possible, population is I think as fast as possible, popping and shifting is I think as fast as possible, and so on.

And from a previous post

Um...no. The point of dequeue and pop is that they return whatever you removed since usually you don't just randomly remove something from a list and then forget about it.

That's 100% 100% 100% untrue... I wrote all of these methods except for 2 (addPush and addUnshift) based on traditional routines in standard programming.

pop removes the last element and returns the value
shift removes the first element and returns the value

Your way-
remove
set var
get var

Is slower...

aznricepuff · Oct 2, 2009

pop removes the last element and returns the value
shift removes the first element and returns the value

That's exactly what I said...and the only reason I had to do:

JASS:

    local integer lastIndex = list.getLastIndex()
    local integer element = list[lastIndex]
    call list.remove(lastIndex)

JASS:

    local integer firstIndex = list.getFirstIndex()
    local integer element = list[firstIndex]
    call list.remove(firstIndex)

was because you hadn't implemented pop or "shift" (I've never even heard of front end dequeuing referred to as shift before) and your remove method did not return what was being removed.

You can iterate through the list just fine.

How? Show me some code.

The first element is itself.. a list is its own list item... lol

Once again, that's like saying a list isn't empty because it has sentinel nodes in it.

aznricepuff · Oct 2, 2009

Ok, I'm going to double post because this has nothing to do with my last post.

I benchmarked ListOptimumSpeed, maskedpoptart's List, and my LinkedList. Operations I tested were: front/tail end enqueuing and dequeuing, forward and reverse iteration, and clear.

The results:

500 elements

1000 elements

2000 elements

Benchmarking done with StopWatch.

As you can see, in terms of speed: List > ListOptimizedSpeed > LinkedList, which is basically what I was expecting.

In general, List was 4x as fast as LinkedList at just about everything...WAY faster at .clear() and I don't know why it hits 0.000 seconds on front end dequeuing but not tail end dequeuing.

Once again, I could not test iteration and dequeuing on ListOptimizedSpeed. But List was twice as fast at enqueuing as ListOptimizedSpeed.

Nestharus · Oct 2, 2009

List Optimum is the best Linked List for wc3

Your tests for List Optimum aren't valid. You fudged them up hardcore.

MPT List-
create = .010
addLast = .019
next = .024

List Optimum-
new = .011
push = .021
next = .002

aznricepuff · Oct 2, 2009

JASS:

private function frontEndEnqueueList1 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list1.addFirst(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function frontEndEnqueueList2 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list2.addFirst(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function frontEndEnqueueList3 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list3.addUnshift(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function frontEndDequeueList1 takes nothing returns real
    local integer temp
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list1.isEmpty())
        set temp = list1.removeFirst()
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function frontEndDequeueList2 takes nothing returns real
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list2.isEmpty())
        set temp = list2.removeFirst()
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function frontEndDequeueList3 takes nothing returns real
    // ??
    return 0.0
endfunction

private function tailEndEnqueueList1 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list1.addLast(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndEnqueueList2 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list2.addLast(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndEnqueueList3 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        call list3.addPush(GetRandomInt(-0xfffffff, 0xfffffff))
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndDequeueList1 takes nothing returns real
    local integer temp
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list1.isEmpty())
        set temp = list1.removeLast()
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndDequeueList2 takes nothing returns real
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list2.isEmpty())
        set temp = list2.removeLast()
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndDequeueList3 takes nothing returns real
    // ??
    return 0.0
endfunction

private function iterateForwardList1 takes nothing returns real
    local IntegerListTypeIterator it
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    set it = list1.listIterator()
    loop
        exitwhen (it.hasNext() == false)
        set temp = it.next()
    endloop
    call it.destroy()
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateForwardList2 takes nothing returns real
    local integer temp
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= list2.size)
        set temp = list2[i]
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateForwardList3 takes nothing returns real
    // ????
    return 0.0
endfunction

private function iterateBackList1 takes nothing returns real
    local IntegerListTypeIterator it
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    set it = list1.listIteratorByIndex(list1.size())
    loop
        exitwhen (it.hasPrevious() == false)
        set temp = it.previous()
    endloop
    call it.destroy()
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateBackList2 takes nothing returns real
    local integer temp
    local integer stopWatch
    local integer i
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    set i = list2.size
    loop
        exitwhen (i <= 0)
        set temp = list2[i]
        set i = i - 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateBackList3 takes nothing returns real
    // ????
    return 0.0
endfunction

private function clearList1 takes nothing returns real
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    call list1.clear()
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function clearList2 takes nothing returns real
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    call list2.clear()
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function clearList3 takes nothing returns real
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    call list3.clean()
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

list1 is LinkedList, list2 is mpt's List, list3 is yours.

Nestharus · Oct 2, 2009

***List Optimum is the best Linked List for wc3***

Your tests for List Optimum aren't valid. You fudged them up hardcore.

MPT List-
create = .010
addLast = .019
next = .024

List Optimum-
new = .011
push = .021
next = .002

JASS:

scope Demo initializer Initialization
    globals
        integer sw
        //IntegerList list
        //List list
        real listMark
    endglobals
    
    private function Test1 takes nothing returns nothing
        local integer i = 0
        local integer b = 0
        set sw = StopWatchCreate()
        loop
            //only tested one thing at a time for 6 total tests : P, would edit, run, edit, run, edit, run ^_^
            //set list = List.new()
            //set list = list.create()

            //call list.addLast(i)
            //call list.push()

            //set b = list[i]
            //exitwhen i == list.size
            //set list = list.next
            //exitwhen list.next == 0

            //if not exitwhen, then use this code
            //set i = i + 1
            //exitwhen i == 2000
        endloop
        set listMark = StopWatchMark(sw)
        call StopWatchDestroy(sw)
    endfunction
    
    private function Test takes nothing returns boolean
        call ExecuteFunc(Test1.name)
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 1000, "List: " + R2S(listMark))
        return false
    endfunction
    
    private function Setup takes nothing returns nothing
        local integer i = 0
        loop 
            //call list.push()
            //call list.addLast(list.size)

            //set i = i + 1
            //exitwhen i == 2000
        endloop
    endfunction
    
    private function Initialization takes nothing returns nothing
        local trigger t = CreateTrigger()
        call TriggerRegisterTimerEvent(t, 1, false)
        call TriggerAddCondition(t, Condition(function Test))
        //set list = IntegerList.create()
        //set list = List.new()
        //call ExecuteFunc(Setup.name)
    endfunction
endscope

aznricepuff · Oct 2, 2009

How are they not valid? Give a reason.

Nestharus · Oct 2, 2009

Because you used the wrong methods...

It's just push(), pop(), unshift(), and shift()

The ones you used you ended up using totally wrong for 1 because you mis-understood them. They are used to add a new item at an index of a list...

1 2 3
addPush(2) -> 1 2 4 3
addUnshift(2) -> 1 4 2 3

They are much slower than push and unshift because they are linking everything up : |

remove() is much the same in that it removes a given list item-
remove(2) -> 1 3

pop and shift .... remove the last and first list items respectively and return the index they removed.
pop() = 3
remaining: 1 2

shift() = 1
remaining:
2 3

I think you need to read array methods =P. I actually wrote these based off of PERL ones because pushFront and pushBack seemed pretty dumb ;P.

aznricepuff · Oct 2, 2009

I used addPush and addUnshift for your List, which are the equivalent methods for addLast and addFirst. Simple push and unshift are NOT the correct equivalents, because unlike addLast and addFirst, they do not specify the value of the new element.

EDIT: Ok well I just saw the edit to your post. In any case, you will still need to set the new value once you've called push() in the test.

Nestharus · Oct 2, 2009

Well, I gotta write documentation on the new API.

Lists and list items are the exact same =). Push actually returns a new list item... the list item is whatever you want it to be.

Now, the default list struct inside will be this-

JASS:

struct List
    implement List
    //! runtextmacro ListIterator("int", "integer")
endstruct

So if you wanted to set the data-

JASS:

set list.int = value

Now, the reason for this is that List by itself has no idea what kind of data you will be using =). The default list includes an integer as a default type as well as a bundle of things for working with it.

So in essence, you can create your own types of lists two ways-

JASS:

struct MyList extends List
endstruct

JASS:

struct MyList
    implement List
endstruct

The list iterator methods would be this-

JASS:

//! runtextmacro ListIterator("name", "type")

That will create a public var of type and name : |. It will also make a bundle of iterator methods for it.

So, interestingly enough, if you wanted to test using every operation that other list pop and shift or w/e does =)

JASS:

    set list.push.int = 15
    
    set var = list.pop.int

The speed difference would be the array set =).

aznricepuff · Oct 2, 2009

List and list items aren't the same. List are the nodes. People don't really care about the nodes. They care about the elements they put inside the nodes. Nobody would just call push() a bunch of times to get new List instances. They would also want to do set list.int = value.

Nestharus · Oct 2, 2009

JASS:

So, interestingly enough, if you wanted to test using every operation that other list pop and shift or w/e does =)
    set list.push.int = 15

    set var = list.pop.int

The speed difference would be the array set =).

I edited it : P

Is that ok for ya? =D

Also, they can do

JASS:

set list.int = value

Lol. It sets the int of the list to the value =P

Look at my examples u >: O

list.name = valueOfType

aznricepuff · Oct 2, 2009

Ok, I just redid the test with the following code (for your List):

JASS:

private function frontEndEnqueueList3 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        set list3 = list3.unshift()
        set list3.int = GetRandomInt(-0xfffffff, 0xfffffff)
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndEnqueueList3 takes nothing returns real
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (i >= ELEMENT_COUNT)
        set list3 = list3.push()
        set list3.int = GetRandomInt(-0xfffffff, 0xfffffff)
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

The results barely changed for the enqueues. Your list is still 1.5-2x slower (~0.030-0.040 sec vs. ~0.010-0.020 sec for mpt's List for 2k iterations).

I still can't get dequeue or iteration to work for your List. Dequeue just doesn't work at all and when I try to iterate the loop always exits before I get to all 2000 elements. If you're wondering, my code is below:

JASS:

private function frontEndDequeueList3 takes nothing returns real
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set list3 = list3.getLast()
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list3.previous() == 0)
        set temp = List(list3.shift()).int
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function tailEndDequeueList3 takes nothing returns real
    local integer i = 0
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set list3 = list3.getFirst()
    set stopWatch = StopWatchCreate()
    loop
        exitwhen (list3.next() == 0)
        set temp = List(list3.pop()).int
        set i = i + 1
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateForwardList3 takes nothing returns real
    local integer temp
    local integer stopWatch
    local integer i = 0
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    set list3 = list3.getFirst()
    loop
        exitwhen (list3.next() == 0)
        set list3 = list3.next()
        set temp = list3.int
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

private function iterateBackList3 takes nothing returns real
    local integer temp
    local integer stopWatch
    local real time = 0.0
    
    set stopWatch = StopWatchCreate()
    set list3 = list3.getLast()
    loop
        exitwhen (list3.previous() == 0)
        set list3 = list3.previous()
        set temp = list3.int
    endloop
    set time = StopWatchMark(stopWatch)
    call StopWatchDestroy(stopWatch)
    return time
endfunction

Nestharus · Oct 2, 2009

Ok, I'm looking through MPT's list code...

For iteration-
impossible for MPT's list to compare with List Optimum Speed in speed, there's just no way from the reading to the setting it can't be done ><.

add/remove-
These actually move everything in the entire list o-o. Mine is pretty much same speed as push and unshift... add/remove is going to be insanely slow on MPT's list ><.

push/unshift/pop/shift-
Because the last element and the first element are always going to be the min and the max, these would actually be rather fast =). But as a result of this speed, add/remove are two useless methods that shouldn't even be used because of how slow they are (mass loops for the loss), so for pushing and unshifting, these should be about 1.5x faster I'd say, which works with your results as well.

So, when it boils down to it, the winners are-
add/remove (adding and removing of an arbitray list item):
List Optimum Speed: not comparable...

push/unshift/pop/shift (populating and remove first and last list items)-
MPT's List: 1.5x to 2x faster

iteration (reading and writing)-
List Optimum Speed: 6x+ faster

List Optimum Speed wins 2/3

Pushing, unshifting, popping, and shifting are pretty important and are commonly used, but iteration is the most important thing. This is the reason you can't build a linked list off of a hashtable, that's a really bad idea. It's going to suck at iteration every time.

aznricepuff · Oct 2, 2009

yes, I've seen your code. You've basically replicated how structs are allocated. So the only difference between this and using actual structs as nodes is that you bypass calls to constructors and destructors.

However, you get into trouble with using this stack method just like with structs:

JASS:

    call list.pop()
    set list2 = List.new()
    call list.next()

If I happened to pop off the List that the variable list is pointing to...I'm screwed when I call list.next().

And it doesn't matter that I'm calling GetRandomInt() in the test because I'm calling it for every list I'm testing. If I get rid of GetRandomInt(), your list will still be slower than mpt's.

EDIT:

Just did the test (front end enqueue) w/o GetRandomInt():

yours: 0.29-0.37
mpt's: 0.15-0.19

Btw, your push has 7 array gets/sets and 1 boolean check. Mpt's has 1 array get, 1 array set, and one hashtable insertion. Benchmarks on wc3c put hashtable insertion at 1.5-2x slower than an array get, so his is the equivalent of 3.5-4 array get/sets.

2ND EDIT:

Btw, I noticed your shift and pop methods don't update the .previousIndex/.nextIndex of the new first/last nodes to 0. Moreover you don't reset .previousIndex and .nextIndex when you recycle your nodes. I fixed that and that finally got iteration working. Tail end dequeuing still refuses to work.

Nestharus · Oct 2, 2009

I edited the previous post before u posted, so read it u =P

list.pop() without any list item would put 0 into the freed indexes stack. The reason for this is that .list is never set for the master list because the master list is always .list. The only way to pop off a master list is to do .clean().

Now, the issue here is that 0 is put into the freed indexes stack : |. That wouldn't cause a problem on the first use, but on the second use that'd be bad ^_^.

JASS:

    call list.pop()
    set list2 = List.new()
    call list2.pop()
    set list3 = List.new()
    call list2.next()

list3 would overwrite list2 thus causing a memory leak =). It would only happen every other use of .pop on an empty list.

This would be considered the map maker's blunder, not mine ^_^. I could write a debug saftey check, but I'm never going to write a safety check that's always on =).

Mine is still faster on add/remove and iteration, but you are right (I say this in previous post too) that pop/shift/push/unshift are slower =P.

What's more important, actual iteration through data or populating first and last index?

aznricepuff · Oct 2, 2009

What's more important, actual iteration through data or populating first and last index?

Depends on what you are doing. If you are using it as a pure stack/queue (i.e. you just throw elements into the list and don't care about them until you remove) you're never going to iterate through the list at all. But if you are using it as some kind of...well...linked list (i.e. storing a bunch of event listeners to iterate through on events) then iteration becomes more important since the other stuff won't really need to be in real time.

And about the pop thing I was talking about this:

JASS:

    // list holds value of 5
    call list.pop() // the list's last node happens to be indexed 5, therefore index 5 is recycled and put into the allocation stack
    call List.new() // new() picks off the top index from the allocation stack, which is index 5. The node indexed 5 is now in a new list.
    call list.next() // I expect this to give me the next node in the original list (i.e. the one that popped a node off from two lines ago), but instead this gives me the next node in the new list (which should be 0) because list still holds the value 5.

In actuality you didn't reset .nextIndex and .previousIndex when deallocating those indices (which caused more bugs) so technically the above wouldn't have caused any problems. But if I were to push something onto the new list before calling next() on list then the same problem arises.

EDIT:

By the way, mpt's list is actually a pseudo-array list with optimized addition/removal to the front and back of the list, not an actual linked list. And implementing a linked list using a hashtable doesn't slow down iteration by much...a hashtable search is 1.5-2x an array get. So you would have basically either 1.5-2x if you're saving elements directly into the hashtable or 2.5-3x if you're using the hashtable to save struct nodes. With direct array accessing it's going to be 2x: one for the array get for the next node and one for the array get to get w/e value you care about from the node.

Nestharus · Oct 2, 2009

So I guess my linked list is the best possible implementation if you care about iteration

MPT's is the best possible implementation if you care about population

Now, on to the agenda-
I'll break off the link ; ).

list.pop-
.previous.next = 0
.previous = 0

list.shift
.next.previous = 0
.next = 0

Easy fixes easy fixes ^_^.

By the way, add/remove is still super bad for MPT's list =P.

aznricepuff · Oct 2, 2009

You would need to do it anytime you deallocate. Including in remove and clean (and btw, your clean was allowing index 0 to be put into the allocation stack...multiple times in fact). And

JASS:

    // list holds value of 5
    call list.pop() // the list's last node happens to be indexed 5, therefore index 5 is recycled and put into the allocation stack
    call List.new() // new() picks off the top index from the allocation stack, which is index 5. The node indexed 5 is now in a new list.
    call list.next() // I expect this to give me the next node in the original list (i.e. the one that popped a node off from two lines ago), but instead this gives me the next node in the new list (which should be 0) because list still holds the value 5.

Will always be a problem unless you separate the List structure from the nodes (i.e. not have a recursive definition of List).

Nestharus · Oct 2, 2009

Well, I'll fix up clean and clear ^_^, then it should be fine : D. And whenever I remove the first element or the last element, I'll be sure to break the active elements off from it.

so pop and shift are fine in current version
clear and clean will be fine soon =P

And clean allowing index 0 to be put into the the stack multiple times... now that's odd o-o. Oh well, will all be fixed ^_^.

I think everyone's also going to be happy with the new layout and with the new module too. This will include Collections, which are very simple and super fast pieces of data.

Collections don't have any defined order, so they are really good when the order doesn't matter. The iteration should be a faster than this iteration speed (hard to believe huh).

Collections will include-
methods: push, pop, remove
operators: [], []=, last

In essence, this is the fastest possible thing there is.

push adds to the top
pop removes from the top and returns the value
remove - removes a given index and returns the value. The removed index is set to the last index and the size is reduced.
[] - translates into just Collection(index) or array[], which returns the actual value
[]= translates into set array[] = value
last- translates into lastIndex

This is code that I write all the time and is the exact same speed as an array with an added remove.

Everything except for remove is inlined, which is ok. Remove in a cJASS version will be inlined as well : |. You can even do it by hand as all the elements will be public (remove is 3 lines).

The overall code hit this will have is 11 lines-
function, endfunction, 3 lines inside
function, endfunction, 2 lines inside
2 var lines

In short, you can pretty much use this instead of an array every time if you don't care about order and it'll keep it indexed ^_^.

If you remove the last element, then just do like .last = .last - 1 and that's it =).
If you want the value, then get the value =P. Removing the last element is 2 lines, removing an inner element is 3 lines. Remove does not work on the last element =O.

aznricepuff · Oct 2, 2009

Ok, as a future note, you don't need to explain everything you plan to update. When it's updated, it's updated, and people can see then what changed.

Also, I don't think you understand what a queue is. You add things to the back of a queue and take things out from the front (FIFO), not add and remove both from the front (which would just be a stack).

And please change the name of shift and unshift (I'd rather you change push and pop too but at least those are commonly used terms).

Oh and personally I would rather have simpler code than brutal efficiency (i.e. if I can do it in one line rather than in 3 or in a way that makes way more sense intuitively at the cost of some speed, I would do it that way every time).

Nestharus · Oct 3, 2009

Oh and personally I would rather have simpler code than brutal efficiency (i.e. if I can do it in one line rather than in 3 or in a way that makes way more sense intuitively at the cost of some speed, I would do it that way every time).

List is done in single lines

vJASS version of collection can't be single lines. It wouldn't be just a small loss of speed but a major loss : \. In a cJASS version, it would be possible to convert it into one line of code. Implementation would also look nicer =).

Should I convert List Optimum Speed into cJASS? : o.

aznricepuff · Oct 3, 2009

I don't like cJASS. I think trying to make JASS's syntax into C(++) is a bad idea. It's like if someone got tired of coding things in Ruby and decided to make a preprocessor to make syntax more like Java or C#. They're two completely different languages...don't try to force a language's syntax onto something else. cJASS is also nowhere near a standard...not even de facto (unlike vJASS). That being said, I will not accept pure cJASS scripts. If you want to include both a normal JASS/vJASS version and a cJASS version, that's fine though.

Nestharus · Oct 3, 2009

That's how pretty much everyone feels =). Guess you'll just have to deal with the 2 calls then instead of 1 on Collections =). No way around it.

Sweet New News ^^
So, I've been working on the new release of List Optimum Speed. The latest release is all written in cJASS, but here's a peak at some of the features ^_-.

Easier To Use/Better Collections-
Collections can primarily be used to control struct allocation and deallocation for inlining and the ultimate performance ; ).

JASS:

struct C extends array {
    implement Collection

    public thistype create() {
        new Collection //inlined!
    }

    public void destroy() {
        destroy Collection //inlined!
    }
}

destroy can also take an index and even a struct name. new can also take a struct name and a var to be set to if you want to do some ini ; ).

Statistic Lists-
In short, these lists merge up common values into single list items. They don't maintain order, but they are rad fast and take up very little memory ; ).

There are two types of statistical lists. First there are generated statistical lists. These lists are generated from plain lists. When it's generated, you can do quick analysis and so on. Generation is somewhat slow as a lot is done, but you could go through all values and get their indexes in the list and instances and so on ^_^. This uses hashtables.

The other type is a plain statistic list. When you add new data into it, it stores it into an index for that data and increments the counter for that data by 1. Because it does this, it uses hashtables ^_-.

IterateList-
Iterate list is for special list operations-
joining-
joins two lists

splicing-
splices two lists

cloning-
clones a list (one value only, but you define the var)

count-
counts values of a list (you determine variable, it counts values of it)

purge-
removes all list items where variable equals value (you determine var, will cause issues with multiple vars)

grep-
get a list of values for a var from a given list. You determine the var and the filter.

example:
if List.GetFilterData > 6 {return true} return false

Fun times

The brand new c list implementation will be available soon : D, I just gotta debug it and possibly add sort. I'm still seriously debating sort. I also have to fix up a few things to prevent collisions (multiple collections within a struct), tie in collections with parent structures, and yea. I might also have to re-organize some of it, but so far looking fantastic. I'll probably ask for a group of volunteers to check it out before doing a public release (though I'm not yet sure where I'll release it).

Maybe this awesome cJASS utility will give some incentive eh? : D.

If there are any other features anyone's looking for, feel free to let me know ^_-. I don't think anyone else has actually done a grep command, so List Optimum Speed will probably be the only one with it : D.

Of all the new features, grep and clone are probably the coolest : D. They use techniques that were initially designed in a framework called AGL.

Here is an example of grep in action-

JASS:

library Test initializer Initialization {
    private struct MyList extends array {
        int data
        implement IterateList
    }
    
    trigger myFilter = CreateTrigger()
    trigger mySet = CreateTrigger()
    MyList myList1
    MyList myList2
    
    bool Filter() {
        if MyList.filter.data >= 4 && MyList.filter.data <= 12 {
            return true
        }
        return false
    }
    
    bool Clone() {
        MyList.cloneList.data = MyList.filter.data
        MyList.filter.remove() //just to show we can remove it if we wanted to
        return false
    }
    
    void Initialization() {
        TriggerAddCondition(myFilter, Condition(function Filter))
        TriggerAddCondition(mySet, Condition(function Clone))
        myList1 = MyList.create()
        myList1.push.data = 13
        myList1.push.data = 13
        myList1.push.data = 9
        myList1.push.data = 4
        myList1.push.data = 12
        myList1.push.data = 1042
        myList1.push.data = 6
        myList1.push.data = 4
        myList1.push.data = 1042
        myList1.push.data = 139
        myList2 = myList1.grep(myFilter, mySet)
    }
}

Still a few things that I need to fix over-all in the system. Some design issues really.

1. If you remove an element via grep or splice or whatever from a given list and put it into another list, that other list is returned. The issue is you don't know which element is removed. If your list var was set to that element, suddenly you lose track of the list and the list is lost. In this way, I believe both lists have to be returned to ensure that you retain everything with a new operator-

manipulated

And it would work like this using the example from above-
myList2 = myList1.grep(myFilter, mySet)
myList1 = MyList.manipulated //returns the first index of the list that was acted on

Another issue is if all list items from a given list are removed, the return value would be 0. Well, if a list is empty, a new list item is inserted ^_^. Lists cannot be empty, or the system just can't work : (. The reason is because initially, the system looks for a .list. Yes, I could put it into the list object in the background, but I split up the collections. Why? So that you could have more instances, 8191 total lists and 8191 total list items. Originally they were both the same sort of object, but yea... limited your instance count for no good reason : P.

So that's the news everyone : D. Oh yea, and if you want to be a volunteer and get your hands on this system (the premier full out collections utility for JASS), uhm... let me kno kk : D.

Collections 1.0 Pre-Release put up, the new face of List Optimum Speed in cJASS style

azlier · Feb 1, 2010

The documentation is misleading. This isn't the fastest list ever. Sure, it may be the fastest list to have all those methods ever, but this still beats yours in speed:

JASS:

struct Node
    Node next
endstruct

Please fix your documentaion.

Nestharus · Feb 3, 2010

Sure thing ; ). I've been meaning to update the Collections lib, but I've wanted to make the update go through a preprocessing lib to increase efficiency and readability : ).

azlier · Feb 3, 2010

And you know what I hate most about this? I can't make the simplest of lists that use next and next= with it. Gah. There goes simplicity.

Nestharus · Feb 3, 2010

And you know what I hate most about this? I can't make the simplest of lists that use next and next= with it. Gah. There goes simplicity.

Read that and decided to do another rewrite... it'll make this way more advanced and pro and offer more layers and will let you do exactly what you want to do =).

So first rewrite offered more power and flexibility, but still didn't give quite enough to go down into the various operations.

Here's an example of the power of this one >: o..

JASS:

/*Dynamic Memory
===================================================================
Allocation:
thisMemory = (freedMemorySpaceSize > 0) ? freedMemorySpace[--freedMemorySpaceSize] : memory++

Deallocation:
freedMemorySpace[freedMemorySpaceSize++] = thisMemory

Beginner API:
    module DynamicMemoryStruct
        public static method new takes nothing returns thistype
        public method delete takes nothing returns nothing
        
Standard API:
    module DynamicMemory
    module TryDynamicMemoryGetFreed
    module TryDynamicMemoryGetNew
    module CatchDynamicMemoryGet
    module TryFreeDynamicMemory
    
    module TryGetDynamicMemory
        implement TryDynamicMemoryGetFreed
        implement TryDynamicMemoryGetNew
        implement CatchDynamicMemoryGet

Developer API:
    //! textmacro DYNAMIC_MEMORY takes NAMESPACE
    //! textmacro TRY_DYNAMIC_MEMORY_GET_FREED takes NAMESPACE, TO_MEMORY
    //! textmacro TRY_DYNAMIC_MEMORY_GET_NEW takes NAMESPACE, TO_MEMORY
    //! textmacro CATCH_DYNAMIC_MEMORY_GET takes RETURN_ERROR
    //! textmacro TRY_DYNAMIC_MEMORY_FREE takes NAMESPACE, FROM_MEMORY, RETURN_ERROR
===================================================================*/

Dynamic or Recycled memory is normally used for instancing structs. As you can see you can go all the way down to declaring namespaces within your struct. The namespaces allow your structs to have different collections within them. The standard layer lets you work differently with previous freed or brand new instances or you can go with simplistic version, which is default. The simplest command just implements everything ; ).

Edit
Updating the List stuff isn't that big of a deal apparently, heh... just adding a few *very* simple elements...

JASS:

DEBUG_throwOverflowError
DEBUG_throwOutOfBoundsError
DEBUG_throwListOnlyOperationError
DEBUG_throwNodeOnlyOperationError

$NAMESPACE$TryTo

PUSH takes NAMESPACE, PUSHED_NODE, NODE
POP takes NAMESPACE, NODE
UNSHIFT takes NAMESPACE, SHIFTED_NODE, NODE
SHIFT takes NAMESPACE, NODE

So really... you can construct w/e the heck you want : ). What you were asking for earlier Azlier was just so simple : (.

Nestharus · Feb 8, 2010

azlier · Feb 8, 2010

Why did you capitalize those method operators?

Nestharus · Feb 8, 2010

$NAMESPACE$Next

that be why ; p

default namespace is "", so it'd just be Next, but if you had a namespace, it'd be like testNext

No way to fix that unless it was in cJASS

Anyways, this now has the fastest and most powerful single and doubly linked list implementations for wc3 ;o. Yes, 7.0 introduces singly linked lists ; O.

azlier · Feb 10, 2010

Sigh. Since I apparently can't spot anything wrong, I guess it's approvallowzizzled.

Nestharus · Feb 10, 2010

updated

Nestharus · Apr 20, 2010

Updated with rewrites

Does not work with AdicHelper as of 1.4.2.7 (29.03.2010)

edit
Going to be redesigning dequeues and stacks to follow single head design for faster iteration speed.

JASS:

//this == head
//node1 == moving node1
//node2 == moving node2
//toNode1 == moving to after toNode1
//toNode2 == moving to before toNode2
//...<-toNode1<->node1<->...<->node2<->toNode2->...

//if 0
//0<-node1<->...<->node2->0
//node2<-head->node1

set node1.previous = toNode1
set node2.next = toNode2

if node1.previous == 0 then //set head's next
    set next = node1
else //finish link
    set toNode1.next = node1
endif

if node2.next == 0 then //set head's previous
    set previous = node2
else //finish link
    set toNode2.previous = node2
endif

Nestharus · Apr 26, 2010

Changes
Ok, made loads of changes and planning to make a few more.

Dequeues

Made a special style of malloc for dequeues
Changed dequeue design to single head
Moved to spiffy link style operations
Added pop, push, shift, and unshift operations for dequeue

Dmalloc

includes allocate, allocateCount, and deallocate(node1, node2)
2 fields instead of the standard 3
freed instances are stored in a sort stack instead of a freed array to take advantage of the links. .previous and .next are updated etc, but it works like a stack. This allows large numbers of nodes to be deallocated without a loop.

Planned additions-

SMalloc, or special malloc for Stacks
Queue

Differences between these collections and others
These collections specialize in ranged operations. If you are only dealing with single operations and never plan on dealing with ranges, these collections aren't for you as they end up performing extra operations on deallocate.

I believe that these are the only collections at the moment on any of the sites that do specialize in range operations, so this shouldn't be in the graveyard ; P.

I could add more that specialize in single operations and follow the same design style as these things if people want, but there are already tons of things out there that do single operations.

This follows a unique 3 layer design style.

Layer 1 is probably the layer most people would use and is just like any other library you might use, implement the module and use the methods.

Layer 2 is used for writing methods, which can then be packed into a module.

Layer 3 is used for writing modules, which can be packed into methods, which can be packed into a single module.

Bribe · Jun 21, 2011

So far you've written about 156 libraries which don't require this. This doesn't even look like a serious library due to its obscurity and lack of any definable purpose, and looks more obsolete than anything. Why use this?

Magtheridon96 · Jun 21, 2011

Then Graveyard it

This is the ugliest library I've ever seen >:S
Textmacros are REALLY ugly if you don't use them right

Nestharus · Jun 21, 2011

eh, I just code lists etc from scratch.

It is currently the fastest lib for these structures =)

Magtheridon96 · Jun 21, 2011

If you change it to a template rather than a system, it would be very useful for people who want to use this kind of structure ^^ (Maybe you can make a tutorial)

[Snippet] List Optimum Speed

500 elements

1000 elements

2000 elements

Attachments