| 04-15-2009, 05:50 PM | #1 |
I've been experimenting with writing an indexer/hash table using the new modules stuff. I kinda like the outcome so far. You can essentially transform any struct so that it acts like a hash table. Experimental Tidy Indexer Library JASS:library TI globals private constant boolean SHOW_ERROR_MESSAGES = true private constant boolean SHOW_DEBUG_MESSAGES = true private constant integer CAPACITY = 6000 //maximum allowed number of indexed keys private constant integer TABLE_SIZE = 8191 private constant integer PROBE_JUMP = 29 //the number of slots probing skips backwards over private constant integer STATE_USED = 1 private constant integer STATE_EMPTY = 0 private constant integer STATE_GHOST = -1 endglobals private module Indexer private static integer array states private static integer array keys private static integer num_keys = 0 static method IndexGet takes integer key, boolean create returns integer local integer j = -1 local integer i = key - (key/TABLE_SIZE)*TABLE_SIZE loop //keep in range if i < 0 then set i = i + TABLE_SIZE endif //return match if found if thistype.keys[i] == key and thistype.states[i] == STATE_USED then return i endif //remember the first open slot if j == -1 and thistype.states[i] != STATE_USED then set j = i endif //exit when the probe chain ends exitwhen thistype.states[i] == STATE_EMPTY //next probe slot set i = i - PROBE_JUMP endloop if not create then return -1 endif //Fail if at capacity if thistype.num_keys >= CAPACITY then if SHOW_ERROR_MESSAGES then call BJDebugMsg("TI: Couldn't index key[" + I2S(key) + "] due to maximum capacity.") endif return -1 endif //Index the key set thistype.keys[j] = key set thistype.states[j] = STATE_USED set thistype.num_keys = thistype.num_keys + 1 debug if SHOW_DEBUG_MESSAGES then debug call BJDebugMsg("TI: Added key[" + I2S(key) + "] => " + I2S(j) + " [total:" + I2S(thistype.num_keys) + "]") debug endif return j endmethod static method IndexDestroy takes integer key returns nothing local integer i = thistype.IndexGet(key, false) if i < 0 then return endif //Clean the index set thistype.states[i] = STATE_GHOST set thistype.num_keys = thistype.num_keys - 1 debug if SHOW_DEBUG_MESSAGES then debug call BJDebugMsg("TI: Removed key[" + I2S(key) + "] => " + I2S(i) + " [total:" + I2S(thistype.num_keys) + "]") debug endif //Check if the following slot is in a probe tail set i = i - PROBE_JUMP if i < 0 then set i = i + TABLE_SIZE endif if thistype.states[i] != STATE_EMPTY then return endif //We're at the end of a probe tail; cut the tail loop set i = i + PROBE_JUMP if i >= TABLE_SIZE then set i = i - TABLE_SIZE endif exitwhen thistype.states[i] != STATE_GHOST set thistype.states[i] = STATE_EMPTY endloop endmethod endmodule private module HandleIndexer implement Indexer private static method H2I takes handle h returns integer return h return 0 endmethod static method HIndexGet takes handle key, boolean create returns integer return thistype.IndexGet(thistype.H2I(key), create) endmethod static method HIndexDestroy takes handle key returns nothing call thistype.IndexDestroy(thistype.H2I(key)) endmethod endmodule private module InstanceList static thistype array TI_list static integer TI_num = 0 integer TI_list_index method TI_ListAdd takes nothing returns nothing if this != 0 and thistype.TI_list[.TI_list_index] != this then set thistype.TI_list[thistype.TI_num] = this set .TI_list_index = thistype.TI_num set thistype.TI_num = thistype.TI_num + 1 endif endmethod method TI_ListRemove takes nothing returns nothing if this != 0 and thistype.TI_list[.TI_list_index] == this then set thistype.TI_num = thistype.TI_num - 1 set thistype.TI_list[.TI_list_index] = thistype.TI_list[thistype.TI_num] set thistype.TI_list[.TI_list_index].TI_list_index = .TI_list_index set thistype.TI_list[thistype.TI_num] = -1 set .TI_list_index = -1 endif endmethod endmodule public module HashTable implement Indexer private static thistype array vals public static method removeKey takes integer key returns nothing call thistype.IndexDestroy(key) endmethod public static method operator[]= takes integer key, thistype val returns nothing set thistype.vals[thistype.IndexGet(key, true)] = val endmethod public static method operator[] takes integer key returns thistype return thistype.vals[thistype.IndexGet(key, false)] endmethod endmodule public module HandleHashTable implement HandleIndexer private static thistype array vals public static method removeKey takes handle key returns nothing call thistype.HIndexDestroy(key) endmethod public static method operator[]= takes handle key, thistype val returns nothing set thistype.vals[thistype.HIndexGet(key, true)] = val endmethod public static method operator[] takes handle key returns thistype return thistype.vals[thistype.HIndexGet(key, false)] endmethod endmodule //! textmacro TI_CreateManagedPropertyType takes type, check public module ManagedProperty_$type$ implement HandleIndexer implement InstanceList private static thistype array vals private static integer tid = 0 private $type$ key private static method tidy takes nothing returns nothing local thistype this local $type$ key if thistype.TI_num == 0 then return endif set thistype.tid = thistype.tid + 1 if thistype.tid >= thistype.TI_num then set thistype.tid = 0 endif set this = thistype.TI_list[thistype.tid] set key = .key if $check$ then call thistype.HIndexDestroy(.key) set .key = null call .TI_ListRemove() call .destroy() endif set key = null endmethod public static method operator[] takes $type$ key returns thistype local integer i = thistype.HIndexGet(key, true) local thistype t = thistype.vals[i] if t.key == null then call thistype.tidy() call thistype.tidy() set t = thistype.create(key) set thistype.vals[i] = t set t.key = key call t.TI_ListAdd() endif return t endmethod endmodule //! endtextmacro private function isTriggerDecayed takes trigger t returns boolean local triggeraction ta = TriggerAddAction(t, function DoNothing) if ta != null then call TriggerRemoveAction(t, ta) set ta = null return false endif return true endfunction //! runtextmacro TI_CreateManagedPropertyType("unit", "GetUnitTypeId(key) == 0") //! runtextmacro TI_CreateManagedPropertyType("item", "GetItemTypeId(key) == 0") //! runtextmacro TI_CreateManagedPropertyType("destructable", "GetDestructableTypeId(key) == 0") //! runtextmacro TI_CreateManagedPropertyType("timer", "not (TimerGetElapsed(key) != 0)") //! runtextmacro TI_CreateManagedPropertyType("trigger", "isTriggerDecayed(key)") endlibrary Example Usage (Integer Hash Table) JASS:struct UnitTypeData implement TI_HashTable real mass = 1 real elasticity = 1 real collisionDamageBuffer = 10 real collisionDamageFactor = 0.2 real thrust = 0 real drag = 0.00005 real friction = 1 real collisionLiftZ = 0 boolean thrusting = false boolean rolling = false endstruct ... function init_vehicle_data takes nothing returns nothing local UnitTypeData dat //car set dat = UnitTypeData.create() set dat.mass = 4 set dat.collisionDamageBuffer = 50 set dat.collisionLiftZ = 100 set UnitTypeData['h001'] = dat //missile set dat = UnitTypeData.create() set dat.thrust = 1000 set dat.thrusting = true set dat.rolling = true set dat.friction = 5 set UnitTypeData['h000'] = dat //land mine set dat = UnitTypeData.create() set dat.collisionDamageBuffer = -100 set UnitTypeData['n000'] = dat //barrel set dat = UnitTypeData.create() set dat.mass = 4 set UnitTypeData['n001'] = dat //wagon set dat = UnitTypeData.create() set dat.mass = 8 set dat.elasticity = 0.3 set UnitTypeData['h002'] = dat endfunction Example Usage (Managed Property) JASS:struct KillCount implement TI_ManagedProperty_Unit unit u = null integer kills = 0 ///called when a new unit is passed to the library public static method create takes unit u returns thistype local KillCount this = KillCount.allocate() set .u = u return this endmethod ///called when the library finds that the unit has decayed private method onDestroy takes nothing returns nothing set .kills = 0 set .u = null endmethod endstruct ... function GetKills takes unit u returns integer return KillCount[u].kills endfunction |
