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