| Home Page | Recent Changes | Preferences

# 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

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

Mapping Topics

Mapping Lessons

UnrealEd Interface

Questions&Answers

Scripting Topics

Scripting Lessons

Making Mods

Class Tree

Questions&Answers

Modeling Topics

Questions&Answers

Log In