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        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    /// Returns the item at index.
69    pub fn get(&self, index: usize) -> Result<&T, Error> {
70        self.data.get(index).ok_or(Error::OutOfBounds)
71    }
72
73    /// Sets the item at index.
74    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    /// Returns a Vec of all elements.
83    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/// A singly linked list.
104#[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    /// Creates a new SinglyLinkedList.
114    pub fn new() -> Self {
115        Self {
116            nodes: Vec::new(),
117            head: None,
118            free: Vec::new(),
119            len: 0,
120        }
121    }
122
123    /// Returns the number of elements.
124    pub fn len(&self) -> usize {
125        self.len
126    }
127
128    /// Returns true if the list is empty.
129    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    /// Appends a value.
159    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    /// Prepends a value.
178    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    /// Inserts a value at the given index.
186    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    /// Removes the first occurrence of a value.
203    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    /// Removes and returns the item at the given index, defaulting to the last.
229    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    /// Returns the item at index.
256    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    /// Returns a mutable reference to the item at index.
262    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    /// Returns the index of the first occurrence of a value.
268    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    /// Returns a Vec of all values.
285    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/// A doubly linked list.
313#[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    /// Creates a new DoublyLinkedList.
324    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    /// Returns the number of elements.
335    pub fn len(&self) -> usize {
336        self.len
337    }
338
339    /// Returns true if the list is empty.
340    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    /// Appends a value.
386    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    /// Prepends a value.
400    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    /// Inserts a value at the given index.
414    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    /// Removes the first occurrence of a value.
438    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    /// Removes and returns the item at the given index, defaulting to the last.
471    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    /// Returns the item at index.
486    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    /// Returns a mutable reference to the item at index.
492    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    /// Returns a Vec of all values.
498    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/// A circular linked list.
525#[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    /// Creates a new CircularLinkedList.
535    pub fn new() -> Self {
536        Self {
537            nodes: Vec::new(),
538            tail: None,
539            free: Vec::new(),
540            len: 0,
541        }
542    }
543
544    /// Returns the number of elements.
545    pub fn len(&self) -> usize {
546        self.len
547    }
548
549    /// Returns true if the list is empty.
550    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    /// Appends a value.
569    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    /// Prepends a value.
584    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    /// Removes the first occurrence of a value.
598    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    /// Returns a Vec of all values.
633    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/// A LIFO stack.
662#[derive(Debug, Clone)]
663pub struct Stack<T> {
664    items: Vec<T>,
665}
666
667impl<T> Stack<T> {
668    /// Creates a new Stack.
669    pub fn new() -> Self {
670        Self { items: Vec::new() }
671    }
672
673    /// Returns the number of elements.
674    pub fn len(&self) -> usize {
675        self.items.len()
676    }
677
678    /// Returns true if the stack is empty.
679    pub fn is_empty(&self) -> bool {
680        self.items.is_empty()
681    }
682
683    /// Pushes a value.
684    pub fn push(&mut self, value: T) {
685        self.items.push(value);
686    }
687
688    /// Pops and returns the top value.
689    pub fn pop(&mut self) -> Result<T, Error> {
690        self.items.pop().ok_or(Error::Empty)
691    }
692
693    /// Returns the top value without removing it.
694    pub fn peek(&self) -> Result<&T, Error> {
695        self.items.last().ok_or(Error::Empty)
696    }
697
698    /// Returns a Vec from top to bottom.
699    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/// A FIFO queue.
714#[derive(Debug, Clone)]
715pub struct Queue<T> {
716    items: std::collections::VecDeque<T>,
717}
718
719impl<T> Queue<T> {
720    /// Creates a new Queue.
721    pub fn new() -> Self {
722        Self {
723            items: std::collections::VecDeque::new(),
724        }
725    }
726
727    /// Returns the number of elements.
728    pub fn len(&self) -> usize {
729        self.items.len()
730    }
731
732    /// Returns true if the queue is empty.
733    pub fn is_empty(&self) -> bool {
734        self.items.is_empty()
735    }
736
737    /// Enqueues a value.
738    pub fn enqueue(&mut self, value: T) {
739        self.items.push_back(value);
740    }
741
742    /// Dequeues and returns the front value.
743    pub fn dequeue(&mut self) -> Result<T, Error> {
744        self.items.pop_front().ok_or(Error::Empty)
745    }
746
747    /// Returns the front value without removing it.
748    pub fn peek(&self) -> Result<&T, Error> {
749        self.items.front().ok_or(Error::Empty)
750    }
751
752    /// Returns a Vec of all values.
753    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}