1pub struct ArenaList<T> {
13 pub nodes: Vec<Option<T>>,
14 pub nexts: Vec<Option<usize>>,
16 pub holes: Vec<usize>,
18 }
20
21impl<T> ArenaList<T> {
22 fn new() -> Self {
23 Self {
24 nodes: Vec::new(),
25 nexts: Vec::new(),
26 holes: Vec::new(),
27 }
28 }
29
30 fn make_node(&mut self, data: Option<T>) -> usize {
32 match self.holes.pop() {
33 Some(new_idx) => {
35 self.nodes[new_idx] = data;
36 self.nexts[new_idx] = None;
37 new_idx
38 }
39 None => {
41 self.nodes.push(data);
42 self.nexts.push(None);
43 self.nexts.len() - 1
44 }
45 }
46 }
47}
48
49pub struct LinkedList<'a, T> {
50 root: usize,
51 owner: &'a mut ArenaList<T>,
53}
54
55impl<'a, T> LinkedList<'a, T> {
56 fn from_vec(arena_list: &'a mut ArenaList<T>, vec1: Vec<T>) -> Self {
57 let dummy = arena_list.make_node(None);
58 let mut prev = dummy;
59 for data in vec1 {
60 let curr = arena_list.make_node(Some(data));
61 arena_list.nexts[prev] = Some(curr);
62 prev = curr;
63 }
64
65 Self {
66 root: dummy,
67 owner: arena_list,
68 }
69 }
70
71 fn clear() {}
72
73
74 fn to_vec(&self) -> Vec<&T> {
75 let mut res = Vec::new();
76 let mut curr_idx = self.root;
77 loop {
78 match self.owner.nexts[curr_idx] {
79 Some(next_idx) => {
80 match &self.owner.nodes[next_idx] {
82 Some(node_data) => res.push(node_data),
83 None => break
84 }
85 curr_idx = next_idx;
86 }
87 None => break
88 }
89 }
90 res
91 }
92
93 fn get(&self, mut num: usize) -> &Option<T> {
94 let mut curr_idx = self.root;
95 loop {
96 match self.owner.nexts[curr_idx] {
97 Some(next_idx) => {
98 if num == 0 {
99 return &self.owner.nodes[next_idx];
100 }
101 curr_idx = next_idx;
102 num -= 1;
103 }
104 None => { return &None; }
105 }
106 }
107 }
108
109 fn insert(&mut self, mut num: usize, data: T) {
110 let new_idx = self.owner.make_node(Some(data));
111 let mut curr_idx = self.root;
112 loop {
113 match self.owner.nexts[curr_idx] {
114 Some(next_idx) => {
115 if num == 0 {
116 self.owner.nexts[new_idx] = Some(next_idx);
117 self.owner.nexts[curr_idx] = Some(new_idx);
118 curr_idx = new_idx;
119 break;
120 }
121 curr_idx = next_idx;
122 num -= 1;
123 }
124 None => break
125 }
126 }
127 }
128
129
130 fn del(&mut self, mut num: usize) -> bool {
131 let mut curr_idx = self.root;
132 loop {
133 match self.owner.nexts[curr_idx] {
134 Some(next_idx) => {
135 if num == 0 {
136 self.owner.nexts[curr_idx] = self.owner.nexts[next_idx];
137 self.owner.nexts[next_idx] = None;
138 self.owner.nodes[next_idx] = None;
139 self.owner.holes.push(next_idx);
140 return true;
141 }
142 curr_idx = next_idx;
143 num -= 1;
144 }
145 None => {
146 return false;
147 }
148 }
149 }
150 }
151}
152
153impl<'a, T> LinkedList<'a, T> {
154 fn split(&mut self, mut num: usize) -> LinkedList<T> {
157 let dummy = self.owner.make_node(None);
158 let mut curr_idx = self.root;
159 loop {
160 match self.owner.nexts[curr_idx] {
161 Some(next_idx) => {
162 if num == 0 {
163 self.owner.nexts[dummy] = Some(next_idx);
164 self.owner.nexts[curr_idx] = None;
165 break;
166 }
167 curr_idx = next_idx;
168 num -= 1;
169 }
170 None => { break; }
171 }
172 }
173 LinkedList { root: dummy, owner: self.owner }
174 }
175}
176
177#[cfg(test)]
178mod tests {
179 use crate::linked_list::{ArenaList, LinkedList};
180
181 #[test]
182 fn test1() {
183 let mut arena_list = ArenaList::new();
184 let vec1 = vec![1, 2, 3, 4, 5, 6];
185 let mut linked_list = LinkedList::from_vec(&mut arena_list, vec1);
186 println!("{:?}", linked_list.to_vec());
187 linked_list.insert(3, 9);
188 linked_list.insert(0, 99);
189 println!("{:?}", linked_list.to_vec());
190 println!("index = {}, val = {:?}", 0, linked_list.get(0));
191 println!("index = {}, val = {:?}", 3, linked_list.get(3));
192 println!("index = {}, val = {:?}", 8, linked_list.get(8));
193 linked_list.del(3);
194 linked_list.del(2);
195 println!("{:?}", linked_list.to_vec());
196 }
197
198 #[test]
199 fn test2() {
200 let mut arena_list = ArenaList::new();
201 let vec1 = vec![1, 2, 3, 4, 5, 6];
202 let mut linked_list1 = LinkedList::from_vec(&mut arena_list, vec1);
203 let mut linked_list2 = linked_list1.split(3);
204 println!("{:?}", linked_list2.to_vec());
205 println!("{:?}", linked_list1.to_vec());
206 }
208}
209
210
211