haar_lib/ds/
linked_list.rs

1//! 連結リスト
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc225/tasks/abc225_d>
5
6#[derive(Clone)]
7/// 連結リストの内部ノード
8pub struct Node<T> {
9    /// `Node`がもつ値
10    pub value: T,
11    prev: Option<usize>,
12    next: Option<usize>,
13}
14
15impl<T> Node<T> {
16    fn new(value: T) -> Self {
17        Self {
18            value,
19            prev: None,
20            next: None,
21        }
22    }
23}
24
25#[derive(Clone, Default)]
26/// 複数の連結リストをまとめたもの
27pub struct LinkedListPool<T> {
28    data: Vec<Node<T>>,
29}
30
31impl<T> LinkedListPool<T> {
32    /// `LinkedListPool`を生成する。
33    pub fn new() -> Self {
34        Self { data: vec![] }
35    }
36
37    /// `prev`の後ろに`next`を接続する。
38    pub fn concat(&mut self, prev: usize, next: usize) -> bool {
39        if self.data[prev].next.is_none() && self.data[next].prev.is_none() {
40            self.data[prev].next = Some(next);
41            self.data[next].prev = Some(prev);
42            true
43        } else {
44            false
45        }
46    }
47
48    /// `cur`の前でリストを切断する。
49    pub fn split_before(&mut self, cur: usize) {
50        if let Some(prev) = self.data[cur].prev.take() {
51            self.data[prev].next = None;
52        }
53    }
54
55    /// `cur`の後ろでリストを切断する。
56    pub fn split_after(&mut self, cur: usize) {
57        if let Some(next) = self.data[cur].next.take() {
58            self.data[next].prev = None;
59        }
60    }
61
62    /// `cur`の次の要素
63    pub fn next_of(&self, cur: usize) -> Option<usize> {
64        self.data[cur].next
65    }
66
67    /// `cur`の前の要素
68    pub fn prev_of(&self, cur: usize) -> Option<usize> {
69        self.data[cur].prev
70    }
71
72    /// `value`を値としてもつ単一要素の連結リストを追加する。
73    pub fn push(&mut self, value: T) {
74        self.data.push(Node::new(value));
75    }
76
77    /// `cur`が属する連結リストの先頭を返す。
78    ///
79    /// **Time complexity** $O(n)$
80    pub fn first_of(&self, mut cur: usize) -> usize {
81        while let Some(prev) = self.data[cur].prev {
82            cur = prev;
83        }
84        cur
85    }
86
87    /// `cur`が属する連結リストの末尾を返す。
88    ///
89    /// **Time complexity** $O(n)$
90    pub fn last_of(&self, mut cur: usize) -> usize {
91        while let Some(next) = self.data[cur].next {
92            cur = next;
93        }
94        cur
95    }
96
97    /// `cur`から`cur`の属する連結リストの終端までの要素の参照を返すイテレータを返す。
98    pub fn iter(&self, cur: usize) -> impl Iterator<Item = &T> {
99        let mut cur = Some(cur);
100        std::iter::from_fn(move || match cur {
101            Some(c) => {
102                cur = self.data[c].next;
103                Some(&self.data[c].value)
104            }
105            _ => None,
106        })
107    }
108
109    /// `cur`から`cur`の属する連結リストの先頭までの要素の参照を返すイテレータを返す。
110    pub fn riter(&self, cur: usize) -> impl Iterator<Item = &T> {
111        let mut cur = Some(cur);
112        std::iter::from_fn(move || match cur {
113            Some(c) => {
114                cur = self.data[c].prev;
115                Some(&self.data[c].value)
116            }
117            _ => None,
118        })
119    }
120}
haar_lib/ds/linked_list.rs

haar_lib/ds/
linked_list.rs
