wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Resources > - Submit a resource -
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 11-13-2009, 12:30 AM   #1
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default [script] Collections

Here is a simple arraylist implementation I wrote that is fully macroed. It supports all types.

Here is a butt load of documentation.
Collapse Zinc:
//! zinc
/*
    Collections implements an arraylist. An Arraylist is a resizable array.
    if you are unsure of the amount of instances you might be storing,
    and would like something portable and type-safe then you can use this class.
    It wraps a hashtable.
    Requires:: JassHelper 0.A.2.7 by Vexorian.
    
    Instantiation::
    --------------
    //! runtextmacro ListTemplate("T","TypeName","BaseName","DefaultVal")
    T -- the T that stored in this collection.
    
    TypeName -- The name of the type used in Save/Load HashTable natives.
    e.g. Integer,Real,Boolean,String,ItemHandle,UnitHandle etc.
    
    BaseName -- the name of the type used in Have/Remove Hashtable natives.
    e.g. Integer,Real,Boolean,Str,Handle
    
    DefaultVal -- The default value of the type.
    e.g. 0,0.0,false,null
    
    Supported Types::
    ----------------
    Integer,Real,Boolean,String,almost all Handle types, and any user type.
    
    use examples::
    //! runtextmacro ListTemplate("item","ItemHandle","Handle","null")
    //! runtextmacro ListTemplate("ItemMenu","Integer","Integer","0")


    New Types::
    -----------
    List_T arraylist of Ts.
    Action_T a function that takes a T.
    
    
    
    List_$T$ method index
    Operators::
    -----------
    Get/Set [index integer]->T -- get or set the element* at index
    NOTE: Does bound checking. Only allowed to store values in 0-Size-1.
    
    List of Properties::
    -------------------
    Getters::
    Size->integer -- gets the total number of elements stored in this collection.
    
    Capacity->integer -- get the max number of elements storable in this instance.
    
    Setters::
    Capacity(integer value) -- sets the max number of elements storable in this instance.
    
    Methods::
    --------
    Add(T value)->boolean -- adds a value to the end of the collections. Returns false on failure.
    
    RemoveAt(integer index)->T -- removes the element located at index and left shifts to fill the whole.
    e.g. if the collection is 1,2,3,4,5 and you remove element 3, then it'll shift to be 1,2,4,5
    
    UnstableRemoveAt(integer index)->T -- removes the element at index. But shifts the last element to fill the hole.
    e.g. if the collection is 1,2,3,4,5 and you remove element 3, then it'll be 1,2,5,4. Obviously only useful if you
    don't care at all about order.
    
    IndexOf(T value)->integer -- returns the first index of a value in the list. Returns -1 if it finds nothing.
    
    Contains(T value)-> boolean -- returns if this list has value in it.
    
    Remove(T value) -> boolean -- removes the first location of value in the collection. And left shifts accordingly.
    returns if it did remove.
    
    Clear() -- removes all elements in this collection. Retains capacity information.
    
    
    ForEach(Action_T func) -- applies func to each member of the collection.
    e.g.
    List_integer ints = List_integer.create(0);
    ints.Add(1);ints.Add(2);ints.Add(3);
    ints.ForEach(function(integer x){BJDebugMsg(I2S(x));} // prints 1/n2/n3/n
    
    Clone()-> List_T -- returns a 
    
    Constructors::
    -------------
    .create(integer capacity)->List_T returns a List_T of capacity capacity.
    
    * Note due to a bug hashtables can't store null so I'm forced to remove the element
        when you try to use the default value
*/
library Collections
{
//! textmacro ListTemplate takes T,typename,baseName,DefaultVal
    type Action_$T$ extends function($T$);
    public struct List_$T$
    {
        private integer m_Size;
        private integer m_Capacity;
        private static hashtable Table = InitHashtable();
        method operator Size()->integer
        {
            return m_Size;
        }
        method operator Capacity()->integer
        {
            return m_Capacity;
        }
        method operator Capacity=(integer value)
        {
            m_Capacity = value;
        }
        
        method operator[](integer index)->$T$
        {
            $T$ retVal = $DefaultVal$;
            if( - 1 < index && index < m_Size)
            {
                retVal = Load$typename$(Table,integer(this),index);
            }
            return retVal;
        }
        method operator[]=(integer index,$T$ value)
        {
            if( -1 < index && index < m_Size)
            {
                // Storing null doesn't actually do anything. It won't override values. So we have to remove things in that case.
                // Since staticif  currently does not support reading parameters from macros this is all that can be done.
                if(value == $DefaultVal$) RemoveSaved$baseName$(Table,integer(this),index);
                else Save$typename$(Table,integer(this),index,value);
            }
        }
        method Add($T$ obj)->boolean
        {
            boolean retVal = false;
            if(m_Capacity == 0 || m_Size < m_Capacity)
            {
                m_Size+=1;
                this[m_Size-1]= obj;
                retVal = true;
            }
            return retVal;
        }
        
        method RemoveAt(integer index)->$T$
        {
            $T$ retVal = $DefaultVal$;
            integer i;
            if(-1 < index && index < m_Size)
            {
                retVal = this[index];
                for(i = index; i < m_Size-1; i+=1)
                {
                    this[i] = this[i+1];
                }
                m_Size-=1;
                RemoveSaved$baseName$(Table,integer(this),m_Size);
            }
            return retVal;
        }
        // Performs at O(1) time, but moves things about
        // in the process.
        method UnStableRemoveAt(integer index)-> $T$ 
        {
            $T$ retVal = $DefaultVal$;
            if( - 1 < index && index < m_Size)
            {
                retVal = this[index];
                this[index] = this[m_Size-1];
                m_Size-=1;
                RemoveSaved$baseName$(Table,integer(this),m_Size);
            }
            return retVal;
        }
        
        method IndexOf($T$ value)->integer
        {
            integer i = 0;
            integer retVal = -1;
            for(i = 0; i < m_Size; i+=1)
            {
                if(this[i] == value)
                {
                    retVal = i;
                    break;
                }
            }
            return retVal;
        }
        
        method Contains($T$ value)->boolean
        {
            return IndexOf(value) > -1;
        }
        
        method Remove($T$ value)->boolean
        {
            integer index = IndexOf(value);
            if(index > -1) RemoveAt(index);
            return (index > -1);
        }
        
        method Clear()
        {
            FlushChildHashtable(Table,integer(this));
            m_Size = 0;
        }
        
        method ForEach(Action_$T$ func)
        {
            integer i;
            for(i = 0;i < m_Size; i+=1)
            {
                func.evaluate(this[i]);
            }
        }
        private method onDestroy()
        {
            Clear();
        }
        
        // This is a shallow clone
        static method Clone(thistype list)->thistype
        {
            thistype retVal = thistype.create(list.m_Capacity);
            integer i;
            for(i = 0; i < list.m_Size; i+=1)
            {
                retVal.Add(list[i]);
            }
            return retVal;
        }
        
        // Yes, I suppose I could've wrote List(T) but hey thistype sweet!
        // passing 0 creates a list without a fixed cap.
        static method create(integer capacity)->thistype
        {
            thistype retVal = thistype.allocate();
            retVal.m_Capacity = capacity;
            return retVal;
        }
    }
//! endtextmacro
}
//! endzinc
T is the type of the object.
TypeName is the name used in The hashtable natives (e.g. Integer,Real,Boolean,UnitHandle, ItemHandle etc)
baseName is the name used in Have/Remove handles (e.g. Integer,Real,Boolean,Handle)
and DefaultValue is the default value. (e.g. 0,false,null)

The reason that the defaultvalue must be known is that there aren't exceptions and we need something to return on errors.
ALSO Hashtables suck when saving the value null.
Collapse Zinc:
SaveUnitHandle(tablevar,0,0,CreateUnit(Player(0),'hfoo',0,0,0));
SaveUnitHandle(tablevar,0,0,null);
BJDebugMsg(I2S(GetHandleId(LoadUnitHandle(tablevar,0,0)))
Will suprisingly print a non-zero value. So we have to add a special case. Since staticif can't read textmacros parameters (unlike their cjass equivalents), we have to suffer a small performance hitting whenever storing 0 in an Integer list.

The type of the list is List_T

Last edited by weaaddar : 11-17-2009 at 03:36 AM.
weaaddar is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 11-16-2009, 11:33 PM   #2
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

So is there something fundamentally wrong with this?
weaaddar is offline   Reply With Quote
Old 11-17-2009, 12:42 AM   #3
Veev
User
 
Join Date: Nov 2006
Posts: 199

Veev will become famous soon enough (63)Veev will become famous soon enough (63)Veev will become famous soon enough (63)

Default

I just think there are very few people (atm) who use Zinc. :/
Veev is offline   Reply With Quote
Old 11-17-2009, 01:09 AM   #4
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,729

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

Quote:
Originally Posted by weaaddar
So is there something fundamentally wrong with this?
It takes long enough for reviewers to go over vJass. I have no clue the timeline for something written in cJass that isn't as simple as Vex's PowerupSentinel.

I mean, it has no documentation for instance. That's the most important thing of any submission and a submission requirement. Explain the reason it's useful, what it does, and give examples of how to use it and stuff in the documentation at the top of the library. Also, the library name "Collections" is very ambiguous and doesn't tell exactly what the library does. You should go for a more descriptive name.
__________________

Last edited by Rising_Dusk : 11-17-2009 at 01:13 AM.
Rising_Dusk is offline   Reply With Quote
Old 11-17-2009, 02:48 AM   #5
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

Its called collections because there are more collections I've written in the namespace they are just not included because they'd be stepping over similar functionality. Its an arraylist/vector, if you used java/c#/c++ you'll know exactly what it is.
weaaddar is offline   Reply With Quote
Old 11-17-2009, 03:02 AM   #6
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,729

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

Quote:
Originally Posted by weaaddar
Its an arraylist/vector, if you used java/c#/c++ you'll know exactly what it is.
Uhm, but that's really not enough. What if potential users haven't used those languages? They need to be able to figure it out too.
Quote:
Originally Posted by weaaddar
Its called collections because there are more collections I've written in the namespace they are just not included because they'd be stepping over similar functionality.
That doesn't seem to be a very good reason to call it that if you ask me.
__________________
Rising_Dusk is offline   Reply With Quote
Old 11-17-2009, 03:39 AM   #7
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

This is Zinc. Not Cjass, and is got a total of 130 lines of code. Probably less if you remove extra lines and comments. I just added 90 lines of comments and a setter to Capacity and a ForEach method and a new type.
As for the name,well it makes sense for me. The Library has a stack, a queue, a linkedlist, this feller I obviously only need to show this code.

Last edited by weaaddar : 11-17-2009 at 03:40 AM.
weaaddar is offline   Reply With Quote
Old 11-18-2009, 08:05 PM   #8
grim001
requires vJass
 
grim001's Avatar


Code Moderator
 
Join Date: Nov 2006
Posts: 1,540

Submissions (10)

grim001 is just really nice (277)grim001 is just really nice (277)

Send a message via AIM to grim001
Default

OK, I've read through the code.

It is obvious that hashtables can be wrapped to create something that behaves like a resizable array; the question is whether that's a good idea. Hashtable lookups are about 5x slower than array lookups, so it's got to be a case where large-ish lists and many instances are required (thus making array usage impractical), but performance is little concern. In practice, it doesn't seem to come up that often.

The primary benefit this seems to offer over Table is that you can easily add or remove things from it, get the size, etc. I have to question the use of all of the O(n) operations, since they could be O(1) if this were using a linked list internally (in which case, why not use something like Stack?)

Also, it is really discouraged to force the user to use a textmacro. If you look at the way Table is setup, it already has the textmacros instantiated. It is not so useful to support a collection of any handle type, since integers can store anything via structs.
grim001 is offline   Reply With Quote
Old 11-20-2009, 12:39 AM   #9
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

Hash lookups are not 5x slower in Jass. Its like 75% the performance of an array. The Gamecache was only 3x slower then the array.

As for the fundamentals, it could be written to be a linked list, but in my case I do a lot of adding to the end and Random access so its cheap enough to keep it as is.
weaaddar is offline   Reply With Quote
Old 11-20-2009, 01:35 AM   #10
grim001
requires vJass
 
grim001's Avatar


Code Moderator
 
Join Date: Nov 2006
Posts: 1,540

Submissions (10)

grim001 is just really nice (277)grim001 is just really nice (277)

Send a message via AIM to grim001
Default

It's roughly 5x slower if you don't include the cost of the variable set operation. Other benchmarks were comparing the cost of set a = somearray[0] versus set a = LoadInteger(ht, 0, 0) whereas mine was factoring out the cost of the variable set.

No one is going to get on board with saying a bunch of O(n) operations using hashtables are a good idea, since they can be avoided by using a more suitable form of storage.

Last edited by grim001 : 11-20-2009 at 01:36 AM.
grim001 is offline   Reply With Quote
Old 11-20-2009, 02:23 AM   #11
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

Well the only O(N) method that could be more optimally done on a linkedlist is remove.

Clone -O(n) obviously.
IndexOf - O(n) since you can't know the array is sorted.
ForEach - o(n) it does say Each in there.

However, at the cost of gaining O(1) remove, you lose O(1) accessor. Which I think is the bigger loss.
weaaddar is offline   Reply With Quote
Old 11-20-2009, 03:20 AM   #12
grim001
requires vJass
 
grim001's Avatar


Code Moderator
 
Join Date: Nov 2006
Posts: 1,540

Submissions (10)

grim001 is just really nice (277)grim001 is just really nice (277)

Send a message via AIM to grim001
Default

Someone submitted a "linked hashset" a while back that had O(1) random access along with O(1) stable removal, but it was graveyarded since no one could really see a use for it.

It would make more sense for RemoveUnstable to be the default method of removal. You could rename the O(n) removal method to RemoveStable or something like that.

Basically, for this to be approved there are two main issues: the user should not need to use textmacros, and someone will need to point out realistic applications where this thing should be useful.

I know it mimics the functionality of an arraylist/vector which is very useful in C++, but it loses some of its usefulness in the WC3 environment since people are usually willing and able to trade limited storage space for better performance.
grim001 is offline   Reply With Quote
Old 11-20-2009, 03:23 AM   #13
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,729

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

No offense, I'd never use this over a private hashtable / AutoIndex.
__________________
Rising_Dusk is offline   Reply With Quote
Old 11-21-2009, 07:49 AM   #14
weaaddar
User


Respected User
 
Join Date: Apr 2002
Posts: 2,372

Submissions (3)

weaaddar has a spectacular aura about (131)

Default

Item menu doesn't care about efficiency enough to reduce the flexibility of using an arraylist. Arraylist makes sense for me, as ItemMenu need s a base thats flexible, even using something like 100 (which is way too large to be a feasible) isn't good enough as then you'd drastically cut down the amount of instantiations you'd need as your hero alone costs at least 3 arraylist just to mimic basic warcraft 3.

Its programatically simpler for me to instantiate by need. Having an integer only version is terrible as that requires creating handle boxs. And I hate that. Type-safe collections are such a godsend. Would it be better as a module? I really, really do not want an untyped collection.
Even if we had a good base type (which we don't integer is terrible), we still can't even write a simple static_cast<T>(x) method or a box class with a castAs<T>() method, as special types pointers don't actually know their own types. They only know if it they all inherit an interface which is pretty terrible considering Vjass lacks multiple inheritance of interfaces.
weaaddar is offline   Reply With Quote
Old 11-21-2009, 08:18 AM   #15
grim001
requires vJass
 
grim001's Avatar


Code Moderator
 
Join Date: Nov 2006
Posts: 1,540

Submissions (10)

grim001 is just really nice (277)grim001 is just really nice (277)

Send a message via AIM to grim001
Default

Quote:
Originally Posted by weaaddar
Item menu doesn't care about efficiency enough to reduce the flexibility of using an arraylist.
Even if you use hashtables or Table rather than arrays, it only takes a few lines of code to include your own add/remove methods within your inventory system. How often do you actually use most of the operations other than add/remove? If you can show me several examples it will work to prove your point.

Quote:
Originally Posted by weaaddar
Having an integer only version is terrible as that requires creating handle boxs. And I hate that. Type-safe collections are such a godsend.
You could instantiate every useful type using textmacros within the library, but leave the handle types commented out in a config section so that the user can uncomment them as needed. I guess that is less lame than any alternative right now, but generics/templates would really be nice here.

Quote:
Originally Posted by weaaddar
Would it be better as a module?
I don't think a module version is needed.

Last edited by grim001 : 11-21-2009 at 01:55 PM.
grim001 is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 06:18 AM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2019, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services