- Joined
- Jul 10, 2007
- Messages
- 6,306
Coded this while working on boolean expression and solved the big problem I needed, so I don't need all of this code. Putting it up in case anyone wants to use any of it for anything. It's actually pretty neat 
. You can join nodes (any), split nodes apart, join at a node introducing a new node, and then print the ranges of the parent nodes.
The base of the tree is a list. The list is split up into partitions, these being the leaves of the tree. Any partition can be iterated over (specific partition).
. You can join nodes (any), split nodes apart, join at a node introducing a new node, and then print the ranges of the parent nodes.The base of the tree is a list. The list is split up into partitions, these being the leaves of the tree. Any partition can be iterated over (specific partition).
JASS:
private struct Node extends array
thistype root
thistype left
thistype right
thistype next
thistype prev
thistype sentinel
boolexpr expression
implement Alloc
method toString takes nothing returns string
local thistype i = prev
local string s = ""
if (i == 0) then
set i = this
endif
loop
if (s == "") then
set s = I2S(i)
else
set s = s + ", " + I2S(i)
endif
exitwhen sentinel == i or i == this or i == 0
set i = i.next
endloop
return s
endmethod
static method create takes nothing returns thistype
return allocate()
endmethod
private method destroy takes nothing returns nothing
if (left == 0) then
call DestroyBoolExpr(expression)
set expression = null
else
set left = 0
set right = 0
set root = 0
set next = 0
set prev = 0
endif
call deallocate()
endmethod
method destroySub takes nothing returns nothing
if (left == 0) then
call DestroyBoolExpr(expression)
set expression = null
else
call left.destroySub()
call right.destroySub()
set left = 0
set right = 0
set root = 0
set next = 0
set prev = 0
endif
call deallocate()
endmethod
private method delink takes nothing returns nothing
local thistype left = this.left
local thistype right = this.right
if (left == 0) then
if (prev != 0) then
set prev.next = next
set prev = 0
endif
if (next != 0) then
set next.prev = prev
set next = 0
endif
else
loop
exitwhen left.left == 0
set left = left.left
endloop
loop
exitwhen right.right == 0
set right = right.right
endloop
if (left.prev != 0) then
set left.prev.next = right.next
set left.prev = 0
endif
if (right.next != 0) then
set right.next.prev = left.prev
set right.next = 0
endif
endif
endmethod
private method link takes Node left, Node right returns nothing
if (left.left == 0) then
if (right.left == 0) then
set left.next = right
set right.prev = left
set this.prev = left
set this.next = right
set this.sentinel = right
else
set left.next = right.prev
set right.prev.prev = left
set this.prev = left
set this.next = right.next
set this.sentinel = right.next
endif
elseif (right.left == 0) then
set left.next.next = right
set right.prev = left.next
set this.prev = left.prev
set this.next = right
set this.sentinel = right
else
set left.next.next = right.prev
set right.prev.prev = left.next
set this.prev = left.prev
set this.next = right.next
set this.sentinel = right.next
endif
endmethod
private method relink takes nothing returns nothing
if (this == 0) then
return
endif
loop
if (left.left == 0) then
if (right.left == 0) then
set this.prev = left
set this.next = right
set this.sentinel = right
else
set this.prev = left
set this.next = right.next
set this.sentinel = right.next
endif
elseif (right.left == 0) then
set this.prev = left.prev
set this.next = right
set this.sentinel = right
else
set this.prev = left.prev
set this.next = right.next
set this.sentinel = right.next
endif
set this = root
exitwhen this == 0
endloop
endmethod
private method replaceRootChild takes thistype newChild returns nothing
set newChild.root = root
if (root != 0) then
if (this == root.left) then
set root.left = newChild
else
set root.right = newChild
endif
call root.relink()
endif
endmethod
static method mergeRight takes Node left, Node right returns Node
local Node this = Node.create()
call link(left, right)
call right.replaceRootChild(this)
set this.left = left
set this.right = right
set left.root = this
set right.root = this
loop
set expression = Or(left.expression, right.expression)
set this = root
exitwhen this == 0
call DestroyBoolExpr(expression)
endloop
return this
endmethod
static method mergeLeft takes Node left, Node right returns Node
local Node this = Node.create()
call link(left, right)
set this.left = left
set this.right = right
set left.root = this
set right.root = this
call left.replaceRootChild(this)
loop
set expression = Or(left.expression, right.expression)
set this = root
exitwhen this == 0
call DestroyBoolExpr(expression)
endloop
return this
endmethod
static method merge takes Node left, Node right returns Node
local Node this = Node.create()
call link(left, right)
set this.left = left
set this.right = right
set left.root = this
set right.root = this
set expression = Or(left.expression, right.expression)
return this
endmethod
method splitLeft takes nothing returns Node
local thistype left = this.left
if (left == 0) then
return this
endif
call replaceRootChild(right)
call destroy()
call left.delink()
return left
endmethod
method splitRight takes nothing returns Node
local thistype right = this.right
local thistype left = this.left
if (right == 0) then
return this
endif
call replaceRootChild(left)
call destroy()
call right.delink()
return right
endmethod
endstruct
