use std::alloc::*;
use std::cmp::*;
use std::fmt::{Debug, Error, Formatter};
use std::hash::*;
use std::iter::*;
use std::marker::PhantomData;
use std::mem;
use std::mem::*;
use std::ops::{Deref, DerefMut, Drop, FnMut, Index, IndexMut, RangeBounds};
use std::ptr;
use std::ptr::*;
use std::slice;
#[macro_export]
macro_rules! gap_buffer {
($elem:expr; $n:expr) => (
{
let mut buf = $crate::GapBuffer::with_capacity($n);
buf.resize($n, $elem);
buf
}
);
($($x:expr),*) => (
{
let mut buf = $crate::GapBuffer::new();
$(
buf.push_back($x);
)*
buf
}
);
($($x:expr,)*) => (gap_buffer![$($x),*])
}
#[derive(Hash)]
pub struct GapBuffer<T>(RawGapBuffer<T>);
impl<T> GapBuffer<T> {
#[inline]
pub fn new() -> Self {
GapBuffer(RawGapBuffer::new())
}
pub fn with_capacity(capacity: usize) -> Self {
let mut buf = GapBuffer::new();
buf.reserve_exact(capacity);
buf
}
#[inline]
pub fn capacity(&self) -> usize {
self.cap
}
pub fn reserve(&mut self, additional: usize) {
self.reserve_as(additional, false);
}
pub fn reserve_exact(&mut self, additional: usize) {
self.reserve_as(additional, true);
}
fn reserve_as(&mut self, additional: usize, exact: bool) {
let len = self.len();
let old_cap = self.cap;
let new_cap = len.checked_add(additional).expect("capacity overflow");
if new_cap <= old_cap {
return;
}
let new_cap = if exact {
new_cap
} else {
max(old_cap.saturating_mul(2), new_cap)
};
self.0.realloc(new_cap);
unsafe {
let p = self.as_mut_ptr();
let count = len - self.gap();
copy(p.add(old_cap - count), p.add(new_cap - count), count);
}
}
pub fn shrink_to_fit(&mut self) {
let len = self.len();
self.set_gap(len);
self.0.realloc(len);
}
#[inline]
pub fn set_gap(&mut self, gap: usize) {
assert!(gap <= self.len());
if gap != self.gap() {
self.move_values(gap);
self.gap = gap;
}
}
fn move_values(&mut self, gap: usize) {
let gap_old = self.gap;
let gap_len = self.gap_len();
let (src, dest, count) = if gap < gap_old {
(gap, gap + gap_len, gap_old - gap)
} else {
(gap_old + gap_len, gap_old, gap - gap_old)
};
let p = self.as_mut_ptr();
unsafe {
copy(p.add(src), p.add(dest), count);
}
}
#[inline]
pub fn gap(&self) -> usize {
self.gap
}
#[inline]
fn set_gap_with_reserve(&mut self, gap: usize, additional: usize) {
self.reserve(additional);
self.set_gap(gap);
}
#[inline]
pub fn insert(&mut self, index: usize, element: T) {
assert!(index <= self.len());
if self.gap() != index || self.len == self.capacity() {
self.set_gap_with_reserve(index, 1);
}
unsafe {
write(self.as_mut_ptr().add(index), element);
}
self.gap += 1;
self.len += 1;
}
#[deprecated(note = "insert_iter renamed to insert_many.")]
pub fn insert_iter(&mut self, index: usize, iter: impl IntoIterator<Item = T>) {
self.insert_many(index, iter);
}
pub fn insert_many(&mut self, mut index: usize, iter: impl IntoIterator<Item = T>) {
assert!(index <= self.len());
let mut iter = iter.into_iter();
let min_len = iter.size_hint().0;
if let Some(value) = iter.next() {
self.set_gap_with_reserve(index, max(min_len, 1));
let p = self.as_mut_ptr();
unsafe {
write(p.add(index), value);
self.gap += 1;
self.len += 1;
index += 1;
for _ in 1..min_len {
if let Some(value) = iter.next() {
write(p.add(index), value);
self.gap += 1;
self.len += 1;
index += 1;
} else {
return;
}
}
}
for value in iter {
self.insert(index, value);
index += 1;
}
}
}
#[inline]
pub fn push_back(&mut self, value: T) {
let len = self.len;
self.insert(len, value);
}
#[inline]
pub fn push_front(&mut self, value: T) {
let len = self.len();
if self.gap() != 0 || len == self.capacity() {
self.set_gap_with_reserve(0, 1);
}
unsafe {
write(self.as_mut_ptr().add(self.cap - self.len - 1), value);
}
self.len += 1;
}
pub fn swap_remove(&mut self, index: usize) -> T {
assert!(index < self.len());
unsafe {
let p = self.as_mut_ptr();
let value;
if index < self.gap() {
let pt = p.add(index);
value = pt.read();
self.gap -= 1;
copy(p.add(self.gap), pt, 1);
self.len -= 1;
} else {
let gap_len = self.gap_len();
let pt = p.add(index + gap_len);
value = pt.read();
copy(p.add(self.gap + gap_len), pt, 1);
self.len -= 1;
}
value
}
}
pub fn remove(&mut self, index: usize) -> T {
assert!(index <= self.len());
let offset;
if self.gap() <= index {
self.set_gap(index);
offset = self.cap - self.len() + index;
} else {
self.set_gap(index + 1);
self.gap = index;
offset = index;
}
self.len -= 1;
if self.len == 0 {
self.gap = 0
}
unsafe { ptr::read(self.as_ptr().add(offset)) }
}
pub fn clear(&mut self) {
self.truncate(0);
}
pub fn truncate(&mut self, len: usize) {
if needs_drop::<T>() {
while len < self.len {
let index = self.len - 1;
self.remove(index);
}
} else {
if self.gap < len {
self.set_gap(len);
} else {
self.gap = len;
}
self.len = len;
}
}
pub fn retain(&mut self, mut f: impl FnMut(&T) -> bool) {
let mut n = 0;
while n < self.len {
if f(&self[n]) {
n += 1;
} else {
self.remove(n);
}
}
}
pub fn pop_front(&mut self) -> Option<T> {
let len = self.len;
match len {
0 => None,
_ => Some(self.remove(0)),
}
}
pub fn pop_back(&mut self) -> Option<T> {
let len = self.len;
match len {
0 => None,
_ => Some(self.remove(len - 1)),
}
}
pub fn drain(&mut self, range: impl RangeBounds<usize>) -> Drain<T> {
let (idx, len) = self.to_idx_len(range);
Drain {
buf: self,
idx,
len,
}
}
pub fn splice<I: IntoIterator<Item = T>>(
&mut self,
range: impl RangeBounds<usize>,
replace_with: I,
) -> Splice<T, I::IntoIter> {
let (idx, len) = self.to_idx_len(range);
Splice {
buf: self,
idx,
end: idx + len,
iter: replace_with.into_iter().fuse(),
}
}
}
pub struct Splice<'a, T: 'a, I: Iterator<Item = T>> {
buf: &'a mut GapBuffer<T>,
idx: usize,
end: usize,
iter: Fuse<I>,
}
impl<'a, T: 'a, I: Iterator<Item = T>> Iterator for Splice<'a, T, I> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.idx < self.end {
if let Some(value) = self.iter.next() {
let value = mem::replace(&mut self.buf[self.idx], value);
self.idx += 1;
Some(value)
} else {
let value = self.buf.remove(self.idx);
self.end -= 1;
Some(value)
}
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let size = self.end - self.idx;
(size, Some(size))
}
}
impl<'a, T: 'a, I: Iterator<Item = T>> Drop for Splice<'a, T, I> {
fn drop(&mut self) {
while self.next().is_some() {}
self.buf.insert_many(self.idx, &mut self.iter);
}
}
impl<'a, T: 'a, I: Iterator<Item = T>> ExactSizeIterator for Splice<'a, T, I> {}
impl<'a, T: 'a, I: Iterator<Item = T>> FusedIterator for Splice<'a, T, I> {}
impl<'a, T: 'a, I: DoubleEndedIterator<Item = T>> DoubleEndedIterator for Splice<'a, T, I> {
fn next_back(&mut self) -> Option<T> {
if self.idx < self.end {
let i = self.end - 1;
let value = if let Some(value) = self.iter.next_back() {
mem::replace(&mut self.buf[i], value)
} else {
self.buf.remove(i)
};
self.end -= 1;
Some(value)
} else {
None
}
}
}
impl<T> GapBuffer<T>
where
T: Clone,
{
pub fn resize(&mut self, new_len: usize, value: T) {
let old_len = self.len();
if new_len < old_len {
self.truncate(new_len);
}
if new_len > old_len {
self.reserve(new_len - old_len);
while self.len < new_len {
self.push_back(value.clone());
}
}
}
}
impl<T> Drop for GapBuffer<T> {
fn drop(&mut self) {
unsafe {
let (s0, s1) = self.as_mut_slices();
try_finally!(drop_in_place(s0), drop_in_place(s1));
}
}
}
impl<T> Deref for GapBuffer<T> {
type Target = Slice<T>;
#[inline]
fn deref(&self) -> &Self::Target {
&(self.0).0
}
}
impl<T> DerefMut for GapBuffer<T> {
#[inline]
fn deref_mut(&mut self) -> &mut Self::Target {
&mut (self.0).0
}
}
impl<T> FromIterator<T> for GapBuffer<T> {
fn from_iter<S: IntoIterator<Item = T>>(s: S) -> GapBuffer<T> {
let mut buf = GapBuffer::new();
buf.extend(s);
buf
}
}
impl<T: Clone> Clone for GapBuffer<T> {
fn clone(&self) -> Self {
self.iter().cloned().collect()
}
}
impl<T> Extend<T> for GapBuffer<T> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let len = self.len;
self.insert_many(len, iter);
}
}
impl<'a, T: 'a + Copy> Extend<&'a T> for GapBuffer<T> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
#[derive(Hash)]
struct RawGapBuffer<T>(Slice<T>);
impl<T> RawGapBuffer<T> {
fn new() -> Self {
RawGapBuffer(Slice::empty())
}
fn realloc(&mut self, new_cap: usize) {
let old_cap = self.0.cap;
if old_cap == new_cap {
return;
}
if size_of::<T>() != 0 {
unsafe {
let old_layout = Self::get_layout(old_cap);
let new_layout = Self::get_layout(new_cap);
let p = self.0.ptr.as_ptr() as *mut u8;
self.0.ptr = if new_cap == 0 {
dealloc(p, old_layout);
NonNull::dangling()
} else {
NonNull::new(if old_cap == 0 {
alloc(new_layout)
} else {
realloc(p, old_layout, new_layout.size())
} as *mut T)
.unwrap_or_else(|| handle_alloc_error(new_layout))
};
}
}
self.0.cap = new_cap;
}
fn get_layout(cap: usize) -> Layout {
let new_size = size_of::<T>()
.checked_mul(cap)
.expect("memory size overflow");
Layout::from_size_align(new_size, align_of::<T>()).unwrap()
}
}
impl<T> Drop for RawGapBuffer<T> {
fn drop(&mut self) {
self.realloc(0)
}
}
#[derive(Hash)]
pub struct Range<'a, T: 'a> {
s: Slice<T>,
_phantom: PhantomData<&'a [T]>,
}
#[derive(Hash)]
pub struct RangeMut<'a, T: 'a> {
s: Slice<T>,
_phantom: PhantomData<&'a mut [T]>,
}
impl<'a, T: 'a> Range<'a, T> {
#[inline]
unsafe fn new(s: Slice<T>) -> Self {
Range {
s,
_phantom: PhantomData::default(),
}
}
#[inline]
pub fn empty() -> Self {
unsafe { Range::new(Slice::empty()) }
}
#[inline]
pub fn get(&self, index: usize) -> Option<&'a T> {
unsafe { self.s.get_with_lifetime(index) }
}
pub fn range(&self, range: impl RangeBounds<usize>) -> Range<'a, T> {
unsafe { self.range_with_lifetime(range) }
}
pub fn as_slices(&self) -> (&'a [T], &'a [T]) {
unsafe { self.as_slices_with_lifetime() }
}
}
impl<'a, T: 'a> RangeMut<'a, T> {
#[inline]
unsafe fn new(s: Slice<T>) -> Self {
RangeMut {
s,
_phantom: PhantomData::default(),
}
}
#[inline]
pub fn empty() -> Self {
unsafe { RangeMut::new(Slice::empty()) }
}
}
impl<'a, T> Deref for Range<'a, T> {
type Target = Slice<T>;
#[inline]
fn deref(&self) -> &Self::Target {
&self.s
}
}
impl<'a, T> Deref for RangeMut<'a, T> {
type Target = Slice<T>;
#[inline]
fn deref(&self) -> &Self::Target {
&self.s
}
}
impl<'a, T> DerefMut for RangeMut<'a, T> {
#[inline]
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.s
}
}
impl<'a, T> Clone for Range<'a, T> {
fn clone(&self) -> Self {
unsafe {
Range::new(Slice {
ptr: self.ptr,
cap: self.cap,
gap: self.gap,
len: self.len,
})
}
}
}
pub struct Slice<T> {
ptr: NonNull<T>,
cap: usize,
gap: usize,
len: usize,
}
impl<T> Slice<T> {
pub fn empty() -> Self {
Slice {
ptr: NonNull::dangling(),
cap: 0,
gap: 0,
len: 0,
}
}
#[inline]
pub fn len(&self) -> usize {
self.len
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn get(&self, index: usize) -> Option<&T> {
unsafe { self.get_with_lifetime(index) }
}
#[inline]
unsafe fn get_with_lifetime<'a>(&self, index: usize) -> Option<&'a T> {
self.get_offset(index).map(|o| &*self.as_ptr().add(o))
}
#[inline]
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
self.get_offset(index)
.map(|o| unsafe { &mut *self.as_mut_ptr().add(o) })
}
#[inline]
pub fn swap(&mut self, a: usize, b: usize) {
let oa = self.get_offset(a).expect("a is out of bounds.");
let ob = self.get_offset(b).expect("b is out of bounds.");
let p = self.as_mut_ptr();
unsafe { ptr::swap(p.add(oa), p.add(ob)) }
}
pub fn range(&self, range: impl RangeBounds<usize>) -> Range<T> {
unsafe { self.range_with_lifetime(range) }
}
unsafe fn range_with_lifetime<'a>(&self, range: impl RangeBounds<usize>) -> Range<'a, T> {
Range::new(self.range_slice(range))
}
pub fn range_mut(&mut self, range: impl RangeBounds<usize>) -> RangeMut<T> {
unsafe { RangeMut::new(self.range_slice(range)) }
}
unsafe fn range_slice(&self, range: impl RangeBounds<usize>) -> Slice<T> {
let (idx, len) = self.to_idx_len(range);
if len == 0 {
return Slice::empty();
}
let gap_is_before = self.gap <= idx;
let gap_is_after = idx + len <= self.gap;
let gap = if gap_is_before {
0
} else if !gap_is_after {
self.gap - idx
} else {
len
};
let begin = if gap_is_before { self.gap_len() } else { 0 } + idx;
let end = if !gap_is_after { self.gap_len() } else { 0 } + idx + len;
Slice {
ptr: NonNull::new(self.ptr.as_ptr().add(begin)).unwrap(),
cap: end - begin,
gap,
len,
}
}
fn to_idx_len(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
use std::ops::Bound::*;
const MAX: usize = usize::max_value();
let len = self.len;
let idx = match range.start_bound() {
Included(&idx) => idx,
Excluded(&MAX) => panic!("attempted to index slice up to maximum usize"),
Excluded(&idx) => idx + 1,
Unbounded => 0,
};
if idx > len {
panic!("index {} out of range for slice of length {}", idx, len);
}
let end = match range.end_bound() {
Included(&MAX) => panic!("attempted to index slice up to maximum usize"),
Included(&idx) => idx + 1,
Excluded(&idx) => idx,
Unbounded => len,
};
if end > len {
panic!("index {} out of range for slice of length {}", end, len);
}
if end < idx {
panic!("slice index starts at {} but ends at {}", idx, end);
}
(idx, end - idx)
}
pub fn as_slices(&self) -> (&[T], &[T]) {
unsafe { self.as_slices_with_lifetime() }
}
unsafe fn as_slices_with_lifetime<'a>(&self) -> (&'a [T], &'a [T]) {
let p0 = self.as_ptr();
let c1 = self.len - self.gap;
let p1 = p0.add(self.cap - c1);
(
slice::from_raw_parts(p0, self.gap),
slice::from_raw_parts(p1, c1),
)
}
pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
unsafe {
let p0 = self.as_mut_ptr();
let c1 = self.len - self.gap;
let p1 = p0.add(self.cap - c1);
(
slice::from_raw_parts_mut(p0, self.gap),
slice::from_raw_parts_mut(p1, c1),
)
}
}
pub fn iter(&self) -> Iter<T> {
let (s0, s1) = self.as_slices();
s0.iter().chain(s1.iter())
}
pub fn iter_mut(&mut self) -> IterMut<T> {
let (s0, s1) = self.as_mut_slices();
s0.iter_mut().chain(s1.iter_mut())
}
#[inline]
fn get_offset(&self, index: usize) -> Option<usize> {
if index < self.gap {
Some(index)
} else if index < self.len {
Some(index + self.gap_len())
} else {
None
}
}
#[inline]
fn gap_len(&self) -> usize {
self.cap - self.len
}
#[inline]
fn as_ptr(&self) -> *const T {
self.ptr.as_ptr()
}
#[inline]
fn as_mut_ptr(&mut self) -> *mut T {
self.ptr.as_ptr()
}
}
unsafe impl<T: Sync> Sync for Slice<T> {}
unsafe impl<T: Send> Send for Slice<T> {}
impl<T> Default for GapBuffer<T> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<'a, T> Default for Range<'a, T> {
#[inline]
fn default() -> Self {
Self::empty()
}
}
impl<'a, T> Default for RangeMut<'a, T> {
#[inline]
fn default() -> Self {
Self::empty()
}
}
impl<T> Index<usize> for GapBuffer<T> {
type Output = T;
#[inline]
fn index(&self, index: usize) -> &T {
self.deref().index(index)
}
}
impl<T> IndexMut<usize> for GapBuffer<T> {
#[inline]
fn index_mut(&mut self, index: usize) -> &mut T {
self.deref_mut().index_mut(index)
}
}
impl<'a, T> Index<usize> for Range<'a, T> {
type Output = T;
#[inline]
fn index(&self, index: usize) -> &T {
self.deref().index(index)
}
}
impl<'a, T> Index<usize> for RangeMut<'a, T> {
type Output = T;
#[inline]
fn index(&self, index: usize) -> &T {
self.deref().index(index)
}
}
impl<'a, T> IndexMut<usize> for RangeMut<'a, T> {
#[inline]
fn index_mut(&mut self, index: usize) -> &mut T {
self.deref_mut().index_mut(index)
}
}
impl<T> Index<usize> for Slice<T> {
type Output = T;
#[inline]
fn index(&self, index: usize) -> &T {
self.get(index).expect("index out of bounds")
}
}
impl<T> IndexMut<usize> for Slice<T> {
#[inline]
fn index_mut(&mut self, index: usize) -> &mut T {
self.get_mut(index).expect("index out of bounds")
}
}
impl<T> Debug for GapBuffer<T>
where
T: Debug,
{
fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
self.deref().fmt(f)
}
}
impl<'a, T> Debug for Range<'a, T>
where
T: Debug,
{
fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
self.deref().fmt(f)
}
}
impl<'a, T> Debug for RangeMut<'a, T>
where
T: Debug,
{
fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
self.deref().fmt(f)
}
}
impl<T> Debug for Slice<T>
where
T: Debug,
{
fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
f.debug_list().entries(self).finish()
}
}
impl<T: Hash> Hash for Slice<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
for value in self {
value.hash(state);
}
}
}
impl<T, S> PartialEq<S> for GapBuffer<T>
where
T: PartialEq,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn eq(&self, other: &S) -> bool {
self.deref().eq(other)
}
}
impl<T: Eq> Eq for GapBuffer<T> {}
impl<'a, T, S> PartialEq<S> for Range<'a, T>
where
T: PartialEq,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn eq(&self, other: &S) -> bool {
self.deref().eq(other)
}
}
impl<'a, T: Eq> Eq for Range<'a, T> {}
impl<'a, T, S> PartialEq<S> for RangeMut<'a, T>
where
T: PartialEq,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn eq(&self, other: &S) -> bool {
self.deref().eq(other)
}
}
impl<'a, T: Eq> Eq for RangeMut<'a, T> {}
impl<T, S> PartialEq<S> for Slice<T>
where
T: PartialEq,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn eq(&self, other: &S) -> bool {
self.iter().eq(other)
}
}
impl<T: Eq> Eq for Slice<T> {}
impl<T, S> PartialOrd<S> for GapBuffer<T>
where
T: PartialOrd,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn partial_cmp(&self, other: &S) -> Option<Ordering> {
self.deref().partial_cmp(other)
}
}
impl<T: Ord> Ord for GapBuffer<T> {
fn cmp(&self, other: &Self) -> Ordering {
self.deref().cmp(other)
}
}
impl<'a, T, S> PartialOrd<S> for Range<'a, T>
where
T: PartialOrd,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn partial_cmp(&self, other: &S) -> Option<Ordering> {
self.deref().partial_cmp(other)
}
}
impl<'a, T: Ord> Ord for Range<'a, T> {
fn cmp(&self, other: &Self) -> Ordering {
self.deref().cmp(other)
}
}
impl<'a, T, S> PartialOrd<S> for RangeMut<'a, T>
where
T: PartialOrd,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn partial_cmp(&self, other: &S) -> Option<Ordering> {
self.deref().partial_cmp(other)
}
}
impl<'a, T: Ord> Ord for RangeMut<'a, T> {
fn cmp(&self, other: &Self) -> Ordering {
self.deref().cmp(other)
}
}
impl<T, S> PartialOrd<S> for Slice<T>
where
T: PartialOrd,
S: ?Sized,
for<'b> &'b S: IntoIterator<Item = &'b T>,
{
fn partial_cmp(&self, other: &S) -> Option<Ordering> {
self.iter().partial_cmp(other)
}
}
impl<T: Ord> Ord for Slice<T> {
fn cmp(&self, other: &Self) -> Ordering {
self.iter().cmp(other)
}
}
pub type Iter<'a, T> = Chain<slice::Iter<'a, T>, slice::Iter<'a, T>>;
pub type IterMut<'a, T> = Chain<slice::IterMut<'a, T>, slice::IterMut<'a, T>>;
pub struct IntoIter<T> {
buf: GapBuffer<T>,
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.buf.pop_front()
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.buf.len();
(len, Some(len))
}
}
impl<T> ExactSizeIterator for IntoIter<T> {}
impl<T> FusedIterator for IntoIter<T> {}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.buf.pop_back()
}
}
impl<T> IntoIterator for GapBuffer<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
IntoIter { buf: self }
}
}
impl<'a, T> IntoIterator for &'a GapBuffer<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, 'b, T> IntoIterator for &'a Range<'b, T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, 'b, T> IntoIterator for &'a RangeMut<'b, T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, T> IntoIterator for &'a Slice<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, T> IntoIterator for &'a mut GapBuffer<T> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> {
self.iter_mut()
}
}
impl<'a, T> IntoIterator for &'a mut RangeMut<'a, T> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> {
self.iter_mut()
}
}
impl<'a, T> IntoIterator for &'a mut Slice<T> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> {
self.iter_mut()
}
}
pub struct Drain<'a, T: 'a> {
buf: &'a mut GapBuffer<T>,
idx: usize,
len: usize,
}
impl<'a, T> Iterator for Drain<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.len == 0 {
None
} else {
self.len -= 1;
Some(self.buf.remove(self.idx))
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<'a, T> Drop for Drain<'a, T> {
fn drop(&mut self) {
let len = self.len;
self.nth(len);
}
}
impl<'a, T> ExactSizeIterator for Drain<'a, T> {}
impl<'a, T> FusedIterator for Drain<'a, T> {}