1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. DID YOU KNOW - That you can unlock new rank icons by posting on the forums or winning contests? Click here to customize your rank or read our User Rank Policy to see a list of ranks that you can unlock. Have you won a contest and still havn't received your rank award? Then please contact the administration.
    Dismiss Notice
  3. The Lich King demands your service! We've reached the 19th edition of the Icon Contest. Come along and make some chilling servants for the one true king.
    Dismiss Notice
  4. The 4th SFX Contest has started. Be sure to participate and have a fun factor in it.
    Dismiss Notice
  5. The poll for the 21st Terraining Contest is LIVE. Be sure to check out the entries and vote for one.
    Dismiss Notice
  6. The results are out! Check them out.
    Dismiss Notice
  7. Don’t forget to sign up for the Hive Cup. There’s a 555 EUR prize pool. Sign up now!
    Dismiss Notice
  8. The Hive Workshop Cup contest results have been announced! See the maps that'll be featured in the Hive Workshop Cup tournament!
    Dismiss Notice
  9. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

YetAnotherLinkedList Lab

Discussion in 'The Lab' started by Pinzu, Aug 6, 2018.

  1. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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.

    PArrayList
    Code (vJASS):
    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


    API

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




    Library
    Code (vJASS):

    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
     


    ListUtilityModule
    Code (vJASS):

    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


    List Sort Module
    Code (vJASS):

    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
     


    Iterator Module
    Code (vJASS):

    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
     


    List Collection Module

    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.
    Code (vJASS):

    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
     


    List Order Module
    Code (vJASS):

    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
     


    List Stack Queue Module
    Code (vJASS):

    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.

    Changelog

    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.


    Future Works

    - 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: Jan 27, 2019
  2. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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.

    Sort test code
    Code (vJASS):

    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.
     
    Last edited: Aug 22, 2018
  3. AGD

    AGD

    Joined:
    Mar 29, 2016
    Messages:
    397
    Resources:
    13
    Spells:
    7
    Tutorials:
    1
    JASS:
    5
    Resources:
    13
    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)
     
    Last edited: Aug 13, 2018
  4. Almia

    Almia

    Joined:
    Apr 24, 2012
    Messages:
    4,842
    Resources:
    35
    Spells:
    30
    Tutorials:
    4
    JASS:
    1
    Resources:
    35
    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
     
  5. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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.


    Node
    Code (vJASS):

    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.

    Your suggested API

    Code (vJASS):

    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


    Fixes to rotation
    Code (vJASS):

     
    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

     


    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?

    Added a toArray method (OP LIMIT 6000 elements)
    Code (vJASS):

    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
     
     
    Last edited: Jan 12, 2019
  6. AGD

    AGD

    Joined:
    Mar 29, 2016
    Messages:
    397
    Resources:
    13
    Spells:
    7
    Tutorials:
    1
    JASS:
    5
    Resources:
    13
    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.
     
  7. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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.
     
    Last edited: Aug 24, 2018
  8. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    Update 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.


    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.
    Code (vJASS):

    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.
     
    Last edited: Aug 25, 2018
  9. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,166
    Resources:
    22
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    4
    JASS:
    3
    Resources:
    22
    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
     
  10. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    - 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.
     
    Last edited: Aug 25, 2018
  11. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,166
    Resources:
    22
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    4
    JASS:
    3
    Resources:
    22
    • 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)
     
  12. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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.
     
    Last edited: Aug 25, 2018
  13. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,166
    Resources:
    22
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    4
    JASS:
    3
    Resources:
    22
    Code (vJASS):

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

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    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
     
    Last edited: Aug 26, 2018