1 // A simple doubly linked list example using slotmap.
2
3 use slotmap::{new_key_type, Key, SlotMap};
4
5 new_key_type! {
6 pub struct ListKey;
7 }
8
9 #[derive(Copy, Clone)]
10 struct Node<T> {
11 value: T,
12 prev: ListKey,
13 next: ListKey,
14 }
15
16 pub struct List<T> {
17 sm: SlotMap<ListKey, Node<T>>,
18 head: ListKey,
19 tail: ListKey,
20 }
21
22 impl<T> List<T> {
new() -> Self23 pub fn new() -> Self {
24 Self {
25 sm: SlotMap::with_key(),
26 head: ListKey::null(),
27 tail: ListKey::null(),
28 }
29 }
30
len(&self) -> usize31 pub fn len(&self) -> usize {
32 self.sm.len()
33 }
34
push_head(&mut self, value: T) -> ListKey35 pub fn push_head(&mut self, value: T) -> ListKey {
36 let k = self.sm.insert(Node {
37 value,
38 prev: ListKey::null(),
39 next: self.head,
40 });
41
42 if let Some(old_head) = self.sm.get_mut(self.head) {
43 old_head.prev = k;
44 } else {
45 self.tail = k;
46 }
47 self.head = k;
48 k
49 }
50
push_tail(&mut self, value: T) -> ListKey51 pub fn push_tail(&mut self, value: T) -> ListKey {
52 let k = self.sm.insert(Node {
53 value,
54 prev: self.tail,
55 next: ListKey::null(),
56 });
57
58 if let Some(old_tail) = self.sm.get_mut(self.tail) {
59 old_tail.next = k;
60 } else {
61 self.head = k;
62 }
63 self.tail = k;
64 k
65 }
66
pop_head(&mut self) -> Option<T>67 pub fn pop_head(&mut self) -> Option<T> {
68 self.sm.remove(self.head).map(|old_head| {
69 self.head = old_head.next;
70 old_head.value
71 })
72 }
73
pop_tail(&mut self) -> Option<T>74 pub fn pop_tail(&mut self) -> Option<T> {
75 self.sm.remove(self.tail).map(|old_tail| {
76 self.tail = old_tail.prev;
77 old_tail.value
78 })
79 }
80
remove(&mut self, key: ListKey) -> Option<T>81 pub fn remove(&mut self, key: ListKey) -> Option<T> {
82 self.sm.remove(key).map(|node| {
83 if let Some(prev_node) = self.sm.get_mut(node.prev) {
84 prev_node.next = node.next;
85 } else {
86 self.head = node.next;
87 }
88
89 if let Some(next_node) = self.sm.get_mut(node.next) {
90 next_node.prev = node.prev;
91 } else {
92 self.tail = node.prev;
93 }
94
95 node.value
96 })
97 }
98
head(&self) -> ListKey99 pub fn head(&self) -> ListKey {
100 self.head
101 }
102
tail(&self) -> ListKey103 pub fn tail(&self) -> ListKey {
104 self.tail
105 }
106
get(&self, key: ListKey) -> Option<&T>107 pub fn get(&self, key: ListKey) -> Option<&T> {
108 self.sm.get(key).map(|node| &node.value)
109 }
110
get_mut(&mut self, key: ListKey) -> Option<&mut T>111 pub fn get_mut(&mut self, key: ListKey) -> Option<&mut T> {
112 self.sm.get_mut(key).map(|node| &mut node.value)
113 }
114 }
115
main()116 fn main() {
117 let mut dll = List::new();
118 dll.push_head(5);
119 dll.push_tail(6);
120 let k = dll.push_head(3);
121 dll.push_tail(7);
122 dll.push_head(4);
123
124 assert_eq!(dll.len(), 4);
125 assert_eq!(dll.pop_head(), Some(4));
126 assert_eq!(dll.pop_head(), Some(5));
127 assert_eq!(dll.head(), k);
128 dll.push_head(10);
129 assert_eq!(dll.remove(k), Some(3));
130 assert_eq!(dll.pop_tail(), Some(7));
131 assert_eq!(dll.pop_tail(), Some(6));
132 assert_eq!(dll.pop_head(), Some(10));
133 assert_eq!(dll.pop_head(), None);
134 assert_eq!(dll.pop_tail(), None);
135 }
136