Trait DoublyEndsMut

pub trait DoublyEndsMut<T, M, P>: HasDoublyEndsMut<T, M, P> + DoublyEnds<T, M, P>
where
    M: MemoryPolicy<Doubly<T>>,
    P: PinnedVec<Node<Doubly<T>>>,
{
    // Provided methods
    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>
       where M: 'a,
             P: 'a { ... }
    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>
       where M: 'a,
             P: 'a { ... }
    fn get_mut<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>
       where M: 'a,
             P: 'a { ... }
    fn try_get_mut<'a>(
        &'a mut self,
        idx: &DoublyIdx<T>,
    ) -> Result<&'a mut T, NodeIdxError>
       where M: 'a,
             P: 'a { ... }
    fn next_mut_of<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>
       where M: 'a,
             P: 'a { ... }
    fn prev_mut_of<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>
       where M: 'a,
             P: 'a { ... }
    fn reverse(&mut self) { ... }
    fn move_next_to(&mut self, idx: &DoublyIdx<T>, idx_target: &DoublyIdx<T>) { ... }
    fn move_prev_to(&mut self, idx: &DoublyIdx<T>, idx_target: &DoublyIdx<T>) { ... }
    fn move_to_front(&mut self, idx: &DoublyIdx<T>) { ... }
    fn move_to_back(&mut self, idx: &DoublyIdx<T>) { ... }
    fn swap(&mut self, idx_a: &DoublyIdx<T>, idx_b: &DoublyIdx<T>) { ... }
    unsafe fn add_link(&mut self, a: &DoublyIdx<T>, b: &DoublyIdx<T>) { ... }
    unsafe fn remove_link(&mut self, a: &DoublyIdx<T>, b: &DoublyIdx<T>) { ... }
    unsafe fn set_front(&mut self, new_front: &DoublyIdx<T>) { ... }
    unsafe fn set_back(&mut self, new_back: &DoublyIdx<T>) { ... }
}

A list or view having a single end: front.

Provided Methods

fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the front of the list, returns None if the list is empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

assert!(list.front_mut().is_none());

list.push_front('a');
assert_eq!(Some(&'a'), list.front());

*list.front_mut().unwrap() = 'x';

assert_eq!(Some(&'x'), list.front());

fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the back of the list, returns None if the list is empty.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

assert!(list.back_mut().is_none());

list.push_back('a');
assert_eq!(Some(&'a'), list.back());

*list.back_mut().unwrap() = 'x';

assert_eq!(Some(&'x'), list.back());

fn get_mut<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the node with the given idx in constant time.

Returns None if the index is invalid.

Safety

Returns Some if all of the following safety conditions hold:

• the index is created from this list,
• the node that this index is created for still belongs to the list (not removed),
• the node positions in this list are not reorganized to reclaim memory:
  • DoublyList or SinglyList automatically reorganizes nodes on removal of items if the utilization of memory drops below a threshold.
  • DoublyListLazy or SinglyListLazy do not reorganize nodes implicitly, the indices are only invalidated if the reclaim_closed_nodes is manually called.

Returns None otherwise. We can use try_get_mut to understand why the index is invalid.

Examples

Following example illustrates where automatic reorganization does not happen since no elements are removed from the list.

The indices remain valid.

use orx_linked_list::*;

let mut list = DoublyList::new();

let a = list.push_back('a');
let b = list.push_back('b');

assert_eq!(list.get(&a), Some(&'a'));
assert_eq!(list.get(&b), Some(&'b'));

*list.get_mut(&a).unwrap() = 'x';

list.push_front('c');
list.push_back('d');
list.push_front('e');
let f = list.push_back('f');

assert_eq!(list.get(&a), Some(&'x'));
assert_eq!(list.get(&b), Some(&'b'));
assert_eq!(list.get(&f), Some(&'f'));

let _ = list.pop_back(); // f is removed

*list.get_mut(&a).unwrap() = 'y';

assert_eq!(list.get(&a), Some(&'y'));
assert_eq!(list.get(&b), Some(&'b'));
assert_eq!(list.get(&f), None);

list.clear(); // all removed

assert_eq!(list.get(&a), None);
assert_eq!(list.get(&b), None);
assert_eq!(list.get(&f), None);

In the following, removal of nodes invalidates indices due to reorganization. In these cases, we safely receive None.

Note that, to have complete control on validity of indices, we can use DoublyListLazy or SinglyListLazy. In these variants, indices are invalidated only if we manually call reclaim_closed_nodes.

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
list.push_back('b');
let c = list.push_back('c');
list.push_back('d');
list.push_back('e');

*list.get_mut(&c).unwrap() = 'x';

list.pop_back(); // does not lead to reorganization

assert_eq!(list.get(&c), Some(&'x'));

list.pop_front(); // leads to reorganization

assert_eq!(list.get(&c), None);

In the final example, we attempt to access to a list element using an index created by another list.

use orx_linked_list::*;

let mut list = DoublyList::new();
let idx = list.push_back('a');

let mut other_list = DoublyList::new();
let other_idx = other_list.push_back('a');

assert!(list.get_mut(&idx).is_some());
// assert_eq!(list.get_mut(&other_idx), None);

fn try_get_mut<'a>( &'a mut self, idx: &DoublyIdx<T>, ) -> Result<&'a mut T, NodeIdxError>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the node with the given idx in constant time.

Returns NodeIdxError if the index is invalid.

Safety

Returns Some if all of the following safety conditions hold:

• the index is created from this list,
• the node that this index is created for still belongs to the list (not removed),
• the node positions in this list are not reorganized to reclaim memory:
  • DoublyList or SinglyList automatically reorganizes nodes on removal of items if the utilization of memory drops below a threshold.
  • DoublyListLazy or SinglyListLazy do not reorganize nodes implicitly, the indices are only invalidated if the reclaim_closed_nodes is manually called.

Otherwise, returns:

• RemovedNode if the particular element is removed from the list.
• OutOfBounds if the index is does not point to the current nodes of the list.
• ReorganizedCollection if nodes of the list are reorganized to reclaim closed nodes.

Examples

Following example illustrates where automatic reorganization does not happen since no elements are removed from the list.

The indices remain valid.

use orx_linked_list::*;

let mut list = DoublyList::new();

let a = list.push_back('a');
let b = list.push_back('b');

assert_eq!(list.try_get(&a), Ok(&'a'));
assert_eq!(list.try_get(&b), Ok(&'b'));

*list.try_get_mut(&a).unwrap() = 'x';

list.push_front('c');
list.push_back('d');
list.push_front('e');
let f = list.push_back('f');

assert_eq!(list.try_get(&a), Ok(&'x'));
assert_eq!(list.try_get(&b), Ok(&'b'));
assert_eq!(list.try_get(&f), Ok(&'f'));

let _ = list.pop_back(); // f is removed

*list.try_get_mut(&a).unwrap() = 'y';

assert_eq!(list.try_get(&a), Ok(&'y'));
assert_eq!(list.try_get(&b), Ok(&'b'));
assert_eq!(list.try_get(&f), Err(NodeIdxError::RemovedNode));

list.clear(); // all removed

assert_eq!(list.try_get(&a), Err(NodeIdxError::OutOfBounds));
assert_eq!(list.try_get(&b), Err(NodeIdxError::OutOfBounds));
assert_eq!(list.try_get(&f), Err(NodeIdxError::OutOfBounds));

In the following, removal of nodes invalidates indices due to reorganization. In these cases, we safely receive None.

Note that, to have complete control on validity of indices, we can use DoublyListLazy or SinglyListLazy. In these variants, indices are invalidated only if we manually call reclaim_closed_nodes.

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('a');
list.push_back('b');
let c = list.push_back('c');
list.push_back('d');
list.push_back('e');

*list.try_get_mut(&c).unwrap() = 'x';

list.pop_back(); // does not lead to reorganization

assert_eq!(list.get(&c), Some(&'x'));

list.pop_front(); // leads to reorganization

assert_eq!(list.try_get_mut(&c), Err(NodeIdxError::ReorganizedCollection));

In the final example, we attempt to access to a list element using an index created by another list.

use orx_linked_list::*;

let mut list = DoublyList::new();
let idx = list.push_back('a');

let mut other_list = DoublyList::new();
let other_idx = other_list.push_back('a');

assert!(list.try_get_mut(&idx).is_ok());
// assert_eq!(list.try_get_mut(&other_idx), Err(NodeIdxError::OutOfBounds));

fn next_mut_of<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the element succeeding the one with the given idx. Returns None if the element at idx is the back.

Panics

Panics if the idx is not valid; i.e., idx_err is not None.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back('c');
list.push_front('b');
let a = list.push_front('a');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let c = list.next_idx_of(&a).and_then(|b| list.next_mut_of(&b));
*c.unwrap() = 'x';

assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'd']));

fn prev_mut_of<'a>(&'a mut self, idx: &DoublyIdx<T>) -> Option<&'a mut T>

where M: 'a, P: 'a,

O(1) Returns a mutable reference to the element preceding the one with the given idx. Returns None if the element at idx is the front.

Panics

Panics if the idx is not valid; i.e., idx_err is not None.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

let c = list.push_back('c');
list.push_front('b');
list.push_front('a');
list.push_back('d');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));

let a = list.prev_idx_of(&c).and_then(|b| list.prev_mut_of(&b));
*a.unwrap() = 'x';

assert!(list.eq_to_iter_vals(['x', 'b', 'c', 'd']));

fn reverse(&mut self)

O(n) Reverses the list (in-place).

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

let c = list.push_back('c');
let _b = list.push_front('b');
let _a = list.push_front('a');
let _d = list.push_back('d');
let e = list.push_back('e');

assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));

list.reverse();
assert!(list.eq_to_iter_vals(['e', 'd', 'c', 'b', 'a']));

let mut slice = list.slice_mut(&e..=&c);
assert!(slice.eq_to_iter_vals(['e', 'd', 'c']));

slice.reverse();
assert!(slice.eq_to_iter_vals(['c', 'd', 'e']));

assert!(list.eq_to_iter_vals(['c', 'd', 'e', 'b', 'a']));

fn move_next_to(&mut self, idx: &DoublyIdx<T>, idx_target: &DoublyIdx<T>)

O(1) Moves the element with the given idx immediately after the target element with the given idx_target.

Panics

Panics if either of the indices is invalid.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..6).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5]));

list.move_next_to(&idx[4], &idx[1]);
assert!(list.eq_to_iter_vals([0, 1, 4, 2, 3, 5]));

list.move_next_to(&idx[2], &idx[5]);
assert!(list.eq_to_iter_vals([0, 1, 4, 3, 5, 2]));

list.move_next_to(&idx[3], &idx[0]);
assert!(list.eq_to_iter_vals([0, 3, 1, 4, 5, 2]));

fn move_prev_to(&mut self, idx: &DoublyIdx<T>, idx_target: &DoublyIdx<T>)

O(1) Moves the element with the given idx immediately before the target element with the given idx_target.

Panics

Panics if either of the indices is invalid.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..6).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5]));

list.move_prev_to(&idx[4], &idx[1]);
assert!(list.eq_to_iter_vals([0, 4, 1, 2, 3, 5]));

list.move_prev_to(&idx[2], &idx[5]);
assert!(list.eq_to_iter_vals([0, 4, 1, 3, 2, 5]));

list.move_prev_to(&idx[3], &idx[0]);
assert!(list.eq_to_iter_vals([3, 0, 4, 1, 2, 5]));

fn move_to_front(&mut self, idx: &DoublyIdx<T>)

O(1) Moves the element with the given idx to the front of the list.

Panics

Panics if the index is invalid or if the list is empty.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..6).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5]));

list.move_to_front(&idx[5]);
assert!(list.eq_to_iter_vals([5, 0, 1, 2, 3, 4]));

list.move_to_front(&idx[2]);
assert!(list.eq_to_iter_vals([2, 5, 0, 1, 3, 4]));

list.move_to_front(&idx[3]);
assert!(list.eq_to_iter_vals([3, 2, 5, 0, 1, 4]));

fn move_to_back(&mut self, idx: &DoublyIdx<T>)

O(1) Moves the element with the given idx to the back of the list.

Panics

Panics if the index is invalid or if the list is empty.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..6).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5]));

list.move_to_back(&idx[1]);
assert!(list.eq_to_iter_vals([0, 2, 3, 4, 5, 1]));

list.move_to_back(&idx[4]);
assert!(list.eq_to_iter_vals([0, 2, 3, 5, 1, 4]));

list.move_to_back(&idx[2]);
assert!(list.eq_to_iter_vals([0, 3, 5, 1, 4, 2]));

fn swap(&mut self, idx_a: &DoublyIdx<T>, idx_b: &DoublyIdx<T>)

O(1) Swaps the elements with indices a and b.

Panics

Panics if the idx is not valid; i.e., idx_err is not None.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..6).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5]));

list.swap(&idx[1], &idx[5]);
assert!(list.eq_to_iter_vals([0, 5, 2, 3, 4, 1]));

list.swap(&idx[4], &idx[0]);
assert!(list.eq_to_iter_vals([4, 5, 2, 3, 0, 1]));

list.swap(&idx[3], &idx[5]);
assert!(list.eq_to_iter_vals([4, 3, 2, 5, 0, 1]));

unsafe fn add_link(&mut self, a: &DoublyIdx<T>, b: &DoublyIdx<T>)

O(1) Adds a link between a and b; i.e.,

• sets a as the prev of b,
• sets b as the next of a.

Panics

Panics if either of the indices a and b is not valid; i.e., idx_err is not None.

Safety

This method is unsafe since it breaks the internal structure of the linked list when used alone. The caller must guarantee that the internal structure is maintained by a series of moves as illustrated in the example.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..8).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5, 6, 7]));

unsafe {
    list.remove_link(&idx[0], &idx[1]);
    list.remove_link(&idx[2], &idx[3]);
    list.add_link(&idx[0], &idx[3]);
    list.add_link(&idx[7], &idx[1]);
    list.set_back(&idx[2]);
}

assert!(list.eq_to_iter_vals([0, 3, 4, 5, 6, 7, 1, 2]));

This example also makes it clear that the unsafe api is very useful; however, it must only be used through a safe method that defines a proved to be legal move as a combination of unsafe moves.

unsafe fn remove_link(&mut self, a: &DoublyIdx<T>, b: &DoublyIdx<T>)

O(1) Removes a link between a and b; i.e.,

• clears the prev of b,
• clears the next of a.

Panics

Panics if either of the indices a and b is not valid; i.e., idx_err is not None. Also panics in debug mode if the link between a and be does not exist.

Safety

This method is unsafe since it breaks the internal structure of the linked list when used alone. The caller must guarantee that the internal structure is maintained by a series of moves as illustrated in the example.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..8).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5, 6, 7]));

unsafe {
    list.remove_link(&idx[0], &idx[1]);
    list.remove_link(&idx[2], &idx[3]);
    list.add_link(&idx[0], &idx[3]);
    list.add_link(&idx[7], &idx[1]);
    list.set_back(&idx[2]);
}

assert!(list.eq_to_iter_vals([0, 3, 4, 5, 6, 7, 1, 2]));

This example also makes it clear that the unsafe api is very useful; however, it must only be used through a safe method that defines a proved to be legal move as a combination of unsafe moves.

unsafe fn set_front(&mut self, new_front: &DoublyIdx<T>)

O(1) Sets the front of the list as the new_front.

Panics

Panics if the index new_front is not valid; i.e., idx_err is not None.

Safety

This method is unsafe since it breaks the internal structure of the linked list when used alone. The caller must guarantee that the internal structure is maintained by a series of moves as illustrated in the example.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..8).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5, 6, 7]));

unsafe {
    list.remove_link(&idx[0], &idx[1]);
    list.remove_link(&idx[2], &idx[3]);
    list.add_link(&idx[0], &idx[3]);
    list.add_link(&idx[7], &idx[1]);
    list.set_back(&idx[2]);
}

assert!(list.eq_to_iter_vals([0, 3, 4, 5, 6, 7, 1, 2]));

This example also makes it clear that the unsafe api is very useful; however, it must only be used through a safe method that defines a proved to be legal move as a combination of unsafe moves.

unsafe fn set_back(&mut self, new_back: &DoublyIdx<T>)

O(1) Sets the back of the list as the new_back.

Panics

Panics if the index new_back is not valid; i.e., idx_err is not None.

Safety

This method is unsafe since it breaks the internal structure of the linked list when used alone. The caller must guarantee that the internal structure is maintained by a series of moves as illustrated in the example.

Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = (0..8).collect();
let idx: Vec<_> = list.indices().collect();

assert!(list.eq_to_iter_vals([0, 1, 2, 3, 4, 5, 6, 7]));

unsafe {
    list.remove_link(&idx[0], &idx[1]);
    list.remove_link(&idx[2], &idx[3]);
    list.add_link(&idx[0], &idx[3]);
    list.add_link(&idx[7], &idx[1]);
    list.set_back(&idx[2]);
}

assert!(list.eq_to_iter_vals([0, 3, 4, 5, 6, 7, 1, 2]));

This example also makes it clear that the unsafe api is very useful; however, it must only be used through a safe method that defines a proved to be legal move as a combination of unsafe moves.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<L, T, M, P> DoublyEndsMut<T, M, P> for L

where L: HasDoublyEndsMut<T, M, P>, M: MemoryPolicy<Doubly<T>>, P: PinnedVec<Node<Doubly<T>>>,