1use std::fmt::Debug;
2
3#[derive(Clone, Hash, Eq)]
4#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
5pub struct VecMap<K, V>(pub Vec<(K, V)>);
6
7impl<K, V, K2, V2> PartialEq<VecMap<K2, V2>> for VecMap<K, V>
8where
9 K: PartialEq<K2>,
10 V: PartialEq<V2>,
11{
12 fn eq(&self, other: &VecMap<K2, V2>) -> bool {
13 self.0.len() == other.0.len()
14 && self
15 .iter()
16 .zip(other.iter())
17 .all(|((k1, v1), (k2, v2))| k1 == k2 && v1 == v2)
18 }
19}
20
21impl<K, V> Default for VecMap<K, V> {
22 fn default() -> Self {
23 Self(Vec::new())
24 }
25}
26impl<K, V> FromIterator<(K, V)> for VecMap<K, V> {
27 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
28 Self(iter.into_iter().collect())
29 }
30}
31impl<K: Debug, V: Debug> Debug for VecMap<K, V> {
32 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33 f.debug_map()
34 .entries(self.0.iter().map(|(k, v)| (k, v)))
35 .finish()
36 }
37}
38impl<K, V> VecMap<K, V> {
39 #[must_use]
40 pub const fn new() -> Self {
41 Self(Vec::new())
42 }
43 pub fn get<E: ?Sized>(&self, key: &E) -> Option<&V>
44 where
45 for<'a> &'a E: PartialEq<&'a K>,
46 {
47 self.0.iter().find(|(k, _)| key == k).map(|(_, v)| v)
48 }
49 pub fn get_mut<E: ?Sized>(&mut self, key: &E) -> Option<&mut V>
50 where
51 for<'a> &'a E: PartialEq<&'a K>,
52 {
53 self.0.iter_mut().find(|(k, _)| key == k).map(|(_, v)| v)
54 }
55 pub fn get_mut_index(&mut self, i: usize) -> Option<&mut (K, V)> {
56 self.0.get_mut(i)
57 }
58 pub fn get_or_insert_mut(&mut self, key: K, value: impl FnOnce() -> V) -> &mut V
59 where
60 K: PartialEq,
61 {
62 let ret = if let Some((i, _)) = self.0.iter().enumerate().find(|(_, (k, _))| k == &key) {
63 i
64 } else {
65 self.0.push((key, value()));
66 self.0.len() - 1
67 };
68 &mut self.0[ret].1
69 }
70 pub fn insert(&mut self, key: K, value: V)
71 where
72 K: PartialEq,
73 {
74 match self.0.iter_mut().find(|(k, _)| k == &key) {
75 Some((_, v)) => *v = value,
76 None => self.0.push((key, value)),
77 }
78 }
79 pub fn remove<E: ?Sized>(&mut self, key: &E) -> Option<V>
80 where
81 for<'a> &'a E: PartialEq<&'a K>,
82 {
83 let index = self.0.iter().position(|(k, _)| key == k)?;
84 Some(self.0.remove(index).1)
85 }
86 pub fn remove_index(&mut self, i: usize) -> (K, V) {
87 self.0.remove(i)
88 }
89
90 #[inline]
91 #[must_use]
92 pub const fn is_empty(&self) -> bool {
93 self.0.is_empty()
94 }
95 pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
96 self.0.iter().map(|(k, v)| (k, v))
97 }
98 pub fn contains_key<E: ?Sized>(&self, key: &E) -> bool
99 where
100 for<'a> &'a E: PartialEq<&'a K>,
101 {
102 self.0.iter().any(|(k, _)| key == k)
103 }
104}
105impl<K, V> IntoIterator for VecMap<K, V> {
106 type Item = (K, V);
107 type IntoIter = std::vec::IntoIter<Self::Item>;
108 fn into_iter(self) -> Self::IntoIter {
109 self.0.into_iter()
110 }
111}
112
113impl<K, V> From<Vec<(K, V)>> for VecMap<K, V> {
114 fn from(v: Vec<(K, V)>) -> Self {
115 Self(v)
116 }
117}
118
119#[derive(Clone, Hash, Eq)]
120#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
121pub struct VecSet<V>(pub Vec<V>);
122
123impl<V, V2> PartialEq<VecSet<V2>> for VecSet<V>
124where
125 V: PartialEq<V2>,
126{
127 fn eq(&self, other: &VecSet<V2>) -> bool {
128 self.0.len() == other.0.len() && self.iter().zip(other.iter()).all(|(v1, v2)| v1 == v2)
129 }
130}
131
132impl<V> Default for VecSet<V> {
133 #[inline]
134 fn default() -> Self {
135 Self(Vec::new())
136 }
137}
138impl<V: PartialEq<V>> FromIterator<V> for VecSet<V> {
139 fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
140 let mut v = Vec::new();
141 for i in iter {
142 if !v.contains(&i) {
143 v.push(i);
144 }
145 }
146 Self(v)
147 }
148}
149impl<V: Debug> Debug for VecSet<V> {
150 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
151 f.debug_list().entries(self.0.iter()).finish()
152 }
153}
154impl<V> IntoIterator for VecSet<V> {
155 type Item = V;
156 type IntoIter = std::vec::IntoIter<Self::Item>;
157 #[inline]
158 fn into_iter(self) -> Self::IntoIter {
159 self.0.into_iter()
160 }
161}
162
163impl<V: PartialEq<V>> From<Vec<V>> for VecSet<V> {
164 #[inline]
165 fn from(v: Vec<V>) -> Self {
166 v.into_iter().collect()
167 }
168}
169
170impl<V> VecSet<V> {
171 #[inline]
172 pub fn iter(&self) -> impl Iterator<Item = &V> {
173 self.0.iter()
174 }
175 pub fn insert(&mut self, value: V)
176 where
177 V: PartialEq,
178 {
179 if !self.0.contains(&value) {
180 self.0.push(value);
181 }
182 }
183 #[inline]
184 #[must_use]
185 pub const fn is_empty(&self) -> bool {
186 self.0.is_empty()
187 }
188 #[inline]
189 #[must_use]
190 pub const fn new() -> Self {
191 Self(Vec::new())
192 }
193}
194
195impl<V: Clone> VecSet<V> {
196 pub fn insert_clone(&mut self, value: &V)
197 where
198 V: PartialEq,
199 {
200 if !self.0.contains(value) {
201 self.0.push(value.clone());
202 }
203 }
204}
205
206#[derive(Clone, Hash, Eq)]
207#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
208pub struct OrdSet<V: Ord>(pub Vec<V>);
209
210impl<V, V2: Ord> PartialEq<OrdSet<V2>> for OrdSet<V>
211where
212 V: Ord + PartialEq<V2>,
213{
214 fn eq(&self, other: &OrdSet<V2>) -> bool {
215 self.0.len() == other.0.len() && self.iter().zip(other.iter()).all(|(v1, v2)| v1 == v2)
216 }
217}
218
219impl<V: Ord> Default for OrdSet<V> {
220 #[inline]
221 fn default() -> Self {
222 Self(Vec::new())
223 }
224}
225impl<V: PartialEq<V> + Ord> FromIterator<V> for OrdSet<V> {
226 fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
227 let mut v = Vec::new();
228 for elem in iter {
229 if let Err(i) = v.binary_search(&elem) {
230 v.insert(i, elem);
231 }
232 }
233 Self(v)
234 }
235}
236impl<V: Debug + Ord> Debug for OrdSet<V> {
237 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
238 f.debug_list().entries(self.0.iter()).finish()
239 }
240}
241impl<V: Ord> IntoIterator for OrdSet<V> {
242 type Item = V;
243 type IntoIter = std::vec::IntoIter<Self::Item>;
244 #[inline]
245 fn into_iter(self) -> Self::IntoIter {
246 self.0.into_iter()
247 }
248}
249
250impl<V: PartialEq<V> + Ord> From<Vec<V>> for OrdSet<V> {
251 #[inline]
252 fn from(v: Vec<V>) -> Self {
253 v.into_iter().collect()
254 }
255}
256
257impl<V: Ord> OrdSet<V> {
258 #[inline]
259 pub fn iter(&self) -> impl Iterator<Item = &V> {
260 self.0.iter()
261 }
262 pub fn insert(&mut self, value: V)
263 where
264 V: PartialEq,
265 {
266 if let Err(i) = self.0.binary_search(&value) {
267 self.0.insert(i, value);
268 }
269 }
270 #[inline]
271 #[must_use]
272 pub const fn is_empty(&self) -> bool {
273 self.0.is_empty()
274 }
275 #[inline]
276 #[must_use]
277 pub const fn new() -> Self {
278 Self(Vec::new())
279 }
280
281 #[inline]
282 #[must_use]
283 pub fn contains(&self, v: &V) -> bool {
284 self.0.binary_search(v).is_ok()
285 }
286}
287
288impl<V: Ord + Clone> OrdSet<V> {
289 pub fn insert_clone(&mut self, value: &V) {
290 if let Err(i) = self.0.binary_search(value) {
291 self.0.insert(i, value.clone());
292 }
293 }
294}