AssociativeArray/Iterator
Iterator
A script-only iterator must use a different syntax from the built-in UnrealScript iterators. The syntax used here is "close" to that used in C++'s STL. Traversing an unthreaded binary search tree in order requires keeping track of the progress of the traversal; this is done in the activation stack in a recursive solution. It must be done explicitly with an iterator.
AssociativeArrayIterator
Warning this code is not insertion safe. That is, if elements are added to the associative array during a traversal, there is no way of knowing whether the nodes will be visited in the traversal. It is even less deletion save but this implementation of associative arrays doesn't support deletion.
class AssociativeArrayIterator extends Object; /* A forward, read-only, in-order iterator for traversing an associative array (a binary search tree (BST)). The iterator is associated with a particular associative array, keeping track of its current position and a stack of "open" nodes. An in-order traversal visits the nodes of a BST in sorted order by their keys. The typical description of the traversal is recursive: "left subtree, current node, right subtree". This means: do an in-order traversal of the left subtree, then visit the current node, then do an in-order traversal of the right subtree. Called on the root node of the tree, this will visit each node in sorted key order. An iterator cannot be recursive: each call to next should return the next element in the collection being interated over. Thus the iterator must capture the state of one step in the recursive, in-order traversal. The iterator uses a stack to keep a collection of "opened" but not yet visited nodes. These are exactly the nodes that would have been current in each recursive call down to the node being visited (curr_); the stack simulates the calling stack for the recursive version of the function and we can push and pop "activation records", one at a time, to complete a traversal of the BST. */ /* The state of an iterator is captured in the binary tree being traversed, the current node, and the collection of open but not visited nodes. */ var private AssociativeArray tree_; var private AssociativeArrayNode curr_; var private AssociativeArrayNodeStack stack_; /* Traversal order is determined by the contents of stack; the iterator must know when to push the root node onto the stack */ var private bool started_; /* Initialize the iterator. aaTree is the associative array this iterator is iterating across. bSetCurrentNodeNone is set true if the current node should NOT be set to the first node in the tree. This backward logic is required to handle the "optionalness" of the parameter; if no parameter is provided on the call, the boolean value is false. */ function init(AssociativeArray aaTree, optional bool bSetCurrentNodeNone) { started_ = false; tree_ = aaTree; stack_ = new(None) class'AssociativeArrayNodeStack'; if (!bSetCurrentNodeNone) next(); } // init /* Get the first value from the current iterator position, the key in the key/value pair. */ function string first() { return curr_.key; } // first /* get the second value from the current iterator position, the value in the key/value pair. */ function string second() { return curr_.value; } // second function AssociativeArray getCollection() { return tree_; } // getCollection function string getIndex() { return curr_.key; } // getIndex function dump() { local string dumpString; dumpString = Name$".dump(): " $"started_ = "$started_ $", tree_ = "$tree_ $", stack_ = "$stack_ $", curr_ = "$curr_; if (curr_ != None) dumpString = dumpString $", curr_.key = "$curr_.key $", curr_.value = "$curr_.value; log(dumpString, 'DevAssociativeArray'); } // dump /* Comparison operator calls this function */ function bool same(AssociativeArrayIterator other) { return ((tree_ == other.tree_) && (curr_ == other.curr_)); } // same /* advance to the next element. The next element is the left-most child of the root (first time through) or the left-most child of the right subtree (think about BST deletion routines and finding successor of a node to be deleted). */ function next() { local AssociativeArrayNode p; if (!started_) { p = tree_.root; } else { p = curr_; if (p != None) p = p.right_child; } do { while (p != None) { stack_.push(p); p = p.left_child; } // push all the left children if (!stack_.isEmpty()) { p = stack_.pop(); started_ = true; curr_ = p; return; } } until (stack_.isEmpty()); curr_ = None; } // next() defaultproperties { started_ = false }
AssociativeArrayNodeStack
The explicit state of an iteration in progress. A stack of AssociativeArrayNodes.
class AssociativeArrayNodeStack extends Object; /* A stack of array nodes; used to implement iterators. */ /* Implementation of the stack itself. Top of the stack is at impl[impl.Length-1] */ var private array<AssociativeArrayNode> impl; /* is the stack currently empty? */ function bool isEmpty() { return (impl.Length == 0); } // isEmpty /* Push the given AssociateArrayNode on the top of the stack. */ function push(AssociativeArrayNode a) { impl[impl.Length] = a; } // push /* Pop and top together: Return and remove the top element from the stack. If there is no such node, return None. */ function AssociativeArrayNode pop() { local AssociativeArrayNode retval; if (!isEmpty()) { retval = impl[impl.Length-1]; impl.Remove(impl.Length - 1, 1); return retval; } else { return None; } } // pop // AssociativeArrayNodeStack