Jesus4Lyf
Good Idea™
- Reaction score
- 397
The latest in "Black Magic". This is effectively an array object that can be created/destroyed, has no size limitations (practically), and can take absolutely any index that works as a WC3 integer.
It uses a forking singularly linked list. The complexity for read/write varies strongly, but once I add balancing (if I ever do) it will settle to about O(log(n)), which is pretty good. Depends if people want this sort of thing. It is already fully functional, it can just be optimised.
So uh. Yeah, this is a bunch of arrays, converted into structs, converted into linked-list nodes, converted into trees, which are encapsulated to be used effectively as arrays. What of it?
Test demonstration (instead of demo map):
Oh, and Azlier... No pointer node!
It uses a forking singularly linked list. The complexity for read/write varies strongly, but once I add balancing (if I ever do) it will settle to about O(log(n)), which is pretty good. Depends if people want this sort of thing. It is already fully functional, it can just be optimised.
JASS:
library BTree
struct BTree
private BTree left=0
private BTree right=0
private integer index
private integer value=0
method operator[] takes integer index returns integer
loop
if this.index==index then
return this.value
endif
if index>this.index then
set this=this.right
else
set this=this.left
endif
exitwhen this==0
endloop
return 0
endmethod
method operator[]= takes integer index, integer value returns nothing
loop // No exitwhen!
if this.value==0 then
set this.index=index
set this.value=value
return
endif
if this.index==index then
set this.value=value
return
endif
if index>this.index then
if this.right==0 then
set this.right=BTree.create()
endif
set this=this.right
else
if this.left==0 then
set this.left=BTree.create()
endif
set this=this.left
endif
endloop
endmethod
private method onDestroy takes nothing returns nothing
if this.left!=0 then
call this.left.destroy()
endif
if this.right!=0 then
call this.right.destroy()
endif
endmethod
endstruct
endlibrarySo uh. Yeah, this is a bunch of arrays, converted into structs, converted into linked-list nodes, converted into trees, which are encapsulated to be used effectively as arrays. What of it?
Test demonstration (instead of demo map):
JASS:
scope Test initializer TestBTree
private function TestBTree takes nothing returns nothing
local BTree t=BTree.create()
set t[50]=1
set t[25]=2
set t[75]=3
set t[76]=4
set t[577151337]=5
call BJDebugMsg(I2S(t[50]))
call BJDebugMsg(I2S(t[25]))
call BJDebugMsg(I2S(t[75]))
call BJDebugMsg(I2S(t[76]))
call BJDebugMsg(I2S(t[577151337]))
call t.destroy()
endfunction
endscope
