Exgroup script feedback

04-04-2009, 08:18 PM

I have recently been working on a script, declaring a struct called exgroup. Exgroup meand extended group, and it is meant to replace normal groups during certain circumstances. The key feature of it, is that a unit can be added multiple times to the same exgroup. This is very useful in some situations. It allows weighted randomness when picking a random unit, and a function will be executed multiple times on certain units, when calling exgroup's equivalent to ForGroup().

Firstly, here is the documentation:

JASS:

//========================================================
// exgroup - A more powerful alternative to group
// Created by 0zyx0
//========================================================

//-What is an exgroup?
  -It is an object type, similar to a group, but with some differences.

//-What makes this better than normal groups?
  -It is an object type, which can be extended.
  -One unit can be added multiple times, giving it multiple memberships.
  -You can remove units matching a given condition, without creating an additional group.
  -You do not have to use any boolexpr variables/functions.
  
//-What are the cons?
  -It can sometimes be slow(er than a normal group), expecially for large exgroups.
  -You can not use an exgroup in place of a group in a function taking a group.
  -You can only have a limited amount of instances. It can be configured at the script header.

//-What does exgroup mean?
  -It means extended group.
  
//-What are the requirements?
  -You need a vJASS compiler, and the library Group Utils by Rising_Dusk.
  -It can all be found at [url]www.wc3c.net[/url]

//-What methods and fields does it have?
  -The basic methods and fields are:
  
integer unitCount   (read only)
    // The number of unit memberships in the exgroup.

boolean isEmpty     (read only)
    // True if the group is empty, false if the exgroup contains any unit.
    
UnitFilter accept = 0
    // Only units matching this filter will be added to the group.
    // Using this will make the exgroup considerably slower.
    // Se below for information about what UnitFilter is.
    
________________________________________________________ 
static method create     takes nothing   returns exgroup
    // Creates a new instance of exgroup.
________________________________________________________ 
static method fromGroup takes group g    returns exgroup
    // Creates a new exgroup with the content from a group.
    // The group will be emptied, but not destoyed.
________________________________________________________ 
method destroy           takes nothing   returns nothing
    // Destroys the exgroup
________________________________________________________  
method addUnit           takes unit u    returns nothing
    // Adds a membership for u to the exgroup.
    // Note that a single unit can have multiple memberships.
________________________________________________________
method removeUnit        takes unit u    returns boolean
    // Removes one membership of u from the exgroup.
    // It returns false if the unit didn't have any membership.
________________________________________________________   
method removeUnitAll     takes unit u    returns nothing
    // Removes all memberships of u from the exgroup.
________________________________________________________     
method addGroup          takes group g   returns nothing
method removeGroup       takes group g   returns nothing
method removeGroupAll    takes group g   returns nothing
    // Does the same as their single unit counterparts, exept that they take a group as an argument.
    // Note that this will empty the group g.
________________________________________________________    
method addExgroup        takes exgroup e returns nothing
    // Adds all units in e to the exgroup.
________________________________________________________
method subtractExgroup   takes exgroup e returns nothing
    // Removes all units in e from the exgroup.
________________________________________________________  
method clone             takes nothing   returns exgroup
    // Clones an exgroup.
________________________________________________________ 
method clear             takes nothing   returns nothing
    // Removes all units from the exgroup. Not equal to destroy!
________________________________________________________
method clearDuplicates   takes nothing   returns nothing
    // All units in the exgroup will only have one membership after this function is called.
    // I don't recommend using it unless you really need it, since it is very slow.
________________________________________________________ 
method containsUnit      takes unit u    returns boolean
    // Returns true if the exgroup contains u.
________________________________________________________   
method getRandomUnit     takes nothing   returns unit
    // Returns a random unit from the exgroup. All units get a chance to be returned
    // equal to its number of memberships, divided by the total number of units.
________________________________________________________
method getUnit           takes nothing   returns group
    // This can be used instead of getRandomUnit, if you don't need the randomness.
    // You can use this to get a unit, do somehting with it, and then removing it from the exgroup.
________________________________________________________ 
method toGroup           takes nothing   returns group
    // Returns a group containing all units contained by the exgroup.
    // The group is created using NewGroup() from Group Utils.
________________________________________________________________________  
// To explain the more advanced methods, which are the most useful ones,
// two function interfaces have to be introduced.

public function interface UnitAction    takes unit u    returns nothing
public function interface UnitFilter    takes unit u    returns boolean
________________________________________________________
method for           takes UnitAction ua returns nothing
    // Calls the given UnitAction for all units in the exgroup,
    // or once per unit membership. The argument has to be a name (without "")
    // of a function taking a unit as a paramenter, returning nothing.
________________________________________________________    
method filterOutAll  takes UnitFilter uf returns nothing
    // Removes all units matching the given condition from the exgroup.
    // Even units with multiple memberships will be removed completely.
    // There is no filterOut method yet.

method addMembership takes UnitFilter uf returns nothing
    // Adds all units in the exgroup matching uf to the exgroup again.
    // WARNING! You should make sure the exgroup contains only one of each unit,
    // possibly by calling clearDuplicates, before using this. You CAN use this
    // multiple times, but ONLY if you don't have modified the content since
    // the last time you called it, or it will have very strange side effects.
    // However, it will become safe to use it again after calling clear, or
    // clearDuplicates.

And here is the script itself:

JASS:

library exgroup requires GroupUtils

globals
    private constant integer maxunits = 819
    // This is how many units an exgroup can contain.
    // The maximum amount of instances is equal to 8190 divided by this value.
    // The deafault maximum amount of instances is 10.
endglobals

public function interface UnitAction takes unit u returns nothing
public function interface UnitFilter takes unit u returns boolean


struct exgroup
    private unit array content[maxunits]
    private integer unitcount = 0
    private integer doublelimit = 0
    UnitFilter accept = 0
    
    method operator isEmpty takes nothing returns boolean
        return .unitcount == 0
    endmethod
    method operator unitCount takes nothing returns integer
        return .unitcount
    endmethod
    method getRandomUnit takes nothing returns unit
        return .content[GetRandomInt(0, .unitcount)]
    endmethod
    method getUnit takes nothing returns unit
        return .content[0]
    endmethod
    
    static method fromGroup takes group g returns exgroup
        local exgroup e = exgroup.create()
        call e.addGroup(g)
        return e
    endmethod
    
//=========================================================================================
//Private methods below. They will absolutley not be useful externally.
    private method placeOfUnit takes unit u returns integer
        local integer i = 0
        loop
            exitwhen i == .unitcount
            if .content[i] == u then
                return i
            endif
            set i = i+1
        endloop
        return .unitcount
    endmethod
    private method placeOfUnitAboveIndex takes unit u, integer i returns integer
        set i = i+1
        loop
            exitwhen i == .unitcount
            if .content[i] == u then
                return i
            endif
            set i = i+1
        endloop
        return .unitcount
    endmethod
//=========================================================================================
//General methods  
    method containsUnit takes unit u returns boolean
        local integer i = 0
        if .isEmpty then
            return false
        endif
        loop
            exitwhen i == .unitcount
            if .content[i] == u then
                return true
            endif
            set i = i+1
        endloop
        return false
    endmethod
    
    method clear takes nothing returns nothing
        local integer i = 0 
        loop
            exitwhen i == .unitcount
            set .content[i] = null
            set i = i+1
        endloop
        set .unitcount = 0
        set .doublelimit = 0
    endmethod
    
//=========================================================================================
// Single Unit methods    
    method addUnit takes unit u returns nothing
        if .accept == 0 then
            set .content[.unitcount] = u
            set .unitcount = .unitcount + 1
            return
        endif
        if .accept.evaluate(u) then
            set .content[.unitcount] = u
            set .unitcount = .unitcount + 1
        endif
    endmethod
    method removeUnit takes unit u returns boolean
        local integer i = .placeOfUnit(u)
        if i == .unitcount then
            return false
        endif
        set .unitcount = .unitcount - 1
        set .content[i] = .content[.unitcount]
        set .content[.unitcount] = null
        return true
    endmethod
    method removeUnitAll takes unit u returns nothing
        local integer i = 0
        loop
            set i = .placeOfUnitAboveIndex(u, i)
            if i == .unitcount then
                return
            endif
            set .unitcount = .unitcount - 1
            set .content[i] = .content[.unitcount]
            set .content[.unitcount] = null
        endloop
    endmethod
    
//=========================================================================================
// Group methods
    method addGroup takes group g returns nothing
        local unit u
        loop
            set u = FirstOfGroup(g)
            if u == null then
                return
            endif
            call .addUnit(u)
            call GroupRemoveUnit(g, u)
        endloop
    endmethod
    method removeGroup takes group g returns nothing
        local unit u
        loop
            set u = FirstOfGroup(g)
            if u == null then
                return
            endif
            call .removeUnit(u)
            call GroupRemoveUnit(g, u)
        endloop
    endmethod
    method removeGroupAll takes group g returns nothing
        local unit u
        loop
            set u = FirstOfGroup(g)
            if u == null then
                return
            endif
            call .removeUnitAll(u)
            call GroupRemoveUnit(g, u)
        endloop
    endmethod
    
    method toGroup takes nothing returns group
        local group g = NewGroup()
        local integer i = 0
        loop
            exitwhen i == .unitcount
            call GroupAddUnit(g, .content[i])
            set i = i+1
        endloop
        return g
    endmethod
    
//=========================================================================================
// Methods with function interface argument
    method for takes UnitAction ua returns nothing
        local integer i = 0
        loop
            exitwhen i == .unitcount
            call ua.execute(.content[i])
            set i = i+1
        endloop
    endmethod
    method filterOutAll takes UnitFilter uf returns nothing
        local integer i = 0
        loop
            exitwhen i == .unitcount
            if uf.evaluate(.content[i]) then
                call .removeUnitAll(.content[i])
            endif
            set i = i+1
        endloop
    endmethod
    method addMembership takes UnitFilter uf returns nothing
        local integer i = 0
        if .doublelimit == 0 then
            set .doublelimit = .unitcount
        endif
        loop
            exitwhen i == .doublelimit
            if uf.evaluate(.content[i]) then
                call .addUnit(.content[i])
            endif
            set i = i+1
        endloop
    endmethod
//=========================================================================================
// Interaction between multiple exgroups
    method addExgroup takes exgroup e returns nothing
        local integer i = 0
        loop
            exitwhen i == e.unitcount
            call .addUnit(e.content[i])
            set i = i+1
        endloop
    endmethod
    method subtractExgroup takes exgroup e returns nothing
        local integer i = 0
        loop
            exitwhen i == e.unitcount
            call .removeUnit(e.content[i])
            set i = i+1
        endloop
    endmethod
    method clone takes nothing returns exgroup
        local exgroup e = exgroup.create()
        call e.addExgroup(this)
        return e
    endmethod
//=========================================================================================

    method clearDuplicates takes nothing returns nothing
        local integer i = 0
        local integer j
        loop
            exitwhen i == .unitcount
            set j = .placeOfUnitAboveIndex(.content[i], i)
            if .content[i] == .content[j] then
                call .removeUnit(.content[j])
            endif
            set i = i+1
        endloop
        set .doublelimit = 0
    endmethod
endstruct

endlibrary

I would like to get feedback about this script, its usefullnes, what should be added, and all kinds of feedback, really. I am planning to submit this as a resource, but I would like to have some comments first.

An improved version can be found below.

04-06-2009, 02:55 AM	#2
Anitarf	I'd make it linked list based instead of array based, it would facilitate a much higher exgroup limit.

04-06-2009, 04:05 AM	#3
Vexorian	I think a more appropriate name is "multigroup"

04-06-2009, 07:52 AM

0zyx0

I recreated the system from scratch, to use multiple unitgroups instead of arrays, adding speed and functionallity, but removing functions related to randomness. I haven't had time to create a new documentation yet.

JASS:

library Multigroup requires GroupUtils
globals
    private constant integer MAX_MEMBERSHIPS = 5
endglobals

public function interface UnitAction takes unit u returns nothing
public function interface UnitFilter takes unit u returns boolean

struct multigroup
    private group array content [MAX_MEMBERSHIPS]
    private integer groupcount = 0
    private integer membershiplimit = MAX_MEMBERSHIPS
    boolean wantRelease = false
    UnitFilter accept
    
    method containsUnit takes unit u returns boolean
        return IsUnitInGroup(u, .content[0])
    endmethod
    method operator isEmpty takes nothing returns boolean
        return .content[0] == null
    endmethod
    method operator unitCount takes nothing returns integer
        local integer i = 0
        local integer j = 0
        loop
            exitwhen i == .groupcount
            set j = j + CountUnitsInGroup(.content[i])
            set i = i + 1
        endloop
        return j
    endmethod
    
    method operator asGroup takes nothing returns group
        return .content[0]
    endmethod
    
    method operator membershipLimit takes nothing returns integer
        return .membershiplimit
    endmethod
    method operator membershipLimit= takes integer j returns nothing
        local integer i = .groupcount
        set .membershiplimit = j
        if j < .groupcount then
            loop
                exitwhen i == j
                call ReleaseGroup(.content[i])
                set i = i-1
            endloop
        endif
    endmethod
    
    method operator membershipMax takes nothing returns integer
        return .groupcount
    endmethod
    
    static method create takes nothing returns multigroup
        local multigroup exg = multigroup.allocate()
        local integer i = 1
        loop
            exitwhen i == MAX_MEMBERSHIPS
            set exg.content[i] = null
            set i = i+1
        endloop
        set exg.groupcount = 1
        return exg
    endmethod
    method onDestroy takes nothing returns nothing
        local integer i = 0
        loop
            exitwhen i == .groupcount
            call ReleaseGroup(.content[i])
            set .content[i] = null
            set i = i+1
        endloop
    endmethod
//=========================================================================================
// Single Unit methods  
      
    method addUnit takes unit u returns boolean
        local integer i = 0
        if .accept != 0 then
            if .accept.evaluate(u) == false then
                return false
            endif
        endif
        loop
            exitwhen i == .membershiplimit
            if .content[i] == null then
                set .content[i] = NewGroup()
                set .groupcount = i+1
            endif
            if IsUnitInGroup(u, .content[i]) == false then
                call GroupAddUnit(.content[i], u)
                return true
            endif
            set i = i+1
        endloop
        return false
    endmethod
    
    method removeUnit takes unit u returns boolean
        local integer i = .groupcount-1
        if IsUnitInGroup(u, .content[0]) == false then
            return false
        endif
        loop
            exitwhen i < 0
            if IsUnitInGroup(u, .content[i]) then
                call GroupRemoveUnit(.content[i], u)
                if IsUnitGroupEmptyBJ(.content[i]) then
                    call ReleaseGroup(.content[i])
                    set .content[i] = null
                    set .groupcount = .groupcount - 1
                endif
                return true
            endif
            set i = i-1
        endloop
        return false
    endmethod
    
    method removeUnitAll takes unit u returns boolean
        local integer i = .groupcount
        loop
            exitwhen i == 0
            call GroupRemoveUnit(.content[i], u)
            set i = i+1
            if IsUnitGroupEmptyBJ(.content[i]) then
                call ReleaseGroup(.content[i])
                set .content[i] = null
                set .groupcount = .groupcount - 1
            endif
            set i = i-1
        endloop
        if IsUnitInGroup(u, .content[0]) then
            call GroupRemoveUnit(.content[0], u)
            if IsUnitGroupEmptyBJ(.content[0]) then
                call ReleaseGroup(.content[0])
                set .content[0] = null
                set .groupcount = .groupcount - 1
            endif
            return true
        endif
        return false
    endmethod
//=========================================================================================
// Group methods
    
    method addGroup takes group g returns nothing
        local unit u
        local group g2 = NewGroup()
        loop
            exitwhen IsUnitGroupEmptyBJ(g)
            set u = FirstOfGroup(g)
            call .addUnit(u)
            call GroupAddUnit(g2, u)
            call GroupRemoveUnit(g, u)
        endloop
        loop
            exitwhen IsUnitGroupEmptyBJ(g2)
            set u = FirstOfGroup(g2)
            call GroupAddUnit(g, u)
            call GroupRemoveUnit(g2, u)
        endloop
        call ReleaseGroup(g2)
        set g2 = null
        set u = null
    endmethod
    
    method removeGroup takes group g returns nothing
        local unit u
        local group g2 = NewGroup()
        loop
            exitwhen IsUnitGroupEmptyBJ(g)
            set u = FirstOfGroup(g)
            call .removeUnit(u)
            call GroupAddUnit(g2, u)
            call GroupRemoveUnit(g, u)
        endloop
        loop
            exitwhen IsUnitGroupEmptyBJ(g2)
            set u = FirstOfGroup(g2)
            call GroupAddUnit(g, u)
            call GroupRemoveUnit(g2, u)
        endloop
        call ReleaseGroup(g2)
        set g2 = null
        set u = null
    endmethod
    
    method removeGroupAll takes group g returns nothing
        local unit u
        local group g2 = NewGroup()
        loop
            exitwhen IsUnitGroupEmptyBJ(g)
            set u = FirstOfGroup(g)
            call .removeUnitAll(u)
            call GroupAddUnit(g2, u)
            call GroupRemoveUnit(g, u)
        endloop
        loop
            exitwhen IsUnitGroupEmptyBJ(g2)
            set u = FirstOfGroup(g2)
            call GroupAddUnit(g, u)
            call GroupRemoveUnit(g2, u)
        endloop
        call ReleaseGroup(g2)
        set g2 = null
        set u = null
    endmethod
    
    static method fromGroup takes group g returns multigroup
        local multigroup mg = multigroup.create()
        call mg.addGroup(g)
        return mg
    endmethod
    
//=========================================================================================
// Clearing methods

    method clear takes nothing returns nothing
        local integer i = 0
        loop
            exitwhen i == .groupcount
            call ReleaseGroup(.content[i])
            set i = i+1
        endloop
    endmethod
    
    method clearDuplicates takes nothing returns nothing
        local integer i = 1
        loop
            exitwhen i == .groupcount
            call ReleaseGroup(.content[i])
            set i = i+1
        endloop
    endmethod
    
//=========================================================================================
// Interaction between multiple multigroups

    method addMultigroup takes multigroup exg returns nothing
        local integer i = 0
        loop
            exitwhen i == exg.groupcount
            call .addGroup(exg.content[i])
            set i = i+1
        endloop
    endmethod
    
    method removeMultigroup takes multigroup exg returns nothing
        local integer i = 0
        loop
            exitwhen i == exg.groupcount
            call .removeGroup(exg.content[i])
            set i = i+1
        endloop
    endmethod
    
    method clone takes nothing returns multigroup
        local multigroup exg = multigroup.create()
        call exg.addMultigroup(this)
        return exg
    endmethod

//=========================================================================================
// Methods with a function interface argument

    method for takes UnitAction ua returns nothing
        local integer i = 0
        local group g
        local unit u
        loop
            exitwhen i == .groupcount
            set g = NewGroup()
            loop
                set u = FirstOfGroup(.content[i])
                exitwhen u == null
                call ua.execute(u)
                call GroupRemoveUnit(.content[i], u)
                call GroupAddUnit(g, u)
            endloop
            call ReleaseGroup(.content[i])
            set .content[i] = g
            set i = i+1
        endloop
        set g = null
        set u = null
    endmethod
    
    method filterOut takes UnitFilter uf returns nothing
        local unit u
        local group g = NewGroup()
        loop
            set u = FirstOfGroup(.content[0])
            exitwhen u == null
            call GroupRemoveUnit(.content[0], u)
            if uf.evaluate(u) then
                if .removeUnit(u) then
                    call GroupAddUnit(g, u)
                endif
            else
                call GroupAddUnit(g, u)
            endif
        endloop
        call ReleaseGroup(.content[0])
        set .content[0] = g
        set g = null
    endmethod
    
    method filterOutAll takes UnitFilter uf returns nothing
        local unit u
        local group g = NewGroup()
        loop
            set u = FirstOfGroup(.content[0])
            exitwhen u == null
            call GroupRemoveUnit(.content[0], u)
            if uf.evaluate(u) then
                call .removeUnitAll(u)
            else
                call GroupAddUnit(g, u)
            endif
        endloop
        call ReleaseGroup(.content[0])
        set .content[0] = g
        set g = null
    endmethod
    
    method filterAdd takes UnitFilter uf returns nothing
        local integer i = 0
        local group g = NewGroup()
        local unit u
        loop
            set u = FirstOfGroup(.content[0])
            exitwhen u == null
            if uf.evaluate(u) then
                call .addUnit(u)
            endif
            call GroupRemoveUnit(.content[0], u)
            call GroupAddUnit(g, u)
        endloop
        call ReleaseGroup(.content[0])
        set .content[0] = g
        set g = null
        set u = null
    endmethod
    
endstruct
endlibrary

04-06-2009, 09:34 AM

PipeDream

It seems to me like the multiple entries implementations are complicated. Your goals of weighted randomness and multiple execution can be done by unique entries with counts, assuming you have some place to put the counts.

To do random weighted sampling, pick a random entry and accept it with probability the desired weight, else try again.

Then you have:
Psample = 1/N
Paccept = w_i
Ptotal = (w_i / N) / (sum_i w_i / N) = w_i

But for N equal weights you'll have to reject N samples, potentially inefficient. Also depends on being able to uniformly sample the collection, which I don't think you can do with groups.

The other approach is bisection. Compile all your elements into a real array v, where v[i] = v[i-1] + w_i, v[-1] = 0. This is an O(N) construction step, which, if you're doing a lot of sampling and not much group twiddling, may be irrelevant. Then pick one random real, and bisect in O(log N) to find the interval containing that real, or assume even distribution to try to find it faster.

These aren't as fast as what you had before, but they do open the door for non integer counts.