lucisearch 0.8.1

//! Geo shape storage, GeoJSON parsing, and serialization.
//!
//! Provides [`GeoShapeStore`] for per-segment geo_shape field storage with a
//! packed R-tree for spatial candidate selection and serialized shapes for
//! exact predicate evaluation.
//!
//! See [[feature-geo-shape]] and [[geospatial]].

use ::geo::algorithm::bounding_rect::BoundingRect;
use ::geo::geometry::{
    Coord, Geometry, GeometryCollection, LineString, MultiLineString, MultiPoint, MultiPolygon,
    Point, Polygon, Rect,
};
use geo_index::rtree::sort::HilbertSort;
use geo_index::rtree::{RTreeBuilder, RTreeIndex, RTreeRef};

// ---------------------------------------------------------------------------
// GeoJSON parsing
// ---------------------------------------------------------------------------

/// Parse a GeoJSON value into a `geo::Geometry<f64>`.
///
/// Supports all standard GeoJSON types plus Elasticsearch's `envelope`
/// extension. Coordinates use GeoJSON order: `[longitude, latitude]`.
pub fn parse_geojson(value: &serde_json::Value) -> Option<Geometry<f64>> {
    let obj = value.as_object()?;
    let shape_type = obj.get("type").and_then(|v| v.as_str())?;

    match shape_type {
        "Point" | "point" => {
            let coords = obj.get("coordinates")?;
            let c = parse_coord(coords)?;
            Some(Geometry::Point(Point(c)))
        }
        "MultiPoint" | "multipoint" => {
            let coords = obj.get("coordinates")?.as_array()?;
            let points: Option<Vec<Point<f64>>> =
                coords.iter().map(|c| parse_coord(c).map(Point)).collect();
            Some(Geometry::MultiPoint(MultiPoint(points?)))
        }
        "LineString" | "linestring" => {
            let coords = obj.get("coordinates")?;
            let line = parse_linestring(coords)?;
            Some(Geometry::LineString(line))
        }
        "MultiLineString" | "multilinestring" => {
            let coords = obj.get("coordinates")?.as_array()?;
            let lines: Option<Vec<LineString<f64>>> = coords.iter().map(parse_linestring).collect();
            Some(Geometry::MultiLineString(MultiLineString(lines?)))
        }
        "Polygon" | "polygon" => {
            let coords = obj.get("coordinates")?;
            let poly = parse_polygon(coords)?;
            Some(Geometry::Polygon(poly))
        }
        "MultiPolygon" | "multipolygon" => {
            let coords = obj.get("coordinates")?.as_array()?;
            let polys: Option<Vec<Polygon<f64>>> = coords.iter().map(parse_polygon).collect();
            Some(Geometry::MultiPolygon(MultiPolygon(polys?)))
        }
        "GeometryCollection" | "geometrycollection" => {
            let geoms = obj.get("geometries")?.as_array()?;
            let parsed: Option<Vec<Geometry<f64>>> = geoms.iter().map(parse_geojson).collect();
            Some(Geometry::GeometryCollection(GeometryCollection(parsed?)))
        }
        "envelope" | "Envelope" => {
            // ES extension: [[minLon, maxLat], [maxLon, minLat]]
            let coords = obj.get("coordinates")?.as_array()?;
            if coords.len() != 2 {
                return None;
            }
            let tl = parse_coord(&coords[0])?; // [minLon, maxLat]
            let br = parse_coord(&coords[1])?; // [maxLon, minLat]
            Some(Geometry::Rect(Rect::new(
                Coord { x: tl.x, y: br.y }, // min corner
                Coord { x: br.x, y: tl.y }, // max corner
            )))
        }
        _ => None,
    }
}

/// Parse a single GeoJSON coordinate `[lon, lat]`.
fn parse_coord(value: &serde_json::Value) -> Option<Coord<f64>> {
    let arr = value.as_array()?;
    if arr.len() < 2 {
        return None;
    }
    let x = arr[0].as_f64()?; // longitude
    let y = arr[1].as_f64()?; // latitude
    Some(Coord { x, y })
}

/// Parse a GeoJSON coordinate array into a `LineString`.
fn parse_linestring(value: &serde_json::Value) -> Option<LineString<f64>> {
    let arr = value.as_array()?;
    let coords: Option<Vec<Coord<f64>>> = arr.iter().map(parse_coord).collect();
    Some(LineString(coords?))
}

/// Parse a GeoJSON polygon (array of rings).
fn parse_polygon(value: &serde_json::Value) -> Option<Polygon<f64>> {
    let rings = value.as_array()?;
    if rings.is_empty() {
        return None;
    }
    let exterior = parse_linestring(&rings[0])?;
    let interiors: Option<Vec<LineString<f64>>> = rings[1..].iter().map(parse_linestring).collect();
    Some(Polygon::new(exterior, interiors?))
}

// ---------------------------------------------------------------------------
// Bounding box computation
// ---------------------------------------------------------------------------

/// Compute (min_x, min_y, max_x, max_y) for a geometry.
/// Returns `(min_lon, min_lat, max_lon, max_lat)`.
pub fn compute_bbox(geom: &Geometry<f64>) -> Option<(f64, f64, f64, f64)> {
    let rect = geom.bounding_rect()?;
    Some((rect.min().x, rect.min().y, rect.max().x, rect.max().y))
}

// ---------------------------------------------------------------------------
// Shape serialization
// ---------------------------------------------------------------------------

const TAG_POINT: u8 = 0;
const TAG_MULTI_POINT: u8 = 1;
const TAG_LINE_STRING: u8 = 2;
const TAG_MULTI_LINE_STRING: u8 = 3;
const TAG_POLYGON: u8 = 4;
const TAG_MULTI_POLYGON: u8 = 5;
const TAG_GEOMETRY_COLLECTION: u8 = 6;
const TAG_RECT: u8 = 7;

/// Serialize a geometry into a compact binary format.
pub fn serialize_shape(geom: &Geometry<f64>) -> Vec<u8> {
    let mut buf = Vec::new();
    write_shape(geom, &mut buf);
    buf
}

fn write_coord(c: &Coord<f64>, buf: &mut Vec<u8>) {
    buf.extend_from_slice(&c.x.to_le_bytes());
    buf.extend_from_slice(&c.y.to_le_bytes());
}

fn write_coords(coords: &[Coord<f64>], buf: &mut Vec<u8>) {
    buf.extend_from_slice(&(coords.len() as u32).to_le_bytes());
    for c in coords {
        write_coord(c, buf);
    }
}

fn write_shape(geom: &Geometry<f64>, buf: &mut Vec<u8>) {
    match geom {
        Geometry::Point(p) => {
            buf.push(TAG_POINT);
            write_coord(&p.0, buf);
        }
        Geometry::MultiPoint(mp) => {
            buf.push(TAG_MULTI_POINT);
            buf.extend_from_slice(&(mp.0.len() as u32).to_le_bytes());
            for p in &mp.0 {
                write_coord(&p.0, buf);
            }
        }
        Geometry::LineString(ls) => {
            buf.push(TAG_LINE_STRING);
            write_coords(&ls.0, buf);
        }
        Geometry::MultiLineString(mls) => {
            buf.push(TAG_MULTI_LINE_STRING);
            buf.extend_from_slice(&(mls.0.len() as u32).to_le_bytes());
            for ls in &mls.0 {
                write_coords(&ls.0, buf);
            }
        }
        Geometry::Polygon(poly) => {
            buf.push(TAG_POLYGON);
            let num_rings = 1 + poly.interiors().len();
            buf.extend_from_slice(&(num_rings as u32).to_le_bytes());
            write_coords(&poly.exterior().0, buf);
            for ring in poly.interiors() {
                write_coords(&ring.0, buf);
            }
        }
        Geometry::MultiPolygon(mp) => {
            buf.push(TAG_MULTI_POLYGON);
            buf.extend_from_slice(&(mp.0.len() as u32).to_le_bytes());
            for poly in &mp.0 {
                let num_rings = 1 + poly.interiors().len();
                buf.extend_from_slice(&(num_rings as u32).to_le_bytes());
                write_coords(&poly.exterior().0, buf);
                for ring in poly.interiors() {
                    write_coords(&ring.0, buf);
                }
            }
        }
        Geometry::GeometryCollection(gc) => {
            buf.push(TAG_GEOMETRY_COLLECTION);
            buf.extend_from_slice(&(gc.0.len() as u32).to_le_bytes());
            for g in &gc.0 {
                let child = serialize_shape(g);
                buf.extend_from_slice(&(child.len() as u32).to_le_bytes());
                buf.extend_from_slice(&child);
            }
        }
        Geometry::Rect(r) => {
            buf.push(TAG_RECT);
            write_coord(&r.min(), buf);
            write_coord(&r.max(), buf);
        }
        // geo crate has Line and Triangle — treat as LineString
        Geometry::Line(l) => {
            buf.push(TAG_LINE_STRING);
            let coords = vec![l.start, l.end];
            write_coords(&coords, buf);
        }
        Geometry::Triangle(t) => {
            buf.push(TAG_POLYGON);
            buf.extend_from_slice(&1u32.to_le_bytes()); // 1 ring
            let coords = vec![t.0, t.1, t.2, t.0]; // closed ring
            write_coords(&coords, buf);
        }
    }
}

/// Deserialize a geometry from binary data. Returns (geometry, bytes_consumed).
pub fn deserialize_shape(data: &[u8]) -> Option<(Geometry<f64>, usize)> {
    if data.is_empty() {
        return None;
    }
    let tag = data[0];
    let mut pos = 1;

    match tag {
        TAG_POINT => {
            let c = read_coord(data, &mut pos)?;
            Some((Geometry::Point(Point(c)), pos))
        }
        TAG_MULTI_POINT => {
            let count = read_u32(data, &mut pos)? as usize;
            let mut points = Vec::with_capacity(count);
            for _ in 0..count {
                points.push(Point(read_coord(data, &mut pos)?));
            }
            Some((Geometry::MultiPoint(MultiPoint(points)), pos))
        }
        TAG_LINE_STRING => {
            let coords = read_coords(data, &mut pos)?;
            Some((Geometry::LineString(LineString(coords)), pos))
        }
        TAG_MULTI_LINE_STRING => {
            let count = read_u32(data, &mut pos)? as usize;
            let mut lines = Vec::with_capacity(count);
            for _ in 0..count {
                lines.push(LineString(read_coords(data, &mut pos)?));
            }
            Some((Geometry::MultiLineString(MultiLineString(lines)), pos))
        }
        TAG_POLYGON => {
            let poly = read_polygon(data, &mut pos)?;
            Some((Geometry::Polygon(poly), pos))
        }
        TAG_MULTI_POLYGON => {
            let count = read_u32(data, &mut pos)? as usize;
            let mut polys = Vec::with_capacity(count);
            for _ in 0..count {
                polys.push(read_polygon(data, &mut pos)?);
            }
            Some((Geometry::MultiPolygon(MultiPolygon(polys)), pos))
        }
        TAG_GEOMETRY_COLLECTION => {
            let count = read_u32(data, &mut pos)? as usize;
            let mut geoms = Vec::with_capacity(count);
            for _ in 0..count {
                let len = read_u32(data, &mut pos)? as usize;
                let (g, _) = deserialize_shape(&data[pos..pos + len])?;
                geoms.push(g);
                pos += len;
            }
            Some((Geometry::GeometryCollection(GeometryCollection(geoms)), pos))
        }
        TAG_RECT => {
            let min = read_coord(data, &mut pos)?;
            let max = read_coord(data, &mut pos)?;
            Some((Geometry::Rect(Rect::new(min, max)), pos))
        }
        _ => None,
    }
}

fn read_f64(data: &[u8], pos: &mut usize) -> Option<f64> {
    if *pos + 8 > data.len() {
        return None;
    }
    let val = f64::from_le_bytes(data[*pos..*pos + 8].try_into().ok()?);
    *pos += 8;
    Some(val)
}

fn read_u32(data: &[u8], pos: &mut usize) -> Option<u32> {
    if *pos + 4 > data.len() {
        return None;
    }
    let val = u32::from_le_bytes(data[*pos..*pos + 4].try_into().ok()?);
    *pos += 4;
    Some(val)
}

fn read_coord(data: &[u8], pos: &mut usize) -> Option<Coord<f64>> {
    let x = read_f64(data, pos)?;
    let y = read_f64(data, pos)?;
    Some(Coord { x, y })
}

fn read_coords(data: &[u8], pos: &mut usize) -> Option<Vec<Coord<f64>>> {
    let count = read_u32(data, pos)? as usize;
    let mut coords = Vec::with_capacity(count);
    for _ in 0..count {
        coords.push(read_coord(data, pos)?);
    }
    Some(coords)
}

fn read_polygon(data: &[u8], pos: &mut usize) -> Option<Polygon<f64>> {
    let num_rings = read_u32(data, pos)? as usize;
    if num_rings == 0 {
        return None;
    }
    let exterior = LineString(read_coords(data, pos)?);
    let mut interiors = Vec::with_capacity(num_rings.saturating_sub(1));
    for _ in 1..num_rings {
        interiors.push(LineString(read_coords(data, pos)?));
    }
    Some(Polygon::new(exterior, interiors))
}

// ---------------------------------------------------------------------------
// GeoShapeStore
// ---------------------------------------------------------------------------

/// Per-segment geo shape storage with packed R-tree for candidate selection.
///
/// Stores bounding boxes for R-tree indexing and serialized shape data for
/// exact predicate evaluation. Indexed by doc_id.
///
/// See [[feature-geo-shape]].
#[derive(Clone)]
pub struct GeoShapeStore {
    count: usize,
    /// Per-doc bounding boxes (min_x, min_y, max_x, max_y). NaN = null.
    bbox_min_xs: Vec<f64>,
    bbox_min_ys: Vec<f64>,
    bbox_max_xs: Vec<f64>,
    bbox_max_ys: Vec<f64>,
    /// Per-doc offsets into shape_data. u32::MAX = null.
    shape_offsets: Vec<u32>,
    /// Concatenated serialized shapes.
    shape_data: Vec<u8>,
    /// Pre-built packed R-tree bytes (built during to_bytes, loaded from from_bytes).
    rtree_data: Vec<u8>,
}

impl GeoShapeStore {
    pub fn new() -> Self {
        Self {
            count: 0,
            bbox_min_xs: Vec::new(),
            bbox_min_ys: Vec::new(),
            bbox_max_xs: Vec::new(),
            bbox_max_ys: Vec::new(),
            shape_offsets: Vec::new(),
            shape_data: Vec::new(),
            rtree_data: Vec::new(),
        }
    }

    /// Add a geometry for the current doc.
    pub fn add(&mut self, geom: &Geometry<f64>) {
        let offset = self.shape_data.len() as u32;
        let serialized = serialize_shape(geom);
        self.shape_data.extend_from_slice(&serialized);
        self.shape_offsets.push(offset);

        if let Some((min_x, min_y, max_x, max_y)) = compute_bbox(geom) {
            self.bbox_min_xs.push(min_x);
            self.bbox_min_ys.push(min_y);
            self.bbox_max_xs.push(max_x);
            self.bbox_max_ys.push(max_y);
        } else {
            self.bbox_min_xs.push(f64::NAN);
            self.bbox_min_ys.push(f64::NAN);
            self.bbox_max_xs.push(f64::NAN);
            self.bbox_max_ys.push(f64::NAN);
        }
        self.count += 1;
    }

    /// Add a null entry for a doc without a geo_shape value.
    pub fn add_null(&mut self) {
        self.bbox_min_xs.push(f64::NAN);
        self.bbox_min_ys.push(f64::NAN);
        self.bbox_max_xs.push(f64::NAN);
        self.bbox_max_ys.push(f64::NAN);
        self.shape_offsets.push(u32::MAX);
        self.count += 1;
    }

    pub fn len(&self) -> usize {
        self.count
    }

    pub fn is_empty(&self) -> bool {
        self.count == 0
    }

    /// Access the raw shape offsets (for R-tree doc ID mapping).
    pub fn shape_offsets_ref(&self) -> &[u32] {
        &self.shape_offsets
    }

    /// Get the pre-built R-tree bytes (empty if not yet built).
    pub fn rtree_data(&self) -> &[u8] {
        &self.rtree_data
    }

    /// Check if a doc's shape is a Rect (bbox == exact geometry).
    pub fn is_rect_shape(&self, doc_id: u32) -> bool {
        let i = doc_id as usize;
        if i >= self.count {
            return false;
        }
        let offset = self.shape_offsets[i];
        if offset == u32::MAX {
            return false;
        }
        let o = offset as usize;
        o < self.shape_data.len() && self.shape_data[o] == TAG_RECT
    }

    /// Get the bounding box for a doc, or None if null.
    pub fn get_bbox(&self, doc_id: u32) -> Option<(f64, f64, f64, f64)> {
        let i = doc_id as usize;
        if i >= self.count {
            return None;
        }
        let min_x = self.bbox_min_xs[i];
        if min_x.is_nan() {
            return None;
        }
        Some((
            min_x,
            self.bbox_min_ys[i],
            self.bbox_max_xs[i],
            self.bbox_max_ys[i],
        ))
    }

    /// Deserialize and return the full geometry for a doc.
    pub fn get_shape(&self, doc_id: u32) -> Option<Geometry<f64>> {
        let i = doc_id as usize;
        if i >= self.count {
            return None;
        }
        let offset = self.shape_offsets[i];
        if offset == u32::MAX {
            return None;
        }
        let (geom, _) = deserialize_shape(&self.shape_data[offset as usize..])?;
        Some(geom)
    }

    /// Build a packed R-tree from the stored bounding boxes.
    pub fn build_rtree(&self) -> Vec<u8> {
        let valid_count = self
            .shape_offsets
            .iter()
            .filter(|&&o| o != u32::MAX)
            .count();
        if valid_count == 0 {
            return Vec::new();
        }
        let mut builder = RTreeBuilder::<f64>::new(valid_count as u32);
        for i in 0..self.count {
            if self.shape_offsets[i] != u32::MAX {
                builder.add(
                    self.bbox_min_xs[i],
                    self.bbox_min_ys[i],
                    self.bbox_max_xs[i],
                    self.bbox_max_ys[i],
                );
            }
        }
        let tree = builder.finish::<HilbertSort>();
        tree.into_inner()
    }

    /// Search the R-tree for candidates whose bboxes intersect the query bbox.
    /// Returns doc IDs (not R-tree insertion indices).
    pub fn search_rtree(
        rtree_data: &[u8],
        query_bbox: (f64, f64, f64, f64),
        shape_offsets: &[u32],
    ) -> Vec<u32> {
        if rtree_data.is_empty() {
            return Vec::new();
        }
        let tree = match RTreeRef::<f64>::try_new(&rtree_data) {
            Ok(t) => t,
            Err(_) => return Vec::new(),
        };
        let (min_x, min_y, max_x, max_y) = query_bbox;
        let rtree_indices = tree.search(min_x, min_y, max_x, max_y);

        // Map R-tree insertion indices back to doc IDs.
        // Insertion order = iteration order of non-null docs.
        let doc_id_map: Vec<u32> = shape_offsets
            .iter()
            .enumerate()
            .filter(|(_, o)| **o != u32::MAX)
            .map(|(i, _)| i as u32)
            .collect();

        rtree_indices
            .iter()
            .filter_map(|&idx| doc_id_map.get(idx as usize).copied())
            .collect()
    }

    // -----------------------------------------------------------------------
    // Binary serialization
    // -----------------------------------------------------------------------

    /// Serialize to bytes for segment storage.
    pub fn to_bytes(&self) -> Vec<u8> {
        let rtree_data = self.build_rtree();
        let mut buf = Vec::new();

        // Count
        buf.extend_from_slice(&(self.count as u32).to_le_bytes());

        // Bbox arrays
        for v in &self.bbox_min_xs {
            buf.extend_from_slice(&v.to_le_bytes());
        }
        for v in &self.bbox_min_ys {
            buf.extend_from_slice(&v.to_le_bytes());
        }
        for v in &self.bbox_max_xs {
            buf.extend_from_slice(&v.to_le_bytes());
        }
        for v in &self.bbox_max_ys {
            buf.extend_from_slice(&v.to_le_bytes());
        }

        // Shape offsets
        for v in &self.shape_offsets {
            buf.extend_from_slice(&v.to_le_bytes());
        }

        // Shape data
        buf.extend_from_slice(&(self.shape_data.len() as u32).to_le_bytes());
        buf.extend_from_slice(&self.shape_data);

        // R-tree
        buf.extend_from_slice(&(rtree_data.len() as u32).to_le_bytes());
        buf.extend_from_slice(&rtree_data);

        buf
    }

    /// Deserialize from segment bytes.
    pub fn from_bytes(data: &[u8]) -> Self {
        if data.len() < 4 {
            return Self::new();
        }
        let count = u32::from_le_bytes(data[0..4].try_into().unwrap()) as usize;
        let mut pos = 4;

        let read_f64_vec = |data: &[u8], pos: &mut usize, n: usize| -> Vec<f64> {
            let mut v = Vec::with_capacity(n);
            for _ in 0..n {
                let val = f64::from_le_bytes(data[*pos..*pos + 8].try_into().unwrap());
                v.push(val);
                *pos += 8;
            }
            v
        };

        let bbox_min_xs = read_f64_vec(data, &mut pos, count);
        let bbox_min_ys = read_f64_vec(data, &mut pos, count);
        let bbox_max_xs = read_f64_vec(data, &mut pos, count);
        let bbox_max_ys = read_f64_vec(data, &mut pos, count);

        let mut shape_offsets = Vec::with_capacity(count);
        for _ in 0..count {
            let v = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
            shape_offsets.push(v);
            pos += 4;
        }

        let shape_data_len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize;
        pos += 4;
        let shape_data = data[pos..pos + shape_data_len].to_vec();
        pos += shape_data_len;

        let rtree_data = if pos + 4 <= data.len() {
            let rtree_len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize;
            pos += 4;
            if rtree_len > 0 && pos + rtree_len <= data.len() {
                data[pos..pos + rtree_len].to_vec()
            } else {
                Vec::new()
            }
        } else {
            Vec::new()
        };

        Self {
            count,
            bbox_min_xs,
            bbox_min_ys,
            bbox_max_xs,
            bbox_max_ys,
            shape_offsets,
            shape_data,
            rtree_data,
        }
    }

    /// Get the R-tree bytes from already-serialized store data.
    /// Used by the reader to pass R-tree data directly to search_rtree().
    pub fn rtree_offset_in_bytes(data: &[u8]) -> Option<(usize, usize)> {
        if data.len() < 4 {
            return None;
        }
        let count = u32::from_le_bytes(data[0..4].try_into().unwrap()) as usize;
        // Skip: count(4) + 4 bbox arrays(count*8 each) + offsets(count*4) + shape_data_len(4) + shape_data
        let mut pos = 4 + count * 8 * 4 + count * 4;
        if pos + 4 > data.len() {
            return None;
        }
        let shape_data_len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize;
        pos += 4 + shape_data_len;
        if pos + 4 > data.len() {
            return None;
        }
        let rtree_len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize;
        pos += 4;
        if rtree_len == 0 || pos + rtree_len > data.len() {
            return None;
        }
        Some((pos, rtree_len))
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;

    #[test]
    fn parse_point() {
        let v = json!({"type": "Point", "coordinates": [-73.98, 40.75]});
        let g = parse_geojson(&v).unwrap();
        if let Geometry::Point(p) = g {
            assert!((p.x() - (-73.98)).abs() < 1e-10);
            assert!((p.y() - 40.75).abs() < 1e-10);
        } else {
            panic!("expected Point");
        }
    }

    #[test]
    fn parse_polygon() {
        let v = json!({
            "type": "Polygon",
            "coordinates": [[[0.0,0.0],[10.0,0.0],[10.0,10.0],[0.0,10.0],[0.0,0.0]]]
        });
        let g = parse_geojson(&v).unwrap();
        assert!(matches!(g, Geometry::Polygon(_)));
    }

    #[test]
    fn parse_envelope() {
        let v = json!({"type": "envelope", "coordinates": [[-77.0, 39.0], [-75.0, 38.0]]});
        let g = parse_geojson(&v).unwrap();
        if let Geometry::Rect(r) = g {
            assert!((r.min().x - (-77.0)).abs() < 1e-10);
            assert!((r.min().y - 38.0).abs() < 1e-10);
            assert!((r.max().x - (-75.0)).abs() < 1e-10);
            assert!((r.max().y - 39.0).abs() < 1e-10);
        } else {
            panic!("expected Rect");
        }
    }

    #[test]
    fn parse_invalid_returns_none() {
        assert!(parse_geojson(&json!({"type": "Unknown"})).is_none());
        assert!(parse_geojson(&json!(42)).is_none());
    }

    #[test]
    fn serialize_roundtrip_point() {
        let geom = Geometry::Point(Point::new(-73.98, 40.75));
        let bytes = serialize_shape(&geom);
        let (decoded, consumed) = deserialize_shape(&bytes).unwrap();
        assert_eq!(consumed, bytes.len());
        assert_eq!(geom, decoded);
    }

    #[test]
    fn serialize_roundtrip_polygon() {
        let poly = Polygon::new(
            LineString(vec![
                Coord { x: 0.0, y: 0.0 },
                Coord { x: 10.0, y: 0.0 },
                Coord { x: 10.0, y: 10.0 },
                Coord { x: 0.0, y: 10.0 },
                Coord { x: 0.0, y: 0.0 },
            ]),
            vec![],
        );
        let geom = Geometry::Polygon(poly);
        let bytes = serialize_shape(&geom);
        let (decoded, _) = deserialize_shape(&bytes).unwrap();
        assert_eq!(geom, decoded);
    }

    #[test]
    fn serialize_roundtrip_rect() {
        let geom = Geometry::Rect(Rect::new(
            Coord { x: -77.0, y: 38.0 },
            Coord { x: -75.0, y: 39.0 },
        ));
        let bytes = serialize_shape(&geom);
        let (decoded, _) = deserialize_shape(&bytes).unwrap();
        assert_eq!(geom, decoded);
    }

    #[test]
    fn store_add_and_get() {
        let mut store = GeoShapeStore::new();
        let poly = Geometry::Polygon(Polygon::new(
            LineString(vec![
                Coord { x: 0.0, y: 0.0 },
                Coord { x: 10.0, y: 0.0 },
                Coord { x: 10.0, y: 10.0 },
                Coord { x: 0.0, y: 10.0 },
                Coord { x: 0.0, y: 0.0 },
            ]),
            vec![],
        ));
        store.add(&poly);
        store.add_null();

        assert_eq!(store.len(), 2);
        assert!(store.get_bbox(0).is_some());
        assert!(store.get_bbox(1).is_none());
        assert_eq!(store.get_shape(0).unwrap(), poly);
        assert!(store.get_shape(1).is_none());
    }

    #[test]
    fn store_serialization_roundtrip() {
        let mut store = GeoShapeStore::new();
        store.add(&Geometry::Point(Point::new(1.0, 2.0)));
        store.add(&Geometry::Polygon(Polygon::new(
            LineString(vec![
                Coord { x: 0.0, y: 0.0 },
                Coord { x: 5.0, y: 0.0 },
                Coord { x: 5.0, y: 5.0 },
                Coord { x: 0.0, y: 0.0 },
            ]),
            vec![],
        )));

        let bytes = store.to_bytes();
        let restored = GeoShapeStore::from_bytes(&bytes);

        assert_eq!(restored.len(), 2);
        assert_eq!(restored.get_shape(0).unwrap(), store.get_shape(0).unwrap());
        assert_eq!(restored.get_shape(1).unwrap(), store.get_shape(1).unwrap());
    }

    #[test]
    fn rtree_search() {
        let mut store = GeoShapeStore::new();
        // Doc 0: polygon at (0,0)-(10,10)
        store.add(&Geometry::Polygon(Polygon::new(
            LineString(vec![
                Coord { x: 0.0, y: 0.0 },
                Coord { x: 10.0, y: 0.0 },
                Coord { x: 10.0, y: 10.0 },
                Coord { x: 0.0, y: 10.0 },
                Coord { x: 0.0, y: 0.0 },
            ]),
            vec![],
        )));
        // Doc 1: polygon at (20,20)-(30,30)
        store.add(&Geometry::Polygon(Polygon::new(
            LineString(vec![
                Coord { x: 20.0, y: 20.0 },
                Coord { x: 30.0, y: 20.0 },
                Coord { x: 30.0, y: 30.0 },
                Coord { x: 20.0, y: 30.0 },
                Coord { x: 20.0, y: 20.0 },
            ]),
            vec![],
        )));

        let rtree_data = store.build_rtree();
        assert!(!rtree_data.is_empty());

        // Search overlapping doc 0 only
        let hits =
            GeoShapeStore::search_rtree(&rtree_data, (5.0, 5.0, 15.0, 15.0), &store.shape_offsets);
        assert_eq!(hits, vec![0]);

        // Search overlapping doc 1 only
        let hits = GeoShapeStore::search_rtree(
            &rtree_data,
            (25.0, 25.0, 35.0, 35.0),
            &store.shape_offsets,
        );
        assert_eq!(hits, vec![1]);

        // Search overlapping both
        let hits =
            GeoShapeStore::search_rtree(&rtree_data, (0.0, 0.0, 30.0, 30.0), &store.shape_offsets);
        assert!(hits.contains(&0) && hits.contains(&1));
    }
}