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