- Joined
- Nov 7, 2014
- Messages
- 571
Listy.j:
demo:
JASS:
library Listy
//! novjass
Listy - your friendly neighborhood linked list library
So you have a struct:
struct Foo
<members>
endstruct
and you want a list of Foo(s)... well, I am afraid you have to change the definition of Foo a little bit:
struct Foo
implement List_Node // <-- we added this line
<members>
endstruct
We only added the line:
implement List_Node
what this does is: it turned our Foo struct into a "list node" that can be added/removed to/from a list
by giving it a few fields and methods (Yes, methods! It polluted your struct with methods!)
Now we have a Foo "list node", but we wanted a list of Foo(s), where is it!?
Well, we have to declare it first:
struct Foo_List
//! runtextmacro LIST_OF("Foo")
endstruct
I am sorry Dave, I am afraid I can''t do this without textmacros.
So Foo_List is a LIST_OF("Foo")... I don''t get it...
Now that we have declared our Foo_List, what can we do with it?
First of all we have to create one:
Foo_List list = Foo_List.create()
Okay, now that we finally have a list of Foo(s), lets make some Foo(s)
Foo foo1 = Foo.create()
Foo foo2 = Foo.create()
Foo foo3 = Foo.create()
and add them:
by using the add_head method
call list.add_head(foo1)
call list.add_head(foo2)
call list.add_head(foo3)
or by using the add_tail method
call list.add_tail(foo1)
call list.add_tail(foo2)
call list.add_tail(foo3)
what''s the difference?
*Sigh* (not valid syntax)
add_head(1)
add_head(2)
add_head(3)
=> 3, 2, 1
add_tail(1)
add_tail(2)
add_tail(3)
=> 1, 2, 3
There''s of course a corresponding remove* method for them:
Foo old_head = list.remove_head()
Foo old_tail = list.remove_tail()
Okay, okay whatever... how do I iterate it forward/backward?
Foo node
// forward
//
set node = list.head
loop
exitwhen node == list.sentinel
// use node
set node = node.next
endloop
// backward
//
set node = list.tail
loop
exitwhen node == list.sentinel
// use node
set node = node.prev
endloop
Wt*... a sentinel? Too much dota... now where''s my null!
There is no null, only sentinel!
Fine, chill out...
I also want to get rid of a node while iterating!
set node = list.head
loop
exitwhen node == list.sentinel
if <cond> then
call node.detach()
endif
set node = node.next
endloop
Ooopsy....
set node = list.head
loop
exitwhen node == list.sentinel
if <cond> then
call node.detach()
call node.destroy() // <-- we added this line, otherwise we leak Foo(s)
endif
set node = node.next
endloop
Well that''s the definition of error-prone right there...
No operation that Listy provides (remove_head, remove_tail, detach) destroys your struct instances!
except one...
call list.destroy()
which destroys all the Foo(s) in the list, then the sentinel and finally the list itself, so all should be leak free (hopefully)...
Great! Only code now:
struct Foo
<members>
endstruct
=>
struct Foo
implement List_Node
<members>
endstruct
struct Foo_List
//! runtextmacro LIST_OF("Foo")
endstruct
Foo_List list = Foo_List.create()
call list.add_head(Foo.create())
call list.add_tail(Foo.create())
call list.remove_head(Foo.create())
call list.remove_tail(Foo.create())
Foo node
// iterate forward
set node = list.head
loop
exitwhen node == list.sentinel
// use node
set node = node.next
endloop
// iterate backward
set node = list.tail
loop
exitwhen node == list.sentinel
// use node
set node = node.prev
endloop
// iterate forward and conditionally remove
set node = list.tail
loop
exitwhen node == list.sentinel
if <cond> then
call node.detach()
call node.destroy()
endif
set node = node.prev
endloop
call list.destroy()
Design decisions:
The linked list is doubly linked list so that only having a node is enough to remove it from it''s owning list.
We use a sentinel so the operations don''t have special cases and null checks, i.e it''s faster.
The cost of that is of course the method pollution by implementing List_Node, which exposes the
the allocate and the deallocate methods (which are private) of the struct so that we can
create/destroy the sentinel itself.
The list doesn''t know how many nodes it has (i.e a length/count member), because it seems that in the
use cases for lists that''s not needed, and would result in more "pollution" and overhead.
We use textmacros to achieve some limited form of type safety, i.e foos.add_tail(bar) would fail, but of course
the user can circumvent that with foos.add_tail(Foo(bar)), i.e by casting bar to Foo.
//! endnovjass
module List_Node
public thistype prev
public thistype next
public method detach takes nothing returns nothing
set this.prev.next = this.next
set this.next.prev = this.prev
endmethod
public static method public_allocate takes nothing returns thistype
return thistype.allocate()
endmethod
public method public_deallocate takes nothing returns nothing
call this.deallocate()
endmethod
endmodule
//! textmacro LIST_OF takes T
readonly $T$ sentinel
method operator head takes nothing returns $T$
return this.sentinel.next
endmethod
method operator head= takes $T$ node returns nothing
set this.sentinel.next = node
endmethod
method operator tail takes nothing returns $T$
return this.sentinel.prev
endmethod
method operator tail= takes $T$ node returns nothing
set this.sentinel.prev = node
endmethod
static method create takes nothing returns thistype
local thistype this = thistype.allocate()
set this.sentinel = $T$.public_allocate()
set this.sentinel.prev = this.sentinel
set this.sentinel.next = this.sentinel
return this
endmethod
method add_head takes $T$ node returns thistype
set node.prev = this.sentinel
set node.next = this.head
set this.head.prev = node
set this.head = node
return node
endmethod
method remove_head takes nothing returns $T$
local $T$ node = this.head
set this.head = this.head.next
return node
endmethod
method add_tail takes $T$ node returns thistype
set node.prev = this.tail
set node.next = this.sentinel
set this.tail.next = node
set this.tail = node
return node
endmethod
method remove_tail takes nothing returns $T$
local $T$ node = this.tail
set this.tail = this.tail.prev
return node
endmethod
method is_empty takes nothing returns boolean
return this.sentinel == this.sentinel.next
endmethod
method destroy takes nothing returns nothing
local $T$ node
set node = this.head
loop
exitwhen node == this.sentinel
call node.destroy()
set node = node.next
endloop
call this.sentinel.public_deallocate()
call this.deallocate()
endmethod
//! endtextmacro
endlibrarydemo:
JASS:
library demo initializer init requires Listy
struct Foo
implement List_Node
integer a
real b
string c
static method create takes integer a, real b, string c returns thistype
local thistype this = thistype.allocate()
set this.a = a
set this.b = b
set this.c = c
return this
endmethod
method to_str takes nothing returns string
return "[Foo(" + I2S(this) + "): a: " + I2S(this.a) + ", b: " + R2S(this.b) + ", c: " + this.c + ")]"
endmethod
endstruct
struct Foo_List
//! runtextmacro LIST_OF("Foo")
endstruct
struct Bar
Foo_List foos
static method create takes nothing returns thistype
local thistype this = thistype.allocate()
set this.foos = Foo_List.create()
return this
endmethod
method destory takes nothing returns nothing
call this.foos.destroy()
call this.deallocate()
endmethod
endstruct
function lazy_init takes nothing returns nothing
local Bar bar = Bar.create()
local Foo_List foos = bar.foos
local Foo foo
call foos.add_tail(Foo.create(1, 2.0, "3"))
call foos.add_tail(Foo.create(4, 5.0, "6"))
call foos.add_tail(Foo.create(7, 8.0, "9"))
set foo = foos.head
loop
exitwhen foo == foos.sentinel
if foo.a == 4 then
call BJDebugMsg("detaching: " + foo.to_str())
call foo.detach()
call foo.destroy()
else
call BJDebugMsg(foo.to_str())
endif
set foo = foo.next
endloop
call bar.destroy()
endfunction
function init takes nothing returns nothing
// so that we can see the Log (F12), because 60 seconds (BJDebugMsg) are never enough =)
call TimerStart(CreateTimer(), 0, false, function lazy_init)
endfunction
endlibrary
