[System] List

[The_Witcher]

This implements the list class into Warcraft III.
It differs from the already exisiting linkedList members in that
it allows the creation of non-struct lists, too, like booleanList, stringList,...

For more information, please read the documentation

Documentation:

//============================================================================== 
//==========================   List   ========================================== 
//============================================================================== 
// List by The_Witcher
//  It supports any type you can imagine!
//  player lists, unit lists, real lists, hashtable lists, effect lists...
//  You can even create lists for custom structs!
//
//============================================================================== 
//  What Is A List ?
//
//  The List class is a very useful general purpose list container.
//  It differs from arrays in that it provides richer functionality. 
//
//  Every list has a pointer which moves through it.
//  This pointer can be set to first, last or the next and previous node
//  you added. You can always access the object the pointer points at.
//
//==============================================================================
//   
//  Usage:
//      Initialization:
//          First initialize the list you need with the textmacro line
//              //! runtextmacro CreateList("<yourListType>")         
//          This will result in a new struct class called  <yourListType>List.
//
//          Example:         //! runtextmacro CreateList("real")
//                           will create the struct realList!
//
//      Working with a List:
//          Create your list instance using 
//              myList = <listType>List.create()
//
//          After that you can add add new objects of the type you specified to
//          your list.
//
//          You move through your list by calling myList.toFirst() or myList.toLast()
//          and then move the pointer node by node using myList.next() and myList.prev()
//
//          You can access the object stored at the pointer's
//          position by the member myList.object
//
//          If you destroy your list using myList.destroy() all nodes will be 
//          destroyed, too, so this is leakfree.
//
//      Looping through a List:
//          It is very easy to loop through a list but I will give an example how to:
//
//          myList.toFirst()
//          loop
//              exitwhen myList.finished
//              //do stuff here
//              call myList.next()
//          endloop
//
//          If you want to interrupt your loop just call myList.finish()
//
//==============================================================================  
//
//  !Note!    yourtype always refers to the type of the list you use! (real, boolean, player, any struct, ...)
// 
//  Methods:
//
//     Moving in the list:
//
//        method toFirst takes nothing returns nothing
//
//        method toLast takes nothing returns nothing
//        
//        method next takes nothing returns nothing
//    
//        method prev takes nothing returns nothing
//
//        method finish takes nothing returns nothing
//
//    Adding/Removing nodes:  
//        
//        method remove takes nothing returns nothing
//           Removes the object at the pointer's position from the list
//        
//        method insertBehind takes yourtype obj returns nothing
//           Inserts the object behind the pointer
//        
//        method insertBefore takes yourtype obj returns nothing
//           Inserts the object before the pointer
//        
//        method add takes yourtype obj returns nothing
//           Inserts the object at the end of the list
//
//        method addList takes yourtypeList list returns nothing
//           Appends the given list to the end of your list, old list isn't destroyed!
//
//    Special functions:
//
//        method search takes yourtype toSearch returns boolean
//           Searches the list for the given object. if true, the pointer points at this object.
//        
//        method getRandom takes nothing returns yourtype
//           Returns a random object of the list. The pointer points at this object.
//
//        method clear takes nothing returns nothing
//           Clears the list without destroying it.
//
//  Members:
//
//       readonly boolean finished
//           useful for loops
//
//       yourtype object
//           returns the object the pointer points at
//

System Code:

library List

//! textmacro CreateList takes TYPE
    private struct $TYPE$node
        $TYPE$ obj
        $TYPE$node next = 0
        $TYPE$node prev = 0
        
        method destroyNext takes nothing returns nothing
            if .next != 0 then
                call .next.destroyNext()
            endif
            call .destroy()
        endmethod
        
        static method create takes $TYPE$ obj returns $TYPE$node
            local $TYPE$node this = $TYPE$node.allocate()
            set .obj = obj
            return this
        endmethod
    endstruct

    struct $TYPE$List
        private $TYPE$node first = 0
        private $TYPE$node last = 0
        private $TYPE$node pointer = 0
        readonly integer count = 0
        
        method toFirst takes nothing returns nothing
            set .pointer = .first
        endmethod
        method toLast takes nothing returns nothing
            set .pointer = .last
        endmethod
        
        method next takes nothing returns nothing
            set .pointer = .pointer.next
        endmethod
        method prev takes nothing returns nothing
            set .pointer = .pointer.prev
        endmethod
        
        method operator finished takes nothing returns boolean
            return .pointer == 0
        endmethod
        method finish takes nothing returns nothing
            set .pointer = 0
        endmethod
        
        method operator object takes nothing returns $TYPE$
            return .pointer.obj
        endmethod
        method operator object= takes $TYPE$ obj returns nothing
            set .pointer.obj = obj
        endmethod
        
        method search takes $TYPE$ toSearch returns boolean
            set .pointer = .first
            loop
                exitwhen .pointer.obj == toSearch or .pointer == 0
                set .pointer = .pointer.next
            endloop
            if .pointer == 0 then
                return false
            endif
            return true
        endmethod
        
        method remove takes nothing returns nothing
            local $TYPE$node temp
            if .pointer != 0 then
                if .pointer == .first then
                    set .first = .pointer.next
                    call .pointer.destroy()
                    set .pointer = .first
                    set .first.prev = 0
                elseif .pointer == .last then
                    set .last = .last.prev
                    set .last.next = 0
                    call .pointer.destroy()
                    set .pointer = 0
                else
                    set .pointer.next.prev = .pointer.prev
                    set .pointer.prev.next = .pointer.next
                    set temp = .pointer
                    set .pointer = .pointer.next
                    call temp.destroy()
                endif
                set .count = .count - 1
            endif
        endmethod
        
        method insertBehind takes $TYPE$ obj returns nothing
            local $TYPE$node new
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
                set .count = .count + 1
            elseif .pointer != 0 then
                set new = $TYPE$node.create(obj)
                set new.next = .pointer.next
                set new.prev = .pointer
                set .pointer.next.prev = new
                set .pointer.next = new
                if .pointer == .last then
                    set .last = new
                endif
                set .count = .count + 1
            endif
        endmethod
        
        method insertBefore takes $TYPE$ obj returns nothing
            local $TYPE$node new
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
                set .count = .count + 1
            elseif .pointer != 0 then
                set new = $TYPE$node.create(obj)
                set new.next = .pointer                
                set new.prev = .pointer.prev
                set .pointer.prev.next = new
                set .pointer.prev = new
                if .pointer == .first then
                    set .first = new
                endif
                set .count = .count + 1
            endif
        endmethod                  
        
        method add takes $TYPE$ obj returns nothing
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
            else
                set .last.next = $TYPE$node.create(obj)
                set .last.next.prev = .last
                set .last = .last.next
            endif
            set .count = .count + 1
        endmethod

        method addList takes $TYPE$List list returns nothing
            call list.toFirst()
            loop
                exitwhen list.finished()
                call .add(list.object)
                call list.next()
            endloop
        endmethod
        
        method getRandom takes nothing returns $TYPE$
            local integer considered = 0
            local $TYPE$node pick
            call .toFirst()
            loop
                exitwhen .finished()
                set considered = considered + 1
                if (GetRandomInt(1, considered) == 1) then
                    set pick = .pointer
                endif
                call .next()
            endloop
            set .pointer = pick
            return pick.obj
        endmethod

        method clear takes nothing returns nothing
            if .count > 0 then
                call .first.destroyNext()
                set .first = 0
                set .last = 0
                set .count = 0
            endif
        endmethod
        
        method onDestroy takes nothing returns nothing
            call .clear()
        endmethod
    endstruct
//! endtextmacro
   
endlibrary

Code with documentation

//============================================================================== 
//==========================   List   ========================================== 
//============================================================================== 
// List by The_Witcher
//  It supports any type you can imagine!
//  player lists, unit lists, real lists, hashtable lists, effect lists...
//  You can even create lists for custom structs!
//
//============================================================================== 
//  What Is A List ?
//
//  The List class is a very useful general purpose list container.
//  It differs from arrays in that it provides richer functionality. 
//
//  Every list has a pointer which moves through it.
//  This pointer can be set to first, last or the next and previous node
//  you added. You can always access the object the pointer points at.
//
//==============================================================================
//   
//  Usage:
//      Initialization:
//          First initialize the list you need with the textmacro line
//              //! runtextmacro CreateList("<yourListType>")         
//          This will result in a new struct class called  <yourListType>List.
//
//          Example:         //! runtextmacro CreateList("real")
//                           will create the struct realList!
//
//      Working with a List:
//          Create your list instance using 
//              myList = <listType>List.create()
//
//          After that you can add add new objects of the type you specified to
//          your list.
//
//          You move through your list by calling myList.toFirst() or myList.toLast()
//          and then move the pointer node by node using myList.next() and myList.prev()
//
//          You can access the object stored at the pointer's
//          position by the member myList.object
//
//          If you destroy your list using myList.destroy() all nodes will be 
//          destroyed, too, so this is leakfree.
//
//      Looping through a List:
//          It is very easy to loop through a list but I will give an example how to:
//
//          myList.toFirst()
//          loop
//              exitwhen myList.finished
//              //do stuff here
//              call myList.next()
//          endloop
//
//          If you want to interrupt your loop just call myList.finish()
//
//==============================================================================  
//
//  !Note!    yourtype always refers to the type of the list you use! (real, boolean, player, any struct, ...)
// 
//  Methods:
//
//     Moving in the list:
//
//        method toFirst takes nothing returns nothing
//
//        method toLast takes nothing returns nothing
//        
//        method next takes nothing returns nothing
//    
//        method prev takes nothing returns nothing
//
//        method finish takes nothing returns nothing
//
//    Adding/Removing nodes:  
//        
//        method remove takes nothing returns nothing
//           Removes the object at the pointer's position from the list
//        
//        method insertBehind takes yourtype obj returns nothing
//           Inserts the object behind the pointer
//        
//        method insertBefore takes yourtype obj returns nothing
//           Inserts the object before the pointer
//        
//        method add takes yourtype obj returns nothing
//           Inserts the object at the end of the list
//
//        method addList takes yourtypeList list returns nothing
//           Appends the given list to the end of your list, old list isn't destroyed!
//
//    Special functions:
//
//        method search takes yourtype toSearch returns boolean
//           Searches the list for the given object. if true, the pointer points at this object.
//        
//        method getRandom takes nothing returns yourtype
//           Returns a random object of the list. The pointer points at this object.
//
//        method clear takes nothing returns nothing
//           Clears the list without destroying it.
//
//  Members:
//
//       readonly boolean finished
//           useful for loops
//
//       yourtype object
//           returns the object the pointer points at
//
//
//==============================================================================   
//========================= System Code ========================================
//==============================================================================

library List

//! textmacro CreateList takes TYPE
    private struct $TYPE$node
        $TYPE$ obj
        $TYPE$node next = 0
        $TYPE$node prev = 0
        
        method destroyNext takes nothing returns nothing
            if .next != 0 then
                call .next.destroyNext()
            endif
            call .destroy()
        endmethod
        
        static method create takes $TYPE$ obj returns $TYPE$node
            local $TYPE$node this = $TYPE$node.allocate()
            set .obj = obj
            return this
        endmethod
    endstruct

    struct $TYPE$List
        private $TYPE$node first = 0
        private $TYPE$node last = 0
        private $TYPE$node pointer = 0
        readonly integer count = 0
        
        method toFirst takes nothing returns nothing
            set .pointer = .first
        endmethod
        method toLast takes nothing returns nothing
            set .pointer = .last
        endmethod
        
        method next takes nothing returns nothing
            set .pointer = .pointer.next
        endmethod
        method prev takes nothing returns nothing
            set .pointer = .pointer.prev
        endmethod
        
        method operator finished takes nothing returns boolean
            return .pointer == 0
        endmethod
        method finish takes nothing returns nothing
            set .pointer = 0
        endmethod
        
        method operator object takes nothing returns $TYPE$
            return .pointer.obj
        endmethod
        method operator object= takes $TYPE$ obj returns nothing
            set .pointer.obj = obj
        endmethod
        
        method search takes $TYPE$ toSearch returns boolean
            set .pointer = .first
            loop
                exitwhen .pointer.obj == toSearch or .pointer == 0
                set .pointer = .pointer.next
            endloop
            if .pointer == 0 then
                return false
            endif
            return true
        endmethod
        
        method remove takes nothing returns nothing
            local $TYPE$node temp
            if .pointer != 0 then
                if .pointer == .first then
                    set .first = .pointer.next
                    call .pointer.destroy()
                    set .pointer = .first
                    set .first.prev = 0
                elseif .pointer == .last then
                    set .last = .last.prev
                    set .last.next = 0
                    call .pointer.destroy()
                    set .pointer = 0
                else
                    set .pointer.next.prev = .pointer.prev
                    set .pointer.prev.next = .pointer.next
                    set temp = .pointer
                    set .pointer = .pointer.next
                    call temp.destroy()
                endif
                set .count = .count - 1
            endif
        endmethod
        
        method insertBehind takes $TYPE$ obj returns nothing
            local $TYPE$node new
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
                set .count = .count + 1
            elseif .pointer != 0 then
                set new = $TYPE$node.create(obj)
                set new.next = .pointer.next
                set new.prev = .pointer
                set .pointer.next.prev = new
                set .pointer.next = new
                if .pointer == .last then
                    set .last = new
                endif
                set .count = .count + 1
            endif
        endmethod
        
        method insertBefore takes $TYPE$ obj returns nothing
            local $TYPE$node new
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
                set .count = .count + 1
            elseif .pointer != 0 then
                set new = $TYPE$node.create(obj)
                set new.next = .pointer                
                set new.prev = .pointer.prev
                set .pointer.prev.next = new
                set .pointer.prev = new
                if .pointer == .first then
                    set .first = new
                endif
                set .count = .count + 1
            endif
        endmethod                  
        
        method add takes $TYPE$ obj returns nothing
            if .first == 0 then
                set .first = $TYPE$node.create(obj)
                set .last = .first
            else
                set .last.next = $TYPE$node.create(obj)
                set .last.next.prev = .last
                set .last = .last.next
            endif
            set .count = .count + 1
        endmethod

        method addList takes $TYPE$List list returns nothing
            call list.toFirst()
            loop
                exitwhen list.finished()
                call .add(list.object)
                call list.next()
            endloop
        endmethod
        
        method getRandom takes nothing returns $TYPE$
            local integer considered = 0
            local $TYPE$node pick
            call .toFirst()
            loop
                exitwhen .finished()
                set considered = considered + 1
                if (GetRandomInt(1, considered) == 1) then
                    set pick = .pointer
                endif
                call .next()
            endloop
            set .pointer = pick
            return pick.obj
        endmethod

        method clear takes nothing returns nothing
            if .count > 0 then
                call .first.destroyNext()
                set .first = 0
                set .last = 0
                set .count = 0
            endif
        endmethod
        
        method onDestroy takes nothing returns nothing
            call .clear()
        endmethod
    endstruct
//! endtextmacro
   
endlibrary

 

[Dirac]

struct MyStruct extends array
    unit u
    implement LinkedList
endstruct

LinkedListModule already out-smarts this in API functionality, code efficiency, versatility and dynamism.

 

[Magtheridon96]

//! textmacro NEW_LIST takes TYPE
    struct $TYPE$List extends array
        $TYPE$ node
        implement LinkedList
    endstruct
//! endtextmacro

That should do it ^.^

 

[Nestharus]

Ultimate insert method >.>.

method insert takes thistype previous returns nothing
    set prev = previous
    set next = previous.next
    set next.prev = this
    set previous.next = this
endmethod

You could even do this for ultimate clarity

method insert takes thistype previous, thistype next returns nothing
    set this.prev = previous
    set this.next = next
    set previous.next = this
    set next.previous = this
endmethod

 

[LeP]

struct MyStruct extends array
    unit u
    implement LinkedList
endstruct

LinkedListModule already out-smarts this in API functionality, code efficiency, versatility and dynamism.

And in buzzword completion, i see .

 

[Bribe]

Buzzword completion?

 

[The_Witcher]

struct MyStruct extends array
    unit u
    implement LinkedList
endstruct

LinkedListModule already out-smarts this in API functionality, code efficiency, versatility and dynamism.

No thats wrong! linkedList itself can only handle structs!

//! textmacro NEW_LIST takes TYPE
    struct $TYPE$List extends array
        $TYPE$ node
        implement LinkedList
    endstruct
//! endtextmacro

That should do it ^.^

well i've never seen this workaround before^^ but it would do well...
there's just no getRandom functionality but advanced users may create them on their own.

 

[Dirac]

Ultimate insert method >.>.

method insert takes thistype previous returns nothing
    set prev = previous
    set next = previous.next
    set next.prev = this
    set previous.next = this
endmethod

You could even do this for ultimate clarity

method insert takes thistype previous, thistype next returns nothing
    set this.prev = previous
    set this.next = next
    set previous.next = this
    set next.previous = this
endmethod

Nes i already tested that, if you check Loc you will see that I already thought of that, but here is why i am NOT using it:

In order for that to work the node's next and prev pointers HAVE to point towards itself, you wouldn't be able to create lists of other allocators (such as unit indexes) you would only be able to insert nodes created within the same linked list.
Otherwise if the pointer points to 0 the list breaks

Here's the code i'm using on Loc

        static method join takes Loc A, Loc B returns nothing
            set A.next.prev = B.prev
            set B.prev.next = A.next
            set A.next = B
            set B.prev = A
            call A.refresh()
        endmethod

 

[Bribe]

All you need to store is integers, then the integers can be indices within a parallel array.

This doesn't have good utility for "getRandom" because it is o(n). A list is not the kind of thing to be used for random indices. You use a linear stack for that.

For LinkedList, you can either use Dirac's LinkedListModule to link to any type you want, or LinkedListStruct to do the same. For randomocity, you can use iPool, because it is o(1) for getting a random index.

I will schedule this for graveyarding.