vec_key_value_pair/
map.rs

1use std::{borrow::Borrow, collections::HashMap, ops::Index};
2
3#[cfg(test)]
4mod tests;
5
6///A drop in replacement for [`std::collections::HashMap`] for extensive documentation and examples, see the original data
7///structure.
8#[derive(Default, Clone, Eq)]
9pub struct VecMap<K, V> {
10    vec: Vec<(K, V)>,
11}
12
13impl<K: std::fmt::Debug, V: std::fmt::Debug> std::fmt::Debug for VecMap<K, V> {
14    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
15        // f.debug_struct("VecMap").field("vec", &self.vec).finish()
16        f.debug_map()
17            .entries(self.vec.iter().map(|(k, v)| (k, v)))
18            .finish()
19    }
20}
21
22impl<K: PartialEq + Eq, V: PartialEq> PartialEq for VecMap<K, V> {
23    fn eq(&self, other: &Self) -> bool {
24        self.iter()
25            .map(|i| other.get(i.0).map(|j| j == i.1).unwrap_or_default())
26            .fold(true, |a, i| i && a)
27    }
28}
29
30pub struct VaccantEntrty<'a, K: std::cmp::Eq, V> {
31    key: K,
32    table: &'a mut Vec<(K, V)>,
33}
34
35impl<'a, K, V> VaccantEntrty<'a, K, V>
36where
37    K: std::cmp::Eq,
38{
39    pub const fn key(&self) -> &K {
40        &self.key
41    }
42
43    pub fn into_key(self) -> K {
44        self.key
45    }
46
47    pub fn insert(self, value: V) -> &'a mut V {
48        let key = self.key;
49        self.table.push((key, value));
50        //When we insert a new value it is always last in the vec so this SHOULD be fine
51        &mut self.table.last_mut().unwrap().1
52    }
53}
54impl<K: std::fmt::Debug + std::cmp::Eq, V> std::fmt::Debug for VaccantEntrty<'_, K, V> {
55    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56        f.debug_tuple("VacantEntry").field(self.key()).finish()
57    }
58}
59
60//Sigh, can use RustcOccupied entry, gotta make shit up myself
61pub struct OccupiedEntrty<'a, K: std::cmp::Eq, V> {
62    ///Index of the entry, only useful in here
63    index: usize,
64    // key: &'a K,
65    table: &'a mut Vec<(K, V)>,
66}
67
68impl<'a, K, V> OccupiedEntrty<'a, K, V>
69where
70    K: std::cmp::Eq,
71{
72    pub fn get(&self) -> &V {
73        &self.table.get(self.index).unwrap().1
74    }
75
76    pub fn get_mut(&mut self) -> &mut V {
77        &mut self.table.get_mut(self.index).unwrap().1
78    }
79
80    pub fn insert(&mut self, value: V) -> V {
81        let old = self.table.remove(self.index);
82        self.table.push((old.0, value));
83        old.1
84    }
85
86    pub fn into_mut(self) -> &'a mut V {
87        &mut self.table.get_mut(self.index).unwrap().1
88    }
89
90    pub fn key(&self) -> &K {
91        &self.table.get(self.index).unwrap().0
92    }
93    pub fn remove(self) -> V {
94        self.table.swap_remove(self.index).1
95    }
96
97    pub fn remove_entry(self) -> (K, V) {
98        self.table.remove(self.index)
99    }
100}
101
102pub enum Entry<'a, K, V>
103where
104    K: std::cmp::Eq,
105{
106    Occupied(OccupiedEntrty<'a, K, V>),
107    Vacant(VaccantEntrty<'a, K, V>),
108}
109
110impl<'a, K, V> Entry<'a, K, V>
111where
112    K: std::cmp::Eq,
113{
114    pub fn or_insert(self, default: V) -> &'a mut V {
115        match self {
116            Entry::Occupied(e) => e.into_mut(),
117            Entry::Vacant(e) => e.insert(default),
118        }
119    }
120
121    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
122        match self {
123            Entry::Occupied(e) => e.into_mut(),
124            Entry::Vacant(e) => e.insert(default()),
125        }
126    }
127    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
128        match self {
129            Entry::Occupied(e) => e.into_mut(),
130            Entry::Vacant(e) => {
131                let value = default(&e.key);
132                e.insert(value)
133            }
134        }
135    }
136    pub fn key(&self) -> &K {
137        match self {
138            Entry::Occupied(e) => e.key(),
139            Entry::Vacant(e) => e.key(),
140        }
141    }
142    #[must_use]
143    pub fn and_modify<F>(self, f: F) -> Self
144    where
145        F: FnOnce(&mut V),
146    {
147        match self {
148            Entry::Occupied(mut e) => {
149                let borrow = e.get_mut();
150                f(borrow);
151                Entry::Occupied(e)
152            }
153            Entry::Vacant(_) => self,
154        }
155    }
156}
157impl<'a, K, V> Entry<'a, K, V>
158where
159    K: std::cmp::Eq,
160    V: Default,
161{
162    pub fn or_default(self) -> &'a mut V {
163        self.or_insert(V::default())
164    }
165}
166
167pub struct IntoIter<K, V> {
168    iter: std::vec::IntoIter<(K, V)>,
169}
170
171impl<K, V> Iterator for IntoIter<K, V>
172where
173    K: Eq,
174{
175    type Item = (K, V);
176
177    fn next(&mut self) -> Option<Self::Item> {
178        self.iter.next()
179    }
180}
181
182impl<K, V> ExactSizeIterator for IntoIter<K, V>
183where
184    K: Eq,
185{
186    fn len(&self) -> usize {
187        self.iter.len()
188    }
189}
190
191impl<K, V> IntoIterator for VecMap<K, V>
192where
193    K: Eq,
194{
195    type Item = (K, V);
196
197    type IntoIter = IntoIter<K, V>;
198
199    fn into_iter(self) -> Self::IntoIter {
200        IntoIter {
201            iter: self.vec.into_iter(),
202        }
203    }
204}
205
206#[derive(Clone, Debug)]
207pub struct Keys<'a, K, V> {
208    inner: core::slice::Iter<'a, (K, V)>,
209}
210
211impl<'a, K, V> Iterator for Keys<'a, K, V> {
212    type Item = &'a K;
213
214    fn next(&mut self) -> Option<Self::Item> {
215        match self.inner.next() {
216            Some((k, _)) => Some(k),
217            None => None,
218        }
219    }
220}
221
222impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
223    fn len(&self) -> usize {
224        self.inner.len()
225    }
226}
227
228#[derive(Clone, Debug)]
229pub struct IntoKeys<K, V> {
230    inner: std::vec::IntoIter<(K, V)>,
231}
232
233impl<K, V> Iterator for IntoKeys<K, V> {
234    type Item = K;
235    fn next(&mut self) -> Option<Self::Item> {
236        self.inner.next().map(|i| i.0)
237    }
238}
239
240impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
241    fn len(&self) -> usize {
242        self.inner.len()
243    }
244}
245
246#[derive(Clone, Debug)]
247pub struct Values<'a, K, V> {
248    inner: core::slice::Iter<'a, (K, V)>,
249}
250
251impl<'a, K, V> Iterator for Values<'a, K, V> {
252    type Item = &'a V;
253
254    fn next(&mut self) -> Option<Self::Item> {
255        match self.inner.next() {
256            Some((_, v)) => Some(v),
257            None => None,
258        }
259    }
260}
261
262impl<K, V> ExactSizeIterator for Values<'_, K, V> {
263    fn len(&self) -> usize {
264        self.inner.len()
265    }
266}
267
268#[derive(Debug)]
269pub struct ValuesMut<'a, K, V> {
270    inner: core::slice::IterMut<'a, (K, V)>,
271}
272
273impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
274    type Item = &'a mut V;
275
276    fn next(&mut self) -> Option<Self::Item> {
277        match self.inner.next() {
278            Some((_, v)) => Some(v),
279            None => None,
280        }
281    }
282}
283
284impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
285    fn len(&self) -> usize {
286        self.inner.len()
287    }
288}
289
290#[derive(Clone, Debug)]
291pub struct IntoValues<K, V> {
292    inner: std::vec::IntoIter<(K, V)>,
293}
294
295impl<K, V> Iterator for IntoValues<K, V> {
296    type Item = V;
297    fn next(&mut self) -> Option<Self::Item> {
298        self.inner.next().map(|i| i.1)
299    }
300}
301
302impl<K, V> ExactSizeIterator for IntoValues<K, V> {
303    fn len(&self) -> usize {
304        self.inner.len()
305    }
306}
307
308#[derive(Clone, Debug)]
309pub struct Iter<'a, K, V> {
310    inner: core::slice::Iter<'a, (K, V)>,
311}
312
313impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
314    fn len(&self) -> usize {
315        self.inner.len()
316    }
317}
318
319impl<'a, K, V> Iterator for Iter<'a, K, V> {
320    type Item = (&'a K, &'a V);
321
322    fn next(&mut self) -> Option<Self::Item> {
323        self.inner.next().map(|(k, v)| (k, v))
324    }
325
326    fn size_hint(&self) -> (usize, Option<usize>) {
327        self.inner.size_hint()
328    }
329}
330
331#[derive(Debug)]
332pub struct IterMut<'a, K, V> {
333    inner: core::slice::IterMut<'a, (K, V)>,
334}
335
336impl<'a, K, V> Iterator for IterMut<'a, K, V> {
337    type Item = (&'a K, &'a mut V);
338
339    fn next(&mut self) -> Option<Self::Item> {
340        self.inner.next().map(|(k, v)| (&(*k), v))
341    }
342
343    fn size_hint(&self) -> (usize, Option<usize>) {
344        self.inner.size_hint()
345    }
346}
347
348impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
349    fn len(&self) -> usize {
350        self.inner.len()
351    }
352}
353
354#[derive(Debug)]
355pub struct Drain<'a, K, V> {
356    inner: std::vec::Drain<'a, (K, V)>,
357}
358
359impl<K, V> Iterator for Drain<'_, K, V> {
360    type Item = (K, V);
361
362    fn next(&mut self) -> Option<Self::Item> {
363        self.inner.next()
364    }
365}
366
367impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
368    fn len(&self) -> usize {
369        self.inner.len()
370    }
371}
372
373impl<K, V> VecMap<K, V>
374where
375    K: Eq,
376{
377    ///Creates an empty `VecMap`
378    pub const fn new() -> Self {
379        Self { vec: Vec::new() }
380    }
381
382    //Creates an empty `VecMap` with at least the specified capacity
383    pub fn with_capacity(capacity: usize) -> Self {
384        Self {
385            vec: Vec::with_capacity(capacity),
386        }
387    }
388
389    ///Returns the number of elements the map can hold without reallocating.
390    pub fn capacity(&self) -> usize {
391        self.vec.capacity()
392    }
393
394    pub fn reserve(&mut self, additional: usize) {
395        self.vec.reserve(additional);
396    }
397
398    pub fn len(&self) -> usize {
399        self.vec.len()
400    }
401
402    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
403        let old = self.remove(&k);
404        self.vec.push((k, v));
405
406        old
407    }
408
409    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
410    where
411        K: Borrow<Q> + PartialEq<Q>,
412        Q: Eq + ?Sized,
413    {
414        let mut ind = None;
415        for (index, i) in self.vec.iter().enumerate() {
416            if i.0 == *k {
417                ind = Some(index);
418            }
419        }
420        if let Some(ind) = ind {
421            return Some(self.vec.remove(ind).1);
422        }
423        None
424    }
425
426    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
427    where
428        K: Borrow<Q> + PartialEq<Q>,
429        Q: Eq + ?Sized,
430    {
431        let mut ind = None;
432        for (index, i) in self.vec.iter().enumerate() {
433            if i.0 == *k {
434                ind = Some(index);
435            }
436        }
437        if let Some(ind) = ind {
438            return Some(self.vec.remove(ind));
439        }
440        None
441    }
442
443    pub fn get<Q>(&self, k: &Q) -> Option<&V>
444    where
445        K: Borrow<Q>,
446        Q: Eq + ?Sized,
447    {
448        for (key, v) in &self.vec {
449            if k == key.borrow() {
450                return Some(v);
451            }
452        }
453        None
454    }
455
456    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
457    where
458        K: Borrow<Q>,
459        Q: Eq + ?Sized,
460    {
461        let mut ind = None;
462        for (index, (key, _)) in self.vec.iter().enumerate() {
463            if k == key.borrow() {
464                ind = Some(index);
465            }
466        }
467        Some(&mut self.vec.get_mut(ind?)?.1)
468    }
469
470    pub fn contains_key<Q>(&self, k: &Q) -> bool
471    where
472        K: Borrow<Q> + PartialEq<Q>,
473        Q: Eq + ?Sized,
474    {
475        for (key, _) in &self.vec {
476            if key == k {
477                return true;
478            }
479        }
480        false
481    }
482
483    pub fn shrink_to_fit(&mut self) {
484        self.vec.shrink_to_fit();
485    }
486
487    pub fn shrink_to(&mut self, min_capacity: usize) {
488        self.vec.shrink_to(min_capacity);
489    }
490
491    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
492        match {
493            let mut val = None;
494            for (index, (map_key, _)) in self.vec.iter().enumerate() {
495                if &key == map_key {
496                    val = Some(index);
497                    break;
498                }
499            }
500            val
501        } {
502            Some(e) => Entry::Occupied(OccupiedEntrty {
503                index: e,
504                table: &mut self.vec,
505            }),
506            None => Entry::Vacant(VaccantEntrty {
507                key,
508                table: &mut self.vec,
509            }),
510        }
511    }
512    pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
513    where
514        K: Borrow<Q> + PartialEq<Q>,
515        Q: Eq + ?Sized,
516    {
517        for i in &self.vec {
518            if &i.0 == k {
519                return Some((&i.0, &i.1));
520            }
521        }
522        None
523    }
524
525    pub fn keys(&self) -> Keys<'_, K, V> {
526        Keys {
527            inner: self.vec.iter(),
528        }
529    }
530
531    pub fn into_keys(self) -> IntoKeys<K, V> {
532        IntoKeys {
533            inner: self.vec.into_iter(),
534        }
535    }
536
537    pub fn values(&self) -> Values<'_, K, V> {
538        Values {
539            inner: self.vec.iter(),
540        }
541    }
542
543    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
544        ValuesMut {
545            inner: self.vec.iter_mut(),
546        }
547    }
548
549    pub fn into_values(self) -> IntoValues<K, V> {
550        IntoValues {
551            inner: self.vec.into_iter(),
552        }
553    }
554
555    pub fn iter(&self) -> Iter<'_, K, V> {
556        Iter {
557            inner: self.vec.iter(),
558        }
559    }
560
561    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
562        IterMut {
563            inner: self.vec.iter_mut(),
564        }
565    }
566
567    pub fn is_empty(&self) -> bool {
568        self.vec.is_empty()
569    }
570
571    pub fn drain(&mut self) -> Drain<'_, K, V> {
572        Drain {
573            inner: self.vec.drain(..),
574        }
575    }
576
577    pub fn retain<F>(&mut self, f: F)
578    where
579        F: FnMut(&K, &mut V) -> bool,
580    {
581        let mut f = f;
582        self.vec.retain_mut(|i| f(&i.0, &mut i.1));
583    }
584
585    pub fn clear(&mut self) {
586        self.vec.clear();
587    }
588
589    pub fn hasher<S>(&self) -> &S
590    where
591        S: std::hash::BuildHasher,
592    {
593        unimplemented!("Hasher is not implemented for VecMap");
594    }
595}
596
597impl<'a, K, V> Extend<(&'a K, &'a V)> for VecMap<K, V>
598where
599    K: Eq + Copy,
600    V: Copy,
601{
602    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
603        for (k, v) in iter {
604            self.insert(*k, *v);
605        }
606    }
607}
608
609impl<K, V> Extend<(K, V)> for VecMap<K, V>
610where
611    K: Eq,
612{
613    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
614        for (k, v) in iter {
615            self.insert(k, v);
616        }
617    }
618}
619
620impl<K, V, const N: usize> From<[(K, V); N]> for VecMap<K, V>
621where
622    K: Eq,
623{
624    fn from(value: [(K, V); N]) -> Self {
625        let mut o = Self::new();
626        for (k, v) in value {
627            o.insert(k, v);
628        }
629        o
630    }
631}
632
633impl<K, V> FromIterator<(K, V)> for VecMap<K, V>
634where
635    K: Eq,
636{
637    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
638        let mut o = Self::new();
639        for (k, v) in iter {
640            o.insert(k, v);
641        }
642        o
643    }
644}
645
646impl<K, Q, V> Index<&Q> for VecMap<K, V>
647where
648    K: Eq + Borrow<Q>,
649    Q: Eq + ?Sized,
650{
651    type Output = V;
652
653    fn index(&self, index: &Q) -> &Self::Output {
654        self.get(index).unwrap()
655    }
656}
657
658impl<'a, K, V> IntoIterator for &'a VecMap<K, V> {
659    type Item = (&'a K, &'a V);
660
661    type IntoIter = Iter<'a, K, V>;
662
663    fn into_iter(self) -> Self::IntoIter {
664        Iter {
665            inner: self.vec.iter(),
666        }
667    }
668}
669
670impl<'a, K, V> IntoIterator for &'a mut VecMap<K, V> {
671    type Item = (&'a K, &'a mut V);
672
673    type IntoIter = IterMut<'a, K, V>;
674
675    fn into_iter(self) -> Self::IntoIter {
676        IterMut {
677            inner: self.vec.iter_mut(),
678        }
679    }
680}
681
682impl<K, V> PartialEq<HashMap<K, V>> for VecMap<K, V>
683where
684    K: Eq,
685    V: PartialEq,
686{
687    fn eq(&self, other: &HashMap<K, V>) -> bool {
688        other.iter().eq(self.iter())
689    }
690}
vec_key_value_pair/map.rs

vec_key_value_pair/
map.rs
