[Snippet] List

[Frotty]

e: I didnt find the other List when I was searching
I needed a simple Array without gaps, didnt find one, made one.
Basically a Table that also saves the position of each entry, yes its as awesome as you think.

library ConsistentArray requires Table
//******************************************************************************
//* By Frotty
//*
//* Bigass Credit to Nestharus because hes so annoying
//*
//* This library is basically an array without gaps.
//* Every values position gets saved in a Table, so that you have aconsistent
//* array, making looping throw it easy.
//*
//*                         ===How to use===
//* Create a new List somewhere:
//*     ConsistentArray myArray = ConsistentArray.create()
//*
//* To add a Value simply use the add() method
//*     myArray .add(myStruct)
//*
//* To get the value of a certain index use the [] operator
//*     myArray [1]
//* This would return the stored integer at position 1
//*
//* To remove a value use the remove() method
//*     myArray .remove(myStruct)
//* Because STructIDs are unique and the List saves the position of the struct,
//* it gets removed and all values with a higher index get moved down.
//*
//* In a loop you often want to stop at the end of the list, use the readonly size variable for that
//* This library also includes a simple implementation of a group enumeration
//********************************************************************************
    
    globals
        // How many Members a List can have. If you want to save structs this shouldnt be higher than 8910
        private constant integer MAX_MEMBERS = 8910 
    endglobals
    
    struct ConsistentArray
        Table objects
        readonly integer size = 0
        
        static method create takes nothing returns thistype
            local thistype this = thistype.allocate()
            set objects = Table.create()
            return this
        endmethod
        
        method add takes integer value returns integer
            if size >= MAX_MEMBERS then
                call BJDebugMsg(SCOPE_PREFIX + " Max members reached: " + I2S(MAX_MEMBERS)  )
                return 8910
            endif
            set objects[MAX_MEMBERS + value] = size
            set objects[size] = value
            set size = size + 1
            return size - 1
        endmethod
        
        method operator [] takes integer index returns integer
            if size > 0 then
                return objects[index]
            else
                call BJDebugMsg( SCOPE_PREFIX + " Cant get value because size is 0" )
                return 0 // 0 == no Struct
            endif
        endmethod
        
        method remove takes integer value returns nothing
            local integer position = objects[MAX_MEMBERS + value]
            if size > 0 then
                loop
                    set objects[position] = objects[position+1]
                    set objects[MAX_MEMBERS + objects[position]] = position
                    set position = position + 1
                    exitwhen position >= size
                endloop
                set size = size - 1
            endif
        endmethod
    
    endstruct

endlibrary

 

[Magtheridon96]

Hmmm...

 

[Frotty]

Hmmm...

+1 ?

 

[Nestharus]

Not well written..

Here is a pretty good generic circularly linked list. Loop until hit head

local thistype node=next //set to first node on list
loop
    exitwhen node.head
    set node=node.next
endloop

module List
    readonly thistype next
    readonly thistype prev
    readonly boolean head
    private static integer c=0
    static method create takes nothing returns thistype
        local thistype i
        if (0==thistype(0).next) then
            set i=c+1
            set c=i
        else
            set i=thistype(0).next
            set thistype(0).next=i.next
        endif
        set i.next=i
        set i.prev=i
        set i.head=true
        return i
    endmethod
    method add takes nothing returns thistype
        local thistype i
        if (0==thistype(0).next) then
            set i=c+1
            set c=i
        else
            set i=thistype(0).next
            set thistype(0).next=i.next
        endif
        set i.prev=prev
        set i.next=this
        set prev.next=i
        set prev=i
        return i
    endmethod
    method remove takes nothing returns nothing
        set next.prev=prev
        set prev.next=next
        set next=thistype(0).next
        set thistype(0).next=this
    endmethod
    method clear takes nothing returns nothing
        if (not next.head) then
            set prev.next=thistype(0).next
            set thistype(0).next=next
            set next=this
            set prev=this
        endif
    endmethod
    method destroy takes nothing returns nothing
        set prev.next=thistype(0).next
        set thistype(0).next=this
        set head=false
    endmethod
endmodule

Here is a non instanced list. Sentinel in this case is 0 rather than a boolean. It uses instance 1 as the recycler.

module List
    readonly thistype next
    readonly thistype prev
    private static integer c=1
    static method add takes nothing returns thistype
        local thistype i
        if (0==thistype(1).next) then
            set i=c+1
            set c=i
        else
            set i=thistype(1).next
            set thistype(1).next=i.next
        endif
        set i.prev=thistype(0).prev
        set i.next=0
        set thistype(0).prev.next=i
        set thistype(0).prev=i
        return i
    endmethod
    method remove takes nothing returns nothing
        set next.prev=prev
        set prev.next=next
        set next=thistype(1).next
        set thistype(1).next=this
    endmethod
    static method clear takes nothing returns nothing
        if (0!=thistype(0).next) then
            set thistype(0).prev.next=thistype(1).next
            set thistype(1).next=thistype(0).next
            set thistype(0).next=0
            set thistype(0).prev=0
        endif
    endmethod
endmodule

 

[Frotty]

no...
I dont need/want a linked list, also Its not supposed to be a module inside of a struct but a global.
It does what its supposed to do, and I didnt find such a simple List via search.

 

[Nestharus]

Well, then name your library Array rather than List ;p.


It's misleading. What you are really doing is arrays =).

edit
Nvm, it looks like more like a really big array/queue deal... so... not sure what to call it.

But if you say list, people auto think of linked list. If you say ArrayList, people think of arrays resizing in background (same with like an ArrayQueue).


Come up with a better name ;p

 

[Frotty]

Whatever~
How does SortedArray sound for you?

 

[Nestharus]

Not SortedArray as that'd imply that the values are sorted ;p.

 

[Frotty]

ConsistentArray ?
But its not liek anyone would find it then.
I mean who would search for array pls.

 

[Nestharus]

Sounds good ; ).

 

[Magtheridon96]

Isn't a "SortedArray" sort of like a Binary Heap?

 

[Nestharus]

Isn't a "SortedArray" sort of like a Binary Heap?

No, like a binary tree

 

[Bribe]

There's a library floating around here called Stack (think it's by Masked Poptart) which does this but using hashtables instead of vJass fake arrays.

I wrote some stuff in Luck which does stuff like this using Table instances, allowing you to create/destroy the lists, I have been meaning to port them to vJass guess I've been putting it off too long.

 

[Frotty]

There's a library floating around here called Stack (think it's by Masked Poptart) which does this but using hashtables instead of vJass fake arrays.

I wrote some stuff in Luck which does stuff like this using Table instances, allowing you to create/destroy the lists, I have been meaning to port them to vJass guess I've been putting it off too long.

What are vjass fake arrays converted to anyway?
Anyway, I used Table before, but I thought it would be unnecessary to set a requirement to such a small thing.

 

[Magtheridon96]

What are vjass fake arrays converted to anyway?

I'd say they're converted to really ugly functions that take 2 indicies like those ones from CSCache xD

 

[Nestharus]

The ugly functions have if statements in them. If an index falls in a certain range, it'll retrieve it from a given array of a set of arrays. They are slower than hashtables : P.

 

[Magtheridon96]

The ugly functions have if statements in them. If an index falls in a certain range, it'll retrieve it from a given array of a set of arrays. They are slower than hashtables : P

Exactly like CSCache ^^
I wonder how gamecache is useful nowadays :/
Any ideas?

 

[Bribe]

For campaigns or for cloning a unit. Pretty limited if you ask me.

 

[BBQ]

I wonder how gamecache is useful nowadays :/
Any ideas?

The sync natives are very, very useful. They are widely used to communicate meta data to replay parsers and bots, which allows you to create stats, track wins/losses and lots of other stuff.

 

[Frotty]

Well thats kinda ugly :/
Now uses Table ! Hooray!
You could also use 2 Tables if you dont want to save Structs only, isnt that cool?
Dont know why I update this anyways~

 

[Nestharus]

Why do you have a positions table? Just change the objects array into a table, get rid of positions table, and you're done =p.

 

[Frotty]

yea.
the array would have made the get function faster tho.

 

[Bribe]

I think this would be replaced by my LinkedList which was replaced by Dirac's LinkedListModule :/

PM me if you feel otherwise.