pdfsink_rs/

table.rs

use crate::clustering::cluster_items;
use crate::geometry::{objects_to_bbox, rect_to_edges, snap_edges};
use crate::text::{extract_text, extract_words, TextOptions};
use crate::types::{
    BBox, Char, Edge, Line, Orientation, Page, Word,
};
use ordered_float::OrderedFloat;
use std::collections::{BTreeMap, BTreeSet};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TableStrategy {
    Lines,
    LinesStrict,
    Text,
    Explicit,
}

impl Default for TableStrategy {
    fn default() -> Self {
        Self::Lines
    }
}

impl std::str::FromStr for TableStrategy {
    type Err = crate::Error;

    fn from_str(s: &str) -> crate::Result<Self> {
        match s {
            "lines" => Ok(Self::Lines),
            "lines_strict" => Ok(Self::LinesStrict),
            "text" => Ok(Self::Text),
            "explicit" => Ok(Self::Explicit),
            other => Err(crate::Error::Message(format!("unknown table strategy: {other}"))),
        }
    }
}

#[derive(Debug, Clone)]
pub enum ExplicitLine {
    Position(f64),
    Edge(Edge),
}

#[derive(Debug, Clone)]
pub struct TableSettings {
    pub vertical_strategy: TableStrategy,
    pub horizontal_strategy: TableStrategy,
    pub explicit_vertical_lines: Vec<ExplicitLine>,
    pub explicit_horizontal_lines: Vec<ExplicitLine>,
    pub snap_tolerance: f64,
    pub snap_x_tolerance: Option<f64>,
    pub snap_y_tolerance: Option<f64>,
    pub join_tolerance: f64,
    pub join_x_tolerance: Option<f64>,
    pub join_y_tolerance: Option<f64>,
    pub edge_min_length: f64,
    pub edge_min_length_prefilter: f64,
    pub min_words_vertical: usize,
    pub min_words_horizontal: usize,
    pub intersection_tolerance: f64,
    pub intersection_x_tolerance: Option<f64>,
    pub intersection_y_tolerance: Option<f64>,
    pub text_options: TextOptions,
}

impl Default for TableSettings {
    fn default() -> Self {
        Self {
            vertical_strategy: TableStrategy::Lines,
            horizontal_strategy: TableStrategy::Lines,
            explicit_vertical_lines: Vec::new(),
            explicit_horizontal_lines: Vec::new(),
            snap_tolerance: 3.0,
            snap_x_tolerance: None,
            snap_y_tolerance: None,
            join_tolerance: 3.0,
            join_x_tolerance: None,
            join_y_tolerance: None,
            edge_min_length: 3.0,
            edge_min_length_prefilter: 1.0,
            min_words_vertical: 3,
            min_words_horizontal: 1,
            intersection_tolerance: 3.0,
            intersection_x_tolerance: None,
            intersection_y_tolerance: None,
            text_options: TextOptions::default(),
        }
    }
}

impl TableSettings {
    pub fn snap_x_tolerance(&self) -> f64 {
        self.snap_x_tolerance.unwrap_or(self.snap_tolerance)
    }

    pub fn snap_y_tolerance(&self) -> f64 {
        self.snap_y_tolerance.unwrap_or(self.snap_tolerance)
    }

    pub fn join_x_tolerance(&self) -> f64 {
        self.join_x_tolerance.unwrap_or(self.join_tolerance)
    }

    pub fn join_y_tolerance(&self) -> f64 {
        self.join_y_tolerance.unwrap_or(self.join_tolerance)
    }

    pub fn intersection_x_tolerance(&self) -> f64 {
        self.intersection_x_tolerance.unwrap_or(self.intersection_tolerance)
    }

    pub fn intersection_y_tolerance(&self) -> f64 {
        self.intersection_y_tolerance.unwrap_or(self.intersection_tolerance)
    }
}

#[derive(Debug, Clone)]
pub struct CellGroup {
    pub cells: Vec<Option<BBox>>,
    pub bbox: BBox,
}

#[derive(Debug, Clone)]
pub struct Table {
    pub cells: Vec<BBox>,
    pub bbox: BBox,
}

impl Table {
    pub fn rows(&self) -> Vec<CellGroup> {
        self.get_rows_or_cols(true)
    }

    pub fn columns(&self) -> Vec<CellGroup> {
        self.get_rows_or_cols(false)
    }

    pub fn extract(&self, page: &Page, options: &TextOptions) -> Vec<Vec<Option<String>>> {
        let mut table_arr = Vec::new();
        for row in self.rows() {
            let mut row_arr = Vec::new();
            let row_chars: Vec<Char> = page
                .chars
                .iter()
                .filter(|ch| char_in_bbox(ch, row.bbox))
                .cloned()
                .collect();

            for cell in row.cells {
                if let Some(cell_bbox) = cell {
                    let cell_chars: Vec<Char> = row_chars
                        .iter()
                        .filter(|ch| char_in_bbox(ch, cell_bbox))
                        .cloned()
                        .collect();
                    if cell_chars.is_empty() {
                        row_arr.push(Some(String::new()));
                    } else {
                        let mut text_options = options.clone();
                        if text_options.layout {
                            text_options.layout_width = Some(cell_bbox.width());
                            text_options.layout_height = Some(cell_bbox.height());
                            text_options.layout_bbox = Some(cell_bbox);
                        }
                        row_arr.push(Some(extract_text(&cell_chars, &text_options)));
                    }
                } else {
                    row_arr.push(None);
                }
            }
            table_arr.push(row_arr);
        }
        table_arr
    }

    fn get_rows_or_cols(&self, rows: bool) -> Vec<CellGroup> {
        let (axis, antiaxis) = if rows { (0usize, 1usize) } else { (1usize, 0usize) };

        let mut cells = self.cells.clone();
        cells.sort_by(|a, b| {
            let ka = bbox_coord(*a, antiaxis)
                .total_cmp(&bbox_coord(*b, antiaxis))
                .then_with(|| bbox_coord(*a, axis).total_cmp(&bbox_coord(*b, axis)));
            ka
        });

        let mut xs: Vec<f64> = cells.iter().map(|bbox| bbox_coord(*bbox, axis)).collect();
        xs.sort_by(|a, b| a.total_cmp(b));
        xs.dedup_by(|a, b| (*a - *b).abs() < 0.0001);

        let groups = cluster_items(&cells, |bbox| bbox_coord(*bbox, antiaxis), 0.0);
        let mut out = Vec::new();
        for group in groups {
            let mut row_cells = Vec::new();
            for x in &xs {
                let cell = group
                    .iter()
                    .find(|bbox| (bbox_coord(**bbox, axis) - *x).abs() < 0.0001)
                    .copied();
                row_cells.push(cell);
            }

            let bbox = merged_optional_bbox(&row_cells);
            out.push(CellGroup { cells: row_cells, bbox });
        }
        out
    }
}

#[derive(Debug, Clone)]
pub struct TableFinder {
    pub settings: TableSettings,
    pub edges: Vec<Edge>,
    pub intersections: BTreeMap<PointKey, Intersection>,
    pub cells: Vec<BBox>,
    pub tables: Vec<Table>,
}

impl TableFinder {
    pub fn new(page: &Page, settings: TableSettings) -> crate::Result<Self> {
        let edges = get_edges(page, &settings)?;
        let intersections = edges_to_intersections(
            &edges,
            settings.intersection_x_tolerance(),
            settings.intersection_y_tolerance(),
        );
        let cells = intersections_to_cells(&intersections);
        let tables = cells_to_tables(&cells)
            .into_iter()
            .map(|group| {
                let bbox = merge_bboxes(&group);
                Table { cells: group, bbox }
            })
            .collect();

        Ok(Self {
            settings,
            edges,
            intersections,
            cells,
            tables,
        })
    }
}

type PointKey = (OrderedFloat<f64>, OrderedFloat<f64>);
type BBoxKey = (
    OrderedFloat<f64>,
    OrderedFloat<f64>,
    OrderedFloat<f64>,
    OrderedFloat<f64>,
);

#[derive(Debug, Clone, Default)]
pub struct Intersection {
    pub vertical: Vec<Edge>,
    pub horizontal: Vec<Edge>,
}

fn get_edges(page: &Page, settings: &TableSettings) -> crate::Result<Vec<Edge>> {
    if matches!(settings.vertical_strategy, TableStrategy::Explicit) && settings.explicit_vertical_lines.len() < 2 {
        return Err(crate::Error::Message(
            "explicit vertical strategy requires at least two explicit vertical lines".to_string(),
        ));
    }
    if matches!(settings.horizontal_strategy, TableStrategy::Explicit) && settings.explicit_horizontal_lines.len() < 2 {
        return Err(crate::Error::Message(
            "explicit horizontal strategy requires at least two explicit horizontal lines".to_string(),
        ));
    }

    let words = if matches!(settings.vertical_strategy, TableStrategy::Text)
        || matches!(settings.horizontal_strategy, TableStrategy::Text)
    {
        extract_words(&page.chars, &settings.text_options, false)
    } else {
        Vec::new()
    };

    let mut v_explicit = Vec::new();
    for entry in &settings.explicit_vertical_lines {
        match entry {
            ExplicitLine::Position(x) => v_explicit.push(Edge {
                x0: *x,
                top: page.bbox.top,
                x1: *x,
                bottom: page.bbox.bottom,
                width: 0.0,
                height: page.bbox.height(),
                orientation: Orientation::Vertical,
                object_type: "explicit".to_string(),
            }),
            ExplicitLine::Edge(edge) => {
                if edge.orientation == Orientation::Vertical {
                    v_explicit.push(edge.clone());
                }
            }
        }
    }

    let mut h_explicit = Vec::new();
    for entry in &settings.explicit_horizontal_lines {
        match entry {
            ExplicitLine::Position(y) => h_explicit.push(Edge {
                x0: page.bbox.x0,
                top: *y,
                x1: page.bbox.x1,
                bottom: *y,
                width: page.bbox.width(),
                height: 0.0,
                orientation: Orientation::Horizontal,
                object_type: "explicit".to_string(),
            }),
            ExplicitLine::Edge(edge) => {
                if edge.orientation == Orientation::Horizontal {
                    h_explicit.push(edge.clone());
                }
            }
        }
    }

    let mut vertical = match settings.vertical_strategy {
        TableStrategy::Lines => filter_edges(&page.edges(), Some(Orientation::Vertical), None, settings.edge_min_length_prefilter),
        TableStrategy::LinesStrict => filter_edges(
            &page.edges(),
            Some(Orientation::Vertical),
            Some("line"),
            settings.edge_min_length_prefilter,
        ),
        TableStrategy::Text => words_to_edges_v(&words, settings.min_words_vertical),
        TableStrategy::Explicit => Vec::new(),
    };
    vertical.extend(v_explicit);

    let mut horizontal = match settings.horizontal_strategy {
        TableStrategy::Lines => filter_edges(&page.edges(), Some(Orientation::Horizontal), None, settings.edge_min_length_prefilter),
        TableStrategy::LinesStrict => filter_edges(
            &page.edges(),
            Some(Orientation::Horizontal),
            Some("line"),
            settings.edge_min_length_prefilter,
        ),
        TableStrategy::Text => words_to_edges_h(&words, settings.min_words_horizontal),
        TableStrategy::Explicit => Vec::new(),
    };
    horizontal.extend(h_explicit);

    let mut edges = Vec::new();
    edges.extend(vertical);
    edges.extend(horizontal);

    let merged = merge_edges(
        &edges,
        settings.snap_x_tolerance(),
        settings.snap_y_tolerance(),
        settings.join_x_tolerance(),
        settings.join_y_tolerance(),
    );

    Ok(filter_edges(&merged, None, None, settings.edge_min_length))
}

fn filter_edges(
    edges: &[Edge],
    orientation: Option<Orientation>,
    edge_type: Option<&str>,
    min_length: f64,
) -> Vec<Edge> {
    edges
        .iter()
        .filter(|edge| {
            let orientation_ok = orientation.map(|value| value == edge.orientation).unwrap_or(true);
            let edge_type_ok = edge_type.map(|value| value == edge.object_type).unwrap_or(true);
            let dim = if edge.orientation == Orientation::Vertical {
                edge.height
            } else {
                edge.width
            };
            orientation_ok && edge_type_ok && dim >= min_length
        })
        .cloned()
        .collect()
}

fn merge_edges(
    edges: &[Edge],
    snap_x_tolerance: f64,
    snap_y_tolerance: f64,
    join_x_tolerance: f64,
    join_y_tolerance: f64,
) -> Vec<Edge> {
    let snapped = if snap_x_tolerance > 0.0 || snap_y_tolerance > 0.0 {
        snap_edges(edges, snap_x_tolerance, snap_y_tolerance)
    } else {
        edges.to_vec()
    };

    let mut sorted = snapped;
    sorted.sort_by(|a, b| edge_group_key(a).cmp(&edge_group_key(b)));

    let mut out = Vec::new();
    let mut idx = 0usize;
    while idx < sorted.len() {
        let key = edge_group_key(&sorted[idx]);
        let mut end = idx + 1;
        while end < sorted.len() && edge_group_key(&sorted[end]) == key {
            end += 1;
        }

        let tolerance = if key.0 == 'h' {
            join_x_tolerance
        } else {
            join_y_tolerance
        };

        out.extend(join_edge_group(&sorted[idx..end], key.0, tolerance));
        idx = end;
    }

    out
}

fn edge_group_key(edge: &Edge) -> (char, OrderedFloat<f64>) {
    match edge.orientation {
        Orientation::Horizontal => ('h', OrderedFloat(edge.top)),
        Orientation::Vertical => ('v', OrderedFloat(edge.x0)),
    }
}

fn join_edge_group(edges: &[Edge], orientation: char, tolerance: f64) -> Vec<Edge> {
    if edges.is_empty() {
        return Vec::new();
    }
    let mut sorted = edges.to_vec();
    if orientation == 'h' {
        sorted.sort_by(|a, b| a.x0.total_cmp(&b.x0));
    } else {
        sorted.sort_by(|a, b| a.top.total_cmp(&b.top));
    }

    let mut joined = vec![sorted[0].clone()];
    for edge in sorted.into_iter().skip(1) {
        let last = joined.last_mut().expect("non-empty");
        let overlaps = if orientation == 'h' {
            edge.x0 <= last.x1 + tolerance
        } else {
            edge.top <= last.bottom + tolerance
        };

        if overlaps {
            if orientation == 'h' && edge.x1 > last.x1 {
                last.x1 = edge.x1;
                last.width = last.x1 - last.x0;
            } else if orientation == 'v' && edge.bottom > last.bottom {
                last.bottom = edge.bottom;
                last.height = last.bottom - last.top;
            }
        } else {
            joined.push(edge);
        }
    }
    joined
}

fn words_to_edges_h(words: &[Word], threshold: usize) -> Vec<Edge> {
    let clusters = cluster_items(words, |word| word.top, 1.0);
    let large: Vec<Vec<Word>> = clusters.into_iter().filter(|cluster| cluster.len() >= threshold).collect();
    if large.is_empty() {
        return Vec::new();
    }

    let rects: Vec<BBox> = large
        .iter()
        .filter_map(|cluster| objects_to_bbox(cluster))
        .collect();

    if rects.is_empty() {
        return Vec::new();
    }

    let min_x0 = rects.iter().map(|bbox| bbox.x0).fold(f64::INFINITY, f64::min);
    let max_x1 = rects.iter().map(|bbox| bbox.x1).fold(f64::NEG_INFINITY, f64::max);

    let mut edges = Vec::new();
    for rect in rects {
        edges.push(Edge {
            x0: min_x0,
            top: rect.top,
            x1: max_x1,
            bottom: rect.top,
            width: max_x1 - min_x0,
            height: 0.0,
            orientation: Orientation::Horizontal,
            object_type: "text".to_string(),
        });
        edges.push(Edge {
            x0: min_x0,
            top: rect.bottom,
            x1: max_x1,
            bottom: rect.bottom,
            width: max_x1 - min_x0,
            height: 0.0,
            orientation: Orientation::Horizontal,
            object_type: "text".to_string(),
        });
    }
    edges
}

fn words_to_edges_v(words: &[Word], threshold: usize) -> Vec<Edge> {
    let by_x0 = cluster_items(words, |word| word.x0, 1.0);
    let by_x1 = cluster_items(words, |word| word.x1, 1.0);
    let by_center = cluster_items(words, |word| (word.x0 + word.x1) / 2.0, 1.0);

    let mut clusters = Vec::new();
    clusters.extend(by_x0);
    clusters.extend(by_x1);
    clusters.extend(by_center);
    clusters.sort_by(|a, b| b.len().cmp(&a.len()));

    let large: Vec<Vec<Word>> = clusters.into_iter().filter(|cluster| cluster.len() >= threshold).collect();
    let mut boxes: Vec<BBox> = large.iter().filter_map(|cluster| objects_to_bbox(cluster)).collect();

    let mut condensed = Vec::new();
    for bbox in boxes.drain(..) {
        if !condensed.iter().any(|existing: &BBox| existing.overlap(bbox).is_some()) {
            condensed.push(bbox);
        }
    }

    if condensed.is_empty() {
        return Vec::new();
    }

    condensed.sort_by(|a, b| a.x0.total_cmp(&b.x0));
    let max_x1 = condensed.iter().map(|bbox| bbox.x1).fold(f64::NEG_INFINITY, f64::max);
    let min_top = condensed.iter().map(|bbox| bbox.top).fold(f64::INFINITY, f64::min);
    let max_bottom = condensed.iter().map(|bbox| bbox.bottom).fold(f64::NEG_INFINITY, f64::max);

    let mut out = Vec::new();
    for bbox in &condensed {
        out.push(Edge {
            x0: bbox.x0,
            top: min_top,
            x1: bbox.x0,
            bottom: max_bottom,
            width: 0.0,
            height: max_bottom - min_top,
            orientation: Orientation::Vertical,
            object_type: "text".to_string(),
        });
    }

    out.push(Edge {
        x0: max_x1,
        top: min_top,
        x1: max_x1,
        bottom: max_bottom,
        width: 0.0,
        height: max_bottom - min_top,
        orientation: Orientation::Vertical,
        object_type: "text".to_string(),
    });

    out
}

fn edges_to_intersections(edges: &[Edge], x_tolerance: f64, y_tolerance: f64) -> BTreeMap<PointKey, Intersection> {
    let vertical: Vec<Edge> = edges
        .iter()
        .filter(|edge| edge.orientation == Orientation::Vertical)
        .cloned()
        .collect();
    let horizontal: Vec<Edge> = edges
        .iter()
        .filter(|edge| edge.orientation == Orientation::Horizontal)
        .cloned()
        .collect();

    let mut intersections: BTreeMap<PointKey, Intersection> = BTreeMap::new();
    for v in &vertical {
        for h in &horizontal {
            if v.top <= h.top + y_tolerance
                && v.bottom >= h.top - y_tolerance
                && v.x0 >= h.x0 - x_tolerance
                && v.x0 <= h.x1 + x_tolerance
            {
                let key = (OrderedFloat(v.x0), OrderedFloat(h.top));
                let entry = intersections.entry(key).or_default();
                entry.vertical.push(v.clone());
                entry.horizontal.push(h.clone());
            }
        }
    }
    intersections
}

fn intersections_to_cells(intersections: &BTreeMap<PointKey, Intersection>) -> Vec<BBox> {
    let points: Vec<PointKey> = intersections.keys().copied().collect();
    let mut out = Vec::new();

    for (idx, point) in points.iter().enumerate() {
        let below: Vec<PointKey> = points.iter().copied().skip(idx + 1).filter(|other| other.0 == point.0).collect();
        let right: Vec<PointKey> = points.iter().copied().skip(idx + 1).filter(|other| other.1 == point.1).collect();

        for below_pt in &below {
            if !edge_connects(*point, *below_pt, intersections) {
                continue;
            }
            for right_pt in &right {
                if !edge_connects(*point, *right_pt, intersections) {
                    continue;
                }

                let bottom_right = (right_pt.0, below_pt.1);
                if intersections.contains_key(&bottom_right)
                    && edge_connects(bottom_right, *right_pt, intersections)
                    && edge_connects(bottom_right, *below_pt, intersections)
                {
                    out.push(BBox::new(point.0.into_inner(), point.1.into_inner(), right_pt.0.into_inner(), below_pt.1.into_inner()));
                    break;
                }
            }
        }
    }

    out
}

fn edge_connects(p1: PointKey, p2: PointKey, intersections: &BTreeMap<PointKey, Intersection>) -> bool {
    if p1.0 == p2.0 {
        let a: BTreeSet<BBoxKey> = intersections[&p1]
            .vertical
            .iter()
            .map(edge_bbox_key)
            .collect();
        let b: BTreeSet<BBoxKey> = intersections[&p2]
            .vertical
            .iter()
            .map(edge_bbox_key)
            .collect();
        return !a.is_disjoint(&b);
    }

    if p1.1 == p2.1 {
        let a: BTreeSet<BBoxKey> = intersections[&p1]
            .horizontal
            .iter()
            .map(edge_bbox_key)
            .collect();
        let b: BTreeSet<BBoxKey> = intersections[&p2]
            .horizontal
            .iter()
            .map(edge_bbox_key)
            .collect();
        return !a.is_disjoint(&b);
    }

    false
}

fn cells_to_tables(cells: &[BBox]) -> Vec<Vec<BBox>> {
    let mut remaining = cells.to_vec();
    let mut current_corners: BTreeSet<PointKey> = BTreeSet::new();
    let mut current_cells: Vec<BBox> = Vec::new();
    let mut tables = Vec::new();

    while !remaining.is_empty() {
        let initial = current_cells.len();

        let snapshot = remaining.clone();
        for cell in snapshot {
            let corners = bbox_corners(cell);
            if current_cells.is_empty() {
                current_corners.extend(corners);
                current_cells.push(cell);
                remove_bbox(&mut remaining, cell);
            } else {
                let corner_count = corners.iter().filter(|corner| current_corners.contains(corner)).count();
                if corner_count > 0 {
                    current_corners.extend(corners);
                    current_cells.push(cell);
                    remove_bbox(&mut remaining, cell);
                }
            }
        }

        if current_cells.len() == initial {
            tables.push(current_cells.clone());
            current_corners.clear();
            current_cells.clear();
        }
    }

    if !current_cells.is_empty() {
        tables.push(current_cells);
    }

    tables.retain(|table| table.len() > 1);
    tables.sort_by(|a, b| {
        let aa = top_left_of_table(a);
        let bb = top_left_of_table(b);
        aa.0.total_cmp(&bb.0).then_with(|| aa.1.total_cmp(&bb.1))
    });
    tables
}

fn char_in_bbox(ch: &Char, bbox: BBox) -> bool {
    let v_mid = (ch.top + ch.bottom) / 2.0;
    let h_mid = (ch.x0 + ch.x1) / 2.0;
    h_mid >= bbox.x0 && h_mid < bbox.x1 && v_mid >= bbox.top && v_mid < bbox.bottom
}

fn merge_bboxes(boxes: &[BBox]) -> BBox {
    let x0 = boxes.iter().map(|bbox| bbox.x0).fold(f64::INFINITY, f64::min);
    let top = boxes.iter().map(|bbox| bbox.top).fold(f64::INFINITY, f64::min);
    let x1 = boxes.iter().map(|bbox| bbox.x1).fold(f64::NEG_INFINITY, f64::max);
    let bottom = boxes.iter().map(|bbox| bbox.bottom).fold(f64::NEG_INFINITY, f64::max);
    BBox::new(x0, top, x1, bottom)
}

fn merged_optional_bbox(boxes: &[Option<BBox>]) -> BBox {
    let selected: Vec<BBox> = boxes.iter().filter_map(|bbox| *bbox).collect();
    merge_bboxes(&selected)
}

fn bbox_coord(bbox: BBox, axis: usize) -> f64 {
    match axis {
        0 => bbox.x0,
        1 => bbox.top,
        _ => unreachable!(),
    }
}

fn bbox_corners(bbox: BBox) -> [PointKey; 4] {
    [
        (OrderedFloat(bbox.x0), OrderedFloat(bbox.top)),
        (OrderedFloat(bbox.x0), OrderedFloat(bbox.bottom)),
        (OrderedFloat(bbox.x1), OrderedFloat(bbox.top)),
        (OrderedFloat(bbox.x1), OrderedFloat(bbox.bottom)),
    ]
}

fn top_left_of_table(cells: &[BBox]) -> (f64, f64) {
    let bbox = merge_bboxes(cells);
    (bbox.top, bbox.x0)
}

fn edge_bbox_key(edge: &Edge) -> BBoxKey {
    (
        OrderedFloat(edge.x0),
        OrderedFloat(edge.top),
        OrderedFloat(edge.x1),
        OrderedFloat(edge.bottom),
    )
}

fn remove_bbox(items: &mut Vec<BBox>, target: BBox) {
    if let Some(idx) = items.iter().position(|bbox| *bbox == target) {
        items.remove(idx);
    }
}

fn line_to_edge(line: &Line) -> Edge {
    let orientation = if (line.top - line.bottom).abs() < 0.0001 {
        Orientation::Horizontal
    } else {
        Orientation::Vertical
    };
    Edge {
        x0: line.x0,
        top: line.top,
        x1: line.x1,
        bottom: line.bottom,
        width: line.width,
        height: line.height,
        orientation,
        object_type: "line".to_string(),
    }
}

fn curve_to_edges(curve: &crate::types::Curve) -> Vec<Edge> {
    let mut edges = Vec::new();
    for pair in curve.pts.windows(2) {
        let p0 = pair[0];
        let p1 = pair[1];
        let orientation = if (p0.x - p1.x).abs() < 0.0001 {
            Some(Orientation::Vertical)
        } else if (p0.y - p1.y).abs() < 0.0001 {
            Some(Orientation::Horizontal)
        } else {
            None
        };

        if let Some(orientation) = orientation {
            edges.push(Edge {
                x0: p0.x.min(p1.x),
                top: p0.y.min(p1.y),
                x1: p0.x.max(p1.x),
                bottom: p0.y.max(p1.y),
                width: (p1.x - p0.x).abs(),
                height: (p1.y - p0.y).abs(),
                orientation,
                object_type: "curve_edge".to_string(),
            });
        }
    }
    edges
}

impl Page {
    pub fn edges(&self) -> Vec<Edge> {
        let mut edges: Vec<Edge> = self.lines.iter().map(line_to_edge).collect();
        for rect in &self.rects {
            edges.extend(rect_to_edges(rect));
        }
        for curve in &self.curves {
            edges.extend(curve_to_edges(curve));
        }
        edges
    }
}