GFreak45
I didnt slap you, i high 5'd your face.
- Reaction score
- 130
NOTE: this library was not made to quickly add loads of data to a struct all at once and sort it instantly, this was made to be able to find the closest value to a specified value in under 20 conditions/variable adjustments and no function calls, and it is also not complete, but should i put more time into this and can it be a high quality resource in the future?
JASS:
library BST /* v0.01
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* *
* Binary Search Tree Module v0.01 *
* by G_Freak45 *
* *
* Requires: *
* *
* Some vJass knowledge, but no other libraries *
* 'NOTE': Having some knowledge on linked lists and binary search trees isnt *
* needed but will help when using this system *
* *
* About the system: *
* *
* Creates a dynamic binary search tree that sorts a linked list accordingly and *
* allows for incredibly quick searches for values in the sorted linked list. *
* 'NOTE': This was not made to quickly add/remove isntances but rather find *
* the instance with the closest value to the value provided *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* *
* Methods, Modules, and Variables. Oh my!!! *
* *
* implement BST *
* -This module creates a binary search tree using a real value to sort the *
* available instances *
* *
* implement BSTint (Coming Soon) *
* -This module creates a binary search tree using integers to sort the struct *
* *
* private method BST_getValue takes nothing returns real *
* -You must have this method in your struct 'ABOVE' the module *
* -Struct isntances are sorted using this method to determine their values *
* *
* private static method find takes real r, thistype start returns thistype *
* -This method finds a value based on the available "real r" starting at the *
* specified starting instance, if the tree branched from this instance does *
* not contain the value requested within its min and max values it will *
* return its parent *
* 'NOTE': Always returns the "next" instance, or rounds up every time if it *
* is not equal to another instances value *
* *
* private boolean isTwin and private thistype nextTwin/prevTwin *
* -isTwin can be used to determine if the instance has a twin (equal value) *
* instance, and nextTwin/prevTwin can be used to itterate through the list of *
* twins for a given twin instance *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* *
* Additional Notes: *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
module BST
thistype parent
thistype next
thistype prev
thistype left
thistype right
thistype sibling
boolean isTwin
thistype nextTwin
thistype prevTwin
thistype domTwin
integer depth
thistype nextDepth
thistype prevDepth
static thistype array recycleList
static thistype listSize
static thistype allocInterface
static trigger allocTrig
static thistype zeroChild
private method find takes thistype start returns thistype
local thistype loop = start
local thistype ret
if start = start.parent.left and start.parent.prev.value < this.value then
return start.parent
elseif start = start.parent.right and start.parent.next.value > this.value then
return start.parent.next
endif
loop
if this.value > loop.value then
set loop = loop.right
if loop.isNull == false then
set ret = loop
endif
elseif this.value < loop.value then
set loop = loop.left
if loop.isNull == false then
set ret = loop
endif
elseif this.value == loop.value then
return loop
endif
exitwhen (0 = loop.left and 0 = loop.right) or (this.value > loop.value and 0 == loop.right) or (this.value < loop.value and 0 == loop.left)
endloop
if this.value > ret.value then
set ret = ret.prev
endif
return ret
endmethod
private static method allocCond takes nothing returns boolean
local thistype this = allocInterface
local thistype find
call TriggerSleepAction(0.0001)
set this.value = this.BST_getValue()
set find = this.find(zeroChild)
set this.depth = find.depth + 1
set this.next = find
set this.prev = find.prev
set this.prev.next = this
set find.prev = this
if 0 != find.left and find.left.value == this.value then
if not find.left.isNull then
set this.isTwin = true
set this.nextTwin = find.left
set this.prevTwin = find.left.prevTwin
set find.left.prevTwin = this
set this.prevTwin.nextTwin = this
else
set this.isTwin = false
set this.left = find.left.left
set this.right = find.left.right
set this.left.parent = this
set this.right.parent = this
set this.next = find.left.next
set this.prev = find.left.prev
set this.next.prev = this
set this.prev.next = this
endif
elseif 0 != find.left and find.left.value != this.value then
set this.prev.right = this
set this.parent = this.prev
else
set find.left = this
set this.parent = find
endif
return false
endmethod
private static method allocate takes real r returns thistype
local thistype this = recycleList[0]
if 0 == this then
debug if listSize = 8190 then
debug call BJDebugMsg("BST ERROR: Your struct containing " + thistype.allocate.name + " has exceeded 8190 instances."
debug return 0
debug endif
set allocInterface = listSize
call TriggerEvaluate(allocTrig)
set listSize = listSize + 1
return listSize
endif
set allocInterface = listSize
call TriggerEvaluate(allocTrig)
set recycleList[0] = recycleList[this]
return this
endmethod
private method deallocate takes nothing returns nothing
if this.isTwin = false then
if 0 == this.left and 0 == this.right then
if this.parent.value > this.value then
set this.parent.left = 0
else
set this.parent.right = 0
endif
set this.parent = 0
elseif 0 == this.left then
if this.parent.value > this.value then
set this.parent.left = this.right
else
set this.parent.right = this.right
endif
set this.right.parent = this.parent
set this.parent = 0
set this.right = 0
elseif 0 == this.right then
if this.parent.value > this.value then
set this.parent.left = this.left
else
set this.parent.right = this.left
endif
set this.left.parent = this.parent
set this.parent = 0
set this.left = 0
elseif SquareRoot(Pow(this.next.value - this.value, 2)) < SquareRoot(Pow(this.prev.value - this.value, 2)) then
set this.next.parent.left = 0
set this.next.parent = this.parent
set this.next.right = this.right
set this.next.left = this.left
set this.right.parent = this.next
set this.left.parent = this.next
if this.value > this.parent.value then
set this.parent.right = this.next
else
set this.parent.left = this.next
endif
else
set this.prev.parent.left = 0
set this.prev.parent = this.parent
set this.prev.right = this.right
set this.prev.left = this.left
set this.right.parent = this.prev
set this.left.parent = this.prev
if this.value > this.parent.value then
set this.parent.right = this.prev
else
set this.parent.left = this.prev
endif
endif
set this.next.prev = this.prev
set this.prev.next = this.next
else
if this.domTwin = this then
set this.nextTwin.parent = this.parent
set this.nextTwin.right = this.right
set this.nextTwin.left = this.left
set this.left.parent = this.nextTwin
set this.right.parent = this.nextTwin
set this.nextTwin.next = this.next
set this.nextTwin.prev = this.prev
set this.next.prev = this.nextTwin
set this.prev.next = this.nextTwin
if this.value > this.parent.value then
set this.parent.right = this.nextTwin
else
set this.parent.left = this.nextTwin
endif
set i = this.nextTwin.nextTwin
set this.nextTwin.prevTwin = this.prevTwin
set this.prevTwin.nextTwin = this.nextTwin
loop
exitwhen i == i.domTwin
set i.domTwin = this.nextTwin
set i = i.nextTwin
endloop
else
set this.nextTwin.prevTwin = this.prevTwin
set this.prevTwin.nextTwin = this.nextTwin
endif
endif
endmethod
endmodule
endlibrary
