From da9b2ad1310e1db0ccb26a53181fa7f9b9033d04 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 2 May 2020 13:56:09 -0400
Subject: frontier/image: Implement image frontiers

---
 src/frontier.rs       | 71 +++++++++++++++++++++++++++++++++++++++++++++++-
 src/frontier/image.rs | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+), 1 deletion(-)
 create mode 100644 src/frontier/image.rs

diff --git a/src/frontier.rs b/src/frontier.rs
index 2c6f43a..1c5a173 100644
--- a/src/frontier.rs
+++ b/src/frontier.rs
@@ -1,6 +1,13 @@
 //! Frontiers on which to place pixels.
 
-use crate::color::Rgb8;
+pub mod image;
+
+use crate::color::{ColorSpace, Rgb8};
+use crate::metric::kd::Cartesian;
+use crate::metric::soft::SoftDelete;
+use crate::metric::Metric;
+
+use std::cell::Cell;
 
 /// A frontier of pixels.
 pub trait Frontier {
@@ -16,3 +23,65 @@ pub trait Frontier {
     /// Place the given color on the frontier, and return its position.
     fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)>;
 }
+
+/// A pixel on a frontier.
+#[derive(Debug)]
+struct Pixel<C> {
+    pos: (u32, u32),
+    color: C,
+    deleted: Cell<bool>,
+}
+
+impl<C: ColorSpace> Pixel<C> {
+    fn new(x: u32, y: u32, color: C) -> Self {
+        Self {
+            pos: (x, y),
+            color,
+            deleted: Cell::new(false),
+        }
+    }
+
+    fn delete(&self) {
+        self.deleted.set(true);
+    }
+}
+
+impl<C: Metric> Metric<Pixel<C>> for C {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &Pixel<C>) -> Self::Distance {
+        self.distance(&other.color)
+    }
+}
+
+impl<C: Metric<[f64]>> Metric<[f64]> for Pixel<C> {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &[f64]) -> Self::Distance {
+        self.color.distance(other)
+    }
+}
+
+impl<C: Metric> Metric for Pixel<C> {
+    type Distance = C::Distance;
+
+    fn distance(&self, other: &Pixel<C>) -> Self::Distance {
+        self.color.distance(&other.color)
+    }
+}
+
+impl<C: Cartesian> Cartesian for Pixel<C> {
+    fn dimensions(&self) -> usize {
+        self.color.dimensions()
+    }
+
+    fn coordinate(&self, i: usize) -> f64 {
+        self.color.coordinate(i)
+    }
+}
+
+impl<C> SoftDelete for Pixel<C> {
+    fn is_deleted(&self) -> bool {
+        self.deleted.get()
+    }
+}
diff --git a/src/frontier/image.rs b/src/frontier/image.rs
new file mode 100644
index 0000000..3655580
--- /dev/null
+++ b/src/frontier/image.rs
@@ -0,0 +1,74 @@
+//! Frontier that targets an image.
+
+use super::{Frontier, Pixel};
+
+use crate::color::{ColorSpace, Rgb8};
+use crate::metric::soft::SoftKdTree;
+use crate::metric::NearestNeighbors;
+
+use image::RgbImage;
+
+/// A [Frontier] that places colors on the closest pixel of a target image.
+#[derive(Debug)]
+pub struct ImageFrontier<C: ColorSpace> {
+    nodes: SoftKdTree<Pixel<C>>,
+    width: u32,
+    height: u32,
+    len: usize,
+    deleted: usize,
+}
+
+impl<C: ColorSpace> ImageFrontier<C> {
+    /// Create an ImageFrontier from an image.
+    pub fn new(img: &RgbImage) -> Self {
+        let width = img.width();
+        let height = img.height();
+        let len = (width as usize) * (height as usize);
+
+        Self {
+            nodes: img
+                .enumerate_pixels()
+                .map(|(x, y, p)| Pixel::new(x, y, C::from(*p)))
+                .collect(),
+            width,
+            height,
+            len,
+            deleted: 0,
+        }
+    }
+}
+
+impl<C: ColorSpace> Frontier for ImageFrontier<C> {
+    fn width(&self) -> u32 {
+        self.width
+    }
+
+    fn height(&self) -> u32 {
+        self.height
+    }
+
+    fn len(&self) -> usize {
+        self.len - self.deleted
+    }
+
+    fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)> {
+        let color = C::from(rgb8);
+
+        if let Some(node) = self.nodes.nearest(&color).map(|n| n.item) {
+            let pos = node.pos;
+
+            node.delete();
+            self.deleted += 1;
+
+            if 32 * self.deleted >= self.len {
+                self.nodes.rebuild();
+                self.len -= self.deleted;
+                self.deleted = 0;
+            }
+
+            Some(pos)
+        } else {
+            None
+        }
+    }
+}
-- 
cgit v1.2.3