- Joined
- Mar 29, 2016
- Messages
- 688
Linked-List that allows dynamic nesting (Tree of Lists).
Script
Nested iteration sample:
Script
JASS:
library TreeList /* v1.1
*/uses /*
*/Table /* https://www.hiveworkshop.com/threads/snippet-new-table.188084/
*/ErrorMessage /* https://github.com/nestharus/JASS/blob/master/jass/Systems/ErrorMessage/main.j
*///! novjass
|-------------|
| Description |
|-------------|
/*
A list which nodes are another list of nodes - basically, a tree of list.
The lists are implemented as circular doubly linked-lists.
This snippet shares the same instance reservior with the Table library.
But this is not a problem since the Table instances limit is insanely
big (around 2^31 - 1 instances) so lets say you have many systems that
might use around 100,000 Table instances (which is very unlikely). Then
you just need around 20,000 of those sytems in order to reach the Table
instances limit.
On the contrary, what seems like a con can actually turn out to be an
advantage, that is, you can directly use the nodes of this snippet as
fully functional Table instances without worrying about possible
collisions and use them to store various data.
*/
|-----|
| API |
|-----|
struct TreeList/*
*/readonly TreeList prev /* The previous member
*/readonly TreeList next /* The next member
*/readonly TreeList first /* The first member of the node's list
*/readonly TreeList last /* The last member of the node's list
*/readonly integer size /* The current size of the list (i.e., its children population)
*/readonly boolean isEmpty /* Boolean flag that tells if the node's list is empty
*/static method create takes nothing returns TreeList/*
- Creates a new list
*/method destroy takes nothing returns nothing/*
- Destroys a list
*/method insert takes TreeList node returns this/*
- Inserts a node next to this node
*/method remove takes nothing returns this/*
- Removes this node
*/method push takes TreeList node returns this/*
- Inserts a node to the front of this node's list
*/method pop takes nothing returns this/*
- Removes the front of this node's list
*/method enqueue takes TreeList node returns this/*
- Inserts a node to the back of this node's list
*/method dequeue takes nothing returns this/*
- Removes the back of this node's list
*/method clear takes nothing returns this/*
- Clears this node's list
*/method flush takes boolean destroyNodes returns this/*
- Flushes this node's list
*/method mergeChildren takes nothing returns this/*
- Merges the nodes of the child lists of this node's list
- This operation destroys this node's child nodes
*/method mergeDescendants takes nothing returns this/*
- Performs a chain of mergeChildren operations starting from this node up
to the leaf nodes
- Basically just combines all the leaf nodes and puts them into this node's
list
*/method collapseBranch takes nothing returns this/*
- Puts the children of this node to its own level and appends them as its
next and before its former 'next'
*/method collapse takes nothing returns this/*
- Performs a chain of collapseBranch operations starting from this node up
to its leaf nodes
*/method rotate takes boolean clockwise returns this/*
- Rotates this node's list clockwise or counter-clockwise depending on the
boolean parameter
*/module TreeListTransversal/*
- Implement this module below your method named onTransverse (may or may not
be a static method). Then, whenever you call TreeList(instance).transverse(),
your method named onTransverse will run for each node starting from the root
up to the leaves.
- Method onTransverse must take nothing and return a boolean. If it returns
false, the transversal will halt.
Textmacros for iteration
- Use these to iterate over a list named 'this' (which means that you must have
a TreeList variable named 'this' within your method). Then you can refer to the
same variable ("this") inside the iteration block to access the currently
iterated node in the list. The original value of the variable "this" will be
restored after the iteration.
*/textmacro TREE_LIST_ITERATOR_START takes CLOCKWISE/*
- run at the beginning of your iteration code block
- "CLOCKWISE" is a boolean parameter that determines the direction of iteration
- clockwise iteration iterates from the first node to the last node while
counter-clockwise iteration does the opposite
*/textmacro TREE_LIST_ITERATOR_END/*
- run at the end of your iteration code block
Note that you can nest these macros to iterate the children of the current iterated
node. This method is slower compared to manually iterating as it involves hashtable
lookups plus some other additional operations to accommodate for the possibility of
nested iterations. But this will prove very useful for some deep nested iterations
as it would eliminate the need for many local variable declarations and would make
your script very much readable and shorter.
*///! endnovjass
private keyword Init
struct TreeList extends array
debug private static Table allocated
private static Table prevT
private static Table nextT
private static Table listT
private method operator list takes nothing returns thistype
return listT[this]
endmethod
method operator prev takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "prev", "thistype", this, "Attempted to access an unallocated instance field")
return prevT[this]
endmethod
method operator next takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "next", "thistype", this, "Attempted to access an unallocated instance field")
return nextT[this]
endmethod
method operator first takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "first", "thistype", this, "Attempted to access an unallocated instance field")
return this.list.next
endmethod
method operator last takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "last", "thistype", this, "Attempted to access an unallocated instance field")
return this.list.prev
endmethod
private method operator prev= takes integer node returns nothing
set prevT[this] = node
endmethod
private method operator next= takes integer node returns nothing
set nextT[this] = node
endmethod
private method operator list= takes integer node returns nothing
set listT[this] = node
endmethod
static method create takes nothing returns thistype
local thistype this = Table.create()
local thistype list = Table.create()
set list.prev = list
set list.next = list
set this.list = list
set thistype(-list).list = this
debug set allocated[this] = 1
debug set allocated[list] = 1
return this
endmethod
method destroy takes nothing returns nothing
local thistype list = this.list
debug call ThrowError(allocated[this] == 0, "TreeList", "destroy()", "thistype", this, "Attempted to doubly destroy instance")
call Table(this).destroy()
call Table(list).destroy()
set this.prev = 0
set this.next = 0
set this.list = 0
set list.prev = 0
set list.next = 0
set thistype(-list).list = 0
debug set allocated[this] = 0
debug set allocated[list] = 0
endmethod
method operator size takes nothing returns integer
local thistype head = this.list
local thistype node = head.next
local integer count = 0
loop
exitwhen node == head
set count = count + 1
set node = node.next
endloop
return count
endmethod
method operator isEmpty takes nothing returns boolean
debug call ThrowError(allocated[this] == 0, "TreeList", "isEmpty", "thistype", this, "Attempted to use an unallocated instance")
return this.first == this.list
endmethod
method insert takes thistype node returns thistype
local thistype next = this.next
debug call ThrowError(allocated[this] == 0, "TreeList", "insert()", "thistype", this, "Attempted to insert node to an unallocated list")
debug call ThrowError(allocated[node] == 0, "TreeList", "insert()", "thistype", node, "Attempted to insert an unallocated node")
set next.prev = node
set this.next = node
set node.prev = this
set node.next = next
return this
endmethod
method push takes thistype node returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "push()", "thistype", this, "Attempted to push node to an unallocated list")
debug call ThrowError(allocated[node] == 0, "TreeList", "push()", "thistype", node, "Attempted to push an unallocated node")
call this.list.insert(node)
return this
endmethod
method enqueue takes thistype node returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "enqueue()", "thistype", this, "Attempted to enqueue node to an unallocated list")
debug call ThrowError(allocated[node] == 0, "TreeList", "enqueue()", "thistype", node, "Attempted to enqueue an unallocated node")
call this.last.insert(node)
return this
endmethod
method remove takes nothing returns thistype
local thistype prev = this.prev
local thistype next = this.next
debug call ThrowError(allocated[this] == 0, "TreeList", "remove()", "thistype", this, "Attempted to remove an unallocated node")
set next.prev = prev
set prev.next = next
return this
endmethod
method pop takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "pop()", "thistype", this, "Attempted to pop an unallocated node")
call this.first.remove()
return this
endmethod
method dequeue takes nothing returns thistype
debug call ThrowError(allocated[this] == 0, "TreeList", "dequeue()", "thistype", this, "Attempted to dequeue an unallocated node")
call this.last.remove()
return this
endmethod
method clear takes nothing returns thistype
local thistype head = this.list
debug call ThrowError(allocated[this] == 0, "TreeList", "clear()", "thistype", this, "Attempted to clear an unallocated node")
set head.prev = 0
set head.next = 0
return this
endmethod
method flush takes boolean destroyNodes returns thistype
local thistype head = this.list
local thistype node = head.next
debug call ThrowError(allocated[this] == 0, "TreeList", "flush()", "thistype", this, "Attempted to flush an unallocated node")
if destroyNodes then
loop
exitwhen node == head
call node.flush(true)
call node.remove()
call node.destroy()
set node = node.next
endloop
else
loop
exitwhen node == head
call node.flush(false)
call node.remove()
set node = node.next
endloop
endif
return this
endmethod
method collapseBranch takes nothing returns thistype
local thistype head = this.list
local thistype next = this.next
local thistype first = head.next
local thistype last = head.prev
debug call ThrowError(allocated[this] == 0, "TreeList", "collapseBranch()", "thistype", this, "Attempted to use an unallocated node")
set first.prev = this
set last.next = next
set next.prev = last
set this.next = first
set head.prev = head
set head.next = head
return this
endmethod
method collapse takes nothing returns thistype
local thistype head = this.list
local thistype node = head.next
debug call ThrowError(allocated[this] == 0, "TreeList", "collapse()", "thistype", this, "Attempted to use an unallocated node")
loop
exitwhen node == head
if not node.isEmpty then
call node.collapseBranch()
endif
set node = node.next
endloop
call this.collapseBranch()
return this
endmethod
method mergeChildren takes nothing returns thistype
local thistype head = this.list
local thistype node = head.next
local thistype last = head
local thistype first
debug call ThrowError(allocated[this] == 0, "TreeList", "mergeChildren()", "thistype", this, "Attempted to use an unallocated node")
loop
exitwhen node == head
if node.isEmpty then
set node = node.next
else
set first = node.first
set last.next = first
set first.prev = last
set last = node.last
set node = node.next
call node.prev.destroy()
endif
endloop
set last.next = head
set head.prev = last
return this
endmethod
method mergeDescendants takes nothing returns thistype
local thistype head = this.list
local thistype node = head.prev
local thistype collapsed
debug call ThrowError(allocated[this] == 0, "TreeList", "mergeDescendants()", "thistype", this, "Attempted to use an unallocated node")
loop
exitwhen node == head
if node.isEmpty then
set node = node.prev
else
call node.mergeDescendants()
call node.collapseBranch()
set collapsed = node
set node = node.prev
call collapsed.remove()
call collapsed.destroy()
endif
endloop
return this
endmethod
method rotate takes boolean clockwise returns thistype
local thistype node
debug call ThrowError(allocated[this] == 0, "TreeList", "rotate()", "thistype", this, "Attempted to use an unallocated node")
if clockwise then
set node = this.last
call node.remove()
return this.push(node)
else
set node = this.first
call node.remove()
return this.enqueue(node)
endif
endmethod
private static Table prevHeadNode
private static Table prevNodeCache
private static TreeList headNode = 0
private static TreeList nodeCache = 0
private static method init takes nothing returns nothing
set prevT = Table.create()
set nextT = Table.create()
set listT = Table.create()
set prevHeadNode = Table.create()
set prevNodeCache = Table.create()
debug set allocated = Table.create()
endmethod
implement Init
endstruct
private module Init
private static method onInit takes nothing returns nothing
call init()
endmethod
endmodule
module TreeListTransversal
method transverse takes nothing returns TreeList
local TreeList head
local TreeList node = this
debug call ThrowError(s__TreeList_allocated[this] == 0, "TreeList", "transverse()", "thistype", this, "Attempted to transverse an unallocated node")
static if thistype.onTransverse.exists then
set head = s__TreeList_listT[this]
set this = head.next
loop
exitwhen this == head
if not onTransverse() then
return -1
endif
if this.transverse() == -1 then
return node
endif
set this = TreeList(this).next
endloop
endif
return node
endmethod
endmodule
//! textmacro TREE_LIST_ITERATOR_START takes CLOCKWISE
set s__TreeList_prevHeadNode[this] = s__TreeList_headNode
set s__TreeList_prevNodeCache[this] = s__TreeList_nodeCache
set s__TreeList_headNode = s__TreeList_listT[this]
set s__TreeList_nodeCache = s__TreeList_headNode
set this = s__TreeList_nodeCache
loop
static if $CLOCKWISE$ then
set s__TreeList_nodeCache = s__TreeList_nodeCache.next
else
set s__TreeList_nodeCache = s__TreeList_nodeCache.prev
endif
set this = s__TreeList_nodeCache
exitwhen this == s__TreeList_headNode
//! endtextmacro
//! textmacro TREE_LIST_ITERATOR_END
endloop
set this = s__TreeList_listT[-this]
set s__TreeList_headNode = s__TreeList_prevHeadNode[this]
set s__TreeList_nodeCache = s__TreeList_prevNodeCache[this]
set s__TreeList_prevHeadNode[this] = 0
set s__TreeList_prevNodeCache[this] = 0
//! endtextmacro
endlibraryNested iteration sample:
JASS:
struct Test extends array
private static method onInit takes nothing returns nothing
/*
| Root Node | | 2nd Level | | 3rd Level | | 4th Level |
*/
local TreeList this = TreeList.create().enqueue(/*
*/TreeList.create().enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/.enqueue(/*
*/TreeList.create().enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/.enqueue(TreeList.create())/*
*/)/*
*/)
call TriggerSleepAction(0.10)
//! runtextmacro TREE_LIST_ITERATOR_START("true")
//iterates over the nodes in the 2nd level starting from the first to the last node ("true" -> clockwise)
call BJDebugMsg(I2S(this))
//! runtextmacro TREE_LIST_ITERATOR_START("false")
//iterates over the nodes in the 3rd level starting from the last to the first node ("false" -> counter-clockwise)
call BJDebugMsg(I2S(this))
//! runtextmacro TREE_LIST_ITERATOR_START("true")
//iterates over the nodes in the 4rd level starting from the first to the last node ("true" -> clockwise)
call BJDebugMsg(I2S(this))
//you can iterate up to the nth level by nesting these macros
//! runtextmacro TREE_LIST_ITERATOR_END()
//! runtextmacro TREE_LIST_ITERATOR_END()
//! runtextmacro TREE_LIST_ITERATOR_END()
call BJDebugMsg(I2S(this)) // the value of "this" is restored to its original value after the iteration
endmethod
endstruct
Last edited:
