Struct rotated_vec::RotatedVec

pub struct RotatedVec<T> { /* fields omitted */ }

A dynamic array based on a 2-level rotated array.

This is roughly a drop-in replacement for Vec, except that there is no deref to a slice, so underlying slice methods are unavailable. Many of the most useful slice methods have been ported.

Examples

use rotated_vec::RotatedVec;

// Type inference lets us omit an explicit type signature (which
// would be `RotatedVec<i32>` in this example).
let mut vec = RotatedVec::new();

// Push some integers onto the vector.
vec.push(-1);
vec.push(6);
vec.push(1729);
vec.push(24);

// Pop an integer from the vector.
vec.pop();

// Insert an integer at a given index.
vec.insert(1, 0);

// Remove an integer at a given index.
vec.remove(1);

// Change an integer at a given index.
vec[1] = 0;

// Iterate over everything.
for int in &vec {
    println!("{}", int);
}

Methods

impl<T> RotatedVec<T> where
    T: Copy + Default + Debug, 

pub fn new() -> Self

Makes a new RotatedVec without any heap allocations.

This is a constant-time operation.

Examples

#![allow(unused_mut)]
use rotated_vec::RotatedVec;

let mut vec: RotatedVec<i32> = RotatedVec::new();

pub fn with_capacity(capacity: usize) -> RotatedVec<T>

Constructs a new, empty RotatedVec<T> with the specified capacity.

The vector will be able to hold exactly capacity elements without reallocating. If capacity is 0, the vector will not allocate.

It is important to note that although the returned vector has the capacity specified, the vector will have a zero length.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::with_capacity(10);

// The vector contains no items, even though it has capacity for more
assert_eq!(vec.len(), 0);

// These are all done without reallocating...
for i in 0..10 {
    vec.push(i);
}

// ...but this may make the vector reallocate
vec.push(11);

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

Returns a reference to the value in the array, if any, at the given index.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let vec: RotatedVec<_> = vec![1, 2, 3].into();
assert_eq!(vec.get(0), Some(&1));
assert_eq!(vec.get(3), None);

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

Returns a mutable reference to the value in the array, if any, at the given index.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
assert_eq!(vec.get_mut(0), Some(&mut 1));
assert_eq!(vec.get_mut(3), None);

pub fn swap(&mut self, a: usize, b: usize)

Swaps two elements in the vector.

This is a constant-time operation.

Arguments

• a - The index of the first element
• b - The index of the second element

Panics

Panics if a or b are out of bounds.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec!["a", "b", "c", "d"].into();
vec.swap(1, 3);
assert_eq!(vec, vec!["a", "d", "c", "b"].into());

pub fn capacity(&self) -> usize

Returns the number of elements the vector can hold without reallocating.

Examples

use rotated_vec::RotatedVec;

let vec: RotatedVec<i32> = RotatedVec::with_capacity(10);
assert_eq!(vec.capacity(), 10);

pub fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more elements to be inserted in the given RotatedVec<T>. After calling reserve_exact, capacity will be greater than or equal to self.len() + additional. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

Panics

Panics if the new capacity overflows usize.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1].into();
vec.reserve_exact(10);
assert!(vec.capacity() >= 11);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given RotatedVec<T>. The collection may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

Panics

Panics if the new capacity overflows usize.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1].into();
vec.reserve(10);
assert!(vec.capacity() >= 11);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the vector as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the vector that there is space for a few more elements.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::with_capacity(10);
vec.extend([1, 2, 3].iter().cloned());
assert_eq!(vec.capacity(), 10);
vec.shrink_to_fit();
assert!(vec.capacity() >= 3);

pub fn truncate(&mut self, len: usize)

Shortens the vector, keeping the first len elements and dropping the rest.

This is an O(√n) operation.

If len is greater than the vector's current length, this has no effect.

Note that this method has no effect on the allocated capacity of the vector.

Examples

Truncating a five element vector to two elements:

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3, 4, 5].into();
vec.truncate(2);
assert_eq!(vec, vec![1, 2].into());

No truncation occurs when len is greater than the vector's current length:

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
vec.truncate(8);
assert_eq!(vec, vec![1, 2, 3].into());

Truncating when len == 0 is equivalent to calling the [clear] method.

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
vec.truncate(0);
assert_eq!(vec, vec![].into());

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> where
    T: Copy + Default + Debug,  type Item = &'a T;

pub fn iter(&self) -> Iter<T>

Gets an iterator that visits the values in the RotatedVec in order.

Examples

use rotated_vec::RotatedVec;

let vec: RotatedVec<usize> = vec![1, 2, 3].into();
let mut iter = vec.iter();
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

Important traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> where
    T: Copy + Default + Debug,  type Item = &'a mut T;

pub fn iter_mut(&mut self) -> IterMut<T>

Gets a mutable iterator that visits the values in the RotatedVec in order.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<usize> = vec![1, 2, 3].into();
let mut iter = vec.iter_mut();
let mut current_elem = None;
current_elem = iter.next();
assert_eq!(current_elem, Some(&mut 1));
*current_elem.unwrap() = 2;
current_elem = iter.next();
assert_eq!(current_elem, Some(&mut 2));
*current_elem.unwrap() = 3;
current_elem = iter.next();
assert_eq!(current_elem, Some(&mut 3));
*current_elem.unwrap() = 4;
assert_eq!(iter.next(), None);
assert_eq!(vec, vec![2, 3, 4].into());

pub fn len(&self) -> usize

Returns the number of elements in the set.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::new();
assert_eq!(vec.len(), 0);
vec.push(1);
assert_eq!(vec.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::new();
assert!(vec.is_empty());
vec.push(1);
assert!(!vec.is_empty());

pub fn clear(&mut self)

Clears the vector, removing all values.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::new();
vec.push(1);
vec.clear();
assert!(vec.is_empty());

pub fn contains(&self, x: &T) -> bool where
    T: PartialEq<T>, 

Returns true if the RotatedVec contains an element equal to the given value.

Examples

use rotated_vec::RotatedVec;

let mut vec = RotatedVec::new();

vec.push(0);
vec.push(1);

assert_eq!(vec.contains(&1), true);
assert_eq!(vec.contains(&10), false);

pub fn push(&mut self, value: T)

Appends an element to the back of a collection.

This is a constant-time operation.

Panics

Panics if the number of elements in the vector overflows a usize.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2].into();
vec.push(3);
assert_eq!(vec, vec![1, 2, 3].into());

pub fn pop(&mut self) -> Option<T>

Removes the last element from a vector and returns it, or None if it is empty.

This is a constant-time operation.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
assert_eq!(vec.pop(), Some(3));
assert_eq!(vec, vec![1, 2].into());

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

Inserts an element at position index within the vector.

This is an O(√n) operation.

Panics

Panics if index > len.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
vec.insert(1, 4);
assert_eq!(vec, vec![1, 4, 2, 3].into());
vec.insert(4, 5);
assert_eq!(vec, vec![1, 4, 2, 3, 5].into());

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

Removes and returns the element at position index within the vector.

This is an O(√n) operation.

Panics

Panics if index is out of bounds.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
assert_eq!(vec.remove(1), 2);
assert_eq!(vec, vec![1, 3].into());

pub fn append(&mut self, other: &mut Self)

Moves all the elements of other into self, leaving other empty.

Panics

Panics if the number of elements in the array overflows a usize.

Examples

use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![1, 2, 3].into();
let mut vec2: RotatedVec<_> = vec![4, 5, 6].into();
vec.append(&mut vec2);
assert_eq!(vec, vec![1, 2, 3, 4, 5, 6].into());
assert_eq!(vec2, vec![].into());

pub fn sort(&mut self) where
    T: Ord, 

Sorts the vector.

This sort is stable (i.e., does not reorder equal elements) and O(n log n) worst-case.

When applicable, unstable sorting is preferred because it is generally faster than stable sorting and it doesn't allocate auxiliary memory. See sort_unstable.

Current implementation

The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the vector is nearly sorted, or consists of two or more sorted sequences concatenated one after another.

Also, it allocates temporary storage half the size of self, but for short vectors a non-allocating insertion sort is used instead.

Examples

use is_sorted::IsSorted;
use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![-5, 4, 1, -3, 2].into();

vec.sort();
assert!(IsSorted::is_sorted(&mut vec.iter()));

pub fn sort_unstable(&mut self) where
    T: Ord, 

Sorts the vector, but may not preserve the order of equal elements.

This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate), and O(n log n) worst-case.

Current implementation

The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on vectors with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.

It is typically faster than stable sorting, except in a few special cases, e.g., when the vector consists of several concatenated sorted sequences.

Examples

use is_sorted::IsSorted;
use rotated_vec::RotatedVec;

let mut vec: RotatedVec<_> = vec![-5, 4, 1, -3, 2].into();

vec.sort_unstable();
assert!(IsSorted::is_sorted(&mut vec.iter()));

Trait Implementations

impl<T: Clone> Clone for RotatedVec<T>

fn clone(&self) -> RotatedVec<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for RotatedVec<T>

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

Formats the value using the given formatter.

impl<T> Default for RotatedVec<T> where
    T: Copy + Default + Debug, 

fn default() -> RotatedVec<T>

Returns the "default value" for a type.

impl<T> Eq for RotatedVec<T> where
    T: Copy + Default + Debug + PartialEq, 

impl<T> Extend<T> for RotatedVec<T> where
    T: Copy + Default + Debug, 

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

Extends a collection with the contents of an iterator.

impl<'a, T> From<&'a [T]> for RotatedVec<T> where
    T: Copy + Default + Debug, 

fn from(slice: &'a [T]) -> Self

Performs the conversion.

impl<T> From<Vec<T>> for RotatedVec<T> where
    T: Copy + Default + Debug, 

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

Performs the conversion.

impl<T> FromIterator<T> for RotatedVec<T> where
    T: Copy + Default + Debug, 

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> Hash for RotatedVec<T> where
    T: Copy + Default + Debug + PartialEq + Hash, 

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<T> Index<usize> for RotatedVec<T> where
    T: Copy + Default + Debug, 

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &T

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for RotatedVec<T> where
    T: Copy + Default + Debug, 

fn index_mut(&mut self, index: usize) -> &mut T

Performs the mutable indexing (container[index]) operation.

impl<T> Into<Vec<T>> for RotatedVec<T> where
    T: Copy + Default + Debug, 

fn into(self) -> Vec<T>

Performs the conversion.

impl<'a, T> IntoIterator for &'a RotatedVec<T> where
    T: Copy + Default + Debug, 

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut RotatedVec<T> where
    T: Copy + Default + Debug, 

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for RotatedVec<T> where
    T: Copy + Default + Debug, 

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Ord for RotatedVec<T> where
    T: Copy + Default + Debug + Ord, 

fn cmp(&self, other: &RotatedVec<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

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

Restrict a value to a certain interval.

impl<T> PartialEq<RotatedVec<T>> for RotatedVec<T> where
    T: Copy + Default + Debug + PartialEq, 

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T> PartialOrd<RotatedVec<T>> for RotatedVec<T> where
    T: Copy + Default + Debug + PartialOrd, 

fn partial_cmp(&self, other: &RotatedVec<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.