Trait DoublyIterable

pub trait DoublyIterable<T, M, P>: HasDoublyEnds<T, M, P>
where
    M: MemoryPolicy<Doubly<T>>,
    P: PinnedVec<Node<Doubly<T>>>,
    Self: Sized,
{
    // Provided methods
    fn iter_ptr<'a>(&'a self) -> DoublyIterPtr<'a, T, P> 
       where M: 'a { ... }
    fn iter<'a>(&'a self) -> DoublyIter<'a, T, P> 
       where M: 'a { ... }
    fn iter_links<'a>(&'a self) -> DoublyLinkIter<'a, T, P> 
       where M: 'a { ... }
    fn indices<'a>(&'a self) -> impl Iterator<Item = DoublyIdx<T>>
       where M: 'a,
             T: 'a,
             P: 'a { ... }
    fn pointers<'a>(&'a self) -> impl Iterator<Item = DoublyPtr<T>>
       where M: 'a,
             T: 'a,
             P: 'a { ... }
    fn ring_iter<'a>(
        &'a self,
        pivot_idx: &DoublyIdx<T>,
    ) -> Chain<DoublyIter<'a, T, P>, DoublyIter<'a, T, P>>
       where M: 'a { ... }
    fn iter_from<'a>(&'a self, idx: &DoublyIdx<T>) -> DoublyIter<'a, T, P> 
       where M: 'a { ... }
    fn iter_backward_from<'a>(
        &'a self,
        idx: &DoublyIdx<T>,
    ) -> Rev<DoublyIter<'a, T, P>>
       where M: 'a { ... }
    fn iter_links_from<'a>(
        &'a self,
        idx: &DoublyIdx<T>,
    ) -> DoublyLinkIter<'a, T, P> 
       where M: 'a { ... }
    fn eq_to_iter_vals<I>(&self, iter: I) -> bool
       where I: IntoIterator<Item = T>,
             T: PartialEq { ... }
    fn eq_to_iter_refs<'a, I>(&self, iter: I) -> bool
       where I: IntoIterator<Item = &'a T>,
             T: 'a + PartialEq { ... }
}

Iterator methods for doubly linked lists.

Provided Methods

fn iter_ptr<'a>(&'a self) -> DoublyIterPtr<'a, T, P>

where M: 'a,

Returns a double-ended iterator of pointers to the elements of the list from front to back.

fn iter<'a>(&'a self) -> DoublyIter<'a, T, P>

where M: 'a,

Returns a double-ended iterator to elements of the list:

• next iterates from front-to-back, while
• next_back iterates from back-to-front.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

// a -> b -> c -> d
list.push_front('b');
list.push_back('c');
list.push_back('d');
list.push_front('a');

// forward iteration
assert_eq!(
    list.iter().copied().collect::<Vec<_>>(),
    &['a', 'b', 'c', 'd']
);

// backward iteration
assert_eq!(
    list.iter().rev().copied().collect::<Vec<_>>(),
    &['d', 'c', 'b', 'a']
);

// mixed iteration
let mut iter = list.iter();

assert_eq!(Some(&'a'), iter.next());
assert_eq!(Some(&'d'), iter.next_back());
assert_eq!(Some(&'b'), iter.next());
assert_eq!(Some(&'c'), iter.next());
assert!(iter.next().is_none());

fn iter_links<'a>(&'a self) -> DoublyLinkIter<'a, T, P>

where M: 'a,

Creates a forward iterator that yields pairs of successive elements representing links.

Examples

use orx_linked_list::*;

let tour: DoublyList<_> = ['a', 'b', 'c', 'd', 'e'].into_iter().collect();

let mut iter = tour.iter_links();

assert_eq!(iter.next(), Some((&'a', &'b')));
assert_eq!(iter.next(), Some((&'b', &'c')));
assert_eq!(iter.next(), Some((&'c', &'d')));
assert_eq!(iter.next(), Some((&'d', &'e')));

assert_eq!(iter.next(), None);

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

where M: 'a, T: 'a, P: 'a,

Returns an iterator of indices of elements of the list.

Recall that indices are used to enable constant time access to any place of the list. Methods adding an element to the list such as push_front or insert return the corresponding index of the element.

This method, on the other hand, is useful to collect all indices at once, probably after a reorganization.

Examples

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back(1);
list.push_front(0);
list.push_back(2);
assert!(list.eq_to_iter_vals([0, 1, 2]));

let idx: Vec<_> = list.indices().collect();

assert_eq!(list.get(&idx[1]), Some(&1));

// O(1) mutations through indices
list.insert_next_to(&idx[0], 42);
list.insert_prev_to(&idx[2], 7);
list.remove(&idx[1]);

assert!(list.eq_to_iter_vals([0, 42, 7, 2]));

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

where M: 'a, T: 'a, P: 'a,

Returns an iterator of pointers to the elements of the list.

Similar to indices, pointers are used to enable constant time access to any place of the list. They are thinner; however, have only some of the safety guarantees that indices have.

fn ring_iter<'a>( &'a self, pivot_idx: &DoublyIdx<T>, ) -> Chain<DoublyIter<'a, T, P>, DoublyIter<'a, T, P>>

where M: 'a,

Creates a forward iterator starting from the pivot_idx and ending at the element before it.

The iterator jumps to front when it hits the back; and hence, gives the linked list a circular behavior.

Examples

use orx_linked_list::*;

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

let iter = list.ring_iter(&idx[2]);
assert_eq!(iter.copied().collect::<Vec<_>>(), [2, 3, 4, 5, 6, 7, 0, 1]);

let iter = list.ring_iter(&idx[4]);
assert_eq!(iter.copied().collect::<Vec<_>>(), [4, 5, 6, 7, 0, 1, 2, 3]);

// ring iterator is also double-ended
let iter = list.ring_iter(&idx[4]).rev();
assert_eq!(iter.copied().collect::<Vec<_>>(), [3, 2, 1, 0, 7, 6, 5, 4]);

// ring iterators are also available for slices
let slice = list.slice(&idx[3]..&idx[7]);
assert!(slice.eq_to_iter_vals([3, 4, 5, 6]));

let iter = slice.ring_iter(&idx[4]);
assert_eq!(iter.copied().collect::<Vec<_>>(), [4, 5, 6, 3,]);

let iter = slice.ring_iter(&idx[6]);
assert_eq!(iter.copied().collect::<Vec<_>>(), [6, 3, 4, 5]);

fn iter_from<'a>(&'a self, idx: &DoublyIdx<T>) -> DoublyIter<'a, T, P>

where M: 'a,

Creates a forward iterator:

• from the node with the given idx
• to the back of the list.

Panics

Panics if the index is invalid; i.e., idx_err does not return None.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back(0);
list.push_back(1);
let idx = list.push_back(2);
list.push_back(3);

let mut iter = list.iter_from(&idx);
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

fn iter_backward_from<'a>( &'a self, idx: &DoublyIdx<T>, ) -> Rev<DoublyIter<'a, T, P>>

where M: 'a,

Creates a backward iterator:

• from the node with the given idx
• to the front of the list.

Panics

Panics if the index is invalid; i.e., idx_err does not return None.

Example

use orx_linked_list::*;

let mut list = DoublyList::new();

list.push_back(0);
list.push_back(1);
let idx = list.push_back(2);
list.push_back(3);

let mut iter = list.iter_backward_from(&idx);
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

fn iter_links_from<'a>(&'a self, idx: &DoublyIdx<T>) -> DoublyLinkIter<'a, T, P>

where M: 'a,

Creates a forward iterator that yields pairs of successive elements representing links:

• starting from the node with the given idx
• to the back of the list.

Panics

Panics if the index is invalid; i.e., idx_err does not return None.

Examples

use orx_linked_list::*;

let tour: DoublyList<_> = ['a', 'b', 'c', 'd', 'e'].into_iter().collect();
let idx: Vec<_> = tour.indices().collect();

let mut iter = tour.iter_links_from(&idx[1]);

assert_eq!(iter.next(), Some((&'b', &'c')));
assert_eq!(iter.next(), Some((&'c', &'d')));
assert_eq!(iter.next(), Some((&'d', &'e')));

assert_eq!(iter.next(), None);

fn eq_to_iter_vals<I>(&self, iter: I) -> bool

where I: IntoIterator<Item = T>, T: PartialEq,

Returns true if the elements of the iterator are equal to those of the list.

fn eq_to_iter_refs<'a, I>(&self, iter: I) -> bool

where I: IntoIterator<Item = &'a T>, T: 'a + PartialEq,

Returns true if the elements of the iterator are equal to those of the list.

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> DoublyIterable<T, M, P> for L

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