[System] UnitSegmentTree

[Nestharus]

library UnitSegmentTree /* v1.0.2.0
*************************************************************************************
*
*   A cross between a range and segment tree that orders units by x and then y
*
*   The front tree stores x's. From there, each x has its own tree that stores y's.
*   It is like a range tree as each node has a tree within it. It is like a segment
*   tree as the first dimension can easily retrieve all y coordinates that fit within
*   a range x.
*
*************************************************************************************
*
*   */uses/*
*
*       */ UnitIndexer          /*          hiveworkshop.com/forums/jass-functions-413/unit-indexer-172090/
*       */ AVL                  /*          hiveworkshop.com/forums/jass-resources-412/snippet-avl-tree-203168/
*
*************************************************************************************

*   struct UnitSegmentTree extends array
*
*       Fields
*       --------------------
*       readonly integer value
*       readonly UnitSegmentTreeY tree
*       readonly thistype next
*       readonly thistype prev
*       readonly boolean head
*
*       Methods
*       --------------------
*       static method create takes nothing returns UnitSegmentTree
*       method add takes UnitIndex whichUnit returns nothing
*       method remove takes UnitIndex whichUnit returns nothing
*       method update takes UnitIndex whichUnit returns nothing
*       method clear takes nothing returns nothing
*       method destroy takes nothing returns nothing
*       method search takes UnitIndex whichUnit returns UnitSegmentTreeY
*       method getUnitsInSegment takes real x, real y, real distance returns SortedUnitList
*       method getUnitsInSegmentTree takes real x, real y, real distance returns UnitTree
*
*************************************************************************************
*
*   struct UnitSegmentTreeY extends array
*
*       Fields
*       --------------------
*       readonly integer value
*       readonly UnitSegmentTree parent
*       readonly UnitIndex index
*       readonly thistype next
*       readonly thistype prev
*       readonly boolean head
*
*       Methods
*       --------------------
*       method searchClose takes integer y, boolean low returns UnitSegmentTreeY
*
*************************************************************************************
*
*   struct SortedUnitList extends array
*
*       Fields
*       --------------------
*       readonly thistype next
*       readonly thistype prev
*       readonly UnitIndex index
*       readonly integer count
*       readonly boolean head
*
*       Methods
*       --------------------
*       static method create takes nothing returns SortedUnitList
*       method add takes UnitIndex whichUnit returns SortedUnitList
*       method addList takes SortedUnitList list returns nothing
*       method remove takes nothing returns nothing
*       method clear takes nothing returns nothing
*       method destroy takes nothing returns nothing
*
*************************************************************************************
*
*   struct UnitTreeXY extends array
*
*       readonly UnitIndex index
*       readonly thistype next
*       readonly thistype prev
*       readonly boolean head
*
*       static method create takes nothing returns UnitTreeXY
*       method destroy takes nothing returns nothing
*       method search takes thistype value returns UnitTreeXY
*       method searchClose UnitIndex index, boolean low returns UnitTreeXY
*       method searchCloseMag2 takes real magnitudeSquared, boolean low returns thistype
*       method add takes UnitIndex index returns thistype
*       method delete takes nothing returns nothing
*       method clear takes nothing returns UnitTreeXY
*
*************************************************************************************/
    struct UnitTreeXY extends array
        method operator index takes nothing returns UnitIndex
            return value
        endmethod
        method operator x takes nothing returns real
            return GetUnitX(index.unit)
        endmethod
        method operator y takes nothing returns real
            return GetUnitY(index.unit)
        endmethod
        private method lessThan takes thistype value returns boolean
            local real x = this.x
            local real y = this.y
            local real x2 = value.x
            local real y2 = value.y
            return x*x+y*y < x2*x2+y2*y2
        endmethod
        
        private method greaterThan takes thistype value returns boolean
            local real x = this.x
            local real y = this.y
            local real x2 = value.x
            local real y2 = value.y
            return x*x+y*y > x2*x2+y2*y2
        endmethod
        
        private method lessThanM takes real mag returns boolean
            local real x = this.x
            local real y = this.y
            return x*x+y*y < mag
        endmethod
        
        private method greaterThanM takes real mag returns boolean
            local real x = this.x
            local real y = this.y
            return x*x+y*y > mag
        endmethod
        
        method searchCloseMag2 takes real m, boolean low returns thistype
            local thistype n
            
            //if tree is empty, return 0
            if (0 == down) then
                return 0
            endif
            
            //perform a standard tree search for the value to the bottom of the tree
            //will always be at most 1 off from the best match
            set this = down
            loop
                if (value.lessThanM(m)) then
                    exitwhen 0 == left
                    set this = left
                else
                    exitwhen 0 == right
                    set this = right
                endif
            endloop
            
            //look at the found value's neighbors on the linked list
            if (low) then
                //shift down if greater than
                if (value.greaterThanM(m)) then
                    set this = prev
                endif
                //return 0 if node wasn't found
                if (0 == root or value.greaterThanM(m)) then
                    return 0
                endif
            else
                //shift up if less than
                if (value.lessThanM(m)) then
                    set this = next
                endif
                //return 0 if node wasn't found
                if (0 == root or value.lessThanM(m)) then
                    return 0
                endif
            endif
            
            return this
        endmethod
        
        implement AVL
    endstruct
    
    struct SortedUnitList extends array
        private static integer instanceCount = 0
        readonly thistype next
        readonly thistype prev
        readonly UnitIndex index
        readonly integer count
        private integer parent
        readonly boolean head
        
        private static method allocate takes nothing returns thistype
            local thistype this = thistype(0).next
            if (0 == this) then
                set this = instanceCount + 1
                set instanceCount = this
            else
                set thistype(0).next = next
            endif
            
            return this
        endmethod
        private method deallocate takes nothing returns nothing
            set next = thistype(0).next
            set thistype(0).next = this
        endmethod
        private static method deallocateSegment takes thistype first, thistype last returns nothing
            set last.next = thistype(0).next
            set thistype(0).next = first
        endmethod
        
        static method create takes nothing returns thistype
            local thistype this = allocate()
            
            set head = true
            
            set next = this
            set prev = this
            set count = 0
            set parent = 0
            set index = 0
            
            return this
        endmethod
        
        method add takes UnitIndex whichUnit returns thistype
            local thistype node = allocate()
            
            set node.prev = prev
            set node.next = this
            set prev.next = node
            set prev = node
            
            set node.parent = this
            set node.index = whichUnit
            
            set count = count + 1
            
            return this
        endmethod
        method addList takes SortedUnitList list returns nothing
            if (not list.next.head) then
                set prev.next = list.next
                set list.next.prev = prev
                set prev = list.prev
                set list.prev.next = this
                
                set list.next = list
                set list.prev = prev
                
                set count = count + list.count
                
                set list.count = 0
            endif
        endmethod
        
        method remove takes nothing returns nothing
            set prev.next = next
            set next.prev = prev
            
            call deallocate()
            
            set this = parent
            
            set count = count - 1
        endmethod
        method clear takes nothing returns nothing
            if (not next.head) then
                call deallocateSegment(next, prev)
                
                set next = this
                set prev = this
                
                set count = 0
            endif
        endmethod
        method destroy takes nothing returns nothing
            call deallocateSegment(this, prev)
        endmethod
    endstruct
    
    private struct TreeY_p extends array
        UnitIndex whichUnit
        
        method lessThan takes integer value returns boolean
            return integer(this) < value
        endmethod
        
        method greaterThan takes integer value returns boolean
            return integer(this) > value
        endmethod
        
        implement AVL
    endstruct
    
    private keyword TreeX
    
    private struct TreeY extends array
        readonly TreeX parent
        static method create takes TreeX parent returns thistype
            local thistype this = TreeY_p.create()
            
            set this.parent = parent
            
            return this
        endmethod
        method add takes integer y, UnitIndex whichUnit returns nothing
            set this = TreeY_p(this).add(y)
            
            set TreeY_p(this).whichUnit = whichUnit
        endmethod
        method operator value takes nothing returns integer
            return TreeY_p(this).value
        endmethod
        method operator whichUnit takes nothing returns UnitIndex
            return TreeY_p(this).whichUnit
        endmethod
        method clear takes nothing returns nothing
            call TreeY(this).clear()
        endmethod
        method operator next takes nothing returns thistype
            return TreeY_p(this).next
        endmethod
        method operator prev takes nothing returns thistype
            return TreeY_p(this).prev
        endmethod
        method operator head takes nothing returns boolean
            return TreeY_p(this).head
        endmethod
        method operator unit takes nothing returns UnitIndex
            return TreeY_p(this).whichUnit
        endmethod
        method remove takes integer y returns nothing
            set this = TreeY_p(this).search(y)
            
            call TreeY_p(this).delete()
        endmethod
        method destroy takes nothing returns nothing
            call TreeY_p(this).destroy()
        endmethod
        method search takes integer y returns thistype
            return TreeY_p(this).search(y)
        endmethod
        method searchClose takes integer y, boolean low returns TreeY
            return TreeY_p(this).searchClose(y, low)
        endmethod
    endstruct
    
    private struct TreeX_p extends array
        method lessThan takes integer value returns boolean
            return integer(this) < value
        endmethod
        
        method greaterThan takes integer value returns boolean
            return integer(this) > value
        endmethod
        
        implement AVL
    endstruct
    
    private struct TreeX extends array
        private TreeY treeY
        method operator value takes nothing returns integer
            return TreeX_p(this).value
        endmethod
        method operator tree takes nothing returns TreeY
            return treeY
        endmethod
        method operator next takes nothing returns thistype
            return TreeX_p(this).next
        endmethod
        method operator prev takes nothing returns thistype
            return TreeX_p(this).prev
        endmethod
        method operator head takes nothing returns boolean
            return TreeX_p(this).head
        endmethod
        static method create takes nothing returns thistype
            return TreeX_p.create()
        endmethod
        method add takes integer x, integer y, UnitIndex whichUnit returns nothing
            set this = TreeX_p(this).add(x)
            if (0 == treeY) then
                set treeY = TreeY.create(this)
            endif
            call treeY.add(y, whichUnit)
        endmethod
        method clear takes nothing returns nothing
            loop
                set this = next
                exitwhen head
                call treeY.clear()
                set treeY = 0
            endloop
            call TreeX_p(this).clear()
        endmethod
        method remove takes integer x, integer y returns nothing
            set this = TreeX_p(this).search(x)
            call treeY.remove(y)
            if (treeY.next.head) then
                call treeY.destroy()
                set treeY = 0
                call TreeX_p(this).delete()
            endif
        endmethod
        method destroy takes nothing returns nothing
            loop
                set this = next
                exitwhen head
                call treeY.destroy()
                set treeY = 0
            endloop
            call TreeX_p(this).destroy()
        endmethod
        method search takes integer x, integer y returns TreeY
            set this = TreeX_p(this).search(x)
            return treeY.search(y)
        endmethod
        method searchClose takes integer x, integer y, boolean low returns TreeY
            set this = TreeX_p(this).searchClose(x, low)
            
            return treeY.searchClose(y, low)
        endmethod
    endstruct
    
    struct UnitSegmentTreeY extends array
        method operator value takes nothing returns integer
            return TreeY(this).value
        endmethod
        method operator parent takes nothing returns UnitSegmentTree
            return TreeY(this).parent
        endmethod
        method operator index takes nothing returns UnitIndex
            return TreeY(this).whichUnit
        endmethod
        method operator next takes nothing returns thistype
            return TreeY(this).next
        endmethod
        method operator prev takes nothing returns thistype
            return TreeY(this).prev
        endmethod
        method operator head takes nothing returns boolean
            return TreeY(this).head
        endmethod
        method searchClose takes integer y, boolean low returns UnitSegmentTreeY
            return TreeY(this).searchClose(y, low)
        endmethod
        method getUnitsInSegment takes integer y0, integer ymin, integer ymax, SortedUnitList list returns nothing
            local UnitSegmentTreeY yp = searchClose(y0, true)
            local UnitSegmentTreeY y
            
            /*
            *   loop backwards
            */
            set y = yp
            loop
                exitwhen y.value < ymin or y.head
                call list.add(y.index)
                set y = y.prev
            endloop
            
            /*
            *   loop forwards
            */
            set y = yp
            loop
                set y = y.next
                exitwhen y.value > ymax or y.head
                call list.add(y.index)
            endloop
        endmethod
        method getUnitsInSegmentTree takes integer y0, integer ymin, integer ymax, UnitTreeXY tree returns nothing
            local UnitSegmentTreeY yp = searchClose(y0, true)
            local UnitSegmentTreeY y
            
            /*
            *   loop backwards
            */
            set y = yp
            loop
                exitwhen y.value < ymin or y.head
                call tree.add(y.index)
                set y = y.prev
            endloop
            
            /*
            *   loop forwards
            */
            set y = yp
            loop
                set y = y.next
                exitwhen y.value > ymax or y.head
                call tree.add(y.index)
            endloop
        endmethod
    endstruct
    
    struct UnitSegmentTree extends array
        private Table x
        private Table y
        method operator value takes nothing returns integer
            return TreeX(this).value
        endmethod
        method operator tree takes nothing returns UnitSegmentTreeY
            return TreeX(this).tree
        endmethod
        method operator next takes nothing returns thistype
            return TreeX(this).next
        endmethod
        method operator prev takes nothing returns thistype
            return TreeX(this).prev
        endmethod
        method operator head takes nothing returns boolean
            return TreeX(this).head
        endmethod
        static method create takes nothing returns thistype
            local thistype this = TreeX.create()
            
            set x = Table.create()
            set y = Table.create()
            
            return this
        endmethod
        method add takes UnitIndex whichUnit returns nothing
            set x[whichUnit] = R2I(GetUnitX(whichUnit.unit))
            set y[whichUnit] = R2I(GetUnitX(whichUnit.unit))
        
            call TreeX(this).add(x[whichUnit], y[whichUnit], whichUnit)
        endmethod
        method remove takes UnitIndex whichUnit returns nothing
            call TreeX(this).remove(x[whichUnit], y[whichUnit])
        endmethod
        method update takes UnitIndex whichUnit returns nothing
            local integer x2 = R2I(GetUnitX(whichUnit.unit))
            local integer y2 = R2I(GetUnitX(whichUnit.unit))
            local integer x0 = x[whichUnit]
            local integer y0 = y[whichUnit]
            
            if (x0 - 128 > x2 or x0 + 128 < x2 or y0 - 128 > x2 or y0 + 128 < x2) then
                call TreeX(this).remove(x0, y0)                
                
                set x[whichUnit] = x2
                set y[whichUnit] = y2
                
                call TreeX(this).add(x2, y2, whichUnit)
            endif
        endmethod
        method clear takes nothing returns nothing
            call x.flush()
            call y.flush()
            
            call TreeX(this).clear()
        endmethod
        method destroy takes nothing returns nothing
            call TreeX(this).destroy()
        endmethod
        method search takes UnitIndex whichUnit returns UnitSegmentTreeY
            return TreeX(this).search(x[whichUnit], y[whichUnit])
        endmethod
        method searchClose takes integer x, integer y, boolean low returns UnitSegmentTreeY
            return TreeX(this).searchClose(x, y, low)
        endmethod
        method getUnitsInSegment takes real xr, real yr, real dr returns SortedUnitList
            local integer x0 = R2I(xr)
            local integer y0 = R2I(yr)
            local integer distance = R2I(dr)
            local integer xmin = x0 - distance
            local integer xmax = x0 + distance
            local integer ymin = y0 - distance
            local integer ymax = y0 + distance
            local UnitSegmentTree xp
            local UnitSegmentTree x
            local SortedUnitList list = SortedUnitList.create()
            
            set xp = searchClose(x0, y0, true)
            set x = xp
            loop
                /*
                *   loop backwards
                */
                exitwhen x.value < xmin or x.head
                
                call x.tree.getUnitsInSegment(y0, ymin, ymax, list)
                
                set x = x.prev
            endloop
            
            set x = xp
            loop
                /*
                *   loop fowards
                */
                set x = x.next
                exitwhen x.value > xmax or x.head
                call x.tree.getUnitsInSegment(y0, ymin, ymax, list)
            endloop
            
            return list
        endmethod
        method getUnitsInSegmentTree takes real xr, real yr, real dr returns UnitTreeXY
            local integer x0 = R2I(xr)
            local integer y0 = R2I(yr)
            local integer distance = R2I(dr)
            local integer xmin = x0 - distance
            local integer xmax = x0 + distance
            local integer ymin = y0 - distance
            local integer ymax = y0 + distance
            local UnitSegmentTree xp
            local UnitSegmentTree x
            local UnitTreeXY tree = UnitTreeXY.create()
            
            set xp = searchClose(x0, y0, true)
            set x = xp
            loop
                /*
                *   loop backwards
                */
                exitwhen x.value < xmin or x.head
                
                call x.tree.getUnitsInSegment(y0, ymin, ymax, tree)
                
                set x = x.prev
            endloop
            
            set x = xp
            loop
                /*
                *   loop fowards
                */
                set x = x.next
                exitwhen x.value > xmax or x.head
                call x.tree.getUnitsInSegment(y0, ymin, ymax, tree)
            endloop
            
            return tree
        endmethod
    endstruct
endlibrary

Demonstration

struct Tester extends array
    private static method onInit takes nothing returns nothing
        local unit u1
        local unit u2
        local unit u3
        local unit u4
        
        local UnitIndex ui1
        local UnitIndex ui2
        local UnitIndex ui3
        local UnitIndex ui4
        
        local UnitSegmentTree tree = UnitSegmentTree.create()
        local UnitSegmentTree x
        local UnitSegmentTreeY y
        
        set u1 = CreateUnit(Player(0), 'hfoo', GetStartLocationX(0) + 512, GetStartLocationY(0) - 512, 270)
        set u2 = CreateUnit(Player(0), 'hrif', GetStartLocationX(0) + 512, GetStartLocationY(0) - 512, 270)
        set u3 = CreateUnit(Player(0), 'hgtw', GetStartLocationX(0) - 512, GetStartLocationY(0) + 512, 270)
        set u4 = CreateUnit(Player(0), 'hpea', GetStartLocationX(0) - 512, GetStartLocationY(0) + 512, 270)
        
        set ui1 = GetUnitUserData(u1)
        set ui2 = GetUnitUserData(u2)
        set ui3 = GetUnitUserData(u3)
        set ui4 = GetUnitUserData(u4)
        
        call tree.add(ui1)
        call tree.add(ui2)
        call tree.add(ui3)
        call tree.add(ui4)
        
        set x = tree
        loop
            set x = x.next
            exitwhen x.head
            set y = x.tree
            loop
                set y = y.next
                exitwhen y.head
                call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,GetUnitName(y.index.unit)+" at ("+I2S(x.value)+","+I2S(y.value)+")")
            endloop
        endloop
    endmethod
endstruct

 

[Magtheridon96]

:O

This is the system you were asking me to code half a year ago

You actually coded it

Good Job bro ^.^

*reads code*

edit
Nice. Barely any function calls in this.
How many units can it handle smoothly?

 

[Bribe]

"An tree of units ordered by x and then y"

Nice description, bro.

 

[Nestharus]

That's all you need to know if you know what a range tree is.

It's not my thing to write tutorials on common data structures ;p. If you want to learn what a range tree is, google it =).

 

[Bribe]

Wenn Sie dies verstehen wollen, können Sie Google auch. However, there is a reason why Hive is also an English-only forum, just as there is a reason why we want descriptions with submitted resources.

Not everyone studies programming structures in a classroom environment, and not everyone studies the German language. Plus there are many different implementations of different programming structures. Don't bring up this Google argument again, you are just being rude to people who have less experience than you.

 

[Nestharus]

Ok, this isn't a range tree.. it's a cross between a range tree and a segment tree. It is closer to a segment tree, hm... because of this, I will add the description -> cross between range and segment tree =D.

edit
ok, because this is an abomination of a tree, I added a description, lol.

 

[Zwiebelchen]

I'm confused. What does this one do?
Is it something like a faster method to enum units in range?

If so, how much faster compared to enumeration?

 

[Nestharus]

Honestly haven't benched it, but I'll get to it : ).

 

[Zwiebelchen]

Honestly haven't benched it, but I'll get to it : ).

Looking forward to it. Although I doubt it will be much faster than enumeration. I'm pretty sure blizzard also used some tree logic in enumeration.

In case it is indeed faster than EnumUnitsInRange, can you provide us with a library that automaticly runs and registers units to it based on a unit indexing event and provides us with EnumUnitsInRangeEx?

 

[Magtheridon96]

Blizzard uses some Quad Tree for finding units in range (I think)

 

[Troll-Brain]

Good job, you've broken your very own resource.

 

[Nestharus]

Blehz... changing name

Wenn Sie dies verstehen wollen, können Sie Google auch. However, there is a reason why Hive is also an English-only forum, just as there is a reason why we want descriptions with submitted resources.

Not everyone studies programming structures in a classroom environment, and not everyone studies the German language. Plus there are many different implementations of different programming structures. Don't bring up this Google argument again, you are just being rude to people who have less experience than you.

Absolutely pointless argument. This is a programming section, not a German section. If it were a German section, then you shouldn't have to explain public German stuff -.-. If it's a programming section, then you shouldn't have to explain public programming stuff.

I only added a description because this resource is my own abomination on public common data structures. If it were actually a normal common tree, I would absolutely refuse to write a description.

This is again a programming section, thus it is up to the users to learn what a data structure is if it is a normal public data structure. It is not up to the coder to explain something like what a Linked List is in a Linked List resource. That is not the author's problem, that's your problem for refusing to google it.

You don't require people to explain what a queue is, so you shouldn't be requiring people to explain more complicated common data structures. Even if you implemented a rule requiring people to explain all data structures they implemented, I wouldn't follow it because that would be an asinine rule.

Again, it's not my problem that you don't know what a segment tree, interval tree, and so on are, it is purely your problem. Stop lashing out just because you don't want to google up the info. You are the moderator, so you need the knowledge in order to moderate these things. I also know that I am not being any better since I am refusing to be a moderator : |.

 

[Bribe]

Programming data structures are potentially wildly different in implementation. You should at the least provide a direct link to the exact implementation you use.

And you caught yourself on this one after I pointed out that different structures can have different implementations, it made you decide to point out that you needed to correct your "description" (ie. add one).

I added a pretty verbose description to MissileRecycler not for you, but for people who were new to the concept and wanted to know why it's a useful resource. I suppose if you got a job as a salesperson you would know why "selling" your work is practical.

 

[Nestharus]

I am not sure as to the usefulness of this. I will need to bench it against GroupEnumUnitsInRange with a first of group loop.


I wrote this with custom targeting in mind, but I came up with a better way to do custom targeting, so who knows, maybe I got to waste my time writing a useless resource that belongs in the graveyard again ;D.

 

[Zwiebelchen]

I am not sure as to the usefulness of this. I will need to bench it against GroupEnumUnitsInRange with a first of group loop.


I wrote this with custom targeting in mind, but I came up with a better way to do custom targeting, so who knows, maybe I got to waste my time writing a useless resource that belongs in the graveyard again ;D.

Just benchmark it. If it's faster, it has a legitimation if you could write a GroupEnumUnitsInRangeEx

 

[Magtheridon96]

Nes, can you /please/ benchmark this against GroupEnumUnitsInRange already? :L

 

[Nestharus]

eh, just gy it

 

[Magtheridon96]

Okay, but if you're ever planning on benchmarking this against GroupEnumUnitsInRange, or getting someone else to do it for you, then I'll gladly move this to the Approved JASS Resources section, update all my spells, and see if I can get a new standard spread (A GroupEnumUnitsInRangeEx standard), but this will depend highly on the speed difference.
If it's 10% faster, keep the resource, forget the standard. If it's 150% faster, keep the resource AND make the standard.