list_ordered_hashmap/
lib.rs

1//! [OrderedHashMap] is an insertion‑ordered hash map that provides O(1) insertion,
2//! lookup, update and removal while preserving the order in which keys were first inserted.
3//!
4//! A new key inserted with [`insert`](OrderedHashMap::insert) is appended to the logical end of the
5//! sequence. Updating an
6//! existing key only changes its value; its relative position does not move. Removing a key unlinks
7//! it in O(1) time. If the same key is inserted again later, it is treated as a fresh insertion and
8//! appears at the end of the iteration order.
9//!
10//! Internally the structure keeps a [`HashMap<K, Index>`] which maps each key to an index inside a
11//! doubly‑linked list [`IndexList<(K, V)>`]. The list stores the actual
12//! `(K, V)` pairs plus linkage (next / prev indices) inside a single slab / arena structure. Each
13//! node is just a slot within that slab; inserting a new element only grows the slab
14//! vector, so there is not a separate heap allocation per entry. Removal uses the stored index to
15//! unlink a node in O(1) without any traversal and without shifting other live elements. This
16//! avoids both the per-node allocation overhead of a classic pointer‑based linked list and the O(n)
17//! element movement costs of a simple vector when deleting from the middle.
18//!
19//! The primary iteration methods ([`iter`](OrderedHashMap::iter), [`keys`](OrderedHashMap::keys),
20//! and [`values`](OrderedHashMap::values)) yield items in insertion order.
21//! Operations `insert`, `get`, `get_mut`, `contains_key`, and `remove` are all O(1) on average.
22//!
23//! The API is intentionally similar to `indexmap::IndexMap`, but this implementation relies on an
24//! [`IndexList`] rather than a simple [`Vec`] so that removals don't cause O(n) shifts.
25
26use derive_where::derive_where;
27use index_list::{Index, IndexList};
28use std::borrow::Borrow;
29use std::collections::HashMap;
30use std::hash::Hash;
31use std::mem;
32
33pub mod entry;
34
35pub use crate::entry::{Entry, OccupiedEntry, VacantEntry};
36
37#[derive_where(Default)]
38pub struct OrderedHashMap<K, V> {
39    map: HashMap<K, Index>,
40    order: IndexList<(K, V)>,
41}
42
43impl<K, V> OrderedHashMap<K, V> {
44    pub fn new() -> Self {
45        Self {
46            map: HashMap::new(),
47            order: IndexList::new(),
48        }
49    }
50
51    pub fn with_capacity(capacity: usize) -> Self {
52        Self {
53            map: HashMap::with_capacity(capacity),
54            order: IndexList::with_capacity(capacity),
55        }
56    }
57
58    pub fn len(&self) -> usize {
59        let Self { map, order } = self;
60        assert_eq!(map.len(), order.len());
61        order.len()
62    }
63
64    pub fn capacity(&self) -> usize {
65        let Self { map, order } = self;
66        map.capacity().min(order.capacity())
67    }
68
69    pub fn is_empty(&self) -> bool {
70        let Self { map, order } = self;
71        assert_eq!(map.is_empty(), order.is_empty());
72        order.is_empty()
73    }
74
75    /// Iterator over (&K, &V) in insertion order.
76    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
77        self.order.iter().map(|(k, v)| (k, v))
78    }
79
80    /// Iterator over (&K, &mut V) in insertion order.
81    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
82        self.order.iter_mut().map(|(k, v)| (&*k, v))
83    }
84
85    #[deprecated(note = "use `iter_mut` instead")]
86    pub fn for_each_mut(&mut self, mut f: impl FnMut(&K, &mut V)) {
87        let mut index = self.order.first_index();
88        while let Some((k, v)) = self.order.get_mut(index) {
89            f(k, v);
90            index = self.order.next_index(index);
91        }
92    }
93
94    /// Returns an iterator over keys in insertion order.
95    pub fn keys(&self) -> impl Iterator<Item = &K> {
96        self.iter().map(|(k, _)| k)
97    }
98
99    /// Returns an iterator over values in insertion order.
100    pub fn values(&self) -> impl Iterator<Item = &V> {
101        self.iter().map(|(_, v)| v)
102    }
103}
104
105impl<K: Eq + Hash, V> OrderedHashMap<K, V> {
106    /// Insert a key-value pair.
107    /// - If the key is new: appends to the end; returns `None`.
108    /// - If the key exists: replaces the value in-place; returns `Some(old_v)`.
109    pub fn insert(&mut self, key: K, value: V) -> Option<V>
110    where
111        K: Clone,
112    {
113        match self.entry(key) {
114            Entry::Occupied(occupied_entry) => {
115                let old = mem::replace(occupied_entry.into_mut(), value);
116                Some(old)
117            }
118            Entry::Vacant(vacant_entry) => {
119                vacant_entry.insert(value);
120                None
121            }
122        }
123    }
124
125    pub fn get<Q: Eq + Hash + ?Sized>(&self, key: &Q) -> Option<&V>
126    where
127        K: Borrow<Q>,
128    {
129        let Self { map, order } = self;
130        let &idx = map.get(key)?;
131        let (k, v) = order.get(idx).unwrap();
132        debug_assert!(*k.borrow() == *key);
133        Some(v)
134    }
135
136    pub fn get_mut<Q: Eq + Hash + ?Sized>(&mut self, key: &Q) -> Option<&mut V>
137    where
138        K: Borrow<Q>,
139    {
140        let Self { map, order } = self;
141        let &idx = map.get(key)?;
142        let (k, v) = order.get_mut(idx).unwrap();
143        debug_assert!(*(*k).borrow() == *key);
144        Some(v)
145    }
146
147    pub fn contains_key<Q: Eq + Hash + ?Sized>(&self, key: &Q) -> bool
148    where
149        K: Borrow<Q>,
150    {
151        self.map.contains_key(key)
152    }
153
154    /// Removes `key` if present and returns its value, in O(1).
155    pub fn remove<Q: Eq + Hash + ?Sized>(&mut self, key: &Q) -> Option<V>
156    where
157        K: Borrow<Q>,
158    {
159        self.remove_entry(key).map(|(_, v)| v)
160    }
161
162    pub fn remove_entry<Q: Eq + Hash + ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
163    where
164        K: Borrow<Q>,
165    {
166        let Self { map, order } = self;
167        let idx = map.remove(key)?;
168        let (k_stored, v) = order.remove(idx).unwrap();
169        debug_assert!(*k_stored.borrow() == *key);
170        Some((k_stored, v))
171    }
172
173    pub fn pop_front(&mut self) -> Option<(K, V)> {
174        let Self { map, order } = self;
175        let (k, v) = order.remove_first()?;
176        map.remove(&k).unwrap();
177        Some((k, v))
178    }
179
180    pub fn pop_back(&mut self) -> Option<(K, V)> {
181        let Self { map, order } = self;
182        let (k, v) = order.remove_last()?;
183        map.remove(&k).unwrap();
184        Some((k, v))
185    }
186
187    pub fn clear(&mut self) {
188        let Self { map, order } = self;
189        map.clear();
190        order.clear();
191    }
192
193    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
194        let Self { map, order } = self;
195        let std_entry = map.entry(key);
196        Entry::new(std_entry, order)
197    }
198
199    pub fn shrink_to(&mut self, min_capacity: usize) {
200        let len = self.len();
201        let Self { map, order } = self;
202        map.shrink_to(min_capacity);
203        let min_capacity = min_capacity.max(len);
204        if min_capacity >= order.capacity() {
205            return;
206        }
207        let mut new_order = IndexList::with_capacity(min_capacity);
208        for (k, v) in order.drain_iter() {
209            let ind = new_order.insert_last((k, v));
210            let k = &new_order.get(ind).unwrap().0;
211            *map.get_mut(k).unwrap() = ind;
212        }
213        *order = new_order;
214    }
215
216    pub fn shrink_to_fit(&mut self) {
217        self.shrink_to(0);
218    }
219}
list_ordered_hashmap/lib.rs

list_ordered_hashmap/
lib.rs
