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.
See also:
LinkedList (by the one and only Bribe)
LinkedListModule (by Dirac)
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.
JASS:
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)