- Joined
- Nov 30, 2007
- Messages
- 1,202
This library was inspired by and partially based on Bannarers ListT. It consits of a main library LinkedList and a bunch of optional modules that can be included to extend the features that exists.
First node
Last node
Number of nodes
Inserts a value at the specified index. Returns true if succesful.
Inserts a node at the specified index. Returns true on success. Having nodes coexist in multiple lists should be avoided.
Adds a node after a node, both nodes should exist in the same list. This is slightly faster than other add operations.
Adds a node before a node, both nodes should exist in the same list. This is slightly faster than other add operations.
Removes all nodes from the list, deallocating the node references. If you wish to clear it without removing the nodes you will have to do so manually by nulling the head reference before calling this method.
Searches for the value inside the list, returns true if it exists.
Destroys the list clearing it in the process.
Removes a node from the list without destroying it. Returns the removed node.
Searches the list for a node with the given value in ascending order, returns the node if found, otherwise 0.
Retrieves the node at a given index, if outside bounds it returns 0.
Returns the index of a given value, searching in either ascending (true) or descending (false) order.
Returns true if the list is empty.
Removes a value at the specified index, returning the value and deallocating the node in the process.
Removes the node from the list and returning the value and deallocating it in the process. Do not remove a node that doesn't belong
to the list you are manipulating.
The number of values the list contains.
Swap the values at the given positions if inside bounds.
This is a wrapper for get.
Creates a linked list.
Splits the list in two at a given position. The right part of the split is returned and the left side is kept in the calling list.
Moves all the current nodes from the source list to the calling list.
The iterator that has triggered the callback function.
Set to true if you want periodic iterations to start over when they reach the end.
The current enumerated node that this iterator is on.
The current list position that the iterator is on.
Destroys the iterator.
Iterates through each node of the list, executing the callback function each time.
To get the last node or index simply use <NAME>Iterator.last.enum and <NAME>Iterator.last.index.
Starts a delayed iteration that either repeats when finished or halts. The cursor moves one step per time cycle executing the callback function each time.
Pauses the periodic iteration.
Resumes the periodic iteration.
Creates an iterator based on the provided list.
Returns a created iterator based on the calling list.
Adds a value to it's proper sorted position. With the precondition that the list was sorted before.
Merge sorts the list, capable of sorting up to 4000 integers without reaching OP limit. Note that this limit is lower for other data types.
Copies all elements from the source list to the calling list, starting at a given position.
Copies all elements from the source table to the calling list, starting at a given position. The elements must be formated as an ArrayList, if any null values are detected the copying will finish.
Copies a list from the specified source table position to the specified destination list position. The number of copied elements is equal to the provided range. The table must be organized as an ArrayList.
Copies a list from the specified source list position to the specified destination list position. The number of copied elements is equal to the provided range. The table must be organized as an ArrayList.
Moves the specified node one position to the left.
Moves the specified node one position to the right.
Reverses the list order so the last element becomes the first and the first element becomes the last.
Shifts all elements to the left based on the provided number of positions.
Shifts all elements to the right based on the provided number of positions.
Used to swap nodes inside the list with each other. As opposed to swap(indexA, indexB) this is a hard swap, it swaps the actual nodes and not just the data. Note that swapping nodes that belong to different lists can lead to undesired behaviour. It is however faster as no lookup time is needed.
Pushes a value to the top of the stack (first element).
Retrieves a value from the top of the stack and removes it.
Retrieves the value from the first position without removing it.
Adds a value to the back of the queue (last element)
Retrieves a value from the front of the queue (first element).
The idea here is to create a module that allows for manipulation of multiple nodes simultaneously. Currently though, it only contains copying of nodes from/to a table/list. I might add containsAll, containsAny and retainAll(list) etc. Though unless someone specifically asks for this, I'm unlikely to do t.
CAUTION:
Be careful with what you do when handling nodes outside of the list. Destroying a node inside a list will break the chain if it was not first removed or ejected. Using nodes that don't belong to a list as an argument is generally speaking an illegal argument and should never be done as it can cause all kinds of funny business. If you wish to transfer a node from one list to another use the eject method first.
Destroying a list will also destroy all nodes held there in, if you wish to keep all the nodes but destroy the list, you need to save the head reference somewhere and set the head to 0 before destroying the list.
1.0.0
- DoubleLinkedList for integers
1.0.1
- Fixed: bug with double remove in the iterator (should not be allowed)
- Fixed: bug with removeLast having a parameter
- Added: method copyRange takes integer start, integer end, boolean keepReferences returns thistype
if no node is provided it creates a new one based on the value
- Added: method copyRange takes integer start, integer end, boolean copyNodes returns thistype
~ Copying a list whilst remaining the same node references in both causes remove()
to not function properly (should be removed on both lists I reckon).
1.0.2
- Removed the posibility of copying a list whilst keeping the same references.
- Added: method sort takes nothing returns nothing (selection sort O^2)
- Added: method rotateLeft takes integer numOfPositions returns nothing
- Added: method rotateRight takes integer numOfPositions returns nothing
1.0.3
- Made iterator a member of List so that it gets recycled rather than having the user
or perhaps all instances created should be saved in a table so that when the list is destroyed
all the iterators (if not destroyed get destroyed)
- Removed addNode takes integer index, Node nodeToAdd, integer value returns boolean
- Fixed: Bug with rotateLeft and rotateRight
1.0.4
- Temporarily removed sort
- Temporarily removed Iterator
- Implemented generic types
1.0.5
- Readded: Iterator
- Readded: Basic sorting (still selection sort) the user can now specify sort condition using
a tetmacro.
- Moved: list.createNode(Value) to Node.create(value)
- Moved: list.destroyNode(Value) to Node.destroy()
1.2.0
- Fixed a bug with the getNode backwards iteration.
- Added: swapNode(Node, Node)
- Added: moveLeft(Node)
- Added: moveRight(Node)
- Added: addList(Index, List) (insert all nodes from a list)
- Added: addTable(Index, Table) (inserts all indexed elements of a table)
- Added: addAfter(node, nodeToAdd)
- Added: split(Index)
- Changed: sorting now uses merge sort and can sort up to 4000 elements before hitting OP limit.
- Fixed: RotateLeft and RotateRight have been modified and can now rotate in inverse direction.
- Fixed: Adding a node with previous references will also delink the previous references to the added
node.
- Changed: clear() to clear(boolean) to take a flag for if the nodes should get deallocated or not.
- Changed: removeNode(node) no longer also destroys the node. However, the wrappers remove(index), removeValue(value), removeFirst and removeLast still do.
- Removed Iterator
- Removed the use of Alloc
1.2.5
- Added: indexOfLast(value): backwards search for the index of a value.
- Added: transfer(index, srcs) takes all the nodes in one list and injects them to another, empties the source list of any nodes.
- Added: addBefore(node, nodeToAdd)
- Added: addSorted(value), adds a node to a sorted position, precondition the list is sorted.
- Added: ejectNode(node) removes the node from the list without destroying it and returns the reference.
- Added: reverse, changes the order so that the tail becomes the first node, and the head the last node.
- Added: IteratorModule containing new tentative and optional features.
- Added: iterator() creates a iterator based on the list.
- Added: iterator.forEach(callback)
- Added: iterator.forEachPeriodic(time, repeating, callback)
- Added: iterator pause()
- Added: iterator resume()
- Added: copyToList and copyToTable.
- Changed: Moved addList, addTable copyToList and copyToTable to List Collection Module.
- Changed: merge used when mergesorting was optimized to not use any methodcalls (except for node operators).
- Changed: addList now copies each node in the source rather than transferring them.
- Changed: MergeSort was made into an optional module and moved to a separate library that must be configured for each list that you wish to include it for.
- Changed removeNode(node) now also deallocates the node again.
- Fixed: addAfter(node) now works.
1.2.6
- Removed: ListWrapperModule and all the methods therein
- Removed: addFirst, addLast, getFirst, getLast, defineFirst, defineLast, get
- Changed: getNode --> get
- Changed: ejectNode --> eject
- Changed: findNode --> find
- Changed: indexOf/IndexOfLast --> indexOf(value, ascending)
- Changed: transfer and split was moved to ListUtilityModule.
- Fixed: Added a .has() check to the Collection Module when dealing with tables.
- Added: method operator [index] ( same as list.get(index) )
- Added: You can now toggle if the list or the nodes should be table based or array based when running the textmacro.
- Added: Stack Queue Module containing regular stack and queue interface: push, pop, peek, offer, poll.
- Added: Swap(indexA, indexB) to the main library.
- change the split method to not allocate any lists internally.
{ static method split(sourceList, index, leftList, rightList) }
- moveLeft and moveRight should take in numberOfPositions as argument
- Periodic iterations should have an argument for number of elements to callback on each cycle
- find should also take in a boolean for ascending or descening order.
- Fix minor errors in the documentation.
JASS:
library PArrayList uses Table
/*
Made by: Pinzu
This is a very basic list using Table for storage.
Requirements:
Table by Bribe
hiveworkshop.com/threads/snippet-new-table.188084/
*/
//! runtextmacro DEFINE_ARRAY_LIST("Int", "integer", "0", "true" )
//! runtextmacro DEFINE_ARRAY_LIST("Unit", "unit", "null", "true" )
//! textmacro_once DEFINE_ARRAY_LIST takes NAME, TYPE, NONE, TABLE_BASED
struct $NAME$ArrayList
static method create takes nothing returns thistype
local thistype this = Table.create()
set this.length = 0
return this
endmethod
implement optional $NAME$ArrayListSortModule
method destroy takes nothing returns nothing
call Table(this).destroy()
endmethod
method clear takes nothing returns nothing
call Table(this).flush()
set .length = 0
endmethod
private method operator length= takes integer index returns nothing
set Table(this).integer[-1] = index
endmethod
method operator length takes nothing returns integer
return Table(this).integer[-1]
endmethod
// Getter: list[index]
method operator [] takes integer index returns $TYPE$
if (index < 0 or index >= .length) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.get:IndexOutOfBounds")
return $NONE$
endif
return Table(this).$TYPE$[index]
endmethod
// Setter: list[index] = element
method operator []= takes integer index, $TYPE$ element returns nothing
if (index < 0 or index >= .length) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.set:IndexOutOfBounds")
return
endif
set Table(this).$TYPE$[index] = element
endmethod
method add takes integer index, $TYPE$ element returns boolean
local integer i
if (index < 0 or index > .length) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.add:IndexOutOfBounds")
return false
endif
set i = .length
loop
exitwhen i == index
set Table(this).$TYPE$[i] = Table(this).$TYPE$[i - 1]
set i = i - 1
endloop
set Table(this).$TYPE$[index] = element
set .length = .length + 1
return true
endmethod
method remove takes integer index returns $TYPE$
local integer i
local $TYPE$ returnValue
if (index < 0 or index >= .length) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.remove:IndexOutOfBounds")
return $NONE$
endif
set i = index
set .length = .length - 1
loop
exitwhen i == .length
set Table(this).$TYPE$[i] = Table(this).$TYPE$[i + 1]
set i = i + 1
endloop
set returnValue = Table(this).$TYPE$[i]
call Table(this).$TYPE$.remove(.length)
return returnValue
endmethod
method contains takes $TYPE$ value returns boolean
return .indexOf(value, true) != -1
endmethod
method indexOf takes $TYPE$ value, boolean ascending returns integer
local integer i
if ascending then
set i = 0
loop
exitwhen i == .length
if Table(this).$TYPE$[i] == value then
return i
endif
set i = i + 1
endloop
else
set i = .length - 1
loop
exitwhen i < 0
if Table(this).$TYPE$[i] == value then
return i
endif
set i = i - 1
endloop
endif
return -1
endmethod
method isEmpty takes nothing returns boolean
return .length == 0
endmethod
method size takes nothing returns integer
return .length
endmethod
method swap takes integer indexA, integer indexB returns nothing
local $TYPE$ temp
if (indexA < 0 or indexA >= .length or indexB < 0 or indexB >= .length) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.swap:IndexOutOfBounds")
return
endif
set temp = Table(this).$TYPE$[indexA]
set Table(this).$TYPE$[indexA] = Table(this).$TYPE$[indexB]
set Table(this).$TYPE$[indexB] = temp
endmethod
static method copy takes $NAME$ArrayList src, integer srcPos, $NAME$ArrayList dest, integer destPos, integer range returns nothing
local integer i = 0
if srcPos < 0 or srcPos == src.length or destPos < 0 or destPos > dest.length then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ArrayList.copy:IndexOutOfBounds")
return
endif
loop
exitwhen i == range or srcPos >= src.length
call dest.add(destPos, src[srcPos])
set destPos = destPos + 1
set srcPos = srcPos + 1
set i = i + 1
endloop
endmethod
endstruct
//! endtextmacro
endlibrary
Linked List |
$NAME$Node head
First node
$NAME$Node tail
Last node
integer length
Number of nodes
method add takes integer index, $TYPE$ value returns boolean
Inserts a value at the specified index. Returns true if succesful.
method addNode takes integer index, $NAME$Node nodeToAdd returns boolean
Inserts a node at the specified index. Returns true on success. Having nodes coexist in multiple lists should be avoided.
method addAfter takes $NAME$Node prevNode, $NAME$Node nodeToAdd returns boolean
Adds a node after a node, both nodes should exist in the same list. This is slightly faster than other add operations.
method addBefore takes $NAME$Node nextNode, $NAME$Node nodeToAdd returns boolean
Adds a node before a node, both nodes should exist in the same list. This is slightly faster than other add operations.
method clear takes nothing returns nothing
Removes all nodes from the list, deallocating the node references. If you wish to clear it without removing the nodes you will have to do so manually by nulling the head reference before calling this method.
method contains takes $TYPE$ value returns boolean
Searches for the value inside the list, returns true if it exists.
method destroy takes nothing returns nothing
Destroys the list clearing it in the process.
method eject takes $NAME$Node nodeToRemove returns $NAME$Node
Removes a node from the list without destroying it. Returns the removed node.
method find takes $TYPE$ value returns $NAME$Node
Searches the list for a node with the given value in ascending order, returns the node if found, otherwise 0.
method get takes integer index returns $NAME$Node
Retrieves the node at a given index, if outside bounds it returns 0.
method indexOf takes $TYPE$ value, boolean ascending returns integer
Returns the index of a given value, searching in either ascending (true) or descending (false) order.
method isEmpty takes nothing returns boolean
Returns true if the list is empty.
method remove takes integer index returns $TYPE$
Removes a value at the specified index, returning the value and deallocating the node in the process.
method removeNode takes $NAME$Node nodeToRemove returns $TYPE$
Removes the node from the list and returning the value and deallocating it in the process. Do not remove a node that doesn't belong
to the list you are manipulating.
method size takes nothing returns integer
The number of values the list contains.
method swap takes integer i, integer j returns nothing
Swap the values at the given positions if inside bounds.
method operator [] takes integer index returns $NAME$Node
This is a wrapper for get.
static method create takes nothing returns thistype
Creates a linked list.
List Utility Module |
method split takes integer index returns thistype
Splits the list in two at a given position. The right part of the split is returned and the left side is kept in the calling list.
method transfer takes integer index, $NAME$LinkedList src returns boolean
Moves all the current nodes from the source list to the calling list.
Iterator |
static thistype last
The iterator that has triggered the callback function.
boolean repeat
Set to true if you want periodic iterations to start over when they reach the end.
$NAME$Node enum
The current enumerated node that this iterator is on.
integer index
The current list position that the iterator is on.
method destroy takes nothing returns nothing
Destroys the iterator.
method forEach takes code callback returns thistype
Iterates through each node of the list, executing the callback function each time.
To get the last node or index simply use <NAME>Iterator.last.enum and <NAME>Iterator.last.index.
method forEachPeriodic takes real time, boolean repeat, code callback returns thistype
Starts a delayed iteration that either repeats when finished or halts. The cursor moves one step per time cycle executing the callback function each time.
method pause takes nothing returns nothing
Pauses the periodic iteration.
method resume takes nothing returns nothing
Resumes the periodic iteration.
static method create takes $NAME$LinkedList list returns thistype
Creates an iterator based on the provided list.
List Iterator Module |
method iterator takes nothing returns $NAME$Iterator
Returns a created iterator based on the calling list.
List Sort Module |
method addSorted takes $TYPE$ value returns nothing
Adds a value to it's proper sorted position. With the precondition that the list was sorted before.
method sort takes nothing returns nothing
Merge sorts the list, capable of sorting up to 4000 integers without reaching OP limit. Note that this limit is lower for other data types.
List Collection Module |
method addList takes integer index, $NAME$LinkedList srcs returns nothing
Copies all elements from the source list to the calling list, starting at a given position.
method addTable takes integer index, Table table returns nothing
Copies all elements from the source table to the calling list, starting at a given position. The elements must be formated as an ArrayList, if any null values are detected the copying will finish.
static method copyToTable takes $NAME$LinkedList src, integer srcPos, Table dest, integer destPos, integer range returns nothing
Copies a list from the specified source table position to the specified destination list position. The number of copied elements is equal to the provided range. The table must be organized as an ArrayList.
static method copyToList takes $NAME$LinkedList src, integer srcPos, $NAME$LinkedList dest, integer destPos, integer range returns nothing
Copies a list from the specified source list position to the specified destination list position. The number of copied elements is equal to the provided range. The table must be organized as an ArrayList.
List Order Module |
method moveLeft takes $NAME$Node node returns nothing
Moves the specified node one position to the left.
method moveRight takes $NAME$Node node returns nothing
Moves the specified node one position to the right.
method reverse takes nothing returns nothing
Reverses the list order so the last element becomes the first and the first element becomes the last.
method rotateLeft takes integer numOfPositions returns nothing
Shifts all elements to the left based on the provided number of positions.
method rotateRight takes integer numOfPositions returns nothing
Shifts all elements to the right based on the provided number of positions.
method swapNode takes $NAME$Node nodeA, $NAME$Node nodeB returns nothing
Used to swap nodes inside the list with each other. As opposed to swap(indexA, indexB) this is a hard swap, it swaps the actual nodes and not just the data. Note that swapping nodes that belong to different lists can lead to undesired behaviour. It is however faster as no lookup time is needed.
List Stack Queue Module |
method push takes $TYPE$ value returns thistype
Pushes a value to the top of the stack (first element).
method pop takes nothing returns $TYPE$
Retrieves a value from the top of the stack and removes it.
method peek takes nothing returns $TYPE$
Retrieves the value from the first position without removing it.
method offer takes $TYPE$ value returns thistype
Adds a value to the back of the queue (last element)
method poll takes nothing returns $TYPE$
Retrieves a value from the front of the queue (first element).
JASS:
library LinkedList uses Table
/*
Made by: Pinzu
Version 1.2.6
Link: https://www.hiveworkshop.com/threads/yetanotherlinkedlist-lab.307673/
Requirements:
Table by Bribe
hiveworkshop.com/threads/snippet-new-table.188084/
Credits:
Bannar, for his resource which this is based on
https://www.hiveworkshop.com/threads/containers-list-t.249011/page-2#post-3283437
IcemanBo, for answering all my question and pointing me in the right direction.
*/
//! runtextmacro DEFINE_PLINKED_LIST("Int", "integer", "0", "true", "false")
//! textmacro_once DEFINE_PLINKED_LIST takes NAME, TYPE, NONE, TABLE_NODES, TABLE_LIST
struct $NAME$Node
static if $TABLE_NODES$ then
method operator data takes nothing returns $TYPE$
return Table(this).$TYPE$[-1]
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]
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]
endmethod
method operator prev= takes thistype value returns nothing
set Table(this)[-3] = value
endmethod
else
thistype next
thistype prev
$TYPE$ data
endif
static method create takes $TYPE$ value returns thistype
local $NAME$Node node
static if $TABLE_NODES$ then
set node = Table.create()
else
set node = .allocate()
set node.next = 0
set node.prev = 0
endif
set node.data = value
return node
endmethod
method destroy takes nothing returns nothing
static if $TABLE_NODES$ then
call Table(this).destroy()
else
call .deallocate()
endif
endmethod
endstruct
struct $NAME$LinkedList
static if TABLE_LIST then
method operator head takes nothing returns $NAME$Node
return Table(this)[-1]
endmethod
method operator head= takes $NAME$Node node returns nothing
set Table(this).integer[-1] = node
endmethod
method operator tail takes nothing returns $NAME$Node
return Table(this)[-2]
endmethod
method operator tail= takes $NAME$Node node returns nothing
set Table(this).integer[-2] = node
endmethod
method operator length takes nothing returns integer
return Table(this)[-3]
endmethod
method operator length= takes integer value returns nothing
set Table(this).integer[-3] = value
endmethod
else
$NAME$Node head
$NAME$Node tail
integer length
endif
implement optional $NAME$ListSortModule
implement optional $NAME$IteratorModule
implement optional $NAME$ListCollectionModule
implement optional $NAME$$ListUtilityModule
implement optional $NAME$ListOrderModule
implement optional $NAME$ListStackQueueModule
static method create takes nothing returns thistype
local thistype this
static if $TABLE_LIST$ then
set this = Table.create()
else
set this = .allocate()
endif
set this.head = 0
set this.tail = 0
set this.length = 0
return this
endmethod
method destroy takes nothing returns nothing
call .clear()
static if $TABLE_LIST$ then
call Table(this).destroy()
else
call .deallocate()
endif
endmethod
method operator [] takes integer index returns $NAME$Node
return .get(index)
endmethod
method get takes integer index returns $NAME$Node
local $NAME$Node node
local integer i
if (index > .length/2) then
set i = .length - 1
set node = .tail
loop
exitwhen i <= index or node == 0
set i = i - 1
set node = node.prev
endloop
else
set i = 0
set node = .head
loop
exitwhen i >= index or node == 0
set i = i + 1
set node = node.next
endloop
endif
return node
endmethod
method find takes $TYPE$ value returns $NAME$Node
local $NAME$Node node = .head
loop
exitwhen node == 0 or node.data == value
set node = node.next
endloop
return node
endmethod
method eject takes $NAME$Node nodeToRemove returns $NAME$Node
if nodeToRemove == 0 then
return 0
endif
if (nodeToRemove == .head) then
set .head = .head.next
if (.head == 0) then
set .tail = 0
else
set .head.prev = 0
endif
elseif (nodeToRemove == .tail) then
set .tail = .tail.prev
if (.tail == 0) then
set .head = 0
else
set .tail.next = 0
endif
else
set nodeToRemove.prev.next = nodeToRemove.next
set nodeToRemove.next.prev = nodeToRemove.prev
endif
set .length = .length - 1
return nodeToRemove
endmethod
method add takes integer index, $TYPE$ value returns boolean
if (index > .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.add:IndexOutOfBounds")
return false
endif
return .addNode(index, $NAME$Node.create(value))
endmethod
method addNode takes integer index, $NAME$Node nodeToAdd returns boolean
if (index > .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.addNode:IndexOutOfBounds")
return false
endif
set nodeToAdd.prev.next = nodeToAdd.next
set nodeToAdd.next.prev = nodeToAdd.prev
if index == 0 then
if (.head == 0) then
set .head = nodeToAdd
set .tail = .head
else
set .head.prev = nodeToAdd
set nodeToAdd.next = .head
set .head = nodeToAdd
endif
set .length = .length + 1
return true
endif
return .addAfter(.get(index - 1), nodeToAdd)
endmethod
method addAfter takes $NAME$Node prevNode, $NAME$Node nodeToAdd returns boolean
if prevNode == 0 then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.addAfter:NullPointerException")
return false
endif
set prevNode.next.prev = nodeToAdd
set nodeToAdd.next = prevNode.next
set prevNode.next = nodeToAdd
set nodeToAdd.prev = prevNode
if nodeToAdd.next == 0 then
set .tail = nodeToAdd
endif
set .length = .length + 1
return true
endmethod
method addBefore takes $NAME$Node nextNode, $NAME$Node nodeToAdd returns boolean
if nextNode == 0 then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.addBefore:NullPointerException")
return false
endif
set nextNode.prev.next = nodeToAdd
set nodeToAdd.prev = nextNode.prev
set nextNode.prev = nodeToAdd
set nodeToAdd.next = nextNode
if nodeToAdd.prev == 0 then
set .head = nodeToAdd
endif
set .length = .length + 1
return true
endmethod
method clear takes nothing returns nothing
local $NAME$Node next
local $NAME$Node node = .head
loop
exitwhen node == 0
set next = node.next
call node.destroy()
set node = next
endloop
set .head = 0
set .tail = 0
set .length = 0
endmethod
method contains takes $TYPE$ value returns boolean
return .find(value) != 0
endmethod
method indexOf takes $TYPE$ value, boolean ascending returns integer
local $NAME$Node node = .head
local integer index = 0
if ascending then
loop
exitwhen node == 0
if (node.data == value) then
return index
endif
set index = index + 1
set node = node.next
endloop
else
set node = .tail
set index = .length - 1
loop
exitwhen node == 0
if (node.data == value) then
return index
endif
set index = index - 1
set node = node.prev
endloop
endif
return -1
endmethod
method isEmpty takes nothing returns boolean
return .length == 0
endmethod
method remove takes integer index returns $TYPE$
if (index >= .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.remove:IndexOutOfBounds")
return $NONE$
endif
return .removeNode(.get(index))
endmethod
method removeNode takes $NAME$Node nodeToRemove returns $TYPE$
local $TYPE$ returnValue = nodeToRemove.data
if nodeToRemove == 0 then
return $NONE$
endif
call .eject(nodeToRemove).destroy()
return returnValue
endmethod
method size takes nothing returns integer
return .length
endmethod
method swap takes integer i, integer j returns nothing
local $NAME$Node n1
local $NAME$Node n2
local $TYPE$ temp
if (i >= .length or i < 0 or j >= .length or j < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.swap:IndexOutOfBounds")
return
endif
set n1 = .get(i)
set n2 = .get(j)
set temp = n1.data
set n1.data = n2.data
set n2.data = temp
endmethod
endstruct
//! endtextmacro
endlibrary
JASS:
library ListUtilityModule uses LinkedList
//! runtextmacro LL_UTILITY("Int", "integer", "0")
//! textmacro_once LL_UTILITY takes NAME, TYPE, NONE
module $NAME$ListUtilityModule
method split takes integer index returns thistype
local $NAME$Node left
local $NAME$Node right
local $NAME$LinkedList list
if (index >= .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.split:IndexOutOfBounds")
return 0
endif
if .length <= 1 then
return 0
endif
set left = .get(index)
set right = left.next
set list = $NAME$LinkedList.create()
set left.next = 0
set right.prev = 0
set list.head = right
set list.tail = .tail
set .tail = left
set list.length = .length - index - 1
set .length = index + 1
return list
endmethod
method transfer takes integer index, $NAME$LinkedList list returns boolean
local $NAME$Node leftNode
local $NAME$Node rightNode
if (index > .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.transfer:IndexOutOfBounds")
return false
endif
if list.head == 0 or this == list then
return false
endif
if index == 0 then
if .length == 0 then
set .head = list.head
set .tail = list.tail
else
set list.tail.next = head
set .head.prev = list.tail
set .head = list.head
endif
elseif index == .length then
set .tail.next = list.head
set list.head.prev = .tail
set .tail = list.tail
else
set leftNode = .get(index - 1)
set rightNode = leftNode.next
set leftNode.next = list.head
set list.head.prev = leftNode
set rightNode.prev = list.tail
set list.tail.next = rightNode
set leftNode = .get(index)
set rightNode = leftNode.next
if rightNode == 0 then
set .tail = list.tail
endif
if leftNode == 0 then
set .head = list.head
endif
endif
set .length = .length + list.length
set list.length = 0
set list.head = 0
set list.tail = 0
return true
endmethod
endmodule
//! endtextmacro
endlibrary
JASS:
library ListSortModule
globals
private constant integer OP_LIMIT_INT = 4000 // integer limit
endglobals
//! runtextmacro LL_SORTER("Int", "integer", "n1.data < n2.data")
//! textmacro_once LL_SORTER takes NAME, TYPE, SORT
module $NAME$ListSortModule
implement $NAME$ListUtilityModule
method addSorted takes $TYPE$ value returns nothing
local $NAME$Node n1 = $NAME$Node.create(value)
local $NAME$Node n2 = .head
if .length == 0 or $SORT$ then
call .addNode(0, n1)
return
endif
set n2 = n2.next
loop
exitwhen n2 == 0
if $SORT$ then
call .addBefore(n2, n1)
return
endif
set n2 = n2.next
endloop
call .addAfter(.tail, n1)
endmethod
method sort takes nothing returns nothing
if .length > OP_LIMIT_INT then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$ListSortModule.sort:LimitReached")
return
endif
call thistype.mergesort(this)
endmethod
private static method mergesort takes $NAME$LinkedList list returns nothing
local $NAME$LinkedList left
local $NAME$LinkedList right
if list.length <= 1 then
return
endif
set left = $NAME$LinkedList.create()
call left.transfer(0, list) // O(1)
set right = left.split(left.length/2 - 1) // O(N/2)
call mergesort(left)
call mergesort(right)
call merge(left, right, list) // O(N) [slightly better as it only needs to sort one of the lists to completion]
call left.deallocate()
call right.deallocate()
endmethod
private static method merge takes $NAME$LinkedList left, $NAME$LinkedList right, $NAME$LinkedList srcs returns nothing
local $NAME$Node n1 = left.head
local $NAME$Node n2 = right.head
if $SORT$ then
set srcs.head = n1
set srcs.tail = n1
set n1 = n1.next
else
set srcs.head = n2
set srcs.tail = n2
set n2 = n2.next
endif
loop
exitwhen n1 == 0 or n2 == 0
if $SORT$ then
set srcs.tail.next = n1
set n1.prev = srcs.tail
set srcs.tail = n1
set n1 = n1.next
else
set srcs.tail.next = n2
set n2.prev = srcs.tail
set srcs.tail = n2
set n2 = n2.next
endif
endloop
if n1 != 0 then
set srcs.tail.next = n1
set n1.prev = srcs.tail
set srcs.tail = left.tail
elseif n2 != 0 then
set srcs.tail.next = n2
set n2.prev = srcs.tail
set srcs.tail = right.tail
endif
endmethod
endmodule
endlibrary
//! endtextmacro
JASS:
library ListIteratorModule uses LinkedList
//! runtextmacro LL_ITERATOR("Int", "integer")
//! textmacro_once LL_ITERATOR takes NAME, TYPE
struct $NAME$Iterator
private static Table table = 0
public static thistype last
private $NAME$LinkedList list
private $NAME$Node nextNode
private trigger callback
private timer tmr
public boolean repeat
public $NAME$Node enum
readonly integer index
static method create takes $NAME$LinkedList list returns thistype
local thistype this = .allocate()
set this.list = list
set this.enum = 0
set this.nextNode = list.head
return this
endmethod
private method cleanup takes nothing returns nothing
if .callback != null then
call TriggerClearConditions(.callback)
call DestroyTrigger(.callback)
set .callback = null
endif
if .tmr != null then
call thistype.table.remove(GetHandleId(.tmr))
call PauseTimer(.tmr)
call DestroyTimer(.tmr)
set .tmr = null
endif
endmethod
method destroy takes nothing returns nothing
call .cleanup()
endmethod
private method exec takes trigger t returns nothing
set .enum = .nextNode
set thistype.last = this
call TriggerEvaluate(t)
set .nextNode = .nextNode.next
set this.index = this.index + 1
endmethod
private static method onTimerExpires takes nothing returns nothing
local timer t = GetExpiredTimer()
local thistype this = thistype.table[GetHandleId(t)]
if this.nextNode == 0 then
if this.index < list.length then
set this.nextNode = list.get(this.index)
else
if not repeat then
call this.cleanup()
else
set this.index = 0
set this.nextNode = this.list.head
call this.exec(this.callback)
endif
endif
else
call this.exec(this.callback)
endif
set t = null
endmethod
method pause takes nothing returns nothing
if .tmr != null then
call PauseTimer(.tmr)
endif
endmethod
method resume takes nothing returns nothing
if .tmr != null then
call ResumeTimer(.tmr)
endif
endmethod
method forEachPeriodic takes real time, boolean repeat, code callback returns thistype
call .cleanup()
set .repeat = repeat
set .nextNode = list.head
set .index = 0
set .callback = CreateTrigger()
call TriggerAddCondition(.callback, Condition(callback))
set .tmr = CreateTimer()
call TimerStart(.tmr, time, true, function thistype.onTimerExpires)
if thistype.table == 0 then
set thistype.table = Table.create()
endif
set table[GetHandleId(.tmr)] = this
return this
endmethod
method forEach takes code callback returns thistype
local trigger localTrg = CreateTrigger()
set .nextNode = list.head
call TriggerAddCondition(localTrg, Condition(callback))
loop
exitwhen .nextNode == 0
call .exec(localTrg)
endloop
call TriggerClearConditions(localTrg)
call DestroyTrigger(localTrg)
set localTrg = null
return this
endmethod
endstruct
module $NAME$IteratorModule
method iterator takes nothing returns $NAME$Iterator
return $NAME$Iterator.create(this)
endmethod
endmodule
//! endtextmacro
endlibrary
The idea here is to create a module that allows for manipulation of multiple nodes simultaneously. Currently though, it only contains copying of nodes from/to a table/list. I might add containsAll, containsAny and retainAll(list) etc. Though unless someone specifically asks for this, I'm unlikely to do t.
JASS:
library ListCollectionModule uses LinkedList
//! runtextmacro LL_COLLECTION("Int", "integer")
//! textmacro_once LL_COLLECTION takes NAME, TYPE
module $NAME$ListCollectionModule
implement $NAME$ListUtilityModule
method addList takes integer index, $NAME$LinkedList srcs returns nothing
local thistype list
local $NAME$Node node
local integer i
if (index > .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.addList:IndexOutOfBounds")
return
endif
if srcs.length <= 0 then
return
endif
set list = $NAME$LinkedList.create()
set node = srcs.head
set i = 0
loop
exitwhen node == 0
call list.addNode(i, $NAME$Node.create(node.data))
set node = node.next
set i = i + 1
endloop
call .transfer(index, list)
call list.deallocate()
endmethod
method addTable takes integer index, Table table returns nothing
local integer i
local thistype list
if (index > .length or index < 0) then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.addTable:IndexOutOfBounds")
return
endif
set list = $NAME$LinkedList.create()
set i = 0
loop
exitwhen table[i] == 0 or not table.$TYPE$.has(i)
call list.add(list.length, table.$TYPE$[i])
set i = i + 1
endloop
call .transfer(index, list)
call list.deallocate()
endmethod
// Not Tested
static method copyToTable takes $NAME$LinkedList src, integer srcPos, Table dest, integer destPos, integer range returns nothing
local $NAME$Node n
local integer i
if srcPos < 0 or srcPos == src.length then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.copyToTable:IndexOutOfBounds")
return
endif
set i = 0
set n = src.get(srcPos)
loop
exitwhen n == 0 or i >= range or not dest.$TYPE$.has(i)
set dest.$TYPE$[destPos] = n.data
set i = i + 1
set destPos = destPos + 1
set n = n.next
endloop
endmethod
// Not Tested
static method copyToList takes $NAME$LinkedList src, integer srcPos, $NAME$LinkedList dest, integer destPos, integer range returns nothing
local $NAME$Node nsrc
local $NAME$Node ndest
local integer i
if srcPos < 0 or srcPos == src.length or destPos < 0 or destPos == dest.length then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.copyToList:IndexOutOfBounds")
return
endif
set nsrc = src.get(srcPos)
set ndest = src.get(destPos)
set i = 0
loop
exitwhen nsrc == 0 or i >= range
call dest.addBefore(ndest, $NAME$Node.create(nsrc.data))
set i = i + 1
set nsrc = nsrc.next
endloop
endmethod
endmodule
//! endtextmacro
endlibrary
JASS:
library ListOrderModule uses LinkedList
//! runtextmacro LL_ORDER("Int", "integer", "0")
//! textmacro_once LL_ORDER takes NAME, TYPE, NONE
module $NAME$ListOrderModule
method swapNode takes $NAME$Node a, $NAME$Node b returns nothing
local $NAME$Node temp
if a == b or a == 0 or b == 0 then
debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, "$NAME$LinkedList.swapNode:InvalidArgument")
return
endif
set temp = a.next
set a.next.prev = b
set a.next = b.next
set b.next.prev = a
set b.next = temp
set temp = a.prev
set a.prev.next = b
set a.prev = b.prev
set b.prev.next = a
set b.prev = temp
if a.prev == 0 then
set .head = a
elseif b.prev == 0 then
set .head = b
endif
if a.next == 0 then
set .tail = a
elseif b.next == 0 then
set .tail = b
endif
endmethod
method moveLeft takes $NAME$Node n returns nothing
if n.prev != 0 then
call swapNode(n, n.prev)
else
call swapNode(n, .tail)
endif
endmethod
method moveRight takes $NAME$Node n returns nothing
if n.next != 0 then
call swapNode(n, n.next)
else
call swapNode(n, .head)
endif
endmethod
method reverse takes nothing returns nothing
local $NAME$Node temp
local $NAME$Node node = .head
if .length <= 1 then
return
endif
set .tail = .head
loop
exitwhen node == 0
set temp = node.prev
set node.prev = node.next
set node.next = temp
set node = node.prev
endloop
set .head = temp.prev
endmethod
private method rotate takes integer numOfPositions returns nothing
local $NAME$Node newHead
if numOfPositions < 0 then
set numOfPositions = -1*numOfPositions
set newHead = .get(.length - ModuloInteger(numOfPositions, .length + 1))
else
set newHead = .get(ModuloInteger(numOfPositions, .length))
endif
set head.prev = tail
set tail.next = head
set head = newHead
set tail = head.prev
set head.prev = 0
set tail.next = 0
endmethod
method rotateLeft takes integer numOfPositions returns nothing
call .rotate(numOfPositions)
endmethod
method rotateRight takes integer numOfPositions returns nothing
call .rotate(-1*numOfPositions)
endmethod
endmodule
//! endtextmacro
endlibrary
JASS:
library ListStackQueueModule uses LinkedList
//! runtextmacro LL_STACK_QUEUE("Int", "integer", "0")
//! textmacro_once LL_STACK_QUEUE takes NAME, TYPE, NONE
module $NAME$ListStackQueueModule
method push takes $TYPE$ value returns thistype
call .add(0, value)
return this
endmethod
method pop takes nothing returns $TYPE$
return .removeNode(.head)
endmethod
method peek takes nothing returns $TYPE$
return .head.data
endmethod
method offer takes $TYPE$ value returns thistype
call .add(.length, value)
return this
endmethod
method poll takes nothing returns $TYPE$
return .remove(0)
endmethod
endmodule
//! endtextmacro
endlibrary
CAUTION:
Be careful with what you do when handling nodes outside of the list. Destroying a node inside a list will break the chain if it was not first removed or ejected. Using nodes that don't belong to a list as an argument is generally speaking an illegal argument and should never be done as it can cause all kinds of funny business. If you wish to transfer a node from one list to another use the eject method first.
Destroying a list will also destroy all nodes held there in, if you wish to keep all the nodes but destroy the list, you need to save the head reference somewhere and set the head to 0 before destroying the list.
1.0.0
- DoubleLinkedList for integers
1.0.1
- Fixed: bug with double remove in the iterator (should not be allowed)
- Fixed: bug with removeLast having a parameter
- Added: method copyRange takes integer start, integer end, boolean keepReferences returns thistype
if no node is provided it creates a new one based on the value
- Added: method copyRange takes integer start, integer end, boolean copyNodes returns thistype
~ Copying a list whilst remaining the same node references in both causes remove()
to not function properly (should be removed on both lists I reckon).
1.0.2
- Removed the posibility of copying a list whilst keeping the same references.
- Added: method sort takes nothing returns nothing (selection sort O^2)
- Added: method rotateLeft takes integer numOfPositions returns nothing
- Added: method rotateRight takes integer numOfPositions returns nothing
1.0.3
- Made iterator a member of List so that it gets recycled rather than having the user
or perhaps all instances created should be saved in a table so that when the list is destroyed
all the iterators (if not destroyed get destroyed)
- Removed addNode takes integer index, Node nodeToAdd, integer value returns boolean
- Fixed: Bug with rotateLeft and rotateRight
1.0.4
- Temporarily removed sort
- Temporarily removed Iterator
- Implemented generic types
1.0.5
- Readded: Iterator
- Readded: Basic sorting (still selection sort) the user can now specify sort condition using
a tetmacro.
- Moved: list.createNode(Value) to Node.create(value)
- Moved: list.destroyNode(Value) to Node.destroy()
1.2.0
- Fixed a bug with the getNode backwards iteration.
- Added: swapNode(Node, Node)
- Added: moveLeft(Node)
- Added: moveRight(Node)
- Added: addList(Index, List) (insert all nodes from a list)
- Added: addTable(Index, Table) (inserts all indexed elements of a table)
- Added: addAfter(node, nodeToAdd)
- Added: split(Index)
- Changed: sorting now uses merge sort and can sort up to 4000 elements before hitting OP limit.
- Fixed: RotateLeft and RotateRight have been modified and can now rotate in inverse direction.
- Fixed: Adding a node with previous references will also delink the previous references to the added
node.
- Changed: clear() to clear(boolean) to take a flag for if the nodes should get deallocated or not.
- Changed: removeNode(node) no longer also destroys the node. However, the wrappers remove(index), removeValue(value), removeFirst and removeLast still do.
- Removed Iterator
- Removed the use of Alloc
1.2.5
- Added: indexOfLast(value): backwards search for the index of a value.
- Added: transfer(index, srcs) takes all the nodes in one list and injects them to another, empties the source list of any nodes.
- Added: addBefore(node, nodeToAdd)
- Added: addSorted(value), adds a node to a sorted position, precondition the list is sorted.
- Added: ejectNode(node) removes the node from the list without destroying it and returns the reference.
- Added: reverse, changes the order so that the tail becomes the first node, and the head the last node.
- Added: IteratorModule containing new tentative and optional features.
- Added: iterator() creates a iterator based on the list.
- Added: iterator.forEach(callback)
- Added: iterator.forEachPeriodic(time, repeating, callback)
- Added: iterator pause()
- Added: iterator resume()
- Added: copyToList and copyToTable.
- Changed: Moved addList, addTable copyToList and copyToTable to List Collection Module.
- Changed: merge used when mergesorting was optimized to not use any methodcalls (except for node operators).
- Changed: addList now copies each node in the source rather than transferring them.
- Changed: MergeSort was made into an optional module and moved to a separate library that must be configured for each list that you wish to include it for.
- Changed removeNode(node) now also deallocates the node again.
- Fixed: addAfter(node) now works.
1.2.6
- Removed: ListWrapperModule and all the methods therein
- Removed: addFirst, addLast, getFirst, getLast, defineFirst, defineLast, get
- Changed: getNode --> get
- Changed: ejectNode --> eject
- Changed: findNode --> find
- Changed: indexOf/IndexOfLast --> indexOf(value, ascending)
- Changed: transfer and split was moved to ListUtilityModule.
- Fixed: Added a .has() check to the Collection Module when dealing with tables.
- Added: method operator [index] ( same as list.get(index) )
- Added: You can now toggle if the list or the nodes should be table based or array based when running the textmacro.
- Added: Stack Queue Module containing regular stack and queue interface: push, pop, peek, offer, poll.
- Added: Swap(indexA, indexB) to the main library.
- change the split method to not allocate any lists internally.
{ static method split(sourceList, index, leftList, rightList) }
- moveLeft and moveRight should take in numberOfPositions as argument
- Periodic iterations should have an argument for number of elements to callback on each cycle
- find should also take in a boolean for ascending or descening order.
- Fix minor errors in the documentation.
Last edited: