PruneGroup

[Anitarf]

I have been dissatisfied with my GroupGet library for a while now, but didn't really know how to change it until recently when I got some inspiration from this thread. The result is PruneGroup, a function that lets you pick any number of fittest units from a group instead of only one like GroupGet. The time complexity is O(n*k), where n is the number of units in the group and k is the number of units picked, so if you're only picking a single unit out of the group this function will be no less effective than GroupGet was.

PruneGroup:

library PruneGroup

//*****************************************************************
//*  PruneGroup
//*  written by: Anitarf
//*
//*  PruneGroup is a function that removes units from a group based
//*  on a user-specified fitness function.
//*
//*    function PruneGroup takes group g, Fitness Function, integer maxUnits, real minFitness returns nothing
//*
//*  The fitness function must follow the Fitness function 
//*  interface that is defined at the start of this library. The
//*  value it returns specifies a unit's fitness, the units with a
//*  higher value will remain in the group while the units with a
//*  lower fitness will be removed from it.
//*  The maxUnits argument specifies at most how many units may
//*  remain in the group, but the actual number may be lower if the
//*  group didn't have that many units in it to begin with or if
//*  too few units had a fitness higher than minFitness, the last
//*  argument of the PruneGroup function.
//*  The fitness limit can be disabled with the NO_FITNESS_LIMIT
//*  constant value defined in the calibration section, this way
//*  you can prune a group based only on the unit limit.
//*****************************************************************

    // This is the function interface for the fitness functions.
    public function interface Fitness takes unit u returns real

    globals
        // If this constant is passed to the PruneGroup function it will ignore the fitness limit.
        // This is a random value that is unlikely to be ever used, you don't really need to change it.
        constant real NO_FITNESS_LIMIT = -112358.13
    endglobals

// END OF CALIBRATION SECTION    
// ================================================================

    globals
        private Fitness func=0
        private integer maxcount=0
        private real minfit=0.0
        private boolean ignoreminfit=false
        
        private unit array fittest
        private real array fitness
        private integer array next
        private integer last=0
        private integer count=0
        private integer N=0
    endglobals

    private function Enum takes nothing returns nothing
        local unit u=GetEnumUnit()
        local real fit=func.evaluate(u)
        local integer i
        local integer j
        // Check if we should bother adding the unit to the list.
        if (ignoreminfit or fit>minfit) and (count<maxcount or fit>fitness[last]) then
            // Get a new index and store the unit.
            set N=N+1
            set count=count+1
            set fittest[N]=u
            set fitness[N]=fit
            // Add the index to the sorted list.
            if last==0 or fit<fitness[last] then
                set next[N]=last
                set last=N
            else
                set i=last
                loop
                    set j=next[i]
                    exitwhen j==0 or fitness[j]>=fit
                    set i=j
                endloop
                set next[N]=next[i]
                set next[i]=N
            endif
            // Remove the last unit from the list if needed.
            if count>maxcount then
                set last=next[last]
                set count=count-1
            endif
        endif
        set u=null
    endfunction

// ================================================================

    function PruneGroup takes group g, Fitness Function, integer maxUnits, real minFitness returns nothing
        // Remember the previous values in case this is interrupting another PruneGroup call.
        local Fitness f=func
        local integer mc=maxcount
        local real mf=minfit
        local integer l=last
        local integer c=count
        local integer n=N
        // Take care of faulty inputs.
        if maxUnits<=0 then
            call GroupClear(g)
            return
        endif
        // Populate the sorted list.
        set count=0
        set last=0
        set minfit=minFitness
        set maxcount=maxUnits
        set ignoreminfit=minfit==NO_FITNESS_LIMIT
        set func=Function
        call ForGroup(g, function Enum)
        // Repopulate the group from the list.
        call GroupClear(g)
        loop
            exitwhen last==0
            call GroupAddUnit(g, fittest[last])
            set last=next[last]
        endloop
        // Cleanup handle references.
        loop
            exitwhen N==n
            set fittest[N]=null
            set N=N-1
        endloop
        // Return the temporary globals to their previous values.
        set func=f
        set minfit=mf
        set maxcount=mc
        set ignoreminfit=minfit==NO_FITNESS_LIMIT
        set count=c
        set last=l
    endfunction

endlibrary

FitnessFunc:

library FitnessFunc requires PruneGroup

//*****************************************************************
//*  FITNESS FUNCTIONS
//*  written by: Anitarf
//*  requires: -PruneGroup
//*
//*  This is a set of functions intended to be used as fitness
//*  functions for PruneGroup calls, so they all take a unit
//*  parameter and return a real in accordance with the Fitness
//*  function interface. The functions provided cover most basic
//*  criteria according to which users might want to sort units.
//*  The functions are:
//*
//*  FitnessFunc_LowLife - favours units with low life
//*  FitnessFunc_HighLife - favours units with high life
//*  FitnessFunc_LowMaxLife - favours units with low max life
//*  FitnessFunc_HighMaxLife - favours units with high max life
//*  FitnessFunc_LowMana - favours units with low mana
//*  FitnessFunc_HighMana - favours units with high mana
//*  FitnessFunc_LowMaxMana - favours units with low max mana
//*  FitnessFunc_HighMaxMana - favours units with high max mana
//*  FitnessFunc_LowDistance - favours units closer to a point
//*  FitnessFunc_HighDistance - favours units further away from a point
//*
//*  The last two functions need to have a point defined before
//*  they can be used as a fitness function for PruneGroup, to
//*  define a point use the following function:
//*
//*    function SetFitnessPosition takes real x, real y returns nothing
//*****************************************************************

    //! textmacro PruneFitness_UnitState takes name, state
    public function Low$name$ takes unit u returns real
        return -GetUnitState(u, $state$)
    endfunction
    public function High$name$ takes unit u returns real
        return GetUnitState(u, $state$)
    endfunction
    //! endtextmacro

    //! runtextmacro PruneFitness_UnitState("Life", "UNIT_STATE_LIFE")
    //! runtextmacro PruneFitness_UnitState("Mana", "UNIT_STATE_MANA")
    //! runtextmacro PruneFitness_UnitState("MaxLife", "UNIT_STATE_MAX_LIFE")
    //! runtextmacro PruneFitness_UnitState("MaxMana", "UNIT_STATE_MAX_MANA")

// ================================================================

    globals
        private real X=0.0
        private real Y=0.0
    endglobals
    function SetFitnessPosition takes real x, real y returns nothing
        set X=x
        set Y=y
    endfunction

    public function LowDistance takes unit u returns real
        local real x = GetUnitX(u)-X
        local real y = GetUnitY(u)-Y
        return -x*x-y*y
    endfunction
    public function HighDistance takes unit u returns real
        local real x = GetUnitX(u)-X
        local real y = GetUnitY(u)-Y
        return x*x+y*y
    endfunction

endlibrary

[fX_]

shouldnt High$name$() return a positive correspondence of the measured state.

maybe associate (bunch) SetFitnessPosition(), with LowDistance() and HighDistance(), respectively, whether by their naming or what

i don't think the 'N' (global) gets restored like the other functional variables of Enum(), in PruneGroup().
can you "insert" an Enum() (or groupenums in general) while another Enum() is running? dont they queue up or work simultaneously?

[Veev]

Very clever, Anitarf: constant real NO_FITNESS_LIMIT = -112358.13

[Anitarf]

Originally Posted by fX_

shouldnt High$name$() return a positive correspondence of the measured state.

Right, that was sloppy of me, fixed.

maybe associate (bunch) SetFitnessPosition(), with LowDistance() and HighDistance(), respectively, whether by their naming or what

The both have Fitness in the name? But sure, if anyone has a better idea for the names, speak up.

i don't think the 'N' (global) gets restored like the other functional variables of Enum(), in PruneGroup().

Oh, but it does, it's just sneaky about it.

can you "insert" an Enum() (or groupenums in general) while another Enum() is running? dont they queue up or work simultaneously?

I use ForGroup, not GroupEnum. A lot of maps would crash and die if JASS could work simultaneously.

Originally Posted by Veev

Very clever, Anitarf: constant real NO_FITNESS_LIMIT = -112358.13

Meh, it's not that original.

[akolyt0r]

still you should use private/public for your constants.

[fX_]

didnt see that

JASS:

loop
set N=N-1
endloop

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
what i mean with all that "Enum() groupEnum" banter is does this interrupt older runs? is it possible to interrupt older ForGroup() runs and how?

[Anitarf]

Originally Posted by fX_

what i mean with all that "Enum() groupEnum" banter is does this interrupt older runs? is it possible to interrupt older ForGroup() runs and how?

It is possible if a fitness function itself calls PruneGroup. Since this library supports custom fitness functions, there's no way to ensure that that can't happen, so the code needs to take that possibility into account.

Originally Posted by akolyt0r

still you should use private/public for your constants.

No need, the NO_FITNESS_LIMIT is a pretty unique constant name, as for NO_UNIT_LIMIT, I'm thinking of removing it since if you have no unit limit, there's no need to use something as complicated as PruneGroup.

[Rising_Dusk]

I like this a lot more than your old approach. I've looked over it and don't see any glaring problems, so I think I will approve this and graveyard the old one. Is that okay?

[Anitarf]

Originally Posted by Rising_Dusk

I like this a lot more than your old approach. I've looked over it and don't see any glaring problems, so I think I will approve this and graveyard the old one. Is that okay?

Sure, if you didn't I was going to graveyard GroupGet myself.
I just did a minor update to the first post, I removed the NO_UNIT_LIMIT constant since if you don't have a unit limit then you needn't use PruneGroup in the first place, you can just do a simple ForGroup. Other than that, the code remains the same.

[Rising_Dusk]

Okay then, Approved.

[SanKakU]

is this for animals vs animals themed map?