| Home Page | Recent Changes | Preferences

# 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 `AssociativeArrayNode`s.

    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

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