remove method

bool remove(T value, { int compare(T v1, T v2)? = null, })

Removes the value from the tree.

Returns true if the value was removed, false otherwise.

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 remove.

Implementation

bool remove(T value, {int compare(T v1, T v2)?: null}) {
  if (compare == null) {
    compare = this._compare;
  }
  _require(compare is Function);

  // Find node to remove
  var nodeToRemove = this._lookupNode(value, compare);
  if (nodeToRemove == null) return false;
  if (_withEquivalenceClasses) {
    if (!nodeToRemove.containsIdentical(value)) return false;
    if (nodeToRemove.hasMultipleValues) {
      nodeToRemove.removeEquivalent(value);
      _size--;
      return true;
    }
    // Else continue as usual and remove the whole node from
    // the tree
  }
  // Find the replacement node
  var replacementNode = this._lookupReplacementNode(nodeToRemove);

  // Find the parent of the replacement node to re-factor the
  // height/balance of the tree
  var nodeToRefactor = null;
  if (replacementNode != null) nodeToRefactor = replacementNode.parent;
  if (nodeToRefactor == null) nodeToRefactor = nodeToRemove.parent;
  if (nodeToRefactor != null && nodeToRefactor == nodeToRemove)
    nodeToRefactor = replacementNode;

  // Replace the node
  _replaceNodeWithNode(nodeToRemove, replacementNode);

  // Re-balance the tree all the way up the tree
  _forEachAncestor(nodeToRefactor, (n) {
    n._updateHeight();
    _balanceAfterDelete(n);
  });
  return true;
}