plain_ds/list/
api.rs

1use crate::core::{DSError, Result};
2
3/// This trait defines common API for all list implementations.
4pub trait List<'a, T: 'a> {
5    /// Returns list size.
6    fn len(&self) -> usize;
7
8    /// Checks if the list is empty.
9    ///
10    /// Efficiency: O(1)
11    fn is_empty(&self) -> bool {
12        self.len() == 0
13    }
14
15    /// Returns the payload value of the first node in the list.
16    fn head(&self) -> Option<&T>;
17
18    /// Returns the payload value of the last node in the list.
19    fn last(&self) -> Option<&T>;
20
21    /// Returns a list item by index, or error if index out of bounds.
22    ///
23    /// Efficiency: O(n)
24    fn get(&self, index: usize) -> Result<&'a T> {
25        self.iter().nth(index).ok_or(DSError::IndexOutOfBounds {
26            index,
27            len: self.len(),
28        })
29    }
30
31    /// Returns a mutable list item by index, or error if index out of bounds.
32    ///
33    /// Efficiency: O(n)
34    fn get_mut(&mut self, index: usize) -> Result<&'a mut T> {
35        let list_size = self.len();
36        self.iter_mut().nth(index).ok_or(DSError::IndexOutOfBounds {
37            index,
38            len: list_size
39        })
40    }
41
42    /// Returns an iterator over the immutable items of the list.
43    fn iter(&self) -> impl Iterator<Item = &'a T>;
44
45    /// Returns an iterator over the mutable items of the list.
46    fn iter_mut(&mut self) -> impl Iterator<Item = &'a mut T>;
47
48    /// Returns an iterator that consumes the list.
49    fn into_iter(self) -> impl Iterator<Item = T>;
50
51    /// Adds a new node to the list.
52    fn push(&mut self, payload: T);
53
54    /// Removes a node from the end of the list and returns its payload value.
55    fn pop_back(&mut self) -> Option<T>;
56
57    /// Removes a node from the front of the list and returns its payload value.
58    fn pop_front(&mut self) -> Option<T>;
59
60    /// Removes a node from the specified location in the list.
61    fn remove(&mut self, index: usize) -> Result<T>;
62
63    /// Removes all items from the list.
64    ///
65    /// Efficiency: O(n)
66    fn clear(&mut self) {
67        while self.len() != 0 {
68            let _ = self.pop_front();
69        }
70    }
71
72    /// Finds the first node whose payload is equal to the given `value` and returns its index.
73    /// Returns `None` if there is no such node.
74    ///
75    /// Efficiency: O(n)
76    fn find(&self, value: &T) -> Option<usize>
77    where T: PartialEq<T>
78    {
79        self.iter()
80            .enumerate()
81            .find(|(_, item)| *item == value)
82            .map(|(index, _)| index)
83    }
84}
plain_ds/list/api.rs

plain_ds/list/
api.rs
