pixelset/set/ops/
set_ops.rs

1use crate::{Pixel, PixelSet};
2
3impl PixelSet {
4    /// Inserts a single new pixel into the set while maintaining sorted
5    /// order and uniqueness.
6    /// 
7    /// Uses binary search to find the insertion point.
8    /// Worst-case complexity: `O(n)` due to element shifting.
9    pub fn add(&mut self, pixel: Pixel) {
10        match self.pixels.binary_search(&pixel) {
11            Ok(_) => {}
12            Err(idx) => {
13                self.pixels.insert(idx, pixel);
14            }
15        }
16    }
17
18    /// Removes a pixel from the set, maintaining sort order.
19    /// 
20    /// Uses binary search to locate the pixel.
21    /// Worst-case complexity: `O(n)` due to element shifting.
22    pub fn discard(&mut self, pixel: Pixel) {
23        if let Ok(idx) = self.pixels.binary_search(&pixel) {
24            self.pixels.remove(idx);
25        }
26    }
27
28    /// Returns a new `PixelSet` representing the union of this set and another, with all 
29    /// pixels from both sets are included.
30    /// 
31    /// Complexity: `O(n + m)`.
32    pub fn extend(&self, other: &Self) -> Self {
33        if self.is_empty() {
34            return other.clone();
35        }
36
37        let mut pixels = Vec::with_capacity(self.pixels.len() + other.pixels.len());
38
39        let mut self_ind = 0;
40        let mut other_ind = 0;
41
42        while self_ind < self.pixels.len() && other_ind < other.pixels.len() {
43            if self.pixels[self_ind] < other.pixels[other_ind] {
44                pixels.push(self.pixels[self_ind]);
45                self_ind += 1;
46            } else if self.pixels[self_ind] > other.pixels[other_ind] {
47                pixels.push(other.pixels[other_ind]);
48                other_ind += 1;
49            } else {
50                pixels.push(self.pixels[self_ind]);
51                self_ind += 1;
52                other_ind += 1;
53            }
54        }
55
56        pixels.extend_from_slice(&self.pixels[self_ind..]);
57        pixels.extend_from_slice(&other.pixels[other_ind..]);
58
59        Self { pixels }
60    }
61
62    /// Returns a new `PixelSet` with pixels in this set that are not in `other`,
63    /// performing a set difference.
64    ///
65    /// Complexity: `O(n + m)`.
66    pub fn without(&self, other: &Self) -> Self {
67        let mut result = Vec::with_capacity(self.pixels.len());
68
69        let mut self_index = 0;
70        let mut other_index = 0;
71
72        while self_index < self.pixels.len() && other_index < other.pixels.len() {
73            let self_pixel = self.pixels[self_index];
74            let other_pixel = other.pixels[other_index];
75
76            if self_pixel < other_pixel {
77                result.push(self_pixel);
78                self_index += 1;
79            } else if self_pixel > other_pixel {
80                other_index += 1;
81            } else {
82                self_index += 1;
83                other_index += 1;
84            }
85        }
86
87        result.extend_from_slice(&self.pixels[self_index..]);
88
89        PixelSet::new_unchecked(result)
90    }
91
92    /// Removes all pixels that appear in `other` from this set, modifying the
93    /// set in-place.
94    /// 
95    /// Complexity: `O(n + m)`.
96    pub fn remove(&mut self, other: &Self) {
97        *self = self.without(other);
98    }
99
100
101    /// Returns a new `PixelSet` containing only the pixels that appear in
102    /// both sets, performing a set intersection.
103    /// 
104    /// Complexity: `O(n + m)`
105    pub fn and(&self, other: &Self) -> Self {
106        let mut pixels = Vec::with_capacity(
107            self.pixels.len().min(other.pixels.len())
108        );
109
110        let mut self_ind = 0;
111        let mut other_ind = 0;
112
113        while self_ind < self.len() && other_ind < other.len() {
114            let self_pixel = self.pixels[self_ind];
115            let other_pixel = other.pixels[other_ind];
116
117            if self_pixel < other_pixel {
118                self_ind += 1;
119            } else if self_pixel > other_pixel {
120                other_ind += 1;
121            } else {
122                // Pixels match → intersection
123                pixels.push(self_pixel);
124                self_ind += 1;
125                other_ind += 1;
126            }
127        }
128
129        PixelSet::new_unchecked(pixels)
130    }
131
132    /// Returns `true` if this set shares any pixel with another set.
133    ///
134    /// Complexity: `O(n log m)`.
135    pub fn intersects(&self, other: &Self) -> bool {
136        self.into_iter().any(|&pixel| other.has(pixel))
137    }
138}
pixelset/set/ops/set_ops.rs

pixelset/set/ops/
set_ops.rs
