1 use super::{VQElement, VQElementSum};
3 struct VQBox<'a, T: VQElement> {
9 impl<'a, T: VQElement> VQBox<'a, T> {
10 fn new(points: &'a mut [T]) -> Self {
11 let mut max = T::min_cw();
12 let mut min = T::max_cw();
13 for point in points.iter() {
14 max = max.max(*point);
15 min = min.min(*point);
17 Self { points, max, min }
19 fn can_split(&self) -> bool {
22 fn calc_min_and_max(points: &[T]) -> (T, T) {
23 let mut max = T::min_cw();
24 let mut min = T::max_cw();
25 for point in points.iter() {
26 max = max.max(*point);
27 min = min.min(*point);
31 fn get_pivot(arr: &[T]) -> usize {
35 let mut lastval = arr[0];
38 for el in arr.iter().skip(1) {
39 if *el != lastval && (pivot == 0 || idx <= arr.len() / 2) {
47 fn split(self) -> (VQBox<'a, T>, VQBox<'a, T>) {
48 let sort_c = T::max_dist_component(&self.min, &self.max);
49 T::sort_by_component(self.points, sort_c);
50 let pivot = Self::get_pivot(self.points);
51 let (part0, part1) = self.points.split_at_mut(pivot);
52 let (min0, max0) = Self::calc_min_and_max(part0);
53 let (min1, max1) = Self::calc_min_and_max(part1);
54 let box0 = VQBox { points: part0, max: max0, min: min0 };
55 let box1 = VQBox { points: part1, max: max1, min: min1 };
61 pub fn quantise_median_cut<T: VQElement, TS: VQElementSum<T>>(src: &[T], dst: &mut [T]) -> usize {
62 let mut points = Vec::with_capacity(src.len());
63 points.extend(src.into_iter());
64 for comp in 0..T::num_components() {
65 T::sort_by_component(points.as_mut_slice(), comp);
67 let box0 = VQBox::new(points.as_mut_slice());
68 let mut boxes: Vec<VQBox<T>> = Vec::with_capacity(dst.len());
70 let mut changed = true;
71 while changed && boxes.len() < dst.len() {
72 let end = boxes.len();
74 let mut split_largest = false;
76 let curbox = boxes.remove(0);
77 if curbox.can_split() {
78 let (box0, box1) = curbox.split();
87 if boxes.len() == dst.len() {
94 for (i, cbox) in boxes.iter().enumerate() {
95 if cbox.can_split() && cbox.points.len() > lcount {
96 lcount = cbox.points.len();
101 let curbox = boxes.remove(maxidx);
102 let (box0, box1) = curbox.split();
109 for (dst, curbox) in dst.iter_mut().zip(boxes.iter()) {
110 let mut sum = TS::zero();
111 sum.add(curbox.min, 1);
112 sum.add(curbox.max, 1);
113 *dst = sum.get_centroid();