rust_algo/
double_linked_list.rs1pub struct Node<T> {
2 data: Option<T>,
3 pub next_idx: Option<usize>,
4 pub prev_idx: Option<usize>,
5}
6
7pub struct ArenaList<T> {
8 pub nodes: Vec<Node<T>>,
9 pub len: usize,
10}
11
12
13pub struct DoubleLinkedList<'a, T> {
14 pub root_idx: usize,
15 owner: &'a mut ArenaList<T>,
16}
17
18
19impl<T> ArenaList<T> {
20 pub fn new() -> Self {
21 Self {
22 nodes: Vec::new(),
23 len: 0,
24 }
25 }
26
27 fn clear(&mut self) {
28 self.nodes.clear();
29 }
30
31 fn add_node(&mut self, data: Option<T>) -> usize {
33 self.nodes.push(
34 Node { data, next_idx: None, prev_idx: None }
35 );
36 self.len += 1;
37 self.len - 1
38 }
39
40 fn add_link(&mut self, src_idx: usize, dst_idx: usize) {
42 self.nodes[src_idx].next_idx = Some(dst_idx);
43 self.nodes[dst_idx].prev_idx = Some(src_idx);
44 }
45
46 fn get_node(&self, idx: usize) -> &Node<T> {
48 return &self.nodes[idx];
49 }
50
51
52 fn del_node(&mut self, idx: usize) -> bool {
54 if idx >= self.nodes.len() {
55 return false;
56 }
57
58 let last_idx = self.nodes.len() - 1;
59
60 let mut node_to_del = self.nodes.swap_remove(idx);
61
62 let src_idx = node_to_del.prev_idx;
64 let dst_idx = node_to_del.next_idx;
65
66
67 match node_to_del.prev_idx {
69 None => { panic!("不可能") }
70 Some(prev_idx) => {
71 if prev_idx == last_idx {
72 self.nodes[idx].next_idx = dst_idx;
74 } else {
75 self.nodes[prev_idx].next_idx = dst_idx;
76 }
77 }
78 }
79
80 match node_to_del.next_idx {
82 None => {}
83 Some(next_idx) => {
84 if next_idx == last_idx {
85 self.nodes[idx].prev_idx = src_idx;
86 } else {
87 self.nodes[next_idx].prev_idx = src_idx;
88 }
89 }
90 }
91
92 if idx == last_idx {
93 return true;
94 }
95
96
97 match self.nodes[idx].prev_idx {
99 None => {}
100 Some(prev_idx) => {
101 if prev_idx == last_idx {
102 self.nodes[idx].next_idx = Some(idx);
104 } else { self.nodes[prev_idx].next_idx = Some(idx); }
105 }
106 }
107
108 match self.nodes[idx].next_idx {
109 None => {}
110 Some(next_idx) => {
111 if next_idx == last_idx {
112 self.nodes[idx].prev_idx = Some(idx)
113 } else { self.nodes[next_idx].prev_idx = Some(idx); }
114 }
115 }
116
117
118 self.len -= 1;
119 true
120 }
121}
122
123impl<'a, T> DoubleLinkedList<'a, T> {
124 pub fn new(arena_list: &'a mut ArenaList<T>) -> Self {
125 let mut res = Self {
126 root_idx: 0,
127 owner: arena_list,
128 };
129 res.owner.add_node(None);
130 res
131 }
132
133 pub fn from_vec(arena_list: &'a mut ArenaList<T>, vec1: Vec<T>) -> DoubleLinkedList<T> {
134 let mut res = Self {
135 root_idx: arena_list.len,
136 owner: arena_list,
137 };
138
139 let mut curr_idx = res.root_idx;
140 res.owner.add_node(None);for data in vec1 {
144 let next_idx = res.owner.add_node(Some(data));
145 res.owner.nodes[curr_idx].next_idx = Some(next_idx);
146 res.owner.nodes[next_idx].prev_idx = Some(curr_idx);
147 curr_idx = next_idx
148 }
149 res
150 }
151
152 pub fn to_vec(&self) -> Vec<&T> {
153 let mut curr_idx = self.root_idx;
154
155 let mut res = Vec::new();
156 loop {
157 match self.owner.nodes[curr_idx].next_idx {
158 None => { break; }
159 Some(next_idx) => {
160 match &self.owner.nodes[next_idx].data {
161 None => { break; }
162 Some(data) => { res.push(data); }
163 }
164 curr_idx = next_idx;
165 }
166 }
167 }
168 res
169 }
170
171
172 pub fn add_node(&mut self, data: Option<T>) -> usize {
174 self.owner.add_node(data)
175 }
176
177
178 pub fn get_node_by_idx(&self, idx: usize) -> &Node<T> {
180 return self.owner.get_node(idx);
181 }
182
183
184 pub fn insert(&mut self, mut num: usize, data: T) {
185 let mut curr_idx = self.root_idx;
186 let new_idx = self.add_node(Some(data));
187
188 loop {
189 if num <= 0 {
190 match self.owner.nodes[curr_idx].next_idx {
191 None => {}
192 Some(next_idx) => {
193 self.owner.add_link(new_idx, next_idx);
194 }
195 }
196 self.owner.add_link(curr_idx, new_idx);
197
198 break;
199 }
200
201 match self.owner.nodes[curr_idx].next_idx {
202 None => break,
203 Some(next_idx) => {
204 curr_idx = next_idx;
205 }
206 }
207
208 num -= 1;
209 }
210 }
211
212 pub fn get(&self, mut num: usize) -> Option<&T> {
213 let mut curr_idx = self.root_idx;
214 loop {
215 if num <= 0 {
216 match self.owner.nodes[curr_idx].next_idx {
217 None => { return None; }
218 Some(next_idx) => {
219 return Option::from(&self.owner.nodes[next_idx].data);
220 }
221 }
222 }
223 match self.owner.nodes[curr_idx].next_idx {
224 None => { return None; }
225 Some(next_idx) => {
226 curr_idx = next_idx;
227 }
228 }
229 num -= 1;
230 }
231 }
232
233 pub fn del(&mut self, mut num: usize) {
234 let mut curr_idx = self.root_idx;
235 loop {
236 if num <= 0 {
237 match self.owner.nodes[curr_idx].next_idx {
238 None => return,
239 Some(next_idx) => { self.owner.del_node(next_idx); }
240 }
241 return;
242 }
243 match self.owner.nodes[curr_idx].next_idx {
244 None => { return; }
245 Some(next_idx) => curr_idx = next_idx
246 }
247 num -= 1;
248 }
249 }
250}