fast-canny 0.1.0

//! 零分配 BFS Hysteresis（切片接口版本）

use bumpalo::collections::Vec as BumpVec;
use bumpalo::Bump;
use std::time::Instant;

/// 基于零分配 BFS 的滞后阈值边缘连通域追踪。
///
/// 完全使用切片接口，无裸指针操作。
pub fn track_edges(edge_map: &mut [u8], width: usize, height: usize, arena: &Bump) {
    let t_start = Instant::now();
    let total = width * height;

    debug_assert_eq!(edge_map.len(), total, "edge_map size mismatch");

    log::info!(
        "[track_edges] START {}x{} total={}",
        width, height, total
    );

    // ── 主动清零四周边界，消除 BFS 越界风险 ──────────────────────
    // 开销 O(W+H)，相对于 BFS 的 O(W×H) 可忽略
    {
        let last = (height - 1) * width;
        edge_map[..width].fill(0);
        edge_map[last..last + width].fill(0);
        for y in 0..height {
            edge_map[y * width] = 0;
            edge_map[y * width + width - 1] = 0;
        }
    }

    #[cfg(debug_assertions)]
    {
        let bad = edge_map[..width].iter().any(|&v| v != 0)
            || edge_map[(height-1)*width..].iter().any(|&v| v != 0)
            || (0..height).any(|y| edge_map[y*width] != 0 || edge_map[y*width+width-1] != 0);
        if bad {
            log::error!("[track_edges] BUG: boundary clear failed");
        }
    }

    let w = width as isize;
    let neighbors: [isize; 8] = [
        -w-1, -w, -w+1,
        -1,         1,
         w-1,  w,  w+1,
    ];

    // ── 步骤 1：分配 BFS 栈（Bump Arena，零堆分配）────────────────
    let stack_cap = total / 4;
    let mut stack = BumpVec::with_capacity_in(stack_cap, arena);

    // ── 步骤 2：收集强边缘种子 ────────────────────────────────────
    let t_scan = Instant::now();
    for (i, &v) in edge_map.iter().enumerate() {
        if v == 255 {
            stack.push(i as isize);
        }
    }
    let seed_count = stack.len();
    log::debug!(
        "[track_edges] seeds={} ({:.1}%), scan={:?}",
        seed_count,
        seed_count as f64 / total as f64 * 100.0,
        t_scan.elapsed()
    );

    if seed_count == 0 {
        log::warn!("[track_edges] NO strong edges — check thresholds");
    }

    // ── 步骤 3：BFS 扩散 ──────────────────────────────────────────
    // 使用切片索引替代裸指针偏移，安全性由边界清零保证：
    // 边界像素值为 0，不满足 == 127，扩散自然终止。
    let t_bfs = Instant::now();
    let mut promoted = 0usize;

    while let Some(idx) = stack.pop() {
        for &offset in &neighbors {
            let n_idx = (idx + offset) as usize;
            // SAFETY 说明（使用 get_unchecked 的理由）：
            // - idx 来自种子扫描，范围 [0, total)
            // - 边界行列已清零，BFS 不会将边界像素入栈
            // - 因此 n_idx 始终在 [0, total) 内
            // 此处改用安全索引，性能影响可忽略（编译器会消除冗余检查）
            if let Some(v) = edge_map.get_mut(n_idx) {
                if *v == 127 {
                    *v = 255;
                    stack.push(n_idx as isize);
                    promoted += 1;
                }
            }
        }
    }

    log::debug!(
        "[track_edges] BFS promoted={}, elapsed={:?}",
        promoted, t_bfs.elapsed()
    );

    // ── 步骤 4：清除孤立弱边缘 ────────────────────────────────────
    let t_cleanup = Instant::now();
    let mut orphans = 0usize;
    for v in edge_map.iter_mut() {
        if *v == 127 {
            *v = 0;
            orphans += 1;
        }
    }
    log::debug!(
        "[track_edges] orphans={} ({:.1}%), cleanup={:?}",
        orphans,
        orphans as f64 / total as f64 * 100.0,
        t_cleanup.elapsed()
    );

    #[cfg(debug_assertions)]
    {
        let final_strong = edge_map.iter().filter(|&&v| v == 255).count();
        let ratio = final_strong as f64 / total as f64 * 100.0;
        if ratio > 20.0 {
            log::warn!("[track_edges] HIGH density {:.1}% — consider raising high_thresh", ratio);
        }
    }

    log::info!(
        "[track_edges] END seeds={} promoted={} orphans={} {:.3}ms",
        seed_count, promoted, orphans,
        t_start.elapsed().as_secs_f64() * 1000.0
    );
}