Skip to main content

data_structures_lib/
linear.rs

1use crate::Error;
2
3/// A dynamic array backed by a Vec.
4#[derive(Debug, Clone)]
5pub struct DynamicArray<T> {
6    data: Vec<T>,
7}
8
9impl<T> DynamicArray<T> {
10    /// Creates a new DynamicArray with the given capacity.
11    pub fn with_capacity(capacity: usize) -> Self {
12        Self {
13            data: Vec::with_capacity(capacity),
14        }
15    }
16
17    /// Creates a new DynamicArray with a default capacity.
18    pub fn new() -> Self {
19        Self::with_capacity(10)
20    }
21
22    /// Returns the number of elements.
23    pub fn len(&self) -> usize {
24        self.data.len()
25    }
26
27    /// Returns true if the array is empty.
28    pub fn is_empty(&self) -> bool {
29        self.data.is_empty()
30    }
31
32    /// Appends a value.
33    pub fn append(&mut self, value: T) {
34        self.data.push(value);
35    }
36
37    /// Inserts a value at the given index.
38    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    /// Removes the first occurrence of a value.
47    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    /// Removes and returns the item at the given index, defaulting to the last.
60    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    /// Returns the item at index.
72    pub fn get(&self, index: usize) -> Result<&T, Error> {
73        self.data.get(index).ok_or(Error::OutOfBounds)
74    }
75
76    /// Sets the item at index.
77    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    /// Returns a Vec of all elements.
86    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/// A singly linked list.
107#[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    /// Creates a new SinglyLinkedList.
117    pub fn new() -> Self {
118        Self {
119            nodes: Vec::new(),
120            head: None,
121            free: Vec::new(),
122            len: 0,
123        }
124    }
125
126    /// Returns the number of elements.
127    pub fn len(&self) -> usize {
128        self.len
129    }
130
131    /// Returns true if the list is empty.
132    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    /// Appends a value.
170    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    /// Prepends a value.
189    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    /// Inserts a value at the given index.
197    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    /// Removes the first occurrence of a value.
214    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    /// Removes and returns the item at the given index, defaulting to the last.
240    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    /// Returns the item at index.
267    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    /// Returns a mutable reference to the item at index.
273    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    /// Returns the index of the first occurrence of a value.
279    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    /// Returns a Vec of all values.
296    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/// A doubly linked list.
324#[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    /// Creates a new DoublyLinkedList.
335    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    /// Returns the number of elements.
346    pub fn len(&self) -> usize {
347        self.len
348    }
349
350    /// Returns true if the list is empty.
351    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    /// Appends a value.
400    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    /// Prepends a value.
414    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    /// Inserts a value at the given index.
428    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    /// Removes the first occurrence of a value.
452    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    /// Removes and returns the item at the given index, defaulting to the last.
485    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    /// Returns the item at index.
500    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    /// Returns a mutable reference to the item at index.
506    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    /// Returns a Vec of all values.
512    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/// A circular linked list.
539#[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    /// Creates a new CircularLinkedList.
549    pub fn new() -> Self {
550        Self {
551            nodes: Vec::new(),
552            tail: None,
553            free: Vec::new(),
554            len: 0,
555        }
556    }
557
558    /// Returns the number of elements.
559    pub fn len(&self) -> usize {
560        self.len
561    }
562
563    /// Returns true if the list is empty.
564    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    /// Appends a value.
591    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    /// Prepends a value.
606    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    /// Removes the first occurrence of a value.
620    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    /// Returns a Vec of all values.
655    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/// A LIFO stack.
684#[derive(Debug, Clone)]
685pub struct Stack<T> {
686    items: Vec<T>,
687}
688
689impl<T> Stack<T> {
690    /// Creates a new Stack.
691    pub fn new() -> Self {
692        Self { items: Vec::new() }
693    }
694
695    /// Returns the number of elements.
696    pub fn len(&self) -> usize {
697        self.items.len()
698    }
699
700    /// Returns true if the stack is empty.
701    pub fn is_empty(&self) -> bool {
702        self.items.is_empty()
703    }
704
705    /// Pushes a value.
706    pub fn push(&mut self, value: T) {
707        self.items.push(value);
708    }
709
710    /// Pops and returns the top value.
711    pub fn pop(&mut self) -> Result<T, Error> {
712        self.items.pop().ok_or(Error::Empty)
713    }
714
715    /// Returns the top value without removing it.
716    pub fn peek(&self) -> Result<&T, Error> {
717        self.items.last().ok_or(Error::Empty)
718    }
719
720    /// Returns a Vec from top to bottom.
721    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/// A FIFO queue.
736#[derive(Debug, Clone)]
737pub struct Queue<T> {
738    items: std::collections::VecDeque<T>,
739}
740
741impl<T> Queue<T> {
742    /// Creates a new Queue.
743    pub fn new() -> Self {
744        Self {
745            items: std::collections::VecDeque::new(),
746        }
747    }
748
749    /// Returns the number of elements.
750    pub fn len(&self) -> usize {
751        self.items.len()
752    }
753
754    /// Returns true if the queue is empty.
755    pub fn is_empty(&self) -> bool {
756        self.items.is_empty()
757    }
758
759    /// Enqueues a value.
760    pub fn enqueue(&mut self, value: T) {
761        self.items.push_back(value);
762    }
763
764    /// Dequeues and returns the front value.
765    pub fn dequeue(&mut self) -> Result<T, Error> {
766        self.items.pop_front().ok_or(Error::Empty)
767    }
768
769    /// Returns the front value without removing it.
770    pub fn peek(&self) -> Result<&T, Error> {
771        self.items.front().ok_or(Error::Empty)
772    }
773
774    /// Returns a Vec of all values.
775    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}