AssociativeArray/DataStructure

Associative Array Data Scructures

Associative arrays are implemented as an unbalance binary search tree (BST). Thus there is a node type and a tree type. Both are Unreal classes (having the nodes be objects makes it easy to declare new ones on the fly).

AssciativeArrrayNode

A tree is built up of linked nodes. This is the node class with "pointers" at left and right subtrees as well as the parent node.

class AssociativeArrayNode
    extends Object;
/* A binary search tree (BST) node. Nodes are ordered on their key; the
   key must be a type that supports < and ==. Associated with each key is a
   value; value can be any arbitrary type that supports assignment.

   This is really just a struct (no member functions). A class is used to
   permit the new operator in UnrealScript to work correctly. 
*/
var string key;
var string value;
var AssociativeArrayNode left_child, right_child, parent;

defaultproperties 
{
  parent=None
  left_child=None
  right_child=None
}

AssociativeArray

This is the implementation of the BST.

class AssociativeArray
    extends Object;
/* Associative Array: Demonstration of operator overloading using UnrealScript.

   Inspired by DynamicArray code on the BeyondUnreal Wiki:
   http://wiki.beyondunreal.com/wiki/Dynamic_Array

   Uses a simple binary tree to hold pairs of strings with other strings;
   the key and data types could both be changed with little pain.
*/


/* Reference to the actual data structure. Under the hood, the associative
   array is a binary search tree (BST). Should search time prove a
   limitation, this proof of concept could be augmented with a smarter data
   structure (red-black tree, hash table, etc.).
*/
var AssociativeArrayNode root;

/* Since end() returns an iterator with the same value every time, it should
   be kept around after its first creation.
*/
var private AssociativeArrayIterator end_;


/* The number of elements in the associative array. This is a private field to
   limit access to it to the getLength function. Performance could be enhanced
   by making the member data publically visible if all clients of associative
   array could be trusted not to change it.
*/
var private int length;

/* return the number of elements in the associative array. */
function int getLength()
{
  return length;
} // getLength

/* insert a key/value pair into the associative array. */
function insert(coerce string key, string value) 
{
  p_insert(key, value, root);
} // insert

/* return the value matching the given key, if one exists; returns "" and
   leaves the associative array unchanged if there is no entry with the
   given key. Since "" could be a legal value, use count to determine
   whether or not a key is in the associative array.
*/
function string lookup(coerce string key) 
{
  local AssociativeArrayNode foundNode;
  foundNode = p_lookup(key, root);
  if (foundNode != None) {
    return foundNode.value;
  } else {
    return "";
  }
} // lookup

/* return the number of entries for the given key. Since the associative
   array is really a map, only 0 (no such entry) or 1 (an entry for the key)
   are valid return values. The name "count" comes from the C++ STL.
*/
function int count(coerce string key) 
{
  local AssociativeArrayNode foundNode;
  foundNode = p_lookup(key, root);
  if (foundNode != None) {
    return 1;
  } else {
    return 0;
  }
} // count

/* log the contents of the associative array. Useful for debugging.
 */
function show() 
{
  p_show(root);
} // show

// -------------------------------------------------------------------------
// "Iterator" functions
// -------------------------------------------------------------------------
/* UnrealScript iterators are native functions. Without access to the C++
   portions of the engine, it is impossible to create new ones. As an
   intermediary step, the following functions return beginning and ending
   "iterator" values modeled on C++ iterators. begin() returns an iterator
   "pointing to" the first element in the associative array. end() returns
   one just past the end of all elements in the associative array.

   This means, in a C++/STL-esque manner (and assuming appropriate operator
   overloading), a loop across the whole array would look like this:

   local AssociativeArrayIterator it;
   for (it = someAA.begin(); it != someAA.end(); ++it) {
     // it.first() and it.second() refer to key and value of each pair in turn
   }
*/
/* Returns an iterator for the first element of the associative array. */
function AssociativeArrayIterator begin() 
{
  local AssociativeArrayIterator retval;

  retval = new(None) class'AssociativeArrayIterator';
  retval.init(self);
  return retval;
} // begin

/* Returns an iterator just past the end of this associative array. */
function AssociativeArrayIterator end() 
{
  if (end_ == None) {
    end_ = new(None) class'AssociativeArrayIterator';
    end_.init(self, true);
  }
  return end_;
} // end

// -------------------------------------------------------------------------
// Implementation functions
// -------------------------------------------------------------------------
/* Recursive implementations of binary search tree functions for inserting,
   lookup, and printing. The "p_" prefix shows that they are protected
   funcitons.
*/

/* insert key/value pair in the tree rooted at curr. */
protected function p_insert(string key, string value,
                            out AssociativeArrayNode curr) 
{
  if (curr == None) {
    curr = new(None) class'AssociativeArrayNode';
    curr.key = key;
    curr.value = value;
    length++;
  } else if (key < curr.key) {
    p_insert(key, value, curr.left_child);
  } else if (key > curr.key) {
    p_insert(key, value, curr.right_child);
  } else { // curr.key == key
    curr.value = value;
  }
}

/* Return a reference to the node with the given key;
   None if there isn't one. */
protected function AssociativeArrayNode p_lookup(string key,
                                                 AssociativeArrayNode curr) 
{
  if (curr == None) {
    return None;
  } else if (key < curr.key) {
    return p_lookup(key, curr.left_child);
  } else if (key > curr.key) {
    return p_lookup(key, curr.right_child);
  } else {
    return curr;
  }
}

/* In-order traversal of binary search tree calling log on each entry */
protected function p_show(AssociativeArrayNode curr) 
{
  if (curr != None) {
    p_show(curr.left_child);
    log("["$curr.key$"] = "$curr.value);
    p_show(curr.right_child);
  }
} // p_show

defaultproperties 
{
  root = None
  length = 0
} // defaultproperties
// AssociativeArray