plain-ds 0.3.1

Plain data structures
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

use crate::core::{DSError, Result};

/// This trait defines common API for all list implementations.
pub trait List<'a, T: 'a> {
    /// Returns list size.
    fn len(&self) -> usize;

    /// Checks if the list is empty.
    ///
    /// **Efficiency**: O(1)
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the payload value of the first node in the list.
    fn head(&self) -> Option<&T>;

    /// Returns the payload value of the last node in the list.
    fn last(&self) -> Option<&T>;

    /// Returns a list item by index, or error if index out of bounds.
    ///
    /// **Efficiency**: O(n)
    fn get(&self, index: usize) -> Result<&'a T> {
        self.iter().nth(index).ok_or(DSError::IndexOutOfBounds {
            index,
            len: self.len(),
        })
    }

    /// Returns a mutable list item by index, or error if index out of bounds.
    ///
    /// **Efficiency**: O(n)
    fn get_mut(&mut self, index: usize) -> Result<&'a mut T> {
        let list_size = self.len();
        self.iter_mut().nth(index).ok_or(DSError::IndexOutOfBounds {
            index,
            len: list_size
        })
    }

    /// Returns an iterator over the immutable items of the list.
    fn iter(&self) -> impl Iterator<Item = &'a T>;

    /// Returns an iterator over the mutable items of the list.
    fn iter_mut(&mut self) -> impl Iterator<Item = &'a mut T>;

    /// Returns an iterator that consumes the list.
    fn into_iter(self) -> impl Iterator<Item = T>;

    /// Adds a new node to the list.
    fn push(&mut self, payload: T);

    /// Removes a node from the end of the list and returns its payload value.
    fn pop_back(&mut self) -> Option<T>;

    /// Removes a node from the front of the list and returns its payload value.
    fn pop_front(&mut self) -> Option<T>;

    /// Removes a node from the specified location in the list.
    fn remove(&mut self, index: usize) -> Result<T>;

    /// Removes all items from the list.
    ///
    /// **Efficiency**: O(n)
    fn clear(&mut self) {
        while self.len() != 0 {
            let _ = self.pop_front();
        }
    }

    /// Finds the first node whose payload is equal to the given `value` and returns its index.
    /// Returns `None` if there is no such node.
    ///
    /// **Efficiency**: O(n)
    fn find(&self, value: &T) -> Option<usize>
    where T: PartialEq<T>
    {
        self.iter()
            .enumerate()
            .find(|(_, item)| *item == value)
            .map(|(index, _)| index)
    }
}