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