Snippet IterableHashMap

[krainert]

EDIT: Name has changed to LinkedHashMap.
In case anybody needs it:
http://krainert.com/content/linkedhashmap/
All methods except IterableHashMap.forEach, which should run in linear time relative to the amount of entries in the map, should run in constant time given that lookups in Blizz's hashtables can be done as such.
If you find any bugs, please do let me know. If you think this library is pointless, please let me know why, and I'll try to get back to it.

library LinkedHashMap

//********************************************************************************************************************************
//* LinkedHashMap
//*  
//*  ABOUT
//*   Author:   krainert
//*   Version:  2.0
//*   
//*  DESCRIPTION
//*   This library provides linked hash maps with integer keys and values
//*   Note: Entries are linked in the order in which theirs keys were added beginning with the entry with the oldest key
//*   
//*  CLASSES
//*   ======== LinkedHashMap ========
//*    -- Description
//*     An linked hash map
//*    -- Operators
//*     [integer key]                  get(key)
//*     [integer key] = integer value  put(key, value)
//*    -- Methods
//*     static LinkedHashMap           create()                                          - returns a new linked hash map
//*     integer                        revision()                                        - returns the revision of this map
//*     integer                        size()                                            - returns the number of entries in this map
//*     boolean                        has(integer key)                                  - returns whether this map contains an entry with key 'key'
//*     integer                        get(integer key)                                  - returns the value of the entry with key 'key' in this map
//*     void                           put(integer key, integer value)                   - adds an entry with key 'key' and value 'value' to this map
//*     void                           remove(integer key)                               - removes the entry with key 'key' from this map
//*     void                           clear()                                           - removes all entries from this map
//*     boolean                        hasNext(integer key)                              - returns whether a successor for the entry with key 'key' exists in this map or whether this map contains any entries if 'key' is -1
//*     integer                        next(integer key)                                 - returns the key of the successor for the entry with key 'key' in this map or the key of the first entry in this map if 'key' is -1
//*     LinkedHashMapIterator          iterator()                                        - returns an iterator for this map
//*     boolean                        forEach(LinkedHashMapIterationHandler handler)    - for every entry in the map calls 'handler' with the value of the current entry as the argument for parameter value
//*    -- Debug mode exclusive methods
//*     void                           print()                                           - prints a summary of the current state of this map
//*   ======== LinkedHashMapIterator ========
//*    -- Description
//*     An linked hash map iterator
//*    -- Methods
//*     static LinkedHashMapIterator   create(LinkedHashMap map)                         - returns a new linked hash map iterator over an linked hash map 'map'
//*     boolean                        hasNext()                                         - returns whether the underlaying map contains any more entries to be iterated
//*     integer                        next()                                            - returns the value of the next entry in the underlaying map to be iterated
//*     
//*  FUNCTION INTERFACES
//*   boolean LinkedHashMapIterationHandler(integer value)                               - handles the entry with value 'value' and returns whether any current iteration of entries of which the call to this handler is part should be terminated subsequently
//*   
//*  CHANGELOG
//*   1.0  2011-11-13  Original release
//*   2.0  2011-11-14  Library renamed from IterableHashMap to LinkedHashMap
//*                    IterableHashMap renamed to LinkedHashMap
//*                    IterableHashMapIterator renamed to LinkedHashMapIterator
//*                    IterableHashMapIterationHandler renamed to LinkedHashMapIterationHandler
//*                    Fault related debug messages disabled outside of debug mode
//*                    Debug mode exclusive method print added to LinkedHashMap
//*   
//********************************************************************************************************************************

globals
    private constant integer KEY_START = -1              //key of a virtual entry preceeding the first in the map
    private constant integer KEY_MIN   = 0               //lowest actual key allowed
    private constant integer KEY_MAX   = 2147483647      //highest actual key allowed
    private constant integer KEY_ERROR = -1              //indicates inability to return a key
    private constant integer VAL_MIN   = 0               //lowest value allowed
    private constant integer VAL_MAX   = 2147483647      //highest value allowed
    private constant integer VAL_ERROR = -1              //indicates inability to return a value
    private constant integer REV_MIN   = -2147483648     //lowest possible revision
    private constant integer REV_MAX   = 2147483647      //highest possible revision
    private constant integer REV_SPAN  = REV_MAX-REV_MIN //max number of modifications to map allowed
    private constant integer VALUE     = 0               //index of values in the hashtable
    private constant integer PREV      = 1               //index of keys for preceeding entries in the hashtable
    private constant integer NEXT      = 2               //index of keys for succeeding entries in the hashtable
endglobals

function interface LinkedHashMapIterationHandler takes integer value returns boolean

struct LinkedHashMapIterator
    private integer rev
    private LinkedHashMap map
    private integer currentKey
    
    static if debug then
        static method msg takes string message returns nothing
            call BJDebugMsg("[LinkedHashMapIterator] " + message)
        endmethod
        static method err takes string message returns nothing
            call msg("ERROR: " + message)
        endmethod
    endif
    
    static method create takes LinkedHashMap map returns thistype
        local thistype r = .allocate()
        set r.rev = map.revision()
        set r.map = map
        set r.currentKey = KEY_START
        return r
    endmethod
    
    method hasNext takes nothing returns boolean
        static if debug then
            if (.rev != .map.revision()) then
                call err("hasNext(): revision mismatch; iterator out of sync with underlying map")
                return false
            endif
        endif
        return .map.hasNext(.currentKey)
    endmethod
    
    method next takes nothing returns integer
        static if debug then
            if (.rev != .map.revision()) then
                call err("next(): revision mismatch; iterator out of sync with underlying map")
                return VAL_ERROR
            endif
            if (not(.map.hasNext(.currentKey))) then
                call err("next(): no successor; underlying map does not contain any more entries")
                return VAL_ERROR
            endif
        endif
        set .currentKey = .map.next(.currentKey)
        return .map.get(.currentKey)
    endmethod
endstruct

struct LinkedHashMap
    private hashtable map = InitHashtable()
    private integer first
    private integer last
    private integer count = 0
    private integer rev = REV_MIN
    
    static if debug then
        static method msg takes string message returns nothing
            call BJDebugMsg("[LinkedHashMap] " + message)
        endmethod
        static method err takes string message returns nothing
            call msg("ERROR: " + message)
        endmethod
    endif
    
    method operator [] takes integer key returns integer
        return .get(key)
    endmethod
    
    method operator []= takes integer key, integer value returns nothing
        call .put(key, value)
    endmethod
    
    static method create takes nothing returns thistype
        return .allocate()
    endmethod
    
    method onDestroy takes nothing returns nothing
        call FlushParentHashtable(.map)
    endmethod
    
    method revision takes nothing returns integer
        return .rev
    endmethod
    
    method size takes nothing returns integer
        return .count
    endmethod
    
    method has takes integer key returns boolean
        static if debug then
            if (key < KEY_MIN or key > KEY_MAX) then
                call err("has(" + I2S(key) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "]")
                return false
            endif
        endif
        return HaveSavedInteger(.map, key, VALUE)
    endmethod
    
    method get takes integer key returns integer
        static if debug then
            if (key < KEY_MIN or key > KEY_MAX) then
                call err("get(" + I2S(key) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "]")
                return VAL_ERROR
            endif
            if (not(HaveSavedInteger(.map, key, VALUE))) then
                call err("get(" + I2S(key) + "): unrecognized key; map does not contain referenced entry")
                return VAL_ERROR
            endif
        endif
        return LoadInteger(.map, key, VALUE)
    endmethod
    
    method put takes integer key, integer value returns nothing
        static if debug then
            if (key < KEY_MIN or key > KEY_MAX) then
                call err("put(" + I2S(key) + "," + I2S(value) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "]")
                return
            endif
            if (value < VAL_MIN or value > VAL_MAX) then
                call err("put(" + I2S(key) + "," + I2S(value) + "): invalid value; value must be in range [" + I2S(VAL_MIN) + "," + I2S(VAL_MAX) + "]")
                return
            endif
            if (.rev == REV_MAX) then
                call err("put(" + I2S(key) + "," + I2S(value) + "): revision overflow; map cannot be modified more than " + I2S(REV_SPAN) + " times")
                return
            endif
        endif
        set .rev = .rev + 1
        if (.count == 0) then
            set .count = 1
            set .first = key
            set .last  = key
        elseif (not(HaveSavedInteger(.map, key, VALUE))) then
            set .count = .count + 1
            call SaveInteger(.map, .last, NEXT, key)
            call SaveInteger(.map, key, PREV, .last)
            set .last = key
        endif
        call SaveInteger(.map, key, VALUE, value)
    endmethod
    
    method remove takes integer key returns nothing
        static if debug then
            if (key < KEY_MIN or key > KEY_MAX) then
                call err("remove(" + I2S(key) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "]")
                return
            endif
            if (not(HaveSavedInteger(.map, key, VALUE))) then
                call err("remove(" + I2S(key) + "): unrecognized key; map does not contain referenced entry")
                return
            endif
            if (.rev == REV_MAX) then
                call err("remove(" + I2S(key) + "): revision overflow; map cannot be modified more than " + I2S(REV_SPAN) + " times")
                return
            endif
        endif
        set .rev = .rev + 1
        if (.count == 1) then
            set .count = 0
        else
            set .count = .count - 1
            if (key == .first) then
                call RemoveSavedInteger(.map, LoadInteger(.map, key, NEXT), PREV)
                set .first = LoadInteger(.map, key, NEXT)
            elseif (key == .last) then
                call RemoveSavedInteger(.map, LoadInteger(.map, key, PREV), NEXT)
                set .last = LoadInteger(.map, key, PREV)
            else
                call SaveInteger(.map, LoadInteger(.map, key, PREV), NEXT, LoadInteger(.map, key, NEXT))
                call SaveInteger(.map, LoadInteger(.map, key, NEXT), PREV, LoadInteger(.map, key, PREV))
            endif
        endif
        call FlushChildHashtable(.map, key)
    endmethod
    
    method clear takes nothing returns nothing
        static if debug then
            if (.rev == REV_MAX) then
                call err("clear(): revision overflow; map cannot be modified more than " + I2S(REV_SPAN) + " times")
                return
            endif
        endif
        set .rev = .rev + 1
        set .count = 0
        call FlushParentHashtable(.map)
        set .map = InitHashtable()
    endmethod
    
    method hasNext takes integer key returns boolean
        static if debug then
            if ((key < KEY_MIN or key > KEY_MAX) and key != KEY_START) then
                call err("hasNext(" + I2S(key) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "] or " + I2S(KEY_START))
                return false
            endif
        endif
        if (key == KEY_START) then
            return .count != 0
        endif
        static if debug then
            if (not(HaveSavedInteger(.map, key, VALUE))) then
                call err("hasNext(" + I2S(key) + "): unrecognized key; map does not contain referenced entry")
                return false
            endif
        endif
        return key != .last
    endmethod
    
    method next takes integer key returns integer
        static if debug then
            if ((key < KEY_MIN or key > KEY_MAX) and key != KEY_START) then
                call err("next(" + I2S(key) + "): invalid key; key must be in range [" + I2S(KEY_MIN) + "," + I2S(KEY_MAX) + "] or " + I2S(KEY_START))
                return KEY_ERROR
            endif
        endif
        if (key == KEY_START) then
            return .first
        endif
        static if debug then
            if (not(HaveSavedInteger(.map, key, VALUE))) then
                call err("next(" + I2S(key) + "): unrecognized key; map does not contain referenced entry")
                return KEY_ERROR
            endif
            if (key == .last) then
                call err("next(" + I2S(key) + "): no successor; map does not contain any more entries")
                return KEY_ERROR
            endif
        endif
        return LoadInteger(.map, key, NEXT)
    endmethod
    
    method iterator takes nothing returns LinkedHashMapIterator
        return LinkedHashMapIterator.create(this)
    endmethod
    
    method forEach takes LinkedHashMapIterationHandler handler returns boolean
        local integer rev = .rev
        local integer key
        if (.count != 0) then
            static if debug then
                if (rev != .rev) then
                    call err("forEach(...): revision mismatch; iteration out of sync with map")
                    return false
                endif
            endif
            set key = .first
            loop
                if handler.evaluate(LoadInteger(.map, key, VALUE)) then
                    return true
                endif
                exitwhen key == .last
                set key = LoadInteger(.map, key, NEXT)
            endloop
        endif
        return false
    endmethod
    
    static if debug then
      method print takes nothing returns nothing
          local integer key
          local integer value
          local integer prev
          local integer next
          call msg("LinkedHashMap")
          call msg("    .first = " + I2S(.first))
          call msg("    .last = " + I2S(.last))
          call msg("    .count = " + I2S(.count))
          call msg("    .rev = " + I2S(.rev))
          call msg("    entries:")
          if (.count != 0) then
              set key = .first
              loop
                  set value = LoadInteger(.map, key, VALUE)
                  if (HaveSavedInteger(.map, key, PREV)) then
                      set prev = LoadInteger(.map, key, PREV)
                  else
                      set prev = -2
                  endif
                  if (HaveSavedInteger(.map, key, NEXT)) then
                      set next = LoadInteger(.map, key, NEXT)
                  else
                      set next = -2
                  endif
                  call msg("        " + I2S(key) + " -> ( " + I2S(value) + " , " + I2S(prev) + " , " + I2S(next) + " )")
                  exitwhen key == .last
                  set key = next
              endloop
          endif
      endmethod
    endif
endstruct

endlibrary

See also:
LinkedList (by the one and only Bribe)
LinkedListModule (by Dirac)

 

[Nestharus]

Post the code here using jass tags.

 

[krainert]

Post the code here using jass tags.

Right, right, you lazy bastards

 

[Laiev]

Every [ljass]BJDebugMsg[/ljass] should only display on debug mode.

This is not C, rewrite your docs.

 

[krainert]

Every [ljass]BJDebugMsg[/ljass] should only display on debug mode.

No [ljass]BJDebugMsg[/ljass] should ever be called if the programmer uses the code correctly. Wherefore exactly should I then omit them outside debug mode?
EDIT: To explicate my logic: Within my code, debug messages displayed outside of debug mode are to be considered as fault indicators. That is to say, had the implementation language been Java, I would've tossed RuntimeExceptions.

This is not C, rewrite your docs.

I find having a readable documentation syntax weight heavier than having one mimicking the syntax of the the implementation language. Should the user be unfamiliar with C-like syntax, he/she should be able to pick it up in a matter of minutes (or seconds).

 

[Nestharus]

The system's code must be featured in the system's original post.

Not lazy, just the rules : )

 

[krainert]

Not lazy, just the rules : )

I sort of chose to interpret that as allowing for specific linking in lieu of copy/paste'ing, but right you are. Thanks

 

[Laiev]

I repeat, this is not C.

And again, Debug Msg should be displayed only in debug mode.

You're slowing down your functions checking ifs all the time, this is unnecessary and some function will not inline because of your 'logic'.

 

[krainert]

I repeat, this is not C.
And again, Debug Msg should be displayed only in debug mode.
You're slowing down your functions checking ifs all the time, this is unnecessary and some function will not inline because of your 'logic'.

Good point! I seem to have overlooked concerns of efficiency. Version 1.1 disabling all debug messages outside of debug mode should be out sometime tomorrow.

 

[Bribe]

Wow this is like my LinkedList system but way more fat and ugly.

 

[krainert]

Wow this is like my LinkedList system but way more fat and ugly.

Thanks for the reference! Looks like you did a good job on the linked list.
One thing, though: Should I pay any particular heed to your picturesque wording?

 

[Bribe]

Only that I can't think of any reason you'd want to use mine let alone yours over Dirac's LinkedListModule. His is much more speedy.

Although if someone can find a practical, non-theoretical reason to use the dynamic hash linked list type structure as I have and you seem to have here, I am all ears.

 

[krainert]

Only that I can't think of any reason you'd want to use mine let alone yours over Dirac's LinkedListModule. His is much more speedy.
Although if someone can find a practical, non-theoretical reason to use the dynamic hash linked list type structure as I have and you seem to have here, I am all ears.

Hmm, yes, LLM is pretty clever. I personally prefer maintaining a rigid dichotomy between structure and elements, but apart from this mostly idealist or theoretical reason, I do believe you're right in that LLM might be (borderline) universally preferable. I'll add links for LinkedList and LLM in #1.