Struct SortedList

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

A sorted singly linked list

This behaves similar to Stack, in that it is a singly linked list, however items are stored in an ordered fashion. This means that insertion is an O(n) operation, and retrieval of the first item is an O(1) operation.

It allows for a user selected ordering operation. If your type T implements Ord:

• Consider using SortedList::new_min() if you want smallest items sorted first.
• Consider using SortedList::new_max() if you want largest items sorted first.

If your type T does NOT implement Ord, or you want to use a custom sorting anyway, consider using SortedList::new_with_cmp()

In order to be part of a SortedList, a type T must implement the Linked trait for sorted_list::Links<T>, which is an alias for stack::Links<T>. This means that you can link the same element into either structure, but you can’t have something that’s linked into a SortedList and a Stack at the same time (without wrapper structs that have separate sets of links, left as an exercise for the reader).

Pushing elements into a SortedList takes ownership of those elements through an owning Handle type. Dropping a SortedList drops all elements currently linked into the stack.

Implementations

impl<T> SortedList<T>

where T: Linked<Links<T>> + Ord,

pub const fn new_min() -> Self

Create a new (empty) sorted list, sorted LEAST FIRST

• Consider using SortedList::new_max() if you want largest items sorted first.
• Consider using SortedList::new_with_cmp() if you want to provide your own sorting implementation.

If two items are considered of equal value, new values will be placed AFTER old values.

pub fn from_stack_min(stack: Stack<T>) -> Self

Create a new sorted list, consuming the stack, sorted LEAST FIRST

pub const fn new_max() -> Self

Create a new (empty) sorted list, sorted GREATEST FIRST

• Consider using SortedList::new_min() if you want smallest items sorted first.
• Consider using SortedList::new_with_cmp() if you want to provide your own sorting implementation.

If two items are considered of equal value, new values will be placed AFTER old values.

pub fn from_stack_max(stack: Stack<T>) -> Self

Create a new sorted list, consuming the stack, sorted GREATEST FIRST

impl<T: Linked<Links<T>>> SortedList<T>

pub const fn new_with_cmp(f: fn(_: &T, _: &T) -> Ordering) -> Self

Create a new (empty) sorted list with the given ordering function

If your type T implements Ord:

• Consider using SortedList::new_min() if you want smallest items sorted first.
• Consider using SortedList::new_max() if you want largest items sorted first.

If T contained an i32, and you wanted the SMALLEST items at the front, then you could provide a function something like:

let f: fn(&i32, &i32) -> core::cmp::Ordering = |lhs, rhs| {
    lhs.cmp(rhs)
};

SortedList takes a function (and not just Ord) so you can use it on types that don’t have a general way of ordering them, allowing you to select a specific metric within the sorting function.

If two items are considered of equal value, new values will be placed AFTER old values.

pub fn from_stack_with_cmp( stack: Stack<T>, f: fn(_: &T, _: &T) -> Ordering, ) -> Self

Create a new sorted list, consuming the stack, using the provided ordering function

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

Pop the front-most item from the list, returning it by ownership (if it exists)

Note that “front” here refers to the sorted ordering. If this list was created with SortedList::new_min, the SMALLEST item will be popped. If this was created with SortedList::new_max, the LARGEST item will be popped.

This is an O(1) operation.

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

Insert a single item into the list, in its sorted order position

Note that if the inserted item is Equal to another item in the list, the newest item is always sorted AFTER the existing item.

This is an O(n) operation.

pub fn iter(&self) -> SortedListIter<'_, T>

Iterate through the items of the list, in sorted order

Trait Implementations

impl<T> Debug for SortedList<T>

where T: Linked<Links<T>>,

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

Formats the value using the given formatter.

impl<T: Linked<Links<T>>> Drop for SortedList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Linked<Links<T>>> Extend<<T as Linked<Links<T>>>::Handle> for SortedList<T>

fn extend<I: IntoIterator<Item = T::Handle>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.