public static List search()

in baremaps-flatgeobuf/src/main/java/org/apache/baremaps/flatgeobuf/PackedRTree.java [272:325]
52 lines of code
8 McCabe index (conditional complexity)

  public static List<SearchHit> search(
      ByteBuffer bb,
      int start,
      int numItems,
      int nodeSize,
      Envelope rect) {
    ArrayList<SearchHit> searchHits = new ArrayList<SearchHit>();
    double minX = rect.getMinX();
    double minY = rect.getMinY();
    double maxX = rect.getMaxX();
    double maxY = rect.getMaxY();
    List<Pair<Integer, Integer>> levelBounds = generateLevelBounds(numItems, nodeSize);
    int leafNodesOffset = levelBounds.get(0).first;
    int numNodes = levelBounds.get(0).second;
    Deque<QueueItem> queue = new LinkedList<QueueItem>();
    queue.add(new QueueItem(0, levelBounds.size() - 1));
    while (!queue.isEmpty()) {
      QueueItem stackItem = queue.pop();
      int nodeIndex = (int) stackItem.nodeIndex;
      int level = stackItem.level;
      boolean isLeafNode = nodeIndex >= numNodes - numItems;
      // find the end index of the node
      int levelEnd = levelBounds.get(level).second;
      int end = Math.min(nodeIndex + nodeSize, levelEnd);
      int nodeStart = start + (nodeIndex * NODE_ITEM_LEN);
      // search through child nodes
      for (int pos = nodeIndex; pos < end; pos++) {
        int offset = nodeStart + ((pos - nodeIndex) * NODE_ITEM_LEN);
        double nodeMinX = bb.getDouble(offset + 0);
        double nodeMinY = bb.getDouble(offset + 8);
        double nodeMaxX = bb.getDouble(offset + 16);
        double nodeMaxY = bb.getDouble(offset + 24);
        if (maxX < nodeMinX) {
          continue;
        }
        if (maxY < nodeMinY) {
          continue;
        }
        if (minX > nodeMaxX) {
          continue;
        }
        if (minY > nodeMaxY) {
          continue;
        }
        long indexOffset = bb.getLong(offset + 32);
        if (isLeafNode) {
          searchHits.add(new SearchHit(indexOffset, (long) pos - leafNodesOffset));
        } else {
          queue.add(new QueueItem(indexOffset, level - 1));
        }
      }
    }
    return searchHits;
  }