[Containers] List<T>

Level 24
Joined
Mar 19, 2008
Messages
3,136
Implementation of double-linked list. Yeah, there were ton of lists already, yet this time its almost complete implementation of list from c++ containers std. Bigger brother of ForwardList<T>.

Adds lot of additional functionality when working with lists. Allows to sort list using top-down merge sort. Code for sort algorithm won't be implemented if no comparator is provided. Default comparators exist only for integers and reals.

Current implementation involves no Table/hashtable. This highly limits the number of lists and especially, nodes. I will upload Table version shortly which allows to create basically unlimited (Table instance limit) lists for given type with just one struct per type.

Implementation of generic double-linked list. Usefull especially when map is packed with spells, each implementing it's own list structure. Template functionality is provided via Table thus it's slower than array-based list implementation, yet as stated, it allows you to create one list type for entire map effectively preventing globals declaration spam. Adds STRUCT-type support for intuitive syntax.

Most of the functions are inline-friendly, thus the actual code size is greatly reduced, even though scrypt by itself isn't big either.

JASS:
/*****************************************************************************
*
*    List<T> v2.1.2.3
*       by Bannar
*
*    Doubly-linked list.
*
******************************************************************************
*
*    Requirements:
*
*       Table by Bribe
*          hiveworkshop.com/threads/snippet-new-table.188084/
*
*       Alloc - choose whatever you like
*          e.g.: by Sevion hiveworkshop.com/threads/snippet-alloc.192348/
*
******************************************************************************
*
*    Implementation:
*
*       macro DEFINE_LIST takes ACCESS, NAME, TYPE
*
*       macro DEFINE_STRUCT_LIST takes ACCESS, NAME, TYPE
*
*          ACCESS - encapsulation, choose restriction access
*            NAME - name of list type
*            TYPE - type of values stored
*
*     Implementation notes:
*
*       - DEFINE_STRUCT_LIST macro purpose is to provide natural typecasting syntax for struct types.
*       - <NAME>Item structs inline directly into hashtable operations thus generate basically no code.
*       - Lists defined with DEFINE_STRUCT_LIST are inlined nicely into single create method and single integer array.
*
******************************************************************************
*
*    struct API:
*
*       struct <NAME>Item:
*
*        | <TYPE> data
*        | <NAME>Item next
*        | <NAME>Item prev
*
*
*       General:
*
*        | static method create takes nothing returns thistype
*        |    Default ctor.
*        |
*        | static method operator [] takes thistype other returns thistype
*        |    Copy ctor.
*        |
*        | method destroy takes nothing returns nothing
*        |    Default dctor.
*        |
*        | method empty takes nothing returns boolean
*        |    Checks whether the list is empty.
*        |
*        | method size takes nothing returns integer
*        |    Returns size of a list.
*
*
*       Access:
*
*        | readonly <NAME>Item first
*        | readonly <NAME>Item last
*        |
*        | method front takes nothing returns $TYPE$
*        |    Retrieves first element.
*        |
*        | method back takes nothing returns $TYPE$
*        |    Retrieves last element.
*
*
*       Modifiers:
*
*        | method clear takes nothing returns nothing
*        |    Flushes list and recycles its nodes.
*        |
*        | method push takes $TYPE$ value returns thistype
*        |    Adds elements to the end.
*        |
*        | method unshift takes $TYPE$ value returns thistype
*        |    Adds elements to the front.
*        |
*        | method pop takes nothing returns thistype
*        |    Removes the last element.
*        |
*        | method shift takes nothing returns thistype
*        |    Removes the first element.
*        |
*        | method find takes $TYPE$ value returns $NAME$Item
*        |    Returns the first node which data equals value.
*        |
*        | method erase takes $NAME$Item node returns boolean
*        |    Removes node from the list, returns true on success.
*        |
*        | method removeElem takes $TYPE$ value returns thistype
*        |    Removes first element that equals value from the list.
*
*
*****************************************************************************/
library ListT requires Table, Alloc

//! runtextmacro DEFINE_LIST("", "IntegerList", "integer")
// Run here any global list types you want to be defined.

//! textmacro_once DEFINE_LIST takes ACCESS, NAME, TYPE
$ACCESS$ struct $NAME$Item extends array
    // No default ctor and dctor due to limited array size

    method operator data takes nothing returns $TYPE$
        return Table(this).$TYPE$[-1] // hashtable[ node, -1 ] = data
    endmethod
    method operator data= takes $TYPE$ value returns nothing
        set Table(this).$TYPE$[-1] = value
    endmethod

    method operator next takes nothing returns thistype
        return Table(this)[-2] // hashtable[ node, -2 ] = next
    endmethod
    method operator next= takes thistype value returns nothing
        set Table(this)[-2] = value
    endmethod

    method operator prev takes nothing returns thistype
        return Table(this)[-3] // hashtable[ node, -3 ] = prev
    endmethod
    method operator prev= takes thistype value returns nothing
        set Table(this)[-3] = value
    endmethod
endstruct

$ACCESS$ struct $NAME$ extends array
    readonly $NAME$Item first
    readonly $NAME$Item last
    private integer count

    implement Alloc

    private static method setNodeOwner takes $NAME$Item node, $NAME$ owner returns nothing
        set Table(node)[-4] = owner
    endmethod

    private static method getNodeOwner takes $NAME$Item node returns thistype
        return Table(node)[-4]
    endmethod

    private method createNode takes $TYPE$ value returns $NAME$Item
        local $NAME$Item node = Table.create()
        set node.data = value
        call setNodeOwner(node, this) // ownership
        return node
    endmethod

    private method deleteNode takes $NAME$Item node returns nothing
        call Table(node).destroy() // also removes ownership
    endmethod

    static method create takes nothing returns thistype
        local thistype this = allocate()
        set count = 0
        return this
    endmethod

    method clear takes nothing returns nothing
        local $NAME$Item node = first
        local $NAME$Item temp

        loop // recycle all Table indexes
            exitwhen 0 == node
            set temp = node.next
            call deleteNode(node)
            set node = temp
        endloop

        set first = 0
        set last = 0
        set count = 0
    endmethod

    method destroy takes nothing returns nothing
        call clear()
        call deallocate()
    endmethod

    method front takes nothing returns $TYPE$
        return first.data
    endmethod

    method back takes nothing returns $TYPE$
        return last.data
    endmethod

    method empty takes nothing returns boolean
        return count == 0
    endmethod

    method size takes nothing returns integer
        return count
    endmethod

    method push takes $TYPE$ value returns thistype
        local $NAME$Item node = createNode(value)

        if not empty() then
            set last.next = node
            set node.prev = last
        else
            set first = node
            set node.prev = 0
        endif

        set last = node
        set node.next = 0
        set count = count + 1
        return this
    endmethod

    method unshift takes $TYPE$ value returns thistype
        local $NAME$Item node = createNode(value)

        if not empty() then
            set first.prev = node
            set node.next = first
        else
            set last = node
            set node.next = 0
        endif

        set first = node
        set node.prev = 0
        set count = count + 1
        return this
    endmethod

    method pop takes nothing returns thistype
        local $NAME$Item node

        if not empty() then
            set node = last
            set last = last.prev

            if last == 0 then
                set first = 0
            else
                set last.next = 0
            endif

            call deleteNode(node)
            set count = count - 1
        debug else
            debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::pop failed for instance "+I2S(this)+". List is empty.")
        endif
        return this
    endmethod

    method shift takes nothing returns thistype
        local $NAME$Item node

        if not empty() then
            set node = first
            set first = first.next

            if first == 0 then
                set last = 0
            else
                set first.prev = 0
            endif

            call deleteNode(node)
            set count = count - 1
        debug else
            debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::shift failed for instance "+I2S(this)+". List is empty.")
        endif
        return this
    endmethod

    static method operator [] takes thistype other returns thistype
        local thistype instance = create()
        local $NAME$Item node = other.first

        loop
            exitwhen node == 0
            call instance.push(node.data)
            set node = node.next
        endloop

        return instance
    endmethod

    method find takes $TYPE$ value returns $NAME$Item
        local $NAME$Item node = first
        loop
            exitwhen node == 0 or node.data == value
            set node = node.next
        endloop
        return node
    endmethod

    method erase takes $NAME$Item node returns boolean
        if getNodeOwner(node) == this then // match ownership
            if node == first then
                call shift()
            elseif node == last then
                call pop()
            else
                set node.prev.next = node.next
                set node.next.prev = node.prev
                call deleteNode(node)
                set count = count - 1
            endif
            return true
        debug else
            debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::erase failed for instance "+I2S(this)+". Attempted to remove invalid node "+I2S(node)+".")
        endif
        return false
    endmethod

    method remove takes $NAME$Item node returns boolean
        debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Method $NAME$::remove is obsolete, use $NAME$::erase instead.")
        return erase(node)
    endmethod

    method removeElem takes $TYPE$ value returns thistype
        local $NAME$Item node = find(value)
        if node != 0 then
            call erase(node)
        endif
        return this
    endmethod
endstruct
//! endtextmacro

//! textmacro_once DEFINE_STRUCT_LIST takes ACCESS, NAME, TYPE
$ACCESS$ struct $NAME$Item extends array
    // Cannot inherit methods via delegate due to limited array size
    method operator data takes nothing returns $TYPE$
        return IntegerListItem(this).data
    endmethod
    method operator data= takes $TYPE$ value returns nothing
        set IntegerListItem(this).data = value
    endmethod

    method operator next takes nothing returns thistype
        return IntegerListItem(this).next
    endmethod
    method operator next= takes thistype value returns nothing
        set IntegerListItem(this).next = value
    endmethod

    method operator prev takes nothing returns thistype
        return IntegerListItem(this).prev
    endmethod
    method operator prev= takes thistype value returns nothing
        set IntegerListItem(this).prev = value
    endmethod
endstruct

$ACCESS$ struct $NAME$ extends array
    private delegate IntegerList parent

    static method create takes nothing returns thistype
        local thistype this = IntegerList.create()
        set parent = this
        return this
    endmethod

    method front takes nothing returns $TYPE$
        return parent.front()
    endmethod

    method back takes nothing returns $TYPE$
        return parent.back()
    endmethod
endstruct
//! endtextmacro

endlibrary
Demo:
JASS:
//! runtextmacro DEFINE_STRUCT_LIST("", "ListOfLists", "IntegerList")

struct test_list extends array

    static method print takes IntegerList list, string prefix returns nothing
        local IntegerListItem node = list.first
        local string s = ""
        loop
            exitwhen node == 0
            set s = s + " " + I2S(node.data)
            set node = node.next
        endloop
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, prefix + s)
    endmethod

    static method test_list takes nothing returns nothing
        local IntegerList list = IntegerList.create()
        local IntegerList list2 = IntegerList.create()
        local IntegerList list3 = IntegerList.create()
        local ListOfLists lol = ListOfLists.create()

        call list.push(55).push(3).push(88).push(0).push(-10).push(1).push(17).push(-1).push(26)
        call list2.push(4).push(55).push(0).push(13).push(7)
        call list3.push(1).push(2).push(2).push(3).push(3).push(2).push(1).push(1).push(2)
        call lol.push(list).push(list2).push(list3)

        call print(list, "List1: ")
        call print(list2, "List2: ")
        call print(list3, "List3: ")

        call list.shift().pop()
        call list2.erase(list2.find(0))

        call print(list, "\nList1: ")
        call print(list2, "List2: ")
        call print(list3, "List3: ")
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "ListOfLists front has size of " + I2S(lol.front().size()))
    endmethod

    static method onInit takes nothing returns nothing
        call TimerStart(CreateTimer(), 2, false, function thistype.test_list)
    endmethod

endstruct
 
Last edited:
Level 24
Joined
Mar 19, 2008
Messages
3,136
Updated to 1.0.1.0 yet immidiately after I've found even better solution to my problem thus here we got 1.0.2.0.

When reading one of TriggerHappy's post I realised that I've cimpletely forgotten about implement optional for modules. In such case we can greatly improve the interaction between user and the interface:

Initialy:
JASS:
struct MyList extends array
    //! runtextmacro DEFINE_LIST("MyList", "integer", "0")
endstruct

struct MyStringList extends array
    static method compare_string takes string a, string b returns integer
        if ( a == b ) then
            return 0
        elseif ( StringLength(a) < StringLength(b) ) then
            return -1
        else // ( a > b )
            return 1
        endif
    endmethod
    //! runtextmacro DEFINE_LIST("MyStringList", "string", "\"\"" )
endstruct
To this:
JASS:
module CompareStrings
    static method compare_string takes string a, string b returns integer
        if ( a == b ) then
            return 0
        elseif ( StringLength(a) < StringLength(b) ) then
            return -1
        else // ( a > b )
            return 1
        endif
    endmethod
endmodule

//! runtextmacro DEFINE_LIST("MyStringList", "string", "\"\"", "CompareStrings" )

//! runtextmacro DEFINE_LIST("MyList", "integer", "0","")
And eventually:
JASS:
module CompareStrings
    // notice that "_$TYPE$" for compare method is no longer needed
    static method compare takes string a, string b returns integer
        if ( a == b ) then
            return 0
        elseif ( StringLength(a) < StringLength(b) ) then
            return -1
        else // ( a > b )
            return 1
        endif
    endmethod
endmodule

//! runtextmacro DEFINE_LIST("MyStringList", "string", "\"\"", "CompareStrings" )

//! runtextmacro DEFINE_LIST("MyList", "integer", "0","")
JASS:
    private static constant boolean DEFINED_LIST_$TYPE$ = true

    static if not thistype.compare_$TYPE$.exists then

        static if thistype.DEFINED_LIST_integer then
            private static method compare_integer takes integer a, integer b returns integer
                if ( a < b ) then
                    return -1
                elseif ( a == b ) then
                    return 0
                else // ( a > b )
                    return 1
                endif
            endmethod
        elseif thistype.DEFINED_LIST_real then
            private static method compare_real takes real a, real b returns integer
                if ( a < b ) then
                    return -1
                elseif ( a == b ) then
                    return 0
                else // ( a > b )
                    return 1
                endif
            endmethod
        endif

    endif
To this:
JASS:
// Default integer & real comparators
//! textmacro_once DEFINE_DEFAULT_COMPARATOR takes TYPE
library_once $TYPE$DefaultComparator
    module $TYPE$DefaultComparator
        static method compare takes $TYPE$ a, $TYPE$ b returns integer
            if ( a < b ) then
                return -1
            elseif ( a == b ) then
                return 0
            else // ( a > b )
                return 1
            endif
        endmethod
    endmodule
endlibrary
//! endtextmacro

//! runtextmacro DEFINE_DEFAULT_COMPARATOR("integer")
//! runtextmacro DEFINE_DEFAULT_COMPARATOR("real")

// (...)

    implement optional $COMPARATOR$
    static if not thistype.compare.exists then
        static if LIBRARY_$TYPE$DefaultComparator then
            implement optional $TYPE$DefaultComparator
        endif
    endif
This method, however, increases argument count for DEFINE_LIST macro from 3 to 4, yet in my opinion it is worth the cost. User can always provide "" to ignore the sort interface.
Method compare within such module must not be private.

Macro as of now declares library with name given by $NAME$ that contains structs for node and list manipulation. No longer generates function prototypes due to struct $NAME$Node being at the top instead of the bottom of the code block.
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
Guys, what do you thing about adding "ADVANCE" parameter to the DEFINE_ macro? It would split list between lite and heavy versions. Some might not use whole potential of this lib thus this implements ton of code they'd never use.
Whats going in my mind:

- ADVANCE (false) -> create, clear, destroy, pushBack/Front, popBack/Front findNode, delete node and of course inliners: front, back, count & size.
- ADVANCE (true) -> everything

The next thing: "OBJECT" (lists/arrays/vecs etc of structs).
All of my <T> take for granted that object value which is going to be added into the container, is .create()-ed with whatever constructor. This is due to lack of way of handling complex contructors. I won't be forcing everyone to implement default ctor via .create(). However, there needs to be a way to copy an instance of object within such (parent) struct. Currently it's static method operator [], but it might change to .copy() method - it's subject to change as already stated.

What I really wanted to say though, is that when container is getting destroyed, it's nodes are also destoryed and deallocated, thus track of such object(s) is lost. Recently I've adressed this issue with additional static if that when evaluated to true will call object's .destroy() method.

Those 2 issues are in my opinion valid and probably will be included within next update as well as debug messages.
 
Level 10
Joined
Sep 19, 2011
Messages
527
sounds like a good idea :).

maybe you can change some parts of the api, like:

method front takes nothing returns $TYPE$ -> method first takes nothing returns $TYPE$

method back takes nothing returns $TYPE$ -> method last takes nothing returns $TYPE$

method empty takes nothing returns boolean -> method isEmpty takes nothing returns boolean

method pushBack takes $TYPE$ value returns nothing -> method push takes $TYPE$ value returns nothing

method popBack takes nothing returns nothing -> method pop takes nothing returns nothing

method pushFront takes $TYPE$ value returns nothing -> method unshift takes $TYPE$ value returns nothing

method popFront takes nothing returns nothing -> method shift takes nothing returns nothing
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
Thanks for ideas.

Honestly this does not sound like c/c++ ^.^

front/back can not be changed to first/last unless I change pointers to front and back node from first/last to front/back. I can, however, make them readonly; problem -> those are pointers directly to nodes, not the data itself. push/pop/shift/unshift sounds nice. I had an idea to replace "fronts" with dequeue and enqueue but your proposition sounds better.

I've always was curious tho, why anyone would name check-if-empty "empty" and function which actually clears the container "clear". The later seems ok, but taking those together, pair of "isEmpty" (which is popular is higher lvl languages) and "empty" sounds a bit more intuituve then "clear" & "empty".
 
Level 14
Joined
Jun 27, 2008
Messages
1,325
Yea well cant blame you Luorax, Java bashing is quite popular. Although most of those pseudo c++ lovers are 14 year olds kids that think "C++" just sounds really badass and dont understand that both languages have their well-defined field of application which makes them unexchangeable.
 
Level 16
Joined
Aug 7, 2009
Messages
1,407
Yea, it's not like that wasn't a joke, or anything.

(I actually kinda like Java, much more than C# - I'm just tired of seeing it everywhere, that's all :'D Not to mention how I hate those self-claimed pros at school who refuse to learn because "java does everything for them", yet when you ask something very basic from they, they fail miserably . And I <3 C++ for what it is, and not because it's "badass", even though I think certain things could be improved)
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
Another approach. I've tried to implement as many suggestions as possible, especially Ruke's.

Indeed this was kind of overhead. Coding all the members and thier overloaded variations from std containers (and not just containers ;> ) was fun, yet it's rather unnecessary, here in war3.

Still, I wanted to provide kind of "global" linked list. There are plenty of module lists implementations, (don't get me wrong, those are nice and all) but after spending some time with ton of spells, map gets flooded with arrays and high amount of repeated code. I wanted this to be an alternative, offering possibility to avoid such things.

JASS:
library ListT requires Table, Alloc, AllocT

    //! runtextmacro DEFINE_LIST("IntegerList", "integer")

	module StructList
		readonly static IntegerList list
		private static IntegerListNode pNode

		static method operator head takes nothing returns thistype
			set pNode = list.front()
			return pNode.data
		endmethod

		method operator next takes nothing returns thistype
			set pNode = pNode.next
			return pNode.data
		endmethod

		method operator prev takes nothing returns thistype
			set pNode = pNode.prev
			return pNode.data
		endmethod

		private static method onInit takes nothing returns nothing
			set list = IntegerList.create()
		endmethod
	endmodule

//! textmacro DEFINE_LIST takes NAME, TYPE
	private module $NAME$NodeInit
		private static method onInit takes nothing returns nothing
			set Next = Table.create()
			set Prev = Table.create()
			set Data = Table.create()
		endmethod
	endmodule

    struct $NAME$Node extends array
		private static Table Next
		private static Table Prev
		private static Table Data

        implement AllocT

        method operator next takes nothing returns thistype
            return Next[this]
        endmethod

        method operator next= takes thistype value returns nothing
            set Next[this] = value
        endmethod

        method operator prev takes nothing returns thistype
            return Prev[this]
        endmethod

        method operator prev= takes thistype value returns nothing
            set Prev[this] = value
        endmethod

        method operator data takes nothing returns $TYPE$
            return Data.$TYPE$[this]
        endmethod

        method operator data= takes $TYPE$ value returns nothing
            set Data.$TYPE$[this] = value
        endmethod

        static method create takes $TYPE$ value returns thistype
            local thistype this = thistype.allocate()
            set this.data = value
            return this
        endmethod

        method destroy takes nothing returns nothing
            call Next.remove(this)
			call Prev.remove(this)
			call Data.$TYPE$.remove(this)

            call deallocate()
        endmethod

		implement $NAME$NodeInit
    endstruct

    struct $NAME$ extends array
		readonly $NAME$Node first
		readonly $NAME$Node last
		private integer count

		implement Alloc

        static method create takes nothing returns thistype
            local thistype this = thistype.allocate()
            set this.count = 0
            set this.first = 0
            set this.last = 0
            return this
        endmethod

        method clear takes nothing returns nothing
            local $NAME$Node node = first
            local $NAME$Node temp

            loop
                exitwhen 0 == node
                set temp = node.next
                call node.destroy()
                set node = temp
            endloop

			set first = 0
			set last = 0
			set count = 0
        endmethod

        method destroy takes nothing returns nothing
            call clear()
            call deallocate()
        endmethod

        method front takes nothing returns $TYPE$
            return first.data
        endmethod

        method back takes nothing returns $TYPE$
            return last.data
        endmethod

        method empty takes nothing returns boolean
            return 0 == count
        endmethod

        method size takes nothing returns integer
            return count
        endmethod

        method push takes $TYPE$ value returns nothing
            local $NAME$Node node = $NAME$Node.create(value)

            if ( not empty() ) then
                set last.next = node
                set node.prev = last
                set last = node
            else
                set first = node
                set last = node
                set node.prev = 0
            endif

            set node.next = 0
            set count = count + 1
        endmethod

        method unshift takes $TYPE$ value returns nothing
            local $NAME$Node node = $NAME$Node.create(value)

            if ( not empty() ) then
                set first.prev = node
                set node.next = first
                set first = node
            else
                set first = node
                set last = node
                set node.next = 0
            endif

            set node.prev = 0
            set count = count + 1
        endmethod

        method pop takes nothing returns nothing
            local $NAME$Node node

            if ( not empty() ) then
                set node = last
                set last = last.prev

                if ( last == 0 ) then
                    set first = 0
                else
                    set last.next = 0
                endif

                call node.destroy()
                set count = count - 1
            else
                // pop on empty list
            endif
        endmethod

        method shift takes nothing returns nothing
            local $NAME$Node node

            if ( not empty() ) then
                set node = first
                set first = first.next

                if ( first == 0 ) then
                    set last = 0
                else
                    set first.prev = 0
                endif

                call node.destroy()
                set count = count - 1
            else
                // shift on empty list
            endif
        endmethod

        static method operator[] takes thistype list returns thistype
            local thistype this = thistype.create()
            local $NAME$Node node = list.first

            loop
                exitwhen node == 0
                call push(node.data)
                set node = node.next
            endloop

            return this
        endmethod

        method find takes $TYPE$ value returns $NAME$Node
            local $NAME$Node node = first
            loop
                exitwhen node == 0 or node.data == value
                set node = node.next
            endloop
            return node
        endmethod

        method remove takes $NAME$Node node returns nothing
            if ( node != 0 ) then
                if ( node == first ) then
                    call shift()
                elseif ( node == last ) then
                    call pop()
                else
                    set node.prev.next = node.next
                    set node.next.prev = node.prev
                    call node.destroy()
                    set count = count - 1
                endif
            else
                // removing invalid node
            endif
        endmethod

    endstruct

//! endtextmacro

endlibrary
As you can see, except for fields and basic methods (push/pop/remove/find/clear) there is nothing left. I felt that leaving "find" might be a good idea since this struct is "global" and code isn't rewritten in each other struct.

I chose arrays for List instances, 8191 is probably enough for lists, although for nodes it is certainly not. This uses "overloaded" version of Alloc for "infinite" amount of instances:

JASS:
library AllocT requires Table

    module AllocT
        private static key table

        static method operator instances takes nothing returns integer
            return Table(table)[-1]
        endmethod

        static method operator instances= takes integer value returns nothing
            set Table(table)[-1] = value
        endmethod

        method operator recycle takes nothing returns thistype
            return Table(table)[this]
        endmethod

        method operator recycle= takes thistype value returns nothing
            set Table(table)[this] = value
        endmethod

        static method allocate takes nothing returns thistype
            local thistype this = thistype(0).recycle

            if (this == 0) then
                set instances = instances + 1
                set this = instances
            else
                set thistype(0).recycle = this.recycle
            endif

            debug set this.recycle = -1

            return this
        endmethod

        method deallocate takes nothing returns nothing
            debug if (this.recycle != -1) then
                debug call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, "Alloc ERROR: Attempted to deallocate an invalid instance at [" + I2S(this) + "]!")
                debug return
            debug endif

            set this.recycle = thistype(0).recycle
            set thistype(0).recycle = this
        endmethod
    endmodule

endlibrary
As stated, for Lists there is just basic Alloc usage.

Back to "thought process behind":
Yes.. global lists instead of modules. I know that most of list usage ends with periodic "callback", especially in typical spell-type script. However, it sometimes striked me when I needed list-type of container (not just for "callback" case) but there were not modules for that around. Like a teacher, who needs a "list" of his students for whole year, not just for single lesson.

That is where my motivation for this containers came from. Still, in regard to "callback" case, I didn't want to hurt those who would use this meaby just to lower code size and amount of arrays declared.
JASS:
// this is the most common/or basic situation
// 0 is head, thus (0).next & (0).prev could return first and last node respectively
    private static method onCallback takes nothing returns nothing
		local thistype this = thistype(0).next

		loop
			exitwhen this == 0

			set this = this.next
		endloop

	endmethod

// with "global" list, we can not use 0 is head anywhere
// as you can see, there is a need of additional local
	private static method onCallback2 takes nothing returns nothing
		local IntegerListNode node = list.first
		local thistype this

		loop
			set this = node.data
			exitwhen this == 0

			set node = node.next
		endloop

	endmethod

// to simplify process, I've created small module just for "callbacks"
// as you can see, code looks basically the same as one from first example
	private static method onCallback3 takes nothing returns nothing
		local thistype this = head

		loop
			exitwhen this == 0

			set this = this.next
		endloop

	endmethod
This is why "StructList" is at the top of library, it's an option for simplifying "callback" case.

OBJECT macro argument has been removed - again, most of list usage in war3 is connected to structs and "global list" idea would fail if for every struct (which are represented as integers anyway) there would be a Struct-List type. Because of this, for integers "runtextmacro" is by default written at the top.

However, the cost of lowered code size and variable/arrays count is speed - node's fields are returned via hashtable. The decision is up to user, he should know when speed is factor of highest value and when we can allow ourselves to use other possiblities.

Awaiting opinions/suggestions. Everything is subject to change.
 
Last edited:
Level 38
Joined
Sep 26, 2009
Messages
8,458
Anachron's Stack resource allows for a global linked list to be done without worrying about going over struct limitations. Perhaps this resource has a place in sparse resources where you know the sum of each combined resource's instances will never pose a threat to the array limit. Problem is, who makes that decision? The map maker would be the most logical. My inclination is to approve this as it is a niche resource which is faster than Anachron's due to not relying on hashtable, even though his is safer and more versatile. The two resources would co-exist.

I would like a second opinion before I give the go-ahead on this one.
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
Updated. Update tries to achieve most of the goals listed in posts above.
Code has been greatly reduced, contains only neccessary features. Most of the functions are inline friendly - especially the child item structs which are basically structs with just one method.
Added few debug messages, improved API and documentation. Fixed demo to reflect the changes. AllocT in the end wasn't even required.

Edit: Fixed issue with delegates inside <NAME>Item structs (DEFINE_STRUCT_LIST macro). These are now solely based on Table instances.

Edit2: Fixed debug calls. Removed create() and destroy() methods from <NAME>Item structs and moved them directly into list struct effectively disallowing user to perform silly actions with these.
Added ownership safety to list to prevent unintentional behaviour when dealing with foreign nodes.
 
Last edited:
Level 23
Joined
Apr 16, 2012
Messages
4,041
hmm...I think this looks good enough, yes it still has the problem of running out of instances, but that is inherit to any non Hashtable based struct, even tho when you are using each node as list itself, it gets a bit costy.

On the API front, there is nothing "lacking" from my point, it supports the most obvious push/pop and it also has neat shift/unshift as well as find.

I think this is good to go for approval, and since Bribe agreed back in 2015, I think I will go ahead and do it right now.

It would be good however, if you linked to Table in the documentation, so that people dont have to go around looking for it, but have the link served to them(Alloc cant since it can use whatever, even tho recommendation for Sevions[since it is approved] could be made too)
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
You can only run out of instances for list-class instances itself, for nodes (and those are usually the problem) the limit is raised to the limit hashtable storage.
It's highly unlikely you will ever create more than 8191 (in the past), and now you can create four times as many before hitting array-index limit. If this would be the real issue, 100% of current lists would be bound to failure and none other but Table-based implementations needed to be used.
My implementation is a mix: nodes are Table-based yet lists remain array-based. With VectorT, ListT and Table it's basically done deal when speaking about Containers for War3 vJass. You need nothing else, maybe apart from LinkedListModule. Those are as close to Wurst data packages are one can get in vJass :)

Updated to 2.1.2.0.

Added removeElem method for ListT due to frequrency of remove and find method invocations.
Added erase method, which deprecates remove method.
Improved documentation and readability.
Reduced size of push and unshift methods slightly.
Validated to be Wurst friendly.

Introduction of removeElem and erase starts 3-6 months period of depreciation. Plan is to have 'remove ' renamed to 'erase' (which is iterator based in c++) and have 'removeElem' renamed to 'remove' (which is value based in c++).
 
Last edited:
Level 24
Joined
Mar 19, 2008
Messages
3,136
ListT core should be left as simple as possible. If jasshelper properly eliminated constants and unused methods then it would have been an entirely different case. And btw, I don't care about optimizer, this job should be done on compiler level.

Back to the topic. getRandom implementation for jass is rather straightforward:
JASS:
function GetRandomListItem takes IntegerList list returns integer
    local integer rand = GetRandomInt(0, list.size())
    local IntegerListItem iter = list.first

    loop
        exitwhen rand == 0
        set rand = rand - 1
        set iter = iter.next
    endloop
    return iter.data
endfunction
Elaborate on the boolexpr filter case.
 
Hmm, I see. Sounds good.

For the boolexpr filter, similar to how you can use one with native GroupEnumUnitsInRange takes group whichGroup, real x, real y, real radius, boolexpr filter returns nothing, I was wondering how hard/feasible/useful it would be to have the ability to pick a random unit in a list depending on a filter. Like, let's say you have 3 footmen, 2 knights and 4 sorceresses in a list and you want to pick one of the 4 sorceresses.
 
Level 15
Joined
Nov 30, 2007
Messages
1,202
Why doesn't the pop() method return the element just popped. It doesn't make sense to me that a struct method returns the struct that just executed the method. But perhaps I'm missing something?

JASS:
            loop
                exitwhen i == max
                set unitType = .unitTypes.back()
                call .unitTypes.pop()
                call BJDebugMsg("id: " + I2S(unitType))
                set i = i + 1
            endloop

The back() method here shouldn't be needed.

Perhaps separate pop() from say removeBack() being two different things (or not). But i really think pop should return the value. :)

Rather than being able to chain pop. list.pop().pop().pop() I see no point with this functionality.

You should add examples of how to iterate through the list and how to iterate through the list and remove an element. Useful if you want to remove a struct based on one of it's data members.
 
Last edited:
Could:
JASS:
call BJDebugMsg("id: " + I2S(.unitTypes.back()))
call .unitTypes.pop()

You should add examples of how to iterate through the list and how to iterate through the list and remove an element. Useful if you want to remove a struct based on one of it's data members.
In his example is a loop:
JASS:
    local IntegerListItem node = list.first
    local string s = ""
    loop
        exitwhen node == 0
        set s = s + " " + I2S(node.data)
        set node = node.next
    endloop
but if an element should be removed I would go something like:
JASS:
    local IntegerListItem node = list.first
    local IntegerListItem temp
    local string s = ""
    loop
        exitwhen node == 0
        set temp = node.next
        set s = s + " " + I2S(node.data)
        if node.data == 12345 then
            call list.erase(node)
        endif
        set node = temp
    endloop

.. about return value instead of object, maybe it's preference. I somehow find it neat to make multiple operations in a row.
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
Thanks @IcemanBo for providing the examples!

I made that mistake in the past, should have added different method for pop/pop-cascade. Didn't remove it for compatibility reasons.

I could start deprecation process now, like I did for several methods in multiple libs, although..
..in JASS world, it turned out that in most cases I did not need the ret of pop and [this] came in handy.
 
Level 24
Joined
Mar 19, 2008
Messages
3,136
exists: find(...) != 0
get: find(...)
no indexOf per se.

You see, the initial version had dozens of methods much like its c++ inspiration. However, after brainstorming for a bit and reading some feedback from my jass bros, I've decided to strip container libs (both, vec and list) from most of their initial functionality and include only the core, elementary methods.
If you need indexOf, just create simple extension method within your map's code. Again, this is just jass. In 99% cases you don't need a cherry on top, the cake alone will do just fine. I think I've struck the right balance.
What's more, quite often, most experienced mappers modify certain elements of imported sources to suit their needs. It's not possible to satisfy everyone. Diplomacy comes in handy here.

```
If you want the cherry, magic, hokus pokus, meet me on the linux kernel battlefields.
 
Level 15
Joined
Nov 30, 2007
Messages
1,202
If you want the cherry, magic, hokus pokus, meet me on the linux kernel battlefields.
Fine, you win this time... :) But could you help explain to me why setNamesAsUsed doesn't work whilst getRandomName does? It doesn't seem to be able to find FullName for some reason.

JASS:
method setNameAsUsed takes FullName name, boolean used returns nothing
            call BJDebugMsg("This is called...")
            if (used) then
                if (.unusedNames.erase(name)) then
                    call .usedNames.push(name)
                    call BJDebugMsg("added to uused names list")
                endif
            else
                if (.usedNames.erase(name)) then
                    call .unusedNames.push(name)
                    call BJDebugMsg("Added to unused names list")
                endif
            endif
        endmethod
    
        method getRandomName takes nothing returns FullName
            local integer unusedSize = .unusedNames.size()
            local integer random
            local IntegerListItem node
            local FullName name = 0
            if (unusedSize > 0) then
                set node = .unusedNames.first
                set random = GetRandomInt(0, unusedSize)
                loop
                    exitwhen random == 0
                    set random = random - 1
                    set node = node.next
                endloop
                call BJDebugMsg("A")
                return node.data
            endif
            set node = .usedNames.first
            set random = GetRandomInt(0, usedNames.size())
            loop
                exitwhen random == 0
                set random = random - 1
                set node = node.next
            endloop
            call BJDebugMsg("B")
            return node.data
        endmethod
They are used like this:
JASS:
        set name = pool.getRandomName()
        call pool.setNameAsUsed(name, true)
 
Last edited:
Level 15
Joined
Nov 30, 2007
Messages
1,202
.erase expects argument of $TYPE$Item type. Your example compiles only because vJass is not type safe.
I've added .removeElem method for conveniency some time ago. It will be renamed to .remove in nearest future - deprecation period slowly comes to an end.

Ah I see thanks. A problem that arises with that though is that removeElem returns thistype and not true or false? This List is like a magic box when it comes to how some API functions work some times. The convenience of cascade methods again haunt me sir. I suggest you change it to return boolean.
 
Last edited:
Level 15
Joined
Nov 30, 2007
Messages
1,202
My listed suggestions:


method getNode takes integer index returns Node
method findNode takes $TYPE$ value returns Node
method removeNode takes Node nodeToRemove returns nothing (All delete logic here)
method addNode takes integer index, Node nodeToAdd, $TYPE$ value returns boolean (All add logic here)
method add takes integer index, $TYPE$ value returns boolean (must have)
method addFirst takes $TYPE$ value returns nothing (useful wrapper)
method addLast takes $TYPE$ value returns nothing (useful wrapper)
method contains takes $TYPE$ value returns boolean (very useful wrapper)
method copyRange takes integer start, integer end returns thistype
method define takes integer index, $TYPE$ value returns boolean (must have)
method defineFirst takes $TYPE$ value returns boolean (useful wrapper)
method defineLast takes $TYPE$ value returns boolean (useful wrapper
method get takes integer index returns $TYPE$ (must have)
method getFirst takes nothing returns $TYPE$ (useful wrapper)
method getLast takes nothing returns $TYPE$ (useful wrapper)
method indexOf takes $TYPE$ value returns integer (very useful wrapper)
method iterator takes nothing returns Iterator (useful wrapper, special mention)
method remove takes integer index returns $TYPE$ (must have)
method removeFirst takes nothing returns $TYPE$ (replaces pop)
method removeLast takes nothing returns $TYPE$
method removeElement takes $TYPE$ value returns boolean
method sort takes nothing returns nothing (optional, but dont see why not)

replace every if-statement that has empty() in it with count == 0

JASS:
struct Iterator extends array
        private Node curNode
        private Node nextNode
        private Node prevNode
        private LinkedList list
 
        implement Alloc
 
        static method create takes LinkedList list, Node head returns thistype
            local thistype this = .allocate()
            set .nextNode = head
            set .curNode = 0
            set .prevNode = 0
            set .list = list
            return this
        endmethod
 
        method hasNext takes nothing returns boolean
            return nextNode != 0
        endmethod
 
        method next takes nothing returns integer
            set .prevNode = .curNode
            set .curNode = .nextNode
            set .nextNode = .nextNode.next
            return .curNode.value
        endmethod
 
         method remove takes nothing returns boolean
            if (.curNode == 0) then
                call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, ITR + ".remove:" + NULL_PTR)
                return false
            endif
            call .list.removeNode(.curNode)
            set .curNode = 0
            return true
        endmethod
    endstruct
Usage
JASS:
call list.add(0, 3)
        call list.add(0, 4)
        call list.add(0, 5)
        call list.add(1, 7)
        set list2 = list.copyRange(0, 1)
        call list.remove(0)
        set itr = list.iterator()
        loop
            exitwhen not itr.hasNext()
            set value = itr.next()
            call BJDebugMsg("Value: " + I2S(value))
            call itr.remove()
            // call itr.remove() <-- Illegal action double remove without next!
        endloop


AddFirst and addLast can implement cascade logic (it makes the most sense to have it in setup)
 
Last edited:
Level 15
Joined
Nov 30, 2007
Messages
1,202
I'd suggest these being implemented in some kind of extension/ plugin lib. Afterwards, static-if could be added for List<T> that would implement code of such plugin lib.

why though? If you change your configuration addNode, removeNode and findNode most of these methods become wrappers. Maybe your current configuration can do it already though, don't know. Perhaps getNode(index) is the one that most of them build upon. So if you only want node manipulation you should change for example:

JASS:
    method push takes $TYPE$ value returns thistype
        local $NAME$Item node = createNode(value)
        if not empty() then
            set last.next = node
            set node.prev = last
        else
            set first = node
            set node.prev = 0
        endif
        set last = node
        set node.next = 0
        set count = count + 1
        return this
    endmethod

Into something that can do more things, example:
JASS:
 method addNode takes integer index, $NAME$ nodeToAdd, $TYPE$ value returns boolean
        if (index > .count or index < 0) then
            call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, LIST + ".add:" + OUT_BOUNDS)
            return false
        endif
        if (nodeToAdd == 0) then
            set nodeToAdd = createNode(value) // if nodeToAdd is 0 we create a new one with the value
        endif
        if (index == 0) then
            call .addFirst(value)
        elseif (index == .count) then
            call .addLast(value)
        else // insertion
            set oldNode = getNode(index) // <---- needed for extended features
            set oldNode.prev.next = nodeToAdd
            set nodeToAdd.prev = oldNode.prev
            set nodeToAdd.next = oldNode
            set oldNode.prev = nodeToAdd
            set .count = .count + 1
        endif
        return true
    endmethod

        method addFirst takes integer value returns nothing 
            local Node nodeToAdd = Node.create(value)
            if (.head == 0) then 
                set .head = nodeToAdd
                set .tail = .head
            else 
               set .head.prev = nodeToAdd
               set nodeToAdd.next = .head
               set .head = nodeToAdd
            endif
            set .length = .length + 1
        endmethod
       
        method addLast takes integer value returns nothing 
            local Node nodeToAdd = Node.create(value)
            set nodeToAdd.prev = tail
            set .tail.next = nodeToAdd
            set .tail = nodeToAdd
            set .length = .length + 1
        endmethod
See my lab post for more examples.
 
Last edited:
Level 24
Joined
Mar 19, 2008
Messages
3,136
List<T> already defines front/ back and first/ last.

"Mandatory" is a very subjective term. History shows that successful jass collection snippets were small. Range of utility functions you've posted out there won't be used by 98% users.
Professional approach is to wrap such utilities within plugin library and add adequate static-if construct into parent lib.

There is an another option - fix jass compiler so unused methods are not generated at all, much like wurst one. And yes, I know about optimizer tool, and yes, I do not care. Such "optimization" should be done on compiler level.
 
Top