- Joined
- Mar 19, 2008
- Messages
- 3,141
Implementation of generic double-linked list. Usefull especially when map is packed with spells, each implementing it's own list structure. Template functionality is provided via Table thus it's slower than array-based list implementation, yet as stated, it allows you to create one list type for entire map effectively preventing globals declaration spam. Adds STRUCT-type support for intuitive syntax.
Most of the functions are inline-friendly, thus the actual code size is greatly reduced, even though scrypt by itself isn't big either.
JASS:
/*****************************************************************************
*
* List<T> v2.1.2.3
* by Bannar
*
* Doubly-linked list.
*
******************************************************************************
*
* Requirements:
*
* Table by Bribe
* hiveworkshop.com/threads/snippet-new-table.188084/
*
* Alloc - choose whatever you like
* e.g.: by Sevion hiveworkshop.com/threads/snippet-alloc.192348/
*
******************************************************************************
*
* Implementation:
*
* macro DEFINE_LIST takes ACCESS, NAME, TYPE
*
* macro DEFINE_STRUCT_LIST takes ACCESS, NAME, TYPE
*
* ACCESS - encapsulation, choose restriction access
* NAME - name of list type
* TYPE - type of values stored
*
* Implementation notes:
*
* - DEFINE_STRUCT_LIST macro purpose is to provide natural typecasting syntax for struct types.
* - <NAME>Item structs inline directly into hashtable operations thus generate basically no code.
* - Lists defined with DEFINE_STRUCT_LIST are inlined nicely into single create method and single integer array.
*
******************************************************************************
*
* struct API:
*
* struct <NAME>Item:
*
* | <TYPE> data
* | <NAME>Item next
* | <NAME>Item prev
*
*
* General:
*
* | static method create takes nothing returns thistype
* | Default ctor.
* |
* | static method operator [] takes thistype other returns thistype
* | Copy ctor.
* |
* | method destroy takes nothing returns nothing
* | Default dctor.
* |
* | method empty takes nothing returns boolean
* | Checks whether the list is empty.
* |
* | method size takes nothing returns integer
* | Returns size of a list.
*
*
* Access:
*
* | readonly <NAME>Item first
* | readonly <NAME>Item last
* |
* | method front takes nothing returns $TYPE$
* | Retrieves first element.
* |
* | method back takes nothing returns $TYPE$
* | Retrieves last element.
*
*
* Modifiers:
*
* | method clear takes nothing returns nothing
* | Flushes list and recycles its nodes.
* |
* | method push takes $TYPE$ value returns thistype
* | Adds elements to the end.
* |
* | method unshift takes $TYPE$ value returns thistype
* | Adds elements to the front.
* |
* | method pop takes nothing returns thistype
* | Removes the last element.
* |
* | method shift takes nothing returns thistype
* | Removes the first element.
* |
* | method find takes $TYPE$ value returns $NAME$Item
* | Returns the first node which data equals value.
* |
* | method erase takes $NAME$Item node returns boolean
* | Removes node from the list, returns true on success.
* |
* | method removeElem takes $TYPE$ value returns thistype
* | Removes first element that equals value from the list.
*
*
*****************************************************************************/
library ListT requires Table, Alloc
//! runtextmacro DEFINE_LIST("", "IntegerList", "integer")
// Run here any global list types you want to be defined.
//! textmacro_once DEFINE_LIST takes ACCESS, NAME, TYPE
$ACCESS$ struct $NAME$Item extends array
// No default ctor and dctor due to limited array size
method operator data takes nothing returns $TYPE$
return Table(this).$TYPE$[-1] // hashtable[ node, -1 ] = data
endmethod
method operator data= takes $TYPE$ value returns nothing
set Table(this).$TYPE$[-1] = value
endmethod
method operator next takes nothing returns thistype
return Table(this)[-2] // hashtable[ node, -2 ] = next
endmethod
method operator next= takes thistype value returns nothing
set Table(this)[-2] = value
endmethod
method operator prev takes nothing returns thistype
return Table(this)[-3] // hashtable[ node, -3 ] = prev
endmethod
method operator prev= takes thistype value returns nothing
set Table(this)[-3] = value
endmethod
endstruct
$ACCESS$ struct $NAME$ extends array
readonly $NAME$Item first
readonly $NAME$Item last
private integer count
implement Alloc
private static method setNodeOwner takes $NAME$Item node, $NAME$ owner returns nothing
set Table(node)[-4] = owner
endmethod
private static method getNodeOwner takes $NAME$Item node returns thistype
return Table(node)[-4]
endmethod
private method createNode takes $TYPE$ value returns $NAME$Item
local $NAME$Item node = Table.create()
set node.data = value
call setNodeOwner(node, this) // ownership
return node
endmethod
private method deleteNode takes $NAME$Item node returns nothing
call Table(node).destroy() // also removes ownership
endmethod
static method create takes nothing returns thistype
local thistype this = allocate()
set count = 0
return this
endmethod
method clear takes nothing returns nothing
local $NAME$Item node = first
local $NAME$Item temp
loop // recycle all Table indexes
exitwhen 0 == node
set temp = node.next
call deleteNode(node)
set node = temp
endloop
set first = 0
set last = 0
set count = 0
endmethod
method destroy takes nothing returns nothing
call clear()
call deallocate()
endmethod
method front takes nothing returns $TYPE$
return first.data
endmethod
method back takes nothing returns $TYPE$
return last.data
endmethod
method empty takes nothing returns boolean
return count == 0
endmethod
method size takes nothing returns integer
return count
endmethod
method push takes $TYPE$ value returns thistype
local $NAME$Item node = createNode(value)
if not empty() then
set last.next = node
set node.prev = last
else
set first = node
set node.prev = 0
endif
set last = node
set node.next = 0
set count = count + 1
return this
endmethod
method unshift takes $TYPE$ value returns thistype
local $NAME$Item node = createNode(value)
if not empty() then
set first.prev = node
set node.next = first
else
set last = node
set node.next = 0
endif
set first = node
set node.prev = 0
set count = count + 1
return this
endmethod
method pop takes nothing returns thistype
local $NAME$Item node
if not empty() then
set node = last
set last = last.prev
if last == 0 then
set first = 0
else
set last.next = 0
endif
call deleteNode(node)
set count = count - 1
debug else
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::pop failed for instance "+I2S(this)+". List is empty.")
endif
return this
endmethod
method shift takes nothing returns thistype
local $NAME$Item node
if not empty() then
set node = first
set first = first.next
if first == 0 then
set last = 0
else
set first.prev = 0
endif
call deleteNode(node)
set count = count - 1
debug else
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::shift failed for instance "+I2S(this)+". List is empty.")
endif
return this
endmethod
static method operator [] takes thistype other returns thistype
local thistype instance = create()
local $NAME$Item node = other.first
loop
exitwhen node == 0
call instance.push(node.data)
set node = node.next
endloop
return instance
endmethod
method find takes $TYPE$ value returns $NAME$Item
local $NAME$Item node = first
loop
exitwhen node == 0 or node.data == value
set node = node.next
endloop
return node
endmethod
method erase takes $NAME$Item node returns boolean
if getNodeOwner(node) == this then // match ownership
if node == first then
call shift()
elseif node == last then
call pop()
else
set node.prev.next = node.next
set node.next.prev = node.prev
call deleteNode(node)
set count = count - 1
endif
return true
debug else
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"$NAME$::erase failed for instance "+I2S(this)+". Attempted to remove invalid node "+I2S(node)+".")
endif
return false
endmethod
method remove takes $NAME$Item node returns boolean
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Method $NAME$::remove is obsolete, use $NAME$::erase instead.")
return erase(node)
endmethod
method removeElem takes $TYPE$ value returns thistype
local $NAME$Item node = find(value)
if node != 0 then
call erase(node)
endif
return this
endmethod
endstruct
//! endtextmacro
//! textmacro_once DEFINE_STRUCT_LIST takes ACCESS, NAME, TYPE
$ACCESS$ struct $NAME$Item extends array
// Cannot inherit methods via delegate due to limited array size
method operator data takes nothing returns $TYPE$
return IntegerListItem(this).data
endmethod
method operator data= takes $TYPE$ value returns nothing
set IntegerListItem(this).data = value
endmethod
method operator next takes nothing returns thistype
return IntegerListItem(this).next
endmethod
method operator next= takes thistype value returns nothing
set IntegerListItem(this).next = value
endmethod
method operator prev takes nothing returns thistype
return IntegerListItem(this).prev
endmethod
method operator prev= takes thistype value returns nothing
set IntegerListItem(this).prev = value
endmethod
endstruct
$ACCESS$ struct $NAME$ extends array
private delegate IntegerList parent
static method create takes nothing returns thistype
local thistype this = IntegerList.create()
set parent = this
return this
endmethod
method front takes nothing returns $TYPE$
return parent.front()
endmethod
method back takes nothing returns $TYPE$
return parent.back()
endmethod
endstruct
//! endtextmacro
endlibrary
JASS:
//! runtextmacro DEFINE_STRUCT_LIST("", "ListOfLists", "IntegerList")
struct test_list extends array
static method print takes IntegerList list, string prefix returns nothing
local IntegerListItem node = list.first
local string s = ""
loop
exitwhen node == 0
set s = s + " " + I2S(node.data)
set node = node.next
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, prefix + s)
endmethod
static method test_list takes nothing returns nothing
local IntegerList list = IntegerList.create()
local IntegerList list2 = IntegerList.create()
local IntegerList list3 = IntegerList.create()
local ListOfLists lol = ListOfLists.create()
call list.push(55).push(3).push(88).push(0).push(-10).push(1).push(17).push(-1).push(26)
call list2.push(4).push(55).push(0).push(13).push(7)
call list3.push(1).push(2).push(2).push(3).push(3).push(2).push(1).push(1).push(2)
call lol.push(list).push(list2).push(list3)
call print(list, "List1: ")
call print(list2, "List2: ")
call print(list3, "List3: ")
call list.shift().pop()
call list2.erase(list2.find(0))
call print(list, "\nList1: ")
call print(list2, "List2: ")
call print(list3, "List3: ")
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "ListOfLists front has size of " + I2S(lol.front().size()))
endmethod
static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(), 2, false, function thistype.test_list)
endmethod
endstruct
Last edited:
.
