remove method

dynamic remove(T? item)

Removes a single item from the tree. Does nothing if the item is not there.

Implementation

remove(T? item) {
  if (item == null) return;

  _RBushNode<T>? node = data;
  final bbox = toBBox(item);
  List<_RBushNode<T>> path = [];
  List<int> indexes = [];
  int i = 0;
  _RBushNode<T>? parent;
  bool goingUp = false;

  // depth-first iterative tree traversal
  while (node != null || path.isNotEmpty) {
    if (node == null) {
      // go up
      node = path.removeLast();
      parent = path.isEmpty ? null : path.last;
      i = indexes.removeLast();
      goingUp = true;
    }

    if (node.leaf) {
      // check current node
      final index = node.leafChildren.indexOf(item);
      if (index != -1) {
        // item found, remove the item and condense tree upwards
        node.leafChildren.removeAt(index);
        path.add(node);
        _condense(path);
        return;
      }
    }

    if (!goingUp && !node.leaf && node.contains(bbox)) {
      // go down
      path.add(node);
      indexes.add(i);
      i = 0;
      parent = node;
      node = node.children.first;
    } else if (parent != null) {
      // go right
      i++;
      node = i >= parent.children.length ? null : parent.children[i];
      goingUp = false;
    } else {
      // nothing found
      node = null;
    }
  }
}