gap_buf/
gap_buffer.rs

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

gap_buf/
gap_buffer.rs
