orx_linked_list/tests/
doubly.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#![allow(unused_imports, dead_code)]
use crate::{
    type_aliases::{BACK_IDX, FRONT_IDX},
    variant::Doubly,
    DoublyEnds, DoublyIterable, List,
};
use core::fmt::Debug;
use orx_pinned_vec::PinnedVec;
use orx_selfref_col::{MemoryPolicy, Node, NodePtr};

type PtrAndNode<'a, T> = (NodePtr<Doubly<T>>, &'a Node<Doubly<T>>);

impl<T, M, P> List<Doubly<T>, M, P>
where
    M: MemoryPolicy<Doubly<T>>,
    T: Debug + PartialEq + Eq,
    P: PinnedVec<Node<Doubly<T>>>,
{
    /// A debugging method that performs internal structural test on the list and panics if it is in an invalid state.
    ///
    /// # Panics
    ///
    /// Panics if the list is in an invalid state.
    #[cfg(feature = "validation")]
    #[allow(clippy::unwrap_used)]
    pub fn validate(&self) {
        let num_active_nodes = self.0.nodes().iter().filter(|x| x.is_active()).count();
        assert_eq!(num_active_nodes, self.len());
        assert_eq!(self.iter().count(), num_active_nodes);

        match num_active_nodes {
            0 => {
                assert!(self.front().is_none());
                assert!(self.back().is_none());
            }
            1 => {
                assert!(self.front().is_some());
                assert_eq!(self.front(), self.back());
                assert_eq!(self.0.ends().get(BACK_IDX), self.0.ends().get(FRONT_IDX));

                let front_ptr = self.0.ends().get(FRONT_IDX).unwrap();
                assert!(self.next(&front_ptr).is_none());
                assert!(self.prev(&front_ptr).is_none());

                let back_ptr = self.0.ends().get(BACK_IDX).unwrap();
                assert!(self.next(&back_ptr).is_none());
                assert!(self.prev(&back_ptr).is_none());
            }
            _ => {
                assert!(self.front().is_some());
                assert_ne!(self.0.ends().get(BACK_IDX), self.0.ends().get(FRONT_IDX));

                let mut fwd_pointers = alloc::vec![];
                let mut ptr = self.0.ends().get(FRONT_IDX).unwrap();
                fwd_pointers.push(ptr.clone());
                while let Some((next_ptr, next)) = self.next(&ptr) {
                    assert_eq!(next.prev().get(), Some(ptr));
                    ptr = next_ptr;
                    fwd_pointers.push(ptr.clone());
                }
                assert_eq!(fwd_pointers.len(), num_active_nodes);

                let mut bwd_pointers = alloc::vec![];
                let mut ptr = self.0.ends().get(BACK_IDX).unwrap();
                bwd_pointers.push(ptr.clone());
                while let Some((prev_ptr, prev)) = self.prev(&ptr) {
                    assert_eq!(prev.next().get(), Some(ptr));
                    ptr = prev_ptr;
                    bwd_pointers.push(ptr.clone());
                }

                bwd_pointers.reverse();
                assert_eq!(fwd_pointers, bwd_pointers);
            }
        }

        // data - fwd
        let mut iter = self.iter();

        assert_eq!(iter.next(), self.front());

        let mut maybe_ptr = self.0.ends().get(FRONT_IDX);
        for _ in 1..num_active_nodes {
            let ptr = maybe_ptr.clone().unwrap();
            maybe_ptr = self.next(&ptr).map(|x| x.0);

            let data = maybe_ptr
                .clone()
                .map(|p| unsafe { self.0.data_unchecked(&p) });
            assert_eq!(iter.next(), data);
        }
        assert!(iter.next().is_none());

        // data - bwd
        let mut iter = self.iter().rev();

        assert_eq!(iter.next(), self.back());

        let mut maybe_ptr = self.0.ends().get(BACK_IDX);
        for _ in 1..num_active_nodes {
            let ptr = maybe_ptr.clone().unwrap();
            maybe_ptr = self.prev(&ptr).map(|x| x.0);

            let data = maybe_ptr
                .clone()
                .map(|p| unsafe { self.0.data_unchecked(&p) });
            assert_eq!(iter.next(), data);
        }
        assert!(iter.next().is_none());
    }

    fn next(&self, ptr: &NodePtr<Doubly<T>>) -> Option<PtrAndNode<T>> {
        self.0.node(ptr).next().get().map(|p| {
            let next_node = self.0.node(&p);
            (p, next_node)
        })
    }

    fn prev(&self, ptr: &NodePtr<Doubly<T>>) -> Option<PtrAndNode<T>> {
        self.0.node(ptr).prev().get().map(|p| {
            let prev_node = self.0.node(&p);
            (p, prev_node)
        })
    }
}