competitive/data_structure/
doubly_linked_list.rs

1/// Manages only prev/next links of indices.
2///
3/// `usize::MAX` means no previous or next index.
4#[derive(Debug, Clone)]
5pub struct DoublyLinkedList {
6    prev: Vec<usize>,
7    next: Vec<usize>,
8}
9
10impl DoublyLinkedList {
11    pub fn new(n: usize) -> Self {
12        Self {
13            prev: vec![usize::MAX; n],
14            next: vec![usize::MAX; n],
15        }
16    }
17
18    pub fn len(&self) -> usize {
19        self.prev.len()
20    }
21
22    pub fn is_empty(&self) -> bool {
23        self.len() == 0
24    }
25
26    pub fn prev(&self, index: usize) -> usize {
27        self.prev[index]
28    }
29
30    pub fn next(&self, index: usize) -> usize {
31        self.next[index]
32    }
33
34    /// Links `front` immediately before `back`.
35    ///
36    /// Panics if `front == back`, `front` already has a next index, or `back` already has a
37    /// previous index.
38    pub fn link(&mut self, front: usize, back: usize) {
39        assert_ne!(front, back);
40        assert_eq!(self.next[front], usize::MAX);
41        assert_eq!(self.prev[back], usize::MAX);
42        self.next[front] = back;
43        self.prev[back] = front;
44    }
45
46    pub fn cut_before(&mut self, index: usize) -> usize {
47        let prev = self.prev[index];
48        if prev != usize::MAX {
49            self.next[prev] = usize::MAX;
50            self.prev[index] = usize::MAX;
51        }
52        prev
53    }
54
55    pub fn cut_after(&mut self, index: usize) -> usize {
56        let next = self.next[index];
57        if next != usize::MAX {
58            self.prev[next] = usize::MAX;
59            self.next[index] = usize::MAX;
60        }
61        next
62    }
63
64    pub fn detach(&mut self, index: usize) -> (usize, usize) {
65        let prev = self.cut_before(index);
66        let next = self.cut_after(index);
67        if prev != usize::MAX && next != usize::MAX {
68            self.link(prev, next);
69        }
70        (prev, next)
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use crate::tools::Xorshift;
78
79    #[test]
80    fn test_doubly_linked_list_random() {
81        const CASES: usize = 200;
82        const Q: usize = 200;
83
84        let mut rng = Xorshift::default();
85        for _ in 0..CASES {
86            let n = rng.random(0..=30);
87            let mut list = DoublyLinkedList::new(n);
88            let mut lists: Vec<Vec<_>> = (0..n).map(|i| vec![i]).collect();
89            let position = |lists: &[Vec<usize>], v| {
90                lists
91                    .iter()
92                    .enumerate()
93                    .find_map(|(i, list)| list.iter().position(|&u| u == v).map(|j| (i, j)))
94                    .unwrap()
95            };
96            assert_eq!(list.is_empty(), n == 0);
97
98            for _ in 0..Q {
99                if n == 0 {
100                    continue;
101                }
102
103                match rng.random(0..4) {
104                    0 if lists.len() >= 2 => {
105                        let mut a = rng.random(0..lists.len());
106                        let mut b = rng.random(0..lists.len() - 1);
107                        if a <= b {
108                            b += 1;
109                        }
110                        let front = *lists[a].last().unwrap();
111                        let back = lists[b][0];
112                        list.link(front, back);
113
114                        let other = lists.remove(b);
115                        if b < a {
116                            a -= 1;
117                        }
118                        lists[a].extend(other);
119                    }
120                    1 => {
121                        let v = rng.random(0..n);
122                        let (i, j) = position(&lists, v);
123                        let prev = if j == 0 { usize::MAX } else { lists[i][j - 1] };
124                        assert_eq!(list.cut_before(v), prev);
125                        if j != 0 {
126                            let right = lists[i].split_off(j);
127                            lists.push(right);
128                        }
129                    }
130                    2 => {
131                        let v = rng.random(0..n);
132                        let (i, j) = position(&lists, v);
133                        let next = if j + 1 == lists[i].len() {
134                            usize::MAX
135                        } else {
136                            lists[i][j + 1]
137                        };
138                        assert_eq!(list.cut_after(v), next);
139                        if j + 1 != lists[i].len() {
140                            let right = lists[i].split_off(j + 1);
141                            lists.push(right);
142                        }
143                    }
144                    _ => {
145                        let v = rng.random(0..n);
146                        let (i, j) = position(&lists, v);
147                        let prev = if j == 0 { usize::MAX } else { lists[i][j - 1] };
148                        let next = if j + 1 == lists[i].len() {
149                            usize::MAX
150                        } else {
151                            lists[i][j + 1]
152                        };
153                        assert_eq!(list.detach(v), (prev, next));
154                        lists[i].remove(j);
155                        if lists[i].is_empty() {
156                            lists.swap_remove(i);
157                        }
158                        lists.push(vec![v]);
159                    }
160                }
161
162                let mut prev = vec![usize::MAX; n];
163                let mut next = vec![usize::MAX; n];
164                for row in &lists {
165                    for (i, &v) in row.iter().enumerate() {
166                        if i != 0 {
167                            prev[v] = row[i - 1];
168                        }
169                        if i + 1 != row.len() {
170                            next[v] = row[i + 1];
171                        }
172                    }
173                }
174                for i in 0..n {
175                    assert_eq!(list.prev(i), prev[i]);
176                    assert_eq!(list.next(i), next[i]);
177                }
178            }
179        }
180    }
181}
competitive/data_structure/doubly_linked_list.rs

competitive/data_structure/
doubly_linked_list.rs
