SwappedGroup

[Luorax]

So according to TriggerHappy's benchmarks a swapped FirstOfGroup enumeration is still faster than ForGroup, almost all the time. I'm gonna need this in the future for changing my aura snippet so I figured I'd post it here.

This is nothing fancy or complicated, just a simple interface for using swapped groups without much trouble.

I'm posting a test map with the requirements and the demo code too.

Code

library SwappedGroup/*
***************************************************************************************
*
*            Swapped Group v1.2.1
*
*                by Luorax
*
***************************************************************************************
*
*        */ uses /*
*           */  GroupUtils /*   [URL]http://www.wc3c.net/showthread.php?t=104464[/URL]
*
***************************************************************************************
*
*            DESCRIPTION
*                >> SwappedGroup provides a lightweight interface for managing swapped 
*                   unit groups.
*
*                >> A swapped group is useful when using FirstOfGroup group enumerations
*                   on groups that need to keep their content after the enumeration, since
*                   all the units will be moved into a 'shadow group' (a secondary group in
*                   the background), and they'll be swapped after the enumeration.
*
*            METHOD LIST
*                >> struct SwappedGroup
*                    > public static method create takes nothing returns
*                       - creates a new SwappedGroup instance (2 groups)
*                         and returns with it.
*
*                    > public static method fromGroup takes group g returns thistype
*                       - creates a new SwappedGroup instance, moves the units in 'g'
*                          to the group of the instance and returns with the instance.
*
*                       - Empties the group passed!
*
*                    > public method destroy takes nothing returns nothing
*                       - Releases the two groups and deallocates the instance.
*
*                    > public method addUnit takes unit u returns nothing
*                       - Add a unit to the current group.
*
*                    > public method removeUnit takes unit u returns nothing
*                       - Removes a unit from the current group.
*
*                    > public method contains takes unit u returns boolean
*                       - Returns true if the group contains u, false otherwise.
*
*                    > public method clear takes nothing returns nothing
*                       - Clears the current group.
*
*                    > public method refresh takes nothing returns nothing
*                       - Refreshes the group, cleaning it from all the ghost
*                         (removed from game) units that could screw over the
*                         enumeration. Please note that this comes with a 
*                         group swap in the background.
*
*                    > public method getNext takes nothing returns unit
*                       - If the group is not empty, returns the first unit
*                         of the group and adds it to the shadow group.
*                       - If the group is empty, returns 'null' and swaps the
*                         groups.
*
*            OPERATORS
*               >> public method operator group takes nothing returns group
*                   - Returns the current group.
*                   - The value returned is different after each enumeration.
*                   - It's only for compatibility with other resources (that
*                     expect regular groups), so try to use the methods above
*                     when possible.
*                   - NEVER under any circumstances use DestroyGroup or 
*                     ReleaseGroup on these groups!
*
*            MODULES
*               >> SGEnumBegin
*                   > Imports a new stataic method: enumerate.
*                   > enumerate has one parameter: enumGroup (SwappedGroup)
*                   > enumerate has one local variable: enumUnit (unit)
*
*                   > the module imports the specification of the method and
*                     opens the loop, which is to be closed by "SGEnumEnd".
*
*                   > enumUnit and enumGroup can be used in the loop to iterate
*                     over the group. Their values are not to be modified!
*
*               >> SGEnumEnd
*                    > Closes the loop opened by "SGEnumBegin".
*                    > Also responsible for doing the group swap.
*            
*            CREDITS
*                > Rising_Dusk for GroupUtils.
*            
*************************************************************************************/  
    globals
        private group array Groups
        
        private integer array BaseIndex
        private integer array CurrentIndex
        private integer array NextIndex
        
        private unit TempUnit
        private integer TempIndex
    endglobals
    
    struct SwappedGroup
        /*
        * Internal methods
        */
        private static method refreshCallback takes nothing returns nothing
            call GroupAddUnit(Groups[NextIndex[TempIndex]],GetEnumUnit())
        endmethod
        /*
        * Operators
        */
        public method operator group takes nothing returns group
            return Groups[CurrentIndex[this]]
        endmethod
        /*
        * Public methods
        */
        public static method create takes nothing returns thistype
            local thistype this=thistype.allocate()
            
            set BaseIndex[this]=((this-1)*2)
            set CurrentIndex[this]=BaseIndex[this]
            
            set Groups[BaseIndex[this]]=NewGroup()
            set Groups[BaseIndex[this]+1]=NewGroup()
            
            set NextIndex[BaseIndex[this]]=BaseIndex[this]+1
            set NextIndex[BaseIndex[this]+1]=BaseIndex[this]
            
            return this
        endmethod
        public static method fromGroup takes group g returns thistype
            local thistype this=thistype.create()
            local unit u
            
            loop
                set u=FirstOfGroup(g)
                exitwhen u==null
                call GroupRemoveUnit(g,u)
                call GroupAddUnit(Groups[CurrentIndex[this]],u)
            endloop
            
            return this
        endmethod
        public method destroy takes nothing returns nothing
            call ReleaseGroup(Groups[BaseIndex[this]])
            call ReleaseGroup(Groups[BaseIndex[this]+1])
            
            call this.deallocate()
        endmethod
        public method add takes unit u returns nothing
            call GroupAddUnit(Groups[CurrentIndex[this]],u)
        endmethod
        public method remove takes unit u returns nothing
            call GroupRemoveUnit(Groups[CurrentIndex[this]],u)
        endmethod
        public method contains takes unit u returns boolean
            return IsUnitInGroup(u,Groups[CurrentIndex[this]])
        endmethod
        public method clear takes nothing returns nothing
            call GroupClear(Groups[CurrentIndex[this]])
        endmethod
        public method refresh takes nothing returns nothing
            set TempIndex=CurrentIndex[this]
            
            call GroupClear(Groups[NextIndex[TempIndex]])
            call ForGroup(Groups[TempIndex],function thistype.refreshCallback)
            call GroupClear(Groups[TempIndex])
            
            set CurrentIndex[this]=NextIndex[TempIndex]
        endmethod
        public method getNext takes nothing returns unit
            set TempIndex=CurrentIndex[this]
            set TempUnit=FirstOfGroup(Groups[TempIndex])
            
            if (TempUnit!=null) then
                call GroupRemoveUnit(Groups[TempIndex],TempUnit)
                call GroupAddUnit(Groups[NextIndex[TempIndex]],TempUnit)
            else
                set CurrentIndex[this]=NextIndex[TempIndex]
            endif
            
            return TempUnit
        endmethod
    endstruct
    
    module SGEnumBegin
        public static method enumerate takes SwappedGroup enumGroup returns nothing
            local unit enumUnit
            
            set TempIndex=CurrentIndex[enumGroup]
            
            loop
                set enumUnit=FirstOfGroup(Groups[TempIndex])
                exitwhen enumUnit==null
                call GroupRemoveUnit(Groups[TempIndex],enumUnit)
                call GroupAddUnit(Groups[NextIndex[TempIndex]],enumUnit)
    endmodule
    
    module SGEnumEnd
            endloop
            
            set CurrentIndex[enumGroup]=NextIndex[TempIndex]
        endmethod
    endmodule
endlibrary

Module Demo

struct TestModule extends array
    
    private static SwappedGroup g1
    private static SwappedGroup g2
    
    implement SGEnumBegin
        call BJDebugMsg("- "+GetHeroProperName(enumUnit))
    implement SGEnumEnd
    
    private static method test takes nothing returns nothing
        call ClearTextMessages()
        
        call BJDebugMsg("Units in g1:")
        call thistype.enumerate(g1)
        
        call BJDebugMsg("\nUnits in g2:")
        call thistype.enumerate(g2)
    endmethod
    
    private static method refresh takes nothing returns nothing
        call g1.refresh()
        call g2.refresh()
    endmethod
    
    private static method onInit takes nothing returns nothing
        local unit u=CreateUnit(Player(0),'Hpal',0.,0.,0.)
        
        set thistype.g1=SwappedGroup.create()
        set thistype.g2=SwappedGroup.create()
        
        call thistype.g1.add(u)
        call thistype.g2.add(u)
        
        set u=CreateUnit(Player(0),'Hamg',0.,0.,0.)
        call thistype.g2.add(u)
        set u=CreateUnit(Player(0),'Hmkg',0.,0.,0.)
        call thistype.g2.add(u)
        set u=CreateUnit(Player(0),'Hblm',0.,0.,0)
        call thistype.g2.add(u)        
        
        call TimerStart(CreateTimer(),1.,true,function thistype.test)
        call TimerStart(CreateTimer(),10.5,true,function thistype.refresh)
    endmethod

endstruct

Changelog

1.0

• Initial release

1.1

• Added new modules to support "direct" enumerations.

1.1.1

• Alloc is no longer required.

1.2

• Added two new methods: "refresh", "contains".
• Group indexes are now stored in a temporary global variable, nearly halving the number of array reads in module based enumerations.

1.2.1

• "addUnit" renamed to "add".
• "removeUnit" renamed to "remove".
• New operator: "group".

 

[Luorax]

I'm kinda iffy about that 'if' in the 'getNext' method. I'm afraid it might slow the entire thing down to ForGroup's level. Hmm, I might have to go with the double module solution.

 

[BPower]

The public keyword is not nessesary. Alloc could be optional.

 

[Luorax]

The public keyword is not nessesary. Alloc could be optional.

It's not, but as you can see, I like to explicitly type out everything. It's not that big of a deal in JASS, but it makes your code clear in general (in a language like C++ it makes it a lot easier to understand what's going on).

Well, Alloc is widely used, and I've been using it too for quite some time. You don't even need to implement it, you just need to CnP it's code, so I can't see any trouble with it being required.

------------------

Anyways, I made a quick update. There was a missing 'then' in the code, and I added the 2 modules for even faster enumerations. Coding is faster with them too, although I'm generally not a big fan of that interface. But still, you need to make compromises sometimes. So much for studying formal languages today, I guess....

[EDIT]
For clarification: SG does NOT stand for Stargate.

 

[Bribe]

I like the idea behind this.

 

[TriggerHappy]

Can you link the required libraries?

And yes, Alloc should never be a requirement unless it's optional.

I also would prefer the public keyword wasn't there, however I guess that's up to you.

 

[Luorax]

Well, if you guys insist I'll remove Alloc completely tho - I've already tried like 3 or 4 different tricks to make it optional, none of them worked, and I think it'd be pointless to just CnP it into the code. I'll keep it as a regular struct.

I'm gonna link GroupUtils too (didn't do so because googling "wc3 grouputils" takes just as much time for me as copying the link, but I can see how it can be convenient for others, and I agree that I should have done it in the first place).

Well, as I said, I always type out everything explicitly, plus I want to make sure I don't forget about the public keyword in languages like Java or C#. I'm having a Prog2 (I'll go with Java, but it's either Java or C#) exam on the 6th of January, so making sure In C++ it's already caused me enough trouble when I forgot the public keyword when inheriting, I'd like to avoid that in the future.

Okay, so anything else? Don't think there's much left to do, though I've always prefered features over a few milliseconds, so feel free to let me know if you have some cool ideas.

 

[Troll-Brain]

There is a major issue with this : ghost units (units removed of the game), FirstOfGroup will return null with such units while the group would most likely be not empty.

 

[TriggerHappy]

I'll also have to benchmark this against just swapping the group directly.

 

[Luorax]

It's something that's always been an issue with FoG enumerations (well, most likely not with instantaneous ones, but if you store the units beforehand then yea). I can make a GroupUtils-esque 'refresh' method, if necessary.

You can always use for safety, but for my aura snippet, for example, where units are removed from the group immediately when they die, this is not a crucial, which can't be said about the speed.

I'll also have to benchmark this against just swapping the group directly.

Yea, I actually wanted to ask you to do it. What do you mean with directly though? I'm pretty sure the "getNext" solution isn't much faster than ForGroup (if it's even faster), but that's why I made the modules too, to provide an easy implementation of the direct swap (at the cost of being limited to one enumerator method per struct - but this is not an issue, the method is static, you can make as many enumerator structs as you want).

 

[Troll-Brain]

If you don't care about ghost units then i don't see why just not use a stack or whatever, instead of a group.

 

[Luorax]

It's something that's already crossed my mind, although I use IsUnitInGroup frequently (which I forgot to make a wrapper for - will be fixed), so I figured it'd be easier to do this, and the built-in functions are possibly faster than what I could ever make (after seeing how slow GetPlayerName is I'm starting to doubt it tho).

I still haven't had the time to touch my map, so I might in fact go with a stack. A HashTable (Table instance) could help with the O(1) lookup, so it's not that big of a deal. There's only one problem with that: removing units from the stack during enumeration. That wouldn't be a problem with a linked list, but with an ArrayList it could lead to some interesting behavior.

 

[TriggerHappy]

GetPlayerNameisn't slow at all, it's just slowerer compared to variable read.

 

[Troll-Brain]

IsUnitInGroup is not that useful when you use an unit indexer, easy as hell to link a boolean/integer/whatever to an unit.

 

[Anachron]

            set TempUnit=FirstOfGroup(Groups[CurrentIndex[this]])
           
            if (TempUnit!=null) then
                call GroupRemoveUnit(Groups[CurrentIndex[this]],TempUnit)
                call GroupAddUnit(Groups[NextGroup[CurrentIndex[this]]],TempUnit)
            else
                set CurrentIndex[this]=NextGroup[CurrentIndex[this]]
            endif
           
            return TempUnit

            local unit enumUnit
           
            loop
                set enumUnit=FirstOfGroup(Groups[CurrentIndex[enumGroup]])
                exitwhen enumUnit==null
                call GroupRemoveUnit(Groups[CurrentIndex[enumGroup]],enumUnit)
                call GroupAddUnit(Groups[NextGroup[CurrentIndex[enumGroup]]],enumUnit)

Isn't it faster if you store Groups[CurrentIndex[enumGroup]] into a local var?
You do two lookups in these functions, you only need one.

 

[Luorax]

GetPlayerNameisn't slow at all, it's just slowerer compared to variable read.

Well, I meant relatively slow. I just don't know what to expect after seeing these things.

 

[Anachron]

I like the change. I vote for approval now

 

[TriggerHappy]

I just don't like the useage of this, and the fact it requires you to code with structs.

It's probably just better to use the swapping method directly instead of relying on this.

 

[Luorax]

Well, it's either a method or a scope private function. Problem is, with a private function, you're limited to one enumerator per scope, whereas with structs you can have as many as you want as the struct name ensures the uniqueness (and provides a good prefix for describing what the enumerator does).

If you like to hardcode everything then fine with me, just go for it, but I personally prefer making libraries for whatever I might have to do multiple times.

What I could do though is I could make "enumUnit" global and make the module only contain the loop and the swap - that way you could insert them into whatever method/function you want, even multiple times per function/method. That's the best I can offer.

[EDIT]

Turns out the whiny JASSHelper will refuse to implement modules that contain no function/method specifications.

 

[Bribe]

Turns out the whiny JASSHelper will refuse to implement modules that contain no function/method specifications.

You have to implement a module into a function if that module doesn't contain a function.

 

[Luorax]

Yea, I know, that's what I've been doing -but I finally found the problem. It's simple: you cannot implement the same module into the same struct multiple times. Meh.... there goes the entire idea.

I could replace the modules with textmacros, but then I'd have to make the variables at least public, which I don't really want to do.

 

[TriggerHappy]

If you like to hardcode everything then fine with me, just go for it, but I personally prefer making libraries for whatever I might have to do multiple times.

Haha that's a stretch.

I'd lean more towards this implementation is terrible.

 

[Luorax]

I'm curious what better you could make.

 

[TriggerHappy]

I'm curious what better you could make.

I wouldn't make it better, that's the point.

Like I said it's probably better to just use the method directly.

That may be just me though, lets here what others think.

 

[Luorax]

Okay, I'm sorry then Thought you had some specific problem with the system and I felt kinda offended for calling it straight up terrible without even telling what that problem is. Because clearly, I don't see how it could be implemented better (a better interface would mean less safety [textmacros] or bad performance [interfaces], which I'd like to avoid).

Anyways, I'm adding a "group" operator, because there could be a million plus one snippets outs there that expect unit groups, and at the moment this is not compatible with any of them. Originally I had that operator instead of the wrappers, but I replaced it, but it's still necessary.

 

[Troll-Brain]

I could miss something but i still don't see the usefulness of that, if you don't have to keep units, use a group and a fog loop, if you need to keep them, use a linked list, il will even be more efficient.

 

[Luorax]

This has all the advantages a unit group has over a linked list: unlimited units per group, unlimited groups per struct/instance, lightweigth, O(1) lookup.

My problems with a linked list:

• Module (external, from the JASS section): due to one of the ultimate abilities, I need two: a temporary (a pre-selection) and one for the affected ones, that pass the second filter. With modules you're limited to one list per struct, which is insufficient.
• Struct with static unit limit: Auras are allocated/deallocated dynamically, and there're many of them. If I set the unit limit to to low then there's a chance that with all the minions, wards and other units around I run out of the space, and with a high limit I might run out of instances. There could be an optimal number, but I honestly don't want to risk bugs because of unstable implementation.
• Struct with dynamic unit limit: Dynamic allocation/deallocation -> fragmentation. It's easy to see this. Not to mention that you also need to keep track of the free and reserved space somehow. This is just like pages in memory management - same pattern, same problems.
• Self-made module: Problematic, I don't have the time at the moment to implement and maintain something like this.

And honestly, I just want to replace that ForGroup with a swapped group, I have much better and more important things to do than implementing stacks in JASS.

 

[Troll-Brain]

That's not that ligthweight, this should be even less efficient than an unit linked list.
But i have to agree that clearing the list would be O(N), unless you don't store units but only their index and use a custom allocator.

About the unlimited part, ok but franckly it should be only theorical, plus you're still concerned about the limit op when looping through the group.

I don't understand what you're trying to say in the module part.

About static unit limit i doubt you will ever reach 8190, but ok.

About dynamic unit: i hardly see where is the problem.

Don't take me wrong i'm not trying to bitch you, in my point of view this resource in the current state is wrong, but it's just me after all, i don't pretend to get the absolute thruth.

 

[TriggerHappy]

The idea behind this is great, however I don't think the current implementation feasible.

Voting for graveyard, unless ofc the OP or someone has something to say.

 

[Luorax]

I'm fairly sure it's the API that you have problems with. Yea, to be honest I've never really been a big fan of that silly module exploit, but the point of this was to abuse the FoG enumeration to its fullest, which is only possible using that exploit.

Now I know that certain methods should not be there (only the group operator, the rest of the accessors should be just straight up removed), but I'm not sure how the iteration should be done. If I wanted to remain fully automatic, I guess I could write a textmacro, with an "expression" parameter, where that would usually be a method/function call, the call of the callback function/method. It wouldn't add a lot to its execution time, but it'd most definitely look better and cleaner.

Another solution would be a swap() method, and leaving it up to the user to iterate the group. In that case, this would only be used to do the swapping, which, I guess, is still something.

The third one would be the "getNext()" method that is already there, but that's slow as f**k, so I don't think it stands a lot of chance against the other options.

With such limited tools that's all I can think of. But I'm still open for suggestions, of course.

 

[Zwiebelchen]

I don't get the purpose of this. A FoG loop that keeps its content is just a few lines of code, why would I ever want to use a lib for that? Especially since the major advantage of FoG is not neccessarily the speed but the fact that I can still access all locals in a FoG loop compared to a ForGroup loop.
Why would I want to bloat up my FoG loop with additional function calls that only makes it more complicated to use?

tl:dr: too much unneccessary overhead compared to manual implementation.

 

[Luorax]

The point is that you don't need to go through the trouble of implementing a FoG enumeration and the group swapping, both of those will be done by this snippet, and at compilation time. Like seriously, it has zero downsides, and even though it may not be a big system, it still doesn't quite fit into the Small Snippets thread.

"tl:dr: too much unneccessary overhead compared to manual implementation."

Couldn't this be said about a lot of other things? Implemeting a stack or a linked list is also a matter of minutes, yet we've got many resources that almost only do that. And this is marked as a "Snippet", precisely for that - its only purpose is to provide a fail-safe (god, how many times I've forgotten about the RemoveUnit call...) interface for FoG enumerations using group swapping

 

[TriggerHappy]

Yea but you increase the filesize by implementing a list in everything aka code bloat.

-mobile

 

[Zwiebelchen]

The point is that you don't need to go through the trouble of implementing a FoG enumeration and the group swapping, both of those will be done by this snippet, and at compilation time. Like seriously, it has zero downsides, and even though it may not be a big system, it still doesn't quite fit into the Small Snippets thread.

"tl:dr: too much unneccessary overhead compared to manual implementation."

Couldn't this be said about a lot of other things? Implemeting a stack or a linked list is also a matter of minutes, yet we've got many resources that almost only do that. And this is marked as a "Snippet", precisely for that - its only purpose is to provide a fail-safe (god, how many times I've forgotten about the RemoveUnit call...) interface for FoG enumerations using group swapping

You can just use a textmacro if you are too lazy to implement it yourself. This avoids the additional overhead and basicly does exactly the same.

And yes, linked list resources are bullshit for the same reason. That's why most resources that make heavy use of linked lists usually implement the list manually.

Also, FoG still requires considerably less function calls on manual implementation than any linked list, so the comparison is somewhat lacking.

local group g = EnumWhatever()
local group temp = CreateGroup()
local unit u
loop
     set u = FirstOfGroup(g)
     exitwhen u == null
     //stuff
     call GroupRemoveUnit(g, u)
     call GroupAddUnit(temp, u)
endloop
call DestroyGroup(g)
set g = temp
set temp = null

That's all a FoG loop needs. It doesn't even need any additional methods or functions like a linked list does. It's purely copy & paste. I don't see why someone would ever need a script for that.

And let's not forget to mention that you only need this if you want to leave the group intact - which is very rarely the case, as 99% of the time you will just want to do stuff for all units in range of X/Y.

If you want to use a group that hasn't been created in the same moment, you have to check for shadow references anyway - which makes the whole thing somewhat pointless, as then a ForGroup is faster.

 

[Troll-Brain]

If you want to use a group that hasn't been created in the same moment, you have to check for shadow references anyway - which makes the whole thing somewhat pointless, as then a ForGroup is faster.

I wouldn't bet on it, as ForForce "opens a new thread" on each iteration, it's quite costly. (like any native jass function which use a code / boolexpr by the way)
But yeah in almost any real case that doesn't matter.

Also, just saying but you can really be fast at linked list browsing, even if you decide to care about ghost units, at the cost of overheads though for all other operations (add, remove unit) + 'Adef' exploit to check and handle when an unit is removed of the game.

I know, i did a such resource, but people didn't seem to use it, and it used UnitIndexer, so rip for ever, i don't care to edit it. (don't worry i'm not complaining at all, just saying facts)

 

[TriggerHappy]

The concept is good but I don't think theres a logical, practical way of going about swapping groups in a public resource.

Scheduling for graveyard, unless Luorax has any problems with it.

EDIT: Graveyarded.