Legacy:AssociativeArray/Iterator

From Unreal Wiki, The Unreal Engine Documentation Site
Jump to navigation Jump to search

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.

<uscript> 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

} </uscript>

AssociativeArrayNodeStack

The explicit state of an iteration in progress. A stack of AssociativeArrayNodes.

<uscript> 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 </uscript>