[vJASS] Generic Groups

[Earth-Fury]

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

 

[PurplePoot]

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).

 

[Earth-Fury]

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?

 

[PurplePoot]

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.