key_node_list/
lib.rs

1//! Doubly-linked list that stores key-node pairs.
2//!
3//! [`KeyNodeList`] is a doubly-linked list, it uses a hash map to maintain
4//! correspondence between keys and nodes, and records the previous key and
5//! the next key of the current node in the node itself. There is no pointer
6//! operations during this process, so `key_node_list` is all implemented in
7//! safe Rust.
8//!
9//! You can complete key lookups, key-node pair updates, key-node pair
10//! deletions and other operations of [`KeyNodeList`] in *O*(1)~ time. You
11//! can also use cursor-based interface to traverse or edit the linked list.
12//!
13//! # Examples
14//!
15//! ## Organizing key-value pairs using `KeyValueList`
16//!
17//! ```
18//! use key_node_list::KeyValueList;
19//!
20//! // construct key-value list from tuple array
21//! let mut list = KeyValueList::from([(1, "Reimu"), (2, "Marisa")]);
22//!
23//! // or pushing other key-value pairs to the front/back of list
24//! list.push_front(0, "Alice").unwrap();
25//! list.push_back(3, "Patchouli").unwrap();
26//!
27//! // query nodes by key
28//! assert_eq!(list[&1].value(), &"Reimu");
29//! assert_eq!(list[&0].value(), &"Alice");
30//!
31//! // also you can update nodes by key
32//! *list.node_mut(&3).unwrap().value_mut() = "Youmu";
33//! *list.front_node_mut().unwrap().value_mut() = "Mokou";
34//! assert_eq!(list[&3].value(), &"Youmu");
35//! assert_eq!(list[&0].value(), &"Mokou");
36//! assert_eq!(list.front_node().unwrap().value(), &"Mokou");
37//!
38//! // remove some key-node pairs
39//! assert!(list.pop_front().is_some());
40//! assert!(list.remove(&2).is_some());
41//!
42//! // all key-node pairs are in order
43//! list.push_back(5, "Yuyuko");
44//! let vec: Vec<_> = list.into_iter().map(|(k, n)| (k, n.into_value())).collect();
45//! assert_eq!(vec, [(1, "Reimu"), (3, "Youmu"), (5, "Yuyuko")]);
46//! ```
47//!
48//! ## Editing list using cursors
49//!
50//! ```
51//! use key_node_list::KeyValueList;
52//!
53//! let mut first_name = KeyValueList::from([
54//!   (1, "Reimu".to_string()),
55//!   (2, "Marisa".to_string()),
56//! ]);
57//!
58//! let last_name = KeyValueList::from([(1, "Hakurei"), (2, "Kirisame")]);
59//!
60//! // append last names after first names
61//! let mut first_cur = first_name.cursor_front_mut();
62//! let mut last_cur = last_name.cursor_front();
63//! while let Some(node) = first_cur.node_mut() {
64//!   node.value_mut().push(' ');
65//!   node.value_mut().push_str(last_cur.node().unwrap().value());
66//!   first_cur.move_next();
67//!   last_cur.move_next();
68//! }
69//!
70//! let vec: Vec<_> = first_name.iter().map(|(k, n)| (k, n.value().as_str())).collect();
71//! assert_eq!(vec, [(&1, "Reimu Hakurei"), (&2, "Marisa Kirisame")]);
72//! ```
73//!
74//! ## Customizing your own nodes
75//!
76//! ```
77//! use key_node_list::{Node, impl_node};
78//! use key_node_list::KeyNodeList;
79//!
80//! struct NameNode<'a> {
81//!   first: &'a str,
82//!   last: &'a str,
83//!   prev: Option<i32>,
84//!   next: Option<i32>,
85//! }
86//!
87//! impl<'a> From<(&'a str, &'a str)> for NameNode<'a> {
88//!   fn from(name: (&'a str, &'a str)) -> Self {
89//!     let (first, last) = name;
90//!     Self {
91//!       first,
92//!       last,
93//!       prev: None,
94//!       next: None,
95//!     }
96//!   }
97//! }
98//!
99//! // implements `Node` trait for `NameNode`
100//! impl_node!(NameNode<'a> { Key = i32, prev = prev, next = next });
101//!
102//! // create a `KeyNodeList` with node type `NameNode`
103//! let mut names: KeyNodeList<_, NameNode> = KeyNodeList::new();
104//! names.push_back(1, ("Reimu", "Hakurei"));
105//! names.push_back(2, ("Marisa", "Kirisame"));
106//! assert_eq!(names[&1].first, "Reimu");
107//! assert_eq!(names[&2].last, "Kirisame");
108//! ```
109
110mod cursor;
111mod iter;
112mod list;
113mod map;
114mod node;
115
116pub use cursor::*;
117pub use iter::*;
118pub use list::*;
119pub use map::*;
120pub use node::*;
121
122/// A [`KeyNodeList`] that uses [`ValueNode<K, V>`] as its node type and
123/// [`HashMap`](std::collections::HashMap) as its underlying hash map.
124///
125/// `KeyValueList` stores key-value pairs and organize them in the form of
126/// a doubly-linked list.
127pub type KeyValueList<K, V> = KeyNodeList<K, ValueNode<K, V>>;
128
129/// Gets a mutable reference of the previous pointer of the specific node.
130macro_rules! node_prev_mut {
131  ($list:expr, $key:expr) => {
132    $list
133      .node_mut::<K>($key)
134      .unwrap()
135      .prev_mut::<$crate::node::Token>()
136  };
137  ($node:expr) => {
138    $node.prev_mut::<$crate::node::Token>()
139  };
140}
141pub(crate) use node_prev_mut;
142
143/// Gets a mutable reference of the next pointer of the specific node.
144macro_rules! node_next_mut {
145  ($list:expr, $key:expr) => {
146    $list
147      .node_mut::<K>($key)
148      .unwrap()
149      .next_mut::<$crate::node::Token>()
150  };
151  ($node:expr) => {
152    $node.next_mut::<$crate::node::Token>()
153  };
154}
155pub(crate) use node_next_mut;
156
157#[cfg(test)]
158mod test {
159  use super::*;
160
161  #[test]
162  fn test_capacity() {
163    let mut list = KeyValueList::new();
164    assert_eq!(list.front_key(), None);
165    assert_eq!(list.back_key(), None);
166    assert_eq!(list.len(), 0);
167    assert!(list.is_empty());
168    list.push_back(1, 1).unwrap();
169    assert_eq!(list.front_key(), Some(&1));
170    assert_eq!(list.back_key(), Some(&1));
171    assert_eq!(list.len(), 1);
172    assert!(!list.is_empty());
173    list.push_back(2, 2).unwrap();
174    assert_eq!(list.front_key(), Some(&1));
175    assert_eq!(list.back_key(), Some(&2));
176    assert_eq!(list.len(), 2);
177    assert!(!list.is_empty());
178    list.clear();
179    assert_eq!(list.front_key(), None);
180    assert_eq!(list.back_key(), None);
181    assert_eq!(list.len(), 0);
182    assert!(list.is_empty());
183  }
184
185  #[test]
186  fn test_push_into_iter() {
187    let mut list = KeyValueList::new();
188    for i in 0..10 {
189      list.push_back(i, i).unwrap();
190    }
191    let vec = list.into_iter().collect::<Vec<_>>();
192    assert_eq!(vec.len(), 10);
193    for (i, (k, n)) in vec.into_iter().enumerate() {
194      assert_eq!(i as i32, k);
195      assert_eq!(i as i32, n.into_value());
196    }
197  }
198
199  #[test]
200  fn test_push_pop() {
201    let mut list = KeyValueList::new();
202    assert_eq!(list.pop_back(), None);
203    assert_eq!(list.pop_front(), None);
204    for i in 0..10 {
205      list.push_back(i, i).unwrap();
206    }
207    let mut cur = 9;
208    while let Some((k, n)) = list.pop_back() {
209      assert_eq!(cur, k);
210      assert_eq!(cur, n.into_value());
211      cur -= 1;
212    }
213    assert_eq!(cur, -1);
214  }
215
216  #[test]
217  fn test_push_front_iter() {
218    let mut list = KeyValueList::new();
219    for i in 0..10 {
220      list.push_front(i, i * 2).unwrap();
221    }
222    for (i, (k, n)) in list.iter().enumerate() {
223      assert_eq!(9 - i, *k);
224      assert_eq!((9 - i) * 2, *n.value());
225    }
226    for (i, k) in list.keys().enumerate() {
227      assert_eq!(9 - i, *k);
228    }
229    for (i, n) in list.nodes().enumerate() {
230      assert_eq!((9 - i) * 2, *n.value());
231    }
232  }
233
234  #[test]
235  fn test_cursor_move() {
236    let mut list = KeyValueList::new();
237    for i in 0..10 {
238      list.push_front(i, i * 2).unwrap();
239    }
240    let mut cur = list.cursor_back();
241    assert_eq!(cur.key(), Some(&0));
242    cur.move_prev();
243    assert_eq!(cur.key(), Some(&1));
244    dbg!(cur.key());
245    dbg!(cur.node());
246    assert_eq!(cur.next_key(), Some(&0));
247    cur.move_next();
248    assert_eq!(cur.key(), Some(&0));
249    cur.move_next();
250    assert_eq!(cur.key(), None);
251    cur.move_next();
252    assert_eq!(cur.key(), Some(&9));
253  }
254
255  #[test]
256  fn test_cursor_insert_remove() {
257    let mut list = KeyValueList::new();
258    for i in 0..10 {
259      list.push_back(i * 10, i * 10).unwrap();
260    }
261    let mut cur = list.cursor_front_mut();
262    while cur.key() != Some(&40) {
263      cur.move_next();
264    }
265    cur.insert_before(37, 37).unwrap();
266    cur.insert_before(38, 38).unwrap();
267    cur.insert_before(39, 39).unwrap();
268    cur.insert_after(42, 42).unwrap();
269    cur.insert_after(41, 41).unwrap();
270    for i in 0..3 {
271      assert_eq!(
272        cur.remove_current().map(|(k, n)| (k, n.into_value())),
273        Some((40 + i, 40 + i))
274      );
275    }
276    assert_eq!(cur.key(), Some(&50));
277    for i in 0..3 {
278      cur.move_prev();
279      assert_eq!(
280        cur.remove_current().map(|(k, n)| (k, n.into_value())),
281        Some((39 - i, 39 - i))
282      );
283    }
284    assert_eq!(cur.prev_key(), Some(&30));
285  }
286
287  #[test]
288  fn test_from_eq() {
289    let list1 = KeyValueList::from([(1, 1), (2, 2), (3, 3)]);
290    let list2 = KeyValueList::from([(1, 1), (2, 2), (3, 3)]);
291    let list3 = KeyValueList::from([(1, 1), (2, 2), (3, 4)]);
292    let list4: KeyValueList<i32, i32> = [(1, 1), (2, 2), (3, 4)].into_iter().collect();
293    let list5: KeyValueList<i32, ()> = [1, 2, 3].into_iter().collect();
294    let mut list6: KeyValueList<i32, ()> = KeyValueList::new();
295    list6.extend([1, 2, 3]);
296    assert_eq!(list1, list2);
297    assert_ne!(list1, list3);
298    assert_eq!(list3, list4);
299    assert_eq!(list5, list6);
300  }
301}
key_node_list/lib.rs

key_node_list/
lib.rs
