[vJASS] Binary Tree Median

[MyPad]

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

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...

 

[IcemanBo]

It's same things always at first. : )
+ Description
+ API
maybe a short example would be helpful.

Here, and in others; why each time implementing your own alloc? If performance is considered, just require an existing alloc, and then all submissions may use it instead of rewrting it each time. : )

 

[MyPad]

I'm going to change this library from Binary Tree Median to just plain Binary Tree. I've already accomplished writing up BinaryHeap_MAX and I will just recode that and finish it with BinaryHeap_MIN. After that, I will add documentation.

I also prefer writing my own allocation instead of outsourcing it so that the user would not think about importing other libraries to make the library work.

 

[IcemanBo]

I also prefer writing my own allocation instead of outsourcing

That's a philosophy against OOP and modular coding. When you use indexers, or damage detection you would implement them, too? Probably not. And that's smaller, but pretty much the same philophy. Better to make it clear, and to outsource logics. If you care much about handy code, you even can use the default allocation methodic- we would accept this, too. You can let it, if you want, but it's not a perfect habit I think to reproduce same functionality.

 

[Flux]

I would suggest just use the default allocation method like IcemanBo said. I know it's not the best, but for public resource it is. If users don't want that, they can edit the resource manually by simply adding "extends array" and "implement Alloc".

 

[MyPad]

Oh, that Allocation method. I finally remembered its purpose... being a demo module. I'll remove that and the struct below as the library is composed of the main code and the demo code.

 

[Almia]

or rather add something like requires optional Alloc

 

[Flux]

You can with implement optional Alloc but how are you gonna make extends array optional?

 

[Aniki]

You can with implement optional Alloc but how are you gonna make extends array optional?

A static if seems to work:

library Foo uses optional Alloc

globals
    private constant boolean Use_Alloc = false
endglobals

private module BarImplementation
    string baz

    static method create takes string baz returns thistype
        local thistype this = allocate()
        set this.baz = baz
        return this
    endmethod

    // Alloc does not give us a destroy method, unlike vJass's default allocation
    // which aliases destroy to deallocate
    method destroy takes nothing returns nothing
        call this.deallocate()
    endmethod
endmodule

static if LIBRARY_Alloc and Use_Alloc then

struct Bar extends array
    implement Alloc
    implement BarImplementation
endstruct

else

struct Bar
    implement BarImplementation
endstruct

endif

endlibrary


function main takes nothing returns nothing
    local Bar bar = Bar.create("abc")
    call bar.destroy()
endfunction

PS: I think MyPad's Alloc (Malloc, MyAlloc, MyPalloc? =)) is better (if we ignore the instance counting stuff, which is not needed) than this one.