streaming_algorithms/
linked_list.rs1use serde::{Deserialize, Serialize};
2use std::{iter, marker, ops};
3
4#[derive(Copy, Clone, PartialEq, Eq, Serialize, Deserialize, Debug)]
5pub struct LinkedListIndex<'a>(usize, marker::PhantomData<&'a ()>);
6impl<'a> LinkedListIndex<'a> {
7 #[inline(always)]
8 pub unsafe fn staticify(self) -> LinkedListIndex<'static> {
9 LinkedListIndex(self.0, marker::PhantomData)
10 }
11}
12
13#[derive(Clone, Serialize, Deserialize)]
14pub struct LinkedList<T> {
15 vec: Box<[(usize, usize, Option<T>)]>,
16 head: usize,
17 tail: usize,
18 free: usize,
19 len: usize,
20}
21impl<T> LinkedList<T> {
22 pub fn new(cap: usize) -> Self {
23 let vec = if cap >= 2 {
24 iter::once((usize::max_value(), 1, None))
25 .chain((1..cap - 1).map(|i| (i - 1, i + 1, None)))
26 .chain(iter::once((cap - 2, usize::max_value(), None)))
27 .collect::<Vec<_>>()
28 } else {
29 (0..cap)
30 .map(|_| (usize::max_value(), usize::max_value(), None))
31 .collect::<Vec<_>>()
32 }
33 .into_boxed_slice();
34 let ret = Self {
35 vec,
36 head: usize::max_value(),
37 tail: usize::max_value(),
38 free: 0,
39 len: 0,
40 };
41 ret.assert();
42 ret
43 }
44 fn assert(&self) {
45 if !cfg!(feature = "assert") {
46 return;
47 }
48 let mut len = 0;
49 {
50 let mut cur = self.head;
51 while cur != usize::max_value() {
52 assert!(self.vec[cur].2.is_some());
53 let next = self.vec[cur].1;
54 if next != usize::max_value() {
55 assert_eq!(self.vec[next].0, cur);
56 } else {
57 assert_eq!(self.tail, cur);
58 }
59 cur = next;
60 len += 1;
61 }
62 }
63 assert_eq!(self.len, len);
64 let mut len_free = 0;
65 {
66 let mut cur = self.free;
67 while cur != usize::max_value() {
68 assert!(!self.vec[cur].2.is_some());
69 let next = self.vec[cur].1;
70 if next != usize::max_value() {
71 assert_eq!(self.vec[next].0, cur);
72 }
73 cur = next;
74 len_free += 1;
75 }
76 }
77 assert_eq!(len + len_free, self.vec.len());
78 }
79 #[inline(always)]
80 fn alloc(&mut self) -> usize {
81 let free = self.free;
82 assert_ne!(free, usize::max_value());
83 self.free = self.vec[free].1;
84 if self.free != usize::max_value() {
85 self.vec[self.free].0 = usize::max_value();
86 }
87 free
88 }
89 #[inline(always)]
90 fn free(&mut self, idx: usize) {
91 if self.free != usize::max_value() {
92 self.vec[self.free].0 = idx;
93 }
94 self.vec[idx].0 = usize::max_value();
95 self.vec[idx].1 = self.free;
96 self.free = idx;
97 }
98 #[inline(always)]
99 pub fn head(&self) -> Option<LinkedListIndex> {
100 if self.head != usize::max_value() {
101 Some(LinkedListIndex(self.head, marker::PhantomData))
102 } else {
103 None
104 }
105 }
106 #[inline(always)]
107 pub fn tail(&self) -> Option<LinkedListIndex> {
108 if self.tail != usize::max_value() {
109 Some(LinkedListIndex(self.tail, marker::PhantomData))
110 } else {
111 None
112 }
113 }
114 #[inline(always)]
115 pub fn len(&self) -> usize {
116 self.len
117 }
118 #[inline(always)]
119 pub fn capacity(&self) -> usize {
120 self.vec.len()
121 }
122 pub fn push_back(&mut self, t: T) -> LinkedListIndex {
123 let idx = self.alloc();
124 self.vec[idx] = (self.tail, usize::max_value(), Some(t));
125 if self.tail != usize::max_value() {
126 self.vec[self.tail].1 = idx;
127 } else {
128 self.head = idx;
129 }
130 self.tail = idx;
131 self.len += 1;
132 self.assert();
133 LinkedListIndex(idx, marker::PhantomData)
134 }
135 pub fn push_front(&mut self, t: T) -> LinkedListIndex {
136 let idx = self.alloc();
137 self.vec[idx] = (usize::max_value(), self.head, Some(t));
138 if self.head != usize::max_value() {
139 self.vec[self.head].0 = idx;
140 } else {
141 self.tail = idx;
142 }
143 self.head = idx;
144 self.len += 1;
145 self.assert();
146 LinkedListIndex(idx, marker::PhantomData)
147 }
148 pub fn pop_back(&mut self) -> T {
149 assert_ne!(self.len, 0);
150 let idx = self.tail;
151 let ret = self.vec[idx].2.take().unwrap();
152 self.tail = self.vec[idx].0;
153 if self.tail != usize::max_value() {
154 self.vec[self.tail].1 = usize::max_value();
155 } else {
156 self.head = usize::max_value();
157 }
158 self.free(idx);
159 self.len -= 1;
160 self.assert();
161 ret
162 }
163 pub fn pop_front(&mut self) -> T {
164 assert_ne!(self.len, 0);
165 let idx = self.head;
166 let ret = self.vec[idx].2.take().unwrap();
167 self.head = self.vec[idx].1;
168 if self.head != usize::max_value() {
169 self.vec[self.head].0 = usize::max_value();
170 } else {
171 self.tail = usize::max_value();
172 }
173 self.free(idx);
174 self.len -= 1;
175 self.assert();
176 ret
177 }
178 pub fn insert_after(&mut self, index: LinkedListIndex, t: T) -> LinkedListIndex {
179 let idx = self.alloc();
180 let next = self.vec[index.0].1;
181 self.vec[idx] = (index.0, next, Some(t));
182 self.vec[index.0].1 = idx;
183 if next != usize::max_value() {
184 self.vec[next].0 = idx;
185 } else {
186 self.tail = idx;
187 }
188 self.len += 1;
189 self.assert();
190 LinkedListIndex(idx, marker::PhantomData)
191 }
192 pub fn insert_before(&mut self, index: LinkedListIndex, t: T) -> LinkedListIndex {
193 let idx = self.alloc();
194 let prev = self.vec[index.0].0;
195 self.vec[idx] = (prev, index.0, Some(t));
196 self.vec[index.0].0 = idx;
197 if prev != usize::max_value() {
198 self.vec[prev].1 = idx;
199 } else {
200 self.head = idx;
201 }
202 self.len += 1;
203 self.assert();
204 LinkedListIndex(idx, marker::PhantomData)
205 }
206 pub fn remove(&mut self, index: LinkedListIndex) -> T {
207 let prev = self.vec[index.0].0;
208 let next = self.vec[index.0].1;
209 if prev != usize::max_value() {
210 self.vec[prev].1 = next;
211 } else {
212 self.head = next;
213 }
214 if next != usize::max_value() {
215 self.vec[next].0 = prev;
216 } else {
217 self.tail = prev;
218 }
219 let ret = self.vec[index.0].2.take().unwrap();
220 self.free(index.0);
221 self.len -= 1;
222 self.assert();
223 ret
224 }
225 pub fn move_after(&mut self, from: LinkedListIndex, to: LinkedListIndex) {
226 assert_ne!(from.0, to.0);
227 let prev = self.vec[from.0].0;
228 let next = self.vec[from.0].1;
229 if prev != usize::max_value() {
230 self.vec[prev].1 = next;
231 } else {
232 self.head = next;
233 }
234 if next != usize::max_value() {
235 self.vec[next].0 = prev;
236 } else {
237 self.tail = prev;
238 }
239
240 let next2 = self.vec[to.0].1;
241 self.vec[from.0].0 = to.0;
242 self.vec[from.0].1 = next2;
243 self.vec[to.0].1 = from.0;
244 if next2 != usize::max_value() {
245 self.vec[next2].0 = from.0;
246 } else {
247 self.tail = from.0;
248 }
249 self.assert();
250 }
251 pub fn move_before(&mut self, from: LinkedListIndex, to: LinkedListIndex) {
252 assert_ne!(from.0, to.0);
253 let prev = self.vec[from.0].0;
254 let next = self.vec[from.0].1;
255 if prev != usize::max_value() {
256 self.vec[prev].1 = next;
257 } else {
258 self.head = next;
259 }
260 if next != usize::max_value() {
261 self.vec[next].0 = prev;
262 } else {
263 self.tail = prev;
264 }
265
266 let prev2 = self.vec[to.0].0;
267 self.vec[from.0].0 = prev2;
268 self.vec[from.0].1 = to.0;
269 self.vec[to.0].0 = from.0;
270 if prev2 != usize::max_value() {
271 self.vec[prev2].1 = from.0;
272 } else {
273 self.head = from.0;
274 }
275 self.assert();
276 }
277 #[inline(always)]
278 pub fn increment(&self, index: &mut LinkedListIndex) {
279 index.0 = self.vec[index.0].1;
280 assert_ne!(index.0, usize::max_value());
281 }
282 #[inline(always)]
283 pub fn decrement(&self, index: &mut LinkedListIndex) {
284 index.0 = self.vec[index.0].0;
285 assert_ne!(index.0, usize::max_value());
286 }
287 pub fn clear(&mut self) {
288 while self.len() != 0 {
289 let _ = self.pop_back();
290 }
291 }
292}
293impl<'a, T> ops::Index<LinkedListIndex<'a>> for LinkedList<T> {
294 type Output = T;
295 #[inline(always)]
296 fn index(&self, index: LinkedListIndex) -> &T {
297 self.vec[index.0].2.as_ref().unwrap()
298 }
299}
300impl<'a, T> ops::IndexMut<LinkedListIndex<'a>> for LinkedList<T> {
301 #[inline(always)]
302 fn index_mut(&mut self, index: LinkedListIndex) -> &mut T {
303 self.vec[index.0].2.as_mut().unwrap()
304 }
305}
306
307pub struct LinkedListIter<'a, T: 'a> {
308 linked_list: &'a LinkedList<T>,
309 index: Option<LinkedListIndex<'a>>,
310}
311impl<'a, T> Iterator for LinkedListIter<'a, T> {
312 type Item = &'a T;
313 fn next(&mut self) -> Option<&'a T> {
314 if let Some(index) = self.index {
315 if index != self.linked_list.tail().unwrap() {
316 self.linked_list.increment(self.index.as_mut().unwrap());
317 } else {
318 self.index = None;
319 }
320 Some(&self.linked_list[index])
321 } else {
322 None
323 }
324 }
325}