Making a hash map struct...

[krainert]

Greetings,

I'm currently working on a hash map struct, but I'm not sure whether I should base it on a hashmap or two arrays of size 8191. I wish to be able to efficiently iterate through all mappings as I intend to provide a for-each functionality, but I'm not sure which is more efficient: always taking up space for two arrays with capacity 8191 or always iterating through all possible key values. Both seem pretty bad. Also: Is it really true that array capacities cannot be dynamically defined - must they really be set when the array is declared? I suppose a compromise would be having both a hashtable and one array of size 8191 where the array stores every key in the hashtable with an assigned value. This would cut the overhead in half while rendering the tedious iteration through all possible keys superfluous, but it sure as hell isn't pretty.

Thanks.

 

[Accname]

Of course you have to initialize an array with a set size. Do you know what arrays are? There is no point for having them if they got dynamic size.

 

[krainert]

Of course you have to initialize an array with a set size. Do you know what arrays are? There is no point for having them if they got dynamic size.

*Cough* Java *Cough* C# *Cough* JavaScript even (the capacities of arrays in the latter are actually fully dynamic). Not every language has to be C++
Can anyone confirm that there is no possible way to declare an array variable in vJass without simultaneously specifying its capacity?

 

[Accname]

*Cough* Java *Cough* C# *Cough* JavaScript even (the capacities of arrays in the latter are actually fully dynamic). Not every language has to be C++
Can anyone confirm that there is no possible way to declare an array variable in vJass without simultaneously specifying its capacity?

Then it isnt an array.
An array needs to have a set size in order to be fully efficient.
Containers with indices and dynamic size are vectors, but even those work the same as arrays but with a buffer. That means they have a larger size set from the beginning and when this size is reached they will copy their entire content to a new position with an even larger capacity. This process is alot of work for the computer which should be avoided whenever possible.

This is still scripting a computer programm and not magic in wonderland.

Getting bit off-topic though.

 

[Solmyr]

Then it isnt an array.
An array needs to have a set size in order to be fully efficient.
Containers with indices and dynamic size are vectors, but even those work the same as arrays but with a buffer. That means they have a larger size set from the beginning and when this size is reached they will copy their entire content to a new position with an even larger capacity. This process is alot of work for the computer which should be avoided whenever possible.

You have obviously never heard of dynamic arrays.

Can anyone confirm that there is no possible way to declare an array variable in vJass without simultaneously specifying its capacity?

Nope, unfortunately, there isn't.

 

[Accname]

You have obviously never heard of dynamic arrays.

Did you read that article yourself? That was what i told him.
Those "dynamic arrays" or vectors have a fixed capacity as well, and when this capacity is reached they will just copy themself into an even bigger space. But this process is very time consuming.

 

[krainert]

Actually, I'm not looking for dynamic array functionality; what I need is any static/dynamic sized array the capacity of which is not determined upon declaration albeit possibly specified upon initialization.

Another question: hashmaps are dynamically sized, am I right? Is there a significant overhead to their use compared to that of arrays? I'm considering doing the following:
Have one hashtable mapping from integer keys to integer values.
Have one hashtable mapping from growing indices to keys and values in the first hashtable.
Continuously maintain both arrays, keeping them in sync.
Use the first hashtable for key-to-value referencing.
Use the second hashtable during iterations over entry pairs.
Perhaps introduce a third hashtable allowing efficient value-to-key referencing? (EDIT: Whoa, no, this should be handled in a separate class using two simple hash maps if at all)

I suppose it all depends on the overhead of hashtables.

 

[Accname]

You can do all that in a single hashtable, theoretically you never need a second one.

But maybe you might try to tell us what exactly you want to do in the first place. Maybe some other user already has a system for whatever you are trying to accomplish.

 

[krainert]

Unrelated question: Structs are referenced as integers. Which values can these take when JassHelper does its thing? Are struct references always positive integers? Can they be 0? Negative?
EDIT: I've asked this here: http://www.thehelper.net/forums/showthread.php/168540-Can-vJass-structs-have-integer-value-0

EDIT:

You can do all that in a single hashtable, theoretically you never need a second one.

I assume hashtable can do lookups faster than I can if I have to iterate through n elements in the process, amrite? In that case having supporting hashtables would improve efficiency.

But maybe you might try to tell us what exactly you want to do in the first place. Maybe some other user already has a system for whatever you are trying to accomplish.

I'm making a suite of integer-only hash tables.
To begin with I'm making a simple one - basically a hashtable which one column and a much, much simpler API (has, load, save, remove, clear, and size).
Then I'll add an interable version, that is a hash table that supports efficient for-each loops using closures. This'll contribute just a few methods (forEach, efficient equals, efficient clone) to the API of the simple hash table.
Then I'll add a two-way version. This'll contribute value-based duplicates for pretty much every method (examples: value-based has, load, and save) in the simple hash table's API.
Finally I'll add an iterable two-way version - just for the heck of it. As far as I can see, the most efficient way to do this one is with three hashtables: key-value, value-key, and index-key,value. This one will extend the first two-way hash table as well as the first iterable one and add two methods (forEachKey and forEachEntry) on top of that.

 

[krainert]

Here we go:

library HashMaps

globals
    private constant integer MAX_MAPPINGS   = 8191
    private constant integer DEF_RETURN_VAL = -1
endglobals

function interface IterationHandler takes integer value returns boolean
function interface ReverseIterationHandler takes integer key returns boolean
function interface TwoWayIterationHandler takes integer key, integer value returns boolean

interface Map
    public method has takes integer key returns boolean
    public method load takes integer key returns integer
    public method save takes integer key, integer value returns boolean
    public method remove takes integer key returns boolean
    public method clear takes nothing returns boolean
    public method size takes nothing returns integer
endinterface

interface IterableMap
    //Map
    public method has takes integer key returns boolean
    public method load takes integer key returns integer
    public method save takes integer key, integer value returns boolean
    public method remove takes integer key returns boolean
    public method clear takes nothing returns boolean
    public method size takes nothing returns integer
    //IterableMap
    public method forEach takes IterationHandler handler returns boolean
endinterface

interface TwoWayMap
    //Map
    public method has takes integer key returns boolean
    public method load takes integer key returns integer
    public method save takes integer key, integer value returns boolean
    public method remove takes integer key returns boolean
    public method clear takes nothing returns boolean
    public method size takes nothing returns integer
    //TwoWayMap
    public method hasValue takes integer value returns boolean
    public method loadValue takes integer value returns integer
    public method saveValue takes integer value, integer value returns boolean
    public method removeValue takes integer value returns boolean
    public method keyOf takes integer value returns integer
endinterface

interface IterableTwoWayMap
    //Map
    public method has takes integer key returns boolean
    public method load takes integer key returns integer
    public method save takes integer key, integer value returns boolean
    public method remove takes integer key returns boolean
    public method clear takes nothing returns boolean
    public method size takes nothing returns integer
    //IterableMap
    public method forEach takes IterationHandler handler returns boolean
    //TwoWayMap
    public method hasValue takes integer value returns boolean
    public method loadValue takes integer value returns integer
    public method saveValue takes integer value, integer value returns boolean
    public method removeValue takes integer value returns boolean
    public method keyOf takes integer value returns integer
    //IterableTwoWayMap
    public method forEachKey takes ReverseIterationHandler handler returns boolean
    public method forEachEntry takes TwoWayIterationHandler handler returns boolean
endinterface

struct HashMap extends Map
    private hashtable map   = InitHashtable()
    private integer   count = 0
    
    method operator [] takes integer key returns integer
        return .load(key)
    endmethod
    
    method operator []= takes integer key, integer value returns nothing
        call .save(key, value)
    endmethod
    
    method operator < takes thistype other returns boolean
        return .count < other.count
    endmethod
    
    public method has takes integer key returns boolean
        return HaveSavedInteger(.map, key, 0)
    endmethod
    
    public method load takes integer key returns integer
        if .has(key) then
            return LoadInteger(.map, key, 0)
        else
            return DEF_RETURN_VAL
        endif
    endmethod
    
    public method save takes integer key, integer value returns boolean
        if .has(key) then
            call SaveInteger(.map, key, 0, value)
            return true
        else
            if .size != MAX_MAPPINGS then
                call SaveInteger(.map, key, 0, value)
                set .count = .count + 1
            else
                call BJDebugMsg("HashMap error: attept to create mapping from " + I2S(key) + " to " + I2S(value) + " thereby exceeding the mapping limit being " + I2S(MAX_MAPPINGS))
            endif
            return false
        endif
    endmethod
    
    public method remove takes integer key returns boolean
        if .has(key) then
            call FlushChildHashtable(.map, key)
            set .count = .count - 1
            return true
        else
            return false
        endif
    endmethod
    
    public method clear takes nothing returns boolean
        if .count != 0 then
            call FlushParentHashtable(.map)
            set .map = InitHashtable()
            set .count = 0
            return true
        else
            return false
        endif
    endmethod
    
    public method size takes nothing returns integer
        return .count
    endmethod
endstruct

struct IndexedMap extends IterableMap
    private Map       map   = HashMap.create()
    private hashtable index = InitHashtable()
    
    method operator [] takes integer key returns integer
        return .load(key)
    endmethod
    
    method operator []= takes integer key, integer value returns nothing
        call .save(key, value)
    endmethod
    
    method operator < takes thistype other returns boolean
        return .map.size() < other.map.size()
    endmethod
    
    public method has takes integer key returns boolean
        return .map.has(key)
    endmethod
    
    public method load takes integer key returns integer
        return map.load(key)
    endmethod
    
    public method save takes integer key, integer value returns boolean
        if map.save(key, value) then
            call SaveInteger(.index, .nextIndex(), 0, key)
            return true
        else
            return false
        endif
    endmethod
    
    public method remove takes integer key returns boolean
        if map.has(key) then
            call map.remove(key)
            call FlushChildHashtable(.index, .keyIndex(key))
            return true
        else
            return false
        endif
    endmethod
    
    public method clear takes nothing returns boolean
        if map.size() != 0 then
            call map.clear()
            call FlushParentHashtable(.index)
            set .index = InitHashtable()
            return true
        else
            return false
        endif
    endmethod
    
    public method forEach takes IterationHandler handler returns boolean
        local integer size = map.size()
        local integer value
        local integer i = 0
        loop
            exitwhen i == size
            if HaveSavedInteger(.index, i, 0) then
                set value = map.load(LoadInteger(.index, i, 0))
                if value != DEF_RETURN_VAL then
                    if handler.evaluate(value) then
                        return true
                    endif
                endif
            endif
            set i = i + 1
        endloop
        return false
    endmethod
    
    public method size takes nothing returns integer
        return .map.size()
    endmethod
    
    private method nextIndex takes nothing returns integer
        local integer size = map.size()
        local integer i = 0
        loop
            exitwhen i == size
            if not(HaveSavedInteger(.index, i, 0)) then
                return i
            endif
            set i = i + 1
        endloop
        return size
    endmethod
    
    private method keyIndex takes integer key returns integer
        local integer current
        local integer i = 0
        loop
            set current = LoadInteger(.index, i, 0)
            if current == key then
                return i
            endif
            set i = i + 1
        endloop
        return 0
    endmethod
endstruct

endlibrary

An issue, though: I get four of these errors: "Symbol value multiply defined". Any clues?
Note: No structs currently implement TwoWayMap or IterableTwoWayMap.

Unrelated: Is there really no way to make one interface extend another?