linked_vector/linked_vector.rs
1
2
3use core::fmt;
4use core::iter::{FromIterator, FusedIterator};
5use core::ops::{Index, IndexMut};
6use core::cmp::Ordering;
7use core::hash::{Hash, Hasher};
8use core::fmt::Formatter;
9use core::fmt::Debug;
10
11use crate::cursor::*;
12
13#[cfg(debug_assertions)]
14use uuid::{uuid, Uuid};
15
16#[cfg(not(debug_assertions))]
17pub(crate) const BAD_HANDLE : HNode = HNode(usize::MAX);
18
19#[cfg(debug_assertions)]
20pub(crate) const BAD_HANDLE : HNode =
21 HNode(usize::MAX,
22 usize::MAX,
23 uuid!("deadbeef-dead-beef-dead-beefdeadbeef"));
24
25/// A handle to a node within a `LinkedVector`. Internally, it holds an index
26/// into the vector holding the LinkedVector's nodes.
27///
28#[cfg(not(debug_assertions))]
29#[repr(transparent)]
30#[derive(Debug, Clone, Copy, PartialEq)]
31pub struct HNode(usize);
32
33/// A handle to a node within a `LinkedVector`. Internally, it holds an index
34/// into the vector holding the LinkedVector's nodes.
35///
36#[cfg(debug_assertions)]
37#[derive(Debug, Clone, Copy, PartialEq)]
38pub struct HNode(usize, usize, Uuid);
39
40impl Default for HNode {
41 #[inline]
42 fn default() -> Self {
43 BAD_HANDLE
44 }
45}
46
47/// The node type used by `LinkedVector`. It holds a value of type `T`, and
48/// handles to the next and previous nodes in the list.
49///
50pub(crate) struct Node<T> {
51 value : Option<T>,
52 next : HNode,
53 prev : HNode,
54
55 // This field is used to detect expired handles. In debug mode if
56 // a handle's 2nd field doesn't match this, it's expried. When
57 // a node is added to the recycle list via. `push_recyc()`, this
58 // number is incremented.
59 #[cfg(debug_assertions)]
60 gen : usize,
61}
62impl<T> Node<T> {
63 #[cfg(debug_assertions)]
64 #[inline]
65 fn new(value: T, gen: usize) -> Self {
66 Self {
67 value : Some(value),
68 next : BAD_HANDLE,
69 prev : BAD_HANDLE,
70 gen,
71 }
72 }
73 #[cfg(not(debug_assertions))]
74 #[inline]
75 fn new(value: T) -> Self {
76 Self {
77 value : Some(value),
78 next : BAD_HANDLE,
79 prev : BAD_HANDLE,
80 }
81 }
82
83 #[cfg(test)]
84 #[inline(always)]
85 pub(crate) fn next(&self) -> HNode {
86 self.next
87 }
88
89 #[cfg(test)]
90 #[inline(always)]
91 pub(crate) fn prev(&self) -> HNode {
92 self.prev
93 }
94}
95
96/// A doubly-linked list that uses handles to refer to elements that exist
97/// within a vector. This allows for O(1) insertion and removal of elements
98/// from the list, and O(1) access to elements by handle.
99///
100pub struct LinkedVector<T> {
101 vec : Vec<Node<T>>,
102 head : HNode,
103 recyc : HNode,
104 len : usize,
105
106 // This field is used to detect foreign handles. If a handle's
107 // 3rd field doesn't match this, it's foreign.
108 #[cfg(debug_assertions)]
109 uuid : Uuid,
110}
111
112impl<T> LinkedVector<T> {
113 /// Creates a new, empty `LinkedVector`.
114 ///
115 #[inline]
116 #[must_use]
117 pub fn new() -> Self {
118 Self {
119 vec : Vec::new(),
120 recyc : BAD_HANDLE,
121 head : BAD_HANDLE,
122 len : 0,
123
124 #[cfg(debug_assertions)]
125 uuid : uuid::Uuid::new_v4()
126 }
127 }
128
129 /// Creates a new, empty `LinkedVector` with the specified capacity.
130 ///
131 #[inline]
132 #[must_use]
133 pub fn with_capacity(size: usize) -> Self {
134 Self {
135 vec : Vec::with_capacity(size),
136 recyc : BAD_HANDLE,
137 head : BAD_HANDLE,
138 len : 0,
139
140 #[cfg(debug_assertions)]
141 uuid : uuid::Uuid::new_v4()
142 }
143 }
144
145 /// Moves all elements from `other` into `self`, leaving `other` empty.
146 /// This operation completes in O(n) time where n is the length of `other`.
147 /// ```
148 /// use linked_vector::*;
149 /// let mut lv1 = LinkedVector::new();
150 /// let mut lv2 = LinkedVector::from([1, 2, 3]);
151 ///
152 /// lv1.append(&mut lv2);
153 ///
154 /// assert_eq!(lv1.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
155 /// assert_eq!(lv2.len(), 0);
156 /// ```
157 #[inline]
158 pub fn append(&mut self, other: &mut Self) {
159 while let Some(value) = other.pop_front() {
160 self.push_back(value);
161 }
162 other.clear();
163 }
164
165 /// Gives a reference to the back element, or `None` if the list is empty.
166 /// This operation completes in O(1) time.
167 /// ```
168 /// use linked_vector::*;
169 /// let mut lv = LinkedVector::from([1, 2, 3]);
170 /// assert_eq!(lv.back(), Some(&3));
171 /// ```
172 #[inline]
173 pub fn back(&self) -> Option<&T> {
174 if self.is_empty() {
175 None
176 } else {
177 self.back_().unwrap().value.as_ref()
178 }
179 }
180
181 /// Gives a mutable reference to the element back element, or `None` if the
182 /// list is empty. This operation completes in O(1) time.
183 /// ```
184 /// use linked_vector::*;
185 /// let mut lv = LinkedVector::from([1, 2, 3]);
186 ///
187 /// *lv.back_mut().unwrap() = 42;
188 ///
189 /// assert_eq!(lv.back_mut(), Some(&mut 42));
190 /// ```
191 #[inline]
192 pub fn back_mut(&mut self) -> Option<&mut T> {
193 if self.is_empty() {
194 None
195 } else {
196 self.get_mut_(self.get_(self.head).prev).value.as_mut()
197 }
198 }
199
200 /// Returns the total number of elements the vector can hold without
201 /// reallocating.
202 ///
203 #[inline]
204 pub fn capacity(&self) -> usize {
205 self.vec.capacity()
206 }
207
208 /// Removes all elements from the list.
209 ///
210 #[inline]
211 pub fn clear(&mut self) {
212 self.vec.clear();
213 self.len = 0;
214 self.head = BAD_HANDLE;
215 self.recyc = BAD_HANDLE;
216 }
217
218 /// Consumes the LinkedVector and produces a new one that has all its nodes
219 /// placed contiguously in sequential order at the front of the internal
220 /// vector. Where performance is critical and the cost of a compacting
221 /// operation is infrequent and acceptible, compacting the vector *may* give
222 /// a gain in performance for certain use cases. All handles from the old
223 /// vector will not be native to the new compacted vector. `compact()`
224 /// completes in O(n) time.
225 ///
226 #[inline]
227 #[must_use]
228 pub fn compact(self) -> Self {
229 self.into_iter().collect()
230 }
231
232 /// Returns `true` if the list contains an element with the given value.
233 /// This operation completes in O(n) time where n is the length of the list.
234 ///
235 #[inline]
236 pub fn contains(&self, value: &T) -> bool
237 where
238 T: PartialEq
239 {
240 self.iter().any(|v| v == value)
241 }
242
243 /// Creates a cursor that can be used to traverse the list starting at the
244 /// given node. This operation completes in O(1) time.
245 /// ```
246 /// use linked_vector::*;
247 /// let lv = LinkedVector::from([1, 2, 3, 4, 5, 6, 7, 8, 9]);
248 /// let h3 = lv.handle(2).unwrap();
249 /// let mut cursor = lv.cursor(h3);
250 ///
251 /// cursor.forward(3);
252 ///
253 /// assert_eq!(*cursor, 6);
254 /// ```
255 #[inline]
256 pub fn cursor(&self, node: HNode) -> Cursor<T> {
257 Cursor::new(self, node)
258 }
259
260 /// Creates a cursor that holds a mutable reference to the LinkedVector that
261 /// can be used to traverse the list starting at the given node. If the
262 /// vector is empty, `None` is returned. This operation completes in O(1)
263 /// time.
264 /// ```
265 /// use linked_vector::*;
266 /// let mut lv = LinkedVector::from([1, 2, 3, 4, 5, 6]);
267 /// let mut cursor = lv.cursor_mut(lv.front_node().unwrap());
268 ///
269 /// cursor.forward(3);
270 ///
271 /// assert_eq!(*cursor, 4);
272 ///
273 /// *cursor = 42;
274 ///
275 /// assert_eq!(lv.to_vec(), vec![1, 2, 3, 42, 5, 6]);
276 /// ```
277 #[inline]
278 pub fn cursor_mut(&mut self, node: HNode) -> CursorMut<T> {
279 CursorMut::new(self, node)
280 }
281
282 /// Returns a Cursor starting at the front element, or `None` if the list is
283 /// empty. If the vector is empty, `None` is returned. This operation
284 /// completes in O(1) time.
285 ///
286 #[inline]
287 pub fn cursor_back(&self) -> Option<Cursor<T>> {
288 if self.is_empty() {
289 None
290 } else {
291 Some(self.cursor(self.back_node().unwrap()))
292 }
293 }
294
295 /// Returns a Cursor starting at the back element, or `None` if the list is
296 /// empty. This operation completes in O(1) time.
297 ///
298 #[inline]
299 pub fn cursor_back_mut(&mut self) -> Option<CursorMut<T>> {
300 if self.is_empty() {
301 None
302 } else {
303 Some(self.cursor_mut(self.back_node().unwrap()))
304 }
305 }
306
307 /// Gives a reference to the element at the front of the vector, or `None`
308 /// if the list is empty. This operation completes in O(1) time.
309 ///
310 #[inline]
311 pub fn cursor_front(&self) -> Option<Cursor<T>> {
312 if self.is_empty() {
313 None
314 } else {
315 Some(self.cursor(self.front_node().unwrap()))
316 }
317 }
318
319 /// Gives a mutable Cursor starting at the front of the vector, or `None` if
320 /// the list is empty. This operation completes in O(1) time.
321 ///
322 #[inline]
323 pub fn cursor_front_mut(&mut self) -> Option<CursorMut<T>> {
324 if self.is_empty() {
325 None
326 } else {
327 Some(self.cursor_mut(self.front_node().unwrap()))
328 }
329 }
330
331 /// Gives a reference to the element at the front of the vector, or `None`
332 /// if the list is empty. This operation completes in O(1) time.
333 ///
334 #[inline]
335 pub fn front(&self) -> Option<&T> {
336 if self.is_empty() {
337 None
338 } else {
339 self.front_().unwrap().value.as_ref()
340 }
341 }
342
343 /// Gives a mutable reference to the element at the front of the vector,
344 /// or `None` if the list is empty. This operation completes in O(1) time.
345 ///
346 #[inline]
347 pub fn front_mut(&mut self) -> Option<&mut T> {
348 if self.is_empty() {
349 None
350 } else {
351 self.get_mut_(self.head).value.as_mut()
352 }
353 }
354
355 /// Returns a handle to the first node in the list, or `None` if the list is
356 /// empty. This operation completes in O(1) time.
357 /// ```
358 /// use linked_vector::*;
359 /// let mut lv = LinkedVector::from([1, 2, 3]);
360 /// let hnode = lv.push_front(42);
361 ///
362 /// assert_eq!(lv.front_node(), Some(hnode));
363 /// assert_eq!(lv.front(), Some(&42));
364 /// ```
365 #[inline]
366 pub fn front_node(&self) -> Option<HNode> {
367 if self.len == 0 {
368 None
369 } else {
370 Some(self.head)
371 }
372 }
373
374 /// Returns a handle to the last node in the list, or `None` if the list is
375 /// empty. This operation completes in O(1) time.
376 ///
377 #[inline]
378 pub fn back_node(&self) -> Option<HNode> {
379 self.front_().map(|node| node.prev)
380 }
381
382 /// Provides a reference to the element indicated by the given handle. This
383 /// operation completes in O(1) time. If the `"optionless-accessors"`
384 /// feature is disabled, this operation returns the reference wrapped in an
385 /// `Option`. This feature is disabled by
386 /// default, see [usage notes](./index.html#usage).
387 /// ```
388 /// use linked_vector::*;
389 /// let mut lv = LinkedVector::from([1, 2, 3]);
390 /// let hnode = lv.push_front(42);
391 ///
392 /// assert_eq!(lv.get(hnode), &42);
393 /// ```
394 #[inline]
395 #[cfg(feature = "optionless-accessors")]
396 pub fn get(&self, node: HNode) -> &T {
397 self.get_(node).value.as_ref().unwrap()
398 }
399
400 /// Provides a reference to the element indicated by the given handle, or
401 /// `None` if the handle is invalid. With the "optionless-accesors" feature,
402 /// this method returns its reference directly - no `Option`,
403 /// see [usage notes](./index.html#usage). This operation completes in
404 /// O(1) time.
405 /// ```
406 /// use linked_vector::*;
407 /// let mut lv = LinkedVector::from([1, 2, 3]);
408 /// let hnode = lv.push_front(42);
409 ///
410 /// assert_eq!(lv.get(hnode), Some(&42));
411 /// ```
412 #[inline]
413 #[cfg(not(feature = "optionless-accessors"))]
414 pub fn get(&self, node: HNode) -> Option<&T> {
415 self.get_(node).value.as_ref()
416 }
417
418 /// Provides a mutable reference to the element indicated by the given
419 /// handle. This operation completes in O(1) time. If the
420 /// `"optionless-accessors"` feature is disabled, this operation returns the
421 /// reference wrapped in an `Option`. This feature is disabled by default,
422 /// see [usage notes](./index.html#usage).
423 /// ```
424 /// use linked_vector::*;
425 /// let mut lv = LinkedVector::new();
426 /// let hnode = lv.push_front(0);
427 ///
428 /// *lv.get_mut(hnode) = 42;
429 ///
430 /// assert_eq!(lv.get(hnode), &42);
431 /// ```
432 #[inline]
433 #[cfg(feature = "optionless-accessors")]
434 pub fn get_mut(&mut self, node: HNode) -> &mut T {
435 self.get_mut_(node).value.as_mut().unwrap()
436 }
437
438 /// Provides a mutable reference to the element indicated by the given
439 /// handle, or `None` if the handle is invalid. With the
440 /// "optionless-accessors" feature enabled, this method returns its
441 /// reference directly - no `Option`, see [usage notes](./index.html#usage).
442 /// This operation completes in O(1) time.
443 /// ```
444 /// use linked_vector::*;
445 /// let mut lv = LinkedVector::new();
446 /// let hnode = lv.push_front(0);
447 ///
448 /// *lv.get_mut(hnode).unwrap() = 42;
449 ///
450 /// assert_eq!(lv[hnode], 42);
451 /// ```
452 #[inline]
453 #[cfg(not(feature = "optionless-accessors"))]
454 pub fn get_mut(&mut self, node: HNode) -> Option<&mut T> {
455 self.get_mut_(node).value.as_mut()
456 }
457
458 /// Returns the handle to the node at the given index, or `None` if the
459 /// index is out of bounds. If `index > self.len / 2`, the search starts
460 /// from the end of the list. This operation performs in O(n / 2) time
461 /// worst case.
462 /// ```
463 /// use linked_vector::*;
464 /// let mut lv = LinkedVector::new();
465 /// let h1 = lv.push_front(1);
466 /// let h2 = lv.push_front(2);
467 /// let h3 = lv.push_front(3);
468 ///
469 /// assert_eq!(lv.handle(1), Some(h2));
470 /// assert_eq!(lv.handle(3), None);
471 /// assert_eq!(lv.handle(2), Some(h1));
472 /// ```
473 #[inline]
474 pub fn handle(&self, index: usize) -> Option<HNode> {
475 if index <= self.len / 2 {
476 self.handles().nth(index)
477 } else if index >= self.len {
478 None
479 } else {
480 self.handles().rev().nth(self.len - index - 1)
481 }
482 }
483
484 /// Returns an iterator over the handles of the vector. The handles will
485 /// reflect the order of the linked list. This operation completes in O(1)
486 /// time.
487 /// ```
488 /// use linked_vector::*;
489 /// let mut lv = LinkedVector::new();
490 ///
491 /// let h1 = lv.push_back(42);
492 /// let h2 = lv.push_back(43);
493 /// let h3 = lv.push_back(44);
494 ///
495 /// let iter = lv.handles();
496 ///
497 /// assert_eq!(iter.collect::<Vec<_>>(), vec![h1, h2, h3]);
498 /// ```
499 #[inline]
500 pub fn handles(&self) -> Handles<T> {
501 Handles::new(self)
502 }
503
504 /// Inserts a new element at the position indicated by the handle, `node`.
505 /// Returns a handle to the newly inserted element. This operation completes
506 /// in O(1) time.
507 /// ```
508 /// use linked_vector::*;
509 /// let mut lv = LinkedVector::new();
510 ///
511 /// let h1 = lv.push_back(42);
512 /// let h2 = lv.insert(h1, 43);
513 ///
514 /// assert_eq!(lv.next_node(h2), Some(h1));
515 /// assert_eq!(lv[h1], 42);
516 /// ```
517 #[inline]
518 pub fn insert(&mut self, node: HNode, value: T) -> HNode {
519 self.insert_(Some(node), value)
520 }
521
522 /// Inserts a new element after the one indicated by the handle, `node`.
523 /// Returns a handle to the newly inserted element. This operation completes
524 /// in O(1) time.
525 /// ```
526 /// use linked_vector::*;
527 /// let mut lv = LinkedVector::new();
528 ///
529 /// let h1 = lv.push_back(42);
530 /// let h2 = lv.insert_after(h1, 43);
531 ///
532 /// assert_eq!(lv.next_node(h1), Some(h2));
533 /// assert_eq!(lv[h2], 43);
534 /// ```
535 #[inline]
536 pub fn insert_after(&mut self, node: HNode, value: T) -> HNode {
537 if let Some(next) = self.next_node(node) {
538 self.insert_(Some(next), value)
539 } else {
540 self.insert_(None, value)
541 }
542 }
543
544 /// Returns `true` if the list contains no elements.
545 ///
546 #[inline]
547 pub fn is_empty(&self) -> bool {
548 self.len == 0
549 }
550
551 /// Returns an iterator over the elements of the list.
552 ///
553 #[inline]
554 pub fn iter(&self) -> Iter<T> {
555 Iter::new(self)
556 }
557
558 /// Returns an iterator over the elements of the list. Renders mutable
559 /// references to the elements.
560 /// ```
561 /// use linked_vector::*;
562 /// let mut lv = LinkedVector::from([1, 2, 3]);
563 ///
564 /// lv.iter_mut().for_each(|x| *x += 1);
565 ///
566 /// assert_eq!(lv, LinkedVector::from([2, 3, 4]));
567 /// ```
568 #[inline]
569 pub fn iter_mut(&mut self) -> IterMut<T> {
570 IterMut::new(self)
571 }
572
573 /// Returns the length of the list.
574 ///
575 #[inline]
576 pub fn len(&self) -> usize {
577 self.len
578 }
579
580 /// Returns a handle to the next node in the list, or `None` if the given
581 /// handle is the last node in the list. This operation completes in O(1)
582 /// ```
583 /// use linked_vector::*;
584 /// let mut lv = LinkedVector::new();
585 ///
586 /// let h1 = lv.push_back(42);
587 /// let h2 = lv.push_back(43);
588 ///
589 /// assert_eq!(lv.next_node(h1), Some(h2));
590 /// ```
591 #[inline]
592 pub fn next_node(&self, node: HNode) -> Option<HNode> {
593 let next = self.get_(node).next;
594 if next == BAD_HANDLE {
595 None
596 } else {
597 Some(next)
598 }
599 }
600
601 /// Returns a reference to the next element's value in the list, or `None`
602 /// if the given handle is the last node in the list. This operation
603 /// completes in O(1) time.
604 ///
605 #[inline]
606 pub fn next_value(&self, node: HNode) -> Option<&T> {
607 self.next_node(node).and_then(|n| self.get_(n).value.as_ref())
608 }
609
610 /// Returns a mutable reference to the next element's value in the list, or
611 /// `None` if the given handle is the last node in the list. This operation
612 /// completes in O(1) time.
613 ///
614 #[inline]
615 pub fn next_value_mut(&mut self, node: HNode) -> Option<&mut T> {
616 self.next_node(node).and_then(move |n| self.get_mut_(n).value.as_mut())
617 }
618
619 /// Returns a handle to the previous node in the list, or `None` if the
620 /// given handle is the first node in the list. This operation completes in
621 /// O(1) time.
622 /// ```
623 /// use linked_vector::*;
624 /// let mut lv = LinkedVector::new();
625 ///
626 /// let h1 = lv.push_back(42);
627 /// let h2 = lv.push_back(43);
628 ///
629 /// assert_eq!(lv.prev_node(h2), Some(h1));
630 /// ```
631 #[inline]
632 pub fn prev_node(&self, node: HNode) -> Option<HNode> {
633 if node != self.head {
634 Some(self.get_(node).prev)
635 } else {
636 None
637 }
638 }
639
640 /// Returns a reference to the previous element's value in the list, or
641 /// `None` if the given handle is the first node in the list. This operation
642 /// completes in O(1) time.
643 ///
644 #[inline]
645 pub fn prev_value(&self, node: HNode) -> Option<&T> {
646 self.prev_node(node).and_then(|n| self.get_(n).value.as_ref())
647 }
648
649 /// Returns a mutable reference to the previous element's value in the list,
650 /// or `None` if the given handle is the first node in the list. This
651 /// operation completes in O(1) time.
652 ///
653 #[inline]
654 pub fn prev_value_mut(&mut self, node: HNode) -> Option<&mut T> {
655 self.prev_node(node).and_then(move |n| self.get_mut_(n).value.as_mut())
656 }
657
658 /// Pops the last element of the vector. Returns `None` if the vector is
659 /// empty. This operation completes in O(1) time.
660 /// ```
661 /// use linked_vector::*;
662 /// let mut lv = LinkedVector::from([1, 2, 3]);
663 ///
664 /// assert_eq!(lv.pop_back(), Some(3));
665 /// ```
666 #[inline]
667 pub fn pop_back(&mut self) -> Option<T> {
668 self.remove_(None)
669 }
670
671 /// Pops the first element of the vector. Returns `None` if the vector is
672 /// empty. This operation completes in O(1) time.
673 /// ```
674 /// use linked_vector::*;
675 /// let mut lv = LinkedVector::from([1, 2, 3]);
676 ///
677 /// assert_eq!(lv.pop_front(), Some(1));
678 /// ```
679 #[inline]
680 pub fn pop_front(&mut self) -> Option<T> {
681 if self.is_empty() {
682 None
683 } else {
684 self.remove_(Some(self.head))
685 }
686 }
687
688 /// Pushes a new element to the back of the list. Returns a handle to the
689 /// newly inserted element. This operation completes in O(1) time.
690 /// ```
691 /// use linked_vector::*;
692 /// let mut lv = LinkedVector::new();
693 ///
694 /// let h1 = lv.push_back(42);
695 /// let h2 = lv.push_back(43);
696 ///
697 /// assert_eq!(lv.next_node(h1), Some(h2));
698 /// ```
699 #[inline]
700 pub fn push_back(&mut self, value: T) -> HNode {
701 self.insert_(None, value)
702 }
703
704 /// Pushes a new element to the front of the list. Returns a handle to the
705 /// newly inserted element. This operation completes in O(1) time.
706 /// ```
707 /// use linked_vector::*;
708 /// let mut lv = LinkedVector::from([1, 2, 3]);
709 ///
710 /// let h1 = lv.front_node().unwrap();
711 /// let h2 = lv.push_front(42);
712 ///
713 /// assert_eq!(lv.next_node(h2), Some(h1));
714 /// ```
715 #[inline]
716 pub fn push_front(&mut self, value: T) -> HNode {
717 if self.is_empty() {
718 self.insert_(None, value)
719 } else {
720 self.insert_(Some(self.head), value)
721 }
722 }
723
724 /// Removes the element indicated by the handle, `node`. Returns the element
725 /// if the handle is valid, or panics otherwise. This operation completes in
726 /// O(1) time. With the `optionless-accessors` feature disabled, this method
727 /// returns the value wrapped in an `Option`. This feature is disabled by
728 /// default, see [usage notes](./index.html#usage).
729 /// ```
730 /// use linked_vector::*;
731 /// let mut lv = LinkedVector::from([1, 2, 3]);
732 /// let handles = lv.handles().collect::<Vec<_>>();
733 ///
734 /// lv.remove(handles[1]);
735 ///
736 /// assert_eq!(lv, LinkedVector::from([1, 3]));
737 /// ```
738 #[inline]
739 #[cfg(feature = "optionless-accessors")]
740 pub fn remove(&mut self, node: HNode) -> T {
741 self.remove_(Some(node)).unwrap()
742 }
743
744 /// Removes the element indicated by the handle, `node`. Returns the element
745 /// if the handle is valid, or `None` otherwise. This operation completes in
746 /// O(1) time. With the `"optionless-accessors"` feature enabled, this
747 /// method returns its value directly, not wrapped in an `Option`,
748 /// see [usage notes](./index.html#usage).
749 /// ```
750 /// use linked_vector::*;
751 /// let mut lv = LinkedVector::from([1, 2, 3]);
752 /// let handles = lv.handles().collect::<Vec<_>>();
753 ///
754 /// lv.remove(handles[1]);
755 ///
756 /// assert_eq!(lv, LinkedVector::from([1, 3]));
757 /// ```
758 #[inline]
759 #[cfg(not(feature = "optionless-accessors"))]
760 pub fn remove(&mut self, node: HNode) -> Option<T> {
761 self.remove_(Some(node))
762 }
763
764 /// Sorts the elemements in place in ascending order. Previously held
765 /// handles will still be valid and reference the same elements (with the
766 /// same values) as before. Only the `next` and `prev` fields of the nodes
767 /// are modified in the list. Uses Rust's stable sort internally and
768 /// requires some auxiliary memory for a temporary handle list.
769 /// ```
770 /// use linked_vector::*;
771 /// let mut lv = LinkedVector::new();
772 /// let h1 = lv.push_back(3);
773 /// let h2 = lv.push_back(2);
774 /// let h3 = lv.push_back(1);
775 ///
776 /// lv.extend([7, 11, 4, 6, 8, 13, 12, 9, 14, 5, 10]);
777 ///
778 /// lv.sort();
779 ///
780 /// assert_eq!(lv.to_vec(), (1..15).collect::<Vec<_>>());
781 /// assert_eq!(lv[h1], 3);
782 /// assert_eq!(lv[h2], 2);
783 /// assert_eq!(lv[h3], 1);
784 /// ```
785 #[inline]
786 pub fn sort(&mut self)
787 where
788 T: Ord
789 {
790 self.sort_by_(|a, b| a.cmp(b), true);
791 }
792
793 /// Sorts the elemements in place using the provided comparison function.
794 /// See [sort()](LinkedVector::sort) for more details.
795 /// ```
796 /// use linked_vector::*;
797 /// let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
798 ///
799 /// lv.sort_by(|a, b| b.cmp(a));
800 ///
801 /// assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);
802 /// ```
803 #[inline]
804 pub fn sort_by<F>(&mut self, compare: F)
805 where
806 F: FnMut(&T, &T) -> Ordering,
807 {
808 self.sort_by_(compare, true)
809 }
810
811 /// Sorts the elemements in place in using the provided key extraction
812 /// function. See [sort()](LinkedVector::sort) for more details.
813 /// ```
814 /// use linked_vector::*;
815 /// let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
816 ///
817 /// lv.sort_by_key(|k| -k);
818 ///
819 /// assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);
820 /// ```
821 #[inline]
822 pub fn sort_by_key<K, F>(&mut self, mut key: F)
823 where
824 K: Ord,
825 F: FnMut(&T) -> K,
826 {
827 self.sort_by_(|a, b| key(a).cmp(&key(b)), true);
828 }
829
830 /// Sorts the elemements in place in ascending order. Previously held
831 /// handles will still be valid and reference the same elements (with the
832 /// same values) as before. Only the `next` and `prev` fields of the nodes
833 /// are modified in the list. Uses Rust's unstable sort internally and
834 /// requires some auxiliary memory for a temporary handle list.
835 /// ```
836 /// use linked_vector::*;
837 /// let mut lv = LinkedVector::from([5, 4, 3, 2, 1, 0]);
838 ///
839 /// lv.sort_unstable();
840 ///
841 /// assert_eq!(lv.to_vec(), vec![0, 1, 2, 3, 4, 5]);
842 /// ```
843 #[inline]
844 pub fn sort_unstable(&mut self)
845 where
846 T: Ord
847 {
848 self.sort_by_(|a, b| a.cmp(b), false);
849 }
850
851 /// Sorts the elemements in place using the provided comparison function.
852 /// See [sort_unstable()](LinkedVector::sort_unstable) for more details.
853 /// ```
854 /// use linked_vector::*;
855 /// let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
856 ///
857 /// lv.sort_unstable_by(|a, b| b.cmp(a));
858 ///
859 /// assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);
860 /// ```
861 #[inline]
862 pub fn sort_unstable_by<F>(&mut self , compare: F)
863 where
864 F: FnMut(&T, &T) -> Ordering,
865 {
866 self.sort_by_(compare, false);
867 }
868
869 /// Sorts the elemements in place in using the provided key extraction
870 /// function. See [sort_unstable()](LinkedVector::sort_unstable) for more
871 /// details.
872 /// ```
873 /// use linked_vector::*;
874 /// let mut lv = LinkedVector::from([1, 2, 3, 4, 5]);
875 ///
876 /// lv.sort_unstable_by_key(|k| -k);
877 ///
878 /// assert_eq!(lv.to_vec(), vec![5, 4, 3, 2, 1]);
879 /// ```
880 #[inline]
881 pub fn sort_unstable_by_key<K, F>(&mut self, mut key: F)
882 where
883 K: Ord,
884 F: FnMut(&T) -> K,
885 {
886 self.sort_by_(|a, b| key(a).cmp(&key(b)), false);
887 }
888
889 /// Returns a vector containing the elements of the list. This operation
890 /// completes in O(n) time.
891 /// ```
892 /// use linked_vector::*;
893 /// let lv = LinkedVector::from([1, 2, 3]);
894 ///
895 /// assert_eq!(lv.to_vec(), vec![1, 2, 3]);
896 /// ```
897 #[inline]
898 pub fn to_vec(&self) -> Vec<T>
899 where
900 T: Clone
901 {
902 self.iter().cloned().collect()
903 }
904
905 /// Returns a reference to the last node. Returns `None` if the list is
906 /// empty. This operation completes in O(1) time.
907 ///
908 #[inline]
909 fn back_(&self) -> Option<&Node<T>> {
910 if self.is_empty() {
911 None
912 } else {
913 Some(self.get_(self.get_(self.head).prev))
914 }
915 }
916
917 /// returns a reference to the first node. Returns `None` if the list is
918 /// empty. This operation completes in O(1) time.
919 ///
920 #[inline]
921 fn front_(&self) -> Option<&Node<T>> {
922 if self.is_empty() {
923 None
924 } else {
925 Some(self.get_(self.head))
926 }
927 }
928
929 /// Inserts `value` before the element indicated by `node`. If `node` is
930 /// `None`, the element is inserted at the end of the list. Returns a handle
931 /// to the newly inserted element. This operation completes in O(1) time.
932 ///
933 #[inline]
934 pub(crate) fn insert_(&mut self, node: Option<HNode>, value: T) -> HNode {
935 if self.is_empty() {
936 #[cfg(debug_assertions)]
937 assert!(node.is_none(), "Empty list has no handles.");
938 let hnew = self.new_node(value);
939 self.head = hnew;
940 self.get_mut_(hnew).prev = hnew;
941 self.len += 1;
942 hnew
943 } else {
944 let hnew = self.new_node(value);
945 if let Some(hnode) = node {
946 let hprev = self.get_(hnode).prev;
947 self.get_mut_(hnew).prev = hprev;
948 self.get_mut_(hnew).next = hnode;
949 self.get_mut_(hnode).prev = hnew;
950 if hnode == self.head {
951 self.head = hnew;
952 } else {
953 self.get_mut_(hprev).next = hnew;
954 }
955 } else {
956 let hnode = self.get_(self.head).prev;
957 self.get_mut_(hnode).next = hnew;
958 self.get_mut_(hnew).prev = hnode;
959 self.get_mut_(self.head).prev = hnew;
960 }
961 self.len += 1;
962 hnew
963 }
964 }
965
966 /// Removes the element indicated by the handle, `node`. Returns the element
967 /// if the handle is valid, or `None` otherwise. This operation completes in
968 /// O(1) time.
969 ///
970 #[inline]
971 pub(crate) fn remove_(&mut self, node: Option<HNode>) -> Option<T> {
972 if self.is_empty() {
973 #[cfg(debug_assertions)]
974 assert!(node.is_none(), "Empty list has no handles.");
975 None
976 } else {
977 let hnode = node.unwrap_or(self.get_(self.head).prev);
978 if self.len > 1 {
979 let hprev = self.get_(hnode).prev;
980 let hnext = self.get_(hnode).next;
981 if hnext == BAD_HANDLE {
982 self.get_mut_(self.head).prev = hprev;
983 } else {
984 self.get_mut_(hnext).prev = hprev;
985 }
986 if hnode == self.head {
987 self.head = hnext;
988 } else {
989 self.get_mut_(hprev).next = hnext;
990 }
991 } else {
992 self.head = BAD_HANDLE;
993 }
994 self.len -= 1;
995 let value = self.get_mut_(hnode).value.take();
996 self.push_recyc(hnode);
997 value
998 }
999 }
1000
1001 /// Returns a reference to the element indicated by the handle, `node`. This
1002 /// operation completes in O(1) time.
1003 ///
1004 #[inline(always)]
1005 pub(crate) fn get_(&self, node: HNode) -> &Node<T> {
1006 #[cfg(debug_assertions)]
1007 self.check_handle(node);
1008
1009 &self.vec[node.0]
1010 }
1011
1012 /// Returns a mutable reference to the element indicated by the handle,
1013 /// `node`. This operation completes in O(1) time.
1014 ///
1015 #[inline(always)]
1016 pub(crate) fn get_mut_(&mut self, node: HNode) -> &mut Node<T> {
1017 #[cfg(debug_assertions)]
1018 self.check_handle(node);
1019
1020 &mut self.vec[node.0]
1021 }
1022
1023 #[cfg(debug_assertions)]
1024 pub(crate) fn check_handle(&self, node: HNode) {
1025 assert!(node.0 != BAD_HANDLE.0, "Handle is invalid.");
1026 assert!(node.2 == self.uuid, "Handle is not native.");
1027 assert!(node.1 == self.vec[node.0].gen, "Handle has expired.");
1028 }
1029
1030 /// Renders a new element node and returns a handle to it. This operation
1031 /// completes in O(1) time.
1032 ///
1033 #[inline]
1034 fn new_node(&mut self, value: T) -> HNode {
1035 if let Some(hnode) = self.pop_recyc() {
1036 #[cfg(debug_assertions)]
1037 {
1038 let gen = self.vec[hnode.0].gen;
1039 self.vec[hnode.0] = Node::new(value, gen);
1040 let mut hnode = hnode;
1041 hnode.1 = gen;
1042 hnode
1043 }
1044 #[cfg(not(debug_assertions))]
1045 {
1046 self.vec[hnode.0] = Node::new(value);
1047 hnode
1048 }
1049 } else {
1050 #[cfg(debug_assertions)]
1051 {
1052 self.vec.push(Node::new(value, 0));
1053 HNode(self.vec.len() - 1, 0, self.uuid)
1054 }
1055 #[cfg(not(debug_assertions))]
1056 {
1057 self.vec.push(Node::new(value));
1058 HNode(self.vec.len() - 1)
1059 }
1060 }
1061 }
1062
1063 /// Internal method that returns a handle to a useable node from the recycle
1064 /// bin. The node is removed from the bin. Only new_node() should call this.
1065 /// Use new_node() if you need a new node instead of this.
1066 ///
1067 #[inline]
1068 fn pop_recyc(&mut self) -> Option<HNode> {
1069 if self.recyc == BAD_HANDLE {
1070 None
1071 } else {
1072 let hnode = self.recyc;
1073 self.recyc = self.vec[hnode.0].next;
1074 self.vec[hnode.0].next = BAD_HANDLE;
1075 Some(hnode)
1076 }
1077 }
1078
1079 /// Pushes a recently discarded node, indicated by the handle, back into
1080 /// the recycle bin. This can be called by any method that discards a node.
1081 ///
1082 #[inline]
1083 fn push_recyc(&mut self, node: HNode) {
1084 self.get_mut_(node).prev = BAD_HANDLE;
1085 if self.recyc == BAD_HANDLE {
1086 self.vec[node.0].next = BAD_HANDLE;
1087 self.recyc = node;
1088 } else {
1089 self.vec[node.0].next = self.recyc;
1090 self.recyc = node;
1091 }
1092 #[cfg(debug_assertions)]
1093 { self.vec[node.0].gen += 1; }
1094 }
1095
1096 /// Sorts the list by the given comparison function. This operation
1097 /// completes in O(2n + n log n) time.
1098 ///
1099 fn sort_by_<F>(&mut self, mut compare: F, stable: bool)
1100 where
1101 F: FnMut(&T, &T) -> Ordering,
1102 {
1103 if self.len < 2 { return; }
1104 let mut handles = self.handles().collect::<Vec<_>>();
1105 if stable {
1106 handles.sort_by(|h1, h2| {
1107 compare(self.vec[h1.0].value.as_ref().unwrap(),
1108 self.vec[h2.0].value.as_ref().unwrap())
1109 });
1110 } else {
1111 handles.sort_unstable_by(|h1, h2| {
1112 compare(self.vec[h1.0].value.as_ref().unwrap(),
1113 self.vec[h2.0].value.as_ref().unwrap())
1114 });
1115 }
1116 for i in 0..self.len - 1 {
1117 self.vec[handles[i].0].next = handles[i + 1];
1118 self.vec[handles[i + 1].0].prev = handles[i];
1119 }
1120 let tail = *handles.last().unwrap();
1121 self.head = handles[0];
1122 self.vec[self.head.0].prev = tail;
1123 self.vec[tail.0].next = BAD_HANDLE;
1124 }
1125}
1126
1127impl<T> Clone for LinkedVector<T>
1128where
1129 T: Clone,
1130{
1131 #[inline]
1132 fn clone(&self) -> Self {
1133 let mut lv = Self::new();
1134 for v in self.iter() {
1135 lv.push_back(v.clone());
1136 }
1137 lv
1138 }
1139}
1140
1141impl<T> Debug for LinkedVector<T>
1142where
1143 T: Debug,
1144{
1145 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1146 write!(f, "LinkedVector(")?;
1147 f.debug_list().entries(self.iter()).finish()?;
1148 write!(f, ")")?;
1149 Ok(())
1150 }
1151}
1152
1153impl<T> Default for LinkedVector<T> {
1154 /// Renders the default value for an HNode. This will internally be set
1155 /// to `BAD_HANDLE` which is a handle that is invalid.
1156 ///
1157 #[inline]
1158 fn default() -> Self {
1159 Self::new()
1160 }
1161}
1162
1163impl<T: Eq> Eq for LinkedVector<T> {}
1164
1165impl<'a, T> Extend<&'a T> for LinkedVector<T>
1166where
1167 T: Clone,
1168{
1169 #[inline]
1170 fn extend<I>(&mut self, iter: I)
1171 where
1172 I: IntoIterator<Item = &'a T>,
1173 {
1174 for v in iter {
1175 self.push_back(v.clone());
1176 }
1177 }
1178}
1179
1180impl<T> Extend<T> for LinkedVector<T> {
1181 #[inline]
1182 fn extend<I>(&mut self, iter: I)
1183 where
1184 I: IntoIterator<Item = T>,
1185 {
1186 for v in iter {
1187 self.push_back(v);
1188 }
1189 }
1190}
1191
1192impl<T, const N: usize> From<[T; N]> for LinkedVector<T> {
1193 #[inline]
1194 fn from(arr: [T; N]) -> Self {
1195 let mut lv = Self::new();
1196 for v in arr {
1197 lv.push_back(v);
1198 }
1199 lv
1200 }
1201}
1202
1203impl<T> FromIterator<T> for LinkedVector<T> {
1204 #[inline]
1205 fn from_iter<I>(iter: I) -> Self
1206 where
1207 I: IntoIterator<Item = T>,
1208 {
1209 let mut lv = Self::new();
1210 for v in iter {
1211 lv.push_back(v);
1212 }
1213 lv
1214 }
1215}
1216
1217impl<T> Hash for LinkedVector<T>
1218where
1219 T: Hash,
1220{
1221 #[inline]
1222 fn hash<H: Hasher>(&self, state: &mut H) {
1223 for v in self.iter() {
1224 v.hash(state);
1225 }
1226 }
1227}
1228
1229impl<T> Index<HNode> for LinkedVector<T> {
1230 type Output = T;
1231
1232 #[inline]
1233 fn index(&self, handle: HNode) -> &Self::Output {
1234 #[cfg(feature = "optionless-accessors")]
1235 { self.get(handle) }
1236
1237 #[cfg(not(feature = "optionless-accessors"))]
1238 { self.get(handle).unwrap() }
1239 }
1240}
1241
1242impl<T> IndexMut<HNode> for LinkedVector<T> {
1243 #[inline]
1244 fn index_mut(&mut self, handle: HNode) -> &mut Self::Output {
1245 #[cfg(feature = "optionless-accessors")]
1246 { self.get_mut(handle) }
1247
1248 #[cfg(not(feature = "optionless-accessors"))]
1249 { self.get_mut(handle).unwrap() }
1250 }
1251}
1252
1253impl<T> Index<usize> for LinkedVector<T> {
1254 type Output = T;
1255
1256 #[inline]
1257 fn index(&self, index: usize) -> &Self::Output {
1258 self.handle(index)
1259 .and_then(|h| self.vec[h.0].value.as_ref())
1260 .expect("Invalid index")
1261 }
1262}
1263
1264impl<T> IndexMut<usize> for LinkedVector<T> {
1265 #[inline]
1266 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
1267 self.handle(index)
1268 .and_then(|h| self.vec[h.0].value.as_mut())
1269 .expect("Invalid index")
1270 }
1271}
1272
1273impl<T> PartialEq for LinkedVector<T>
1274where
1275 T: PartialEq
1276{
1277 #[inline]
1278 fn eq(&self, other: &Self) -> bool {
1279 self.len() == other.len() && self.iter().eq(other)
1280 }
1281}
1282
1283/// An iterator over the elements of a `LinkedVector`. Yields the handles of
1284/// each element.
1285///
1286pub struct Handles<'a, T> {
1287 lv : &'a LinkedVector<T>,
1288 hnode : HNode,
1289 hrev : HNode,
1290 len : usize,
1291}
1292
1293impl<'a, T> Handles<'a, T> {
1294 #[inline]
1295 pub fn new(lv: &'a LinkedVector<T>) -> Self {
1296 Self {
1297 hnode : lv.head,
1298 hrev : lv.front_().map(|h| h.prev).unwrap_or(BAD_HANDLE),
1299 len : lv.len(),
1300 lv,
1301 }
1302 }
1303}
1304
1305impl<'a, T> Iterator for Handles<'a, T> {
1306 type Item = HNode;
1307 #[inline]
1308 fn next(&mut self) -> Option<Self::Item> {
1309 if self.len > 0 {
1310 let hnode = self.hnode;
1311 self.hnode = self.lv.get_(hnode).next;
1312 self.len -= 1;
1313 Some(hnode)
1314 } else {
1315 None
1316 }
1317 }
1318 #[inline]
1319 fn size_hint(&self) -> (usize, Option<usize>) {
1320 (self.len, Some(self.len))
1321 }
1322 #[inline]
1323 fn last(self) -> Option<Self::Item> {
1324 self.lv.front_().map(|h| h.prev)
1325 }
1326}
1327
1328impl<'a, T> DoubleEndedIterator for Handles<'a, T> {
1329 #[inline]
1330 fn next_back(&mut self) -> Option<Self::Item> {
1331 if self.len > 0 {
1332 let hrev = self.hrev;
1333 let node = self.lv.get_(hrev);
1334 self.hrev = node.prev;
1335 self.len -= 1;
1336 Some(hrev)
1337 } else {
1338 None
1339 }
1340 }
1341}
1342
1343impl<T> ExactSizeIterator for Handles<'_, T> {}
1344
1345impl<T> FusedIterator for Handles<'_, T> {}
1346
1347/// The basic iterator class of `LinkedVector`. Yields references to the
1348/// elements of the vector.
1349///
1350pub struct Iter<'a, T> {
1351 lv : &'a LinkedVector<T>,
1352 hnode : HNode,
1353 hrev : HNode,
1354 len : usize,
1355}
1356impl<'a, T> Iter<'a, T> {
1357 #[inline]
1358 pub fn new(lv: &'a LinkedVector<T>) -> Self {
1359 Self {
1360 hnode : lv.head,
1361 hrev : lv.front_().map(|h| h.prev).unwrap_or(BAD_HANDLE),
1362 len : lv.len(),
1363 lv,
1364 }
1365 }
1366}
1367
1368impl<'a, T> Iterator for Iter<'a, T> {
1369 type Item = &'a T;
1370 #[inline]
1371 fn next(&mut self) -> Option<Self::Item> {
1372 if self.len > 0 {
1373 let hnode = self.hnode;
1374 self.hnode = self.lv.get_(hnode).next;
1375 self.len -= 1;
1376 #[cfg(feature = "optionless-accessors")]
1377 { Some(self.lv.get(hnode)) }
1378
1379 #[cfg(not(feature = "optionless-accessors"))]
1380 { self.lv.get(hnode) }
1381 } else {
1382 None
1383 }
1384 }
1385 #[inline]
1386 fn size_hint(&self) -> (usize, Option<usize>) {
1387 (self.len, Some(self.len))
1388 }
1389 #[inline]
1390 fn last(self) -> Option<Self::Item> {
1391 self.lv.back()
1392 }
1393}
1394
1395impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1396 #[inline]
1397 fn next_back(&mut self) -> Option<Self::Item> {
1398 if self.len > 0 {
1399 let hrev = self.hrev;
1400 let node = self.lv.get_(hrev);
1401 self.hrev = node.prev;
1402 self.len -= 1;
1403 #[cfg(feature = "optionless-accessors")]
1404 { Some(self.lv.get(hrev)) }
1405
1406 #[cfg(not(feature = "optionless-accessors"))]
1407 { self.lv.get(hrev) }
1408 } else {
1409 None
1410 }
1411 }
1412}
1413
1414impl<T> ExactSizeIterator for Iter<'_, T> {}
1415
1416impl<T> FusedIterator for Iter<'_, T> {}
1417
1418impl<'a, T> IntoIterator for &'a LinkedVector<T> {
1419 type Item = &'a T;
1420 type IntoIter = Iter<'a, T>;
1421 #[inline]
1422 fn into_iter(self) -> Self::IntoIter {
1423 Iter {
1424 hnode : self.head,
1425 hrev : self.front_().map(|h| h.prev).unwrap_or(BAD_HANDLE),
1426 len : self.len(),
1427 lv : self,
1428 }
1429 }
1430}
1431
1432/// The basic iterator class of `LinkedVector`. Yields mutable references to
1433/// the elements of the vector.
1434///
1435pub struct IterMut<'a, T> {
1436 lv : &'a mut LinkedVector<T>,
1437 hnode : HNode,
1438 hrev : HNode,
1439 len : usize,
1440}
1441
1442impl<'a, T> IterMut<'a, T> {
1443 #[inline]
1444 pub fn new(lv: &'a mut LinkedVector<T>) -> Self {
1445 Self {
1446 hnode : lv.head,
1447 hrev : lv.front_().map(|h| h.prev).unwrap_or(BAD_HANDLE),
1448 len : lv.len(),
1449 lv,
1450 }
1451 }
1452}
1453
1454impl<'a, T> Iterator for IterMut<'a, T> {
1455 type Item = &'a mut T;
1456 #[inline]
1457 fn next(&mut self) -> Option<Self::Item> {
1458 if self.len > 0 {
1459 let hnode = self.hnode;
1460 self.hnode = self.lv.get_(hnode).next;
1461 self.len -= 1;
1462 #[cfg(feature = "optionless-accessors")]
1463 { Some(unsafe { &mut *(self.lv.get_mut(hnode) as *mut T) }) }
1464
1465 #[cfg(not(feature = "optionless-accessors"))]
1466 {
1467 Some(unsafe { &mut *(self.lv.get_mut(hnode).unwrap() as *mut T)})
1468 }
1469 } else {
1470 None
1471 }
1472 }
1473 #[inline]
1474 fn size_hint(&self) -> (usize, Option<usize>) {
1475 (self.len, Some(self.len))
1476 }
1477 #[inline]
1478 fn last(self) -> Option<Self::Item> {
1479 self.lv.back_mut()
1480 }
1481}
1482
1483impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1484 #[inline]
1485 fn next_back(&mut self) -> Option<Self::Item> {
1486 if self.len > 0 {
1487 let hrev = self.hrev;
1488 let node = self.lv.get_(hrev);
1489 self.hrev = node.prev;
1490 self.len -= 1;
1491 #[cfg(feature = "optionless-accessors")]
1492 { Some(unsafe { &mut *(self.lv.get_mut(hrev) as *mut T) }) }
1493
1494 // TODO - compare this version with 1.1 version.
1495 #[cfg(not(feature = "optionless-accessors"))]
1496 {
1497 Some(unsafe { &mut *(self.lv.get_mut(hrev).unwrap() as *mut T) })
1498 }
1499 } else {
1500 None
1501 }
1502 }
1503}
1504
1505impl<T> ExactSizeIterator for IterMut<'_, T> {}
1506
1507impl<T> FusedIterator for IterMut<'_, T> {}
1508
1509impl<'a, T> IntoIterator for &'a mut LinkedVector<T> {
1510 type Item = &'a mut T;
1511 type IntoIter = IterMut<'a, T>;
1512 #[inline]
1513 fn into_iter(self) -> Self::IntoIter {
1514 IterMut {
1515 hnode : self.head,
1516 hrev : self.front_().map(|h| h.prev).unwrap_or(BAD_HANDLE),
1517 len : self.len(),
1518 lv : self,
1519 }
1520 }
1521}
1522
1523/// The consuming iterator class of `LinkedVector`. Yields owned elements of the
1524/// vector.
1525///
1526pub struct IntoIter<T>(LinkedVector<T>);
1527
1528impl<T> IntoIterator for LinkedVector<T> {
1529 type Item = T;
1530 type IntoIter = IntoIter<T>;
1531 #[inline]
1532 fn into_iter(self) -> Self::IntoIter {
1533 IntoIter(self)
1534 }
1535}
1536
1537impl<T> Iterator for IntoIter<T> {
1538 type Item = T;
1539 #[inline]
1540 fn next(&mut self) -> Option<Self::Item> {
1541 self.0.pop_front()
1542 }
1543 #[inline]
1544 fn size_hint(&self) -> (usize, Option<usize>) {
1545 (self.0.len(), Some(self.0.len()))
1546 }
1547}
1548
1549impl<T> DoubleEndedIterator for IntoIter<T> {
1550 #[inline]
1551 fn next_back(&mut self) -> Option<Self::Item> {
1552 self.0.pop_back()
1553 }
1554}
1555
1556impl<T> ExactSizeIterator for IntoIter<T> {}
1557
1558impl<T> FusedIterator for IntoIter<T> {}