remove method

QuadTree<T> remove(T d)

Implementation

QuadTree<T> remove(T d) {
  num pointX = xFun.call(d), pointY = yFun.call(d);

  if (pointX.isNaN || pointX.isNaN) {
    return this;
  }

  QuadNode<T>? parent;
  QuadNode<T>? node = _root;
  QuadNode<T>? retainer;
  QuadNode<T>? previous;
  QuadNode<T>? next;
  num x0 = _x0;
  num y0 = _y0;
  num x1 = _x1;
  num y1 = _y1;
  int xm = 0, ym = 0;
  int right = 0, bottom = 0;
  int i = 0;
  int j = 0;
  // 如果树为空则将叶子节点初始化为根节点
  if (node == null) {
    return this;
  }
  //查找该点的叶节点。
  //当下降时，还保留最深的父级和未删除的同级
  if (node.hasChild) {
    while (true) {
      int a = xm = ((x0 + x1) / 2).round();
      int b = ym = ((y0 + y1) / 2).round();
      if ((right = _toInt(pointX >= a)) != 0) {
        x0 = xm;
      } else {
        x1 = xm;
      }
      if ((bottom = _toInt(pointY >= b)) != 0) {
        y0 = ym;
      } else {
        y1 = ym;
      }
      parent = node;
      if ((node = node![i = bottom << 1 | right]) == null) {
        return this;
      }
      if (!node!.hasChild) {
        break;
      }
      if ((parent![(i + 1) & 3]) != null || (parent[(i + 2) & 3]) != null || (parent[(i + 3) & 3]) != null) {
        retainer = parent;
        j = i;
      }
    }
  }

  // Find the point to remove.
  while (node!.data != d) {
    previous = node;
    node = node.next;
    if (node == null) {
      return this;
    }
  }

  if ((next = node.next) != null) {
    node.next = null;
  }

  // If there are multiple coincident points, remove just the point.
  if (previous != null) {
    previous.next = next;
    return this;
  }

  // If this is the root point, remove it.
  if (parent == null) {
    _root = next;
    return this;
  }
  // Remove this leaf.
  parent[i] = next;

  // If the parent now contains exactly one leaf, collapse superfluous parents.
  QuadNode<T>? tmpNode = parent[0];
  tmpNode ??= parent[1];
  tmpNode ??= parent[2];
  tmpNode ??= parent[3];

  QuadNode<T>? tmpNode2 = parent[3];
  tmpNode2 ??= parent[2];
  tmpNode2 ??= parent[1];
  tmpNode2 ??= parent[0];

  if ((node = tmpNode) != null && node == tmpNode2 && !node!.hasChild) {
    if (retainer != null) {
      retainer[j] = node;
    } else {
      _root = node;
    }
  }
  return this;
}