- Joined
- Sep 26, 2009
- Messages
- 9,521
LinkedList allows you to store data for the purpose of iterating over it. I hope the iteration methods are as quick as possible.
This supports iterating forwards, backwards, inserting at any arbitrary position in the list, removing from any position in the list, copying the list or converting a unit group into a list (if the UnitIndexer library is found).
An extension to Table, this also has nearly-unlimited instances, so you won't find yourself running short.
Run it in debug mode.
This supports iterating forwards, backwards, inserting at any arbitrary position in the list, removing from any position in the list, copying the list or converting a unit group into a list (if the UnitIndexer library is found).
An extension to Table, this also has nearly-unlimited instances, so you won't find yourself running short.
JASS:
library LinkedListStruct
/*
About
LinkedList is a high-level data structure useful for creating dynamic
lists that can be iterated over, added or removed from at any point,
with all operations being O(1) in complexity.
This was inspired by "List" by MaskedPoptart which was not exactly a
list but a linear stack with mostly O(N) operations in the important
areas to keep things in numerical sequence.
Disclaimer
This is meant to store either positive or negative integers, but not
both in the same list. The value "0" is treated as null & should not
be treated as an actual value to be stored. You shouldn't be using 0
for dynamic data as it is (for structs and unit indexers 0 is a null
index), so this shouldn't be bad news.
You also cannot store the same value twice. Being a linked list, the
value itself is used as a pointer to its next & previous values - it
cannot be multiply-defined because that wouldn't make sense. If you
want to change a node's position in the list you should first remove
it and then re-insert it somewhere.
API
struct LinkedList extends array
static method create takes nothing returns LinkedList
->
Create a new list. You can create a virtually-unlimited number of
LinkedLists, so you never have to worry about consuming too much
RAM, handle count or leakage from dynamic unit groups.
method destroy takes nothing returns nothing
->
Destroy the list if you are done with it.
method flush takes nothing returns nothing
->
Empty the list of all its contents. This is a really fast method
compared to emptying the list node by node.
method operator first takes nothing returns integer
->
Get the node at the beginning of the list.
method operator last takes nothing returns integer
->
Get the node at the end of the list.
method next takes integer node returns integer
->
Get the node's next node in the list.
method prev takes integer node returns integer
->
Get the node's previous node in the list.
method operator [] takes integer node returns integer
->
Get a node arbitrarily. Useful for less verbosity.
method operator flushed takes nothing returns boolean
->
Is the list completely empty?
method contains takes integer node returns boolean
->
Is the node listed?
method append takes integer node returns nothing
->
Add a node to the end of the list. This is the fastest way to add
to the list and you don't really need the other insertion methods
unless you are doing some really complex mapping.
method prepend takes integer node returns nothing
->
Add a node to the beginning of the list.
method insertAfter takes integer from, integer node returns nothing
->
Insert a node after another's position.
method insertBefore takes integer from, integer node returns nothing
->
Insert a node before another's position.
method remove takes integer node returns nothing
->
Removes the node from the list. This method completely erases its
position from the list, so if you are iterating through the list,
you must store the next/prev node before calling this method, or
use one of the following two methods.
method popNext takes integer node returns integer
->
Removes the node and returns the next node from its position in
the list. Use this if you want to remove a node while looping
forward.
method popPrev takes integer node returns integer
->
Removes the node and returns the previous node from its position
in the list. Use this if you want to remove a node while looping
backwards.
method copy takes nothing returns LinkedList
->
Returns an exact copy of the list in the form of a new list.
debug method print takes nothing returns nothing
->
Available only in debug mode, this prints out the list in a read-
able format.
optional method addGroup takes group g returns nothing
->
Available only if UnitIndexer is in the map, this clears a unit
group and adds its contents to the LinkedList.
*/
struct LinkedList extends array
private static hashtable h = InitHashtable()
private static thistype rec = 0
private static integer index = 0
method operator [] takes integer node returns integer
return LoadInteger(.h, this, node)
endmethod
private method operator []= takes integer node, integer value returns nothing
call SaveInteger(.h, this, node, value)
endmethod
private method del takes integer node returns nothing
call RemoveSavedInteger(.h, this, node)
endmethod
private static method operator main takes nothing returns thistype
return 0
endmethod
static method create takes nothing returns thistype
local thistype this = .rec
if this == 0 then
set this = .index + 1
set .index = this
else
set .rec = .main[-this]
call .main.del(-this)
endif
set .main[-this] = -1
return this
endmethod
method flush takes nothing returns nothing
call .main.del(this)
call FlushChildHashtable(.h, this)
endmethod
method destroy takes nothing returns nothing
if .main[-this] != -1 then
debug call BJDebugMsg("Table Error: Tried to double-free instance: " + I2S(this))
return
endif
call this.flush()
set .main[-this] = rec
set rec = this
endmethod
method operator first takes nothing returns integer
return this[0]
endmethod
method operator last takes nothing returns integer
return .main[this]
endmethod
method next takes integer node returns integer
return this[node]
endmethod
method prev takes integer node returns integer
if node == 0 then
return this.last
endif
return this[-node]
endmethod
method operator flushed takes nothing returns boolean
return 0 == this[0]
endmethod
method contains takes integer node returns boolean
return 0 != this[node] or node == .main[this]
endmethod
method append takes integer node returns nothing
local integer bot = .main[this]
if this.contains(node) then
debug call BJDebugMsg("LinkedList Error: Attempt to append an already-inserted node: " + I2S(node))
return
endif
set this[-node] = bot
set this[bot] = node
set .main[this] = node
endmethod
method prepend takes integer node returns nothing
local integer top = this[0]
if this.contains(node) then
debug call BJDebugMsg("LinkedList Error: Attempt to prepend an already-inserted node: " + I2S(node))
return
endif
if 0 == top then
set .main[this] = node
else
set this[-top] = node
set this[node] = top
endif
set this[0] = node
endmethod
method insertAfter takes integer from, integer node returns nothing
local integer nn = this[from]
if 0 == from then
call this.prepend(node)
elseif 0 == nn then
if from == .main[this] then
call this.append(node)
debug else
debug call BJDebugMsg("LinkedList Error: Attempt to insert after unlisted node: " + I2S(from))
endif
else
if this.contains(node) then
debug call BJDebugMsg("LinkedList Error: Attempt to insert an already-inserted node: " + I2S(node))
return
endif
set this[-nn] = node
set this[node] = nn
set this[-node] = from
set this[from] = node
endif
endmethod
method insertBefore takes integer from, integer node returns nothing
if 0 == from then
call this.append(node)
else
call this.insertAfter(this[-from], node)
endif
endmethod
method remove takes integer node returns nothing
local integer nn = this[node]
local integer pn = this[-node]
if this.contains(node) then
if 0 == nn then
if 0 == pn then
call this.flush()
return
endif
set .main[this] = pn
call this.del(pn)
elseif 0 == pn then
set this[0] = nn
call this.del(-nn)
else
set this[pn] = nn
set this[-nn] = pn
endif
call this.del(node)
call this.del(-node)
debug else
debug call BJDebugMsg("LinkedList Error: Attempt to remove a non-existing node: " + I2S(node))
endif
endmethod
method popNext takes integer node returns integer
local integer pop = this[node]
call this.remove(node)
return pop
endmethod
method popPrev takes integer node returns integer
local integer pop = this[-node]
call this.remove(node)
return pop
endmethod
method copy takes nothing returns thistype
local thistype new = .create()
local integer i = this.first
loop
exitwhen 0 == i
call new.append(i)
set i = this[i]
endloop
return new
endmethod
static if DEBUG_MODE then
method print takes nothing returns nothing
local string s = "LinkedList: |cffffcc33"
local integer i = this.first
loop
exitwhen 0 == i
set s = s + "[" + I2S(i) + "]"
set i = this[i]
endloop
call BJDebugMsg(s + "|r")
endmethod
endif
endstruct
endlibraryRun it in debug mode.
JASS:
function InitTrig_List takes nothing returns nothing
local LinkedList l = LinkedList.create()
call l.append(2)
call l.append(3)
call l.append(6)
call l.prepend(1)
call l.insertAfter(3, 4)
call l.insertBefore(6, 5)
debug call l.print()
call l.remove(2)
call l.remove(4)
call l.remove(6)
debug call l.print()
call l.insertAfter(1, 2)
call l.insertAfter(3, 4)
call l.insertAfter(5, 6)
call l.remove(1)
call l.remove(3)
call l.remove(5)
debug call l.print()
endfunction
Last edited:
