key_node_list/
list.rs

1use crate::cursor::{Cursor, CursorMut};
2use crate::iter::{IntoIter, IntoKeys, IntoNodes, Iter, Keys, Nodes};
3use crate::map::Map;
4use crate::node::Node;
5use crate::{node_next_mut, node_prev_mut};
6use std::borrow::Borrow;
7use std::collections::HashMap;
8use std::fmt;
9use std::hash::Hash;
10use std::iter::FromIterator;
11use std::marker::PhantomData;
12use std::ops::Index;
13
14/// A doubly-linked list that stores key-node pairs.
15#[derive(Clone)]
16pub struct KeyNodeList<K, N, M = HashMap<K, N>> {
17  pub(crate) nodes: M,
18  pub(crate) head: Option<K>,
19  pub(crate) tail: Option<K>,
20  phantom: PhantomData<N>,
21}
22
23impl<K, N, M> KeyNodeList<K, N, M>
24where
25  M: Default,
26{
27  /// Creates an empty linked list.
28  #[inline]
29  pub fn new() -> Self {
30    Self::default()
31  }
32}
33
34impl<K, N, M> KeyNodeList<K, N, M>
35where
36  M: Map<K, N>,
37{
38  /// Creates an linked list with the given hash map `map`.
39  #[inline]
40  pub fn with_map(map: M) -> Self {
41    Self {
42      nodes: map,
43      head: None,
44      tail: None,
45      phantom: PhantomData,
46    }
47  }
48
49  /// Returns a reference to the front key, or `None` if the list is empty.
50  ///
51  /// This operation should compute in *O*(1) time.
52  #[inline]
53  pub fn front_key(&self) -> Option<&K> {
54    self.head.as_ref()
55  }
56
57  /// Returns a reference to the back key, or `None` if the list is empty.
58  ///
59  /// This operation should compute in *O*(1) time.
60  #[inline]
61  pub fn back_key(&self) -> Option<&K> {
62    self.tail.as_ref()
63  }
64
65  /// Returns the number of key-node pairs in the list.
66  ///
67  /// This operation should compute in *O*(1) time.
68  #[inline]
69  pub fn len(&self) -> usize {
70    self.nodes.len()
71  }
72
73  /// Returns `true` if the list contains no key-node pairs.
74  ///
75  /// This operation should compute in *O*(1) time.
76  #[inline]
77  pub fn is_empty(&self) -> bool {
78    self.nodes.is_empty()
79  }
80
81  /// Removes all key-node pairs in the list.
82  #[inline]
83  pub fn clear(&mut self) {
84    self.nodes.clear();
85    self.head = None;
86    self.tail = None;
87  }
88
89  /// Returns an iterator over all keys and nodes.
90  /// The iterator element type is `(&'a K, &'a N)`.
91  #[inline]
92  pub fn iter(&self) -> Iter<'_, K, N, M> {
93    Iter {
94      list: self,
95      key: self.head.as_ref(),
96    }
97  }
98
99  /// Returns an iterator over all keys.
100  /// The iterator element type is `&'a K`.
101  #[inline]
102  pub fn keys(&self) -> Keys<'_, K, N, M> {
103    Keys { iter: self.iter() }
104  }
105
106  /// Returns an iterator over all nodes.
107  /// The iterator element type is `&'a N`.
108  #[inline]
109  pub fn nodes(&self) -> Nodes<'_, K, N, M> {
110    Nodes { iter: self.iter() }
111  }
112}
113
114impl<K, N, M> KeyNodeList<K, N, M>
115where
116  K: Hash + Eq,
117  M: Map<K, N>,
118{
119  /// Returns `true` if the linked list contains a node for the specified key.
120  ///
121  /// This operation should compute in *O*(1) time on average.
122  #[inline]
123  pub fn contains_key<Q>(&self, key: &Q) -> bool
124  where
125    K: Borrow<Q>,
126    Q: ?Sized + Hash + Eq,
127  {
128    self.nodes.contains_key(key)
129  }
130
131  /// Returns a reference to the node corresponding to the key,
132  /// or `None` if key does not exist.
133  ///
134  /// This operation should compute in *O*(1) time on average.
135  #[inline]
136  pub fn node<Q>(&self, key: &Q) -> Option<&N>
137  where
138    K: Borrow<Q>,
139    Q: ?Sized + Hash + Eq,
140  {
141    self.nodes.get(key)
142  }
143
144  /// Returns a mutable reference to the node corresponding to the key,
145  /// or `None` if key does not exist.
146  ///
147  /// This operation should compute in *O*(1) time on average.
148  #[inline]
149  pub fn node_mut<Q>(&mut self, key: &Q) -> Option<&mut N>
150  where
151    K: Borrow<Q>,
152    Q: ?Sized + Hash + Eq,
153  {
154    self.nodes.get_mut(key)
155  }
156
157  /// Returns a reference to the front node, or `None` if the list is empty.
158  ///
159  /// This operation should compute in *O*(1) time on average.
160  #[inline]
161  pub fn front_node(&self) -> Option<&N> {
162    self.head.as_ref().and_then(|k| self.nodes.get(k))
163  }
164
165  /// Returns a mutable reference to the front node,
166  /// or `None` if the list is empty.
167  ///
168  /// This operation should compute in *O*(1) time on average.
169  #[inline]
170  pub fn front_node_mut(&mut self) -> Option<&mut N> {
171    self.head.as_ref().and_then(|k| self.nodes.get_mut(k))
172  }
173
174  /// Returns a reference to the back node, or `None` if the list is empty.
175  ///
176  /// This operation should compute in *O*(1) time on average.
177  #[inline]
178  pub fn back_node(&self) -> Option<&N> {
179    self.tail.as_ref().and_then(|k| self.nodes.get(k))
180  }
181
182  /// Returns a mutable reference to the back node,
183  /// or `None` if the list is empty.
184  ///
185  /// This operation should compute in *O*(1) time on average.
186  #[inline]
187  pub fn back_node_mut(&mut self) -> Option<&mut N> {
188    self.tail.as_ref().and_then(|k| self.nodes.get_mut(k))
189  }
190
191  /// Provides a cursor at the specific key.
192  ///
193  /// The cursor is pointing to the null pair if the key does not exist.
194  #[inline]
195  pub fn cursor(&self, key: K) -> Cursor<'_, K, N, M> {
196    Cursor {
197      list: self,
198      key: self.contains_key(&key).then_some(key),
199    }
200  }
201
202  /// Provides a cursor with editing operations at the specific key.
203  ///
204  /// The cursor is pointing to the null pair if the key does not exist.
205  #[inline]
206  pub fn cursor_mut(&mut self, key: K) -> CursorMut<'_, K, N, M> {
207    CursorMut {
208      key: self.contains_key(&key).then_some(key),
209      list: self,
210    }
211  }
212}
213
214impl<K, N, M> KeyNodeList<K, N, M>
215where
216  K: Hash + Eq + Clone,
217  M: Map<K, N>,
218{
219  /// Provides a cursor at the front key-node pair.
220  ///
221  /// The cursor is pointing to the null pair if the list is empty.
222  #[inline]
223  pub fn cursor_front(&self) -> Cursor<'_, K, N, M> {
224    Cursor {
225      list: self,
226      key: self.head.clone(),
227    }
228  }
229
230  /// Provides a cursor with editing operations at the front key-node pair.
231  ///
232  /// The cursor is pointing to the null pair if the list is empty.
233  #[inline]
234  pub fn cursor_front_mut(&mut self) -> CursorMut<'_, K, N, M> {
235    CursorMut {
236      key: self.head.clone(),
237      list: self,
238    }
239  }
240
241  /// Provides a cursor at the back key-node pair.
242  ///
243  /// The cursor is pointing to the null pair if the list is empty.
244  #[inline]
245  pub fn cursor_back(&self) -> Cursor<'_, K, N, M> {
246    Cursor {
247      list: self,
248      key: self.tail.clone(),
249    }
250  }
251
252  /// Provides a cursor with editing operations at the back key-node pair.
253  ///
254  /// The cursor is pointing to the null pair if the list is empty.
255  #[inline]
256  pub fn cursor_back_mut(&mut self) -> CursorMut<'_, K, N, M> {
257    CursorMut {
258      key: self.tail.clone(),
259      list: self,
260    }
261  }
262}
263
264impl<K, N, M> KeyNodeList<K, N, M>
265where
266  K: Hash + Eq + Clone,
267  N: Node<Key = K>,
268  M: Map<K, N>,
269{
270  /// Creates a consuming iterator over all keys.
271  /// The list cannot be used after calling this.
272  /// The iterator element type is `K`.
273  #[inline]
274  pub fn into_keys(self) -> IntoKeys<K, N, M> {
275    IntoKeys {
276      iter: self.into_iter(),
277    }
278  }
279
280  /// Creates a consuming iterator over all nodes.
281  /// The list cannot be used after calling this.
282  /// The iterator element type is `N`.
283  #[inline]
284  pub fn into_nodes(self) -> IntoNodes<K, N, M> {
285    IntoNodes {
286      iter: self.into_iter(),
287    }
288  }
289
290  /// Adds a key-node pair first in the list.
291  ///
292  /// If `key` already exists, returns an error containing `key` and `node`.
293  ///
294  /// This operation should compute in *O*(1) time on average.
295  pub fn push_front<T: Into<N>>(&mut self, key: K, node: T) -> Result<(), (K, T)> {
296    self.nodes.insert(key.clone(), node).map(|_| {
297      let next = self.head.replace(key.clone());
298      match &next {
299        Some(k) => *node_prev_mut!(self, k) = Some(key.clone()),
300        None => self.tail = Some(key.clone()),
301      }
302      let node = self.node_mut(&key).unwrap();
303      *node_prev_mut!(node) = None;
304      *node_next_mut!(node) = next;
305    })
306  }
307
308  /// Adds a key-node pair back in the list.
309  ///
310  /// If `key` already exists, returns an error containing `key` and `node`.
311  ///
312  /// This operation should compute in *O*(1) time on average.
313  pub fn push_back<T: Into<N>>(&mut self, key: K, node: T) -> Result<(), (K, T)> {
314    self.nodes.insert(key.clone(), node).map(|_| {
315      let prev = self.tail.replace(key.clone());
316      match &prev {
317        Some(k) => *node_next_mut!(self, k) = Some(key.clone()),
318        None => self.head = Some(key.clone()),
319      }
320      let node = self.node_mut(&key).unwrap();
321      *node_prev_mut!(node) = prev;
322      *node_next_mut!(node) = None;
323    })
324  }
325
326  /// Adds a key first in the list.
327  ///
328  /// If `key` already exists, returns an error containing `key`.
329  ///
330  /// This operation should compute in *O*(1) time on average.
331  #[inline]
332  pub fn push_key_front(&mut self, key: K) -> Result<(), K>
333  where
334    (): Into<N>,
335  {
336    self.push_front(key, ()).map_err(|(k, _)| k)
337  }
338
339  /// Adds a key back in the list.
340  ///
341  /// If `key` already exists, returns an error containing `key`.
342  ///
343  /// This operation should compute in *O*(1) time on average.
344  #[inline]
345  pub fn push_key_back(&mut self, key: K) -> Result<(), K>
346  where
347    (): Into<N>,
348  {
349    self.push_back(key, ()).map_err(|(k, _)| k)
350  }
351
352  /// Removes the first key-node pair and returns it, or `None` if the list
353  /// is empty.
354  ///
355  /// This operation should compute in *O*(1) time on average.
356  pub fn pop_front(&mut self) -> Option<(K, N)> {
357    self.head.take().map(|k| {
358      let node = self.nodes.remove(&k).unwrap();
359      self.head = node.next().cloned();
360      (k, node)
361    })
362  }
363
364  /// Removes the last key-node pair and returns it, or `None` if the list
365  /// is empty.
366  ///
367  /// This operation should compute in *O*(1) time on average.
368  pub fn pop_back(&mut self) -> Option<(K, N)> {
369    self.tail.take().map(|k| {
370      let node = self.nodes.remove(&k).unwrap();
371      self.tail = node.prev().cloned();
372      (k, node)
373    })
374  }
375
376  /// Removes the key-node pair at the given key and returns it,
377  /// or returns `None` if `key` does not exists.
378  pub fn remove<Q>(&mut self, key: &Q) -> Option<(K, N)>
379  where
380    K: Borrow<Q>,
381    Q: ?Sized + Hash + Eq,
382  {
383    self.nodes.remove_entry(key).map(|(k, n)| {
384      match n.prev() {
385        Some(k) => *node_next_mut!(self, k) = n.next().cloned(),
386        None => self.head = n.next().cloned(),
387      }
388      match n.next() {
389        Some(k) => *node_prev_mut!(self, k) = n.prev().cloned(),
390        None => self.tail = n.prev().cloned(),
391      }
392      (k, n)
393    })
394  }
395}
396
397impl<K, N, M> fmt::Debug for KeyNodeList<K, N, M>
398where
399  K: Hash + Eq + fmt::Debug,
400  N: Node<Key = K> + fmt::Debug,
401  M: Map<K, N>,
402{
403  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
404    f.debug_list().entries(self).finish()
405  }
406}
407
408impl<K, N, M> Default for KeyNodeList<K, N, M>
409where
410  M: Default,
411{
412  #[inline]
413  fn default() -> Self {
414    KeyNodeList {
415      nodes: M::default(),
416      head: None,
417      tail: None,
418      phantom: PhantomData,
419    }
420  }
421}
422
423impl<'a, K, T, N, M> Extend<(&'a K, &'a T)> for KeyNodeList<K, N, M>
424where
425  K: Eq + Hash + Copy,
426  T: Into<N> + Copy,
427  N: Node<Key = K> + Copy,
428  M: Map<K, N>,
429{
430  fn extend<I: IntoIterator<Item = (&'a K, &'a T)>>(&mut self, iter: I) {
431    self.extend(iter.into_iter().map(|(k, n)| (*k, *n)))
432  }
433}
434
435impl<'a, K: 'a, N, M> Extend<&'a K> for KeyNodeList<K, N, M>
436where
437  K: Eq + Hash + Copy,
438  (): Into<N>,
439  N: Node<Key = K> + Copy,
440  M: Map<K, N>,
441{
442  /// Extends a `KeyNodeList` with an key iterator
443  /// if the node can be built with a `()`.
444  ///
445  /// # Example
446  ///
447  /// ```
448  /// use key_node_list::KeyValueList;
449  ///
450  /// let mut list: KeyValueList<i32, ()> = KeyValueList::new();
451  /// list.extend(&[1, 2, 3]);
452  /// assert_eq!(list.front_key(), Some(&1));
453  /// assert_eq!(list.back_key(), Some(&3));
454  /// ```
455  fn extend<I: IntoIterator<Item = &'a K>>(&mut self, iter: I) {
456    self.extend(iter.into_iter().copied())
457  }
458}
459
460impl<K, T, N, M> Extend<(K, T)> for KeyNodeList<K, N, M>
461where
462  K: Eq + Hash + Clone,
463  T: Into<N>,
464  N: Node<Key = K>,
465  M: Map<K, N>,
466{
467  fn extend<I: IntoIterator<Item = (K, T)>>(&mut self, iter: I) {
468    iter.into_iter().for_each(|(k, n)| {
469      let _ = self.push_back(k, n);
470    });
471  }
472}
473
474impl<K, N, M> Extend<K> for KeyNodeList<K, N, M>
475where
476  K: Eq + Hash + Clone,
477  (): Into<N>,
478  N: Node<Key = K>,
479  M: Map<K, N>,
480{
481  /// Extends a `KeyNodeList` with an key iterator
482  /// if the node can be built with a `()`.
483  ///
484  /// # Example
485  ///
486  /// ```
487  /// use key_node_list::KeyValueList;
488  ///
489  /// let mut list: KeyValueList<i32, ()> = KeyValueList::new();
490  /// list.extend([1, 2, 3]);
491  /// assert_eq!(list.front_key(), Some(&1));
492  /// assert_eq!(list.back_key(), Some(&3));
493  /// ```
494  fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
495    iter.into_iter().for_each(|k| {
496      let _ = self.push_key_back(k);
497    });
498  }
499}
500
501impl<K, T, N, M, const LEN: usize> From<[(K, T); LEN]> for KeyNodeList<K, N, M>
502where
503  K: Eq + Hash + Clone,
504  T: Into<N>,
505  N: Node<Key = K>,
506  M: Map<K, N> + Default,
507{
508  fn from(arr: [(K, T); LEN]) -> Self {
509    IntoIterator::into_iter(arr).collect()
510  }
511}
512
513impl<K, T, N, M> FromIterator<(K, T)> for KeyNodeList<K, N, M>
514where
515  K: Eq + Hash + Clone,
516  T: Into<N>,
517  N: Node<Key = K>,
518  M: Map<K, N> + Default,
519{
520  fn from_iter<I: IntoIterator<Item = (K, T)>>(iter: I) -> Self {
521    let mut list = Self::new();
522    list.extend(iter);
523    list
524  }
525}
526
527impl<K, N, M> FromIterator<K> for KeyNodeList<K, N, M>
528where
529  K: Eq + Hash + Clone,
530  (): Into<N>,
531  N: Node<Key = K>,
532  M: Map<K, N> + Default,
533{
534  /// Creates a `KeyNodeList` from an key iterator
535  /// if the node can be built with a `()`.
536  ///
537  /// # Example
538  ///
539  /// ```
540  /// use key_node_list::KeyValueList;
541  ///
542  /// let list: KeyValueList<i32, ()> = [1, 2, 3].into_iter().collect();
543  /// assert_eq!(list.front_key(), Some(&1));
544  /// assert_eq!(list.back_key(), Some(&3));
545  /// ```
546  fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
547    let mut list = Self::new();
548    list.extend(iter);
549    list
550  }
551}
552
553impl<'a, K, Q, N, M> Index<&'a Q> for KeyNodeList<K, N, M>
554where
555  K: Hash + Eq + Borrow<Q>,
556  Q: ?Sized + Hash + Eq,
557  M: Map<K, N>,
558{
559  type Output = N;
560
561  /// Returns a reference to the value corresponding to the supplied key.
562  ///
563  /// # Panics
564  ///
565  /// Panics if the key is not present in the [`KeyNodeList`].
566  #[inline]
567  fn index(&self, key: &'a Q) -> &Self::Output {
568    self.nodes.get(key).expect("no entry found for key")
569  }
570}
571
572impl<K, N, M> IntoIterator for KeyNodeList<K, N, M>
573where
574  K: Hash + Eq + Clone,
575  N: Node<Key = K>,
576  M: Map<K, N>,
577{
578  type Item = (K, N);
579  type IntoIter = IntoIter<K, N, M>;
580
581  fn into_iter(self) -> Self::IntoIter {
582    IntoIter { list: self }
583  }
584}
585
586impl<'a, K, N, M> IntoIterator for &'a KeyNodeList<K, N, M>
587where
588  K: Hash + Eq,
589  N: Node<Key = K>,
590  M: Map<K, N>,
591{
592  type Item = (&'a K, &'a N);
593  type IntoIter = Iter<'a, K, N, M>;
594
595  fn into_iter(self) -> Self::IntoIter {
596    self.iter()
597  }
598}
599
600impl<K, N, M> PartialEq<KeyNodeList<K, N, M>> for KeyNodeList<K, N, M>
601where
602  M: PartialEq,
603{
604  fn eq(&self, other: &KeyNodeList<K, N, M>) -> bool {
605    self.nodes == other.nodes
606  }
607}
608
609impl<K, N, M> Eq for KeyNodeList<K, N, M> where M: PartialEq {}
key_node_list/list.rs

key_node_list/
list.rs
