Help Learning Linked Lists

[Kenny]

So a while back, we started to see a lot of "black magic" pop up (I'm looking at you Jesus4Lyf ), and i started wondering if it would be worth learning linked lists, as I am a ridiculously slow learning when it comes to new concepts.

Then after making a few spells and stuff, I realised that I am using the struct stacks a lot, and maybe it would be helpful to implement a linked list that can be used to keep track of the currently used structs to reduce complexity a little, and by complexity I mean making it easier to write and stuff. I'm not sure whether its faster or not, but I would assume they would be around the same.

So I went a-learnin' and basically I've come up with this:

library LLM

    //! textmacro LIST
    
        integer next  = 0
        integer prev  = 0

        static integer first = 0
        static integer last  = 0
        static integer max   = 0
        
        method linkNode takes nothing returns boolean
            if .first == 0 then
                set .first = this
            else
                set .prev = .last
                set .prev.next = this
            endif
            
            set .last = this
            set .max = .max + 1
                
            return true
        endmethod
        
        method unlinkNode takes nothing returns boolean
            if .first == this then
                set .first = .next
            endif
            
            if .last == this then
                set .last = .prev
            endif
            
            set .prev.next = .next
            set .next.prev = .prev
            set .max = .max - 1
            
            return true
        endmethod
        
        method getNext takes nothing returns integer
            return .next
        endmethod
        
        method getPrev takes nothing returns integer
            return .prev
        endmethod
        
        method getMax takes nothing returns integer
            return .max
        endmethod
        
    //! endtextmacro
    
endlibrary

Okay so I'm not even sure if it works as I'm not on my home computer, so feedback is good. If it doesn't work I don't want it done for me (at first ), maybe just some hints.

What I want to do in the future:

- Add a boolean variable to see whether or not a struct is already assigned to a node.
- Anything that anyone can point out.

Thanks in advance.

EDIT:

Oh and the reason I am using textmacro and integer members is because I don't have the latest Jasshelper, I want to be able to test it when i get on my home computer. I will probably update it when I read the jasshelper manual a bit more.

 

[wraithseeker]

http://www.wc3c.net/showthread.php?t=103604

Maybe you could take a look at this for some reference.

 

[Kenny]

Maybe you could take a look at this for some reference.

Thanks, but for now, I'd rather not look at any other peoples systems involving linked lists, as I think I absorb what needs to be learnt better that way.

Anywho, I read through the JassHelper manual and decided to make it use thistype as it would be so much better. This is what I have:

library List

    module List
    
        private thistype next = 0
        private thistype prev = 0
        private boolean  link = false

        private static thistype first = 0
        private static thistype last  = 0
        private static thistype size  = 0
        
        method insertNode takes nothing returns boolean
            if .link == false then
                set .link = true
                
                if .first == 0 then
                    set .first = this
                else
                    set .prev = .last
                    set .prev.next = this
                endif
                
                set .last = this
                set .size = .size + 1
                
                return true
            endif
                
            return false
        endmethod
        
        method removeNode takes nothing returns boolean
            if .link == true then
                set .link = false
                
                if .first == this then
                    set .first = .next
                endif
                
                if .last == this then
                    set .last = .prev
                endif
                
                set .prev.next = .next
                set .next.prev = .prev
                set .size = .size - 1
                
                return true
            endif
            
            return false
        endmethod
        
        //! textmacro Get takes STATIC, NAME, TYPE, VALUE
        $STATIC$ method $NAME$ takes nothing returns $TYPE$
            return .$VALUE$
        endmethod
        //! endtextmacro

        //! runtextmacro Get("","getNext","thistype","next")
        //! runtextmacro Get("","getPrev","thistype","prev")
        //! runtextmacro Get("","isLink","boolean","link")
        //! runtextmacro Get(" static","getFirst","thistype","first")
        //! runtextmacro Get(" static","getLast","thistype","last")
        //! runtextmacro Get(" static","getSize","thistype","size")
        
    endmodule

endlibrary

Questions:

- Do I need to be able to release the list? If so, does that mean I need to unlink each node before i destroy them?
- Do my methods for getFirst, getLast and getSize need to be static? (I changed the textmacro to accompany all methods).
- Kind of ties in with point one. I was thinking about adding flushList and destroyList functionality. Is this possible? (This is where I'm stumped i think).
- Anything else I should add?

 

[Tom Jones]

Nope.

Nope.

struct ...
      list l

      method ...
          local list l = .l.first

          loop
              exitwhen l == 0
              ...
              set l = l.next
          endloop
      endmethod
endstruct

A) Unlink all listmembers. B) Add a onDestroy method.

 

[Kenny]

Sorry to disappoint, but:

I am a ridiculously slow learning when it comes to new concepts

Anywho, I get most of what your saying, just still a little confused.

I think I'm going to keep my various method textmacro-majig as is until someone shows me why it shouldn't be like that.

I am trying to figure out a way to save a flush method and a destroy method. What happens if for some reason, a node gets added while im flushing or destroying, what can i do to counter it?

Also by onDestroy method, did you mean a destroyList method or just the plain old onDestroy? If so, what would be its purpose?

EDIT:

Oh and I was finally able to test it and it worked. Hell yeah, first attempt at something to do with linked lists and it worked0. Even though it is pretty basic.


EDIT 2:

Been working on it a bit more. Only really found flushing the list necessary (As opposed to removing and destroying nodes). Someone is welcome to tell me otherwise. Here's what I have now:

library Linked

    public module List
    
        static timer Timer = null           // Timer for personal use.
        
        private thistype next = 0           // Next node link.
        private thistype prev = 0           // Prev node link.
        private boolean  link = false       // If link is added to list.

        private static thistype head = 0    // Head == first node in list.
        private static thistype last = 0    // Last == last node added to list.
        private static integer  size = 0    // Size == How many nodes are currently in the list.
        
        // Insert a node into the list:
        method insertNode takes nothing returns boolean
            if .link == false then
                set .link = true
                
                if .head == 0 then
                    set .head = this
                else
                    set .prev = .last
                    set .prev.next = this
                endif
                
                set .last = this
                set .size = .size + 1
                
                return true
            debug else
                debug call BJDebugMsg("Error: Attempt to insert previously existing node into list.")
            endif
                
            return false
        endmethod
        
        // Remove a node from the list:
        method removeNode takes nothing returns boolean
            if .link == true then
                set .link = false
                
                if .head == this then
                    set .head = .next
                endif
                
                if .last == this then
                    set .last = .prev
                endif
                
                set .prev.next = .next
                set .next.prev = .prev
                set .size = .size - 1
                
                return true
            debug else
                debug call BJDebugMsg("Error: Attempt to remove currently inexistant node from list.")
            endif
            
            return false
        endmethod
        
        // BJ function. Two for one:
        method deleteNode takes nothing returns nothing
            if .removeNode() then
                call .destroy()
            endif
        endmethod
        
        // Flush all nodes in the list:
        static method flushList takes nothing returns nothing
            local thistype d = .head
            
            loop
                exitwhen d == 0
                call d.removeNode()
                set d = d.next
            endloop
        endmethod
        
        // For personal timer:
        static method listInit takes nothing returns nothing
            set .Timer = CreateTimer()
        endmethod
        
        // Creates all the small useful functions needed:
        //! textmacro GetFunctions takes STATIC, NAME, TYPE, VALUE
        $STATIC$ method $NAME$ takes nothing returns $TYPE$
            return .$VALUE$
        endmethod
        //! endtextmacro

        //! runtextmacro GetFunctions("","getNext","thistype","next")
        //! runtextmacro GetFunctions("","getPrev","thistype","prev")
        //! runtextmacro GetFunctions("","isLink","boolean","link")
        //! runtextmacro GetFunctions(" static","getFirst","thistype","head")
        //! runtextmacro GetFunctions(" static","getLast","thistype","last")
        //! runtextmacro GetFunctions(" static","getSize","thistype","size")
        
    endmodule

endlibrary

Everything seems to work okay. Just wondering what input some more experience members might have.

The timer in there is just because I found myself needing a timer whenever I needed this module, and it made it easier. I know it doesn't really belong, but oh well.

The question still remains: What if I somehow add a node to the list, while it is currently flushing or something? Should I find a way to prevent this? I'm currently trying to think of a way, but nothing significant has popped into my head.

 

[Kenny]

Bump. Last question in my last post still remains. And is everything else okay with it? Or have I missed something important?

 

[Builder Bob]

As there's nothing in your flushing method that can run any other code throughout the process, it will be impossible to insert a node while it's flushing. As soon as the flushing starts, it will finish before any other code can run.

Or am I missing anything?

 

[Kenny]

Ohh fair enough then, i just thought there may be a situation where they can both somehow be run simultaniously, or insertNode() to be used just when flushList() is ending, so a new node gets flushed instantly.

But thats unlikely, lol.

 

[Builder Bob]

Well, war3 cannot run multiple threads of code simultaneously.

When an event triggers or a timer expires, they will actually wait for any and all other already running code to end before running.

 

[Kenny]

Aiight, cool. Thanks for the clarification. I thought of a way to fix it using a boolean, but i guess its not necessary anymore.

Can you see any problems with the rest of the script?

Everything seems to work okay on my end, and it shaved off lke 32 lines from one of my spells, and makes it so much easier to code, I was surprised by how useful it is.

 

[Builder Bob]

Can you see any problems with the rest of the script?

Everything seems to work okay on my end, and it shaved off lke 32 lines from one of my spells, and makes it so much easier to code, I was surprised by how useful it is.

Looks good to me. Linked lists are awesome ^^

 

[Kenny]

Looks good to me. Linked lists are awesome ^^

Thanks for your help, and yes they are awesome. It saves quite a bit of time.

Anyway, for anyone who reads this. Do you think its worth submitting?

I just thought, with the trend of people using struct array loops, this could come in very handy. And I just thought I'd ask now to save it being a waste of a thread.

Final Product (Hopefully):

library Linked

    public module List
    
        static timer Timer = null           // Timer for personal use.
        
        private thistype next = 0           // Next node link.
        private thistype prev = 0           // Prev node link.
        private boolean  link = false       // If link is added to list.

        private static thistype head = 0    // Head == first node in list.
        private static thistype last = 0    // Last == last node added to list.
        private static integer  size = 0    // Size == How many nodes are currently in the list.
        
        // Insert a node into the list:
        method insertNode takes nothing returns boolean
            if .link == false then
                set .link = true
                
                if .head == 0 then
                    set .head = this
                else
                    set .prev = .last
                    set .prev.next = this
                endif
                
                set .last = this
                set .size = .size + 1
                
                return true
            debug else
                debug call BJDebugMsg("Linked List (insertNode error): Attempt to insert previously existing node into list.")
            endif
                
            return false
        endmethod
        
        // Remove a node from the list:
        method removeNode takes nothing returns boolean
            if .link == true then
                set .link = false
                
                if .head == this then
                    set .head = .next
                endif
                
                if .last == this then
                    set .last = .prev
                endif
                
                set .prev.next = .next
                set .next.prev = .prev
                set .size = .size - 1
                
                return true
            debug else
                debug call BJDebugMsg("Linked List (removeNode error): Attempt to remove currently inexistant node from list.")
            endif
            
            return false
        endmethod
        
        // BJ function. Two for one:
        method deleteNode takes nothing returns nothing
            if .removeNode() then
                call .destroy()
            debug else
                debug call BJDebugMsg("Linked List (deleteNode error): Unabled to destroy data attached to node.")
            endif
        endmethod
        
        // Flush all nodes in the list:
        static method flushList takes boolean wantDelete returns nothing
            local thistype d = .head
            
            loop
                exitwhen d == 0
                call d.removeNode()
                if wantDelete then
                    call d.destroy()
                endif
                set d = d.next
            endloop
        endmethod
        
        // For personal timer:
        static method createTimer takes nothing returns nothing
            set .Timer = CreateTimer()
        endmethod
        
        // Creates all the small useful functions needed:
        //! textmacro GetFunctions takes STATIC, NAME, TYPE, VALUE
        $STATIC$ method $NAME$ takes nothing returns $TYPE$
            return .$VALUE$
        endmethod
        //! endtextmacro

        //! runtextmacro GetFunctions("","getNext","thistype","next")
        //! runtextmacro GetFunctions("","getPrev","thistype","prev")
        //! runtextmacro GetFunctions("","isLink","boolean","link")
        //! runtextmacro GetFunctions(" static","getFirst","thistype","head")
        //! runtextmacro GetFunctions(" static","getLast","thistype","last")
        //! runtextmacro GetFunctions(" static","getSize","thistype","size")
        
    endmodule

endlibrary