Struct LinkedList

Source

pub struct LinkedList<K, V>where
    K: Debug,
    V: Debug,
{ /* private fields */ }

Expand description

A double linked min list. The head (top/front) of the list is the first item. Sorted Order::Less than other items. The tail (bottom/back) is the last item of the list. Sorted Order::Greater than other items.

Implementations§

Source §

impl<'a, K, V> LinkedList<K, V>
where K: Debug + Ord + PartialOrd + 'a, V: Debug + 'a,

Source

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty LinkedList<K,V> with the specified capacity. The LinkedList will be able to hold exactly capacity elements without reallocating. If capacity is 0, the list will not allocate.

Source

pub fn iter(&self) -> ListIterator<'_, K, V> ⓘ

Source

pub fn len(&self) -> usize

Returns the number of inserted elements

Source

pub fn capacity(&self) -> (usize, usize)

Returns the capacity or the vectors

Source

pub fn is_empty(&self) -> bool

Returns true if the list is empty

Source

pub fn clear(&mut self)

Clears the list. Warning: any Pointer object referring to this list will be corrupted.

Source

pub fn next_free_index(&self) -> usize

Returns the next free index. This value will be invalid if any insert or remove operation is performed on the list.

Source

pub fn get_k(&self, index: usize) -> Result<&K, MapError>

Returns the item key at index

Source

pub fn get_v(&self, index: usize) -> Result<&V, MapError>

Returns the item value at index

Source

pub fn get(&self, index: usize) -> Result<(&K, &V), MapError>

Returns the item key and value at index

§Examples

let mut ll = LinkedList::<i8, i8>::default();
ll.ordered_insert(1,1);
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
ll.ordered_insert(0,0);
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));
assert!(ll.get(ll.tail()).is_ok());
assert_eq!(ll.get(ll.tail()).unwrap(), (&1,&1));

Source

pub fn get_prev_k(&self, index: usize) -> Result<&K, MapError>

Returns the previous key item of item at index

Source

pub fn ordered_insert(&mut self, key: K, value: V) -> Result<usize, MapError>

Insert item at position defined by Order (lesser first) This is the same as ‘ordered_insert_pos()’ with self.head_ as position hint Insert item by Order (lesser first) with a position hint.

Note that insert(key, value) is a NOP if the key already exists, not even the new value will be used.

§Examples

let mut ll = LinkedList::<i8, i8>::default();
ll.ordered_insert(1,1);
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
ll.ordered_insert(0,0);
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));
ll.ordered_insert(0,100); // <- this is a NOP
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&0,&0));

Source

pub fn ordered_insert_pos( &mut self, key: K, value: V, position: usize, ) -> Result<usize, MapError>

Insert item by Order (lesser first) with a position hint. Note that insert(key, value) is a NOP if the key already exists, not even the new value will be used.

§Examples

let mut ll = LinkedList::<i8, i8>::default();
ll.ordered_insert(1,1);
ll.ordered_insert_pos(2,2,0);
assert!(ll.get(ll.head()).is_ok());
assert_eq!(ll.get(ll.head()).unwrap(), (&1,&1));
assert!(ll.get(ll.tail()).is_ok());
assert_eq!(ll.get(ll.tail()).unwrap(), (&2,&2));

Source

pub fn lower_bound(&self, key: K) -> Result<Option<usize>, MapError>

Returns the first element in the container whose key is not considered to go before position (i.e., either it is equivalent or goes after). If ‘search_from_head’ is true the search will be performed from the head otherwise from the tail. Returns None if no data is found

§Examples

let mut ll = LinkedList::<i8, i8>::default();
ll.ordered_insert(1,1);
ll.ordered_insert(2,2);
ll.ordered_insert(3,3);
let lb = ll.get(ll.lower_bound(2).unwrap().unwrap()).unwrap();
assert_eq!(lb, (&2,&2));
let lb = ll.get(ll.lower_bound(0).unwrap().unwrap()).unwrap();
assert_eq!(lb, (&1,&1));
let lb = ll.get(ll.lower_bound(1).unwrap().unwrap()).unwrap();
assert_eq!(lb, (&1,&1));
let lb = ll.get(ll.lower_bound(3).unwrap().unwrap()).unwrap();
assert_eq!(lb, (&3,&3));
assert!( ll.lower_bound(4).unwrap().is_none());

Source

pub fn pop_front(&mut self) -> Result<Option<(K, V)>, MapError>

Pop the head item

§Examples

let mut ll = LinkedList::<i8, i8>::default();
let _ = ll.ordered_insert(1, 0); // 0
let _ = ll.ordered_insert(2, 1); // 1
assert_eq!(ll.pop_front().unwrap().unwrap(), (1_i8,0_i8));
assert_eq!(ll.pop_front().unwrap().unwrap(), (2_i8,1_i8));

Source

pub fn pop_back(&mut self) -> Result<Option<(K, V)>, MapError>

Pop the tail item

§Examples

let mut ll = LinkedList::<i8, i8>::default();
let _ = ll.ordered_insert(1, 0); // 0
let _ = ll.ordered_insert(2, 1); // 1
assert_eq!(ll.pop_back().unwrap().unwrap(), (2_i8,1_i8));
assert_eq!(ll.pop_back().unwrap().unwrap(), (1_i8,0_i8));

Source

pub fn peek_front_k(&self) -> Option<&K>

Peek the head key

§Examples

let mut ll = LinkedList::<i8, i8>::default();
let _ = ll.ordered_insert(1, 0); // 0
let _ = ll.ordered_insert(2, 1); // 1
assert_eq!(ll.peek_front_k().unwrap(), &1_i8);

Source

pub fn peek_back_k(&self) -> Option<&K>

Peek the tail key

§Examples

let mut ll = LinkedList::<i8, i8>::default();
let _ = ll.ordered_insert(1, 0); // 0
let _ = ll.ordered_insert(2, 1); // 1
assert_eq!(ll.peek_back_k().unwrap(), &2_i8);