Roll Observatory packages and add a roll script

quiver/lib/src/collection/treeset.dart

Index: quiver/lib/src/collection/treeset.dart
diff --git a/quiver/lib/src/collection/treeset.dart b/quiver/lib/src/collection/treeset.dart
deleted file mode 100644
index 200c21fcf1a61df65451a798e40cf3d31b6c0cf6..0000000000000000000000000000000000000000
--- a/quiver/lib/src/collection/treeset.dart
+++ /dev/null
@@ -1,1050 +0,0 @@
-// Copyright 2014 Google Inc. All Rights Reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-part of quiver.collection;
-
-/**
- * A [Set] of items stored in a binary tree according to [comparator].
- * Supports bidirectional iteration.
- */
-abstract class TreeSet<V> extends IterableBase<V> implements Set<V> {
-  final Comparator<V> comparator;
-
-  int get length;
-
-  /**
-   * Create a new [TreeSet] with an ordering defined by [comparator] or the
-   * default `(a, b) => a.compareTo(b)`.
-   */
-  factory TreeSet({Comparator<V> comparator}) {
-    if (comparator == null) {
-      comparator = (a, b) => a.compareTo(b);
-    }
-    return new AvlTreeSet(comparator: comparator);
-  }
-
-  TreeSet._(this.comparator);
-
-  /**
-   * Returns an [BidirectionalIterator] that iterates over this tree.
-   */
-  BidirectionalIterator<V> get iterator;
-
-  /**
-   * Returns an [BidirectionalIterator] that iterates over this tree, in reverse.
-   */
-  BidirectionalIterator<V> get reverseIterator;
-
-  /**
-   * Returns an [BidirectionalIterator] that starts at [anchor].
-   * By default, the iterator includes the anchor with the first movement;
-   * set [inclusive] to false if you want to exclude the anchor. Set [reversed]
-   * to true to change the direction of of moveNext and movePrevious.
-   *
-   * Note: This iterator allows you to walk the entire set. It does not present
-   * a subview.
-   */
-  BidirectionalIterator<V> fromIterator(V anchor,
-      {bool reversed: false, bool inclusive: true});
-
-  /**
-   * Search the tree for the matching [object] or the [nearestOption]
-   * if missing.  See [TreeSearch].
-   */
-  V nearest(V object, {TreeSearch nearestOption: TreeSearch.NEAREST});
-
-  // TODO: toString or not toString, that is the question.
-}
-
-/**
- * Controls the results for [TreeSet.searchNearest]()
- */
-class TreeSearch {
-
-  /**
-   * If result not found, always chose the smaler element
-   */
-  static const LESS_THAN = const TreeSearch._(1);
-
-  /**
-   * If result not found, chose the nearest based on comparison
-   */
-  static const NEAREST = const TreeSearch._(2);
-
-  /**
-   * If result not found, always chose the greater element
-   */
-  static const GREATER_THAN = const TreeSearch._(3);
-
-  final int _val;
-  const TreeSearch._(this._val);
-}
-
-/**
- * A node in the [TreeSet].
- */
-abstract class _TreeNode<V> {
-  _TreeNode<V> get left;
-  _TreeNode<V> get right;
-
-  //TODO(codefu): Remove need for [parent]; this is just an implementation note
-  _TreeNode<V> get parent;
-  V object;
-
-  /**
-   * TreeNodes are always allocated as leafs.
-   */
-  _TreeNode({this.object});
-
-  /**
-   *  Return the minimum node for the subtree
-   */
-  _TreeNode<V> get minimumNode {
-    var node = this;
-    while (node.left != null) {
-      node = node.left;
-    }
-    return node;
-  }
-
-  /**
-   *  Return the maximum node for the subtree
-   */
-  _TreeNode<V> get maximumNode {
-    var node = this;
-    while (node.right != null) {
-      node = node.right;
-    }
-    return node;
-  }
-
-  /**
-   *  Return the next greatest element (or null)
-   */
-  _TreeNode<V> get successor {
-    var node = this;
-    if (node.right != null) {
-      return node.right.minimumNode;
-    }
-    while (node.parent != null && node == node.parent.right) {
-      node = node.parent;
-    }
-    return node.parent;
-  }
-
-  /**
-   *  Return the next smaller element (or null)
-   */
-  _TreeNode<V> get predecessor {
-    var node = this;
-    if (node.left != null) {
-      return node.left.maximumNode;
-    }
-    while (node.parent != null && node.parent._left == node) {
-      node = node.parent;
-    }
-    return node.parent;
-  }
-}
-
-/**
- * AVL implementation of a self-balancing binary tree. Optimized for lookup
- * operations.
- *
- * Notes: Adapted from "Introduction to Algorithms", second edition,
- *        by Thomas H. Cormen, Charles E. Leiserson,
- *           Ronald L. Rivest, Clifford Stein.
- *        chapter 13.2
- */
-class AvlTreeSet<V> extends TreeSet<V> {
-  int _length = 0;
-  AvlNode<V> _root;
-  // Modification count to the tree, monotonically increasing
-  int _modCount = 0;
-
-  int get length => _length;
-
-  AvlTreeSet({Comparator<V> comparator}) : super._(comparator);
-
-  /**
-   * Add the element to the tree.
-   */
-  bool add(V element) {
-    if (_root == null) {
-      AvlNode<V> node = new AvlNode<V>(object: element);
-      _root = node;
-      ++_length;
-      ++_modCount;
-      return true;
-    }
-
-    AvlNode<V> x = _root;
-    while (true) {
-      int compare = comparator(element, x.object);
-      if (compare == 0) {
-        return false;
-      } else if (compare < 0) {
-        if (x._left == null) {
-          AvlNode<V> node = new AvlNode<V>(object: element).._parent = x;
-          x
-            .._left = node
-            .._balanceFactor -= 1;
-          break;
-        }
-        x = x.left;
-      } else {
-        if (x._right == null) {
-          AvlNode<V> node = new AvlNode<V>(object: element).._parent = x;
-          x
-            .._right = node
-            .._balanceFactor += 1;
-          break;
-        }
-        x = x.right;
-      }
-    }
-
-    ++_modCount;
-
-    // AVL balancing act (for height balanced trees)
-    // Now that we've inserted, we've unbalanced some trees, we need
-    //  to follow the tree back up to the _root double checking that the tree
-    //  is still balanced and _maybe_ perform a single or double rotation.
-    //  Note: Left additions == -1, Right additions == +1
-    //  Balanced Node = { -1, 0, 1 }, out of balance = { -2, 2 }
-    //  Single rotation when Parent & Child share signed balance,
-    //  Double rotation when sign differs!
-    AvlNode<V> node = x;
-    while (node._balanceFactor != 0 && node.parent != null) {
-      // Find out which side of the parent we're on
-      if (node.parent._left == node) {
-        node.parent._balanceFactor -= 1;
-      } else {
-        node.parent._balanceFactor += 1;
-      }
-
-      node = node.parent;
-      if (node._balanceFactor == 2) {
-        // Heavy on the right side - Test for which rotation to perform
-        if (node.right._balanceFactor == 1) {
-          // Single (left) rotation; this will balance everything to zero
-          _rotateLeft(node);
-          node._balanceFactor = node.parent._balanceFactor = 0;
-          node = node.parent;
-        } else {
-          // Double (Right/Left) rotation
-          // node will now be old node.right.left
-          _rotateRightLeft(node);
-          node = node.parent; // Update to new parent (old grandchild)
-          if (node._balanceFactor == 1) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = -1;
-          } else if (node._balanceFactor == 0) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = 0;
-          } else {
-            node.right._balanceFactor = 1;
-            node.left._balanceFactor = 0;
-          }
-          node._balanceFactor = 0;
-        }
-        break; // out of loop, we're balanced
-      } else if (node._balanceFactor == -2) {
-        // Heavy on the left side - Test for which rotation to perform
-        if (node.left._balanceFactor == -1) {
-          _rotateRight(node);
-          node._balanceFactor = node.parent._balanceFactor = 0;
-          node = node.parent;
-        } else {
-          // Double (Left/Right) rotation
-          // node will now be old node.left.right
-          _rotateLeftRight(node);
-          node = node.parent;
-          if (node._balanceFactor == -1) {
-            node.right._balanceFactor = 1;
-            node.left._balanceFactor = 0;
-          } else if (node._balanceFactor == 0) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = 0;
-          } else {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = -1;
-          }
-          node._balanceFactor = 0;
-        }
-        break; // out of loop, we're balanced
-      }
-    } // end of while (balancing)
-    _length++;
-    return true;
-  }
-
-  /**
-   * Test to see if an element is stored in the tree
-   */
-  AvlNode<V> _getNode(V element) {
-    if (element == null) return null;
-    AvlNode<V> x = _root;
-    while (x != null) {
-      int compare = comparator(element, x.object);
-      if (compare == 0) {
-        // This only means our node matches; we need to search for the exact
-        // element. We could have been glutons and used a hashmap to back.
-        return x;
-      } else if (compare < 0) {
-        x = x.left;
-      } else {
-        x = x.right;
-      }
-    }
-    return null;
-  }
-
-  /**
-   * This function will right rotate/pivot N with its left child, placing
-   * it on the right of its left child.
-   *
-   *      N                      Y
-   *     / \                    / \
-   *    Y   A                  Z   N
-   *   / \          ==>       / \ / \
-   *  Z   B                  D  CB   A
-   * / \
-   *D   C
-   *
-   * Assertion: must have a left element
-   */
-  void _rotateRight(AvlNode<V> node) {
-    AvlNode<V> y = node.left;
-    if (y == null) throw new AssertionError();
-
-    // turn Y's right subtree(B) into N's left subtree.
-    node._left = y.right;
-    if (node.left != null) {
-      node.left._parent = node;
-    }
-    y._parent = node.parent;
-    if (y._parent == null) {
-      _root = y;
-    } else {
-      if (node.parent._left == node) {
-        node.parent._left = y;
-      } else {
-        node.parent._right = y;
-      }
-    }
-    y._right = node;
-    node._parent = y;
-  }
-
-  /**
-   * This function will left rotate/pivot N with its right child, placing
-   * it on the left of its right child.
-   *
-   *      N                      Y
-   *     / \                    / \
-   *    A   Y                  N   Z
-   *       / \      ==>       / \ / \
-   *      B   Z              A  BC   D
-   *         / \
-   *        C   D
-   *
-   * Assertion: must have a right element
-   */
-  void _rotateLeft(AvlNode<V> node) {
-    AvlNode<V> y = node.right;
-    if (y == null) throw new AssertionError();
-
-    // turn Y's left subtree(B) into N's right subtree.
-    node._right = y.left;
-    if (node.right != null) {
-      node.right._parent = node;
-    }
-    y._parent = node.parent;
-    if (y._parent == null) {
-      _root = y;
-    } else {
-      if (node.parent._left == node) {
-        y.parent._left = y;
-      } else {
-        y.parent._right = y;
-      }
-    }
-    y._left = node;
-    node._parent = y;
-  }
-
-  /**
-   *  This function will double rotate node with right/left operations.
-   *  node is S.
-   *
-   *    S                      G
-   *   / \                    / \
-   *  A   C                  S   C
-   *     / \      ==>       / \ / \
-   *    G   B              A  DC   B
-   *   / \
-   *  D   C
-   */
-  void _rotateRightLeft(AvlNode<V> node) {
-    _rotateRight(node.right);
-    _rotateLeft(node);
-  }
-
-  /**
-   * This function will double rotate node with left/right operations.
-   * node is S.
-   *
-   *    S                      G
-   *   / \                    / \
-   *  C   A                  C   S
-   * / \          ==>       / \ / \
-   *B   G                  B  CD   A
-   *   / \
-   *  C   D
-   */
-  void _rotateLeftRight(AvlNode<V> node) {
-    _rotateLeft(node.left);
-    _rotateRight(node);
-  }
-
-  bool addAll(Iterable<V> items) {
-    bool modified = false;
-    for (V ele in items) {
-      modified = add(ele) ? true : modified;
-    }
-    return modified;
-  }
-
-  void clear() {
-    _length = 0;
-    _root = null;
-    ++_modCount;
-  }
-
-  bool containsAll(Iterable<Object> items) {
-    for (var ele in items) {
-      if (!contains(ele)) return false;
-    }
-    return true;
-  }
-
-  bool remove(Object item) {
-    AvlNode<V> x = _getNode(item);
-    if (x != null) {
-      _removeNode(x);
-      return true;
-    }
-    return false;
-  }
-
-  void _removeNode(AvlNode<V> node) {
-    AvlNode<V> y, w;
-
-    ++_modCount;
-    --_length;
-
-    // note: if you read wikipedia, it states remove the node if its a leaf,
-    // otherwise, replace it with its predecessor or successor. We're not.
-    if (node._right == null || node.right._left == null) {
-      // simple solutions
-      if (node.right != null) {
-        y = node.right;
-        y._parent = node.parent;
-        y._balanceFactor = node._balanceFactor - 1;
-        y._left = node.left;
-        if (y.left != null) {
-          y.left._parent = y;
-        }
-      } else if (node.left != null) {
-        y = node.left;
-        y._parent = node.parent;
-        y._balanceFactor = node._balanceFactor + 1;
-      } else {
-        y = null;
-      }
-      if (_root == node) {
-        _root = y;
-      } else if (node.parent._left == node) {
-        node.parent._left = y;
-        if (y == null) {
-          // account for leaf deletions changing the balance
-          node.parent._balanceFactor += 1;
-          y = node.parent; // start searching from here;
-        }
-      } else {
-        node.parent._right = y;
-        if (y == null) {
-          node.parent._balanceFactor -= 1;
-          y = node.parent;
-        }
-      }
-      w = y;
-    } else {
-      // This node is not a leaf; we should find the successor node, swap
-      //it with this* and then update the balance factors.
-      y = node.successor;
-      y._left = node.left;
-      if (y.left != null) {
-        y.left._parent = y;
-      }
-
-      w = y.parent;
-      w._left = y.right;
-      if (w.left != null) {
-        w.left._parent = w;
-      }
-      // known: we're removing from the left
-      w._balanceFactor += 1;
-
-      // known due to test for n->r->l above
-      y._right = node.right;
-      y.right._parent = y;
-      y._balanceFactor = node._balanceFactor;
-
-      y._parent = node.parent;
-      if (_root == node) {
-        _root = y;
-      } else if (node.parent._left == node) {
-        node.parent._left = y;
-      } else {
-        node.parent._right = y;
-      }
-    }
-
-    // Safe to kill node now; its free to go.
-    node._balanceFactor = 0;
-    node._left = node._right = node._parent = null;
-    node.object = null;
-
-    // Recalculate max values all the way to the top.
-    node = w;
-    while (node != null) {
-      node = node.parent;
-    }
-
-    // Re-balance to the top, ending early if OK
-    node = w;
-    while (node != null) {
-      if (node._balanceFactor == -1 || node._balanceFactor == 1) {
-        // The height of node hasn't changed; done!
-        break;
-      }
-      if (node._balanceFactor == 2) {
-        // Heavy on the right side; figure out which rotation to perform
-        if (node.right._balanceFactor == -1) {
-          _rotateRightLeft(node);
-          node = node.parent; // old grand-child!
-          if (node._balanceFactor == 1) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = -1;
-          } else if (node._balanceFactor == 0) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = 0;
-          } else {
-            node.right._balanceFactor = 1;
-            node.left._balanceFactor = 0;
-          }
-          node._balanceFactor = 0;
-        } else {
-          // single left-rotation
-          _rotateLeft(node);
-          if (node.parent._balanceFactor == 0) {
-            node.parent._balanceFactor = -1;
-            node._balanceFactor = 1;
-            break;
-          } else {
-            node.parent._balanceFactor = 0;
-            node._balanceFactor = 0;
-            node = node.parent;
-            continue;
-          }
-        }
-      } else if (node._balanceFactor == -2) {
-        // Heavy on the left
-        if (node.left._balanceFactor == 1) {
-          _rotateLeftRight(node);
-          node = node.parent; // old grand-child!
-          if (node._balanceFactor == -1) {
-            node.right._balanceFactor = 1;
-            node.left._balanceFactor = 0;
-          } else if (node._balanceFactor == 0) {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = 0;
-          } else {
-            node.right._balanceFactor = 0;
-            node.left._balanceFactor = -1;
-          }
-          node._balanceFactor = 0;
-        } else {
-          _rotateRight(node);
-          if (node.parent._balanceFactor == 0) {
-            node.parent._balanceFactor = 1;
-            node._balanceFactor = -1;
-            break;
-          } else {
-            node.parent._balanceFactor = 0;
-            node._balanceFactor = 0;
-            node = node.parent;
-            continue;
-          }
-        }
-      }
-
-      // continue up the tree for testing
-      if (node.parent != null) {
-        // The concept of balance here is reverse from addition; since
-        // we are taking away weight from one side or the other (thus
-        // the balance changes in favor of the other side)
-        if (node.parent.left == node) {
-          node.parent._balanceFactor += 1;
-        } else {
-          node.parent._balanceFactor -= 1;
-        }
-      }
-      node = node.parent;
-    }
-  }
-
-  /**
-   * See [Set.removeAll]
-   */
-  void removeAll(Iterable items) {
-    for (var ele in items) {
-      remove(ele);
-    }
-  }
-
-  /**
-   * See [Set.retainAll]
-   */
-  void retainAll(Iterable<Object> elements) {
-    List<V> chosen = [];
-    for (var target in elements) {
-      if (contains(target)) {
-        chosen.add(target);
-      }
-    }
-    clear();
-    addAll(chosen);
-  }
-
-  /**
-   * See [Set.retainWhere]
-   */
-  void retainWhere(bool test(V element)) {
-    List<V> chosen = [];
-    for (var target in this) {
-      if (test(target)) {
-        chosen.add(target);
-      }
-    }
-    clear();
-    addAll(chosen);
-  }
-
-  /**
-   * See [Set.removeWhere]
-   */
-  void removeWhere(bool test(V element)) {
-    List<V> damned = [];
-    for (var target in this) {
-      if (test(target)) {
-        damned.add(target);
-      }
-    }
-    removeAll(damned);
-  }
-
-  /**
-   * See [IterableBase.first]
-   */
-  V get first {
-    if (_root == null) return null;
-    AvlNode<V> min = _root.minimumNode;
-    return min != null ? min.object : null;
-  }
-
-  /**
-   * See [IterableBase.last]
-   */
-  V get last {
-    if (_root == null) return null;
-    AvlNode<V> max = _root.maximumNode;
-    return max != null ? max.object : null;
-  }
-
-  /**
-   * See [Set.lookup]
-   */
-  V lookup(Object element) {
-    if (element == null || _root == null) return null;
-    AvlNode<V> x = _root;
-    int compare = 0;
-    while (x != null) {
-      compare = comparator(element, x.object);
-      if (compare == 0) {
-        return x.object;
-      } else if (compare < 0) {
-        x = x.left;
-      } else {
-        x = x.right;
-      }
-    }
-    return null;
-  }
-
-  V nearest(V object, {TreeSearch nearestOption: TreeSearch.NEAREST}) {
-    AvlNode<V> found = _searchNearest(object, option: nearestOption);
-    return (found != null) ? found.object : null;
-  }
-
-  /**
-   * Search the tree for the matching element, or the 'nearest' node.
-   * NOTE: [BinaryTree.comparator] needs to have finer granulatity than -1,0,1
-   * in order for this to return something that's meaningful.
-   */
-  AvlNode<V> _searchNearest(V element,
-      {TreeSearch option: TreeSearch.NEAREST}) {
-    if (element == null || _root == null) {
-      return null;
-    }
-    AvlNode<V> x = _root;
-    AvlNode<V> previous;
-    int compare = 0;
-    while (x != null) {
-      previous = x;
-      compare = comparator(element, x.object);
-      if (compare == 0) {
-        return x;
-      } else if (compare < 0) {
-        x = x.left;
-      } else {
-        x = x.right;
-      }
-    }
-
-    if (option == TreeSearch.GREATER_THAN) {
-      return (compare < 0) ? previous : previous.successor;
-    } else if (option == TreeSearch.LESS_THAN) {
-      return (compare < 0) ? previous.predecessor : previous;
-    }
-    // Default: nearest absolute value
-    // Fell off the tree looking for the exact match; now we need
-    // to find the nearest element.
-    x = (compare < 0) ? previous.predecessor : previous.successor;
-    if (x == null) {
-      return previous;
-    }
-    int otherCompare = comparator(element, x.object);
-    if (compare < 0) {
-      return compare.abs() < otherCompare ? previous : x;
-    }
-    return otherCompare.abs() < compare ? x : previous;
-  }
-
-  //
-  // [IterableBase]<V> Methods
-  //
-
-  /**
-   * See [IterableBase.iterator]
-   */
-  BidirectionalIterator<V> get iterator => new _AvlTreeIterator._(this);
-
-  /**
-   * See [TreeSet.reverseIterator]
-   */
-  BidirectionalIterator<V> get reverseIterator =>
-      new _AvlTreeIterator._(this, reversed: true);
-
-  /**
-   * See [TreeSet.fromIterator]
-   */
-  BidirectionalIterator<V> fromIterator(V anchor,
-          {bool reversed: false, bool inclusive: true}) =>
-      new _AvlTreeIterator<V>._(this,
-          anchorObject: anchor, reversed: reversed, inclusive: inclusive);
-
-  /**
-   * See [IterableBase.contains]
-   */
-  bool contains(Object object) {
-    AvlNode<V> x = _getNode(object as V);
-    return x != null;
-  }
-
-  //
-  // [Set] methods
-  //
-
-  /**
-   * See [Set.intersection]
-   */
-  Set<V> intersection(Set<Object> other) {
-    TreeSet<V> set = new TreeSet(comparator: comparator);
-
-    // Opitimized for sorted sets
-    if (other is TreeSet) {
-      var i1 = iterator;
-      var i2 = other.iterator;
-      var hasMore1 = i1.moveNext();
-      var hasMore2 = i2.moveNext();
-      while (hasMore1 && hasMore2) {
-        var c = comparator(i1.current, i2.current);
-        if (c == 0) {
-          set.add(i1.current);
-          hasMore1 = i1.moveNext();
-          hasMore2 = i2.moveNext();
-        } else if (c < 0) {
-          hasMore1 = i1.moveNext();
-        } else {
-          hasMore2 = i2.moveNext();
-        }
-      }
-      return set;
-    }
-
-    // Non-optimized version.
-    for (var target in this) {
-      if (other.contains(target)) {
-        set.add(target);
-      }
-    }
-    return set;
-  }
-
-  /**
-   * See [Set.union]
-   */
-  Set<V> union(Set<V> other) {
-    TreeSet<V> set = new TreeSet(comparator: comparator);
-
-    if (other is TreeSet) {
-      var i1 = iterator;
-      var i2 = other.iterator;
-      var hasMore1 = i1.moveNext();
-      var hasMore2 = i2.moveNext();
-      while (hasMore1 && hasMore2) {
-        var c = comparator(i1.current, i2.current);
-        if (c == 0) {
-          set.add(i1.current);
-          hasMore1 = i1.moveNext();
-          hasMore2 = i2.moveNext();
-        } else if (c < 0) {
-          set.add(i1.current);
-          hasMore1 = i1.moveNext();
-        } else {
-          set.add(i2.current);
-          hasMore2 = i2.moveNext();
-        }
-      }
-      if (hasMore1 || hasMore2) {
-        i1 = hasMore1 ? i1 : i2;
-        do {
-          set.add(i1.current);
-        } while (i1.moveNext());
-      }
-      return set;
-    }
-
-    // Non-optimized version.
-    return set
-      ..addAll(this)
-      ..addAll(other);
-  }
-
-  /**
-   * See [Set.difference]
-   */
-  Set<V> difference(Set<V> other) {
-    TreeSet<V> set = new TreeSet(comparator: comparator);
-
-    if (other is TreeSet) {
-      var i1 = iterator;
-      var i2 = other.iterator;
-      var hasMore1 = i1.moveNext();
-      var hasMore2 = i2.moveNext();
-      while (hasMore1 && hasMore2) {
-        var c = comparator(i1.current, i2.current);
-        if (c == 0) {
-          hasMore1 = i1.moveNext();
-          hasMore2 = i2.moveNext();
-        } else if (c < 0) {
-          set.add(i1.current);
-          hasMore1 = i1.moveNext();
-        } else {
-          hasMore2 = i2.moveNext();
-        }
-      }
-      if (hasMore1) {
-        do {
-          set.add(i1.current);
-        } while (i1.moveNext());
-      }
-      return set;
-    }
-
-    // Non-optimized version.
-    for (var target in this) {
-      if (!other.contains(target)) {
-        set.add(target);
-      }
-    }
-    return set;
-  }
-
-  /**
-   * Visible for testing only.
-   */
-  AvlNode<V> getNode(V object) => _getNode(object);
-}
-
-typedef bool _IteratorMove();
-
-/**
- * This iterator either starts at the beginning or end (see [TreeSet.iterator]
- * and [TreeSet.reverseIterator]) or from an anchor point in the set (see
- * [TreeSet.fromIterator]). When using fromIterator, the inital
- * anchor point is included in the first movement (either [moveNext] or
- * [movePrevious]) but can optionally be excluded in the constructor.
- */
-class _AvlTreeIterator<V> implements BidirectionalIterator<V> {
-  static const LEFT = -1;
-  static const WALK = 0;
-  static const RIGHT = 1;
-
-  final bool reversed;
-  final AvlTreeSet<V> tree;
-  final int _modCountGuard;
-  final Object anchorObject;
-  final bool inclusive;
-
-  _IteratorMove _moveNext;
-  _IteratorMove _movePrevious;
-
-  int state;
-  _TreeNode<V> _current;
-
-  _AvlTreeIterator._(AvlTreeSet<V> tree,
-      {reversed: false, this.inclusive: true, this.anchorObject: null})
-      : this.tree = tree,
-        this._modCountGuard = tree._modCount,
-        this.reversed = reversed {
-    if (anchorObject == null || tree.length == 0) {
-      // If the anchor is far left or right, we're just a normal iterator.
-      state = reversed ? RIGHT : LEFT;
-      _moveNext = reversed ? _movePreviousNormal : _moveNextNormal;
-      _movePrevious = reversed ? _moveNextNormal : _movePreviousNormal;
-      return;
-    }
-
-    state = WALK;
-    // Else we've got an anchor we have to worry about initalizing from.
-    // This isn't known till the caller actually performs a previous/next.
-    _moveNext = () {
-      _current = tree._searchNearest(anchorObject,
-          option: reversed ? TreeSearch.LESS_THAN : TreeSearch.GREATER_THAN);
-      _moveNext = reversed ? _movePreviousNormal : _moveNextNormal;
-      _movePrevious = reversed ? _moveNextNormal : _movePreviousNormal;
-      if (_current == null) {
-        state = reversed ? LEFT : RIGHT;
-      } else if (tree.comparator(_current.object, anchorObject) == 0 &&
-          !inclusive) {
-        _moveNext();
-      }
-      return state == WALK;
-    };
-
-    _movePrevious = () {
-      _current = tree._searchNearest(anchorObject,
-          option: reversed ? TreeSearch.GREATER_THAN : TreeSearch.LESS_THAN);
-      _moveNext = reversed ? _movePreviousNormal : _moveNextNormal;
-      _movePrevious = reversed ? _moveNextNormal : _movePreviousNormal;
-      if (_current == null) {
-        state = reversed ? RIGHT : LEFT;
-      } else if (tree.comparator(_current.object, anchorObject) == 0 &&
-          !inclusive) {
-        _movePrevious();
-      }
-      return state == WALK;
-    };
-  }
-
-  V get current => (state != WALK || _current == null) ? null : _current.object;
-
-  bool moveNext() => _moveNext();
-  bool movePrevious() => _movePrevious();
-
-  bool _moveNextNormal() {
-    if (_modCountGuard != tree._modCount) {
-      throw new ConcurrentModificationError(tree);
-    }
-    if (state == RIGHT || tree.length == 0) return false;
-    switch (state) {
-      case LEFT:
-        _current = tree._root.minimumNode;
-        state = WALK;
-        return true;
-      case WALK:
-      default:
-        _current = _current.successor;
-        if (_current == null) {
-          state = RIGHT;
-        }
-        return state == WALK;
-    }
-  }
-
-  bool _movePreviousNormal() {
-    if (_modCountGuard != tree._modCount) {
-      throw new ConcurrentModificationError(tree);
-    }
-    if (state == LEFT || tree.length == 0) return false;
-    switch (state) {
-      case RIGHT:
-        _current = tree._root.maximumNode;
-        state = WALK;
-        return true;
-      case WALK:
-      default:
-        _current = _current.predecessor;
-        if (_current == null) {
-          state = LEFT;
-        }
-        return state == WALK;
-    }
-  }
-}
-
-/**
- * Private class used to track element insertions in the [TreeSet].
- */
-class AvlNode<V> extends _TreeNode<V> {
-  AvlNode<V> _left;
-  AvlNode<V> _right;
-  //TODO(codefu): Remove need for [parent]; this is just an implementation note
-  AvlNode<V> _parent;
-  int _balanceFactor = 0;
-
-  AvlNode<V> get left => _left;
-  AvlNode<V> get right => _right;
-  AvlNode<V> get parent => _parent;
-  int get balance => _balanceFactor;
-
-  AvlNode({V object}) : super(object: object);
-
-  String toString() =>
-      "(b:$balance o: $object l:${left != null} r:${right != null})";
-}