Should I add this to the Table library?

[Bribe]

Should I add this to the Table library? It simplifies the need someone may have for indexing with large parent and child keys. I thought of this after seeing some recent posts. It is mostly a wrapper, but creates a Table as needed when indexing to guarantee the same utility as you'd find in a regular hashtable (though it lacks the FlushParent function - that would prove too much to replicate). The user must manually remove each parent index prior to destroying the HashTable.

struct HashTable extends array

    method operator [] takes integer index returns Table
        local Table t = Table(this)[index]
        if t == 0 then
            set t = Table.create()
        endif
        return t
    endmethod

    method remove takes integer index returns nothing
        local Table t = Table(this)[index]
        if t != 0 then
            call t.destroy()
            call Table(this).remove(index)
        endif
    endmethod
    
    method destroy takes nothing returns nothing
        call Table(this).destroy()
    endmethod
    
    static method create takes nothing returns thistype
        return Table.create()
    endmethod

endstruct

example:

local HashTable hash = HashTable.create()
set hash['hfoo'][StringHash("poop")] = 66
set hash['hfoo'].unit[99999] = bj_lastReplacedUnit
call hash.remove('hfoo')
call hash.destroy()

 

[IcemanBo]

Looks good. I'm for it.

 

[PurgeandFire]

Seems like a good addition for those who are switching from hashtables to Table. Users tend to get stuck as soon as they realize they are limited to one index, so perhaps this would be a nice feature to motivate them to switch.

 

[Zwiebelchen]

To be honest, I was never a huge fan of table. It's not that I don't see the theoretical reasoning and advantage behind it, don't get me wrong, but I just fail to see any practical reasons to ever use it.

Hashtables are amazing. The fact that you're limited to 256 is not in any way a problem in any realistic application. People will have one or two global hashtables for standard scenarios like timer attachment. If a library or system requires it's own hashtable, what's the problem with that? Even if you - at some point - reach 20 hashtables used in your map, you will in no way ever notice any significant speed difference, let alone FPS.

So, I can not agree with Purge's comment here;
I think the reason why people don't use table more is not the limitation; it's because it adds an additional layer of inconvenience. But for what reason? Memory is cheap and Hardware just gets faster every year. In a game that hasn't changed for 10 years, I highly doubt the difference will even be measurable in any real-world application.

To me, the only real advantage of table over native Hashtables is, that I actually prefer the struct syntax over the verbose hashtable natives.

 

[edo494]

the problem is that nowadays every spell in the database that doesnt use arrays uses hashtables. Now imagine you have giant map with 15 downloaded systems and lets say 300 abilities(which is not unrealistic, some maps have much much more).

300+15>>256

 

[Zwiebelchen]

the problem is that nowadays every spell in the database that doesnt use arrays uses hashtables. Now imagine you have giant map with 15 downloaded systems and lets say 300 abilities(which is not unrealistic, some maps have much much more).

300+15>>256

This is something that can be easily enforced by a simple and effective convention for spell submissions, in which all timer attachments should be done in a global, constant hashtable that all spells share.

constant hashtable TIMER_HASH = InitHashtable()

All systems or spells that do timer attachment can just use this one global hashtable and be done with it. Timer attachment via hashtables has no chance of collision between spells, as long as every spell uses it's own timer.

If a spell needs to attach to units, a unit indexer and array variables can be used easily.


Also, the number of high quality spells in the spell section that actually use hashtables is not really that large. Most either use a timer system or a unit indexer.

 

[Bribe]

I created NewTable for many reasons. One, I needed more Table instances than Vexorian's provided, and I wanted to be able to save reals into the Table. Later on, I figured out that the negative index field could be used for projects like in my Retro system.

Making Table work for spells and systems was not my motive, but is quite a plus when I see people taking advantage of it in ways I didn't originally envision.

 

[Waffle]

Honestly the 1 thing that silently annoys me is the inability to use types other than integer as indicies.

like strings for one, must in stead use the StringHash. and it is not obvious how that is computed or if it has a possibility of colliding..

 

[PurgeandFire]

@Zwiebelchen: That's true, memory is cheap. Making small optimizations won't make a significant difference, and will probably lead to a lot of wasted time in personal projects.

But for public resources, I don't see anything wrong with encouraging good practices/standards--even if they don't make a real world difference. It is just a matter of erring on the side of caution/covering bases.

Take for example, nulling locals. Honestly, it really isn't necessary. Many of the major GUI functions do not null their references, and as we all know, there are plenty of GUI maps that will run without significant issue. Compared to forgetting to destroy objects, the leak is miniscule. The reason we do it is rather archaic in the first place--the original TimerUtils/timer attachment systems would use H2I offset by 0x100000 to manage their data. This could cause crashes if handle ID's weren't recycled, so it became common practice to null locals. Most systems today do not rely on those ID's (especially since we have hashtables), so the only reason we're doing it now is to prevent that leak (and maybe to make handle counters accurate). It is kinda funny, actually. But I still support nulling as a "good practice".

Similarly, using Table is not necessary. Chances of a person hitting the 256 limit is really low. And I have to admit, that isn't the reason I use it. I like its readability and how well it works in tandem with structs. It is very pretty, and I find it easier to review resources that use it. It isn't required for spells/systems, but it is practically required for vJASS submissions that involve hashtables. I label it as a "good practice", and I think that "layer of inconvenience" dissolves as soon as you get used to the system. But hey, that is just my opinion.

 

[edo494]

if he allowed string or potentially even any handle on top of that as [] index, then he would have to use StringHash regardless, because you can only call hashtable things with integers anyways.

Also, for handles GetHandleId, which is potentially colliding too with raw integers

 

[Waffle]

the issue is not the usage of StringHash
its that StringHash("a") and StringHash("b") and GetHandleId(u) can all map to the same value.
StringHash("a") is inferior to "a" as a key because you lose information.
in REAL(my selfish view of what a usable hashtable should do) hashtables the table stores the actual value itself and if there are hash collisions it does the right thing but just a little bit more slowly.

in jass it is impossible to have any 2 keys with the same hash value in the same hashtable ever.

now i admit a 32 bit hash makes low enough hash collision chance that im ok using StringHash for now, but some day my map is going to magically break and this annoys me to no end.

imo paving over the native api's shit is one of the most important services that a good library can provide to the community. and this part i think naggs to be paved over rly badly.

also its not like this will kill performance, hash collisions are aftterall going to almost-never happen. its just going to just make sure those rare cases your map wont implode for no good reason and it also makes expressing your code more elegant because you can say what you mean not what the api thinks you need. (i need to store a value and get it back and i need to use this object as its key..)


also @Bribe, if u don't want to do it yourself.. would you be receptive to a patch or 2?

 

[Bribe]

also @Bribe, if u don't want to do it yourself.. would you be receptive to a patch or 2?

I'm just going to copy paste it into the Table library. Did you have other changes you'd like to see before I do?

 

[Zwiebelchen]

I'm still not sure what a potential use-case scenario of string indices is.

Almost everything in WC3 has an integer substitute; handle Ids, rawcodes, even orders have an integer equivalent.
The only thing I can think of where string indices might be useful is if you want to correlate data to filepaths... which I can't find a good reason for either.

 

[Bribe]

String indices were good to avoid namespace collisions, but there are better alternatives like Table/TableArray indices which are already stored as integers.

 

[Waffle]

I'm still not sure what a potential use-case scenario of string indices is.

Almost everything in WC3 has an integer substitute; handle Ids, rawcodes, even orders have an integer equivalent.
The only thing I can think of where string indices might be useful is if you want to correlate data to filepaths... which I can't find a good reason for either.

the thing is, GetHandleID gives you the handle id, the handle id like the name suggests is basically the identity of the handle. there is a 1-1 correlation.

with strings its different, the hash is derived from a string and for each string there is always 1 hash, however, a hash can be generated from a multitude of different strings. jass2 hashtables use 32 bit hashes which does make such occurrances rather uncommon, but it does not eliminate them. unless there is some very special magic that guarantees there are no collisions (theoretically possible with that global string table..but unlikely given what the StringHash's return values look like).

say you want to have a mapping from player names to actual player instances or sth. now you can have all sorts of values used as keys and your map is eligible to randomly implode if 2 people with an unfortunate name happen to play at the same time.

the more keys in use tho the more likely this becomes..

 

[Bribe]

It is done! Table 4.0 awaits...

http://www.hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/

 

[edo494]

the issue is not the usage of StringHash
its that StringHash("a") and StringHash("b") and GetHandleId(u) can all map to the same value.
StringHash("a") is inferior to "a" as a key because you lose information.
in REAL(my selfish view of what a usable hashtable should do) hashtables the table stores the actual value itself and if there are hash collisions it does the right thing but just a little bit more slowly.

in jass it is impossible to have any 2 keys with the same hash value in the same hashtable ever.

now i admit a 32 bit hash makes low enough hash collision chance that im ok using StringHash for now, but some day my map is going to magically break and this annoys me to no end.

imo paving over the native api's shit is one of the most important services that a good library can provide to the community. and this part i think naggs to be paved over rly badly.

also its not like this will kill performance, hash collisions are aftterall going to almost-never happen. its just going to just make sure those rare cases your map wont implode for no good reason and it also makes expressing your code more elegant because you can say what you mean not what the api thinks you need. (i need to store a value and get it back and i need to use this object as its key..)


also @Bribe, if u don't want to do it yourself.. would you be receptive to a patch or 2?

You dont understand me.

Imagine this:

struct TableString
    method operator [] takes string s returns /* something */
        ...
    endmethod
endstruct

so now you can use TableString()["string"] = 5, but for him to use hashtable, he still has to do StringHash, so it doesnt matter if you type it into the index, or he does call it from his operator[], it will still have to go through StringHash.

 

[btdonald]

I've worked with HashTable
It works well.

library Track uses Table, Trigger
    globals
        private constant integer PLATFORM = 'OTip'
    endglobals
    
    struct Track extends array
        readonly static HashTable hashtable
        readonly static Table table
        readonly static Trigger anyHover
        readonly static Trigger anyClick
        readonly static Track Triggering
        
        implement AllocT
        
        static method operator [] takes trackable t returns thistype
            return table[GetHandleId(t)]
        endmethod
        
        method operator owner takes nothing returns player
            return hashtable[this.id].player[1]
        endmethod
        
        method operator path takes nothing returns string
            return hashtable[this.id].string[1]
        endmethod
        
        method operator x takes nothing returns real
            return hashtable[this.id].real[1]
        endmethod
        
        method operator y takes nothing returns real
            return hashtable[this.id].real[2]
        endmethod
        
        method operator z takes nothing returns real
            return hashtable[this.id].real[3]
        endmethod
        
        method operator facing takes nothing returns real
            return hashtable[this.id].real[4]
        endmethod
        
        method operator data takes nothing returns integer
            return hashtable[this.id][3]
        endmethod
        
        method operator data= takes integer data returns nothing
            set hashtable[this.id][3] = data
        endmethod
        
        method operator object takes nothing returns trackable
            return hashtable[this.id].trackable[this.id]
        endmethod
        
        method operator id takes nothing returns integer
            return table[this]
        endmethod
        
        method operator hoverTrigger takes nothing returns Trigger
            return hashtable[this.id][1]
        endmethod
        
        method operator clickTrigger takes nothing returns Trigger
            return hashtable[this.id][2]
        endmethod
        
        method operator enabled= takes boolean flag returns nothing
            set hashtable[this.id].boolean[1] = flag
        endmethod
        
        method operator enabled takes nothing returns boolean
            return hashtable[this.id].boolean[1]
        endmethod
        
        private static method onHover takes nothing returns boolean
            local trackable t = GetTriggeringTrackable()
            local thistype this = thistype[t]
            
            set Triggering = this
            
            if this.enabled then
                call this.hoverTrigger.fire()
            endif
            return false
        endmethod
        
        private static method onClick takes nothing returns boolean
            local trackable t = GetTriggeringTrackable()
            local thistype this = thistype[t]
            
            set Triggering = this
            
            if this.enabled then
                call this.clickTrigger.fire()
            endif
            return false
        endmethod
        
        method clearHoverActions takes nothing returns nothing
            call this.hoverTrigger.clear()
        endmethod
        
        method clearClickActions takes nothing returns nothing
            call this.clickTrigger.clear()
        endmethod
        
        method clear takes nothing returns nothing  
            call clearHoverActions()
            call clearClickActions()
        endmethod
        
        static method registerAnyHoverEvent takes boolexpr c returns TriggerCondition
            return anyHover.register(c)
        endmethod
        
        static method registerAnyClickEvent takes boolexpr c returns TriggerCondition
            return anyClick.register(c)
        endmethod
        
        method registerHoverEvent takes boolexpr c returns TriggerCondition
            return this.hoverTrigger.register(c)
        endmethod
        
        method registerClickEvent takes boolexpr c returns TriggerCondition
            return this.clickTrigger.register(c)
        endmethod
        
        method destroy takes nothing returns nothing
            call this.hoverTrigger.destroy()
            call this.clickTrigger.destroy()
            call hashtable.remove(this.id)
            set table[this.id] = 0
            set table[this] = 0
            call this.deallocate()
        endmethod
        
        static method createEx takes string path, real x, real y, real z, real facing, player p, integer data returns thistype
            local thistype this = create(path,x,y,z,facing,p)
                set hashtable[this.id][3] = data
            return this
        endmethod
        
        static method create takes string path, real x, real y, real z, real facing, player p returns thistype
            local thistype this = allocate()
            local destructable d = null
            local string s = ""
            local trackable t
            local integer id
            local Trigger trig
            
            if p != null then
                if p == GetLocalPlayer() then
                    set s = path
                endif
            else
                set s = path
            endif
            
            if z != 0 then
                set d = CreateDestructableZ(PLATFORM, x, y, z, 0, 1, 0)
            endif
            
            set t = CreateTrackable(s, x, y, facing)
            set id = GetHandleId(t)
            
            set table[id] = this
            set table[this] = id
            
            set hashtable[id].trackable[id] = t
            
            set hashtable[id].real[1] = x
            set hashtable[id].real[2] = y
            set hashtable[id].real[3] = z
            set hashtable[id].real[4] = facing
            
            set hashtable[id].player[1] = p
            set hashtable[id].boolean[1] = true // Enabled
            set hashtable[id].string[1] = path 
            
            set trig = Trigger.create(false)
            set hashtable[id][1] = trig // On Hover
            call TriggerRegisterTrackableTrackEvent(trig.trigger, t)  
            call TriggerAddCondition(trig.trigger, Filter(function thistype.onHover))
            call trig.reference(anyHover)
            
            set trig = Trigger.create(false)
            set hashtable[id][2] = Trigger.create(false) // On Click
            call TriggerRegisterTrackableHitEvent(trig.trigger, t)
            call TriggerAddCondition(trig.trigger, Filter(function thistype.onClick))
            call trig.reference(anyClick)
            
            return this
        endmethod
        
        private static method onInit takes nothing returns nothing
            set hashtable = HashTable.create()
            set table = Table.create()
            set anyHover = Trigger.create(false)
            set anyClick = Trigger.create(false)
        endmethod
    endstruct
// FUNCTION WRAPPERS
    function CreateTrack takes string path, real x, real y, real z, real facing, player p returns Track
        return Track.create(path,x,y,z,facing,p)
    endfunction
    
    function CreateTrackEx takes string path, real x, real y, real z, real facing, player p, integer data returns Track
        return Track.createEx(path,x,y,z,facing,p,data)
    endfunction
    
    function DestroyTrack takes Track t returns nothing
        call t.destroy()
    endfunction
    
    function GetTriggeringTrack takes nothing returns Track
        return Track.Triggering
    endfunction
    
//! textmacro GET_TRACK takes NAME, SUPER, TYPE
    function GetTrack$NAME$ takes Track t returns $TYPE$
        return t.$SUPER$
    endfunction
//! endtextmacro

//! runtextmacro GET_TRACK("Data","data", "integer")    
//! runtextmacro GET_TRACK("X","x", "real")    
//! runtextmacro GET_TRACK("Y","y", "real")    
//! runtextmacro GET_TRACK("Z","z", "real")
//! runtextmacro GET_TRACK("Facing","facing", "real")
//! runtextmacro GET_TRACK("Path","path", "string")                
//! runtextmacro GET_TRACK("Owner","owner", "player")
//! runtextmacro GET_TRACK("Object","object", "trackable")
//! runtextmacro GET_TRACK("HoverTrigger", "hoverTrigger", "Trigger")  
//! runtextmacro GET_TRACK("ClickTrigger", "clickTrigger", "Trigger")

    function SetTrackData takes Track t, integer data returns nothing
        set t.data = data
    endfunction
    
    function IsTrackEnabled takes Track t returns boolean
        return t.enabled
    endfunction
    
    function EnableTrack takes Track t returns nothing
        set t.enabled = true
    endfunction
    
    function DisableTrack takes Track t returns nothing
        set t.enabled = false
    endfunction

//! textmacro REGISTER_TRACK takes NAME    
    function RegisterAnyTrack$NAME$Event takes boolexpr c returns TriggerCondition
        return Track.registerAny$NAME$Event(c)
    endfunction
    
    function RegisterTrack$NAME$Event takes Track t, boolexpr c returns TriggerCondition
        return t.register$NAME$Event(c)
    endfunction
    
    function ClearTrack$NAME$Actions takes Track t returns nothing
        call t.clear$NAME$Actions()
    endfunction
//! endtextmacro

//! runtextmacro REGISTER_TRACK("Hover")
//! runtextmacro REGISTER_TRACK("Click")

    function ClearTrackActions takes Track t returns nothing
        call t.clear()
    endfunction
endlibrary

 

[PurgeandFire]

@edo: It is fine if it has to go through StringHash. It just needs to be able to handle collisions. Since hashtables have 2 keys, it is pretty easy to form a separate chaining hashtable... i.e. you can use StringHash(str) as a parent key, and then have a child key 0 and store the data. If there is a collision, change the child key to 1.

The only annoying part is destroying.

 

[Zwiebelchen]

the thing is, GetHandleID gives you the handle id, the handle id like the name suggests is basically the identity of the handle. there is a 1-1 correlation.

with strings its different, the hash is derived from a string and for each string there is always 1 hash, however, a hash can be generated from a multitude of different strings. jass2 hashtables use 32 bit hashes which does make such occurrances rather uncommon, but it does not eliminate them. unless there is some very special magic that guarantees there are no collisions (theoretically possible with that global string table..but unlikely given what the StringHash's return values look like).

say you want to have a mapping from player names to actual player instances or sth. now you can have all sorts of values used as keys and your map is eligible to randomly implode if 2 people with an unfortunate name happen to play at the same time.

the more keys in use tho the more likely this becomes..

I know about stringhash. I was not asking for an explanation why stringhash is bad. I asked for a potential use-case scenario of when you ever need to index a table via a string.

 

[Waffle]

any time you want to look up something using a player name for instance, also i use it for a command system and theres a gazillion other uses..

string operations are so darn common i really cant believe you've never run in to a single use case..

 

[Xonok]

any time you want to look up something using a player name for instance, also i use it for a command system and theres a gazillion other uses..

Players have other identifying features. Since hashtables don't persist through sessions you can easily loop from 0-11 and thus know which player has a certain name. Then you can use their player index.
How is that complicated compared to writing a new way of using hashtables?

 

[Waffle]

we've already got
1) a hashtable that uses strings as keys
and
2) an augmented version of StringHash() that guarantees no collisions for distinct strings.
3) they are both quite simple little scripts, and once the api is flushed out will prolyl be public.

..
and furthermore just because the example i came up with in like 3 sec may not impress you, you rly must be unimaginative if you need me to provide you with all the possible uses before you will admit that such a resource can be benefitial.

 

[Xonok]

In the end it's just better to use a separate hashtable for this.

 

[Waffle]

and how exactly is that solving anything?

 

[Zwiebelchen]

any time you want to look up something using a player name for instance, also i use it for a command system and theres a gazillion other uses..

string operations are so darn common i really cant believe you've never run in to a single use case..

What does this command system do and why do you need string indices for it?

The reason I'm asking this is because all uses I could come up with have an alternative solution that is not even more complicated to implement. And probably even faster, because strings are slow as fuck.

If there are a gazillion of other uses, then it should be easy to come up with at least 5 convincing examples, right? You mentioned one (that is non-descriptive without further explanation).


The only real application I could come up with after almost 10 minutes of brainstorming was an Ascii2Int snippet which is used in most save/load systems to convert base36 into base2 integers.

 

[Waffle]

you dont need integers to program just use a bunch of bytes, it will be fast as fuck

not correct? who cares?
undefined behaviour? but its fast!
does not express the problem domain even remotely? but its fast!
not readable? not my problem, i'm right listen to me do as i say!

and thats how you end up with https://get.adobe.com/flashplayer/ fast as fuck, but has an 0day every 5 minutes (really tho, no less than 2 this past week btw)

also if my input is a string then i can't really avoid touching a string can i.

and so you are telling me, in stead of touching it once i should go and make a for-loop against all possible matches??(i cant use a hashtable thus i must use an array) how is that any faster?

 

[Xonok]

I fail to see the problem that you're trying to solve. So far you've provided one example and it was easy to rebuke. (If you really want to link things to players, why the hell would you use their name instead of index?)

 

[edo494]

you dont need integers to program just use a bunch of bytes, it will be fast as fuck

not correct? who cares?
undefined behaviour? but its fast!
does not express the problem domain even remotely? but its fast!
not readable? not my problem, i'm right listen to me do as i say!

0. You cant use bytes in Jass

1. using integers is no less incorrect than using strings
2. I fail to see how integers bring undefined behaviour into the play. This is not C++, the only undefined behaviour you have in Jass is using ConvertXX functions out of bounds.
3. I fail to see how integers do not express the domain problem.
4. Your code can be complete, utter shit when using strings, same with integers. Readability really goes down to the object between keyboard and the chair, not to data type

 

[Waffle]

@Xonox you havent rebucked shit. if i say want to get a player instance from a chat string then the input is a string is it not and a lookup table is the most natural solution. the fact you can represent a player as an integer is irrelevant as the commands take colors or player names as input.

@edo you fail to see is that that post was not about some implementation, its about how some people suffer from i-havent-used-it-thus-its-useless and because of this they inhibit the development of new techniques that might better express some problem domains. the fact that you think that something might not express my problem domain well is actually irrelevant since you have no understanding of my probelm and thus you cannot make an informed judgement. also you ask for an example and i have provided examples, and example is something thats sopposed to be easily understandable and representative of the general problem, aslo easy. to be a real life one is not a requirement of an example. you attack some toy examples and then tout it as a big victory but you never even take the time to understand what the issue is. how can i even take you seriously?!

 

[Xonok]

It is you that's trying to prove a point. So far you've failed to do so. Whether it's because me and edo are stupid or because you didn't explain properly is irrelevant.

 

[Bribe]

Ok guys you've made your points please take this off topic somewhere else - preferably to oblivion. There are good points on both sides, but you're bashing Waffle before even considering what s/he's coded. There are plenty of times you're working with strings, for example special effects

 

[edo494]

you know, you could write proper example for using strings as indexes instead of arrays, instead of writing 5 line response.

Judgment can only be as informed, as the post/idea it is judging.

I have yet to see an example of yours in this thread

Edit: I posted this on page 2, didnt see the 2 newest posts.

I dont want to attack or disregard anyone, just want some example that would make writing collision-free string index struct worth writing

 

[Waffle]

"I dont want to attack or disregard anyone, just want some example that would make writing collision-free string index struct worth writing"

you do realise that string indexing that is not guaranteed to be collision free is equivalent to just picking a value at random..

 

[edo494]

and who here doesnt understand...

The time it takes to write such resource should be justifiable, and you propsed it, so you should/are yet to propose some real example(doesnt need to be code, algorithm will do) where not using strings as indexes would make it either too hard to create, or make it too unreadable

 

[Zwiebelchen]

and who here doesnt understand...

The time it takes to write such resource should be justifiable, and you propsed it, so you should/are yet to propose some real example(doesnt need to be code, algorithm will do) where not using strings as indexes would make it either too hard to create, or make it too unreadable

As I said; the first thing that comes to my mind would be a Char2Int table.

But you can probably do that via StringHash aswell, as the number of valid ascii codes is not large enough for StringHash to collide.

Waffle has a point with chat commands, though.

Basicly, a reverse lookup table for GetPlayerName that returns the specific player instance based on the name.
... which is kind of useless in reality as you can also just loop through all players and computing time isn't really a critical factor here, but yeah, it's a legit example.