///|
/// Represents a connected blob component in a segmented binary image.
pub(all) struct ConnectedComponent {
  label : Int
  area : Int
  bounding_box : Rect2D
  centroid : Point2D
} derive(Debug, Eq)

///|
/// Creates a new connected component record.
pub fn ConnectedComponent::new(
  label : Int,
  area : Int,
  bounding_box : Rect2D,
  centroid : Point2D,
) -> ConnectedComponent {
  { label, area, bounding_box, centroid }
}

///|
/// Connected Component Labeling (CCL) using Two-Pass Union-Find algorithm (8-connectivity or 4-connectivity).
/// Returns (labeled_image, components_array).
pub fn connected_components(
  binary_img : Image,
  connectivity_8? : Bool = true,
) -> (Array[Int], Array[ConnectedComponent]) {
  let w = binary_img.width
  let h = binary_img.height
  let size = w * h
  let labels = Array::make(size, 0)
  if size == 0 {
    return (labels, [])
  }

  // Disjoint set union-find parent table
  let parent : Array[Int] = [0] // 0 is background
  let mut next_label = 1

  let find_root = fn(x : Int) -> Int {
    let mut root = x
    while parent[root] != root {
      root = parent[root]
    }
    // Path compression
    let mut curr = x
    while curr != root {
      let p = parent[curr]
      parent[curr] = root
      curr = p
    }
    root
  }

  let union_labels = fn(x : Int, y : Int) -> Unit {
    let rx = find_root(x)
    let ry = find_root(y)
    if rx != ry {
      if rx < ry {
        parent[ry] = rx
      } else {
        parent[rx] = ry
      }
    }
  }

  // First pass: label assignment and equivalence recording
  for y in 0.. 0 {
        let neighbor_labels : Array[Int] = []

        // West
        if x > 0 {
          let l = labels[y * w + (x - 1)]
          if l > 0 {
            neighbor_labels.push(l)
          }
        }
        // North
        if y > 0 {
          let l = labels[(y - 1) * w + x]
          if l > 0 {
            neighbor_labels.push(l)
          }
        }

        if connectivity_8 {
          // North-West
          if x > 0 && y > 0 {
            let l = labels[(y - 1) * w + (x - 1)]
            if l > 0 {
              neighbor_labels.push(l)
            }
          }
          // North-East
          if x < w - 1 && y > 0 {
            let l = labels[(y - 1) * w + (x + 1)]
            if l > 0 {
              neighbor_labels.push(l)
            }
          }
        }

        if neighbor_labels.length() == 0 {
          // New component
          let l = next_label
          labels[y * w + x] = l
          parent.push(l)
          next_label += 1
        } else {
          // Find minimum neighbor label and union others
          let mut min_l = neighbor_labels[0]
          for l in neighbor_labels {
            if l < min_l {
              min_l = l
            }
          }
          labels[y * w + x] = min_l
          for l in neighbor_labels {
            union_labels(min_l, l)
          }
        }
      }
    }
  }

  // Flatten disjoint sets and create contiguous component index map
  let label_map = Array::make(next_label, 0)
  let mut actual_count = 0
  for i in 1.. 0 {
        let final_l = label_map[l]
        labels[y * w + x] = final_l

        areas[final_l] += 1
        sum_xs[final_l] += x.to_double()
        sum_ys[final_l] += y.to_double()

        if x < min_xs[final_l] {
          min_xs[final_l] = x
        }
        if x > max_xs[final_l] {
          max_xs[final_l] = x
        }
        if y < min_ys[final_l] {
          min_ys[final_l] = y
        }
        if y > max_ys[final_l] {
          max_ys[final_l] = y
        }
      }
    }
  }

  // Build ConnectedComponent records
  let components : Array[ConnectedComponent] = []
  for i in 1..<=actual_count {
    let a = areas[i]
    if a > 0 {
      let bbox = Rect2D::new(
        min_xs[i].to_double(),
        min_ys[i].to_double(),
        (max_xs[i] - min_xs[i] + 1).to_double(),
        (max_ys[i] - min_ys[i] + 1).to_double(),
      )
      let centroid = Point2D::new(
        sum_xs[i] / a.to_double(),
        sum_ys[i] / a.to_double(),
      )
      components.push(ConnectedComponent::new(i, a, bbox, centroid))
    }
  }

  (labels, components)
}