Skip to content

Migration Guide: v1.x to v2.0

This guide covers all breaking changes in fastquadtree 2.0 and how to update your code.

Overview of Breaking Changes

Change Impact
Class split track_objects=True users must switch to *Objects classes
Query return types as_items parameter removed
NumPy methods Runtime type detection removed; use explicit _np methods
Insertion API insert_many returns InsertResult instead of int
Deletion API Signature changed from delete(id_, geom) to delete(id_, x, y, ...)
Custom IDs New feature for non-Objects classes
Serialization New format; v1 serialized data not compatible
Removed methods count_items() removed; use len()

Class Split

The track_objects parameter has been removed. Instead, use the appropriate class for your use case.

Choosing Your Class

v1.x Usage v2.0 Class
QuadTree(..., track_objects=False) QuadTree
QuadTree(..., track_objects=True) QuadTreeObjects
RectQuadTree(..., track_objects=False) RectQuadTree
RectQuadTree(..., track_objects=True) RectQuadTreeObjects

Before (v1.x)

from fastquadtree import QuadTree, RectQuadTree

# Without object tracking
qt = QuadTree((0, 0, 100, 100), capacity=4, track_objects=False)

# With object tracking
qt_tracked = QuadTree((0, 0, 100, 100), capacity=4, track_objects=True)
qt_tracked.insert((10, 20), obj={"name": "point_a"})

After (v2.0)

from fastquadtree import (
    QuadTree,
    QuadTreeObjects,
    RectQuadTree,
    RectQuadTreeObjects,
)

# Without object tracking (default, fastest)
qt = QuadTree((0, 0, 100, 100), capacity=4)

# With object tracking
qt_tracked = QuadTreeObjects((0, 0, 100, 100), capacity=4)
qt_tracked.insert((10, 20), obj={"name": "point_a"})

Query Return Types

The as_items parameter has been removed. Return types are now determined by which class you use.

Before (v1.x)

# Tuple output (default)
results = qt.query(rect)
for id_, x, y in results:
    ...

# Item output
results = qt.query(rect, as_items=True)
for item in results:
    print(item.id_, item.x, item.y, item.obj)

After (v2.0)

# QuadTree always returns tuples
results = qt.query(rect)
for id_, x, y in results:
    ...

# QuadTreeObjects always returns PointItem objects
results = qt_obj.query(rect)
for item in results:
    print(item.id_, item.x, item.y, item.obj)

# If you only need IDs from an Objects tree (fast path)
ids = qt_obj.query_ids(rect)

NumPy Methods

Runtime type detection has been removed. NumPy arrays are no longer accepted by standard methods.

Before (v1.x)

import numpy as np

# Same method accepted both
qt.insert_many([(1, 2), (3, 4)])
qt.insert_many(np.array([[1, 2], [3, 4]], dtype=np.float32))

After (v2.0)

import numpy as np

# Python sequences use standard methods
qt.insert_many([(1, 2), (3, 4)])

# NumPy arrays require _np methods
qt.insert_many_np(np.array([[1, 2], [3, 4]], dtype=np.float32))

# Same pattern for queries
results = qt.query(rect)                  # list output
ids, coords = qt.query_np(rect)           # NumPy output

# And nearest neighbors
neighbors = qt.nearest_neighbors(point, k=5)
ids, coords = qt.nearest_neighbors_np(point, k=5)

TypeError on misuse

Passing a NumPy array to a non-_np method raises TypeError. This catches bugs early rather than silently degrading performance.

NumPy Output Guarantees

All _np methods return arrays with consistent dtypes:

  • ids: np.uint64, shape (N,)
  • coords: np.float32, np.float64, np.int32, or np.int64 (matches tree's dtype), shape (N, 2) for points or (N, 4) for rects

Insertion API

Single Insert

Single insert() still returns an int ID. No change required unless you want to use custom IDs (see Custom IDs).

Bulk Insert

insert_many() now returns an InsertResult dataclass instead of an int or tuple.

Before (v1.x)

# Count only
count = qt.insert_many(points)

# Count and start ID
count, start_id = qt.insert_many(points, get_start_id=True)

After (v2.0)

result = qt.insert_many(points)

result.count      # number inserted
result.start_id   # first ID in batch
result.end_id     # last ID in batch
result.ids        # range(start_id, end_id + 1)

Quick Fix

If you have many call sites, a wrapper function eases migration:

def insert_many_v1(qt, geoms, get_start_id=False):
    """Compatibility wrapper returning v1-style output."""
    result = qt.insert_many(geoms)
    if get_start_id:
        return result.count, result.start_id
    return result.count

Deletion API

Non-Objects Classes

Geometry is now passed as separate arguments, not a tuple.

Before (v1.x)

# Points
qt.delete(id_, (x, y))

# Rects
rqt.delete(id_, (min_x, min_y, max_x, max_y))

After (v2.0)

# Points
qt.delete(id_, x, y)

# Rects
rqt.delete(id_, min_x, min_y, max_x, max_y)

Objects Classes

Objects classes can delete by ID alone since they track coordinates internally.

# Delete by ID (Objects classes only)
qt_obj.delete(id_)

# Delete by location (removes lowest ID at that point)
qt_obj.delete_at(x, y)

# Delete by object identity
qt_obj.delete_by_object(obj)        # deletes all matches, returns count
qt_obj.delete_one_by_object(obj)    # deletes one match, returns bool

Custom IDs

New in v2.0. Non-Objects classes now support user-provided IDs on single inserts.

# Auto-assigned (default)
id_ = qt.insert((10, 20))

# Custom ID
qt.insert((10, 20), id_=42)
qt.insert((30, 40), id_=1000)

This is useful when correlating quadtree entries with external data structures like lists or database rows.

Collision Warning

The quadtree does not validate ID uniqueness. Mixing auto-assigned and custom IDs, or reusing custom IDs, leads to undefined behavior on deletion and update. If you use custom IDs, you are responsible for ensuring uniqueness.

QuadTreeObjects does not support custom IDs because it uses dense ID allocation for efficient object lookup.

Update/Move API

Moving items requires coordinates for non-Objects classes (which don't store them internally).

Points

# QuadTree: must provide old coordinates
qt.update(id_, old_x, old_y, new_x, new_y)

# QuadTreeObjects: only needs new coordinates
qt_obj.update(id_, new_x, new_y)

Rects

# RectQuadTree: must provide old coordinates
rqt.update(id_, old_min_x, old_min_y, old_max_x, old_max_y, new_min_x, new_min_y, new_max_x, new_max_y)

# RectQuadTreeObjects: only needs new coordinates
rqt_obj.update(id_, new_min_x, new_min_y, new_max_x, new_max_y)

Serialization

The serialization format has changed. v1 serialized data cannot be loaded in v2.

Before (v1.x)

# Dict-based (removed)
state = qt.to_dict()
qt2 = QuadTree.from_dict(state)

# Bytes with explicit dtype on load
data = qt.to_bytes()
qt2 = QuadTree.from_bytes(data, dtype="f32")

After (v2.0)

# Bytes only, dtype encoded in payload
data = qt.to_bytes()
qt2 = QuadTree.from_bytes(data)

Objects Classes

Object serialization is now explicit and guarded for safety.

# Without objects (default)
data = qt_obj.to_bytes()
data = qt_obj.to_bytes(include_objects=False)  # equivalent

# With objects (opt-in)
data = qt_obj.to_bytes(include_objects=True)

# Loading requires explicit opt-in for objects
qt2 = QuadTreeObjects.from_bytes(data)                        # objects ignored
qt2 = QuadTreeObjects.from_bytes(data, allow_objects=True)    # objects loaded

Security Note

Object deserialization uses pickle-like semantics. Never load serialized data from untrusted sources with allow_objects=True.

Migrating Persisted Data

If you have v1 serialized data you need to preserve:

  1. Load it with fastquadtree 1.x
  2. Extract the raw point/rect data
  3. Re-insert into a v2 tree
  4. Save with the new format
# Migration script (run with v1.x installed)
import fastquadtree as fqt_v1
import pickle

# Load old data
with open("tree_v1.fqt", "rb") as f:
    old_data = pickle.load(f)

# Extract items (adjust based on your tree type)
items = [...]  # extract from old_data

# Save as intermediate format
with open("tree_items.pkl", "wb") as f:
    pickle.dump(items, f)

# Rebuild script (run with v2.0 installed)
import fastquadtree as fqt
import pickle

with open("tree_items.pkl", "rb") as f:
    items = pickle.load(f)

qt = fqt.QuadTree((0, 0, 100, 100), capacity=4)
for x, y in items:
    qt.insert((x, y))

qt.to_bytes()  # new format

Removed Methods

v1.x v2.0 Replacement
qt.count_items() len(qt)
qt.to_dict() qt.to_bytes()

New Features in v2.0

These are non-breaking additions you can start using:

__contains__

if (10.0, 20.0) in qt:
    print("Point exists")

Iteration

# QuadTree
for id_, x, y in qt:
    ...

# QuadTreeObjects
for item in qt_obj:
    print(item.id_, item.x, item.y, item.obj)

query_ids (Objects classes)

Fast path when you only need IDs:

ids = qt_obj.query_ids(rect)  # list[int]

update_by_object (Objects classes)

Convenience method to update an item by finding it via its associated object:

# Points
qt_obj.update_by_object(obj, new_x, new_y)

# Rects
rqt_obj.update_by_object(obj, new_min_x, new_min_y, new_max_x, new_max_y)

If multiple items have the same object, updates the one with the lowest ID. Returns True if the item was found and updated, False otherwise.

Quick Reference

Find and Replace Patterns

Find Replace
QuadTree(..., track_objects=True) QuadTreeObjects(...)
RectQuadTree(..., track_objects=True) RectQuadTreeObjects(...)
, track_objects=False (remove)
, as_items=True (remove, switch to Objects class)
, as_items=False (remove)
.insert_many(np_array) .insert_many_np(np_array)
.query(rect, as_items=...) .query(rect)
.delete(id_, (x, y)) .delete(id_, x, y)
.count_items() len(...)

Import Template

from fastquadtree import (
    QuadTree,
    QuadTreeObjects,
    RectQuadTree,
    RectQuadTreeObjects,
    InsertResult,
    PointItem,
    RectItem,
)