Struct gapbuf::GapBuffer

pub struct GapBuffer<T>(_);

Dynamic array that allows efficient insertion and deletion operations clustered near the same location.

GapBuffer<T> has methods similar to Vec.

Methods

impl<T> GapBuffer<T>

pub fn new() -> Self

Constructs a new, empty GapBuffer<T>.

The gap buffer will not allocate until elements are pushed onto it.

Examples

let mut buf = GapBuffer::<i32>::new();

assert_eq!(buf.is_empty(), true);
assert_eq!(buf.len(), 0);
assert_eq!(buf.capacity(), 0);

use gapbuf::GapBuffer;

let mut buf = GapBuffer::new();
buf.push_back(5);

pub fn with_capacity(capacity: usize) -> Self

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

Examples

use gapbuf::GapBuffer;

let buf: GapBuffer<i32> = GapBuffer::with_capacity(5);
assert_eq!(buf.is_empty(), true);
assert_eq!(buf.len(), 0);
assert_eq!(buf.capacity(), 5);

pub fn capacity(&self) -> usize

Returns the number of elements the GapBuffer<T> can hold without reallocating.

Examples

use gapbuf::GapBuffer;

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

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

Reserves capacity for at least additional more elements to be inserted in the given GapBuffer<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 gapbuf::GapBuffer;

let mut buf = GapBuffer::new();
buf.push_back(1);
buf.reserve(10);
assert!(buf.capacity() >= 11);

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

Reserves the minimum capacity for exactly additional more elements to be inserted in the given GapBuffer<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 gapbuf::GapBuffer;

let mut buf = GapBuffer::new();
buf.push_back(1);
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the GapBuffer<T> as much as possible.

Examples

use gapbuf::GapBuffer;

let mut buf = GapBuffer::new();
buf.push_back(1);

buf.reserve(10);
assert!(buf.capacity() >= 11);

buf.shrink_to_fit();
assert_eq!(buf.capacity(), 1);

pub fn set_gap(&mut self, gap: usize)

Set gap offset of the GapBuffer<T>.

Panics

Panics if index > len.

Computational amount

O(n) , n = |self.gap() - gap|

pub fn gap(&self) -> usize

Return gap offset of the GapBuffer<T>.

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

Inserts an element at position index within the GapBuffer<T>.

Panics

Panics if index > len.

Panics if the number of elements in the gap buffer overflows a usize.

Computational amount

O(n) , n = |index - self.gap()|

pub fn insert_iter(     &mut self,     index: usize,     iter: impl IntoIterator<Item = T> )

Inserts multiple elements at position index within the GapBuffer<T>.

Panics

Panics if index > len.

Panics if the number of elements in the gap buffer overflows a usize.

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

Appends an element to the back of a GapBuffer.

Panics

Panics if the number of elements in the gap buffer overflows a usize.

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

Prepends an element to the GapBuffer.

Panics

Panics if the number of elements in the gap buffer overflows a usize.

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

Removes an element from the GapBuffer and returns it.

The removed element is replaced by the near the gap.

Panics

Panics if index >= self.len().

Computational amount

O(1)

Examples

use gapbuf::GapBuffer;

let mut buf = gap_buffer![1, 2, 3, 4, 5];
buf.set_gap(5);
let value = buf.swap_remove(0);
assert_eq!(value, 1);
assert_eq!(buf, [5, 2, 3, 4]);

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

Removes an element from the GapBuffer and returns it.

Panics

Panics if index >= self.len().

Computational amount

O(n), n = |index - self.gap()|

Examples

use gapbuf::GapBuffer;

let mut buf = gap_buffer![1, 2, 3, 4, 5];
let value = buf.remove(0);
assert_eq!(value, 1);
assert_eq!(buf, [2, 3, 4, 5]);

pub fn clear(&mut self)

Clears the GapBuffer, removing all values.

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

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

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

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

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

Examples

let mut buf = gap_buffer![1, 2, 3, 4];
buf.truncate(2);
assert_eq!(buf, [1, 2]);

pub fn retain(     &mut self,     f: impl FnMut(&T) -> bool )

Retains only the elements specified by the predicate.

Examples

let mut buf = gap_buffer![1, 2, 3, 4];
buf.retain(|&x| x%2 == 0);
assert_eq!(buf, [2, 4]);

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

Removes the first element and returns it, or None if the GapBuffer is empty.

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

Removes the last element and returns it, or None if the GapBuffer is empty.

Important traits for Drain<'a, T>

impl<'a, T> Iterator for Drain<'a, T> type Item = T;

pub fn drain(     &mut self,     range: impl RangeBounds<usize> ) -> Drain<T>

Creates a draining iterator that removes the specified range in the GapBuffer and yields the removed items.

Note 1: The element range is removed even if the iterator is only partially consumed or not consumed at all. Note 2: It is unspecified how many elements are removed from the GapBuffer if the Drain value is leaked.

Panics

Panics if the range is out of bounds.

Examples

let mut buf = gap_buffer![1, 2, 3, 4];

let d : Vec<_> = buf.drain(1..3).collect();
assert_eq!(buf, [1, 4]);
assert_eq!(d, [2, 3]);

buf.drain(..);
assert_eq!(buf.is_empty(), true);

Important traits for Splice<'a, T, I>

impl<'a, T: 'a, I: Iterator<Item = T>> Iterator for Splice<'a, T, I> type Item = T;

pub fn splice<I: IntoIterator<Item = T>>(     &mut self,     range: impl RangeBounds<usize>,     replace_with: I ) -> Splice<T, I::IntoIter>

Creates a splicing iterator that replaces the specified range in the GapBuffer with the given replace_with iterator and yields the removed items. replace_with does not need to be the same length as range.

The element range is removed even if the iterator is not consumed until the end.

This is optimal if the length of range is equal to the length of replace_with. Otherwise, call GapBuffer::set_gap internally.

Examples

let mut b = gap_buffer![1, 2, 3, 4];
let r : Vec<_> = b.splice(1..3, vec![7, 8, 9]).collect();

assert_eq!(b, [1, 7, 8, 9, 4]);
assert_eq!(r, [2, 3]);

impl<T> GapBuffer<T> where     T: Clone,

pub fn resize(&mut self, new_len: usize, value: T)

Resize the GapBuffer<T> in-place so that len is equal to new_len.

Methods from Deref<Target = Slice<T>>

pub fn len(&self) -> usize

Returns the number of elements in the GapBuffer.

pub fn is_empty(&self) -> bool

Returns true if the GapBuffer contains no elements.

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

Returns a reference to an element at index or None if out of bounds.

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

Returns a mutable reference to an element at index or None if out of bounds.

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

Swaps two elements in the GapBuffer.

Arguments

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

Panics

Panics if a >= self.len() or b >= self.len().

pub fn range(     &self,     range: impl RangeBounds<usize> ) -> Range<T>

Return a immutable sub-range of this Slice.

Panics

Panics if range is out of bounds.

Examples

let buf = gap_buffer![1, 2, 3, 4, 5];

let r1 = buf.range(1..);
assert_eq!(r1, [2, 3, 4, 5]);

let r2 = r1.range(1..3);
assert_eq!(r2, [3, 4]);

pub fn range_mut(     &mut self,     range: impl RangeBounds<usize> ) -> RangeMut<T>

Return a mutable sub-range of this Slice.

Panics

Panics if range is out of bounds.

Examples

let mut buf = gap_buffer![1, 2, 3, 4, 5];
{
    let mut r = buf.range_mut(1..);
    assert_eq!(r, [2, 3, 4, 5]);
    r[0] = 0;
}
assert_eq!(buf, [1, 0, 3, 4, 5]);

pub fn as_slices(&self) -> (&[T], &[T])

Returns a pair of slices. First slice is before gap. Second slice is after gap.

Examples

let mut buf = gap_buffer![1, 2, 3, 4, 5];
buf.set_gap(2);
let (s1, s2) = buf.as_slices();
assert_eq!(s1, [1, 2]);
assert_eq!(s2, [3, 4, 5]);

pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])

Returns a pair of slices. First slice is before gap. Second slice is after gap.

Examples

let mut buf = gap_buffer![1, 2, 3, 4, 5];
buf.set_gap(2);
{
    let (mut s1, mut s2) = buf.as_mut_slices();
    s1[0] = 10;
    s2[0] = 11;
}
assert_eq!(buf, [10, 2, 11, 4, 5]);

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

Returns an iterator over the Slice.

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

Returns an iterator that allows modifying each value.

Trait Implementations

impl<T: Hash> Hash for GapBuffer<T>

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

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> Drop for GapBuffer<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Deref for GapBuffer<T>

type Target = Slice<T>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T> DerefMut for GapBuffer<T>

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<T> FromIterator<T> for GapBuffer<T>

fn from_iter<S: IntoIterator<Item = T>>(s: S) -> GapBuffer<T>

Creates a value from an iterator.

impl<T: Clone> Clone for GapBuffer<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Extend<T> for GapBuffer<T>

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

Extends a collection with the contents of an iterator.

impl<'a, T: 'a + Copy> Extend<&'a T> for GapBuffer<T>

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

Extends a collection with the contents of an iterator.

impl<T> Default for GapBuffer<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T> Index<usize> for GapBuffer<T>

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 GapBuffer<T>

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

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

impl<T> Debug for GapBuffer<T> where     T: Debug,

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

Formats the value using the given formatter.

impl<T, S> PartialEq<S> for GapBuffer<T> where     T: PartialEq,     S: ?Sized,     &'b S: IntoIterator<Item = &'b T>,

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: Eq> Eq for GapBuffer<T>

impl<T, S> PartialOrd<S> for GapBuffer<T> where     T: PartialOrd,     S: ?Sized,     &'b S: IntoIterator<Item = &'b T>,

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

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

fn lt(&self, other: &Rhs) -> bool

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

fn le(&self, other: &Rhs) -> bool

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

fn gt(&self, other: &Rhs) -> bool

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

fn ge(&self, other: &Rhs) -> bool

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

impl<T: Ord> Ord for GapBuffer<T>

fn cmp(&self, other: &Self) -> 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.

impl<T> IntoIterator for GapBuffer<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = T;

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a GapBuffer<T>

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) -> Iter<'a, T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut GapBuffer<T>

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) -> IterMut<'a, T>

Creates an iterator from a value.