YetAnotherLinkedList Lab

Pinzu · Aug 6, 2018

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.

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.

Pinzu · Aug 7, 2018

Updated 1.0.5.

I've implemented all the API that was planned and it now also handles <T>. I hope it works as intended (it's not yet fully tested though, but the code looks right to me at least).

I need help with 3 things and any suggestions on how to accomplish it would be great.

1) The sort algorithm needs to be changed to MergeSort if you are up to it, you can copy the code and attempt to implement it bassed on what's already provided.
2) The library has 2 features sort and iterator, these should preferably me methods inside the LinkedList. However, I want to make them optional and be excluded if the user does not need them.

3) Finally. I'm not sure how the iterator cleanup should take place. Shall they be indexed and all removed when the LinkedList is destroyed, limit the use to one and recycle them or leave it up to the user to handle his own memory!

Any advice on optimizations or code that should be changed is also appreciated.

JASS:

scope MyListTest initializer Init
    globals
        IntLinkedList list
        IntNode curNode
    endglobals
 
    function PrintListIter takes nothing returns nothing
        local integer counter = 0
        local string s = ""
        loop
            exitwhen curNode == 0 or counter == 30
            set s = s + I2S(curNode.data) + ", "
            set curNode = curNode.next
            set counter = counter + 1
        endloop
        call BJDebugMsg(s)
        if (curNode != 0) then
            call ExecuteFunc("PrintListIter")
        endif
    endfunction
 
    private function SortingDone takes nothing returns nothing
        local IntLinkedList last = GetLastSortedList()
        call BJDebugMsg("Sort completed.")
        set curNode = last.head
        call ExecuteFunc("PrintListIter")
    endfunction
    private function Main takes nothing returns nothing
        local trigger t
        local string s = ""
        local integer max = 1000
        local integer i = 0
 
        set list = IntLinkedList.create()
        set i = 0
        loop
            exitwhen i == max
            call list.add(0, GetRandomInt(-100, 100))
            set i = i + 1
        endloop
 
 
        call BJDebugMsg("Size " + I2S(list.size()))
        set t = CreateTrigger()
        call TriggerAddAction(t, function SortingDone)
        call list.sort(t)
    endfunction
 
    private function Init takes nothing returns nothing
        local timer t = CreateTimer()
        call TimerStart(t, 0.5, false, function Main)
    endfunction
endscope

After further testing and help from Ice the sorting method was made to become asynchronous, but as it uses selection sort O(n^2) it is horrible to use. But could sort 2000+ (with a terrible freeze as result) without async it could sort 350 elements before reaching OP limit.

A way forward from here would be to just transpose all the elements from the list into an array, sorting them and putting them back in. But that probably shouldn't be handled in the main library.

The question then becomes should i keep the basic sort() method that can sort up to 350 elements in the library or should i exclude it all together? 350 elements and possibly higher with a better algorithm could be quite useful after all.

AGD · Aug 8, 2018

When making a global linkedlist struct, you better not limit the max number of list instances as there are so many things that can have a list of its own. One example is struct instances, another thing can be units. A systems for some reason might allocate a list for each unit on an index event, and there's a chance that multiple systems would do the same. In which case, the current instances limit would easily be exceeded. Ofcourse you could re-run the textmacros for already defined types and just give it a different name, but that would defeat the purpose of a global data structure. I suggest to just use Table as an allocator for all the structs. Btw, currently, Alloc's allocate() is nowhere used in the Node struct.
Nevermind this. Same issue could be faced by any non-Table based struct. Now the more sensible thing to do would be for the user to be efficient in managing the amount of allocated object instances. :O

As for the potential code bloat, I'm not so much worried right now as long it's all linked-list related because as we're aware, Blizz adapted the vJass as WE's language and there's a big chance (I think so) that WE's compiler will also be updated, especially with Mindworxz into the mix. But right now, you could provide static ifs to turn extra features on/off.

I don't know what's the point of an interator in jass though since usually the purpose of having an iterator is just to provide a better syntax for iteration like "node++", but there's no such operator in vjass and it would be better just use the usual way of iterating as it's simple and it also prevents a lot of overhead when making an iterator struct like you did.

There are probably alot of room for optimizations in the other utility methods but I haven't looked at all of them yet. But I'm pretty sure the rotate left/right methods can be optimized by not rotating by 1 repeatedly but instead, just skip to the node that's going to be the new head and then make it so and make it's prev the new tail, then just link the prev head and tail together.

Some more utility functions I can suggest are:
- node swap, O(1)
- appending two lists, O(1), (this can simplify a mergesort algorithm)
- move a node to the left/right (basically just a wrapper to node swap)

Almia · Aug 17, 2018

A sorting algorithm should accept a comparator function.

I have had a compilation of sorting algoritmhs for the Table library before:
TableSort

a Bottom Up Merge Sort could be the best sort for lists

Pinzu · Aug 21, 2018

AGD said:
As for the potential code bloat, I'm not so much worried right now as long it's all linked-list related because as we're aware, Blizz adapted the vJass as WE's language and there's a big chance (I think so) that WE's compiler will also be updated, especially with Mindworxz into the mix. But right now, you could provide static ifs to turn extra features on/off.

I don't know what's the point of an interator in jass though since usually the purpose of having an iterator is just to provide a better syntax for iteration like "node++", but there's no such operator in vjass and it would be better just use the usual way of iterating as it's simple and it also prevents a lot of overhead when making an iterator struct like you did.

There are probably alot of room for optimizations in the other utility methods but I haven't looked at all of them yet. But I'm pretty sure the rotate left/right methods can be optimized by not rotating by 1 repeatedly but instead, just skip to the node that's going to be the new head and then make it so and make it's prev the new tail, then just link the prev head and tail together.

Some more utility functions I can suggest are:
- node swap, O(1)
- appending two lists, O(1), (this can simplify a mergesort algorithm)
- move a node to the left/right (basically just a wrapper to node swap)

By append a list, you mean copy all the nodes? Othererwise you'll run into trouble when destroying the other list, as when destroy is called all the nodes in that list are also destroyed. So either its gonna be O(n) or what you are looking for is better handled inside the sort itself. Alternativley the user will have to be careful with how they destroy their list.

Same goes for node swap, does it need to swap anything other than the data inside the nodes?

Actually I tested the node structure and I managed to come up to 145k created instances and then i got bored and reversed it.

JASS:

scope TestList initializer Init
    globals
        private IntLinkedList cur
        private integer curData
        private integer steps = 1
        private trigger t
        private IntLinkedList head
        private IntLinkedList tail
        private boolean reverse = false
    endglobals
    private function Periodic takes nothing returns nothing
        local integer i = 0
        if not reverse then
            loop
                exitwhen i == steps
                set curData = curData + 1
                set tail.next = IntLinkedList.create(curData)
                set tail.next.prev = tail
                set tail = tail.next
                call BJDebugMsg(I2S(cur.data))
                set cur = cur.next
                set i = i + 1
            endloop
        else
            loop
                exitwhen i == steps or cur == 0
                call BJDebugMsg(I2S(cur.data))
                set cur = cur.prev
                set i = i + 1
            endloop
            if (cur == 0) then
                set cur = head
            endif
        endif
    endfunction
    function Start takes nothing returns nothing
        call EnableTrigger(t)
    endfunction
    function Stop takes nothing returns nothing
        call DisableTrigger(t)
    endfunction
    function Interval takes nothing returns nothing
        set steps = S2I(PChat.last.word[1])
    endfunction
    function Head takes nothing returns nothing
        call BJDebugMsg(I2S(head.data))
    endfunction
 
    function toggleReverse takes nothing returns nothing
        set reverse = not reverse
    endfunction
    private function Init takes nothing returns nothing
        set t = CreateTrigger()
        call TriggerRegisterTimerEventPeriodic(t, 0.01)
        call TriggerAddAction(t, function Periodic)
        set curData = 1
        set cur = IntLinkedList.create(curData)
        set head = cur
        set tail = cur
        call Command.register("-start", function Start)
        call Command.register("-stop", function Stop)
        call Command.register("-interval", function Interval)
        call Command.register("-head", function Head)
        call Command.register("-reverse", function toggleReverse)
    endfunction
endscope

Here are your suggested methods. I didnt test moveLeft, moveRight or appendList but they look okay to me. I also changed the clear method to take in a boolean to flag weather or not the nodes should get deallocated or not.

JASS:

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, TAG + ".swapNode:" + ERR_ARG)
                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, n.head)
            endif
        endmethod
 
        method appendList takes $NAME$LinkedList list returns nothing
            if list.head == 0 then
                return
            endif
            set .tail.next = list.head
            set .tail = list.tail
            set .length = .length + list.length
        endmethod

JASS:

method rotateLeft takes integer numOfPositions returns nothing
            local $NAME$Node newHead
            if (numOfPositions < 1) then
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, TAG + ".rotateLeft:" + ERR_ARG)
                return
            endif
            if .length <= 1 then
                return
            endif
            set numOfPositions = ModuloInteger(numOfPositions, .length)
            set newHead = .getNode(numOfPositions)
            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 rotateRight takes integer numOfPositions returns nothing
            local $NAME$Node newHead
            if (numOfPositions < 1) then
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, TAG + ".rotateRight:" + ERR_ARG)
                return
            endif
            if .length <= 1 then
                return
            endif
            set numOfPositions = ModuloInteger(numOfPositions, .length + 1)
            set newHead = .getNode(.length - numOfPositions)
            set head.prev = tail
            set tail.next = head
            set head = newHead
            set tail = head.prev
            set head.prev = 0
            set tail.next = 0
        endmethod

Almia said:
A sorting algorithm should accept a comparator function.

I have had a compilation of sorting algoritmhs for the Table library before:
TableSort

a Bottom Up Merge Sort could be the best sort for lists

Did you manage OP limit in any of those? Because then I could just cast the list to an array and sort it there. Also what's the biggest size you manged to sort?

JASS:

static method copyToArray takes  $NAME$Node srcs, Table dest, integer destIndex, integer range returns Table
            local integer i = destIndex
            local integer j = 0
            loop
                exitwhen srcs == 0 or j == MAX_RANGE_TO_ARRAY or j == range
                set dest.$TYPE$[i] = srcs.data
                set i = i + 1
                set j = j + 1
                set srcs = srcs.next
            endloop
            if j == MAX_RANGE_TO_ARRAY then
                debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, TAG + ".toArray:" + ERR_OP)
            endif
            return dest
        endmethod

AGD · Aug 22, 2018

Pinzu said:
By append a list, you mean copy all the nodes? Othererwise you'll run into trouble when destroying the other list, as when destroy is called all the nodes in that list are also destroyed. So either its gonna be O(n) or what you are looking for is better handled inside the sort itself. Alternativley the user will have to be careful with how they destroy their list.

What I had in mind is the nodes itself will be transferred - meaning the links of the source list to its nodes will be removed (so you could also call it transfer instead of append list). Same goes for node swap.

Pinzu · Aug 22, 2018

Update: 1.2
Most notable changes are that the sorting algorithm now uses merge sort and can sort up to 4000 elements without hitting OP limit (for integers). I also added addList and addTable to insert lists and tables into a list.

Finally, split(index) was added which allocates a new list containing the right side of the list. I'm not certain that the current syntax of it is the most logical. Perhaps it would be better to write something like:

static method split(sourceList, index, leftList, rightList) This would then empty the source list and then devide the nodes between left and right.

You can find the full changes and changelog in the opening post.

Pinzu · Aug 25, 2018

- 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.

The API has expanded yet again.... yay? ^^

Anyway, I could use some suggestions on what to move into optional modules, and how to organize the library.

Also added a tentative module for forEach syntax. It's just a concept atm so it's probably lacking some flexibility right now. Might in the future also include a argument for how many nodes should be iterated at each time interval.

JASS:

private function Iterate takes nothing returns nothing
    call BJDebugMsg(I2S(IntIterator.last.data))
endfunction

call list.iterator().forEach(function Iterate).destroy() // Iterates through the list and then destroys the iterator.

// Alternativly you can write
set itr = IntIterator(list)
call itr.forEach().destroy()

// Iterates through each node periodically with a 0.5 second interval, will start over when it reaches the end.
set itr = list.iterator().forEachPeriodic(0.5, true, function Iterate)

set itr = list.iterator().forEachPeriodic(0.5, false, function Iterate)  // One Shot iteration with delay

call itr.pause() // will pause the iterator
call itr.resume() // will resume the iterator

Also, as of right now I'm not entierly sure how to best inform the callback that it has finished so that they can clean up the iterator if that is wanted.

IcemanBo · Aug 25, 2018

Pinzu said:
how to organize the library

Imo, just some quick opinion, API could maybe be shortened a bit.

Only one add and one remove function with index parameter could do it. Example
list.add("Hello", list.front)
list.remove(list.back)
Methods for add before/after can maybe be helpful, but if code gets big maybe not too essential.
addTable,addNode, addSorted
why/when to use this exactly - what does it do? Should one same node exist in multiple lists? I would probably not think so, and just also remove all nodes on cleanup maybe without extra boolean param.
For "define" are also not three methods maybe needed. Is it actually needed at all? One would just use the operator data=, or?
moveRight/Left I would remove, and just would user use swap(index, index+1) or so

Pinzu · Aug 25, 2018

IcemanBo said:
Imo, just some quick opinion, API could maybe be shortened a bit.

Only one add and one remove function with index parameter could do it. Example
list.add("Hello", list.front)
list.remove(list.back)
Methods for add before/after can maybe be helpful, but if code gets big maybe not too essential.

addTable,addNode, addSorted
why/when to use this exactly - what does it do? Should one same node exist in multiple lists? I would probably not think so, and just also remove all nodes on cleanup maybe without extra boolean param.

For "define" are also not three methods maybe needed. Is it actually needed at all? One would just use the operator data=, or?

moveRight/Left I would remove, and just would user use swap(index, index+1) or so

- addFirst, addLast, getFirst, getLast and removeFirst, and maybe even define and get removeLast are essentially useless as you have: list.getNode(index).data = 10, list.removeNode(list.getNode(4)) or list.remove(4)
- addSorted is part of the list sort module and adds a node in order, if you want to maintain such a thing. So if you have a list containing 2, 4, 6 8 and want to add 5 it will become: 2 4 5 6 8.
- addTable pretends that the table is an indexed array and tries to add all elementss from 0 to n in the table to the list (similar to copyToTable but I haven't tested those so i kept the old method). All these methods have already been removed to List Collection Module. It creates a copy of the node and doesn't put the same node reference in the list (nothing does that anymore).

Maybe even list.removeNode(node) is replaced by list.ejectNode(node).destroy()

Your swap method would just be a wrapper for: list.swapNode(list.getNode(1), list.getNode(3)). Maybe it would look prettier but it would have slightly less utility. Though it would be safer as you wouldn't be able to swap nodes from different lists, which is dangerous when it's swapping heads or tails.

As for addNode, it's baasically what happens when you use add(index, value) I could make it private but the code is not going anywhere, i don't think. So it might be more useful to keep it public. The bloat of addAfter and addBefore is negligible as it's used in addNode and other places.

If i remove the list.clear(true/false) logic I would have to put in a different method for list.clear(false) as it's used in a few places in the library.
----

I color coded the API to illustrate the different modules that i may or may not put things in.

IcemanBo · Aug 25, 2018

Maybe just allow swapping within a list, it would be fine imo, so swap(3, 5) would be good!^^
Pinzu said:

If i remove the list.clear(true/false) logic I would have to put in a different method for list.clear(false) as it's used in a few places in the library.

Click to expand...

I can not spot these places. Does it make sense to have (unique) list elements un-attached to any list?
Or ejectNode can be replaced by remove?
Even if addAfter, addBefore stays, I believe, only one method can exist which can handle add-logics at any place, and all others would just call this one method, with specifying index.
Could you prodive the iteratorIndex inside the forEach callback, to know the current loop amount? (it's not necessarily equal with index in list, I guess, if removed or so)
And maybe there can be maybe 1 static trigger for the iteratoions that is just cleaned of conditions but never destroyed.

Nice you made colors to API, but could you please sort them by lib/module at first, and then only if needed by alphabet? (maybe even seperated by empty line or complete new list)

Pinzu · Aug 25, 2018

IcemanBo said:
Maybe just allow swapping within a list, it would be fine imo, so swap(3, 5) would be good!^^

I can not spot these places. Does it make sense to have (unique) list elements un-attached to any list?

Or ejectNode can be replaced by remove?

Even if addAfter, addBefore stays, I believe, only one method can exist which can handle add-logics at any place, and all others would just call this one method, with specifying index.

Could you prodive the iteratorIndex inside the forEach callback, to know the current loop amount? (it's not necessarily equal with index in list, I guess, if removed or so)
And maybe there can be maybe 1 static trigger for the iteratoions that is just cleaned of conditions but never destroyed.

Nice you made colors to API, but could you please sort them by lib/module at first, and then only if needed by alphabet? (maybe even seperated by empty line or complete new list)

1) But that's O(n) wher as swapNode can be O(1) if you have the nodes on you. Though moveLeft and moveRight should be replaced with swap(index, index)
2) It's in the transfer and split methods if I recall, maybe more.
3) EjectNode was just to continue with the node access concept. It's basically the safe way to remove a node and put it in another list if you'd ever want to do that.

list2.addNode(0, list1.ejectNode(list1.getNode(2))) or something like that. Though you could probably just do: list2.add(0, list1.remov(2))

Maybe you're right, don't know^^

4) Sure the index can be readonly integer. I made it none static so you can have multiple iterators per list.

I'm a bit reluctant to make node private to protect the user, because half of what makes linked list structure exciting is the direct access to nodes, if that's not there one should stick to an ArrayList , or? Removing ejectNode, changing swapNode to swap and removing addNode would be in the spirit of protecting the user, but remove the benefit of a node structure, I'm thinking.

I'll add ejectAll returning the head to replace .clear(false) and end that discussion.

IcemanBo · Aug 25, 2018

Pinzu said:
It's in the transfer and split methods if I recall, maybe more

JASS:

        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, TAG + ".addList:" + ERR_BOUNDS)
                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 = .getNode(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 = .getNode(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
 
        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, TAG + ".split:" + ERR_BOUNDS)
                return 0
            endif
            if .length <= 1 then
                return 0
            endif
            set left = .getNode(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

^is the opening post maybe not updated? clear(false) seems not used.

ejectNode, having same nodes in multiple lists, and fun games alike -- it may become risky , but at same time the question is if the win of functionality is worth it. Dunno, at least it's harder to check things, I guess. Maybe a reference counter is then required to at least check how often a node is injected into a list, to know if it should be hard-destroyed once a list gets destroyed, or just uncoupled. Or a hard, and a soft destroy, with caring/not caring for ref counter. User will have always to define it.

Maybe it can be possible to use nodes, but imo it's probably not required to double the API because of that, for allowing node syntax + allowing index syntax. If user wants to use data= operator or destroy() or such, then it's legit.

Pinzu · Aug 26, 2018

Update: 1.2.6
- Removed: ListWrapperModule and all the methods therein
- Removed: addFirst, addLast, get, getFirst, getLast, define, defineFirst, defineLast
- Changed: clear(cleanup) --> clear()
- 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.

Introduced some minor changes. Most notably...

Now you can decide yourself if the list and node struct should be table or array based.
Eliminated a redudant module and replaced it with a method operator.

list.get(index) is replaced with list[index].data or list.get(index).data
list.define(index, value) is replaced with list[index].data = value or list.get(index).data = value
list.getFirst() is replaced with list.head.data
list.getLast() is replaced with list.tail.data

YetAnotherLinkedList Lab

Similar threads