Nestharus
o-o
- Reaction score
- 83
JASS:
library AVL /* v1.1.0.4
*************************************************************************************
*
* An AVL Tree with a Linked List. The Linked List allows one to loop through all the values
* in the tree in ascendending or descending order. The tree allows on to search for exact or
* closest values.
*
* An AVL Tree specializes in searches. The balancing algorithm is a little heftier than its
* counterpart, the red-black tree. However, the heftier balancing ensures minimal iterations when
* searching for values.
*
* Plain value searches are O(1). The AVL Tree uses a hashtable in the background to do
* extremely fast precise value searches.
*
* Close value searches are O(1+log n). The value is first looked up in the hashtable
* to see if it exists. If it doesn't exist, a close approximiation is looked for. From there,
* it looks around that approximiation in the linked list for neighboring values that might be
* closer. The closer approximation is always at most 1 off from the actual value in the list.
*
*************************************************************************************
*
* */uses/*
*
* */ Table /* hiveworkshop.com/forums/jass-functions-413/snippet-new-table-188084/
*
************************************************************************************
*
* module AVLTree
*
* Interface:
* method lessThan takes thistype value returns boolean
* method greaterThan takes thistype value returns boolean
*
* readonly thistype tree
* - Tree pointer. Accessible from any node on the tree.
* readonly thistype root
* - Root of two children (if root is 0, it's the tree's root)
* readonly thistype left
* readonly thistype right
* readonly thistype down (tree pointer only)
* - The tree has only 1 child, the root
*
* readonly thistype next
* readonly thistype prev
* readonly boolean head
*
* readonly thistype value
* - Value stored in node
*
* static method create takes nothing returns thistype
* method destroy takes nothing returns nothing
*
* method search takes thistype value returns thistype
* - Returns the node containing the value
* - If the value didn't exist, it will return 0
* method searchClose takes thistype value, boolean low returns thistype
* - Searches for the best match to the value.
* -
* - Low = True
* - Search for the closest value <= to the target value
* -
* - Low = False
* - Search for the closest value >= to the target value
*
* method has takes thistype value returns boolean
* - Returns true if a node contains the value
*
* method add takes thistype value returns thistype
* - Returns new node containing added value. If the value
* - was already in the tree, it returns the node that already
* - contained that value.
* method delete takes nothing returns nothing
* - Deletes node
*
* -> Delete the value 15 from the tree if it exists
* -> call search(15).delete()
*
* method clear takes nothing returns thistype
* - Clears the tree of all nodes
* - Returns tree pointer (just in case some node in the tree was passed in rather than the tree)
*
************************************************************************************/
module AVL
private static Table array table //for O(1) searches on specific values
private static thistype c=0 //instance count
private static thistype array b //root
private static thistype array l //left
private static thistype array r //right
private static integer array h //height
private static thistype array p //parent
private static thistype array v //value
private static integer array nn //next node
private static integer array pn //prev node
private static integer array ro //root
method operator tree takes nothing returns thistype
return ro[this]
endmethod
method operator root takes nothing returns thistype
return p[this]
endmethod
method operator down takes nothing returns thistype
return b[this]
endmethod
method operator left takes nothing returns thistype
return l[this]
endmethod
method operator right takes nothing returns thistype
return r[this]
endmethod
method operator value takes nothing returns thistype
return v[this]
endmethod
method operator next takes nothing returns thistype
return nn[this]
endmethod
method operator prev takes nothing returns thistype
return pn[this]
endmethod
method operator head takes nothing returns boolean
return 0==p[this]
endmethod
private method getHeight takes nothing returns integer
//return the bigger leaf height
if (h[l[this]]>h[r[this]]) then
return h[l[this]]+1
endif
return h[r[this]]+1
endmethod
private method updateParent takes integer n returns nothing
//only update the parent of a target leaf if that leaf isn't the original leaf
if (n!=this) then
//update the parent point to
//first leaf
if (0==p[p[this]]) then
set b[p[this]]=n
//left
elseif (l[p[this]]==this) then
set l[p[this]]=n
//right
else
set r[p[this]]=n
endif
//update the leaf point back
//if the leaf isn't null, update the leaf's parent
if (0!=n) then
set p[n]=p[this]
endif
endif
endmethod
private method finishRotate takes thistype n returns nothing
//this code is identical in rotateLeft and rotateRight, so it has
//been abstracted to a method
call updateParent(n)
set p[this]=n
set h[this]=getHeight()
set h[n]=n.getHeight()
endmethod
private method rotateLeft takes nothing returns thistype
local thistype n=r[this]
set r[this]=l[n]
set p[l[n]]=this
set l[n]=this
call finishRotate(n)
return n
endmethod
private method rotateRight takes nothing returns thistype
local thistype n=l[this]
set l[this]=r[n]
set p[r[n]]=this
set r[n]=this
call finishRotate(n)
return n
endmethod
//return the difference between the left and right leaf heights
private method getBalanceFactor takes nothing returns integer
return h[l[this]]-h[r[this]]
endmethod
private static method allocate takes nothing returns thistype
local integer n
if (0==nn[0]) then
set n=c+1
set c=n
else
set n=nn[0] //notice that the recycler uses the next pointer
//the reason it is used is for fast clear/destroy and to save
//a variable
set nn[0]=nn[n]
endif
set l[n]=0 //left leaf
set r[n]=0 //right leaf
set b[n]=0 //down leaf (first node of tree)
set h[n]=1 //height (a node will always have at least a height of 1 for itself)
return n
endmethod
static method create takes nothing returns thistype
local integer n=allocate()
set p[n]=0 //the parent of the tree node is 0
//initialize tree next and prev
set nn[n]=n
set pn[n]=n
//tree value table for O(1) searches on specific values
set table[n]=Table.create()
//tree root is itself (allows one to pass any node from the tree into the methods)
set ro[n]=n
return n
endmethod
//balance from the current node up to the root O(log n)
//balancing is rotations wherever rotations need to be done
private method balance takes nothing returns nothing
local integer f
loop
exitwhen 0==p[this]
set h[this]=getHeight()
set f=getBalanceFactor()
if (2==f) then
if (-1==l[this].getBalanceFactor()) then
call l[this].rotateLeft()
endif
set this=rotateRight()
return
elseif (-2==f) then
if (1==r[this].getBalanceFactor()) then
call r[this].rotateRight()
endif
set this=rotateLeft()
return
endif
set this=p[this]
endloop
endmethod
//goes to the very bottom of a node (for deletion)
private method getBottom takes nothing returns thistype
if (0!=r[this]) then
if (0!=l[this]) then
set this=r[this]
loop
exitwhen 0==l[this]
set this=l[this]
endloop
return this
else
return r[this]
endif
elseif (0!=l[this]) then
return l[this]
endif
return this
endmethod
method search takes thistype val returns thistype
return table[ro[this]][val]
endmethod
method has takes thistype val returns boolean
return table[ro[this]].has(val)
endmethod
method searchClose takes thistype val, boolean low returns thistype
local thistype n
//retrieve tree
set this=ro[this]
//if tree is empty, return 0
if (0==b[this]) then
return 0
endif
//check to see if the node exists in the tree and return it if it does
set n=table[this][val]
if (0!=n) then
return n
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=b[this]
loop
if (val.lessThan(v[this])) then
exitwhen 0==l[this]
set this=l[this]
else
exitwhen 0==r[this]
set this=r[this]
endif
endloop
//look at the found value's neighbors on the linked list
if (low) then
//shift down if greater than
if (v[this].greaterThan(val)) then
set this=prev
endif
//return 0 if node wasn't found
if (0==p[this] or v[this].greaterThan(val)) then
return 0
endif
else
//shift up if less than
if (v[this].lessThan(val)) then
set this=next
endif
//return 0 if node wasn't found
if (0==p[this] or v[this].lessThan(val)) then
return 0
endif
endif
return this
endmethod
method add takes thistype val returns thistype
local thistype n
//check if the tree already has the value in it
set this=ro[this]
set n=table[this][val]
//if the tree doesn't have the value in it, add the value
if (0==n) then
set n=this
set this=allocate()
set ro[this]=n //store tree into leaf
set table[n][val]=this //store leaf into value table
set v[this]=val //store value into leaf
//if the tree is empty
if (0==b[n]) then
set b[n]=this //place as first node
set p[this]=n //parent of first node is tree
//add to list
set nn[this]=n
set pn[this]=n
set nn[n]=this
set pn[n]=this
else
//go to the first node in the tree
set n=b[n]
//go to the bottom of the tree with search algorithm
loop
if (val.lessThan(v[n])) then
exitwhen 0==l[n]
set n=l[n]
else
exitwhen 0==r[n]
set n=r[n]
endif
endloop
//add leaf to tree
set p[this]=n
if (val.lessThan(v[n])) then
set l[n]=this
else
set r[n]=this
endif
//update the height of the parent
set h[n]=n.getHeight()
//balance from the parent upwards
call p[n].balance()
//add leaf to list
if (v[n].greaterThan(v[this])) then
set n=pn[n]
endif
set nn[this]=nn[n]
set pn[this]=n
set pn[nn[n]]=this
set nn[n]=this
endif
return this
endif
return n
endmethod
method delete takes nothing returns nothing
local thistype n
local thistype y
//if the leaf to be deleted isn't 0 and the leaf isn't the tree
if (0 != this and 0 != p[this]) then
//remove the leaf from the value table
call table[ro[this]].remove(v[this])
set n=getBottom() //retrieve the bottom leaf
set y=p[n] //store the parent here for balancing later
//move the found leaf into the deleted leaf's position
call n.updateParent(0)
call updateParent(n)
if (this!=n) then
set l[n]=l[this]
set p[l[n]]=n
set r[n]=r[this]
set p[r[n]]=n
set p[n]=p[this]
set h[n]=h[this]
endif
//balance from the found leaf's old parent upwards
call y.balance()
//remove deleted leaf from list
set nn[pn[this]]=nn[this]
set pn[nn[this]]=pn[this]
set nn[this]=nn[0]
set nn[0]=this
endif
endmethod
method clear takes nothing returns thistype
//quick clear
set this=ro[this]
set nn[pn[this]]=nn[0]
set nn[0]=nn[this]
set nn[this]=this
set pn[this]=this
return this
endmethod
method destroy takes nothing returns nothing
//quick destroy
set this=ro[this]
set nn[pn[this]]=nn[0]
set nn[0]=this
call table[this].destroy()
endmethod
endmodule
endlibraryJASS:
struct Tester extends array
private method lessThan takes thistype val returns boolean
return integer(this)<integer(val)
endmethod
private method greaterThan takes thistype val returns boolean
return integer(this)>integer(val)
endmethod
private method difference takes thistype val returns integer
return integer(this)-integer(val)
endmethod
implement AVL
private static method init takes nothing returns nothing
local thistype this=create()
local thistype node1=add(1)
local thistype node2=add(2)
local thistype node3=add(3)
//call clear()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60," "+I2S(down.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60," "+I2S(down.left.value)+" "+I2S(down.right.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60," "+I2S(down.left.left.value)+" "+I2S(down.left.right.value)+" "+I2S(down.right.left.value)+" "+I2S(down.right.right.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,I2S(down.left.left.left.value)+" "+I2S(down.left.left.right.value)+" "+I2S(down.left.right.left.value)+" "+I2S(down.left.right.right.value)+" "+I2S(down.right.left.left.value)+" "+I2S(down.right.left.right.value)+" "+I2S(down.right.right.left.value)+" "+I2S(down.right.right.right.value))
call DestroyTimer(GetExpiredTimer())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init)
endmethod
endstructJASS:
struct Tester extends array
private method lessThan takes thistype val returns boolean
return integer(this)<integer(val)
endmethod
private method greaterThan takes thistype val returns boolean
return integer(this)>integer(val)
endmethod
private method difference takes thistype val returns integer
return integer(this)-integer(val)
endmethod
implement AVL
private static method init takes nothing returns nothing
local thistype this=create()
local thistype s
local string str=""
call add(5)
call add(10)
call add(15)
call add(20)
call add(25)
call add(30)
call add(35)
call add(40)
call add(45)
call add(50)
call add(55)
call add(60)
call add(65)
call add(70)
call add(75)
loop
set this=next
exitwhen head
if (str=="") then
set str=I2S(value)
else
set str=str+","+I2S(value)
endif
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,str)
set s = searchClose(22,false)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"22 High -> "+I2S(s.value))
set s = searchClose(22,true)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"22 Low -> "+I2S(s.value))
call DestroyTimer(GetExpiredTimer())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init)
endmethod
endstruct
