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

gap_buf/
gap_buffer.rs
