[vJASS] Generic Groups

Poot said to send this to its own thread, so here it be. This has yet to be really tested properly, so I don't suggest you use it for anything quite yet...

Change Log / Development Log

• Version 0.2.0
  • Added removeAll() method
  • Added removeGroup() method
  • Changed iterator API around
  • Removed isEmpty() in favour of comparing .length > 0
  • Misc. fixes
• Version 0.1.1
  • Changed code around a lot
  • Changed the way [] and []= work
• Version 0.1.0
  • Added [] and []= operator overloads. JASS needs Exception handling.
• Version 0.0.1
  • First documented release

System Code:

// Things to document:
// - Check that .length > 0 before .pop()ing, as
// there is no way for pop() to report emptyness.

library GenericGroups
//! textmacro GroupDeclare takes GNAME, GTYPE, GDEFAULT
scope $GNAME$GroupScope

function interface $GNAME$ForGroup takes $GNAME$ sourceGroup, $GTYPE$ value, integer tag returns nothing

private struct $GNAME$Node
    $GNAME$Node next = 0
    $GNAME$Node prev = 0

    $GTYPE$ value = $GDEFAULT$
endstruct

struct $GNAME$
    $GNAME$Node first = 0
    $GNAME$Node last = 0

    integer length = 0

    $GNAME$Node now = -1

    //========================================================================================
    // Creation of group
    //========================================================================================

    method copy takes nothing returns $GNAME$
        local $GNAME$Node enum = this.first
        local $GNAME$ to = $GNAME$.create()

        loop
            exitwhen enum == 0

            call to.pushBack(enum.value)

            set enum = enum.next
        endloop

        return to
    endmethod

    //========================================================================================
    // Addition to group
    //========================================================================================

    method add takes $GTYPE$ value returns nothing
        call this.pushBack(value)
    endmethod

    method addGroup takes $GNAME$ from returns nothing
        local $GNAME$Node enum = from.first

        loop
            exitwhen enum == 0

            call this.pushBack(enum.value)

            set enum = enum.next
        endloop
    endmethod

    //========================================================================================
    // Removal from group
    //========================================================================================

    method remove takes $GTYPE$ value returns boolean
        local $GNAME$Node enum = this.first

        loop
            exitwhen enum == 0

            if enum.value == value then
                call this.removeNode(enum)

                return true
            endif

            set enum = enum.next
        endloop

        return false
    endmethod

    method removeAll takes $GTYPE$ value returns boolean
        local $GNAME$Node enum = this.first
        local boolean b = false

        loop
            exitwhen enum == 0

            if enum.value == value then
                if enum.next == 0 then
                    call this.removeNode(enum)
                    return true
                else
                    set enum = enum.next
                    call this.removeNode(enum.prev)
                    set b = true
                endif
            else
                set enum = enum.next
            endif
        endloop

        return b
    endmethod

    method removeGroup takes $GNAME$ toRemove returns nothing
        loop
            exitwhen not this.iteratorStep()

            loop
                exitwhen not toRemove.iteratorStep()

                if this.enumValue == toRemove.enumValue then
                    call this.removeNode(this.now)
                    call toRemove.iteratorReset()
                    exitwhen true
                endif
            endloop
        endloop
    endmethod

    method clear takes nothing returns nothing
        local $GNAME$Node enum = this.first

        loop
            exitwhen enum == 0

            if enum.next == 0 then
                call enum.destroy()
                exitwhen true
            else
                set enum = enum.next
                call enum.prev.destroy()
            endif
        endloop

        set this.first = 0
        set this.last = 0

        set this.length = 0

        set this.now = -1
    endmethod

    //========================================================================================
    // Retrieval of value
    //========================================================================================

    method containsValue takes $GTYPE$ value returns boolean
        local $GNAME$Node enum = this.first

        loop
            exitwhen enum == 0

            if enum.value == value then
                return true
            endif

            set enum = enum.next
        endloop

        return false
    endmethod

    method getRandom takes nothing returns $GTYPE$
        local $GNAME$Node enum = this.first
        local integer goto = GetRandomInt(0, this.length - 1)
        local integer i = 0

        loop
            if i == goto then
                return enum.value
            endif

            set i = i + 1
            set enum = enum.next
        endloop

        return $GDEFAULT$ // Will never be reached
    endmethod

    //========================================================================================
    // Operator Overloading
    //========================================================================================

    method operator [] takes integer k returns $GTYPE$
        local $GNAME$Node enum = this.first
        local integer i = 0

        if enum == 0 then
            call this.pushBack($GDEFAULT$)
            set enum = this.first
        endif

        loop
            if enum == 0 then
                call this.pushBack($GDEFAULT$)
                set enum = this.last
            endif

            if i == k then
                return enum.value
            endif

            set i = i + 1
            set enum = enum.next
        endloop

        return $GDEFAULT$ // Will never be reached
    endmethod



    method operator []= takes integer k, $GTYPE$ value returns nothing
        local $GNAME$Node enum = this.first
        local integer i = 0

        if enum == 0 then
            call this.pushBack($GDEFAULT$)
            set enum = this.first
        endif

        loop
            if enum == 0 then
                call this.pushBack($GDEFAULT$)
                set enum = this.last
            endif

            if i == k then
                set enum.value = value
                return
            endif

            set i = i + 1
            set enum = enum.next
        endloop
    endmethod

    //========================================================================================
    // Deque Methods
    //========================================================================================

    method pushFront takes $GTYPE$ value returns nothing
        local $GNAME$Node n = $GNAME$Node.create()

        set n.value = value

        set n.next = this.first
        set this.first.prev = n
        set this.first = n

        if this.last == 0 then
            set this.last = n
        endif

        set this.length = this.length + 1
    endmethod

    method pushBack takes $GTYPE$ value returns nothing
        local $GNAME$Node n = $GNAME$Node.create()

        set n.value = value

        set n.prev = this.last
        set this.last.next = n
        set this.last = n

        if this.first == 0 then
            set this.first = n
        endif

        set this.length = this.length + 1
    endmethod

    method popFront takes nothing returns $GTYPE$
        local $GTYPE$ value = this.first.value

        debug if this.first == 0 then
        debug call BJDebugMsg("$GNAME$.popFront() Error: Group is empty, check .isEmpty() before .pop()ing!")
        debug endif

        call this.removeNode(this.first)

        return value
    endmethod

    method popBack takes nothing returns $GTYPE$
        local $GTYPE$ value = this.last.value

        debug if this.last == 0 then
        debug call BJDebugMsg("$GNAME$.popBack() Error: Group is empty, check .isEmpty() before .pop()ing!")
        debug endif

        call this.removeNode(this.last)

        return value
    endmethod

    //========================================================================================
    // Iteration
    //========================================================================================

    $GTYPE$ enumValue

    method iteratorStep takes nothing returns boolean
        if this.now == -1 then
            if this.first == 0 then
                return false
            endif

            set this.now = this.first
            set this.enumValue = this.now.value

            return true
        elseif this.now == 0 or this.now.next == 0 then
            set this.now = -1

            return false
        endif

        set this.now = this.now.next
        set this.enumValue = this.now.value

        return true
    endmethod

    method iteratorReset takes nothing returns nothing
        set this.now = -1
    endmethod

    method forGroup takes $GNAME$ForGroup func, integer tag returns nothing
        loop
            exitwhen not this.iteratorStep()

            call func.evaluate(this, this.enumValue, tag)
        endloop
    endmethod

    //========================================================================================
    // Private API
    //========================================================================================
    private method removeNode takes $GNAME$Node n returns nothing
        if n == this.now then
            if this.now.next == 0 then
                set this.now = 0
            elseif this.now.prev == 0 then
                set this.now = -1
            else
                set this.now = this.now.prev
            endif
        endif

        if this.first == n then
            set this.first = this.first.next
            if this.first != 0 then
                set this.first.prev = 0
            endif
        else
            set n.prev.next = n.next
        endif

        if this.last == n then
            set this.last = this.last.prev
            if this.last != 0 then
                set this.last.next = 0
            endif
        else
            set n.next.prev = n.prev
        endif

        call n.destroy()

        set this.length = this.length - 1
    endmethod
endstruct

endscope
//! endtextmacro

endlibrary

To Do:

• Fix anything I've missed
• Documentation

You could reduce the potential length of this (assuming multiple types of lists are used) by a huge amount via inheritance. Anything that just deals with the list items and not with their actual type values can be generalized to an interface (or parent struct).

the problem with using inheritance is the array limit. 8190 instances of a single struct type. All children are of the parent type as well. Not a problem for lists, but it is a problem for nodes. (You need to have the nodes type in the list class in order to use it, which means the node types would need a common ancestor to be manipulated in a parent list type.)

Besides, JASS allocates arrays in chunks, so its not really a big deal to spam array usage. (Or function usage... open up a GUI map's script file, and see what I mean...)

There is the option of using common ancestors and the extended struct limit, but that adds a somewhat heafty function call and comparison for all struct operations. (Which is something I would really like to avoid.)

Considering the API is value-based and not node-based, inheritance also doesn't have the benefit of polymorphism. (The main, and basically only reason to use inheritance.)

I think I'll move copy to be an instance method that takes nothing and returns a copy of the instance its called on...

Edit: Oh, and I had an idea for [] and []=. I could automagically extend the list to an out of range element. This would require addition of a "GDEFALT" to the macro, but it would replace undefined functionality with working code. Thoughts?

As for []/[]=, that seems to be a fine idea.

About the inheritance, only a few methods (clear, for one) could be done this way anyways, but it should still reduce waste a good deal, assuming there are several types of lists in the map. However, I underestimated the amount of methods that could actually use this.