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    pub fn drain(&mut self, range: impl RangeBounds<usize>) -> Drain<'_, T> {
510        let (idx, len) = self.to_idx_len(range);
511        Drain {
512            buf: self,
513            idx,
514            len,
515        }
516    }
517
518    /// Creates an extracting iterator that removes elements from the specified range in the GapBuffer based on a predicate
519    ///
520    /// Note that this iterator will only remove elements that are consumed. If dropped, it will retain the remaining elements.
521    ///
522    /// # Panics
523    ///
524    /// Panics if the `range` is out of bounds.
525    ///
526    /// # Examples
527    ///
528    /// ```
529    /// use gap_buf::gap_buffer;
530    ///
531    /// let mut buf = gap_buffer![1, 2, 3, 4];
532    ///
533    /// let d : Vec<_> = buf.extract_if(.., |num| *num % 2 == 1).collect();
534    /// assert_eq!(buf, [2, 4]);
535    /// assert_eq!(d, [1, 3]);
536    ///
537    /// buf.extract_if(.., |_| true);
538    /// assert_eq!(buf.is_empty(), false);
539    /// ```
540    pub fn extract_if<F>(
541        &mut self,
542        range: impl RangeBounds<usize>,
543        filter: F,
544    ) -> ExtractIf<'_, T, F>
545    where
546        F: FnMut(&mut T) -> bool,
547    {
548        let (idx, end) = self.to_idx_len(range);
549        ExtractIf {
550            buf: self,
551            idx,
552            end,
553            pred: filter,
554        }
555    }
556
557    /// Creates a splicing iterator
558    /// that replaces the specified range in the GapBuffer with the given replace_with iterator and
559    /// yields the removed items.
560    /// replace_with does not need to be the same length as range.
561    ///
562    /// The element range is removed even if the iterator is not consumed until the end.
563    ///
564    /// This is optimal if the length of `range` is equal to the length of `replace_with`.
565    /// Otherwise, call [`GapBuffer::set_gap`] internally.
566    ///
567    /// # Examples
568    ///
569    /// ```
570    /// use gap_buf::gap_buffer;
571    ///
572    /// let mut b = gap_buffer![1, 2, 3, 4];
573    /// let r : Vec<_> = b.splice(1..3, vec![7, 8, 9]).collect();
574    ///
575    /// assert_eq!(b, [1, 7, 8, 9, 4]);
576    /// assert_eq!(r, [2, 3]);
577    /// ```
578    pub fn splice<I: IntoIterator<Item = T>>(
579        &mut self,
580        range: impl RangeBounds<usize>,
581        replace_with: I,
582    ) -> Splice<'_, T, I::IntoIter> {
583        let (idx, len) = self.to_idx_len(range);
584        Splice {
585            buf: self,
586            idx,
587            end: idx + len,
588            iter: replace_with.into_iter().fuse(),
589        }
590    }
591}
592
593/// A splicing iterator for [`GapBuffer`].
594///
595/// This struct is created by [`GapBuffer::splice`].
596pub struct Splice<'gb, T: 'gb, I: Iterator<Item = T>> {
597    buf: &'gb mut GapBuffer<T>,
598    idx: usize,
599    end: usize,
600    iter: Fuse<I>,
601}
602impl<'gb, T: 'gb, I: Iterator<Item = T>> Iterator for Splice<'gb, T, I> {
603    type Item = T;
604
605    fn next(&mut self) -> Option<T> {
606        if self.idx < self.end {
607            if let Some(value) = self.iter.next() {
608                let value = mem::replace(&mut self.buf[self.idx], value);
609                self.idx += 1;
610                Some(value)
611            } else {
612                let value = self.buf.remove(self.idx);
613                self.end -= 1;
614                Some(value)
615            }
616        } else {
617            None
618        }
619    }
620    fn size_hint(&self) -> (usize, Option<usize>) {
621        let size = self.end - self.idx;
622        (size, Some(size))
623    }
624}
625impl<'gb, T: 'gb, I: Iterator<Item = T>> Drop for Splice<'gb, T, I> {
626    fn drop(&mut self) {
627        while self.next().is_some() {}
628        self.buf.insert_many(self.idx, &mut self.iter);
629    }
630}
631impl<'gb, T: 'gb, I: Iterator<Item = T>> ExactSizeIterator for Splice<'gb, T, I> {}
632impl<'gb, T: 'gb, I: Iterator<Item = T>> FusedIterator for Splice<'gb, T, I> {}
633impl<'gb, T: 'gb, I: DoubleEndedIterator<Item = T>> DoubleEndedIterator for Splice<'gb, T, I> {
634    fn next_back(&mut self) -> Option<T> {
635        if self.idx < self.end {
636            let i = self.end - 1;
637            let value = if let Some(value) = self.iter.next_back() {
638                mem::replace(&mut self.buf[i], value)
639            } else {
640                self.buf.remove(i)
641            };
642            self.end -= 1;
643            Some(value)
644        } else {
645            None
646        }
647    }
648}
649
650impl<T> GapBuffer<T>
651where
652    T: Clone,
653{
654    /// Resize the `GapBuffer<T>` in-place so that `len` is equal to `new_len`.
655    pub fn resize(&mut self, new_len: usize, value: T) {
656        let old_len = self.len();
657        if new_len < old_len {
658            self.truncate(new_len);
659        }
660        if new_len > old_len {
661            self.reserve(new_len - old_len);
662            while self.len < new_len {
663                self.push_back(value.clone());
664            }
665        }
666    }
667}
668
669impl<T> Drop for GapBuffer<T> {
670    fn drop(&mut self) {
671        unsafe {
672            let (s0, s1) = self.as_mut_slices();
673            try_finally!(drop_in_place(s0), drop_in_place(s1));
674        }
675    }
676}
677
678impl<T> Deref for GapBuffer<T> {
679    type Target = Slice<T>;
680
681    #[inline]
682    fn deref(&self) -> &Self::Target {
683        &(self.0).0
684    }
685}
686impl<T> DerefMut for GapBuffer<T> {
687    #[inline]
688    fn deref_mut(&mut self) -> &mut Self::Target {
689        &mut (self.0).0
690    }
691}
692
693impl<T> From<Vec<T>> for GapBuffer<T> {
694    /// An `O(1)` conversion from a [`Vec<T>`].
695    fn from(value: Vec<T>) -> Self {
696        Self(RawGapBuffer::from_vec(value))
697    }
698}
699
700impl<T> FromIterator<T> for GapBuffer<T> {
701    fn from_iter<S: IntoIterator<Item = T>>(s: S) -> GapBuffer<T> {
702        let mut buf = GapBuffer::new();
703        buf.extend(s);
704        buf
705    }
706}
707
708impl<T: Clone> Clone for GapBuffer<T> {
709    fn clone(&self) -> Self {
710        self.iter().cloned().collect()
711    }
712}
713
714impl<T> Extend<T> for GapBuffer<T> {
715    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
716        let len = self.len;
717        self.insert_many(len, iter);
718    }
719}
720
721impl<'gb, T: 'gb + Copy> Extend<&'gb T> for GapBuffer<T> {
722    fn extend<I: IntoIterator<Item = &'gb T>>(&mut self, iter: I) {
723        self.extend(iter.into_iter().cloned());
724    }
725}
726
727#[derive(Hash)]
728#[cfg_attr(feature = "bincode", derive(bincode::Decode, bincode::Encode))]
729struct RawGapBuffer<T>(Slice<T>);
730
731impl<T> RawGapBuffer<T> {
732    const fn new() -> Self {
733        RawGapBuffer(Slice::empty())
734    }
735
736    const fn from_vec(vec: Vec<T>) -> Self {
737        Self(Slice::from_vec(vec))
738    }
739
740    fn realloc(&mut self, new_cap: usize) {
741        let old_cap = self.0.cap;
742        if old_cap == new_cap {
743            return;
744        }
745        if size_of::<T>() != 0 {
746            unsafe {
747                let old_layout = Self::get_layout(old_cap);
748                let new_layout = Self::get_layout(new_cap);
749                let p = self.0.ptr.as_ptr() as *mut u8;
750                self.0.ptr = if new_cap == 0 {
751                    dealloc(p, old_layout);
752                    NonNull::dangling()
753                } else {
754                    NonNull::new(if old_cap == 0 {
755                        alloc(new_layout)
756                    } else {
757                        realloc(p, old_layout, new_layout.size())
758                    } as *mut T)
759                    .unwrap_or_else(|| handle_alloc_error(new_layout))
760                };
761            }
762        }
763        self.0.cap = new_cap;
764    }
765
766    fn get_layout(cap: usize) -> Layout {
767        let new_size = size_of::<T>()
768            .checked_mul(cap)
769            .expect("memory size overflow");
770        Layout::from_size_align(new_size, align_of::<T>()).unwrap()
771    }
772}
773impl<T> Drop for RawGapBuffer<T> {
774    fn drop(&mut self) {
775        self.realloc(0)
776    }
777}
778
779////////////////////////////////////////////////////////////////////////////////
780// Range, RangeMut
781////////////////////////////////////////////////////////////////////////////////
782
783/// Immutable sub-range of [`GapBuffer`]
784///
785/// This struct is created by [`Slice::range`].
786#[derive(Hash)]
787pub struct Range<'gb, T: 'gb> {
788    s: Slice<T>,
789    _phantom: PhantomData<&'gb [T]>,
790}
791
792/// Mutable sub-range of [`GapBuffer`].
793///
794/// This struct is created by [`Slice::range_mut`].
795#[derive(Hash)]
796pub struct RangeMut<'gb, T: 'gb> {
797    s: Slice<T>,
798    _phantom: PhantomData<&'gb mut [T]>,
799}
800impl<'gb, T: 'gb> Range<'gb, T> {
801    #[inline]
802    const unsafe fn new(s: Slice<T>) -> Self {
803        Range {
804            s,
805            _phantom: PhantomData,
806        }
807    }
808
809    /// Construct a new, empty `Range`.
810    #[inline]
811    pub const fn empty() -> Self {
812        unsafe { Range::new(Slice::empty()) }
813    }
814
815    /// Returns a reference to an element at index or None if out of bounds.
816    ///
817    /// Unlike [`Slice::get`], return value not borrow `self`.
818    #[inline]
819    pub fn get(&self, index: usize) -> Option<&'gb T> {
820        unsafe { self.s.get_with_lifetime(index) }
821    }
822
823    /// Return a immutable sub-range of this Slice.
824    ///
825    /// Unlike [`Slice::range`], return value not borrow `self`.
826    pub fn range(&self, range: impl RangeBounds<usize>) -> Range<'gb, T> {
827        unsafe { self.range_with_lifetime(range) }
828    }
829
830    /// Returns a pair of slices.
831    /// First slice is before gap. Second slice is after gap.
832    ///
833    /// Unlike [`Slice::as_slices`], return value not borrow `self`.
834    pub fn as_slices(&self) -> (&'gb [T], &'gb [T]) {
835        unsafe { self.as_slices_with_lifetime() }
836    }
837}
838impl<'gb, T: 'gb> RangeMut<'gb, T> {
839    #[inline]
840    const unsafe fn new(s: Slice<T>) -> Self {
841        RangeMut {
842            s,
843            _phantom: PhantomData,
844        }
845    }
846
847    /// Construct a new, empty `RangeMut`.
848    #[inline]
849    pub const fn empty() -> Self {
850        unsafe { RangeMut::new(Slice::empty()) }
851    }
852}
853
854impl<T> Deref for Range<'_, T> {
855    type Target = Slice<T>;
856
857    #[inline]
858    fn deref(&self) -> &Self::Target {
859        &self.s
860    }
861}
862impl<T> Deref for RangeMut<'_, T> {
863    type Target = Slice<T>;
864
865    #[inline]
866    fn deref(&self) -> &Self::Target {
867        &self.s
868    }
869}
870
871impl<T> DerefMut for RangeMut<'_, T> {
872    #[inline]
873    fn deref_mut(&mut self) -> &mut Self::Target {
874        &mut self.s
875    }
876}
877
878impl<T> Clone for Range<'_, T> {
879    fn clone(&self) -> Self {
880        unsafe {
881            Range::new(Slice {
882                ptr: self.ptr,
883                cap: self.cap,
884                gap: self.gap,
885                len: self.len,
886            })
887        }
888    }
889}
890
891////////////////////////////////////////////////////////////////////////////////
892// Slice
893////////////////////////////////////////////////////////////////////////////////
894
895/// Sub-range of [`GapBuffer`].
896/// `Slice` define common method for [`GapBuffer`], [`Range`], [`RangeMut`].
897pub struct Slice<T> {
898    ptr: NonNull<T>,
899    cap: usize,
900    gap: usize,
901    len: usize,
902}
903impl<T> Slice<T> {
904    /// Construct a new, empty `Slice`.
905    pub const fn empty() -> Self {
906        Slice {
907            ptr: NonNull::dangling(),
908            cap: 0,
909            gap: 0,
910            len: 0,
911        }
912    }
913
914    /// Constructs a `Slice` from a [`Vec<T>`] at `O(1)`.
915    const fn from_vec(mut vec: Vec<T>) -> Self {
916        let slice = Slice {
917            ptr: match NonNull::new(vec.as_mut_ptr()) {
918                Some(non_null) => non_null,
919                None => NonNull::dangling(),
920            },
921            cap: vec.capacity(),
922            gap: vec.len(),
923            len: vec.len(),
924        };
925
926        let _dont_drop = std::mem::ManuallyDrop::new(vec);
927
928        slice
929    }
930
931    /// Returns the number of elements in the GapBuffer.
932    #[inline]
933    pub const fn len(&self) -> usize {
934        self.len
935    }
936
937    /// Returns true if the GapBuffer contains no elements.
938    #[inline]
939    pub const fn is_empty(&self) -> bool {
940        self.len() == 0
941    }
942
943    /// Returns a reference to an element at index or None if out of bounds.
944    #[inline]
945    pub fn get(&self, index: usize) -> Option<&T> {
946        unsafe { self.get_with_lifetime(index) }
947    }
948    #[inline]
949    unsafe fn get_with_lifetime<'gb>(&self, index: usize) -> Option<&'gb T> {
950        self.get_offset(index)
951            .map(|o| unsafe { &*self.as_ptr().add(o) })
952    }
953
954    /// Returns a mutable reference to an element at index or None if out of bounds.
955    #[inline]
956    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
957        self.get_offset(index)
958            .map(|o| unsafe { &mut *self.as_mut_ptr().add(o) })
959    }
960
961    #[inline]
962    fn move_values(&mut self, gap: usize) {
963        let gap_old = self.gap;
964        let gap_len = self.gap_len();
965        let (src, dest, count) = if gap < gap_old {
966            (gap, gap + gap_len, gap_old - gap)
967        } else {
968            (gap_old + gap_len, gap_old, gap - gap_old)
969        };
970        let p = self.as_mut_ptr();
971        unsafe {
972            copy(p.add(src), p.add(dest), count);
973        }
974    }
975
976    /// Swaps two elements in the GapBuffer.
977    ///
978    /// # Arguments
979    ///
980    /// * a - The index of the first element
981    /// * b - The index of the second element
982    ///
983    /// # Panics
984    /// Panics if `a >= self.len()` or `b >= self.len()`.
985    #[inline]
986    pub const fn swap(&mut self, a: usize, b: usize) {
987        let oa = self.get_offset(a).expect("a is out of bounds.");
988        let ob = self.get_offset(b).expect("b is out of bounds.");
989        let p = self.as_mut_ptr();
990        unsafe { ptr::swap(p.add(oa), p.add(ob)) }
991    }
992
993    /// Return a immutable sub-range of this Slice.
994    ///
995    /// # Panics
996    /// Panics if `range` is out of bounds.
997    ///
998    /// # Examples
999    /// ```
1000    /// use gap_buf::gap_buffer;
1001    ///
1002    /// let buf = gap_buffer![1, 2, 3, 4, 5];
1003    ///
1004    /// let r1 = buf.range(1..);
1005    /// assert_eq!(r1, [2, 3, 4, 5]);
1006    ///
1007    /// let r2 = r1.range(1..3);
1008    /// assert_eq!(r2, [3, 4]);
1009    /// ```
1010    pub fn range(&self, range: impl RangeBounds<usize>) -> Range<'_, T> {
1011        unsafe { self.range_with_lifetime(range) }
1012    }
1013    unsafe fn range_with_lifetime<'gb>(&self, range: impl RangeBounds<usize>) -> Range<'gb, T> {
1014        unsafe { Range::new(self.range_slice(range)) }
1015    }
1016
1017    /// Return a mutable sub-range of this Slice.
1018    ///
1019    /// # Panics
1020    /// Panics if `range` is out of bounds.
1021    ///
1022    /// # Examples
1023    /// ```
1024    /// use gap_buf::gap_buffer;
1025    ///
1026    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
1027    /// {
1028    ///     let mut r = buf.range_mut(1..);
1029    ///     assert_eq!(r, [2, 3, 4, 5]);
1030    ///     r[0] = 0;
1031    /// }
1032    /// assert_eq!(buf, [1, 0, 3, 4, 5]);
1033    /// ```
1034    pub fn range_mut(&mut self, range: impl RangeBounds<usize>) -> RangeMut<'_, T> {
1035        unsafe { RangeMut::new(self.range_slice(range)) }
1036    }
1037    unsafe fn range_slice(&self, range: impl RangeBounds<usize>) -> Slice<T> {
1038        let (idx, len) = self.to_idx_len(range);
1039        if len == 0 {
1040            return Slice::empty();
1041        }
1042
1043        let gap_is_before = self.gap <= idx;
1044        let gap_is_after = idx + len <= self.gap;
1045
1046        let gap = if gap_is_before {
1047            0
1048        } else if !gap_is_after {
1049            self.gap - idx
1050        } else {
1051            len
1052        };
1053        let begin = if gap_is_before { self.gap_len() } else { 0 } + idx;
1054        let end = if !gap_is_after { self.gap_len() } else { 0 } + idx + len;
1055
1056        Slice {
1057            ptr: NonNull::new(unsafe { self.ptr.as_ptr().add(begin) }).unwrap(),
1058            cap: end - begin,
1059            gap,
1060            len,
1061        }
1062    }
1063    fn to_idx_len(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
1064        use std::ops::Bound::*;
1065        const MAX: usize = usize::MAX;
1066        let len = self.len;
1067        let idx = match range.start_bound() {
1068            Included(&idx) => idx,
1069            Excluded(&MAX) => panic!("attempted to index slice up to maximum usize"),
1070            Excluded(&idx) => idx + 1,
1071            Unbounded => 0,
1072        };
1073        if idx > len {
1074            panic!("index {idx} out of range for slice of length {len}");
1075        }
1076
1077        let end = match range.end_bound() {
1078            Included(&MAX) => panic!("attempted to index slice up to maximum usize"),
1079            Included(&idx) => idx + 1,
1080            Excluded(&idx) => idx,
1081            Unbounded => len,
1082        };
1083        if end > len {
1084            panic!("index {end} out of range for slice of length {len}");
1085        }
1086
1087        if end < idx {
1088            panic!("slice index starts at {idx} but ends at {len}");
1089        }
1090        (idx, end - idx)
1091    }
1092
1093    /// Returns a pair of slices.
1094    /// First slice is before gap. Second slice is after gap.
1095    ///
1096    /// # Examples
1097    /// ```
1098    /// use gap_buf::gap_buffer;
1099    ///
1100    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
1101    /// buf.set_gap(2);
1102    /// let (s1, s2) = buf.as_slices();
1103    /// assert_eq!(s1, [1, 2]);
1104    /// assert_eq!(s2, [3, 4, 5]);
1105    /// ```
1106    pub fn as_slices(&self) -> (&[T], &[T]) {
1107        unsafe { self.as_slices_with_lifetime() }
1108    }
1109    const unsafe fn as_slices_with_lifetime<'gb>(&self) -> (&'gb [T], &'gb [T]) {
1110        let p0 = self.as_ptr();
1111        let c1 = self.len - self.gap;
1112        let p1 = unsafe { p0.add(self.cap - c1) };
1113        (unsafe { slice::from_raw_parts(p0, self.gap) }, unsafe {
1114            slice::from_raw_parts(p1, c1)
1115        })
1116    }
1117
1118    /// Returns a pair of slices.
1119    /// First slice is before gap. Second slice is after gap.
1120    ///
1121    /// # Examples
1122    /// ```
1123    /// use gap_buf::gap_buffer;
1124    ///
1125    /// let mut buf = gap_buffer![1, 2, 3, 4, 5];
1126    /// buf.set_gap(2);
1127    /// {
1128    ///     let (mut s1, mut s2) = buf.as_mut_slices();
1129    ///     s1[0] = 10;
1130    ///     s2[0] = 11;
1131    /// }
1132    /// assert_eq!(buf, [10, 2, 11, 4, 5]);
1133    /// ```
1134    pub const fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
1135        unsafe {
1136            let p0 = self.as_mut_ptr();
1137            let c1 = self.len - self.gap;
1138            let p1 = p0.add(self.cap - c1);
1139            (
1140                slice::from_raw_parts_mut(p0, self.gap),
1141                slice::from_raw_parts_mut(p1, c1),
1142            )
1143        }
1144    }
1145
1146    /// Returns an iterator over the Slice.
1147    pub fn iter(&self) -> Iter<'_, T> {
1148        let (s0, s1) = self.as_slices();
1149        s0.iter().chain(s1.iter())
1150    }
1151
1152    /// Returns an iterator that allows modifying each value.
1153    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
1154        let (s0, s1) = self.as_mut_slices();
1155        s0.iter_mut().chain(s1.iter_mut())
1156    }
1157
1158    #[inline]
1159    const fn get_offset(&self, index: usize) -> Option<usize> {
1160        if index < self.gap {
1161            Some(index)
1162        } else if index < self.len {
1163            Some(index + self.gap_len())
1164        } else {
1165            None
1166        }
1167    }
1168
1169    #[inline]
1170    const fn gap_len(&self) -> usize {
1171        self.cap - self.len
1172    }
1173
1174    #[inline]
1175    const fn as_ptr(&self) -> *const T {
1176        self.ptr.as_ptr()
1177    }
1178
1179    #[inline]
1180    const fn as_mut_ptr(&mut self) -> *mut T {
1181        self.ptr.as_ptr()
1182    }
1183}
1184
1185impl<T: Clone> Clone for Slice<T> {
1186    fn clone(&self) -> Self {
1187        let vec = self.iter().cloned().collect();
1188        Self::from_vec(vec)
1189    }
1190}
1191
1192unsafe impl<T: Sync> Sync for Slice<T> {}
1193unsafe impl<T: Send> Send for Slice<T> {}
1194
1195#[cfg(feature = "bincode")]
1196impl<T: bincode::Decode<Context>, Context> bincode::Decode<Context> for Slice<T> {
1197    fn decode<D: bincode::de::Decoder<Context = Context>>(
1198        decoder: &mut D,
1199    ) -> Result<Self, bincode::error::DecodeError> {
1200        let vec: Vec<T> = bincode::Decode::decode(decoder)?;
1201        Ok(Self::from_vec(vec))
1202    }
1203}
1204
1205#[cfg(feature = "bincode")]
1206impl<'de, T, Context> bincode::BorrowDecode<'de, Context> for Slice<T>
1207where
1208    T: bincode::BorrowDecode<'de, Context>,
1209{
1210    fn borrow_decode<D: bincode::de::BorrowDecoder<'de, Context = Context>>(
1211        decoder: &mut D,
1212    ) -> Result<Self, bincode::error::DecodeError> {
1213        let vec: Vec<T> = bincode::BorrowDecode::borrow_decode(decoder)?;
1214        Ok(Self::from_vec(vec))
1215    }
1216}
1217
1218#[cfg(feature = "bincode")]
1219impl<T: bincode::Encode> bincode::Encode for Slice<T> {
1220    fn encode<E: bincode::enc::Encoder>(
1221        &self,
1222        encoder: &mut E,
1223    ) -> Result<(), bincode::error::EncodeError> {
1224        use bincode::enc::write::Writer;
1225        let (s0, s1) = self.as_slices();
1226
1227        bincode::Encode::encode(&(self.len as u64), encoder)?;
1228
1229        if unty::type_equal::<T, u8>() {
1230            // Safety: T = u8
1231            let s0: &[u8] = unsafe { core::mem::transmute(s0) };
1232            encoder.writer().write(s0)?;
1233            let s1: &[u8] = unsafe { core::mem::transmute(s1) };
1234            encoder.writer().write(s1)?;
1235        } else {
1236            for item in self {
1237                item.encode(encoder)?;
1238            }
1239        }
1240
1241        Ok(())
1242    }
1243}
1244
1245impl<T> From<Slice<T>> for Vec<T> {
1246    fn from(mut value: Slice<T>) -> Self {
1247        if value.gap != value.len {
1248            value.move_values(value.len);
1249        }
1250        let vec = unsafe { Self::from_raw_parts(value.ptr.as_ptr(), value.len, value.cap) };
1251
1252        let _dont_drop = std::mem::ManuallyDrop::new(value);
1253
1254        vec
1255    }
1256}
1257
1258////////////////////////////////////////////////////////////////////////////////
1259// Default
1260////////////////////////////////////////////////////////////////////////////////
1261
1262impl<T> Default for GapBuffer<T> {
1263    #[inline]
1264    fn default() -> Self {
1265        Self::new()
1266    }
1267}
1268impl<T> Default for Range<'_, T> {
1269    #[inline]
1270    fn default() -> Self {
1271        Self::empty()
1272    }
1273}
1274impl<T> Default for RangeMut<'_, T> {
1275    #[inline]
1276    fn default() -> Self {
1277        Self::empty()
1278    }
1279}
1280
1281////////////////////////////////////////////////////////////////////////////////
1282// Index, IndexMut
1283////////////////////////////////////////////////////////////////////////////////
1284
1285impl<T> Index<usize> for GapBuffer<T> {
1286    type Output = T;
1287
1288    #[inline]
1289    fn index(&self, index: usize) -> &T {
1290        self.deref().index(index)
1291    }
1292}
1293impl<T> IndexMut<usize> for GapBuffer<T> {
1294    #[inline]
1295    fn index_mut(&mut self, index: usize) -> &mut T {
1296        self.deref_mut().index_mut(index)
1297    }
1298}
1299
1300impl<T> Index<usize> for Range<'_, T> {
1301    type Output = T;
1302
1303    #[inline]
1304    fn index(&self, index: usize) -> &T {
1305        self.deref().index(index)
1306    }
1307}
1308impl<T> Index<usize> for RangeMut<'_, T> {
1309    type Output = T;
1310
1311    #[inline]
1312    fn index(&self, index: usize) -> &T {
1313        self.deref().index(index)
1314    }
1315}
1316impl<T> IndexMut<usize> for RangeMut<'_, T> {
1317    #[inline]
1318    fn index_mut(&mut self, index: usize) -> &mut T {
1319        self.deref_mut().index_mut(index)
1320    }
1321}
1322
1323impl<T> Index<usize> for Slice<T> {
1324    type Output = T;
1325
1326    #[inline]
1327    fn index(&self, index: usize) -> &T {
1328        self.get(index).expect("index out of bounds")
1329    }
1330}
1331impl<T> IndexMut<usize> for Slice<T> {
1332    #[inline]
1333    fn index_mut(&mut self, index: usize) -> &mut T {
1334        self.get_mut(index).expect("index out of bounds")
1335    }
1336}
1337
1338////////////////////////////////////////////////////////////////////////////////
1339// Debug
1340////////////////////////////////////////////////////////////////////////////////
1341
1342impl<T> Debug for GapBuffer<T>
1343where
1344    T: Debug,
1345{
1346    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1347        self.deref().fmt(f)
1348    }
1349}
1350impl<T> Debug for Range<'_, T>
1351where
1352    T: Debug,
1353{
1354    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1355        self.deref().fmt(f)
1356    }
1357}
1358impl<T> Debug for RangeMut<'_, T>
1359where
1360    T: Debug,
1361{
1362    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1363        self.deref().fmt(f)
1364    }
1365}
1366
1367impl<T> Debug for Slice<T>
1368where
1369    T: Debug,
1370{
1371    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
1372        f.debug_list().entries(self).finish()
1373    }
1374}
1375
1376impl<T: Hash> Hash for Slice<T> {
1377    fn hash<H: Hasher>(&self, state: &mut H) {
1378        for value in self {
1379            value.hash(state);
1380        }
1381    }
1382}
1383
1384////////////////////////////////////////////////////////////////////////////////
1385// Eq, PartialEq
1386////////////////////////////////////////////////////////////////////////////////
1387
1388impl<T, S> PartialEq<S> for GapBuffer<T>
1389where
1390    T: PartialEq,
1391    S: ?Sized,
1392    for<'b> &'b S: IntoIterator<Item = &'b T>,
1393{
1394    fn eq(&self, other: &S) -> bool {
1395        self.deref().eq(other)
1396    }
1397}
1398impl<T: Eq> Eq for GapBuffer<T> {}
1399
1400impl<T, S> PartialEq<S> for Range<'_, 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 Range<'_, T> {}
1411
1412impl<T, S> PartialEq<S> for RangeMut<'_, 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 RangeMut<'_, T> {}
1423
1424impl<T, S> PartialEq<S> for Slice<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.iter().eq(other)
1432    }
1433}
1434impl<T: Eq> Eq for Slice<T> {}
1435
1436////////////////////////////////////////////////////////////////////////////////
1437// Ord, PartialOrd
1438////////////////////////////////////////////////////////////////////////////////
1439
1440impl<T, S> PartialOrd<S> for GapBuffer<T>
1441where
1442    T: PartialOrd,
1443    S: ?Sized,
1444    for<'b> &'b S: IntoIterator<Item = &'b T>,
1445{
1446    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1447        self.deref().partial_cmp(other)
1448    }
1449}
1450
1451impl<T: Ord> Ord for GapBuffer<T> {
1452    fn cmp(&self, other: &Self) -> Ordering {
1453        self.deref().cmp(other)
1454    }
1455}
1456
1457impl<T, S> PartialOrd<S> for Range<'_, T>
1458where
1459    T: PartialOrd,
1460    S: ?Sized,
1461    for<'b> &'b S: IntoIterator<Item = &'b T>,
1462{
1463    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1464        self.deref().partial_cmp(other)
1465    }
1466}
1467
1468impl<T: Ord> Ord for Range<'_, T> {
1469    fn cmp(&self, other: &Self) -> Ordering {
1470        self.deref().cmp(other)
1471    }
1472}
1473
1474impl<T, S> PartialOrd<S> for RangeMut<'_, T>
1475where
1476    T: PartialOrd,
1477    S: ?Sized,
1478    for<'b> &'b S: IntoIterator<Item = &'b T>,
1479{
1480    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1481        self.deref().partial_cmp(other)
1482    }
1483}
1484
1485impl<T: Ord> Ord for RangeMut<'_, T> {
1486    fn cmp(&self, other: &Self) -> Ordering {
1487        self.deref().cmp(other)
1488    }
1489}
1490
1491impl<T, S> PartialOrd<S> for Slice<T>
1492where
1493    T: PartialOrd,
1494    S: ?Sized,
1495    for<'b> &'b S: IntoIterator<Item = &'b T>,
1496{
1497    fn partial_cmp(&self, other: &S) -> Option<Ordering> {
1498        self.iter().partial_cmp(other)
1499    }
1500}
1501
1502impl<T: Ord> Ord for Slice<T> {
1503    fn cmp(&self, other: &Self) -> Ordering {
1504        self.iter().cmp(other)
1505    }
1506}
1507
1508////////////////////////////////////////////////////////////////////////////////
1509// iterator
1510////////////////////////////////////////////////////////////////////////////////
1511
1512/// Immutable GapBuffer iterator.
1513pub type Iter<'gb, T> = Chain<slice::Iter<'gb, T>, slice::Iter<'gb, T>>;
1514
1515/// Mutable GapBuffer iterator.
1516pub type IterMut<'gb, T> = Chain<slice::IterMut<'gb, T>, slice::IterMut<'gb, T>>;
1517
1518/// An iterator that moves out of a [`GapBuffer`].
1519pub struct IntoIter<T> {
1520    buf: GapBuffer<T>,
1521}
1522impl<T> Iterator for IntoIter<T> {
1523    type Item = T;
1524
1525    fn next(&mut self) -> Option<T> {
1526        self.buf.pop_front()
1527    }
1528    fn size_hint(&self) -> (usize, Option<usize>) {
1529        let len = self.buf.len();
1530        (len, Some(len))
1531    }
1532}
1533impl<T> ExactSizeIterator for IntoIter<T> {}
1534impl<T> FusedIterator for IntoIter<T> {}
1535impl<T> DoubleEndedIterator for IntoIter<T> {
1536    fn next_back(&mut self) -> Option<T> {
1537        self.buf.pop_back()
1538    }
1539}
1540
1541impl<T> IntoIterator for GapBuffer<T> {
1542    type Item = T;
1543    type IntoIter = IntoIter<T>;
1544    fn into_iter(self) -> IntoIter<T> {
1545        IntoIter { buf: self }
1546    }
1547}
1548
1549impl<'gb, T> IntoIterator for &'gb GapBuffer<T> {
1550    type Item = &'gb T;
1551    type IntoIter = Iter<'gb, T>;
1552    fn into_iter(self) -> Iter<'gb, T> {
1553        self.iter()
1554    }
1555}
1556impl<'gb, T> IntoIterator for &'gb Range<'_, 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}
1563impl<'gb, T> IntoIterator for &'gb RangeMut<'_, T> {
1564    type Item = &'gb T;
1565    type IntoIter = Iter<'gb, T>;
1566    fn into_iter(self) -> Iter<'gb, T> {
1567        self.iter()
1568    }
1569}
1570
1571impl<'gb, T> IntoIterator for &'gb Slice<T> {
1572    type Item = &'gb T;
1573    type IntoIter = Iter<'gb, T>;
1574    fn into_iter(self) -> Iter<'gb, T> {
1575        self.iter()
1576    }
1577}
1578
1579impl<'gb, T> IntoIterator for &'gb mut GapBuffer<T> {
1580    type Item = &'gb mut T;
1581    type IntoIter = IterMut<'gb, T>;
1582    fn into_iter(self) -> IterMut<'gb, T> {
1583        self.iter_mut()
1584    }
1585}
1586
1587impl<'gb, T> IntoIterator for &'gb mut RangeMut<'gb, T> {
1588    type Item = &'gb mut T;
1589    type IntoIter = IterMut<'gb, T>;
1590    fn into_iter(self) -> IterMut<'gb, T> {
1591        self.iter_mut()
1592    }
1593}
1594
1595impl<'gb, T> IntoIterator for &'gb mut Slice<T> {
1596    type Item = &'gb mut T;
1597    type IntoIter = IterMut<'gb, T>;
1598    fn into_iter(self) -> IterMut<'gb, T> {
1599        self.iter_mut()
1600    }
1601}
1602
1603/// A draining iterator for [`GapBuffer`].
1604///
1605/// This struct is created by [`GapBuffer::drain`].
1606pub struct Drain<'gb, T: 'gb> {
1607    buf: &'gb mut GapBuffer<T>,
1608    idx: usize,
1609    len: usize,
1610}
1611
1612impl<T> Iterator for Drain<'_, T> {
1613    type Item = T;
1614    fn next(&mut self) -> Option<T> {
1615        if self.len == 0 {
1616            None
1617        } else {
1618            self.len -= 1;
1619            Some(self.buf.remove(self.idx))
1620        }
1621    }
1622    fn size_hint(&self) -> (usize, Option<usize>) {
1623        (self.len, Some(self.len))
1624    }
1625}
1626
1627impl<T> Drop for Drain<'_, T> {
1628    fn drop(&mut self) {
1629        let len = self.len;
1630        self.nth(len);
1631    }
1632}
1633
1634impl<T> ExactSizeIterator for Drain<'_, T> {}
1635impl<T> FusedIterator for Drain<'_, T> {}
1636
1637/// An iterator that conditionally extracts from a [`GapBuffer`].
1638///
1639/// this struct is created by [`GapBuffer::extract_if`].
1640#[must_use]
1641pub struct ExtractIf<'gb, T: 'gb, F> {
1642    buf: &'gb mut GapBuffer<T>,
1643    idx: usize,
1644    end: usize,
1645    pred: F,
1646}
1647
1648impl<T, F> Iterator for ExtractIf<'_, T, F>
1649where
1650    F: FnMut(&mut T) -> bool,
1651{
1652    type Item = T;
1653
1654    fn next(&mut self) -> Option<T> {
1655        while self.idx < self.end {
1656            if (self.pred)(self.buf.get_mut(self.idx).unwrap()) {
1657                self.end -= 1;
1658                return Some(self.buf.remove(self.idx));
1659            } else {
1660                self.idx += 1;
1661            }
1662        }
1663
1664        None
1665    }
1666}
1667
1668impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&mut T) -> bool {}
gap_buf/gap_buffer.rs

gap_buf/
gap_buffer.rs
