Snippet Linked List Module

Kenny

Back for now.
Reaction score
202
On second thoughts, this should have a non-static .isList() method.

True true. So should I keep the debug messages, and just add a method that returns something like this.list != 0 or whatever? Or should I make the isList boolean non-debug?

Also can you explain what you want the [] operator to do?
 

Jesus4Lyf

Good Idea™
Reaction score
397
JASS:
method operator [] takes integer index returns thistype
    loop
        set this=this.next
        set index=index-1
        exitwhen index==0
    endloop
    return this
endmethod

I think that should do it, but that will be [1] based, not [0] based. So first element would be [1]. I'm not sure if it should be that or [0]. For some reason [1] makes more sense to me with linked lists, but I believe convention is [0].

Would allow for getRandom to just return RandomInt(1,this.count) kinda thing. As opposed to 0, this.count-1. :thup:

Also, I'm increasingly thinking using "list" to double up as "count" is a good idea. :)
 

Troll-Brain

You can change this now in User CP.
Reaction score
85
I would use it for my libraries submitted here, for the sake of don't reinventing the wheel and following a standard.
But plz make the struct members first and next "readonly", instead of "private"

getNext(), getPrev() are annoying to use.
 

Kenny

Back for now.
Reaction score
202
How about something like this:

JASS:
//------------------------------------------------------------------------------------\\
//                              Linked List Module [v2]                               \\
//                               By kenny! & Jesus4Lyf                                \\
//                              Constructed using vJASS                               \\
//                                Requires: NewGen WE                                 \\
//------------------------------------------------------------------------------------\\
//                                                                                    \\
//------------------------------------------------------------------------------------\\
//  DESCRIPTION:                                                                      \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                      \\
//    This module is a very powerful tool for structs. It enables users to create a   \\
//    linked list using a struct instance as the list itself, allowing for multiple   \\
//    lists in the one struct. It is simple to use and generates a very intuitive and \\
//    basic interface that is easy to follow and understand. A linked list can be     \\
//    used to store struct instances instead of using the 'struct stack' method, and  \\
//    can also be used to attached a list to units and so on. When used appropriately \\
//    it can give great functionality to users.                                       \\
//                                                                                    \\
//  METHODS:                                                                          \\
// ¯¯¯¯¯¯¯¯¯                                                                          \\
//    There are several methods available to you when you use this module, they       \\
//    include:                                                                        \\
//                                                                                    \\
//      Static methods:                                                               \\
//     ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                               \\
//        - .createList()     - Creates a list using a struct instance as its 'base'. \\
//                            - Returns thistype. Retuns the list itself.             \\
//                                                                                    \\
//      Non-static methods:                                                           \\
//     ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                           \\
//        - .destroyList()    - Destroys each link in the list, as well as the list.  \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .getFirst()       - Retrieves the first link in the list and returns it.  \\
//                            - Returns thistype. Returns the first link.             \\
//                                                                                    \\
//        - .getNext()        - Retrieves the next link in the list and returns it.   \\
//                            - Returns thistype. Returns the next link.              \\
//                                                                                    \\
//        - .hasNext()        - Checks to see if the current link has a next link.    \\
//                            - Returns boolean. Returns true is next link is there.  \\
//                                                                                    \\
//        - .getLast()        - Retrieves the last link in the list and returns it.   \\
//                            - Returns thistype. Returns the last link.              \\
//                                                                                    \\
//        - .getPrev()        - Retrieves the prev link in the list and returns it.   \\
//                            - Returns thistype. Returns the previous link.          \\
//                                                                                    \\
//        - .hasPrev()        - Checks to see if the current link has a next link.    \\
//                            - Returns boolean. Returns true if prev link is there.  \\
//                                                                                    \\
//        - .addToStart()     - Adds a struct instance to the start of the list.      \\
//                            - Returns thistype. Returns the parameter.              \\
//                                                                                    \\
//        - .addToEnd()       - Adds a struct instance to the end of the list.        \\
//                            - Returns thistype. Returns the parameter.              \\
//                                                                                    \\
//        - .detachFirst()    - Removes the first link from the list.                 \\
//                            - Returns thistype. Returns the first link.             \\
//                                                                                    \\
//        - .detachLast()     - Removes the last link from the list.                  \\
//                            - Returns thistype. Returns the last link.              \\
//                                                                                    \\
//        - .detachThis()     - Removes the current link from the list.               \\
//                            - Returns thistype. Returns the current link.           \\
//                                                                                    \\
//        - .destroyFirst()   - Removes the first link from the list and calls the    \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .destroyLast()    - Removes the last link from the list and calls the     \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .destroyThis()    - Removes the current link from the list and call the   \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//  USAGE/EXAMPLES:                                                                   \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                   \\
//    To use this module within a struct you must implement it using the following:   \\
//                                                                                    \\
//      private struct Data                                                           \\
//          implement Linked_List                                                     \\
//                                                                                    \\
//          Do stuff here using the module.                                           \\
//      endstruct                                                                     \\
//                                                                                    \\
//    It is easiest to implement it right under struct declaration.                   \\
//                                                                                    \\
//    There are only two methods available which use parameters. Usage for these two  \\
//    methods are as follows:                                                         \\
//                                                                                    \\
//      call .addToStart(thistype value)                                              \\
//      call .addToEnd(thistype value)                                                \\
//                                                                                    \\
//    The above take one parameter. The parameter must be a thistype value. Meaning   \\
//    it takes a struct instance as the parameter.                                    \\   
//                                                                                    \\
//  PROS & CONS:                                                                      \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                      \\
//    As this module is just a simplification of struct stack syntax, there are not   \\
//    many negative points for it. However, just for the sake of it:                  \\
//                                                                                    \\
//      Pros:                                                                         \\
//     ¯¯¯¯¯¯                                                                         \\
//        - Simplifies syntax a fair bit. Makes it easier to read.                    \\
//        - Allows for multiple linked lists within a single struct, generating       \\
//          multiple storage components.                                              \\
//        - Reduces time spent developing spells/scripts and reduces lines.           \\
//        - There is also a -possible- efficiency gain over the normal struct stack.  \\
//          But this I am not sure of.                                                \\
//                                                                                    \\
//      Cons:                                                                         \\
//     ¯¯¯¯¯¯                                                                         \\
//        - A single node can only exist in one list at a time.                       \\
//        - onDestroy gets called for list nodes.                                     \\
//                                                                                    \\
//  IMPORTING:                                                                        \\
// ¯¯¯¯¯¯¯¯¯¯¯                                                                        \\
//    Simply create a new trigger, name it LinkedList or something along those lines. \\
//    Then convert it to custom text, and paste this in its place and save. Done.     \\
//                                                                                    \\
//  THANKS/CREDITS:                                                                   \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                   \\
//    - Jesus4Lyf - For basically re-inventing the module to make it far more useful  \\
//                  and dynamic. Also for helping me understand linked lists better   \\
//                  and helping to develop the script further. Major props to him.    \\
//                                                                                    \\
//------------------------------------------------------------------------------------\\

library Linked
    
    public module List
        
        private thistype nextNode = 0      // Next node link.
        private thistype prevNode = 0      // Prev node link.
        private thistype listNode = 0      // Which listNode this node belongs to.
        private boolean  aList    = false  // For user safety.
                                   
        //------------------------------------------------------\\  
        // Create the linked list.                                  
        static method createList takes nothing returns thistype
            local thistype this = .allocate()
            
            set this.aList = true
            
            return this // return struct created as a listNode
        endmethod
        
        //------------------------------------------------------\\
        // Destroy the linked list.
        method destroyList takes nothing returns nothing
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (destroyList): Struct instance is not a listNode.")
                return
            endif
            
            loop
                call this.destroy()
                set this = this.nextNode
                exitwhen this == 0
            endloop
        endmethod
        
        //------------------------------------------------------\\
        // [] method operator.
        method operator[] takes integer index returns thistype
            loop
                set this=this.next
                set index=index-1
                exitwhen index==0
            endloop
            return this
        endmethod
        
        //------------------------------------------------------\\
        // Method operators for simpler interface.
        method operator first takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method operator next takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method operator hasNext takes nothing returns boolean
            return this.nextNode != 0
        endmethod
        
        method operator last takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method operator prev takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method operator hasPrev takes nothing returns boolean
            return this.prevNode != 0
        endmethod
        
        method operator isList takes nothing returns boolean    
            return this.aList
        endmethod
        
        //------------------------------------------------------\\
        // Deprecated methods for backwards compatability.
        method getFirst takes nothing returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (getFirst): Struct instance is not a listNode.")
                return 0
            endif
            return this.nextNode // return this.first
        endmethod
        
        method getNext takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method hasNext takes nothing returns boolean
            return this.nextNode != 0
        endmethod
        
        method getLast takes nothing returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (getLast): Struct instance is not a listNode.")
                return 0
            endif
            return this.prevNode // return this.last
        endmethod
        
        method getPrev takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method hasPrev takes nothing returns boolean
            return this.prevNode != 0
        endmethod
        
        //------------------------------------------------------\\
        // Attach methods.
        method addToStart takes thistype toAdd returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (addToStart): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.nextNode.prevNode = toAdd  // set this.first.prevNode = toAdd
            set toAdd.nextNode = this.nextNode  // set toAdd.prevNode = this.last
            set this.nextNode = toAdd       // set this.last = toAdd
            
            if this.prevNode == 0 then      // if this.last == 0 then
                set this.prevNode = toAdd   // set this.last = toAdd
            endif
            
            set toAdd.listNode = this
            
            return toAdd                // return toAdd for simplicity
        endmethod
    
        method addToEnd takes thistype toAdd returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (addToEnd): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.prevNode.nextNode = toAdd  // set this.last.nextNode = toAdd
            set toAdd.prevNode = this.prevNode  // set toAdd.prevNode = this.last
            set this.prevNode = toAdd       // set this.last = toAdd
            
            if this.nextNode == 0 then      // if this.first == 0 then
                set this.nextNode = toAdd   // set this.first = toAdd
            endif
            
            set toAdd.listNode = this
            
            return toAdd                // return toAdd for simplicity
        endmethod
        
        //------------------------------------------------------\\
        // Detach methods.
        method detachFirst takes nothing returns thistype
            local thistype first = this.nextNode // local thistype first = this.first
            
            if not this.isList then
                debug call BJDebugMsg("Lniked List Module (detachFirst): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.nextNode = this.nextNode.nextNode   // set this.first = this.first.nextNode
            set this.nextNode.prevNode = 0           // set this.first.prevNode = 0
            
            set first.nextNode = 0
            set first.prevNode = 0
            set first.listNode = 0
            
            if this.prevNode == first then       // if this.last == first then
                set this.prevNode = 0            // set this.last = 0
            endif
            
            return first
        endmethod
        
        method detachLast takes nothing returns thistype
            local thistype last = this.prevNode // local thistype last = this.last
            
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (detachLast): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.prevNode = this.prevNode.prevNode  // set this.last = this.last.prevNode
            set this.prevNode.nextNode = 0          // set this.last.nextNode = 0
            
            set last.nextNode = 0
            set last.prevNode = 0
            set last.listNode = 0
            
            if this.nextNode == last then       // if this.first == last then
                set this.nextNode = 0           // set this.first = 0
            endif
            
            return last
        endmethod
        
        method detachThis takes nothing returns thistype
            if this.listNode == 0 then
                debug call BJDebugMsg("Linked List Module (detachThis): Struct instance is not a attached to a listNode.")
                return 0
            endif
            
            if this.listNode.nextNode == this then      // if this.listNode.first == this then
                call this.listNode.detachFirst()
            elseif this.listNode.prevNode == this then  // if this.listNode.last == this then
                call this.listNode.detachLast()
            else
                set this.nextNode.prevNode = this.prevNode
                set this.prevNode.nextNode = this.nextNode
                set this.nextNode = 0
                set this.prevNode = 0
                set this.listNode = 0
            endif
            
            return this
        endmethod
        
        //------------------------------------------------------\\
        // Destroy methods.
        method destroyFirst takes nothing returns nothing
            call this.detachFirst().destroy()    // detach and destroy first link.
        endmethod
        
        method destroyLast takes nothing returns nothing
            call this.detachLast().destroy()     // detach and destroy last link.
        endmethod
        
        method destroyThis takes nothing returns nothing
            call this.detachThis().destroy()  // detach and destroy current link.
        endmethod
        
    endmodule
    
endlibrary


Made the interface a bit simpler, added the [] method operator, and made a isList boolean so that onDestroy methods can discern between lists and nodes, and rewrote the debug messages so that if the user does something wrong in non-debug mode, the methods wont continue and screw things up.

I'm still thinking about adding a 'count' integer. I might update this after that.
 

Troll-Brain

You can change this now in User CP.
Reaction score
85
It's nicer, but i don't see what's wrong with readonly, at least it will save you some extra lines of code, even if the result is the same when the map is saved on debug mode off.

A .count could be indeed useful, in fact i need it, i could add it myself ofc, but it will be better if it is incorporated inside the module.
 

Kenny

Back for now.
Reaction score
202
It's nicer, but i don't see what's wrong with readonly

I just don't like the fact that if I use readonly, there is only next and first members, and no first, last, hasNext and hasPrev...

That means I will probably use method operators for 4 out of the 6 things, so I decided to use operators for all 6.

It doesn't make a difference, I just think it looks better. :D

I will probably add .count as soon as I can use the editor.
 

Troll-Brain

You can change this now in User CP.
Reaction score
85
It doesn't make a difference, I just think it looks better. :D
Zomg you're so not Azlier, it would save the world, imagine you will save some extra function calls on debug mode on, are you a fool, DO IT NOW ! :D

I will probably add .count as soon as I can use the editor.
Ok, so i will use it myself now so, for my code.
 

Kenny

Back for now.
Reaction score
202
Okay, I got to work on it some more, but not in the editor, so I'm not sure if it compiles or not.

JASS:
//------------------------------------------------------------------------------------\\
//                              Linked List Module [v2]                               \\
//                               By kenny! & Jesus4Lyf                                \\
//                              Constructed using vJASS                               \\
//                                Requires: NewGen WE                                 \\
//------------------------------------------------------------------------------------\\
//                                                                                    \\
//------------------------------------------------------------------------------------\\
//  DESCRIPTION:                                                                      \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                      \\
//    This module is a very powerful tool for structs. It enables users to create a   \\
//    linked list using a struct instance as the list itself, allowing for multiple   \\
//    lists in the one struct. It is simple to use and generates a very intuitive and \\
//    basic interface that is easy to follow and understand. A linked list can be     \\
//    used to store struct instances instead of using the 'struct stack' method, and  \\
//    can also be used to attached a list to units and so on. When used appropriately \\
//    it can give great functionality to users.                                       \\
//                                                                                    \\
//  METHODS:                                                                          \\
// ¯¯¯¯¯¯¯¯¯                                                                          \\
//    There are several methods available to you when you use this module, they       \\
//    include:                                                                        \\
//                                                                                    \\
//      Static methods:                                                               \\
//     ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                               \\
//        - .createList()     - Creates a list using a struct instance as its 'base'. \\
//                            - Returns thistype. Retuns the list itself.             \\
//                                                                                    \\
//      Non-static methods:                                                           \\
//     ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                           \\
//        - .destroyList()    - Destroys each link in the list, as well as the list.  \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .getFirst()       - Retrieves the first link in the list and returns it.  \\
//                            - Returns thistype. Returns the first link.             \\
//                                                                                    \\
//        - .getNext()        - Retrieves the next link in the list and returns it.   \\
//                            - Returns thistype. Returns the next link.              \\
//                                                                                    \\
//        - .hasNext()        - Checks to see if the current link has a next link.    \\
//                            - Returns boolean. Returns true is next link is there.  \\
//                                                                                    \\
//        - .getLast()        - Retrieves the last link in the list and returns it.   \\
//                            - Returns thistype. Returns the last link.              \\
//                                                                                    \\
//        - .getPrev()        - Retrieves the prev link in the list and returns it.   \\
//                            - Returns thistype. Returns the previous link.          \\
//                                                                                    \\
//        - .hasPrev()        - Checks to see if the current link has a next link.    \\
//                            - Returns boolean. Returns true if prev link is there.  \\
//                                                                                    \\
//        - .addToStart()     - Adds a struct instance to the start of the list.      \\
//                            - Returns thistype. Returns the parameter.              \\
//                                                                                    \\
//        - .addToEnd()       - Adds a struct instance to the end of the list.        \\
//                            - Returns thistype. Returns the parameter.              \\
//                                                                                    \\
//        - .detachFirst()    - Removes the first link from the list.                 \\
//                            - Returns thistype. Returns the first link.             \\
//                                                                                    \\
//        - .detachLast()     - Removes the last link from the list.                  \\
//                            - Returns thistype. Returns the last link.              \\
//                                                                                    \\
//        - .detachThis()     - Removes the current link from the list.               \\
//                            - Returns thistype. Returns the current link.           \\
//                                                                                    \\
//        - .destroyFirst()   - Removes the first link from the list and calls the    \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .destroyLast()    - Removes the last link from the list and calls the     \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//        - .destroyThis()    - Removes the current link from the list and call the   \\
//                              .destroy() method.                                    \\
//                            - Returns nothing.                                      \\
//                                                                                    \\
//  USAGE/EXAMPLES:                                                                   \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                   \\
//    To use this module within a struct you must implement it using the following:   \\
//                                                                                    \\
//      private struct Data                                                           \\
//          implement Linked_List                                                     \\
//                                                                                    \\
//          Do stuff here using the module.                                           \\
//      endstruct                                                                     \\
//                                                                                    \\
//    It is easiest to implement it right under struct declaration.                   \\
//                                                                                    \\
//    There are only two methods available which use parameters. Usage for these two  \\
//    methods are as follows:                                                         \\
//                                                                                    \\
//      call .addToStart(thistype value)                                              \\
//      call .addToEnd(thistype value)                                                \\
//                                                                                    \\
//    The above take one parameter. The parameter must be a thistype value. Meaning   \\
//    it takes a struct instance as the parameter.                                    \\   
//                                                                                    \\
//  PROS & CONS:                                                                      \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                      \\
//    As this module is just a simplification of struct stack syntax, there are not   \\
//    many negative points for it. However, just for the sake of it:                  \\
//                                                                                    \\
//      Pros:                                                                         \\
//     ¯¯¯¯¯¯                                                                         \\
//        - Simplifies syntax a fair bit. Makes it easier to read.                    \\
//        - Allows for multiple linked lists within a single struct, generating       \\
//          multiple storage components.                                              \\
//        - Reduces time spent developing spells/scripts and reduces lines.           \\
//        - There is also a -possible- efficiency gain over the normal struct stack.  \\
//          But this I am not sure of.                                                \\
//                                                                                    \\
//      Cons:                                                                         \\
//     ¯¯¯¯¯¯                                                                         \\
//        - A single node can only exist in one list at a time.                       \\
//        - onDestroy gets called for list nodes.                                     \\
//                                                                                    \\
//  IMPORTING:                                                                        \\
// ¯¯¯¯¯¯¯¯¯¯¯                                                                        \\
//    Simply create a new trigger, name it LinkedList or something along those lines. \\
//    Then convert it to custom text, and paste this in its place and save. Done.     \\
//                                                                                    \\
//  THANKS/CREDITS:                                                                   \\
// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯                                                                   \\
//    - Jesus4Lyf - For basically re-inventing the module to make it far more useful  \\
//                  and dynamic. Also for helping me understand linked lists better   \\
//                  and helping to develop the script further. Major props to him.    \\
//                                                                                    \\
//------------------------------------------------------------------------------------\\

library Linked
    
    public module List
        
        private thistype nextNode = 0      // Next node link.
        private thistype prevNode = 0      // Prev node link.
        private thistype listNode = 0      // Which listNode this node belongs to.
        private boolean  aList    = false  // For user safety.
                                   
        //------------------------------------------------------\\  
        // Create the linked list.                                  
        static method createList takes nothing returns thistype
            local thistype this = thistype.allocate()
            
            set this.aList = true
            
            return this // return struct created as a listNode
        endmethod
        
        //------------------------------------------------------\\
        // Destroy the linked list.
        method destroyList takes nothing returns nothing
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (destroyList): Struct instance is not a listNode.")
                return
            endif
            
            loop
                call this.destroy()
                set this = this.nextNode
                exitwhen this == 0
            endloop
        endmethod
        
        //------------------------------------------------------\\
        // [] method operator.
        method operator[] takes integer index returns thistype
            loop
                set this=this.next
                set index=index-1
                exitwhen index==0
            endloop
            return this
        endmethod
        
        //------------------------------------------------------\\
        // Method operators for simpler interface.
        method operator first takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method operator next takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method operator hasNext takes nothing returns boolean
            return this.nextNode != 0
        endmethod
        
        method operator last takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method operator prev takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method operator hasPrev takes nothing returns boolean
            return this.prevNode != 0
        endmethod
        
        method operator isList takes nothing returns boolean    
            return this.aList
        endmethod
        
        method operator count takes nothing returns integer
            return integer(this.listNode)
        endmethod
        
        //------------------------------------------------------\\
        // Deprecated methods for backwards compatability.
        method getFirst takes nothing returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (getFirst): Struct instance is not a listNode.")
                return 0
            endif
            return this.nextNode // return this.first
        endmethod
        
        method getNext takes nothing returns thistype
            return this.nextNode
        endmethod
        
        method hasNext takes nothing returns boolean
            return this.nextNode != 0
        endmethod
        
        method getLast takes nothing returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (getLast): Struct instance is not a listNode.")
                return 0
            endif
            return this.prevNode // return this.last
        endmethod
        
        method getPrev takes nothing returns thistype
            return this.prevNode
        endmethod
        
        method hasPrev takes nothing returns boolean
            return this.prevNode != 0
        endmethod
        
        method getList takes nothing returns boolean
            return this.aList
        endmethod
        
        method getCount takes nothing returns integer
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (getCount): Struct instance is not a listNode.")
                return 0
            endif
            return integer(this.listNode)
        endmethod
        
        //------------------------------------------------------\\
        // Attach methods.
        method addToStart takes thistype toAdd returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (addToStart): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.nextNode.prevNode = toAdd  // set this.first.prevNode = toAdd
            set toAdd.nextNode = this.nextNode  // set toAdd.prevNode = this.last
            set this.nextNode = toAdd       // set this.last = toAdd
            
            if this.prevNode == 0 then      // if this.last == 0 then
                set this.prevNode = toAdd   // set this.last = toAdd
            endif
            
            set toAdd.listNode = this
            set integer(this.listNode) = integer(this.listNode) + 1
            
            return toAdd                // return toAdd for simplicity
        endmethod
    
        method addToEnd takes thistype toAdd returns thistype
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (addToEnd): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.prevNode.nextNode = toAdd  // set this.last.nextNode = toAdd
            set toAdd.prevNode = this.prevNode  // set toAdd.prevNode = this.last
            set this.prevNode = toAdd       // set this.last = toAdd
            
            if this.nextNode == 0 then      // if this.first == 0 then
                set this.nextNode = toAdd   // set this.first = toAdd
            endif
            
            set toAdd.listNode = this
            set integer(this.listNode) = integer(this.listNode) + 1
            
            return toAdd                // return toAdd for simplicity
        endmethod
        
        //------------------------------------------------------\\
        // Detach methods.
        method detachFirst takes nothing returns thistype
            local thistype first = this.nextNode // local thistype first = this.first
            
            if not this.isList then
                debug call BJDebugMsg("Lniked List Module (detachFirst): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.nextNode = this.nextNode.nextNode   // set this.first = this.first.nextNode
            set this.nextNode.prevNode = 0           // set this.first.prevNode = 0
            
            set first.nextNode = 0
            set first.prevNode = 0
            set first.listNode = 0
            
            if this.prevNode == first then       // if this.last == first then
                set this.prevNode = 0            // set this.last = 0
            endif
            
            set integer(this.listNode) = integer(this.listNode) - 1
            
            return first
        endmethod
        
        method detachLast takes nothing returns thistype
            local thistype last = this.prevNode // local thistype last = this.last
            
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (detachLast): Struct instance is not a listNode.")
                return 0
            endif
            
            set this.prevNode = this.prevNode.prevNode  // set this.last = this.last.prevNode
            set this.prevNode.nextNode = 0          // set this.last.nextNode = 0
            
            set last.nextNode = 0
            set last.prevNode = 0
            set last.listNode = 0
            
            if this.nextNode == last then       // if this.first == last then
                set this.nextNode = 0           // set this.first = 0
            endif
            
            set integer(this.listNode) = integer(this.listNode) - 1
            
            return last
        endmethod
        
        method detachThis takes nothing returns thistype
            if this.listNode == 0 then
                debug call BJDebugMsg("Linked List Module (detachThis): Struct instance is not a attached to a listNode.")
                return 0
            endif
            
            if this.listNode.nextNode == this then      // if this.listNode.first == this then
                call this.listNode.detachFirst()
            elseif this.listNode.prevNode == this then  // if this.listNode.last == this then
                call this.listNode.detachLast()
            else
                set this.nextNode.prevNode = this.prevNode
                set this.prevNode.nextNode = this.nextNode
                set this.nextNode = 0
                set this.prevNode = 0
                set this.listNode = 0
                
                set integer(this.listNode) = integer(this.listNode) - 1
            endif
            
            return this
        endmethod
        
        //------------------------------------------------------\\
        // Destroy methods.
        method destroyFirst takes nothing returns nothing
            call this.detachFirst().destroy()    // detach and destroy first link.
        endmethod
        
        method destroyLast takes nothing returns nothing
            call this.detachLast().destroy()     // detach and destroy last link.
        endmethod
        
        method destroyThis takes nothing returns nothing
            call this.detachThis().destroy()  // detach and destroy current link.
        endmethod
        
    endmodule
    
endlibrary


Includes .count now.

EDIT:

I was thinking about how the onDestroy method gets called for list nodes and how to fix it, I came up with this:

JASS:
...
        method destroyList takes nothing returns nothing
            if not this.isList then
                debug call BJDebugMsg("Linked List Module (destroyList): Struct instance is not a listNode.")
                return
            endif
            
            loop
                if not this.isList then
                    call this.destroy()
                else
                    call this.deallocate()
                endif
                set this = this.nextNode
                exitwhen this == 0
            endloop
        endmethod
...


Is that the best way to go about this?

(Hopes for Jesus4Lyf to appear)

My fail work in progress:

JASS:
library ListModule
    
    module LinkedList
    
        private thistype nextx = 0      // Next node link. Doubles as head for a list.
        private thistype prevx = 0      // Prev node link. Doubles as tail for a list.
        private thistype listx = 0      // Which list this node belongs to. Doubles as size for a list.
        private boolean  aList = false  // For user safety.
        
        static method createList takes nothing returns thistype
            local thistype this = thistype.allocate()
            
            set this.aList = true
            set this.nextx = this
            set this.prevx = this
            set this.nextx.prevx = 0
            set this.prevx.nextx = 0
            
            return this
        endmethod
        
        method destroyList takes nothing returns nothing
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (destroyList): Struct instance is not a list.")
                debug return
            debug endif
            
            loop
                if this.aList then
                    call this.deallocate()
                else
                    call this.destroy()
                endif
                set this = this.nextx
                exitwhen this == 0
            endloop
        endmethod
        
        method searchList takes thistype toSearch returns thistype
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (searchList): Struct instance is not a list.")
                debug return 0
            debug endif
            
            loop
                if this == toSearch then
                    return this
                endif
                set this = this.nextx
                exitwhen this == 0
            endloop
            
            return 0
        endmethod

        method operator[] takes integer index returns thistype
            loop
                set this = this.nextx
                set index = index - 1
                exitwhen index == 0
            endloop
            return this
        endmethod

        method operator head takes nothing returns thistype
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (head): Struct instance is not a list.")
                debug return 0
            debug endif
            return this.nextx
        endmethod
        
        method operator next takes nothing returns thistype
            return this.nextx
        endmethod
        
        method operator hasNext takes nothing returns boolean
            return this.nextx != 0
        endmethod
        
        method operator tail takes nothing returns thistype
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (last): Struct instance is not a list.")
                debug return 0
            debug endif
            return this.prevx
        endmethod
        
        method operator prev takes nothing returns thistype
            return this.prevx
        endmethod
        
        method operator hasPrev takes nothing returns boolean
            return this.prevx != 0
        endmethod
        
        method operator size takes nothing returns integer
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (size/empty): Struct instance is not a list.")
                debug return 0
            debug endif
            return integer(this.listx)
        endmethod
        
        method operator empty takes nothing returns boolean
            return this.size == 0
        endmethod
        
        method operator isList takes nothing returns boolean    
            return this.aList
        endmethod
        
        method addToStart takes thistype toAdd returns thistype
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (addToStart): Struct instance is not a list.")
                debug return 0
            debug endif
            
            set this.nextx.prevx = toAdd
            set toAdd.nextx = this.nextx
            set this.nextx  = toAdd
            set toAdd.prevx = this
            
            set toAdd.listx = this
            set this.listx  = integer(this.listx) + 1
            
            return toAdd
        endmethod
    
        method addToEnd takes thistype toAdd returns thistype
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (addToEnd): Struct instance is not a list.")
                debug return 0
            debug endif
            
            set this.prevx.nextx = toAdd
            set toAdd.prevx = this.prevx
            set this.prevx  = toAdd
            set toAdd.nextx = this
            
            set toAdd.listx = this
            set this.listx  = integer(this.listx) + 1
            
            return toAdd
        endmethod
        
        method detachHead takes nothing returns thistype
            local thistype first = this.nextx
            
            debug if not this.aList then
                debug call BJDebugMsg("Lniked List Module (detachHead): Struct instance is not a list.")
                debug return 0
            debug endif
            
            set this.nextx = this.nextx.nextx
            set this.nextx.prevx = this
            set this.listx = integer(this.listx) - 1
            
            return first
        endmethod
        
        method detachTail takes nothing returns thistype
            local thistype last = this.prevx
            
            debug if not this.aList then
                debug call BJDebugMsg("Linked List Module (detachLast): Struct instance is not a list.")
                debug return 0
            debug endif
            
            set this.prevx = this.prevx.prevx
            set this.prevx.nextx = this
            set this.listx = integer(this.listx) - 1
            
            return last
        endmethod
        
        method detachThis takes nothing returns thistype
            debug if this.listx == 0 then
                debug call BJDebugMsg("Linked List Module (detachThis): Struct instance is not attached to a list.")
                debug return 0
            debug endif
            
            if this.listx.nextx == this then
                call this.listx.detachHead()
            elseif this.listx.prevx == this then
                call this.listx.detachTail()
            else
                set this.prevx.nextx = this.nextx
                set this.nextx.prevx = this.prevx
                set this.listx.listx = integer(this.listx.listx) - 1
            endif
            
            return this
        endmethod
        
        method destroyHead takes nothing returns nothing
            call this.detachHead().destroy()
        endmethod
        
        method destroyTail takes nothing returns nothing
            call this.detachTail().destroy()
        endmethod
        
        method destroyThis takes nothing returns nothing
            call this.detachThis().destroy()
        endmethod
        
    endmodule
    
endlibrary


.addToStart() + this.head + this.next seems to work just fine.

.addToEnd() + this.tail + this.prev does not.

I'm not sure how to make them both work..
 

Tom_Kazansky

--- wraith it ! ---
Reaction score
157
errm..., Kenny, I have a question: can I have many instances of the list ? (many lists)

i.e: I have a struct for buff, one unit can have many buffs
-> many instance of the struct
-> I have to attach these struct instance to the unit
-> so I attach to the unit one instance of the struct and call .createList() to make it "a list".
-> for the other instances, I will .addToStart(..) (or .addToEnd(..) ) so they are linked together

is that ok ?

I currently use Hashtable to attach the struct instances to unit but it would be slow, right ?

sorry for asking too much :|
 

Kenny

Back for now.
Reaction score
202
Actually, from the sounds of it, that should work fine. :)

Basically the only drawback of the newest implementation of this module is that one link cannot exist in two separate lists at the same time.

However, for buffs that shouldn't be a problem, as the same buff instance cannot be on two units at once.

And hashtables would be fine for something like this (maybe use Table to decrease the total amount of hashtables used in your map).

If you want it to be faster, I suggest unit indexing (AIDS or AutoIndex).
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top