remove method
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;
}