Struct GapBuffer

Source

pub struct GapBuffer<T>(/* private fields */);

Expand description

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

GapBuffer<T> has methods similar to Vec.

Implementations§

Source §

impl<T> GapBuffer<T>

Source

pub const 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 gap_buf::GapBuffer;

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

Source

pub fn with_capacity(capacity: usize) -> Self

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

§Examples

use gap_buf::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);

Source

pub const fn capacity(&self) -> usize

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

§Examples

use gap_buf::GapBuffer;

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

Source

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 gap_buf::GapBuffer;

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

Source

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 gap_buf::GapBuffer;

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

Source

pub fn shrink_to_fit(&mut self)

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

§Examples

use gap_buf::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);

Source

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|

Source

pub const fn gap(&self) -> usize

Return gap offset of the GapBuffer<T>.

Source

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

Source

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

👎Deprecated: insert_iter renamed to insert_many.

Source

pub fn insert_many(&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.

Source

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.

Source

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.

Source

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 gap_buf::gap_buffer;

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

Source

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 gap_buf::gap_buffer;

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

Source

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.

Source

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

use gap_buf::gap_buffer;

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

Source

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

Retains only the elements specified by the predicate.

§Examples

use gap_buf::gap_buffer;

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

Source

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

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

Source

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

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

Source

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

use gap_buf::gap_buffer;

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

Source

pub fn extract_if<F>( &mut self, range: impl RangeBounds<usize>, filter: F, ) -> ExtractIf<'_, T, F> ⓘ
where F: FnMut(&mut T) -> bool,

Creates an extracting iterator that removes elements from the specified range in the GapBuffer based on a predicate

Note that this iterator will only remove elements that are consumed. If dropped, it will retain the remaining elements.

§Panics

Panics if the range is out of bounds.

§Examples

use gap_buf::gap_buffer;

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

let d : Vec<_> = buf.extract_if(.., |num| *num % 2 == 1).collect();
assert_eq!(buf, [2, 4]);
assert_eq!(d, [1, 3]);

buf.extract_if(.., |_| true);
assert_eq!(buf.is_empty(), false);

Source

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

use gap_buf::gap_buffer;

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

Source §

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

Source

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>>§

Source

pub fn len(&self) -> usize

Returns the number of elements in the GapBuffer.

Source

pub fn is_empty(&self) -> bool

Returns true if the GapBuffer contains no elements.

Source

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

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

Source

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.

Source

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

Source

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

use gap_buf::gap_buffer;

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

Source

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

use gap_buf::gap_buffer;

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

Source

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

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

§Examples

use gap_buf::gap_buffer;

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

Source

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

use gap_buf::gap_buffer;

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