gap_buf/
gap_buffer.rs

1use std::alloc::{alloc, dealloc, handle_alloc_error, realloc, Layout};
2use std::cmp::{max, Ordering};
3use std::fmt::{Debug, Error, Formatter};
4use std::hash::{Hash, Hasher};
5use std::iter::{Chain, Fuse, FusedIterator};
6use std::marker::PhantomData;
7use std::mem::{self, align_of, needs_drop, size_of};
8use std::ops::{Deref, DerefMut, Drop, FnMut, Index, IndexMut, RangeBounds};
9use std::ptr::{self, copy, drop_in_place, write, NonNull};
10use std::slice;
11
12/// Creates a [`GapBuffer`] containing the arguments.
13///
14/// `gap_buffer!` allows [`GapBuffer`] to be defined with the same syntax as [`vec!`](std::vec!).
15/// There are two forms of this macro:
16///
17/// - Create a [`GapBuffer`] containing a given list of elements:
18///
19/// ```
20/// use gap_buf::gap_buffer;
21/// let b = gap_buffer![1, 2, 3];
22/// assert_eq!(b.len(), 3);
23/// assert_eq!(b[0], 1);
24/// assert_eq!(b[1], 2);
25/// assert_eq!(b[2], 3);
26/// ```
27///
28/// - Create a [`GapBuffer`] from a given element and size:
29///
30/// ```
31/// use gap_buf::gap_buffer;
32/// let b = gap_buffer!["abc"; 2];
33/// assert_eq!(b.len(), 2);
34/// assert_eq!(b[0], "abc");
35/// assert_eq!(b[1], "abc");
36/// ```
37#[macro_export]
38macro_rules! gap_buffer {
39    ($elem:expr; $n:expr) => (
40        {
41            let mut buf = $crate::GapBuffer::with_capacity($n);
42            buf.resize($n, $elem);
43            buf
44        }
45    );
46    ($($x:expr),*) => (
47        {
48            let mut buf = $crate::GapBuffer::new();
49            $(
50                buf.push_back($x);
51            )*
52            buf
53        }
54    );
55    ($($x:expr,)*) => (gap_buffer![$($x),*])
56}
57
58/// Dynamic array that allows efficient insertion and deletion operations clustered near the same location.
59///
60/// `GapBuffer<T>` has methods similar to [`Vec`](std::vec::Vec).
61#[derive(Hash)]
62pub struct GapBuffer<T>(RawGapBuffer<T>);
63
64impl<T> GapBuffer<T> {
65    /// Constructs a new, empty `GapBuffer<T>`.
66    ///
67    /// The gap buffer will not allocate until elements are pushed onto it.
68    ///
69    /// # Examples
70    /// ```
71    /// # use gap_buf::GapBuffer;
72    /// let mut buf = GapBuffer::<i32>::new();
73    ///
74    /// assert_eq!(buf.is_empty(), true);
75    /// assert_eq!(buf.len(), 0);
76    /// assert_eq!(buf.capacity(), 0);
77    /// ```
78    ///
79    /// ```
80    /// use gap_buf::GapBuffer;
81    ///
82    /// let mut buf = GapBuffer::new();
83    /// buf.push_back(5);
84    /// ```
85    #[inline]
86    pub const fn new() -> Self {
87        GapBuffer(RawGapBuffer::new())
88    }
89
90    /// Constructs a new, empty `GapBuffer<T>` with the specified capacity.
91    ///
92    /// # Examples
93    /// ```
94    /// use gap_buf::GapBuffer;
95    ///
96    /// let buf: GapBuffer<i32> = GapBuffer::with_capacity(5);
97    /// assert_eq!(buf.is_empty(), true);
98    /// assert_eq!(buf.len(), 0);
99    /// assert_eq!(buf.capacity(), 5);
100    /// ```
101    pub fn with_capacity(capacity: usize) -> Self {
102        let mut buf = GapBuffer::new();
103        buf.reserve_exact(capacity);
104        buf
105    }
106
107    /// Returns the number of elements the `GapBuffer<T>` can hold without reallocating.
108    ///
109    /// # Examples
110    /// ```
111    /// use gap_buf::GapBuffer;
112    ///
113    /// let buf: GapBuffer<i32> = GapBuffer::with_capacity(10);
114    /// assert_eq!(buf.capacity(), 10);
115    /// ```
116    #[inline]
117    pub const fn capacity(&self) -> usize {
118        self.0.0.cap
119    }
120
121    /// Reserves capacity for at least additional more elements to be inserted in the given `GapBuffer<T>`.
122    /// The collection may reserve more space to avoid frequent reallocations.
123    /// After calling reserve, capacity will be greater than or equal to `self.len() + additional`.
124    /// Does nothing if capacity is already sufficient.
125    ///
126    /// # Panics
127    /// Panics if the new capacity overflows usize.
128    ///
129    /// # Examples
130    /// ```
131    /// use gap_buf::GapBuffer;
132    ///
133    /// let mut buf = GapBuffer::new();
134    /// buf.push_back(1);
135    /// buf.reserve(10);
136    /// assert!(buf.capacity() >= 11);
137    /// ```
138    pub fn reserve(&mut self, additional: usize) {
139        self.reserve_as(additional, false);
140    }
141
142    /// Reserves the minimum capacity for exactly additional more elements to be inserted in the given `GapBuffer<T>`.
143    /// After calling reserve_exact, capacity will be greater than or equal to self.len() + additional.
144    /// Does nothing if the capacity is already sufficient.
145    ///
146    /// Note that the allocator may give the collection more space than it requests.
147    /// Therefore capacity can not be relied upon to be precisely minimal.
148    /// Prefer [`reserve`] if future insertions are expected.
149    ///
150    /// # Panics
151    /// Panics if the new capacity overflows usize.
152    ///
153    /// # Examples
154    /// ```
155    /// use gap_buf::GapBuffer;
156    ///
157    /// let mut buf = GapBuffer::new();
158    /// buf.push_back(1);
159    /// buf.reserve_exact(10);
160    /// assert!(buf.capacity() >= 11);
161    /// ```
162    ///
163    /// [`reserve`]: #method.reserve
164    pub fn reserve_exact(&mut self, additional: usize) {
165        self.reserve_as(additional, true);
166    }
167    fn reserve_as(&mut self, additional: usize, exact: bool) {
168        let len = self.len();
169        let old_cap = self.cap;
170        let new_cap = len.checked_add(additional).expect("capacity overflow");
171        if new_cap <= old_cap {
172            return;
173        }
174        let new_cap = if exact {
175            new_cap
176        } else {
177            max(old_cap.saturating_mul(2), new_cap)
178        };
179        self.0.realloc(new_cap);
180
181        unsafe {
182            let p = self.as_mut_ptr();
183            let count = len - self.gap();
184            copy(p.add(old_cap - count), p.add(new_cap - count), count);
185        }
186    }
187
188    /// Shrinks the capacity of the `GapBuffer<T>` as much as possible.
189    ///
190    /// # Examples
191    /// ```
192    /// use gap_buf::GapBuffer;
193    ///
194    /// let mut buf = GapBuffer::new();
195    /// buf.push_back(1);
196    ///
197    /// buf.reserve(10);
198    /// assert!(buf.capacity() >= 11);
199    ///
200    /// buf.shrink_to_fit();
201    /// assert_eq!(buf.capacity(), 1);
202    /// ```
203    pub fn shrink_to_fit(&mut self) {
204        let len = self.len();
205        self.set_gap(len);
206        self.0.realloc(len);
207    }
208
209    /// Set gap offset of the `GapBuffer<T>`.
210    ///
211    /// # Panics
212    /// Panics if `index > len`.
213    ///
214    /// # Computational amount
215    /// `O(n)` , `n = |self.gap() - gap|`
216    #[inline]
217    pub fn set_gap(&mut self, gap: usize) {
218        assert!(gap <= self.len());
219        if gap != self.gap() {
220            self.move_values(gap);
221            self.gap = gap;
222        }
223    }
224    fn move_values(&mut self, gap: usize) {
225        let gap_old = self.gap;
226        let gap_len = self.gap_len();
227        let (src, dest, count) = if gap < gap_old {
228            (gap, gap + gap_len, gap_old - gap)
229        } else {
230            (gap_old + gap_len, gap_old, gap - gap_old)
231        };
232        let p = self.as_mut_ptr();
233        unsafe {
234            copy(p.add(src), p.add(dest), count);
235        }
236    }
237
238    /// Return gap offset of the `GapBuffer<T>`.
239    #[inline]
240    pub const fn gap(&self) -> usize {
241        self.0.0.gap
242    }
243
244    #[inline]
245    fn set_gap_with_reserve(&mut self, gap: usize, additional: usize) {
246        self.reserve(additional);
247        self.set_gap(gap);
248    }
249
250    /// Inserts an element at position index within the `GapBuffer<T>`.
251    ///
252    /// # Panics
253    /// Panics if `index > len`.
254    ///
255    /// Panics if the number of elements in the gap buffer overflows a usize.
256    ///
257    /// # Computational amount
258    /// `O(n)` , `n = |index - self.gap()|`
259    #[inline]
260    pub fn insert(&mut self, index: usize, element: T) {
261        assert!(index <= self.len());
262        if self.gap() != index || self.len == self.capacity() {
263            self.set_gap_with_reserve(index, 1);
264        }
265        unsafe {
266            write(self.as_mut_ptr().add(index), element);
267        }
268        self.gap += 1;
269        self.len += 1;
270    }
271
272    #[deprecated(note = "insert_iter renamed to insert_many.")]
273    pub fn insert_iter(&mut self, index: usize, iter: impl IntoIterator<Item = T>) {
274        self.insert_many(index, iter);
275    }
276
277    /// Inserts multiple elements at position index within the `GapBuffer<T>`.
278    ///
279    /// # Panics
280    /// Panics if `index > len`.
281    ///
282    /// Panics if the number of elements in the gap buffer overflows a usize.
283    pub fn insert_many(&mut self, mut index: usize, iter: impl IntoIterator<Item = T>) {
284        assert!(index <= self.len());
285        let mut iter = iter.into_iter();
286        let min_len = iter.size_hint().0;
287        if let Some(value) = iter.next() {
288            self.set_gap_with_reserve(index, max(min_len, 1));
289            let p = self.as_mut_ptr();
290            unsafe {
291                write(p.add(index), value);
292                self.gap += 1;
293                self.len += 1;
294                index += 1;
295                for _ in 1..min_len {
296                    if let Some(value) = iter.next() {
297                        write(p.add(index), value);
298                        self.gap += 1;
299                        self.len += 1;
300                        index += 1;
301                    } else {
302                        return;
303                    }
304                }
305            }
306            for value in iter {
307                self.insert(index, value);
308                index += 1;
309            }
310        }
311    }
312
313    /// Appends an element to the back of a GapBuffer.
314    ///
315    /// # Panics
316    /// Panics if the number of elements in the gap buffer overflows a usize.
317    #[inline]
318    pub fn push_back(&mut self, value: T) {
319        let len = self.len;
320        self.insert(len, value);
321    }
322
323    /// Prepends an element to the GapBuffer.
324    ///
325    /// # Panics
326    /// Panics if the number of elements in the gap buffer overflows a usize.
327    #[inline]
328    pub fn push_front(&mut self, value: T) {
329        let len = self.len();
330        if self.gap() != 0 || len == self.capacity() {
331            self.set_gap_with_reserve(0, 1);
332        }
333        unsafe {
334            write(self.as_mut_ptr().add(self.cap - self.len - 1), value);
335        }
336        self.len += 1;
337    }
338
339    /// Removes an element from the GapBuffer and returns it.
340    ///
341    /// The removed element is replaced by the near the gap.
342    ///
343    /// # Panics
344    /// Panics if `index >= self.len()`.
345    ///
346    /// # Computational amount
347    /// `O(1)`
348    ///
349    /// # Examples
350    /// ```
351    /// use gap_buf::gap_buffer;
352    ///
353    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
354    /// buf.set_gap(5);
355    /// let value = buf.swap_remove(0);
356    /// assert_eq!(value, 1);
357    /// assert_eq!(buf, [5, 2, 3, 4]);
358    /// ```
359    pub fn swap_remove(&mut self, index: usize) -> T {
360        assert!(index < self.len());
361
362        unsafe {
363            let p = self.as_mut_ptr();
364            let value;
365            if index < self.gap() {
366                let pt = p.add(index);
367                value = pt.read();
368                self.gap -= 1;
369                copy(p.add(self.gap), pt, 1);
370            } else {
371                let gap_len = self.gap_len();
372                let pt = p.add(index + gap_len);
373                value = pt.read();
374                copy(p.add(self.gap + gap_len), pt, 1);
375            }
376            self.len -= 1;
377            value
378        }
379    }
380
381    /// Removes an element from the GapBuffer and returns it.
382    ///
383    /// # Panics
384    /// Panics if `index >= self.len()`.
385    ///
386    /// # Computational amount
387    /// `O(n)`, `n = |index - self.gap()|`
388    ///
389    /// # Examples
390    /// ```
391    /// use gap_buf::gap_buffer;
392    ///
393    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
394    /// let value = buf.remove(0);
395    /// assert_eq!(value, 1);
396    /// assert_eq!(buf, [2, 3, 4, 5]);
397    /// ```
398    pub fn remove(&mut self, index: usize) -> T {
399        assert!(index <= self.len());
400        let offset;
401        if self.gap() <= index {
402            self.set_gap(index);
403            offset = self.cap - self.len() + index;
404        } else {
405            self.set_gap(index + 1);
406            self.gap = index;
407            offset = index;
408        }
409        self.len -= 1;
410        if self.len == 0 {
411            self.gap = 0
412        }
413        unsafe { ptr::read(self.as_ptr().add(offset)) }
414    }
415
416    /// Clears the GapBuffer, removing all values.
417    ///
418    /// Note that this method has no effect on the allocated capacity of the GapBuffer.
419    pub fn clear(&mut self) {
420        self.truncate(0);
421    }
422
423    /// Shortens the GapBuffer, keeping the first len elements and dropping the rest.
424    ///
425    /// If len is greater than the GapBuffer's current length, this has no effect.
426    ///
427    /// Note that this method has no effect on the allocated capacity of the vector.
428    ///
429    /// # Examples
430    ///
431    /// ```
432    /// use gap_buf::gap_buffer;
433    ///
434    /// let mut buf = gap_buffer![1, 2, 3, 4];
435    /// buf.truncate(2);
436    /// assert_eq!(buf, [1, 2]);
437    /// ```
438    pub fn truncate(&mut self, len: usize) {
439        if needs_drop::<T>() {
440            while len < self.len {
441                let index = self.len - 1;
442                self.remove(index);
443            }
444        } else {
445            if self.gap < len {
446                self.set_gap(len);
447            } else {
448                self.gap = len;
449            }
450            self.len = len;
451        }
452    }
453
454    /// Retains only the elements specified by the predicate.
455    ///
456    /// # Examples
457    ///
458    /// ```
459    /// use gap_buf::gap_buffer;
460    ///
461    /// let mut buf = gap_buffer![1, 2, 3, 4];
462    /// buf.retain(|&x| x%2 == 0);
463    /// assert_eq!(buf, [2, 4]);
464    /// ```
465    pub fn retain(&mut self, mut f: impl FnMut(&T) -> bool) {
466        let mut n = 0;
467        while n < self.len {
468            if f(&self[n]) {
469                n += 1;
470            } else {
471                self.remove(n);
472            }
473        }
474    }
475
476    /// Removes the first element and returns it, or None if the GapBuffer is empty.
477    pub fn pop_front(&mut self) -> Option<T> {
478        let len = self.len;
479        match len {
480            0 => None,
481            _ => Some(self.remove(0)),
482        }
483    }
484
485    /// Removes the last element and returns it, or None if the GapBuffer is empty.
486    pub fn pop_back(&mut self) -> Option<T> {
487        let len = self.len;
488        match len {
489            0 => None,
490            _ => Some(self.remove(len - 1)),
491        }
492    }
493
494    /// Creates a draining iterator that removes the specified range in the GapBuffer and yields the removed items.
495    ///
496    /// - Note 1: The element range is removed even if the iterator is only partially consumed or not consumed at all.
497    /// - Note 2: It is unspecified how many elements are removed from the GapBuffer if the Drain value is leaked.
498    ///
499    /// # Panics
500    /// Panics if the `range` is out of bounds.
501    ///
502    /// # Examples
503    ///
504    /// ```
505    /// use gap_buf::gap_buffer;
506    ///
507    /// let mut buf = gap_buffer![1, 2, 3, 4];
508    ///
509    /// let d : Vec<_> = buf.drain(1..3).collect();
510    /// assert_eq!(buf, [1, 4]);
511    /// assert_eq!(d, [2, 3]);
512    ///
513    /// buf.drain(..);
514    /// assert_eq!(buf.is_empty(), true);
515    /// ```
516    pub fn drain(&mut self, range: impl RangeBounds<usize>) -> Drain<'_, T> {
517        let (idx, len) = self.to_idx_len(range);
518        Drain {
519            buf: self,
520            idx,
521            len,
522        }
523    }
524
525    /// Creates an extracting iterator that removes elements from the specified range in the GapBuffer based on a predicate
526    ///
527    /// Note that this iterator will only remove elements that are consumed. If dropped, it will retain the remaining elements.
528    ///
529    /// # Panics
530    ///
531    /// Panics if the `range` is out of bounds.
532    ///
533    /// # Examples
534    ///
535    /// ```
536    /// use gap_buf::gap_buffer;
537    ///
538    /// let mut buf = gap_buffer![1, 2, 3, 4];
539    ///
540    /// let d : Vec<_> = buf.extract_if(.., |num| *num % 2 == 1).collect();
541    /// assert_eq!(buf, [2, 4]);
542    /// assert_eq!(d, [1, 3]);
543    ///
544    /// buf.extract_if(.., |_| true);
545    /// assert_eq!(buf.is_empty(), false);
546    /// ```
547    pub fn extract_if<F>(&mut self, range: impl RangeBounds<usize>, filter: F) -> ExtractIf<'_, T, F>
548    where
549        F: FnMut(&mut T) -> bool
550    {
551        let (idx, end) = self.to_idx_len(range);
552        ExtractIf {
553            buf: self,
554            idx,
555            end,
556            pred: filter
557        }
558    }
559
560    /// Creates a splicing iterator
561    /// that replaces the specified range in the GapBuffer with the given replace_with iterator and
562    /// yields the removed items.
563    /// replace_with does not need to be the same length as range.
564    ///
565    /// The element range is removed even if the iterator is not consumed until the end.
566    ///
567    /// This is optimal if the length of `range` is equal to the length of `replace_with`.
568    /// Otherwise, call [`GapBuffer::set_gap`] internally.
569    ///
570    /// # Examples
571    ///
572    /// ```
573    /// use gap_buf::gap_buffer;
574    ///
575    /// let mut b = gap_buffer![1, 2, 3, 4];
576    /// let r : Vec<_> = b.splice(1..3, vec![7, 8, 9]).collect();
577    ///
578    /// assert_eq!(b, [1, 7, 8, 9, 4]);
579    /// assert_eq!(r, [2, 3]);
580    /// ```
581    pub fn splice<I: IntoIterator<Item = T>>(
582        &mut self,
583        range: impl RangeBounds<usize>,
584        replace_with: I,
585    ) -> Splice<'_, T, I::IntoIter> {
586        let (idx, len) = self.to_idx_len(range);
587        Splice {
588            buf: self,
589            idx,
590            end: idx + len,
591            iter: replace_with.into_iter().fuse(),
592        }
593    }
594}
595
596/// A splicing iterator for [`GapBuffer`].
597///
598/// This struct is created by [`GapBuffer::splice`].
599pub struct Splice<'gb, T: 'gb, I: Iterator<Item = T>> {
600    buf: &'gb mut GapBuffer<T>,
601    idx: usize,
602    end: usize,
603    iter: Fuse<I>,
604}
605impl<'gb, T: 'gb, I: Iterator<Item = T>> Iterator for Splice<'gb, T, I> {
606    type Item = T;
607
608    fn next(&mut self) -> Option<T> {
609        if self.idx < self.end {
610            if let Some(value) = self.iter.next() {
611                let value = mem::replace(&mut self.buf[self.idx], value);
612                self.idx += 1;
613                Some(value)
614            } else {
615                let value = self.buf.remove(self.idx);
616                self.end -= 1;
617                Some(value)
618            }
619        } else {
620            None
621        }
622    }
623    fn size_hint(&self) -> (usize, Option<usize>) {
624        let size = self.end - self.idx;
625        (size, Some(size))
626    }
627}
628impl<'gb, T: 'gb, I: Iterator<Item = T>> Drop for Splice<'gb, T, I> {
629    fn drop(&mut self) {
630        while self.next().is_some() {}
631        self.buf.insert_many(self.idx, &mut self.iter);
632    }
633}
634impl<'gb, T: 'gb, I: Iterator<Item = T>> ExactSizeIterator for Splice<'gb, T, I> {}
635impl<'gb, T: 'gb, I: Iterator<Item = T>> FusedIterator for Splice<'gb, T, I> {}
636impl<'gb, T: 'gb, I: DoubleEndedIterator<Item = T>> DoubleEndedIterator for Splice<'gb, T, I> {
637    fn next_back(&mut self) -> Option<T> {
638        if self.idx < self.end {
639            let i = self.end - 1;
640            let value = if let Some(value) = self.iter.next_back() {
641                mem::replace(&mut self.buf[i], value)
642            } else {
643                self.buf.remove(i)
644            };
645            self.end -= 1;
646            Some(value)
647        } else {
648            None
649        }
650    }
651}
652
653impl<T> GapBuffer<T>
654where
655    T: Clone,
656{
657    /// Resize the `GapBuffer<T>` in-place so that `len` is equal to `new_len`.
658    pub fn resize(&mut self, new_len: usize, value: T) {
659        let old_len = self.len();
660        if new_len < old_len {
661            self.truncate(new_len);
662        }
663        if new_len > old_len {
664            self.reserve(new_len - old_len);
665            while self.len < new_len {
666                self.push_back(value.clone());
667            }
668        }
669    }
670}
671
672impl<T> Drop for GapBuffer<T> {
673    fn drop(&mut self) {
674        unsafe {
675            let (s0, s1) = self.as_mut_slices();
676            try_finally!(drop_in_place(s0), drop_in_place(s1));
677        }
678    }
679}
680
681impl<T> Deref for GapBuffer<T> {
682    type Target = Slice<T>;
683
684    #[inline]
685    fn deref(&self) -> &Self::Target {
686        &(self.0).0
687    }
688}
689impl<T> DerefMut for GapBuffer<T> {
690    #[inline]
691    fn deref_mut(&mut self) -> &mut Self::Target {
692        &mut (self.0).0
693    }
694}
695
696impl<T> FromIterator<T> for GapBuffer<T> {
697    fn from_iter<S: IntoIterator<Item = T>>(s: S) -> GapBuffer<T> {
698        let mut buf = GapBuffer::new();
699        buf.extend(s);
700        buf
701    }
702}
703
704impl<T: Clone> Clone for GapBuffer<T> {
705    fn clone(&self) -> Self {
706        self.iter().cloned().collect()
707    }
708}
709impl<T> Extend<T> for GapBuffer<T> {
710    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
711        let len = self.len;
712        self.insert_many(len, iter);
713    }
714}
715impl<'gb, T: 'gb + Copy> Extend<&'gb T> for GapBuffer<T> {
716    fn extend<I: IntoIterator<Item = &'gb T>>(&mut self, iter: I) {
717        self.extend(iter.into_iter().cloned());
718    }
719}
720
721#[derive(Hash)]
722struct RawGapBuffer<T>(Slice<T>);
723
724impl<T> RawGapBuffer<T> {
725    const fn new() -> Self {
726        RawGapBuffer(Slice::empty())
727    }
728
729    fn realloc(&mut self, new_cap: usize) {
730        let old_cap = self.0.cap;
731        if old_cap == new_cap {
732            return;
733        }
734        if size_of::<T>() != 0 {
735            unsafe {
736                let old_layout = Self::get_layout(old_cap);
737                let new_layout = Self::get_layout(new_cap);
738                let p = self.0.ptr.as_ptr() as *mut u8;
739                self.0.ptr = if new_cap == 0 {
740                    dealloc(p, old_layout);
741                    NonNull::dangling()
742                } else {
743                    NonNull::new(if old_cap == 0 {
744                        alloc(new_layout)
745                    } else {
746                        realloc(p, old_layout, new_layout.size())
747                    } as *mut T)
748                    .unwrap_or_else(|| handle_alloc_error(new_layout))
749                };
750            }
751        }
752        self.0.cap = new_cap;
753    }
754    
755    fn get_layout(cap: usize) -> Layout {
756        let new_size = size_of::<T>()
757            .checked_mul(cap)
758            .expect("memory size overflow");
759        Layout::from_size_align(new_size, align_of::<T>()).unwrap()
760    }
761}
762impl<T> Drop for RawGapBuffer<T> {
763    fn drop(&mut self) {
764        self.realloc(0)
765    }
766}
767
768////////////////////////////////////////////////////////////////////////////////
769// Range, RangeMut
770////////////////////////////////////////////////////////////////////////////////
771
772/// Immutable sub-range of [`GapBuffer`]
773///
774/// This struct is created by [`Slice::range`].
775#[derive(Hash)]
776pub struct Range<'gb, T: 'gb> {
777    s: Slice<T>,
778    _phantom: PhantomData<&'gb [T]>,
779}
780
781/// Mutable sub-range of [`GapBuffer`].
782///
783/// This struct is created by [`Slice::range_mut`].
784#[derive(Hash)]
785pub struct RangeMut<'gb, T: 'gb> {
786    s: Slice<T>,
787    _phantom: PhantomData<&'gb mut [T]>,
788}
789impl<'gb, T: 'gb> Range<'gb, T> {
790    #[inline]
791    const unsafe fn new(s: Slice<T>) -> Self {
792        Range {
793            s,
794            _phantom: PhantomData,
795        }
796    }
797
798    /// Construct a new, empty `Range`.
799    #[inline]
800    pub const fn empty() -> Self {
801        unsafe { Range::new(Slice::empty()) }
802    }
803
804    /// Returns a reference to an element at index or None if out of bounds.
805    ///
806    /// Unlike [`Slice::get`], return value not borrow `self`.
807    #[inline]
808    pub fn get(&self, index: usize) -> Option<&'gb T> {
809        unsafe { self.s.get_with_lifetime(index) }
810    }
811
812    /// Return a immutable sub-range of this Slice.
813    ///
814    /// Unlike [`Slice::range`], return value not borrow `self`.
815    pub fn range(&self, range: impl RangeBounds<usize>) -> Range<'gb, T> {
816        unsafe { self.range_with_lifetime(range) }
817    }
818
819    /// Returns a pair of slices.
820    /// First slice is before gap. Second slice is after gap.
821    ///
822    /// Unlike [`Slice::as_slices`], return value not borrow `self`.
823    pub fn as_slices(&self) -> (&'gb [T], &'gb [T]) {
824        unsafe { self.as_slices_with_lifetime() }
825    }
826}
827impl<'gb, T: 'gb> RangeMut<'gb, T> {
828    #[inline]
829    const unsafe fn new(s: Slice<T>) -> Self {
830        RangeMut {
831            s,
832            _phantom: PhantomData,
833        }
834    }
835
836    /// Construct a new, empty `RangeMut`.
837    #[inline]
838    pub const fn empty() -> Self {
839        unsafe { RangeMut::new(Slice::empty()) }
840    }
841}
842
843impl<T> Deref for Range<'_, T> {
844    type Target = Slice<T>;
845
846    #[inline]
847    fn deref(&self) -> &Self::Target {
848        &self.s
849    }
850}
851impl<T> Deref for RangeMut<'_, T> {
852    type Target = Slice<T>;
853
854    #[inline]
855    fn deref(&self) -> &Self::Target {
856        &self.s
857    }
858}
859
860impl<T> DerefMut for RangeMut<'_, T> {
861    #[inline]
862    fn deref_mut(&mut self) -> &mut Self::Target {
863        &mut self.s
864    }
865}
866impl<T> Clone for Range<'_, T> {
867    fn clone(&self) -> Self {
868        unsafe {
869            Range::new(Slice {
870                ptr: self.ptr,
871                cap: self.cap,
872                gap: self.gap,
873                len: self.len,
874            })
875        }
876    }
877}
878
879////////////////////////////////////////////////////////////////////////////////
880// Slice
881////////////////////////////////////////////////////////////////////////////////
882
883/// Sub-range of [`GapBuffer`].
884/// `Slice` define common method for [`GapBuffer`], [`Range`], [`RangeMut`].
885pub struct Slice<T> {
886    ptr: NonNull<T>,
887    cap: usize,
888    gap: usize,
889    len: usize,
890}
891impl<T> Slice<T> {
892    /// Construct a new, empty `Slice`.
893    pub const fn empty() -> Self {
894        Slice {
895            ptr: NonNull::dangling(),
896            cap: 0,
897            gap: 0,
898            len: 0,
899        }
900    }
901
902    /// Returns the number of elements in the GapBuffer.
903    #[inline]
904    pub const fn len(&self) -> usize {
905        self.len
906    }
907
908    /// Returns true if the GapBuffer contains no elements.
909    #[inline]
910    pub const fn is_empty(&self) -> bool {
911        self.len() == 0
912    }
913
914    /// Returns a reference to an element at index or None if out of bounds.
915    #[inline]
916    pub fn get(&self, index: usize) -> Option<&T> {
917        unsafe { self.get_with_lifetime(index) }
918    }
919    #[inline]
920    unsafe fn get_with_lifetime<'gb>(&self, index: usize) -> Option<&'gb T> {
921        self.get_offset(index).map(|o| &*self.as_ptr().add(o))
922    }
923
924    /// Returns a mutable reference to an element at index or None if out of bounds.
925    #[inline]
926    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
927        self.get_offset(index)
928            .map(|o| unsafe { &mut *self.as_mut_ptr().add(o) })
929    }
930
931    /// Swaps two elements in the GapBuffer.
932    ///
933    /// # Arguments
934    ///
935    /// * a - The index of the first element
936    /// * b - The index of the second element
937    ///
938    /// # Panics
939    /// Panics if `a >= self.len()` or `b >= self.len()`.
940    #[inline]
941    pub const fn swap(&mut self, a: usize, b: usize) {
942        let oa = self.get_offset(a).expect("a is out of bounds.");
943        let ob = self.get_offset(b).expect("b is out of bounds.");
944        let p = self.as_mut_ptr();
945        unsafe { ptr::swap(p.add(oa), p.add(ob)) }
946    }
947
948    /// Return a immutable sub-range of this Slice.
949    ///
950    /// # Panics
951    /// Panics if `range` is out of bounds.
952    ///
953    /// # Examples
954    /// ```
955    /// use gap_buf::gap_buffer;
956    ///
957    /// let buf = gap_buffer![1, 2, 3, 4, 5];
958    ///
959    /// let r1 = buf.range(1..);
960    /// assert_eq!(r1, [2, 3, 4, 5]);
961    ///
962    /// let r2 = r1.range(1..3);
963    /// assert_eq!(r2, [3, 4]);
964    /// ```
965    pub fn range(&self, range: impl RangeBounds<usize>) -> Range<'_, T> {
966        unsafe { self.range_with_lifetime(range) }
967    }
968    unsafe fn range_with_lifetime<'gb>(&self, range: impl RangeBounds<usize>) -> Range<'gb, T> {
969        Range::new(self.range_slice(range))
970    }
971
972    /// Return a mutable sub-range of this Slice.
973    ///
974    /// # Panics
975    /// Panics if `range` is out of bounds.
976    ///
977    /// # Examples
978    /// ```
979    /// use gap_buf::gap_buffer;
980    ///
981    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
982    /// {
983    ///     let mut r = buf.range_mut(1..);
984    ///     assert_eq!(r, [2, 3, 4, 5]);
985    ///     r[0] = 0;
986    /// }
987    /// assert_eq!(buf, [1, 0, 3, 4, 5]);
988    /// ```
989    pub fn range_mut(&mut self, range: impl RangeBounds<usize>) -> RangeMut<'_, T> {
990        unsafe { RangeMut::new(self.range_slice(range)) }
991    }
992    unsafe fn range_slice(&self, range: impl RangeBounds<usize>) -> Slice<T> {
993        let (idx, len) = self.to_idx_len(range);
994        if len == 0 {
995            return Slice::empty();
996        }
997
998        let gap_is_before = self.gap <= idx;
999        let gap_is_after = idx + len <= self.gap;
1000
1001        let gap = if gap_is_before {
1002            0
1003        } else if !gap_is_after {
1004            self.gap - idx
1005        } else {
1006            len
1007        };
1008        let begin = if gap_is_before { self.gap_len() } else { 0 } + idx;
1009        let end = if !gap_is_after { self.gap_len() } else { 0 } + idx + len;
1010
1011        Slice {
1012            ptr: NonNull::new(self.ptr.as_ptr().add(begin)).unwrap(),
1013            cap: end - begin,
1014            gap,
1015            len,
1016        }
1017    }
1018    fn to_idx_len(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
1019        use std::ops::Bound::*;
1020        const MAX: usize = usize::MAX;
1021        let len = self.len;
1022        let idx = match range.start_bound() {
1023            Included(&idx) => idx,
1024            Excluded(&MAX) => panic!("attempted to index slice up to maximum usize"),
1025            Excluded(&idx) => idx + 1,
1026            Unbounded => 0,
1027        };
1028        if idx > len {
1029            panic!("index {idx} out of range for slice of length {len}");
1030        }
1031
1032        let end = match range.end_bound() {
1033            Included(&MAX) => panic!("attempted to index slice up to maximum usize"),
1034            Included(&idx) => idx + 1,
1035            Excluded(&idx) => idx,
1036            Unbounded => len,
1037        };
1038        if end > len {
1039            panic!("index {end} out of range for slice of length {len}");
1040        }
1041
1042        if end < idx {
1043            panic!("slice index starts at {idx} but ends at {len}");
1044        }
1045        (idx, end - idx)
1046    }
1047
1048    /// Returns a pair of slices.
1049    /// First slice is before gap. Second slice is after gap.
1050    ///
1051    /// # Examples
1052    /// ```
1053    /// use gap_buf::gap_buffer;
1054    ///
1055    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
1056    /// buf.set_gap(2);
1057    /// let (s1, s2) = buf.as_slices();
1058    /// assert_eq!(s1, [1, 2]);
1059    /// assert_eq!(s2, [3, 4, 5]);
1060    /// ```
1061    pub fn as_slices(&self) -> (&[T], &[T]) {
1062        unsafe { self.as_slices_with_lifetime() }
1063    }
1064    const unsafe fn as_slices_with_lifetime<'gb>(&self) -> (&'gb [T], &'gb [T]) {
1065        let p0 = self.as_ptr();
1066        let c1 = self.len - self.gap;
1067        let p1 = p0.add(self.cap - c1);
1068        (
1069            slice::from_raw_parts(p0, self.gap),
1070            slice::from_raw_parts(p1, c1),
1071        )
1072    }
1073
1074    /// Returns a pair of slices.
1075    /// First slice is before gap. Second slice is after gap.
1076    ///
1077    /// # Examples
1078    /// ```
1079    /// use gap_buf::gap_buffer;
1080    ///
1081    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
1082    /// buf.set_gap(2);
1083    /// {
1084    ///     let (mut s1, mut s2) = buf.as_mut_slices();
1085    ///     s1[0] = 10;
1086    ///     s2[0] = 11;
1087    /// }
1088    /// assert_eq!(buf, [10, 2, 11, 4, 5]);
1089    /// ```
1090    pub const fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
1091        unsafe {
1092            let p0 = self.as_mut_ptr();
1093            let c1 = self.len - self.gap;
1094            let p1 = p0.add(self.cap - c1);
1095            (
1096                slice::from_raw_parts_mut(p0, self.gap),
1097                slice::from_raw_parts_mut(p1, c1),
1098            )
1099        }
1100    }
1101
1102    /// Returns an iterator over the Slice.
1103    pub fn iter(&self) -> Iter<'_, T> {
1104        let (s0, s1) = self.as_slices();
1105        s0.iter().chain(s1.iter())
1106    }
1107
1108    /// Returns an iterator that allows modifying each value.
1109    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
1110        let (s0, s1) = self.as_mut_slices();
1111        s0.iter_mut().chain(s1.iter_mut())
1112    }
1113
1114    #[inline]
1115    const fn get_offset(&self, index: usize) -> Option<usize> {
1116        if index < self.gap {
1117            Some(index)
1118        } else if index < self.len {
1119            Some(index + self.gap_len())
1120        } else {
1121            None
1122        }
1123    }
1124
1125    #[inline]
1126    const fn gap_len(&self) -> usize {
1127        self.cap - self.len
1128    }
1129
1130    #[inline]
1131    const fn as_ptr(&self) -> *const T {
1132        self.ptr.as_ptr()
1133    }
1134
1135    #[inline]
1136    const fn as_mut_ptr(&mut self) -> *mut T {
1137        self.ptr.as_ptr()
1138    }
1139}
1140unsafe impl<T: Sync> Sync for Slice<T> {}
1141unsafe impl<T: Send> Send for Slice<T> {}
1142
1143////////////////////////////////////////////////////////////////////////////////
1144// Default
1145////////////////////////////////////////////////////////////////////////////////
1146
1147impl<T> Default for GapBuffer<T> {
1148    #[inline]
1149    fn default() -> Self {
1150        Self::new()
1151    }
1152}
1153impl<T> Default for Range<'_, T> {
1154    #[inline]
1155    fn default() -> Self {
1156        Self::empty()
1157    }
1158}
1159impl<T> Default for RangeMut<'_, T> {
1160    #[inline]
1161    fn default() -> Self {
1162        Self::empty()
1163    }
1164}
1165
1166////////////////////////////////////////////////////////////////////////////////
1167// Index, IndexMut
1168////////////////////////////////////////////////////////////////////////////////
1169
1170impl<T> Index<usize> for GapBuffer<T> {
1171    type Output = T;
1172
1173    #[inline]
1174    fn index(&self, index: usize) -> &T {
1175        self.deref().index(index)
1176    }
1177}
1178impl<T> IndexMut<usize> for GapBuffer<T> {
1179    #[inline]
1180    fn index_mut(&mut self, index: usize) -> &mut T {
1181        self.deref_mut().index_mut(index)
1182    }
1183}
1184
1185impl<T> Index<usize> for Range<'_, T> {
1186    type Output = T;
1187
1188    #[inline]
1189    fn index(&self, index: usize) -> &T {
1190        self.deref().index(index)
1191    }
1192}
1193impl<T> Index<usize> for RangeMut<'_, T> {
1194    type Output = T;
1195
1196    #[inline]
1197    fn index(&self, index: usize) -> &T {
1198        self.deref().index(index)
1199    }
1200}
1201impl<T> IndexMut<usize> for RangeMut<'_, T> {
1202    #[inline]
1203    fn index_mut(&mut self, index: usize) -> &mut T {
1204        self.deref_mut().index_mut(index)
1205    }
1206}
1207
1208impl<T> Index<usize> for Slice<T> {
1209    type Output = T;
1210
1211    #[inline]
1212    fn index(&self, index: usize) -> &T {
1213        self.get(index).expect("index out of bounds")
1214    }
1215}
1216impl<T> IndexMut<usize> for Slice<T> {
1217    #[inline]
1218    fn index_mut(&mut self, index: usize) -> &mut T {
1219        self.get_mut(index).expect("index out of bounds")
1220    }
1221}
1222
1223////////////////////////////////////////////////////////////////////////////////
1224// Debug
1225////////////////////////////////////////////////////////////////////////////////
1226
1227impl<T> Debug for GapBuffer<T>
1228where
1229    T: Debug,
1230{
1231    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1232        self.deref().fmt(f)
1233    }
1234}
1235impl<T> Debug for Range<'_, T>
1236where
1237    T: Debug,
1238{
1239    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1240        self.deref().fmt(f)
1241    }
1242}
1243impl<T> Debug for RangeMut<'_, T>
1244where
1245    T: Debug,
1246{
1247    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1248        self.deref().fmt(f)
1249    }
1250}
1251
1252impl<T> Debug for Slice<T>
1253where
1254    T: Debug,
1255{
1256    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1257        f.debug_list().entries(self).finish()
1258    }
1259}
1260
1261impl<T: Hash> Hash for Slice<T> {
1262    fn hash<H: Hasher>(&self, state: &mut H) {
1263        for value in self {
1264            value.hash(state);
1265        }
1266    }
1267}
1268
1269////////////////////////////////////////////////////////////////////////////////
1270// Eq, PartialEq
1271////////////////////////////////////////////////////////////////////////////////
1272
1273impl<T, S> PartialEq<S> for GapBuffer<T>
1274where
1275    T: PartialEq,
1276    S: ?Sized,
1277    for<'b> &'b S: IntoIterator<Item = &'b T>,
1278{
1279    fn eq(&self, other: &S) -> bool {
1280        self.deref().eq(other)
1281    }
1282}
1283impl<T: Eq> Eq for GapBuffer<T> {}
1284
1285impl<T, S> PartialEq<S> for Range<'_, T>
1286where
1287    T: PartialEq,
1288    S: ?Sized,
1289    for<'b> &'b S: IntoIterator<Item = &'b T>,
1290{
1291    fn eq(&self, other: &S) -> bool {
1292        self.deref().eq(other)
1293    }
1294}
1295impl<T: Eq> Eq for Range<'_, T> {}
1296
1297impl<T, S> PartialEq<S> for RangeMut<'_, T>
1298where
1299    T: PartialEq,
1300    S: ?Sized,
1301    for<'b> &'b S: IntoIterator<Item = &'b T>,
1302{
1303    fn eq(&self, other: &S) -> bool {
1304        self.deref().eq(other)
1305    }
1306}
1307impl<T: Eq> Eq for RangeMut<'_, T> {}
1308
1309impl<T, S> PartialEq<S> for Slice<T>
1310where
1311    T: PartialEq,
1312    S: ?Sized,
1313    for<'b> &'b S: IntoIterator<Item = &'b T>,
1314{
1315    fn eq(&self, other: &S) -> bool {
1316        self.iter().eq(other)
1317    }
1318}
1319impl<T: Eq> Eq for Slice<T> {}
1320
1321////////////////////////////////////////////////////////////////////////////////
1322// Ord, PartialOrd
1323////////////////////////////////////////////////////////////////////////////////
1324
1325impl<T, S> PartialOrd<S> for GapBuffer<T>
1326where
1327    T: PartialOrd,
1328    S: ?Sized,
1329    for<'b> &'b S: IntoIterator<Item = &'b T>,
1330{
1331    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1332        self.deref().partial_cmp(other)
1333    }
1334}
1335
1336impl<T: Ord> Ord for GapBuffer<T> {
1337    fn cmp(&self, other: &Self) -> Ordering {
1338        self.deref().cmp(other)
1339    }
1340}
1341
1342impl<T, S> PartialOrd<S> for Range<'_, T>
1343where
1344    T: PartialOrd,
1345    S: ?Sized,
1346    for<'b> &'b S: IntoIterator<Item = &'b T>,
1347{
1348    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1349        self.deref().partial_cmp(other)
1350    }
1351}
1352
1353impl<T: Ord> Ord for Range<'_, T> {
1354    fn cmp(&self, other: &Self) -> Ordering {
1355        self.deref().cmp(other)
1356    }
1357}
1358
1359impl<T, S> PartialOrd<S> for RangeMut<'_, T>
1360where
1361    T: PartialOrd,
1362    S: ?Sized,
1363    for<'b> &'b S: IntoIterator<Item = &'b T>,
1364{
1365    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1366        self.deref().partial_cmp(other)
1367    }
1368}
1369
1370impl<T: Ord> Ord for RangeMut<'_, T> {
1371    fn cmp(&self, other: &Self) -> Ordering {
1372        self.deref().cmp(other)
1373    }
1374}
1375
1376impl<T, S> PartialOrd<S> for Slice<T>
1377where
1378    T: PartialOrd,
1379    S: ?Sized,
1380    for<'b> &'b S: IntoIterator<Item = &'b T>,
1381{
1382    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1383        self.iter().partial_cmp(other)
1384    }
1385}
1386
1387impl<T: Ord> Ord for Slice<T> {
1388    fn cmp(&self, other: &Self) -> Ordering {
1389        self.iter().cmp(other)
1390    }
1391}
1392
1393////////////////////////////////////////////////////////////////////////////////
1394// iterator
1395////////////////////////////////////////////////////////////////////////////////
1396
1397/// Immutable GapBuffer iterator.
1398pub type Iter<'gb, T> = Chain<slice::Iter<'gb, T>, slice::Iter<'gb, T>>;
1399
1400/// Mutable GapBuffer iterator.
1401pub type IterMut<'gb, T> = Chain<slice::IterMut<'gb, T>, slice::IterMut<'gb, T>>;
1402
1403/// An iterator that moves out of a [`GapBuffer`].
1404pub struct IntoIter<T> {
1405    buf: GapBuffer<T>,
1406}
1407impl<T> Iterator for IntoIter<T> {
1408    type Item = T;
1409
1410    fn next(&mut self) -> Option<T> {
1411        self.buf.pop_front()
1412    }
1413    fn size_hint(&self) -> (usize, Option<usize>) {
1414        let len = self.buf.len();
1415        (len, Some(len))
1416    }
1417}
1418impl<T> ExactSizeIterator for IntoIter<T> {}
1419impl<T> FusedIterator for IntoIter<T> {}
1420impl<T> DoubleEndedIterator for IntoIter<T> {
1421    fn next_back(&mut self) -> Option<T> {
1422        self.buf.pop_back()
1423    }
1424}
1425
1426impl<T> IntoIterator for GapBuffer<T> {
1427    type Item = T;
1428    type IntoIter = IntoIter<T>;
1429    fn into_iter(self) -> IntoIter<T> {
1430        IntoIter { buf: self }
1431    }
1432}
1433
1434impl<'gb, T> IntoIterator for &'gb GapBuffer<T> {
1435    type Item = &'gb T;
1436    type IntoIter = Iter<'gb, T>;
1437    fn into_iter(self) -> Iter<'gb, T> {
1438        self.iter()
1439    }
1440}
1441impl<'gb, T> IntoIterator for &'gb Range<'_, T> {
1442    type Item = &'gb T;
1443    type IntoIter = Iter<'gb, T>;
1444    fn into_iter(self) -> Iter<'gb, T> {
1445        self.iter()
1446    }
1447}
1448impl<'gb, T> IntoIterator for &'gb RangeMut<'_, T> {
1449    type Item = &'gb T;
1450    type IntoIter = Iter<'gb, T>;
1451    fn into_iter(self) -> Iter<'gb, T> {
1452        self.iter()
1453    }
1454}
1455
1456impl<'gb, T> IntoIterator for &'gb Slice<T> {
1457    type Item = &'gb T;
1458    type IntoIter = Iter<'gb, T>;
1459    fn into_iter(self) -> Iter<'gb, T> {
1460        self.iter()
1461    }
1462}
1463
1464impl<'gb, T> IntoIterator for &'gb mut GapBuffer<T> {
1465    type Item = &'gb mut T;
1466    type IntoIter = IterMut<'gb, T>;
1467    fn into_iter(self) -> IterMut<'gb, T> {
1468        self.iter_mut()
1469    }
1470}
1471
1472impl<'gb, T> IntoIterator for &'gb mut RangeMut<'gb, T> {
1473    type Item = &'gb mut T;
1474    type IntoIter = IterMut<'gb, T>;
1475    fn into_iter(self) -> IterMut<'gb, T> {
1476        self.iter_mut()
1477    }
1478}
1479
1480impl<'gb, T> IntoIterator for &'gb mut Slice<T> {
1481    type Item = &'gb mut T;
1482    type IntoIter = IterMut<'gb, T>;
1483    fn into_iter(self) -> IterMut<'gb, T> {
1484        self.iter_mut()
1485    }
1486}
1487
1488/// A draining iterator for [`GapBuffer`].
1489///
1490/// This struct is created by [`GapBuffer::drain`].
1491pub struct Drain<'gb, T: 'gb> {
1492    buf: &'gb mut GapBuffer<T>,
1493    idx: usize,
1494    len: usize,
1495}
1496
1497impl<T> Iterator for Drain<'_, T> {
1498    type Item = T;
1499    fn next(&mut self) -> Option<T> {
1500        if self.len == 0 {
1501            None
1502        } else {
1503            self.len -= 1;
1504            Some(self.buf.remove(self.idx))
1505        }
1506    }
1507    fn size_hint(&self) -> (usize, Option<usize>) {
1508        (self.len, Some(self.len))
1509    }
1510}
1511
1512impl<T> Drop for Drain<'_, T> {
1513    fn drop(&mut self) {
1514        let len = self.len;
1515        self.nth(len);
1516    }
1517}
1518
1519impl<T> ExactSizeIterator for Drain<'_, T> {}
1520impl<T> FusedIterator for Drain<'_, T> {}
1521
1522/// An iterator that conditionally extracts from a [`GapBuffer`].
1523///
1524/// this struct is created by [`GapBuffer::extract_if`].
1525#[must_use]
1526pub struct ExtractIf<'gb, T: 'gb, F> {
1527    buf: &'gb mut GapBuffer<T>,
1528    idx: usize,
1529    end: usize,
1530    pred: F,
1531}
1532
1533impl<T, F> Iterator for ExtractIf<'_, T, F>
1534where
1535    F: FnMut(&mut T) -> bool
1536{
1537    type Item = T;
1538
1539    fn next(&mut self) -> Option<T> {
1540        while self.idx < self.end {
1541            if (self.pred)(self.buf.get_mut(self.idx).unwrap()) {
1542                self.end -= 1;
1543                return Some(self.buf.remove(self.idx));
1544            } else {
1545                self.idx += 1;
1546            }
1547        }
1548
1549        None
1550    }
1551}
1552
1553impl<T, F> FusedIterator for ExtractIf<'_, T, F>
1554where
1555    F: FnMut(&mut T) -> bool
1556{
1557}
gap_buf/gap_buffer.rs

gap_buf/
gap_buffer.rs
