#### MyPad

**Spell Reviewer**

- Joined
- May 9, 2014

- Messages
- 1,628

I thought about coding a median form of a Binary Tree without using static array variables so here it is:

Hoping to improve this library in the future...

JASS:

```
library BinaryMedian
module BinaryMedian
private thistype nodeHead_next // globalized next linked list term for head instance
private thistype nodeHead_prev // globalized previous linked list term for head instance
private thistype nodeTree_next // localized next linked list term for instance
private thistype nodeTree_prev // localized previous linked list term for instance
private thistype nodeHead // The root head
private thistype node_tempHead // Current head for allocation
thistype head // Head of current instance
thistype left // left child
thistype right // right child
integer value // integer value
private method nodeHead_pop takes nothing returns nothing
set nodeHead_next.nodeHead_prev = nodeHead_prev
set nodeHead_prev.nodeHead_next = nodeHead_next
endmethod
private method nodeHead_push takes nothing returns nothing
set nodeHead_next = 0
set nodeHead_prev = nodeHead_next.nodeHead_prev
set nodeHead_next.nodeHead_prev = this
set nodeHead_prev.nodeHead_next = this
endmethod
private method nodeTree_pop takes nothing returns nothing
set nodeTree_next.nodeTree_prev = nodeTree_prev
set nodeTree_prev.nodeTree_next = nodeTree_next
endmethod
private method nodeTree_push takes thistype which returns nothing
set nodeTree_next = which
set nodeTree_prev = nodeTree_next.nodeTree_prev
set nodeTree_next.nodeTree_prev = this
set nodeTree_prev.nodeTree_next = this
endmethod
private static method nodeHead_search takes integer whichHead returns thistype
local thistype this = thistype(0).nodeHead_next
loop
exitwhen this == 0 or this == thistype(whichHead)
set this = this.nodeHead_next
endloop
return this
endmethod
private static thistype nHead = 0
private method adjust takes nothing returns nothing
local boolean isLeft = false
local boolean isRight = false
set nHead = this.nodeHead
loop
exitwhen this.head == 0 or (this.head.left == 0 or this.head.right == 0)
if this == this.head.left then
set isLeft = true
set isRight = false
exitwhen this.value <= this.head.value
set this.value = this.value + this.head.value
set this.head.value = this.value - this.head.value
set this.value = this.value - this.head.value
elseif this == this.head.right then
set isRight = true
set isLeft = false
exitwhen this.value >= this.head.value
set this.value = this.value + this.head.value
set this.head.value = this.value - this.head.value
set this.value = this.value - this.head.value
endif
set this = this.head
endloop
if (this.value > this.nodeHead.value and isRight) or (this.value < this.nodeHead.value and isLeft) then
set this.value = this.value + this.nodeHead.value
set this.nodeHead.value = this.value - this.nodeHead.value
set this.value = this.value - this.nodeHead.value
endif
loop
exitwhen this.right == 0 or this.value <= this.right.value
set this.value = this.value + this.nodeHead.value
set this.nodeHead.value = this.value - this.nodeHead.value
set this.value = this.value - this.nodeHead.value
set this = this.right
endloop
loop
exitwhen nHead == nHead.nodeHead.node_tempHead
set nHead = nHead.nodeTree_next
call nHead.adjust()
endloop
endmethod
method node_destroy takes nothing returns nothing
local thistype that = this.nodeHead.nodeTree_prev
set this.value = that.value
if that.head.right == that then
set that.head.right = 0
set that.nodeHead.node_tempHead = that.nodeHead.node_tempHead.nodeTree_prev
elseif that.head.left == that then
set that.head.left = 0
endif
set that.head = 0
set that.nodeHead = 0
set that.value = 0
call that.nodeTree_pop()
call this.adjust()
endmethod
method node_create takes integer whichHead, integer value returns thistype
local thistype that = nodeHead_search(whichHead)
if that == 0 then
// Head does not exist. Create one.
set that = this
set this.nodeTree_next = this
set this.nodeTree_prev = this
call this.nodeHead_push()
set this.nodeHead = this
set this.head = 0
set this.node_tempHead = this
set this.value = value
else
// Head exists (that). Insert the node.
if that.node_tempHead.left == 0 then
// Insert node to the left
set that.node_tempHead.left = this
set this.value = value
set this.nodeHead = that
set this.head = that.node_tempHead
call this.nodeTree_push(that)
call this.adjust()
elseif that.node_tempHead.right == 0 then
// Insert node to the right
set that.node_tempHead.right = this
set this.value = value
set this.nodeHead = that
set this.head = that.node_tempHead
call this.nodeTree_push(that)
// adjust the tempHead
set that.node_tempHead = that.node_tempHead.nodeTree_next
call this.adjust()
endif
endif
return this
endmethod
static method node_search takes integer whichHead, integer value returns thistype
local thistype head = thistype(whichHead).nodeHead
loop
exitwhen head == 0 or head.value == value
if value > head.value then
set head = head.right
elseif value < head.value then
set head = head.left
endif
endloop
return head
endmethod
endmodule
endlibrary
```

Hoping to improve this library in the future...

Last edited: