1#[cfg(feature = "serialize")]
2#[macro_use]
3extern crate serde;
4
5use std::cmp::Ordering;
6
7#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
8#[derive(Debug, Clone, Copy)]
9pub struct BestMapNonEmpty<K, V> {
10 key: K,
11 value: V,
12}
13
14impl<K: PartialOrd, V> BestMapNonEmpty<K, V> {
15 pub fn insert_gt(&mut self, key: K, value: V) {
16 if key > self.key {
17 self.insert(key, value);
18 }
19 }
20
21 pub fn insert_ge(&mut self, key: K, value: V) {
22 if key >= self.key {
23 self.insert(key, value);
24 }
25 }
26
27 pub fn insert_lt(&mut self, key: K, value: V) {
28 if key < self.key {
29 self.insert(key, value);
30 }
31 }
32
33 pub fn insert_le(&mut self, key: K, value: V) {
34 if key <= self.key {
35 self.insert(key, value);
36 }
37 }
38}
39
40impl<K, V> BestMapNonEmpty<K, V> {
41 pub fn new(key: K, value: V) -> Self {
42 Self {
43 key: key,
44 value: value,
45 }
46 }
47
48 fn insert(&mut self, key: K, value: V) {
49 self.key = key;
50 self.value = value;
51 }
52
53 pub fn get(&self) -> (&K, &V) {
54 (&self.key, &self.value)
55 }
56 pub fn key(&self) -> &K {
57 &self.key
58 }
59 pub fn value(&self) -> &V {
60 &self.value
61 }
62
63 pub fn into_key_and_value(self) -> (K, V) {
64 (self.key, self.value)
65 }
66 pub fn into_key(self) -> K {
67 self.key
68 }
69 pub fn into_value(self) -> V {
70 self.value
71 }
72}
73
74#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
75#[derive(Debug, Clone, Copy)]
76pub struct BestMap<K, V> {
77 non_empty: Option<BestMapNonEmpty<K, V>>,
78}
79impl<K, V> Default for BestMap<K, V> {
80 fn default() -> Self {
81 Self::new()
82 }
83}
84
85impl<K: PartialOrd, V> BestMap<K, V> {
86 pub fn insert_gt(&mut self, key: K, value: V) {
87 if let Some(non_empty) = self.non_empty.as_mut() {
88 non_empty.insert_gt(key, value);
89 return;
90 }
91 self.non_empty = Some(BestMapNonEmpty::new(key, value));
92 }
93
94 pub fn insert_ge(&mut self, key: K, value: V) {
95 if let Some(non_empty) = self.non_empty.as_mut() {
96 non_empty.insert_ge(key, value);
97 return;
98 }
99 self.non_empty = Some(BestMapNonEmpty::new(key, value));
100 }
101
102 pub fn insert_lt(&mut self, key: K, value: V) {
103 if let Some(non_empty) = self.non_empty.as_mut() {
104 non_empty.insert_lt(key, value);
105 return;
106 }
107 self.non_empty = Some(BestMapNonEmpty::new(key, value));
108 }
109
110 pub fn insert_le(&mut self, key: K, value: V) {
111 if let Some(non_empty) = self.non_empty.as_mut() {
112 non_empty.insert_le(key, value);
113 return;
114 }
115 self.non_empty = Some(BestMapNonEmpty::new(key, value));
116 }
117}
118
119impl<K, V> BestMap<K, V> {
120 pub fn new() -> Self {
121 Self { non_empty: None }
122 }
123
124 pub fn get(&self) -> Option<(&K, &V)> {
125 self.non_empty.as_ref().map(BestMapNonEmpty::get)
126 }
127
128 pub fn key(&self) -> Option<&K> {
129 self.non_empty.as_ref().map(BestMapNonEmpty::key)
130 }
131
132 pub fn value(&self) -> Option<&V> {
133 self.non_empty.as_ref().map(BestMapNonEmpty::value)
134 }
135
136 pub fn into_key_and_value(self) -> Option<(K, V)> {
137 self.non_empty.map(BestMapNonEmpty::into_key_and_value)
138 }
139
140 pub fn into_key(self) -> Option<K> {
141 self.non_empty.map(BestMapNonEmpty::into_key)
142 }
143
144 pub fn into_value(self) -> Option<V> {
145 self.non_empty.map(BestMapNonEmpty::into_value)
146 }
147
148 pub fn is_empty(&self) -> bool {
149 self.non_empty.is_none()
150 }
151}
152
153#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
154#[derive(Debug, Clone, Copy)]
155pub struct BestSetNonEmpty<T>(BestMapNonEmpty<T, ()>);
156
157impl<T: PartialOrd> BestSetNonEmpty<T> {
158 pub fn insert_gt(&mut self, value: T) {
159 self.0.insert_gt(value, ());
160 }
161 pub fn insert_ge(&mut self, value: T) {
162 self.0.insert_ge(value, ());
163 }
164 pub fn insert_lt(&mut self, value: T) {
165 self.0.insert_lt(value, ());
166 }
167 pub fn insert_le(&mut self, value: T) {
168 self.0.insert_le(value, ());
169 }
170}
171
172impl<T> BestSetNonEmpty<T> {
173 pub fn new(value: T) -> Self {
174 BestSetNonEmpty(BestMapNonEmpty::new(value, ()))
175 }
176
177 pub fn get(&self) -> &T {
178 self.0.key()
179 }
180 pub fn into_value(self) -> T {
181 self.0.into_key()
182 }
183}
184
185#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
186#[derive(Debug, Clone, Copy)]
187pub struct BestSet<T>(BestMap<T, ()>);
188impl<T> Default for BestSet<T> {
189 fn default() -> Self {
190 Self::new()
191 }
192}
193
194impl<T: PartialOrd> BestSet<T> {
195 pub fn insert_gt(&mut self, value: T) {
196 self.0.insert_gt(value, ());
197 }
198 pub fn insert_ge(&mut self, value: T) {
199 self.0.insert_ge(value, ());
200 }
201 pub fn insert_lt(&mut self, value: T) {
202 self.0.insert_lt(value, ());
203 }
204 pub fn insert_le(&mut self, value: T) {
205 self.0.insert_le(value, ());
206 }
207}
208
209impl<T> BestSet<T> {
210 pub fn new() -> Self {
211 BestSet(BestMap::new())
212 }
213 pub fn get(&self) -> Option<&T> {
214 self.0.key()
215 }
216 pub fn into_value(self) -> Option<T> {
217 self.0.into_key()
218 }
219 pub fn is_empty(&self) -> bool {
220 self.0.is_empty()
221 }
222}
223
224#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
225#[derive(Debug, Clone)]
226pub struct BestMultiSet<T>(Vec<T>);
227impl<T> Default for BestMultiSet<T> {
228 fn default() -> Self {
229 Self::new()
230 }
231}
232
233pub type BestMultiSetIter<'a, T> = ::std::slice::Iter<'a, T>;
234pub type BestMultiSetDrain<'a, T> = ::std::vec::Drain<'a, T>;
235
236impl<T> BestMultiSet<T> {
237 pub fn new() -> Self {
238 BestMultiSet(Vec::new())
239 }
240 pub fn iter(&self) -> BestMultiSetIter<T> {
241 self.0.iter()
242 }
243 pub fn drain(&mut self) -> BestMultiSetDrain<T> {
244 self.0.drain(..)
245 }
246 pub fn first(&self) -> Option<&T> {
247 self.0.first()
248 }
249 pub fn clear(&mut self) {
250 self.0.clear();
251 }
252 pub fn is_empty(&self) -> bool {
253 self.0.is_empty()
254 }
255 fn replace_with_single(&mut self, value: T) {
256 self.0.clear();
257 self.0.push(value);
258 }
259 pub fn insert_lt_by<F>(&mut self, value: T, mut compare: F)
260 where
261 F: FnMut(&T, &T) -> Ordering,
262 {
263 match self.0.first().map(|v| compare(&value, v)) {
264 None | Some(Ordering::Equal) => self.0.push(value),
265 Some(Ordering::Less) => self.replace_with_single(value),
266 Some(Ordering::Greater) => (),
267 }
268 }
269 pub fn insert_gt_by<F>(&mut self, value: T, mut compare: F)
270 where
271 F: FnMut(&T, &T) -> Ordering,
272 {
273 match self.0.first().map(|v| compare(&value, v)) {
274 None | Some(Ordering::Equal) => self.0.push(value),
275 Some(Ordering::Greater) => self.replace_with_single(value),
276 Some(Ordering::Less) => (),
277 }
278 }
279}
280
281impl<T: PartialOrd> BestMultiSet<T> {
282 pub fn insert_lt(&mut self, value: T) {
283 match self.0.first().map(|v| value.partial_cmp(v)) {
284 None | Some(Some(Ordering::Equal)) => self.0.push(value),
285 Some(None) | Some(Some(Ordering::Greater)) => (),
286 Some(Some(Ordering::Less)) => self.replace_with_single(value),
287 }
288 }
289 pub fn insert_gt(&mut self, value: T) {
290 match self.0.first().map(|v| value.partial_cmp(v)) {
291 None | Some(Some(Ordering::Equal)) => self.0.push(value),
292 Some(None) | Some(Some(Ordering::Less)) => (),
293 Some(Some(Ordering::Greater)) => self.replace_with_single(value),
294 }
295 }
296}
297
298impl<'a, T> IntoIterator for &'a BestMultiSet<T> {
299 type Item = &'a T;
300 type IntoIter = BestMultiSetIter<'a, T>;
301 fn into_iter(self) -> Self::IntoIter {
302 self.iter()
303 }
304}