• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[Snippet] [Needs work] Linked List Struct

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
LinkedList allows you to store data for the purpose of iterating over it. I hope the iteration methods are as quick as possible.

This supports iterating forwards, backwards, inserting at any arbitrary position in the list, removing from any position in the list, copying the list or converting a unit group into a list (if the UnitIndexer library is found).

An extension to Table, this also has nearly-unlimited instances, so you won't find yourself running short.

JASS:
library LinkedListStruct
/*
    About
    
        LinkedList is a high-level data structure useful for creating dynamic
        lists that can be iterated over, added or removed from at any point,
        with all operations being O(1) in complexity.
        
        This was inspired by "List" by MaskedPoptart which was not exactly a
        list but a linear stack with mostly O(N) operations in the important
        areas to keep things in numerical sequence.
        
    Disclaimer
    
        This is meant to store either positive or negative integers, but not
        both in the same list. The value "0" is treated as null & should not
        be treated as an actual value to be stored. You shouldn't be using 0
        for dynamic data as it is (for structs and unit indexers 0 is a null
        index), so this shouldn't be bad news.
        
        You also cannot store the same value twice. Being a linked list, the
        value itself is used as a pointer to its next & previous values - it
        cannot be multiply-defined because that wouldn't make sense. If you
        want to change a node's position in the list you should first remove
        it and then re-insert it somewhere.
    
    API
    
    struct LinkedList extends array
    
        static method create takes nothing returns LinkedList
        ->
            Create a new list. You can create a virtually-unlimited number of
            LinkedLists, so you never have to worry about consuming too much
            RAM, handle count or leakage from dynamic unit groups.
        
        method destroy takes nothing returns nothing
        ->
            Destroy the list if you are done with it.
        
        method flush takes nothing returns nothing
        ->
            Empty the list of all its contents. This is a really fast method
            compared to emptying the list node by node.
        
        method operator first takes nothing returns integer
        ->
            Get the node at the beginning of the list.
        
        method operator last takes nothing returns integer
        ->
            Get the node at the end of the list.
        
        method next takes integer node returns integer
        ->
            Get the node's next node in the list.
        
        method prev takes integer node returns integer
        ->
            Get the node's previous node in the list.
        
        method operator [] takes integer node returns integer
        ->
            Get a node arbitrarily. Useful for less verbosity.
        
        method operator flushed takes nothing returns boolean
        ->
            Is the list completely empty?
        
        method contains takes integer node returns boolean
        ->
            Is the node listed?
        
        method append takes integer node returns nothing
        ->
            Add a node to the end of the list. This is the fastest way to add
            to the list and you don't really need the other insertion methods
            unless you are doing some really complex mapping.
        
        method prepend takes integer node returns nothing
        ->
            Add a node to the beginning of the list.
        
        method insertAfter takes integer from, integer node returns nothing
        ->
            Insert a node after another's position.
        
        method insertBefore takes integer from, integer node returns nothing
        ->
            Insert a node before another's position.
        
        method remove takes integer node returns nothing
        ->
            Removes the node from the list. This method completely erases its
            position from the list, so if you are iterating through the list,
            you must store the next/prev node before calling this method, or
            use one of the following two methods.
        
        method popNext takes integer node returns integer
        ->
            Removes the node and returns the next node from its position in
            the list. Use this if you want to remove a node while looping
            forward.
        
        method popPrev takes integer node returns integer
        ->
            Removes the node and returns the previous node from its position
            in the list. Use this if you want to remove a node while looping
            backwards.
        
        method copy takes nothing returns LinkedList
        ->
            Returns an exact copy of the list in the form of a new list.
        
        debug method print takes nothing returns nothing
        ->
            Available only in debug mode, this prints out the list in a read-
            able format.
        
        optional method addGroup takes group g returns nothing
        ->
            Available only if UnitIndexer is in the map, this clears a unit
            group and adds its contents to the LinkedList.
*/
    
    struct LinkedList extends array
        private static hashtable h = InitHashtable()
        private static thistype rec = 0
        private static integer index = 0
        
        method operator [] takes integer node returns integer
            return LoadInteger(.h, this, node)
        endmethod
        
        private method operator []= takes integer node, integer value returns nothing
            call SaveInteger(.h, this, node, value)
        endmethod
        
        private method del takes integer node returns nothing
            call RemoveSavedInteger(.h, this, node)
        endmethod
        
        private static method operator main takes nothing returns thistype
            return 0
        endmethod
        
        static method create takes nothing returns thistype
            local thistype this = .rec
            if this == 0 then
                set this = .index + 1
                set .index = this
            else
                set .rec = .main[-this]
                call .main.del(-this)
            endif
            set .main[-this] = -1
            return this
        endmethod
        
        method flush takes nothing returns nothing
            call .main.del(this)
            call FlushChildHashtable(.h, this)
        endmethod
        
        method destroy takes nothing returns nothing
            if .main[-this] != -1 then
                debug call BJDebugMsg("Table Error: Tried to double-free instance: " + I2S(this))
                return
            endif
            call this.flush()
            set .main[-this] = rec
            set rec = this
        endmethod
        
        method operator first takes nothing returns integer
            return this[0]
        endmethod
        
        method operator last takes nothing returns integer
            return .main[this]
        endmethod
        
        method next takes integer node returns integer
            return this[node]
        endmethod
        
        method prev takes integer node returns integer
            if node == 0 then
                return this.last
            endif
            return this[-node]
        endmethod
        
        method operator flushed takes nothing returns boolean
            return 0 == this[0]
        endmethod
        
        method contains takes integer node returns boolean
            return 0 != this[node] or node == .main[this]
        endmethod
        
        method append takes integer node returns nothing
            local integer bot = .main[this]
            if this.contains(node) then
                debug call BJDebugMsg("LinkedList Error: Attempt to append an already-inserted node: " + I2S(node))
                return
            endif
            set this[-node] = bot
            set this[bot] = node
            set .main[this] = node
        endmethod
        
        method prepend takes integer node returns nothing
            local integer top = this[0]
            if this.contains(node) then
                debug call BJDebugMsg("LinkedList Error: Attempt to prepend an already-inserted node: " + I2S(node))
                return
            endif
            if 0 == top then
                set .main[this] = node
            else
                set this[-top] = node
                set this[node] = top
            endif
            set this[0] = node
        endmethod
        
        method insertAfter takes integer from, integer node returns nothing
            local integer nn = this[from]
            if 0 == from then
                call this.prepend(node)
            elseif 0 == nn then
                if from == .main[this] then
                    call this.append(node)
                debug else
                    debug call BJDebugMsg("LinkedList Error: Attempt to insert after unlisted node: " + I2S(from))
                endif
            else
                if this.contains(node) then
                    debug call BJDebugMsg("LinkedList Error: Attempt to insert an already-inserted node: " + I2S(node))
                    return
                endif
                set this[-nn] = node
                set this[node] = nn
                set this[-node] = from
                set this[from] = node
            endif
        endmethod
        
        method insertBefore takes integer from, integer node returns nothing
            if 0 == from then
                call this.append(node)
            else
                call this.insertAfter(this[-from], node)
            endif
        endmethod
        
        method remove takes integer node returns nothing
            local integer nn = this[node]
            local integer pn = this[-node]
            if this.contains(node) then
                if 0 == nn then
                    if 0 == pn then
                        call this.flush()
                        return
                    endif
                    set .main[this] = pn
                    call this.del(pn)
                elseif 0 == pn then
                    set this[0] = nn
                    call this.del(-nn)
                else
                    set this[pn] = nn
                    set this[-nn] = pn
                endif
                call this.del(node)
                call this.del(-node)
            debug else
                debug call BJDebugMsg("LinkedList Error: Attempt to remove a non-existing node: " + I2S(node))
            endif
        endmethod
        
        method popNext takes integer node returns integer
            local integer pop = this[node]
            call this.remove(node)
            return pop
        endmethod
        
        method popPrev takes integer node returns integer
            local integer pop = this[-node]
            call this.remove(node)
            return pop
        endmethod
        
        method copy takes nothing returns thistype
            local thistype new = .create()
            local integer i = this.first
            loop
                exitwhen 0 == i
                call new.append(i)
                set i = this[i]
            endloop
            return new
        endmethod
        
        static if DEBUG_MODE then
            method print takes nothing returns nothing
                local string s = "LinkedList: |cffffcc33"
                local integer i = this.first
                loop
                    exitwhen 0 == i
                    set s = s + "[" + I2S(i) + "]"
                    set i = this[i]
                endloop
                call BJDebugMsg(s + "|r")
            endmethod
        endif
        
    endstruct
    
endlibrary



Run it in debug mode.

JASS:
function InitTrig_List takes nothing returns nothing
    local LinkedList l = LinkedList.create()
    call l.append(2)
    call l.append(3)
    call l.append(6)
    call l.prepend(1)
    call l.insertAfter(3, 4)
    call l.insertBefore(6, 5)
    debug call l.print()
    call l.remove(2)
    call l.remove(4)
    call l.remove(6)
    debug call l.print()
    call l.insertAfter(1, 2)
    call l.insertAfter(3, 4)
    call l.insertAfter(5, 6)
    call l.remove(1)
    call l.remove(3)
    call l.remove(5)
    debug call l.print()
endfunction
 
Last edited:
Level 17
Joined
Apr 27, 2008
Messages
2,455
Imho Table is good for specific things like spells, for commonly used systems you just should use an hashtable, not because of the requirement but just to be faster.
No one is going to have 255 or more general system which use an hashtable, and use hashtables dynamically seems a really bad idea, because of the 256 limit.
I mean you won't make happen to reach this limit earlier if you use an hashtable for your library.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Exactly.

Btw, what about auto removing units of a list when they are removed of the game (it will make UnitIndexer as a requirement however)

EDIT : Oh i didn't get that was a generic linked list, not an unit one, what about an add-on so ?

EDIT 2 : You use an hashtable for each things, such as next and prev, instead of simple struct members.
I suppose it's for allow as many linked list as required, but it's going to lose in an hard way against a LL written with struct members only.
Hashtable write -> 40 times slower, hahstable read -> 4 times slower than an array.

So to be honest i would never use this tool.

Ofc i know if you make a LL without an hashtable but only struct instances you can have only a limit of LL and it must be < 8191 (members of linked list + linked list by themselves).

Maybe a module instead of a struct is the way to go here.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
I wasn't aware about it (but in an other hand i don't care that much, inline simple linked list is pretty easy, once you know how to do it ^^).

Also i don't pretend to get the absolute truth, just my point of view, and it can change later.
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
You need to realize the point of this. It is not meant to replace your normal "thistype next/thistype prev" combo, this is meant to be a linked list for EVERY instance.

This is not meant to be used like a static linked list, this is for when you need to store LOTS of data, such as with a projectile system, storing every target associated with each projectile, without worrying about hitting any limits with faux 2-D arrays.

This is also a useful replacement to dynamic unit groups, instead of storing units in a group to periodically loop over them you have this.

Do I need to update my description to make this more clear?
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
@ Troll-Brain, I did another bench with the removal of Table but I found myself duplicating much if its API like for constructors, destructors and the like. Is it really such a harsh requirement? The optimizer is supposed to kill inlined functions (or does it not do that any more)? If it doesn't then I can release the Table-free version.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
There are several reasons :

- It is a data structure so it is supposed to be as fast as possible (remember that i'm not a speedfreak, it just makes sense here for me)
- The requirement of Table isn't worth it for the user, just because what i've previoulsy said.

Now i'm agree that using directly an hashtable is way less "sexy" than a Table, but the user isn't supposed to edit the library (but ofc keep short senseless names far away from it)

I'm a guy that hates "useless" requirements, i mean when we have to use an other ressource when it could be pretty easily inlined without any revelant difference in the map script.
And the user should always be favorised against the coder in a public ressource.
For example imho WorldBounds should always be only an optionnal requirement.
Don't take me wrong, i'm not trying to reduce the usefulness of Table, WorldBounds is just the perfect example of my statement.

It's probably not such an harsh requirement.
But from my point of view it's just more logic to use an hashtable here rather than a Table.

Now, make your choice.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
Heh, if you used this in a projectile system, your max projectile count would go way down ; P.


Please give a solid example of where you would use this ;o. You definitely wouldn't use this in a .03125 second time ;p.


Because you aren't going for speed on this, add some other things like .has() and count().


Also, be sure to let users know that they can't store any data into arrays when using this.. it has to be stored into tables. Why? Because you are talking about a node count of possibly over 8191. Yea, the hit on this thing is immense :|.
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
.has() is the ".contains()" method and what do you have in mind for the ".count()" method? You have the ".flushed()" method to check if the list is empty and I can't really see a large benefit of tracking any other number.

What I meant by projectile system is that each target should have its own LinkedList, and when a missile is fired the target is added to the list or removed from the list when the projectile hits it. This is beneficial if a target wants something like "stop all missiles targetting me" or if you want to tell all missiles to stop homing if the target is removed from the game.

It is not meant to be used like T32-esqueue, it is meant to be used when you need an incredibly dynamic option that doesn't fit into arrays.

The way the data is stored is not meant to use the LinkedList id's as pointers, but to use pointers to the LinkedList id's. So if you are using UnitIndexer, for example, you want to have the unit index as the pointer to its linked list(s).
 
Level 6
Joined
Jun 20, 2011
Messages
249
Bribe sometimes i need to access the head of the list, but it seems that the prev and next values of the head both point to the next value, sounds like the prev pointer is broken. Or there is no such thing as a head? If so i can't work with this

EDIT: I just realized why and you really need to fix this
JASS:
        method next takes integer node returns integer
            return this[node]
        endmethod
        
        method prev takes integer node returns integer
            return this[-node]
        endmethod
this[-0] and this[0] points toward the same value.
 
Level 6
Joined
Jun 20, 2011
Messages
249
The thing is, i'm currently dealing with "parts" of linked lists because of my merge sort, and there really a simple way to tell if a node is the head or isn't. I also want to be able to fully navigate through linked lists as if it were a normal array list, this system isn't letting me.

If you manage to fix this issue i'll be able to finish MergeSort application for LinkedLists.
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
So you want to be able to navigate through the list as both a ciruclarly linked list and as a stack? And you want to go further backwards than the head, but from an offset point in the list? I suppose I could add an additional check to the "prev" operator that checks if the node is not equal to 0 (that is what you are looking for right?)

But the LinkedList is not meant to be iterated through via the stack route. What you want is perhaps a Stack wrapper. In fact, I originally had a library named Stack that I thought useless, which did that exact same thing. It would be easy enough to make as an extension as I already did the work and have it saved on my hard drive.
 
Level 6
Joined
Jun 20, 2011
Messages
249
All i want is to know the prev value of any node of the list whether is the head or not : /

EDIT:Here's the merge sort for your system... had to allocate the "exit" local to keep track of the list's node-after-the-last-one
JASS:
library MergeSort /* v1.1.0

*/uses/*
*/  LinkedList  /* hiveworkshop.com/forums/submissions-414/snippet-linkedlist-205300/

A tool for sorting linked lists.

**********************************************************************/
    
    function interface CompareFunc takes integer v1, integer v2 returns boolean
    
    function MergeSortEx takes LinkedList whichList, integer start, integer end, CompareFunc func returns integer
        local integer half=start
        local integer list=start
        local integer exit=whichList.next(end)
        local integer result=whichList.prev(start)
        
        local integer memory=0
        
        //*********************************************************************
        //  If the last node (end.prev) of the list is equal to the first node
        //  (start) then skip.
        if start==end then
            return start
        endif
        
        //*********************************************************************
        //  Looks for the value placed at the half of the list.
        loop
            exitwhen list==exit
            set half=whichList.next(half)
            set list=whichList.next(list)
            exitwhen list==exit
            set list=whichList.next(list)
        endloop
        
        //*********************************************************************
        //  Now it calls this function again but for each half (from start up
        //  to the previous node from the half and from the half up to the end)
        set start=MergeSortEx(whichList,start,whichList.prev(half),func)
        set half=MergeSortEx(whichList,half,end,func)
        
        //*********************************************************************
        //  Merges the list using 2 pointers: start and half.
        loop
            exitwhen start==exit or half==exit or start==half
            if func.evaluate(start,half) then
                
                //*********************************************************************
                //  If the pointers pass the compare method it means that the half node
                //  needs to be placed behind the start node.
                set memory=whichList.next(half)

                //*********************************************************************
                //  So we remove the half node from the list...
                call whichList.remove(half)

                //*********************************************************************
                //  ...and place it behind the start node.
                call whichList.insertBefore(start,half)

                //*********************************************************************
                //  After that we need half to point towards the node that was
                //  previously pointing next[half] before, that's why i stored it
                //  inside "memory" and now retreive it.
                set half=memory
            else
                
                //*********************************************************************
                //  If the value doesn't pass the compare method it means there's no
                //  need for moving (the list is fine) and moves along
                set start=whichList.next(start)
            endif
        endloop
        return whichList.next(result)
    endfunction
    
    function MergeSort takes LinkedList whichList, CompareFunc func returns nothing
        call MergeSortEx(whichList,whichList.first,whichList.last,func)
    endfunction

endlibrary
INB4 FUNCTION INTERFACES EWWWWW
Please just tell me how to avoid them
 
Last edited:
Level 6
Joined
Jun 20, 2011
Messages
249
Bribe please add a linked list module to this system since some people won't use hashtables for their linked lists.
Here i wrote this one
JASS:
    module LinkedList
        private static integer array recycle
        private static integer instanceCount = 0
        
        thistype    head
        thistype    next
        thistype    prev
        
        static method allocate takes nothing returns thistype
            local thistype this=recycle[0]
            if 0==this then
                set instanceCount=instanceCount+1
                return instanceCount
            endif
            set recycle[0]=recycle[recycle[0]]
            return this
        endmethod
        
        method deallocate takes nothing returns nothing
            set recycle[this]=recycle[0]
            set recycle[0]=this
        endmethod
                
        static method create takes nothing returns thistype
            local thistype this=allocate()
            set this.next=this
            set this.prev=this
            set this.head=this
            return this
        endmethod
        
        method clear takes nothing returns nothing
            set this=this.head
            loop
                exitwhen this==this.next
                call this.next.deallocate()
                set this.next=this.next.next
            endloop
        endmethod
        
        method destroy takes nothing returns nothing
            static if ADDITIONAL_SAFETY then
                if this.head!=this then
                    set this=this.head
                endif
            endif
            call this.clear()
            call this.deallocate()
        endmethod
        
        method insertAfter takes nothing returns thistype
            local thistype new=allocate()
            
            set new.head=this.head
            
            //*********************************************************************
            //  Places the instance inside a linked list.
            set this.next.prev=new
            set new.next=this.next
            set this.next=new
            set new.prev=this
            return new
        endmethod
        
        method insertBefore takes nothing returns thistype
            local thistype new=allocate()
            
            set new.head=this.head
            
            //*********************************************************************
            //  Places the instance inside a linked list.
            set this.prev.next=new
            set new.prev=this.prev
            set this.prev=new
            set new.next=this
            return new
        endmethod
        
        method remove takes nothing returns nothing
        
            static if ADDITIONAL_SAFETY then
                if this.head==this then
                    call this.destroy()
                    return
                endif
            endif
            
            call this.deallocate()
            
            //*********************************************************************
            //  Remove the instance from the linked list.
            set this.prev.next=this.next
            set this.next.prev=this.prev
        endmethod
    endmodule
Since you have access to the head you don't need the prepend or append methods and the first and last operators can be easily replaced with head.next or prev
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
I am working on an update that will allow you to remove nodes while looping through the list, without breaking the iteration like it does in the current version:

JASS:
library LinkedListStruct requires optional Table /*
    
    About
    
        LinkedList is a high-level data structure useful for creating dynamic
        lists that can be iterated over, added or removed from at any point,
        with all operations being O(1) in complexity.
        
        This was inspired by "List" by MaskedPoptart which was not exactly a
        list but a linear stack with mostly O(N) operations in the important
        areas to keep things in numerical sequence.
    
    Disclaimer
    
        This is meant to store either positive or negative integers, but not
        both in the same list. The value "0" is treated as null & should not
        be treated as an actual value to be stored. You shouldn't be using 0
        for dynamic data as it is (for structs and unit indexers 0 is a null
        index), so this shouldn't be bad news.
        
        You also cannot store the same value twice. Being a linked list, the
        value itself is used as a pointer to its next & previous values - it
        cannot be multiply-defined because that wouldn't make sense. If you
        want to change a node's position in the list you should first remove
        it and then re-insert it somewhere.
    
    Optional Requirement
    
        New Table - hiveworkshop.com/forums/showthread.php?t=188084
    
    API
    
    struct LinkedList extends array
    
        static method create takes nothing returns LinkedList
        ->
            Create a new list. You can create a virtually-unlimited number of
            LinkedLists, so you never have to worry about consuming too much
            RAM, handle count or leakage from dynamic unit groups.
        
        method destroy takes nothing returns nothing
        ->
            Destroy the list if you are done with it.
        
        method flush takes nothing returns nothing
        ->
            Empty the list of all its contents. This is a really fast method
            compared to emptying the list node by node.
        
        method operator first takes nothing returns integer
        ->
            Get the node at the beginning of the list.
        
        method operator last takes nothing returns integer
        ->
            Get the node at the end of the list.
        
        method next takes integer node returns integer
        ->
            Get the node's next node in the list.
        
        method prev takes integer node returns integer
        ->
            Get the node's previous node in the list.
        
        method operator [] takes integer node returns integer
        ->
            Get a node arbitrarily. Useful for less verbosity.
        
        method operator flushed takes nothing returns boolean
        ->
            Is the list completely empty?
        
        method contains takes integer node returns boolean
        ->
            Is the node listed?
        
        method append takes integer node returns nothing
        ->
            Add a node to the end of the list. This is the fastest way to add
            to the list and you don't really need the other insertion methods
            unless you are doing some really complex mapping.
        
        method prepend takes integer node returns nothing
        ->
            Add a node to the beginning of the list.
        
        method insertAfter takes integer from, integer node returns nothing
        ->
            Insert a node after another's position.
        
        method insertBefore takes integer from, integer node returns nothing
        ->
            Insert a node before another's position.
        
        method remove takes integer node returns nothing
        ->
            Removes the node from the list. This method completely erases its
            position from the list, so if you are iterating through the list,
            you must store the next/prev node before calling this method, or
            use one of the following two methods.
        
        method copy takes nothing returns LinkedList
        ->
            Returns an exact copy of the list in the form of a new list.
        
        debug method print takes nothing returns nothing
        ->
            Available only in debug mode, this prints out the list in a read-
            able format.
        
        optional method addGroup takes group g returns nothing
        ->
            Available only if UnitIndexer is in the map, this clears a unit
            group and adds its contents to the LinkedList.
*/
    globals
        //You can set this to false if you want to ensure you can have
        //"unlimited" LinkedList indices when you have the Table library in
        //your map.
        private constant boolean USE_TABLE = LIBRARY_Table
    endglobals
    
    private module InitTA
        private static method onInit takes nothing returns nothing
            //You can define a "max instances" here, if you use Table in your
            //map and have "USE_TABLE" set to "true". I set it to about a
            //million, so that means you can have more than 100 arrays
            //completely filled with LinkedLists. Should be about 1000 times
            //more than you'll ever need.
            local integer max = 0x100000
            set .ta = TableArray[max]
            set .has = TableArray[max]
        endmethod
    endmodule
    
    struct LinkedList extends array
        static if USE_TABLE then
            private static TableArray ta
            private static TableArray has
            implement InitTA
        else
            private static hashtable h = InitHashtable()
        endif
        private static integer index = 0
        
        static if USE_TABLE then
            method operator [] takes integer node returns integer
                return .ta[this][node]
            endmethod
            private method operator []= takes integer node, integer value returns nothing
                set .ta[this][node] = value
            endmethod
            private method del takes integer node returns nothing
                call .ta[this].remove(node)
            endmethod
        else
            method operator [] takes integer node returns integer
                return LoadInteger(.h, this, node)
            endmethod
            private method operator []= takes integer node, integer value returns nothing
                call SaveInteger(.h, this, node, value)
            endmethod
            private method del takes integer node returns nothing
                call RemoveSavedInteger(.h, this, node)
            endmethod
        endif
        
        private static method operator main takes nothing returns thistype
            return 0
        endmethod
        
        static method create takes nothing returns thistype
            local thistype this = .main[0]
            if this == 0 then
                set this = .index + 1
                set .index = this
            else
                set .main[0] = .main[-this]
            endif
            set .main[-this] = -1
            return this
        endmethod
        
        method flush takes nothing returns nothing
            call .main.del(this)
            static if USE_TABLE then
                call .ta[this].flush()
                call .has[this].flush()
            else
                call FlushChildHashtable(.h, this)
                call FlushChildHashtable(.ht, -this)
            endif
        endmethod
        method operator flushed takes nothing returns boolean
            return .main[this] == 0
        endmethod
        
        method destroy takes nothing returns nothing
            if .main[-this] != -1 then
                debug call BJDebugMsg("Table Error: Tried to double-free instance: " + I2S(this))
            else
                call this.flush()
                set .main[-this] = .main[0]
                set .main[0] = this
            endif
        endmethod
        
        method operator first takes nothing returns integer
            return this[0]
        endmethod
        method operator last takes nothing returns integer
            return .main[this]
        endmethod
        
        method next takes integer node returns integer
            return this[node]
        endmethod
        method prev takes integer node returns integer
            return this[-node]
        endmethod
        
        method contains takes integer node returns boolean
            static if USE_TABLE then
                return .has[this].boolean[node]
            else
                return LoadBoolean(.h, -this, node)
            endif
        endmethod
        private method insert takes integer node returns nothing
            static if USE_TABLE then
                set .has[this].boolean[node] = true
            else
                call SaveBoolean(.h, -this, node, true)
            endif
        endmethod
        
        private method unlinkEx takes integer node returns nothing
            local integer nn = this[node]
            local integer pn = this[-node]
            if nn == 0 then
                if pn == 0 then
                    call this.flush()
                else
                    set .main[this] = pn
                    call this.del(pn)
                endif
            elseif pn == 0 then
                set this[0] = nn
                call this.del(-nn)
            else
                set this[pn] = nn
                set this[-nn] = pn
            endif
        endmethod
        private method unlink takes integer node returns boolean
            if this.contains(node) then
                call this.unlinkEx(node)
                return true
            endif
            return false
        endmethod
        
        method append takes integer node returns nothing
            local integer top
            if node != 0 then
                call this.unlink(node)
                call this.insert(node)
                set top = .main[this]
                set .main[this] = node
                set this[-node] = top
                set this[top] = node
                set this[node] = 0
            endif
        endmethod
        
        method prepend takes integer node returns nothing
            local integer bot
            if node != 0 then
                call this.unlink(node)
                call this.insert(node)
                set bot = this[0]
                if bot == 0 then
                    set .main[this] = node
                else
                    set this[-bot] = node
                    set this[node] = bot
                endif
                set this[0] = node
                set this[-node] = 0
            endif
        endmethod
        
        method insertAfter takes integer from, integer node returns nothing
            local integer nn = this[from]
            if from == 0 then
                call this.prepend(node)
            elseif nn == 0 then
                call this.append(node)
            elseif from != node and node != 0 then
                call this.unlink(node)
                call this.insert(node)
                set this[-nn] = node
                set this[node] = nn
                set this[-node] = from
                set this[from] = node
            endif
        endmethod
        
        method insertBefore takes integer from, integer node returns nothing
            call this.insertAfter(this[-from], node)
        endmethod
        
        private static timer removeTimer = CreateTimer()
        private static integer removeN = -1
        private static thistype array removeMain
        private static integer array removeNode
        private static method delayedRemove takes nothing returns nothing
            local thistype this
            local integer node
            loop
                set this = .removeMain[.removeN]
                set node = .removeNode[.removeN]
                if not this.contains(node) then
                    //If the same node wasn't re-added to the list:
                    call this.del(node)
                    call this.del(-node)
                endif
                set .removeN = .removeN - 1
                exitwhen .removeN < 0
            endloop
        endmethod
        method remove takes integer node returns nothing
            if this.unlink(node) and not this.flushed then
                //Delay data clearing to prevent loops from malfunctioning
                if .removeN < 0 then
                    call TimerStart(.removeTimer, 0, false, function thistype.delayedRemove)
                endif
                set .removeN = .removeN + 1
                set .removeMain[.removeN] = this
                set .removeNode[.removeN] = node
                //Mark the node as removed so that there is no reference
                //problem in the mean time.
                static if USE_TABLE then
                    call .has[this].boolean.remove(node)
                else
                    call RemoveSavedBoolean(.h, -this, node)
                endif
            endif
        endmethod
        
        static if DEBUG_MODE then
            method print takes nothing returns nothing
                local string s = "LinkedList: |cffffcc33"
                local integer i = this.first
                loop
                    exitwhen i == 0
                    set s = s + "[" + I2S(i) + "]"
                    set i = this[i]
                endloop
                call BJDebugMsg(s + "|r")
            endmethod
        endif
        
    endstruct
    
endlibrary
 
Last edited:
Top