- Joined
- Jul 10, 2007
- Messages
- 6,306
new thread
Still writing examples on how to iterate over the tree, but this is a standard tree.
How it works?
All nodes within the tree are trees themselves. A tree has a queue of children implemented as a list (this is so that any child can be arbitrarily removed). To remove a child, that child is destroyed.
From what I'm seeing so far, a Tree must be Shared and can only be either Shared or SharedNxUnique. There is also no point to having a static tree.
So far, I've written the breadth-first search algorithm for this
. I plan to write all of the others up too.
And some example code
Still writing examples on how to iterate over the tree, but this is a standard tree.
How it works?
All nodes within the tree are trees themselves. A tree has a queue of children implemented as a list (this is so that any child can be arbitrarily removed). To remove a child, that child is destroyed.
From what I'm seeing so far, a Tree must be Shared and can only be either Shared or SharedNxUnique. There is also no point to having a static tree.
So far, I've written the breadth-first search algorithm for this
. I plan to write all of the others up too.
JASS:
library Tree /* v1.0.0.0
************************************************************************************
*
* */uses/*
*
* */ ErrorMessage /* hiveworkshop.com/forums/submissions-414/snippet-error-message-239210/
*
************************************************************************************
*
* module Tree
*
* Description
* -------------------------
*
* Trees and nodes are the same
*
* Fields
* -------------------------
*
* readonly static integer sentinel
*
* readonly thistype root
* readonly thistype children
*
* readonly thistype next
*
* Methods
* -------------------------
*
* static method create takes nothing returns thistype
* method destroy takes nothing returns nothing
*
* method clear takes nothing returns nothing
*
* method insert takes nothing returns thistype
*
* debug static method calculateMemoryUsage takes nothing returns integer
* debug static method getAllocatedMemoryAsString takes nothing returns string
*
* Examples
* -------------------------
*
* Breadth-First (level by level)
*
* local UniqueQueue queue = UniqueQueue.create()
* local UniqueQueue children
*
* local thistype node = this.children
* local UniqueQueue child
*
* //first put into queue
* loop
* exitwhen node == 0
*
* call queue.enqueue(node)
*
* set node = node.next
* endloop
*
* //loop until there are no children
* loop
* set child = queue.first
* exitwhen child == 0
*
* //create a queue to store the next level's children
* set children = UniqueQueue.create()
*
* //loop over all children of current level
* loop
* set node = thistype(child).children
*
* //
* // Put Code Here
* //
*
* //loop over all children of current child
* loop
* exitwhen node == 0
*
* //now on next level, put next level's node into queue
* call children.enqueue(node)
*
* set node = node.next
* endloop
*
* set child = child.next
* exitwhen child == 0
* endloop
*
* //go to next level
* call queue.destroy()
* set queue = children
* endloop
*
* call queue.destroy()
*
* Depth-First (bottom up)
*
*
*
* In-Order (left to right)
*
*
*
* Post-Order (right to left)
*
*
*
************************************************************************************/
module Tree
/*
* All nodes within a tree are collections
*/
private static thistype collectionCount = 0
debug private boolean isCollection
private thistype _root
method operator root takes nothing returns thistype
debug call ThrowError(this == 0, "Tree", "root", "thistype", this, "Attempted To Read Null Node.")
debug call ThrowError(not isCollection, "Tree", "root", "thistype", this, "Attempted To Read Invalid Node.")
return _root
endmethod
private thistype _next
method operator next takes nothing returns thistype
debug call ThrowError(this == 0, "Tree", "next", "thistype", this, "Attempted To Go Out Of Bounds.")
debug call ThrowError(not isCollection, "Tree", "next", "thistype", this, "Attempted To Read Invalid Node.")
return _next
endmethod
private thistype _prev
private thistype _first
method operator children takes nothing returns thistype
debug call ThrowError(this == 0, "Tree", "children", "thistype", this, "Attempted To Read Null Node.")
debug call ThrowError(not isCollection, "Tree", "children", "thistype", this, "Attempted To Read Invalid Node.")
return _first
endmethod
private thistype _last
static method operator sentinel takes nothing returns integer
return 0
endmethod
private static method _allocateCollection takes nothing returns thistype
local thistype this = thistype(0)._first
if (0 == this) then
debug call ThrowError(collectionCount == 8191, "Tree", "allocateCollection", "thistype", 0, "Overflow.")
set this = collectionCount + 1
set collectionCount = this
else
set thistype(0)._first = _first
endif
return this
endmethod
private method _enqueue takes nothing returns thistype
local thistype node = _allocateCollection()
set node._root = this
if (_first == 0) then
set _first = node
set _last = node
set node._prev = 0
else
set _last._next = node
set node._prev = _last
set _last = node
endif
set node._next = 0
return node
endmethod
private method _remove takes nothing returns nothing
local thistype node = this
set this = node._root
set node._root = 0
if (0 == node._prev) then
set _first = node._next
else
set node._prev._next = node._next
endif
if (0 == node._next) then
set _last = node._prev
else
set node._next._prev = node._prev
endif
set node._next = thistype(0)._next
set thistype(0)._next = node
endmethod
private method _clear takes nothing returns nothing
if (_first == 0) then
return
endif
set _last._next = thistype(0)._next
set thistype(0)._next = _first
set _first = 0
set _last = 0
endmethod
static method create takes nothing returns thistype
local thistype this = _allocateCollection()
debug set isCollection = true
return this
endmethod
method destroy takes nothing returns nothing
local thistype node = _first
local thistype next
debug call ThrowError(this == 0, "Tree", "destroy", "thistype", this, "Attempted To Destroy Null Tree.")
debug call ThrowError(not isCollection, "Tree", "destroy", "thistype", this, "Attempted To Destroy Invalid Tree.")
loop
exitwhen node == 0
set next = node.next
call node._remove()
call node.destroy()
set node = next
endloop
call _clear()
if (_root != 0) then
call ._remove()
set _root = 0
endif
set _first = thistype(0)._first
set thistype(0)._first = this
debug set isCollection = false
endmethod
method clear takes nothing returns nothing
local thistype node = _first
local thistype next
debug call ThrowError(this == 0, "Tree", "clear", "thistype", this, "Attempted To Clear Null Tree.")
debug call ThrowError(not isCollection, "Tree", "clear", "thistype", this, "Attempted To Clear Invalid Tree.")
loop
exitwhen node == 0
set next = node.next
call node.destroy()
set node = next
endloop
set _first = 0
set _last = 0
endmethod
method insert takes nothing returns thistype
local thistype node
debug call ThrowError(this == 0, "Tree", "insert", "thistype", this, "Attempted To Insert To Null Tree.")
debug call ThrowError(not isCollection, "Tree", "insert", "thistype", this, "Attempted To Insert To Invalid Tree.")
set node = _enqueue()
debug set node.isCollection = true
return node
endmethod
static if DEBUG_MODE then
static method calculateMemoryUsage takes nothing returns integer
local thistype start = 1
local thistype end = collectionCount
local integer count = 0
loop
exitwhen integer(start) > integer(end)
if (integer(start) + 500 > integer(end)) then
return count + checkRegion(start, end)
else
set count = count + checkRegion(start, start + 500)
set start = start + 501
endif
endloop
return count
endmethod
private static method checkRegion takes thistype start, thistype end returns integer
local integer count = 0
loop
exitwhen integer(start) > integer(end)
if (start.isCollection) then
set count = count + 1
endif
set start = start + 1
endloop
return count
endmethod
static method getAllocatedMemoryAsString takes nothing returns string
local thistype start = 1
local thistype end = collectionCount
local string memory = null
loop
exitwhen integer(start) > integer(end)
if (integer(start) + 500 > integer(end)) then
if (memory != null) then
set memory = memory + ", "
endif
set memory = memory + checkRegion2(start, end)
set start = end + 1
else
if (memory != null) then
set memory = memory + ", "
endif
set memory = memory + checkRegion2(start, start + 500)
set start = start + 501
endif
endloop
return memory
endmethod
private static method checkRegion2 takes thistype start, thistype end returns string
local string memory = null
loop
exitwhen integer(start) > integer(end)
if (start.isCollection) then
if (memory == null) then
set memory = I2S(start)
else
set memory = memory + ", " + I2S(start) + "C"
endif
endif
set start = start + 1
endloop
return memory
endmethod
endif
endmodule
endlibraryAnd some example code
JASS:
struct UniqueQueue extends array
implement UniqueQueue
endstruct
struct TreeTester extends array
/*
* readonly string string
* readonly integer size
*/
implement Tree
string identifier
private method insertEx takes string identifier returns thistype
local thistype node = insert()
set node.identifier = identifier
return node
endmethod
private method breadthfirst takes nothing returns nothing
local UniqueQueue queue = UniqueQueue.create()
local UniqueQueue children
local thistype node = this.children
local UniqueQueue child
local string line
//first put into queue
loop
exitwhen node == 0
call queue.enqueue(node)
set node = node.next
endloop
loop
set child = queue.first
exitwhen child == 0
set line = ""
set children = UniqueQueue.create()
loop
if (line != "") then
set line = line + ", "
endif
set line = line + thistype(child).identifier
set node = thistype(child).children
loop
exitwhen node == 0
call children.enqueue(node)
set node = node.next
endloop
set child = child.next
exitwhen child == 0
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,line)
call queue.destroy()
set queue = children
endloop
call queue.destroy()
endmethod
private static method init takes nothing returns nothing
local thistype tree = create()
local thistype c1 = tree.insertEx("1")
local thistype c1_1 = c1.insertEx("1.1")
local thistype c2 = tree.insertEx("2")
local thistype c3 = tree.insertEx("3")
local thistype c3_1 = c3.insertEx("3.1")
local thistype c3_2 = c3.insertEx("3.2")
local thistype c3_2_1 = c3_2.insertEx("3.2.1")
local thistype c3_2_1_1 = c3_2_1.insertEx("3.2.1.1")
local thistype c4 = tree.insertEx("4")
local thistype c5 = tree.insertEx("5")
set tree.identifier = "root"
call tree.breadthfirst()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
call c3.destroy()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
call c1_1.destroy()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
call c4.destroy()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
call c5.destroy()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
call tree.destroy()
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,tree.string)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,"Memory Usage: " + I2S(calculateMemoryUsage()))
endmethod
private static method init0 takes nothing returns nothing
call DestroyTimer(GetExpiredTimer())
call init.execute()
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init0)
endmethod
private method operator string takes nothing returns string
local string base = identifier + "("
local string s = base
local thistype node = children
loop
exitwhen node == sentinel
if (s != base) then
set s = s + ", "
endif
set s = s + node.string
set node = node.next
endloop
return s + ")"
endmethod
private method operator size takes nothing returns integer
local integer sz = 0
local thistype node = children
loop
exitwhen node == sentinel
set sz = sz + node.size
set node = node.next
endloop
return sz + 1
endmethod
endstruct
Last edited:
