unique_id_lookup/lib.rs
1use std::collections::HashMap;
2
3/// An associative array specifically designed for integer keys.
4///
5/// # Examples
6///
7/// ```
8/// use unique_id_lookup::UniqueIdLookup;
9/// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
10/// lookup.insert(5, 'a');
11/// assert_eq!(lookup.get(5).unwrap(), 'a');
12/// ```
13pub struct UniqueIdLookup<T> {
14 buf: Vec<Option<T>>,
15 offset: usize,
16}
17
18/// Will be retired soon.
19pub struct UniqueIdLookupIterator<'a, T> {
20 lookup: &'a UniqueIdLookup<T>,
21 index: usize,
22}
23
24/// An iterator over the ID-value pairs visiting all occupied entries.
25pub struct UniqueIdLookupIteratorOccupied<'a, T> {
26 lookup: &'a UniqueIdLookup<T>,
27 index: usize,
28}
29
30/// An iterator over the values (only occupied entries have a value).
31pub struct UniqueIdLookupIteratorValues<'a, T> {
32 lookup: &'a UniqueIdLookup<T>,
33 index: usize,
34}
35
36/// An iterator over the IDs visiting all vacant entries.
37pub struct UniqueIdLookupIteratorVacantIDs<'a, T> {
38 lookup: &'a UniqueIdLookup<T>,
39 index: usize,
40}
41
42impl<T> UniqueIdLookup<T> {
43 const RESULT_NONE: Option<T> = None;
44
45 /// Creates an empty `UniqueIdLookup`.
46 ///
47 /// The map is initially created with a capacity of 0, so it will not allocate until it
48 /// is first inserted into.
49 ///
50 /// # Examples
51 ///
52 /// ```
53 /// use unique_id_lookup::UniqueIdLookup;
54 /// let mut lookup: UniqueIdLookup<i16> = UniqueIdLookup::new();
55 /// ```
56 pub const fn new() -> Self {
57 UniqueIdLookup {
58 buf: Vec::new(),
59 offset: 0,
60 }
61 }
62
63 /// Creates an empty `UniqueIdLookup` with at least the specified capacity.
64 #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `with_capacity_and_offset()` instead.")]
65 pub fn with_capacity(capacity: usize) -> Self {
66 UniqueIdLookup::with_capacity_and_offset(capacity, 0)
67 }
68
69 /// Creates an empty `UniqueIdLookup` with at least the specified capacity and `offset` (the minimum ID).
70 ///
71 /// If `capacity` and `offset` are set correctly this leads to more space efficiency and
72 /// a constant time complexity of `insert()`.
73 pub fn with_capacity_and_offset(capacity: usize, offset: usize) -> Self {
74 UniqueIdLookup {
75 buf: Vec::with_capacity(capacity),
76 offset,
77 }
78 }
79
80 /// Creates an empty `UniqueIdLookup` capacity to hold all values between min_id and max_id.
81 ///
82 /// # Examples
83 ///
84 /// ```
85 /// use unique_id_lookup::UniqueIdLookup;
86 /// let min_id = 10;
87 /// let max_id = 30;
88 /// let lookup: UniqueIdLookup<i16> = UniqueIdLookup::with_min_max_id(min_id, max_id);
89 /// assert_eq!(lookup.get_offset(), min_id);
90 /// assert_eq!(lookup.capacity(), 1 + max_id - min_id);
91 /// ```
92 pub fn with_min_max_id<I: Into<usize> + Copy>(min_id: I, max_id: I) -> Self {
93 let capacity = 1 + max_id.into() - min_id.into();
94 UniqueIdLookup::with_capacity_and_offset(capacity, min_id.into())
95 }
96
97 /// Creates a `UniqueIdLookup<T>` from a `HashMap<I, T>`.
98 ///
99 /// The ID-Type `I` has to implement the trait `Into<usize>`.
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// use std::collections::HashMap;
105 /// use unique_id_lookup::UniqueIdLookup;
106 /// let hash_map: HashMap<u16, char> = HashMap::from([(65, 'A'), (66, 'B')]);
107 /// let lookup = UniqueIdLookup::from_hash_map(hash_map);
108 /// ```
109 pub fn from_hash_map<I: Into<usize> + Ord + Copy>(map: HashMap<I, T>) -> Self {
110 if map.is_empty() {
111 return UniqueIdLookup::new();
112 }
113
114 let min_id = (*map.keys().min().unwrap()).into();
115 let max_id = (*map.keys().max().unwrap()).into();
116 let mut lookup = UniqueIdLookup::with_min_max_id(min_id, max_id);
117 for (id, v) in map.into_iter() {
118 lookup.insert(id.into(), v);
119 }
120 lookup
121 }
122
123 /// Inserts a ID-value pair into the map.
124 ///
125 /// The method always inserts (replaces it the key is present already).
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use unique_id_lookup::UniqueIdLookup;
131 /// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
132 /// lookup.insert(1, 'a');
133 /// assert_eq!(lookup.get(1).unwrap(), 'a');
134 /// lookup.insert(1, 'b');
135 /// assert_eq!(lookup.get(1).unwrap(), 'b');
136 /// ```
137 ///
138 /// # Complexity
139 ///
140 /// Can have constant time complexity if the map is pre-allocated using with_capacity_and_offset().
141 pub fn insert(&mut self, id: usize, value: T) -> &mut T {
142 if !self.buf.is_empty() {
143 if id < self.offset {
144 let nbr_prepend_elements = self.offset - id;
145 for _i in 0..(nbr_prepend_elements - 1) {
146 self.buf.insert(0, None);
147 }
148 self.buf.insert(0, Some(value));
149 self.offset = id;
150 return self.buf[0].as_mut().unwrap();
151 } else {
152 let index = id - self.offset;
153 if index < self.buf.len() {
154 self.buf[index] = Some(value);
155 } else {
156 self.buf.resize_with(index + 1, || None);
157 self.buf[index] = Some(value);
158 }
159 return self.buf[index].as_mut().unwrap();
160 }
161 } else {
162 // empty
163 if self.capacity() == 0 || id < self.offset {
164 self.offset = id;
165 self.buf.push(Some(value));
166 return self.buf[0].as_mut().unwrap();
167 } else {
168 let index = id - self.offset;
169 self.buf.resize_with(index + 1, || None);
170 self.buf[index] = Some(value);
171 return self.buf[index].as_mut().unwrap();
172 }
173 }
174 }
175
176
177 /// Only inserts a ID-value pair into the map if not present, and does nothing otherwise.
178 ///
179 /// # Examples
180 ///
181 /// ```
182 /// use unique_id_lookup::UniqueIdLookup;
183 /// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
184 /// lookup.insert_if_absent(1, 'a');
185 /// assert_eq!(lookup.get(1).unwrap(), 'a');
186 /// lookup.insert_if_absent(1, 'b');
187 /// assert_eq!(lookup.get(1).unwrap(), 'a');
188 /// ```
189 ///
190 /// # Complexity
191 ///
192 /// Can have constant time complexity if the map is pre-allocated using with_capacity_and_offset().
193 pub fn insert_if_absent(&mut self, id: usize, value: T) -> &mut T {
194 if self.contains_id(id) {
195 return self.get_mut(id).unwrap();
196 }
197 return self.insert(id, value);
198 }
199
200 /// Returns `true` if the map contains a value for the specified ID.
201 ///
202 /// # Examples
203 ///
204 /// ```
205 /// use unique_id_lookup::UniqueIdLookup;
206 /// let mut lookup: UniqueIdLookup<i16> = UniqueIdLookup::new();
207 /// lookup.insert(5, 17);
208 /// assert_eq!(lookup.contains_id(0), false);
209 /// assert_eq!(lookup.contains_id(5), true);
210 /// ```
211 #[inline]
212 pub fn contains_id(&self, id: usize) -> bool {
213 if id < self.offset {
214 return false;
215 }
216 let index = id - self.offset;
217 if index >= self.buf.len() {
218 return false;
219 }
220 let value = &self.buf[index];
221 value.is_some()
222 }
223
224 /// Returns a reference to an element or `None` if the ID was not found.
225 ///
226 /// # Panics
227 ///
228 /// Panics if `id` is out of bounds of the underlying vector.
229 ///
230 /// # Examples
231 ///
232 /// ```
233 /// use std::collections::HashMap;
234 /// use unique_id_lookup::UniqueIdLookup;
235 /// let hash_map: HashMap<u16, char> = HashMap::from([(5, 'c')]);
236 /// let lookup = UniqueIdLookup::from_hash_map(hash_map);
237 /// let c = lookup.get(5).unwrap();
238 /// ```
239 #[inline]
240 pub fn get(&self, id: usize) -> &Option<T> {
241 let index = id - self.offset;
242 &self.buf[index]
243 }
244
245 /// Same as .get() but returns None outside of the bounds of the underlying vector.
246 #[inline]
247 pub fn get_or_none(&self, id: usize) -> &Option<T> {
248 if id < self.offset {
249 return &UniqueIdLookup::RESULT_NONE;
250 }
251 let index = id - self.offset;
252 if index >= self.buf.len() {
253 return &UniqueIdLookup::RESULT_NONE;
254 }
255 &self.buf[index]
256 }
257
258 /// Returns a mutable reference to an element or `None` if the ID was not found.
259 #[inline]
260 pub fn get_mut(&mut self, id: usize) -> Option<&mut T> {
261 let index = id - self.offset;
262 self.buf.get_mut(index)?.as_mut()
263 }
264
265 /// Removes and returns the element with ID `id`. Essentially this is just marking the element as vacant.
266 ///
267 /// # Panics
268 ///
269 /// Panics if `id` is out of bounds of the underlying vector.
270 ///
271 /// # Complexity
272 ///
273 /// Constant time complexity
274 ///
275 /// # Examples
276 ///
277 /// ```
278 /// use std::collections::HashMap;
279 /// use unique_id_lookup::UniqueIdLookup;
280 /// let hash_map: HashMap<u16, char> = HashMap::from([(5, 'c'), (6, 'd')]);
281 /// let mut lookup = UniqueIdLookup::from_hash_map(hash_map);
282 /// assert_eq!(lookup.len_occupied(), 2);
283 /// assert_eq!(lookup.remove(5).unwrap(), 'c');
284 /// assert_eq!(lookup.len_occupied(), 1);
285 /// assert!(lookup.get(5).is_none());
286 /// ```
287 #[inline]
288 pub fn remove(&mut self, id: usize) -> Option<T> {
289 let index = id - self.offset;
290 let mut removed_value: Option<T> = None;
291 std::mem::swap(&mut self.buf[index], &mut removed_value);
292 removed_value
293 }
294
295 /// An iterator visiting all elements that have a value.
296 #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `iter_occupied()` instead.")]
297 pub fn iter(&self) -> UniqueIdLookupIterator<T> {
298 UniqueIdLookupIterator {
299 lookup: self,
300 index: 0,
301 }
302 }
303
304 /// Returns an iterator over the ID-value pairs visiting all occupied entries.
305 ///
306 /// The iterator element type is the tuple (usize, &'a T)`.
307 ///
308 /// # Examples
309 ///
310 /// ```
311 /// use unique_id_lookup::UniqueIdLookup;
312 /// let arr: [(usize, char); 3] = [(5, 'c'), (6, 'd'), (8, 'f')];
313 /// let lookup = UniqueIdLookup::from(arr);
314 /// for (id, payload) in lookup.iter_occupied() {
315 /// let tup = (id, *payload);
316 /// assert!(arr.contains(&tup));
317 /// }
318 /// ```
319 pub fn iter_occupied(&self) -> UniqueIdLookupIteratorOccupied<T> {
320 UniqueIdLookupIteratorOccupied {
321 lookup: self,
322 index: 0,
323 }
324 }
325
326 /// Returns an iterator over the values (only occupied entries have a value).
327 ///
328 /// The iterator element type is &'a T.
329 ///
330 /// # Examples
331 ///
332 /// ```
333 /// use unique_id_lookup::UniqueIdLookup;
334 /// let arr: [(usize, char); 3] = [(5, 'c'), (6, 'd'), (8, 'f')];
335 /// let lookup = UniqueIdLookup::from(arr);
336 /// for payload in lookup.values() {
337 /// assert!(['c', 'd', 'f'].contains(&payload));
338 /// }
339 /// ```
340 pub fn values(&self) -> UniqueIdLookupIteratorValues<T> {
341 UniqueIdLookupIteratorValues {
342 lookup: self,
343 index: 0,
344 }
345 }
346
347 /// An iterator visiting all vacant IDs.
348 ///
349 /// # Examples
350 ///
351 /// ```
352 /// use unique_id_lookup::UniqueIdLookup;
353 /// let arr: [(usize, char); 4] = [(5, 'c'), (6, 'd'), (8, 'f'), (10, 'h')];
354 /// let lookup = UniqueIdLookup::from(arr);
355 /// for id in lookup.iter_vacant_ids() {
356 /// assert_eq!([7, 9].contains(&id), true);
357 /// }
358 /// ```
359 pub fn iter_vacant_ids(&self) -> UniqueIdLookupIteratorVacantIDs<T> {
360 UniqueIdLookupIteratorVacantIDs {
361 lookup: self,
362 index: 0,
363 }
364 }
365
366 /// Returns the offset to the underlying (dynamic) array. Mainly important for testing.
367 #[inline]
368 pub const fn get_offset(&self) -> usize {
369 self.offset
370 }
371
372 #[inline]
373 pub fn capacity(&self) -> usize {
374 self.buf.capacity()
375 }
376
377 /// Returns the number of elements in the underlying (dynamic) array.
378 #[inline]
379 pub fn range_len(&self) -> usize {
380 self.buf.len()
381 }
382
383 /// Returns the number of elements in the underlying (dynamic) array that actually have a value.
384 #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `len_occupied()` instead (just a name change).")]
385 pub fn len(&self) -> usize {
386 self.len_occupied()
387 }
388
389 /// Returns the number of occupied entries.
390 ///
391 /// # Complexity
392 ///
393 /// Takes linear (in `self.buf.len()`) time.
394 pub fn len_occupied(&self) -> usize {
395 self.buf.iter().filter(|payload| payload.is_some()).count()
396 }
397
398 /// Returns the fraction of accupied elements to all elements in the underlying vector.
399 ///
400 /// UniqueIdLookup is a good choice if the density is close to 1.
401 ///
402 /// ```
403 /// use std::collections::HashMap;
404 /// use unique_id_lookup::UniqueIdLookup;
405 /// let hash_map: HashMap<u16, char> = HashMap::from([(1, 'a'), (4, 'd')]);
406 /// let mut lookup = UniqueIdLookup::from_hash_map(hash_map);
407 /// assert_eq!(lookup.occupation_density(), 0.5);
408 /// ```
409 pub fn occupation_density(&self) -> f64 {
410 if self.buf.is_empty() {
411 return f64::NAN;
412 }
413 self.len_occupied() as f64 / self.buf.len() as f64
414 }
415
416 /// Returns false if at least one occupied entry exists.
417 pub fn is_occupied_empty(&self) -> bool {
418 for e in self.buf.iter() {
419 if e.is_some() {
420 return false;
421 }
422 }
423 true
424 }
425
426 #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `is_occupied_empty()` instead (just a name change).")]
427 pub fn is_empty(&self) -> bool {
428 self.is_occupied_empty()
429 }
430
431 /// Returns a flatten vector with all occupied entires consuming the collection itself.
432 ///
433 /// # Examples
434 ///
435 /// ```
436 /// use unique_id_lookup::UniqueIdLookup;
437 /// let arr: [(usize, char); 4] = [(5, 'c'), (6, 'd'), (8, 'f'), (10, 'h')];
438 /// let lookup = UniqueIdLookup::from(arr);
439 /// assert_eq!(lookup.into_occupied_vec(), vec!['c', 'd', 'f', 'h']);
440 /// ```
441 pub fn into_occupied_vec(self) -> Vec<T> {
442 let nbr_occupied = self.len_occupied();
443 let mut result = Vec::with_capacity(nbr_occupied);
444 for item in self.buf.into_iter().flatten() {
445 result.push(item);
446 }
447 result
448 }
449
450 /// Shrinks the capacity of the underlying vector as much as possible.
451 ///
452 /// This includes removing vacant ememnts on both sides. Hence the offset might be changed.
453 ///
454 /// # Examples
455 ///
456 /// ```
457 /// use unique_id_lookup::UniqueIdLookup;
458 /// let mut lookup = UniqueIdLookup::with_capacity_and_offset(10, 5);
459 /// assert_eq!(lookup.get_offset(), 5);
460 /// lookup.insert(8, 8);
461 /// lookup.insert(12, 12);
462 /// assert_eq!(lookup.get_offset(), 5);
463 ///
464 /// lookup.shrink_to_fit_and_trim_vacant();
465 /// assert_eq!(lookup.len_occupied(), 2);
466 /// assert_eq!(lookup.capacity(), 5);
467 /// assert_eq!(lookup.get_offset(), 8);
468 /// assert_eq!(lookup.get(8).unwrap(), 8);
469 /// assert_eq!(lookup.get(12).unwrap(), 12);
470 /// ```
471 pub fn shrink_to_fit_and_trim_vacant(&mut self) {
472 if let Some(index_r) = self.buf.iter().rposition(Option::is_some) {
473 self.buf.truncate(index_r + 1);
474 let mut new_offset = self.offset;
475 while !self.buf.is_empty() && self.buf[0].is_none() {
476 self.buf.remove(0);
477 new_offset += 1;
478 }
479 self.offset = new_offset;
480 } else {
481 self.buf.clear();
482 self.offset = 0;
483 }
484 self.buf.shrink_to_fit()
485 }
486
487}
488
489/// Will be retired soon.
490impl<'a, T> Iterator for UniqueIdLookupIterator<'a, T> {
491 type Item = (usize, &'a Option<T>);
492
493 fn next(&mut self) -> Option<Self::Item> {
494 while self.index < self.lookup.buf.len() {
495 let payload = &self.lookup.buf[self.index];
496 if payload.is_none() {
497 self.index += 1;
498 continue;
499 }
500 let id = self.index + self.lookup.offset;
501 let result = Some((id, payload));
502 self.index += 1;
503 return result;
504 }
505 None
506 }
507}
508
509
510
511
512impl<'a, T> Iterator for UniqueIdLookupIteratorValues<'a, T> {
513 type Item = &'a T;
514
515 fn next(&mut self) -> Option<Self::Item> {
516 while self.index < self.lookup.buf.len() {
517 let payload = &self.lookup.buf[self.index];
518 if payload.is_none() {
519 self.index += 1;
520 continue;
521 }
522 let result = Some(payload.as_ref().unwrap());
523 self.index += 1;
524 return result;
525 }
526 None
527 }
528}
529
530impl<'a, T> Iterator for UniqueIdLookupIteratorOccupied<'a, T> {
531 type Item = (usize, &'a T);
532
533 fn next(&mut self) -> Option<Self::Item> {
534 while self.index < self.lookup.buf.len() {
535 let payload = &self.lookup.buf[self.index];
536 if payload.is_none() {
537 self.index += 1;
538 continue;
539 }
540 let id = self.index + self.lookup.offset;
541 let result = Some((id, payload.as_ref().unwrap()));
542 self.index += 1;
543 return result;
544 }
545 None
546 }
547}
548
549impl<'a, T> Iterator for UniqueIdLookupIteratorVacantIDs<'a, T> {
550 type Item = usize;
551
552 fn next(&mut self) -> Option<Self::Item> {
553 while self.index < self.lookup.buf.len() {
554 let payload = &self.lookup.buf[self.index];
555 if payload.is_some() {
556 self.index += 1;
557 continue;
558 }
559 let id = self.index + self.lookup.offset;
560 let result = Some(id);
561 self.index += 1;
562 return result;
563 }
564 None
565 }
566}
567
568impl<I, T, const N: usize> From<[(I, T); N]> for UniqueIdLookup<T>
569where
570 I: Into<usize> + Ord + Copy,
571{
572 /// Converts a array `[(I, T); N]` into a `UniqueIdLookup<T>`.
573 ///
574 /// # Examples
575 ///
576 /// ```
577 /// use unique_id_lookup::UniqueIdLookup;
578 ///
579 /// let arr: [(usize, char); 3] = [(5, 'c'), (7, 'e'), (8, 'f')];
580 /// let lookup = UniqueIdLookup::from(arr);
581 /// assert_eq!(lookup.len_occupied(), 3);
582 /// assert_eq!(lookup.get(5).unwrap(), 'c');
583 /// ```
584 fn from(arr: [(I, T); N]) -> Self {
585 if arr.is_empty() {
586 return UniqueIdLookup::new();
587 }
588 let mut min_id = usize::MAX;
589 let mut max_id = 0usize;
590 for &(id, _) in &arr {
591 let id_usize = id.into();
592 min_id = min_id.min(id_usize);
593 max_id = max_id.max(id_usize);
594 }
595 let mut lookup = UniqueIdLookup::with_min_max_id(min_id, max_id);
596 for (id, v) in arr.into_iter() {
597 lookup.insert(id.into(), v);
598 }
599 lookup
600 }
601}