Struct SortedList 

pub struct SortedList<T> { /* private fields */ }

An ordered collection that maintains its elements in sorted order.

The SortedList automatically keeps elements sorted upon insertion, ensuring efficient search operations.

Type Parameters

• T: The type of elements stored in the list. Must implement PartialOrd.

Examples

use plain_ds::SortedList;

let mut list = SortedList::new();
list.push(3);
list.push(1);
list.push(2);

assert_eq!(list.len(), 3);
assert_eq!(list.to_vec(), vec![1, 2, 3]);

Implementations

impl<T> SortedList<T>

pub fn new() -> Self

Creates empty ordered list.

pub fn from_slice(slice: &[T]) -> Self

where T: Clone + PartialOrd,

Creates list from slice.

Efficiency: O(n)

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Collect list values into a vector.

Efficiency: O(n)

pub fn find_if(&self, predicate: impl Fn(&T) -> bool) -> Option<usize>

where T: PartialOrd,

Finds the first node whose payload satisfies the predicate and returns its index. Returns None if there is no such node.

Efficiency: O(n)

Trait Implementations

impl<'a, T> List<'a, T> for SortedList<T>

where T: PartialOrd + 'a,

fn len(&self) -> usize

Returns list size.

Efficiency: O(1)

fn head(&self) -> Option<&T>

Returns the payload value of the first node in the list.

Efficiency: O(1)

fn last(&self) -> Option<&T>

Returns the payload value of the last node in the list.

Efficiency: O(1)

fn iter(&self) -> impl Iterator<Item = &'a T>

Returns an iterator over the immutable items of the list.

fn iter_mut(&mut self) -> impl Iterator<Item = &'a mut T>

Returns an iterator over the mutable items of the list.

fn into_iter(self) -> impl Iterator<Item = T>

Returns an iterator that consumes the list.

fn push(&mut self, payload: T)

Adds a new node to the list according to the sort order.

Efficiency: O(n) at worst

fn pop_back(&mut self) -> Option<T>

Removes a node from the end of the list and returns its payload value.

Efficiency: O(n)

fn pop_front(&mut self) -> Option<T>

Removes a node from the front of the list and returns its payload value.

Efficiency: O(1)

fn remove(&mut self, index: usize) -> Result<T>

Removes a node from the specified location in the list. Error returns, if the index out of bounds.

Efficiency: O(n)

fn find(&self, value: &T) -> Option<usize>

where T: PartialEq<T>,

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) at worst

fn is_empty(&self) -> bool

Checks if the list is empty.

fn get(&self, index: usize) -> Result<&'a T>

Returns a list item by index, or error if index out of bounds.

fn get_mut(&mut self, index: usize) -> Result<&'a mut T>

Returns a mutable list item by index, or error if index out of bounds.

fn clear(&mut self)

Removes all items from the list.