oxihuman_core/
compact_set.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Compact ordered set of u32 values backed by a sorted Vec.
6
7/// A compact, sorted set of `u32` values.
8#[allow(dead_code)]
9#[derive(Debug, Clone, Default, PartialEq, Eq)]
10pub struct CompactSet {
11    values: Vec<u32>,
12}
13
14#[allow(dead_code)]
15impl CompactSet {
16    pub fn new() -> Self {
17        Self::default()
18    }
19
20    pub fn insert(&mut self, value: u32) -> bool {
21        match self.values.binary_search(&value) {
22            Ok(_) => false,
23            Err(pos) => {
24                self.values.insert(pos, value);
25                true
26            }
27        }
28    }
29
30    pub fn remove(&mut self, value: u32) -> bool {
31        match self.values.binary_search(&value) {
32            Ok(pos) => {
33                self.values.remove(pos);
34                true
35            }
36            Err(_) => false,
37        }
38    }
39
40    pub fn contains(&self, value: u32) -> bool {
41        self.values.binary_search(&value).is_ok()
42    }
43
44    pub fn len(&self) -> usize {
45        self.values.len()
46    }
47
48    pub fn is_empty(&self) -> bool {
49        self.values.is_empty()
50    }
51
52    pub fn iter(&self) -> std::slice::Iter<'_, u32> {
53        self.values.iter()
54    }
55
56    pub fn min(&self) -> Option<u32> {
57        self.values.first().copied()
58    }
59
60    pub fn max(&self) -> Option<u32> {
61        self.values.last().copied()
62    }
63
64    pub fn clear(&mut self) {
65        self.values.clear();
66    }
67
68    pub fn union(&self, other: &CompactSet) -> CompactSet {
69        let mut result = self.clone();
70        for &v in &other.values {
71            result.insert(v);
72        }
73        result
74    }
75
76    pub fn intersection(&self, other: &CompactSet) -> CompactSet {
77        let mut result = CompactSet::new();
78        for &v in &self.values {
79            if other.contains(v) {
80                result.insert(v);
81            }
82        }
83        result
84    }
85
86    pub fn difference(&self, other: &CompactSet) -> CompactSet {
87        let mut result = CompactSet::new();
88        for &v in &self.values {
89            if !other.contains(v) {
90                result.insert(v);
91            }
92        }
93        result
94    }
95
96    pub fn to_vec(&self) -> Vec<u32> {
97        self.values.clone()
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn new_is_empty() {
107        assert!(CompactSet::new().is_empty());
108    }
109
110    #[test]
111    fn insert_and_contains() {
112        let mut s = CompactSet::new();
113        assert!(s.insert(5));
114        assert!(s.contains(5));
115        assert!(!s.contains(6));
116    }
117
118    #[test]
119    fn duplicate_insert_returns_false() {
120        let mut s = CompactSet::new();
121        assert!(s.insert(3));
122        assert!(!s.insert(3));
123        assert_eq!(s.len(), 1);
124    }
125
126    #[test]
127    fn remove_works() {
128        let mut s = CompactSet::new();
129        s.insert(7);
130        assert!(s.remove(7));
131        assert!(s.is_empty());
132        assert!(!s.remove(7));
133    }
134
135    #[test]
136    fn sorted_ordering() {
137        let mut s = CompactSet::new();
138        s.insert(10);
139        s.insert(2);
140        s.insert(6);
141        let v = s.to_vec();
142        assert_eq!(v, vec![2, 6, 10]);
143    }
144
145    #[test]
146    fn min_max() {
147        let mut s = CompactSet::new();
148        s.insert(4);
149        s.insert(1);
150        s.insert(9);
151        assert_eq!(s.min(), Some(1));
152        assert_eq!(s.max(), Some(9));
153    }
154
155    #[test]
156    fn union_op() {
157        let mut a = CompactSet::new();
158        a.insert(1);
159        a.insert(2);
160        let mut b = CompactSet::new();
161        b.insert(2);
162        b.insert(3);
163        let u = a.union(&b);
164        assert_eq!(u.to_vec(), vec![1, 2, 3]);
165    }
166
167    #[test]
168    fn intersection_op() {
169        let mut a = CompactSet::new();
170        a.insert(1);
171        a.insert(2);
172        a.insert(3);
173        let mut b = CompactSet::new();
174        b.insert(2);
175        b.insert(4);
176        let i = a.intersection(&b);
177        assert_eq!(i.to_vec(), vec![2]);
178    }
179
180    #[test]
181    fn difference_op() {
182        let mut a = CompactSet::new();
183        a.insert(1);
184        a.insert(2);
185        a.insert(3);
186        let mut b = CompactSet::new();
187        b.insert(2);
188        let d = a.difference(&b);
189        assert_eq!(d.to_vec(), vec![1, 3]);
190    }
191
192    #[test]
193    fn clear_empties() {
194        let mut s = CompactSet::new();
195        s.insert(1);
196        s.insert(2);
197        s.clear();
198        assert!(s.is_empty());
199    }
200}
oxihuman_core/compact_set.rs

oxihuman_core/
compact_set.rs
