Updated::
Dictionary is an associative array, like Vexorian's table. Unlike Table however, Dictionary keeps track of elements stored in it and provides a means to iterate through the collection. This is basically a linked list and a hashtable combined. There is a readonly array struct that will inline, and doesn't allow mutation.
The macro is instanced currently for 3 types
Dict_integer
Dict_string
Dict_handle // kind of useless.
Thankfully it is a macro so you can instance your own. just at the bottom of Dictionary library instance to your hearts content. The macro takes 3 parameters
//! runtextmacro DictTemplate (T,HashFunc,DefaultVal)
where T is the type, HashFunc is a function to generate a hash, and defaultVal is the default for the type.
Another included type is Set. Set is like a unitgroup but for any type T. Set provides a readonly node as well, and a fast contain operator. It too is all constant time operations except for its clear op.
More text in the script header.
And here is a usage example as to why you might try some of the features.
TryGetValue is basically a contains and fetch in the same go. It is perfect for usage in memoization, as sometimes 0 is an acceptable value, and testing for 0 is not inductive as to whether this was because the dictionary failed to retrieve, or because thats what was stored there.
Here is fibonacci. You can try running the Fib method which has exponential runtime, and quickly blow out your op limit, or you can use the faster MemoizedFib which can compute any value in a worse case of o(n).
Also demonstrated is how to enumerate through the values of the dictionary. Using the for loop feature of zinc. Its slightly miserable and a bit long, but it will compile cleanly to some nice jass.
You'll note that you don't have to destroy the readonly node at the end, you are done as it is an array struct and isn't "instanced".
Dictionary is an associative array, like Vexorian's table. Unlike Table however, Dictionary keeps track of elements stored in it and provides a means to iterate through the collection. This is basically a linked list and a hashtable combined. There is a readonly array struct that will inline, and doesn't allow mutation.
The macro is instanced currently for 3 types
Dict_integer
Dict_string
Dict_handle // kind of useless.
Thankfully it is a macro so you can instance your own. just at the bottom of Dictionary library instance to your hearts content. The macro takes 3 parameters
//! runtextmacro DictTemplate (T,HashFunc,DefaultVal)
where T is the type, HashFunc is a function to generate a hash, and defaultVal is the default for the type.
Another included type is Set. Set is like a unitgroup but for any type T. Set provides a readonly node as well, and a fast contain operator. It too is all constant time operations except for its clear op.
More text in the script header.
JASS:
//! zinc
// Thanks goes to Jesus4lyf for his clever optimizations and showing
// the light of typecast abuses.
// Also thanks to Vexorian for Zinc and JassHelper. Zinc makes writing Jass
// enjoyable and quick.
//=============================================================================
// Dict_T
//=============================================================================
// Dictionary is an associative array that keeps track of elements
// stored in the array. All its operations are o(1) unless stated otherwise.
// Hashtable calls # are displayed in [] next to the method description.
// Property Index::
// ----------------
// Count->integer
// returns number of elements in this dictionary.
//
// Value->integer
// returns the last value retrieved by the TryGetValue method.
//
// operator[T key]->integer [1 ht load]
// reutrns the Value associated with this key. 0 if it fails.
//
// operator[T key]=integer [max 1 ht loads,1 ht save]
// associate key with value in the dictionary.
// Method Index::
// --------------
// Contains(T key)->boolean [1 ht load]
// returns if this key is in the dictionary.
//
// TryGetValue(T key)->boolean [1 ht load]
// returns if this key is in the dictionary, and sets Value to the
// the value associated with the key.
//
// Add(T key,integer value)->boolean [max 1 ht load, 1 ht save]
// tries to add key,value to the dictionary, if and only if the key
// isn't already part of the collection. Returns true if key was added.
//
// Remove(T key)->integer [max 1 ht remove, 1 ht load]
// tries to remove this key from the collection. Returns the value
// that was associated if it succeeded, 0 if it failed.
//
// GetReadOnlyNode()->RO_DictNode_T
// returns a new read only dict Node see further documentation For
// the enumeration paradigm (it kind of sucks!)
//
// Clear() (O(n) operation) [1 ht child hashtable flush]
// Clears the collection of all elements in it.
//=============================================================================
// Set_T
//=============================================================================
// Set is a uniqueness enforcing collection structure. Only one
// instance of any object can be stored in the collection at a time.
// It is like a unitgroup but for any type T that you can instance the macro for.
// Internally it is a thin-wrapper for a dictionary, and thus should inline
// around the calls to dictionary.
// Property Index::
// ----------------
// Count->integer
// returns number of elements in this dictionary.
//
// Method Index::
// --------------
// Contains(T object)->boolean [1 ht load]
// returns if this object is in the dictionary.
//
// Add(T object)->boolean [max 1 ht load, 1 ht save]
// tries to add object to the dictionary, if and only if the object
// isn't already part of the set. Returns if the object was added.
//
// Remove(T object)->boolean [max 1 ht remove, 1 ht load]
// tries to remove object from the collection. Returns if the
// the object was removed.
//
// GetReadOnlyNode()->RO_SetNode_T
// returns a new read only set Node see further documentation For
// the enumeration paradigm (it kind of sucks!)
//
// Clear() (O(n) operation) [1 ht child hashtable flush]
// Clears the collection of all elements in it.
//=============================================================================
// RO_Set/DictNode_T
//=============================================================================
// Read only set/dict node is a safe way to enumerate through a collection,
// it is high performance as it will inline, and doesn't use any hashtable
// calls. They are also array structs meaning that no create or destroy
// method should ever be called (may also be an error!)
//Unfortunately, the enumeration paradigm is pretty awful
// Zinc -- this is actually pretty clean to be honest this is almost
// as good as it gets!
/* here for copy and paste usage::
RO_DictNode_integer node;
integer key;
integer value;
for(node = dict.GetReadOnlyNode(); node != dict; node = node.Next)
{
key = node.Key;
value = node.value;
// code goes here
}
*/
// Vjass -- this ofcourse is much uglier
/*
local RO_DictNode_integer node
local integer key
local integer value
loop
exitwhen node == dict
set key = node.Key
set value = node.Value
// code goes here
set node = node.Next
endloop
*/
// RO_DictNode_T Property Index::
// ==============================
// Key-> T
// returns the key at this point in the enumeration.
// Value -> integer
// returns the value at this point in the enumeration.
// RO_SetNode_T Property Index::
// =============================
// Object -> T
// returns the object stored at this point in the enumeration.
// Shared Properties::
// ====================
// Next -> thistype
// returns the next node in a safe readonly wrapper.
//=============================================================================
library Dictionary
{
hashtable Table = InitHashtable();
//! textmacro DictTemplate takes T,HashFunc,DefaultVal
// Node is private, and should stay that way.
// A consumer should never have to know about this class.
struct Node_$T$
{
thistype Next;
thistype Prev;
$T$ Key;
integer Value;
static method create($T$ key,integer value)->thistype
{
thistype n = thistype.allocate();
n.Key = key;
n.Value = value;
return n;
}
}
public struct RO_SetNode_$T$[]
{
method operator Next()->thistype
{
return Node_$T$(this).Next;
}
method operator Object()->$T$
{
return Node_$T$(this).Key;
}
}
public struct RO_DictNode_$T$[]
{
method operator Next()->thistype
{
return Node_$T$(this).Next;
}
method operator Key()->$T$
{
return Node_$T$(this).Key;
}
method operator Value()->integer
{
return Node_$T$(this).Value;
}
}
public struct Dict_$T$
{
private integer m_count;
private method Fetch($T$ key)->Node_$T$
{
return LoadInteger(Table,integer(this),$HashFunc$(key));
}
method Contains($T$ key)->boolean
{
return Fetch(key) > 0;
}
private method operator Prev()->Node_$T$
{
return Node_$T$(this).Prev;
}
private method operator Prev=(Node_$T$ node)
{
Node_$T$(this).Prev = node;
}
private method operator Next()->Node_$T$
{
return Node_$T$(this).Next;
}
method operator Count()->integer
{
return m_count;
}
method operator Value()->integer
{
return Node_$T$(this).Value;
}
private method operator Value=(integer value)
{
Node_$T$(this).Value = value;
}
private method Insert($T$ key,integer value)
{
integer ung = 6;
Node_$T$ node = Node_$T$.create(key,value);
Prev.Next = node;
node.Next = this;
Prev = node;
m_count+=1;
SaveInteger(Table,integer(this),$HashFunc$(key),node);
}
method operator[]($T$ key)->integer
{
return Fetch(key).Value;
}
method operator[]=($T$ key,integer value)
{
Node_$T$ node = Fetch(key);
if(node == 0)
{
Insert(key,value);
return;
}
node.Value = value;
}
method TryGetValue($T$ key)->boolean
{
Node_$T$ node = Fetch(key);
this.Value = node.Value;
return node > 0;
}
method Add($T$ key,integer value)->boolean
{
Node_$T$ node;
if(Contains(key)) return false;
Insert(key,value);
return true;
}
method Remove($T$ key)->integer
{
Node_$T$ node = Fetch(key);
integer retVal = node.Value;
if(node != 0)
{
RemoveSavedInteger(Table,integer(this),$HashFunc$(key));
node.Prev.Next = node.Next;
node.Next.Prev = node.Prev;
node.destroy();
m_count-=1;
}
return retVal;
}
method GetReadOnlyNode()->RO_DictNode_$T$
{
return RO_DictNode_$T$(Next);
}
method Clear()
{
Node_$T$ node = this.Next;
while(node != this)
{
node.destroy();
node = node.Next;
}
FlushChildHashtable(Table,integer(this));
m_count = 0;
}
static method create()->thistype
{
Node_$T$ n = Node_$T$.create($DefaultVal$,0);
n.Next = n;
n.Prev = n;
return n;
}
private method onDestroy()
{
Clear();
}
}
public struct Set_$T$
{
method operator Count()->integer
{
return Dict_$T$(this).Count;
}
method Add($T$ object)->boolean
{
return Dict_$T$(this).Add(object,-1);
}
method Remove($T$ object)->boolean
{
return Dict_$T$(this).Remove(object) == -1;
}
method Contains($T$ object)->boolean
{
return Dict_$T$(this).Contains(object);
}
method Clear()
{
Dict_$T$(this).Clear();
}
private method onDestroy()
{
Dict_$T$(this).destroy();
}
method GetReadOnlyNode()->RO_SetNode_$T$
{
return RO_SetNode_$T$(Node_$T$(this).Next);
}
static method create()->thistype
{
return Dict_$T$.create();
}
}
//! endtextmacro
//! runtextmacro DictTemplate("integer","","0")
//! runtextmacro DictTemplate("handle","GetHandleId","null")
//! runtextmacro DictTemplate("string","StringHash","null")
}
//! endzincTryGetValue is basically a contains and fetch in the same go. It is perfect for usage in memoization, as sometimes 0 is an acceptable value, and testing for 0 is not inductive as to whether this was because the dictionary failed to retrieve, or because thats what was stored there.
Here is fibonacci. You can try running the Fib method which has exponential runtime, and quickly blow out your op limit, or you can use the faster MemoizedFib which can compute any value in a worse case of o(n).
Also demonstrated is how to enumerate through the values of the dictionary. Using the for loop feature of zinc. Its slightly miserable and a bit long, but it will compile cleanly to some nice jass.
You'll note that you don't have to destroy the readonly node at the end, you are done as it is an array struct and isn't "instanced".
JASS:
library fib
{
Dict_integer Dict;
public function Fib(integer n)->integer
{
if(n < 2) return n;
return Fib(n-1)+Fib(n-2);
}
public function MemoizedFib(integer n)->integer
{
if(Dict.TryGetValue(n)) return Dict.Value;
if(n < 2)
{
Dict[n] = n;
return n;
}
Dict[n] = MemoizedFib(n-1)+MemoizedFib(n-2);
return Dict[n];
}
function onInit()
{
RO_DictNode_integer node;
Dict = Dict_integer.create();
BJDebugMsg(I2S(MemoizedFib(15)));
for(node = Dict.GetReadOnlyNode(); node != Dict; node = node.Next)
{
BJDebugMsg("key= " + I2S(node.Key) + "value= " + I2S(node.Value));
}
}
}
