Struct RotatedVec

Source

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

Expand description

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);
}

Implementations§

Source §

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

Source

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();

Source

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);

Source

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);

Source

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);

Source

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());

Source

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);

Source

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);

Source

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);

Source

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);

Source

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());

Source

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);

Source

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());

Source

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);

Source

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());

Source

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());

Source

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);

Source

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());

Source

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());

Source

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());

Source

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());

Source

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());

Source

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()));

Source

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()));