Struct SortedList

pub struct SortedList<T>
where
    T: Ord,
{ /* private fields */ }

A sorted list data structure

Example

use sortedlist_rs::SortedList;

let array = vec![90, 19, 25];
let mut sorted_list = SortedList::from(array);

println!("{:?}", sorted_list);
// [19, 25, 90]

sorted_list.insert(100);
sorted_list.insert(1);
sorted_list.insert(20);
println!("{:?}", sorted_list);
// [1, 19, 20, 25, 90, 100]

let x = sorted_list.remove(3);
assert_eq!(25, x);
// removed the 3-rd smallest (0-indexed) element.

assert_eq!(&20, sorted_list.kth_smallest(2));

assert_eq!(20, sorted_list[2]);

println!("{:?}", sorted_list);
// [1, 19, 20, 90, 100]

Implementations

impl<T> SortedList<T>

where T: Ord,

Public method implementations

pub fn new() -> Self

Creates an empty SortedList.

Example

use sortedlist_rs::SortedList;

let sorted_list: SortedList<i32> = SortedList::new();

pub fn kth_smallest(&self, k: usize) -> &T

Find the k-th smallest (0-indexed) element in the SortedList.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 3]);
assert_eq!(&3, sorted_list.kth_smallest(1));

pub fn clear(&mut self)

Clears the SortedList.

Example

use sortedlist_rs::SortedList;

let mut sorted_list = SortedList::from([10, 2, 3]);
sorted_list.clear();

assert_eq!(0, sorted_list.len());
assert_eq!(true, sorted_list.is_empty());

pub fn insert(&mut self, element: T)

Insert element into the SortedList.

Example

use sortedlist_rs::SortedList;

let mut sorted_list = SortedList::new();
sorted_list.insert(10);
sorted_list.insert(6);
sorted_list.insert(99);

assert_eq!(3, sorted_list.len());
assert_eq!(6, sorted_list[0]);
assert_eq!(10, sorted_list[1]);

pub fn remove(&mut self, k: usize) -> T

Pops the k-th smallest (0-indexed) element from the SortedList.

Example

use sortedlist_rs::SortedList;

let mut sorted_list = SortedList::from([10, 2, 99, 20, 30]);
let popped = sorted_list.remove(3);

assert_eq!(30, popped);

pub fn binary_search(&self, element: &T) -> Result<usize, usize>

Binary searches the given element in the SortedList. Returns Ok(i) for exact match, Err(i) otherwise.

Example

use sortedlist_rs::SortedList;

let mut sorted_list = SortedList::from([10, 2, 99, 20, 30]);

let result = sorted_list.binary_search(&30);
assert_eq!(Ok(3), result);

let result = sorted_list.binary_search(&90);
assert_eq!(Err(4), result);

pub fn contains(&self, element: &T) -> bool

Returns whether the SortedList contains a specific element.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);

assert_eq!(true, sorted_list.contains(&10));
assert_eq!(false, sorted_list.contains(&90));

pub fn len(&self) -> usize

Returns the number of elements stored in the SortedList.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);

assert_eq!(4, sorted_list.len());

pub fn is_empty(&self) -> bool

Returns whether the SortedList is empty.

Example

use sortedlist_rs::SortedList;

let mut sorted_list: SortedList<i32> = SortedList::new();
assert_eq!(true, sorted_list.is_empty());

sorted_list.insert(1);
assert_eq!(false, sorted_list.is_empty());

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

Returns the last element of the SortedList, i.e. the largest element.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);

assert_eq!(Some(&99), sorted_list.last());

pub fn first(&self) -> Option<&T>

Returns the first element of the SortedList, i.e. the smallest element.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);

assert_eq!(Some(&2), sorted_list.first());

pub fn get(&self, index: usize) -> Option<&T>

Returns the element for the given index in the SortedList.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);

assert_eq!(Some(&20), sorted_list.get(2));

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

Returns a flattened view of the SortedList.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);
let flattened = sorted_list.flatten();

assert_eq!(vec![&2, &10, &20, &99], flattened);

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

where T: Clone,

Convert self into a new Vec.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([10, 2, 99, 20]);
let v = sorted_list.to_vec();

assert_eq!(vec![2, 10, 20, 99], v);

Trait Implementations

impl<T> Debug for SortedList<T>

where T: Ord + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for SortedList<T>

where T: Ord,

fn default() -> Self

Creates an empty SortedList.

impl<T> From<&[T]> for SortedList<T>

where T: Ord + Clone,

fn from(array: &[T]) -> Self

Allocate a SortedList and fill it by cloning array’s items.

impl<T> From<&mut [T]> for SortedList<T>

where T: Ord + Clone,

fn from(array: &mut [T]) -> Self

Allocate a SortedList and fill it by cloning array’s items.

impl<T, const N: usize> From<[T; N]> for SortedList<T>

where T: Ord,

fn from(array: [T; N]) -> Self

Allocate a SortedList and move array’s item into it.

impl<T> From<IntoIter<T>> for SortedList<T>

where T: Ord,

fn from(iter: IntoIter<T>) -> Self

Creates a SortedList from an IntoIter

impl<T> From<Vec<T>> for SortedList<T>

where T: Ord,

fn from(array: Vec<T>) -> Self

Creates a SortedList from a Vec

impl<T> Index<usize> for SortedList<T>

where T: Ord,

fn index(&self, index: usize) -> &Self::Output

Access the SortedList for the given index.

Example

use sortedlist_rs::SortedList;

let sorted_list = SortedList::from([20, 2, 10, 99, 50, 32]);

assert_eq!(32, sorted_list[3]);

type Output = T

The returned type after indexing.