assoc_list/
lib.rs

1#![allow(dead_code)]
2
3use std::borrow::Borrow;
4
5pub struct AssocList<K, V>(Vec<(K, V)>);
6pub enum Entry<'a, K, V> {
7    Vacant(VacantEntry<'a, K, V>),
8    Occupied(OccupiedEntry<'a, K, V>),
9}
10pub struct VacantEntry<'a, K, V> {
11    key: K,
12    map: &'a mut AssocList<K, V>,
13}
14pub struct OccupiedEntry<'a, K, V> {
15    key: K,
16    map: &'a mut AssocList<K, V>,
17}
18
19impl<K: Eq, V> AssocList<K, V> {
20    pub fn new() -> Self { Self(vec![]) }
21
22    pub fn is_empty(&self) -> bool { self.0.is_empty() }
23    pub fn len(&self) -> usize { self.0.len() }
24
25    pub fn get<Q>(&self, key: Q) -> Option<&V>
26    where
27        Q: Borrow<K>,
28        K: PartialEq<Q>,
29    {
30        self.0.iter().find(|(k, _)| k == &key).map(|(_, v)| v)
31    }
32
33    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
34        if let Some((_, v)) = self.0.iter_mut().find(|(k, _)| k == &key) {
35            Some(std::mem::replace(v, value))
36        } else {
37            self.0.push((key, value));
38            None
39        }
40    }
41
42    pub fn remove<Q>(&mut self, key: Q) -> Option<V>
43    where
44        Q: Borrow<K>,
45        K: PartialEq<Q>,
46    {
47        (0..self.0.len())
48            .find(|&i| self.0[i].0 == key)
49            .map(|i| self.0.remove(i).1)
50    }
51
52    pub fn entry(&mut self, key: K) -> Entry<K, V> {
53        if self.0.iter().any(|(k, _)| k == &key) {
54            Entry::occupied(key, self)
55        } else {
56            Entry::vacant(key, self)
57        }
58    }
59}
60
61impl<K: Eq, V> Default for AssocList<K, V> {
62    fn default() -> Self { Self::new() }
63}
64
65impl<'a, K: Eq, V> Entry<'a, K, V> {
66    pub(crate) fn vacant(key: K, map: &'a mut AssocList<K, V>) -> Self {
67        Self::Vacant(VacantEntry { key, map })
68    }
69    pub(crate) fn occupied(key: K, map: &'a mut AssocList<K, V>) -> Self {
70        Self::Occupied(OccupiedEntry { key, map })
71    }
72
73    pub fn and_modify<F: FnOnce(&mut V)>(self, f: F) -> Entry<'a, K, V> {
74        match self {
75            Self::Occupied(mut entry) => {
76                f(entry.get_mut());
77                Self::Occupied(entry)
78            }
79            Self::Vacant(entry) => Self::Vacant(entry),
80        }
81    }
82
83    pub fn key(&self) -> &K {
84        match *self {
85            Self::Occupied(ref entry) => entry.key(),
86            Self::Vacant(ref entry) => entry.key(),
87        }
88    }
89    pub fn or_default(self) -> &'a mut V
90    where
91        V: Default,
92    {
93        match self {
94            Self::Occupied(entry) => entry.into_mut(),
95            Self::Vacant(entry) => entry.insert(Default::default()),
96        }
97    }
98    pub fn or_insert(self, default: V) -> &'a mut V {
99        match self {
100            Self::Occupied(entry) => entry.into_mut(),
101            Self::Vacant(entry) => entry.insert(default),
102        }
103    }
104    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
105        match self {
106            Self::Occupied(entry) => entry.into_mut(),
107            Self::Vacant(entry) => entry.insert(default()),
108        }
109    }
110    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(
111        self,
112        default: F,
113    ) -> &'a mut V {
114        match self {
115            Self::Occupied(entry) => entry.into_mut(),
116            Self::Vacant(entry) => {
117                let value = default(entry.key());
118                entry.insert(value)
119            }
120        }
121    }
122}
123
124impl<'a, K: Eq, V> VacantEntry<'a, K, V> {
125    pub fn into_key(self) -> K { self.key }
126    pub fn key(&self) -> &K { &self.key }
127    pub fn insert(self, value: V) -> &'a mut V {
128        let Self { key, map } = self;
129        map.0.push((key, value));
130        &mut map.0.last_mut().unwrap().1
131    }
132}
133
134impl<'a, K: Eq, V> OccupiedEntry<'a, K, V> {
135    pub fn insert(&mut self, value: V) -> V {
136        std::mem::replace(self.get_mut(), value)
137    }
138    pub fn get(&self) -> &V {
139        let Self { key, map } = self;
140        map.0.iter().find(|(k, _)| k == key).map(|(_, v)| v).unwrap()
141    }
142    pub fn get_mut(&mut self) -> &mut V {
143        let Self { key, map } = self;
144        map.0.iter_mut().find(|(k, _)| k == key).map(|(_, v)| v).unwrap()
145    }
146    pub fn into_mut(self) -> &'a mut V {
147        let Self { key, map } = self;
148        map.0.iter_mut().find(|(k, _)| k == &key).map(|(_, v)| v).unwrap()
149    }
150    pub fn key(&self) -> &K { &self.key }
151    pub fn remove(self) -> V { self.remove_entry().1 }
152    pub fn remove_entry(self) -> (K, V) {
153        let Self { key, map } = self;
154        let i = (0..map.len()).find(|&i| key == map.0[i].0).unwrap();
155        map.0.remove(i)
156    }
157}
158
159#[test]
160fn sanity_check() {
161    let mut alist = AssocList::new();
162
163    assert_eq!(alist.entry(0).key(), &0);
164
165    alist.entry(0).or_insert("zero");
166    assert_eq!(alist.get(0).unwrap(), &"zero");
167    assert_eq!(alist.len(), 1);
168
169    alist.entry(0).or_insert_with(|| "xxx");
170    assert_eq!(alist.get(0).unwrap(), &"zero");
171    assert_eq!(alist.len(), 1);
172
173    alist.entry(2).or_insert_with_key(|_| "two");
174    assert!(alist.get(1).is_none());
175    assert_eq!(alist.get(2).unwrap(), &"two");
176    assert_eq!(alist.len(), 2);
177
178    alist.entry(2).and_modify(|v| *v = "second");
179    assert_eq!(alist.len(), 2);
180
181    if let Entry::Occupied(o) = alist.entry(2) {
182        assert_eq!(o.get(), &"second");
183        assert_eq!(o.remove(), "second");
184        assert_eq!(alist.len(), 1);
185    }
186
187    alist.entry(1).or_default();
188    assert_eq!(alist.len(), 2);
189    assert!(alist.get(1).unwrap().is_empty());
190    if let Entry::Occupied(mut o) = alist.entry(1) {
191        o.insert("first");
192        assert_eq!(o.get(), &"first");
193    }
194}
assoc_list/lib.rs

assoc_list/
lib.rs
