1use crate::Error;
2
3#[derive(Debug, Clone)]
5pub struct DynamicArray<T> {
6 data: Vec<T>,
7}
8
9impl<T> DynamicArray<T> {
10 pub fn with_capacity(capacity: usize) -> Self {
12 Self {
13 data: Vec::with_capacity(capacity),
14 }
15 }
16
17 pub fn new() -> Self {
19 Self::with_capacity(10)
20 }
21
22 pub fn len(&self) -> usize {
24 self.data.len()
25 }
26
27 pub fn is_empty(&self) -> bool {
29 self.data.is_empty()
30 }
31
32 pub fn append(&mut self, value: T) {
34 self.data.push(value);
35 }
36
37 pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
39 if index > self.data.len() {
40 return Err(Error::OutOfBounds);
41 }
42 self.data.insert(index, value);
43 Ok(())
44 }
45
46 pub fn remove(&mut self, value: &T) -> Result<(), Error>
48 where
49 T: PartialEq,
50 {
51 if let Some(index) = self.data.iter().position(|x| x == value) {
52 self.data.remove(index);
53 Ok(())
54 } else {
55 Err(Error::NotFound)
56 }
57 }
58
59 pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
61 let idx = index.unwrap_or(self.data.len().saturating_sub(1));
62 if idx >= self.data.len() {
63 return Err(Error::OutOfBounds);
64 }
65 Ok(self.data.remove(idx))
66 }
67
68 pub fn get(&self, index: usize) -> Result<&T, Error> {
70 self.data.get(index).ok_or(Error::OutOfBounds)
71 }
72
73 pub fn set(&mut self, index: usize, value: T) -> Result<(), Error> {
75 if index >= self.data.len() {
76 return Err(Error::OutOfBounds);
77 }
78 self.data[index] = value;
79 Ok(())
80 }
81
82 pub fn to_vec(&self) -> Vec<T>
84 where
85 T: Clone,
86 {
87 self.data.clone()
88 }
89}
90
91impl<T> Default for DynamicArray<T> {
92 fn default() -> Self {
93 Self::new()
94 }
95}
96
97#[derive(Debug)]
98struct SNode<T> {
99 value: T,
100 next: Option<usize>,
101}
102
103#[derive(Debug)]
105pub struct SinglyLinkedList<T> {
106 nodes: Vec<SNode<T>>,
107 head: Option<usize>,
108 free: Vec<usize>,
109 len: usize,
110}
111
112impl<T> SinglyLinkedList<T> {
113 pub fn new() -> Self {
115 Self {
116 nodes: Vec::new(),
117 head: None,
118 free: Vec::new(),
119 len: 0,
120 }
121 }
122
123 pub fn len(&self) -> usize {
125 self.len
126 }
127
128 pub fn is_empty(&self) -> bool {
130 self.len == 0
131 }
132
133 fn alloc(&mut self, value: T) -> usize {
134 if let Some(index) = self.free.pop() {
135 self.nodes[index] = SNode { value, next: None };
136 index
137 } else {
138 self.nodes.push(SNode { value, next: None });
139 self.nodes.len() - 1
140 }
141 }
142
143 fn free_node(&mut self, index: usize) {
144 self.free.push(index);
145 }
146
147 fn node_at(&self, index: usize) -> Result<usize, Error> {
148 if index >= self.len {
149 return Err(Error::OutOfBounds);
150 }
151 let mut current = self.head.unwrap();
152 for _ in 0..index {
153 current = self.nodes[current].next.unwrap();
154 }
155 Ok(current)
156 }
157
158 pub fn append(&mut self, value: T) {
160 let index = self.alloc(value);
161 if let Some(tail_index) = self.tail() {
162 self.nodes[tail_index].next = Some(index);
163 } else {
164 self.head = Some(index);
165 }
166 self.len += 1;
167 }
168
169 fn tail(&self) -> Option<usize> {
170 let mut current = self.head?;
171 while let Some(next) = self.nodes[current].next {
172 current = next;
173 }
174 Some(current)
175 }
176
177 pub fn prepend(&mut self, value: T) {
179 let index = self.alloc(value);
180 self.nodes[index].next = self.head;
181 self.head = Some(index);
182 self.len += 1;
183 }
184
185 pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
187 if index > self.len {
188 return Err(Error::OutOfBounds);
189 }
190 if index == 0 {
191 self.prepend(value);
192 return Ok(());
193 }
194 let prev = self.node_at(index - 1)?;
195 let new_index = self.alloc(value);
196 self.nodes[new_index].next = self.nodes[prev].next;
197 self.nodes[prev].next = Some(new_index);
198 self.len += 1;
199 Ok(())
200 }
201
202 pub fn remove(&mut self, value: &T) -> Result<(), Error>
204 where
205 T: PartialEq,
206 {
207 let head = self.head.ok_or(Error::NotFound)?;
208 if &self.nodes[head].value == value {
209 let next = self.nodes[head].next;
210 self.free_node(head);
211 self.head = next;
212 self.len -= 1;
213 return Ok(());
214 }
215 let mut current = head;
216 while let Some(next) = self.nodes[current].next {
217 if &self.nodes[next].value == value {
218 self.nodes[current].next = self.nodes[next].next;
219 self.free_node(next);
220 self.len -= 1;
221 return Ok(());
222 }
223 current = next;
224 }
225 Err(Error::NotFound)
226 }
227
228 pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
230 if self.is_empty() {
231 return Err(Error::Empty);
232 }
233 let idx = index.unwrap_or(self.len - 1);
234 if idx >= self.len {
235 return Err(Error::OutOfBounds);
236 }
237 if idx == 0 {
238 let head = self.head.unwrap();
239 let value = std::mem::replace(&mut self.nodes[head].value, unsafe { std::mem::zeroed() });
240 let next = self.nodes[head].next;
241 self.free_node(head);
242 self.head = next;
243 self.len -= 1;
244 return Ok(value);
245 }
246 let prev = self.node_at(idx - 1)?;
247 let current = self.nodes[prev].next.unwrap();
248 let value = std::mem::replace(&mut self.nodes[current].value, unsafe { std::mem::zeroed() });
249 self.nodes[prev].next = self.nodes[current].next;
250 self.free_node(current);
251 self.len -= 1;
252 Ok(value)
253 }
254
255 pub fn get(&self, index: usize) -> Result<&T, Error> {
257 let node = self.node_at(index)?;
258 Ok(&self.nodes[node].value)
259 }
260
261 pub fn get_mut(&mut self, index: usize) -> Result<&mut T, Error> {
263 let node = self.node_at(index)?;
264 Ok(&mut self.nodes[node].value)
265 }
266
267 pub fn find(&self, value: &T) -> Result<usize, Error>
269 where
270 T: PartialEq,
271 {
272 let mut current = self.head;
273 let mut i = 0;
274 while let Some(idx) = current {
275 if &self.nodes[idx].value == value {
276 return Ok(i);
277 }
278 current = self.nodes[idx].next;
279 i += 1;
280 }
281 Err(Error::NotFound)
282 }
283
284 pub fn to_vec(&self) -> Vec<T>
286 where
287 T: Clone,
288 {
289 let mut result = Vec::with_capacity(self.len);
290 let mut current = self.head;
291 while let Some(idx) = current {
292 result.push(self.nodes[idx].value.clone());
293 current = self.nodes[idx].next;
294 }
295 result
296 }
297}
298
299impl<T> Default for SinglyLinkedList<T> {
300 fn default() -> Self {
301 Self::new()
302 }
303}
304
305#[derive(Debug)]
306struct DNode<T> {
307 value: T,
308 prev: Option<usize>,
309 next: Option<usize>,
310}
311
312#[derive(Debug)]
314pub struct DoublyLinkedList<T> {
315 nodes: Vec<DNode<T>>,
316 head: Option<usize>,
317 tail: Option<usize>,
318 free: Vec<usize>,
319 len: usize,
320}
321
322impl<T> DoublyLinkedList<T> {
323 pub fn new() -> Self {
325 Self {
326 nodes: Vec::new(),
327 head: None,
328 tail: None,
329 free: Vec::new(),
330 len: 0,
331 }
332 }
333
334 pub fn len(&self) -> usize {
336 self.len
337 }
338
339 pub fn is_empty(&self) -> bool {
341 self.len == 0
342 }
343
344 fn alloc(&mut self, value: T) -> usize {
345 if let Some(index) = self.free.pop() {
346 self.nodes[index] = DNode {
347 value,
348 prev: None,
349 next: None,
350 };
351 index
352 } else {
353 self.nodes.push(DNode {
354 value,
355 prev: None,
356 next: None,
357 });
358 self.nodes.len() - 1
359 }
360 }
361
362 fn free_node(&mut self, index: usize) {
363 self.free.push(index);
364 }
365
366 fn node_at(&self, index: usize) -> Result<usize, Error> {
367 if index >= self.len {
368 return Err(Error::OutOfBounds);
369 }
370 if index <= self.len / 2 {
371 let mut current = self.head.unwrap();
372 for _ in 0..index {
373 current = self.nodes[current].next.unwrap();
374 }
375 Ok(current)
376 } else {
377 let mut current = self.tail.unwrap();
378 for _ in 0..self.len - index - 1 {
379 current = self.nodes[current].prev.unwrap();
380 }
381 Ok(current)
382 }
383 }
384
385 pub fn append(&mut self, value: T) {
387 let index = self.alloc(value);
388 if let Some(tail) = self.tail {
389 self.nodes[tail].next = Some(index);
390 self.nodes[index].prev = Some(tail);
391 self.tail = Some(index);
392 } else {
393 self.head = Some(index);
394 self.tail = Some(index);
395 }
396 self.len += 1;
397 }
398
399 pub fn prepend(&mut self, value: T) {
401 let index = self.alloc(value);
402 if let Some(head) = self.head {
403 self.nodes[head].prev = Some(index);
404 self.nodes[index].next = Some(head);
405 self.head = Some(index);
406 } else {
407 self.head = Some(index);
408 self.tail = Some(index);
409 }
410 self.len += 1;
411 }
412
413 pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
415 if index > self.len {
416 return Err(Error::OutOfBounds);
417 }
418 if index == 0 {
419 self.prepend(value);
420 return Ok(());
421 }
422 if index == self.len {
423 self.append(value);
424 return Ok(());
425 }
426 let next = self.node_at(index)?;
427 let prev = self.nodes[next].prev.unwrap();
428 let new_index = self.alloc(value);
429 self.nodes[new_index].prev = Some(prev);
430 self.nodes[new_index].next = Some(next);
431 self.nodes[prev].next = Some(new_index);
432 self.nodes[next].prev = Some(new_index);
433 self.len += 1;
434 Ok(())
435 }
436
437 pub fn remove(&mut self, value: &T) -> Result<(), Error>
439 where
440 T: PartialEq,
441 {
442 let mut current = self.head;
443 while let Some(idx) = current {
444 if &self.nodes[idx].value == value {
445 self.remove_node(idx);
446 return Ok(());
447 }
448 current = self.nodes[idx].next;
449 }
450 Err(Error::NotFound)
451 }
452
453 fn remove_node(&mut self, index: usize) {
454 let prev = self.nodes[index].prev;
455 let next = self.nodes[index].next;
456 if let Some(p) = prev {
457 self.nodes[p].next = next;
458 } else {
459 self.head = next;
460 }
461 if let Some(n) = next {
462 self.nodes[n].prev = prev;
463 } else {
464 self.tail = prev;
465 }
466 self.free_node(index);
467 self.len -= 1;
468 }
469
470 pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
472 if self.is_empty() {
473 return Err(Error::Empty);
474 }
475 let idx = index.unwrap_or(self.len - 1);
476 if idx >= self.len {
477 return Err(Error::OutOfBounds);
478 }
479 let node = self.node_at(idx)?;
480 let value = std::mem::replace(&mut self.nodes[node].value, unsafe { std::mem::zeroed() });
481 self.remove_node(node);
482 Ok(value)
483 }
484
485 pub fn get(&self, index: usize) -> Result<&T, Error> {
487 let node = self.node_at(index)?;
488 Ok(&self.nodes[node].value)
489 }
490
491 pub fn get_mut(&mut self, index: usize) -> Result<&mut T, Error> {
493 let node = self.node_at(index)?;
494 Ok(&mut self.nodes[node].value)
495 }
496
497 pub fn to_vec(&self) -> Vec<T>
499 where
500 T: Clone,
501 {
502 let mut result = Vec::with_capacity(self.len);
503 let mut current = self.head;
504 while let Some(idx) = current {
505 result.push(self.nodes[idx].value.clone());
506 current = self.nodes[idx].next;
507 }
508 result
509 }
510}
511
512impl<T> Default for DoublyLinkedList<T> {
513 fn default() -> Self {
514 Self::new()
515 }
516}
517
518#[derive(Debug)]
519struct CNode<T> {
520 value: T,
521 next: Option<usize>,
522}
523
524#[derive(Debug)]
526pub struct CircularLinkedList<T> {
527 nodes: Vec<CNode<T>>,
528 tail: Option<usize>,
529 free: Vec<usize>,
530 len: usize,
531}
532
533impl<T> CircularLinkedList<T> {
534 pub fn new() -> Self {
536 Self {
537 nodes: Vec::new(),
538 tail: None,
539 free: Vec::new(),
540 len: 0,
541 }
542 }
543
544 pub fn len(&self) -> usize {
546 self.len
547 }
548
549 pub fn is_empty(&self) -> bool {
551 self.len == 0
552 }
553
554 fn alloc(&mut self, value: T) -> usize {
555 if let Some(index) = self.free.pop() {
556 self.nodes[index] = CNode { value, next: None };
557 index
558 } else {
559 self.nodes.push(CNode { value, next: None });
560 self.nodes.len() - 1
561 }
562 }
563
564 fn free_node(&mut self, index: usize) {
565 self.free.push(index);
566 }
567
568 pub fn append(&mut self, value: T) {
570 let index = self.alloc(value);
571 if let Some(tail) = self.tail {
572 let head = self.nodes[tail].next.unwrap();
573 self.nodes[tail].next = Some(index);
574 self.nodes[index].next = Some(head);
575 self.tail = Some(index);
576 } else {
577 self.nodes[index].next = Some(index);
578 self.tail = Some(index);
579 }
580 self.len += 1;
581 }
582
583 pub fn prepend(&mut self, value: T) {
585 let index = self.alloc(value);
586 if let Some(tail) = self.tail {
587 let head = self.nodes[tail].next.unwrap();
588 self.nodes[tail].next = Some(index);
589 self.nodes[index].next = Some(head);
590 } else {
591 self.nodes[index].next = Some(index);
592 self.tail = Some(index);
593 }
594 self.len += 1;
595 }
596
597 pub fn remove(&mut self, value: &T) -> Result<(), Error>
599 where
600 T: PartialEq,
601 {
602 let tail = self.tail.ok_or(Error::NotFound)?;
603 let head = self.nodes[tail].next.unwrap();
604 if &self.nodes[head].value == value {
605 if head == tail {
606 self.tail = None;
607 } else {
608 self.nodes[tail].next = self.nodes[head].next;
609 }
610 self.free_node(head);
611 self.len -= 1;
612 return Ok(());
613 }
614 let mut current = head;
615 for _ in 0..self.len - 1 {
616 if &self.nodes[self.nodes[current].next.unwrap()].value == value {
617 let to_remove = self.nodes[current].next.unwrap();
618 let after = self.nodes[to_remove].next;
619 self.nodes[current].next = after;
620 if to_remove == tail {
621 self.tail = Some(current);
622 }
623 self.free_node(to_remove);
624 self.len -= 1;
625 return Ok(());
626 }
627 current = self.nodes[current].next.unwrap();
628 }
629 Err(Error::NotFound)
630 }
631
632 pub fn to_vec(&self) -> Vec<T>
634 where
635 T: Clone,
636 {
637 if self.is_empty() {
638 return Vec::new();
639 }
640 let mut result = Vec::with_capacity(self.len);
641 let tail = self.tail.unwrap();
642 let start = self.nodes[tail].next.unwrap();
643 let mut current = start;
644 loop {
645 result.push(self.nodes[current].value.clone());
646 current = self.nodes[current].next.unwrap();
647 if current == start {
648 break;
649 }
650 }
651 result
652 }
653}
654
655impl<T> Default for CircularLinkedList<T> {
656 fn default() -> Self {
657 Self::new()
658 }
659}
660
661#[derive(Debug, Clone)]
663pub struct Stack<T> {
664 items: Vec<T>,
665}
666
667impl<T> Stack<T> {
668 pub fn new() -> Self {
670 Self { items: Vec::new() }
671 }
672
673 pub fn len(&self) -> usize {
675 self.items.len()
676 }
677
678 pub fn is_empty(&self) -> bool {
680 self.items.is_empty()
681 }
682
683 pub fn push(&mut self, value: T) {
685 self.items.push(value);
686 }
687
688 pub fn pop(&mut self) -> Result<T, Error> {
690 self.items.pop().ok_or(Error::Empty)
691 }
692
693 pub fn peek(&self) -> Result<&T, Error> {
695 self.items.last().ok_or(Error::Empty)
696 }
697
698 pub fn to_vec(&self) -> Vec<T>
700 where
701 T: Clone,
702 {
703 self.items.iter().rev().cloned().collect()
704 }
705}
706
707impl<T> Default for Stack<T> {
708 fn default() -> Self {
709 Self::new()
710 }
711}
712
713#[derive(Debug, Clone)]
715pub struct Queue<T> {
716 items: std::collections::VecDeque<T>,
717}
718
719impl<T> Queue<T> {
720 pub fn new() -> Self {
722 Self {
723 items: std::collections::VecDeque::new(),
724 }
725 }
726
727 pub fn len(&self) -> usize {
729 self.items.len()
730 }
731
732 pub fn is_empty(&self) -> bool {
734 self.items.is_empty()
735 }
736
737 pub fn enqueue(&mut self, value: T) {
739 self.items.push_back(value);
740 }
741
742 pub fn dequeue(&mut self) -> Result<T, Error> {
744 self.items.pop_front().ok_or(Error::Empty)
745 }
746
747 pub fn peek(&self) -> Result<&T, Error> {
749 self.items.front().ok_or(Error::Empty)
750 }
751
752 pub fn to_vec(&self) -> Vec<T>
754 where
755 T: Clone,
756 {
757 self.items.iter().cloned().collect()
758 }
759}
760
761impl<T> Default for Queue<T> {
762 fn default() -> Self {
763 Self::new()
764 }
765}