add method

void add(T? value, { int compare(T v1, T v2)? = null, })

Adds a value to the tree.

If supplied, compare is used to compare value with values already present in the tree. compare must be consistent with the ordering of values already present in this tree, but it may supply a more efficient implementation of the comparison operation for this very invocation of add.

Implementation

void add(T? value, {int compare(T v1, T v2)?: null}) {
  var localCompare;
  if (compare == null) {
    localCompare = this._compare;
  } else {
    localCompare = compare;
  }

  var newNode = new _AvlTreeNode(value, null) as _AvlTreeNode<T>?;

  // If root is null, assign
  if (_root == null) {
    _root = newNode;
    _size++;
  } else {
    var node = _root;
    loop:
    while (node != null) {
      var c = localCompare(value, node.compareValue);
      switch (c) {
        case -1:
          if (node.left != null) {
            node = node.left;
            continue;
          }
          // New left node
          node.left = newNode;
          newNode!.parent = node;
          _size++;
          break loop;

        case 1:
          if (node.right != null) {
            node = node.right;
            continue;
          }
          // New right node
          node.right = newNode;
          newNode!.parent = node;
          _size++;
          break loop;

        case 0:
          if (!_withEquivalenceClasses) {
            throw new StateError(
                "can't add value, value already present: $value");
          }
          if (node.containsIdentical(value)) {
            throw new StateError(
                "can't add value, value already present: $value");
          }
          node.addEquivalent(value);
          _size++;
          newNode = null;
          break loop;
      }
    }
  }

  _forEachAncestor(newNode, (n) {
    n._updateHeight();
    _balanceAfterInsert(n);
  });
}