extract_vec.rs

#![feature(collections_range)]

use std::ops::{Bound, Range, RangeBounds};
use std::ptr;
use std::mem;

/// An extracting iterator for `Vec<T>`.
struct ExtractImpl<'a, T: 'a, F: FnMut(&mut T) -> bool> {
    /// Current remaining range to remove
    iter: Range<usize>,

    /// Counters for how many deletes have occured
    del_front: usize,
    del_back: usize,

    /// Counters to lazily compact retained items
    retained_front: usize,
    retained_back: usize,

    /// The vector
    vec: &'a mut Vec<T>,

    /// The original length of the vector, prior to memory safety adjustements
    len: usize,

    /// Whether or not to drain on destruct
    drain: bool,

    /// The predicate
    f: F,
}

unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for ExtractImpl<'a, T, F> {}
unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for ExtractImpl<'a, T, F> {}

impl<'a, T: 'a, F: FnMut(&mut T) -> bool> ExtractImpl<'a, T, F> {
    fn new<R: RangeBounds<usize>>(v: &mut Vec<T>, range: R, f: F) -> ExtractImpl<T, F> {
        // Memory safety
        //
        // When the Extract is first created, it shortens the length of
        // the source vector to make sure no uninitalized or moved-from elements
        // are accessible at all if the Extract's destructor never gets to run.
        //
        // Extract will ptr::read out the values to remove.
        // When finished, retained elements are copied back to cover
        // the hole, and the vector length is restored to the new length.
        //

        let len = v.len();
        let start = match range.start() {
            Bound::Unbounded => 0,
            Bound::Included(&v) => v,
            Bound::Excluded(&v) => v + 1,
        };
        let end = match range.end() {
            Bound::Unbounded => len,
            Bound::Included(&v) => v + 1,
            Bound::Excluded(&v) => v,
        };

        // bounds check happens here
        &v[start..end];

        unsafe {
            // set self.vec length's to start, to be safe in case Extract is leaked
            v.set_len(start);
        }

        ExtractImpl {
            iter: start..end,
            del_front: 0,
            del_back: 0,
            retained_front: 0,
            retained_back: 0,
            vec: v,
            len,
            drain: false,
            f,
        }
    }

    fn set_drain(&mut self, drain: bool) {
        self.drain = drain;
    }

    fn change_filter<F2>(mut self, f: F2) -> ExtractImpl<'a, T, F2>
    where
        F2: FnMut(&mut T) -> bool,
    {
        unsafe {
            let v = ExtractImpl {
                iter: self.iter.clone(),
                del_front: self.del_front,
                del_back: self.del_back,
                retained_front: self.retained_front,
                retained_back: self.retained_back,
                vec: mem::replace(&mut self.vec, mem::uninitialized()),
                len: self.len,
                drain: self.drain,
                f,
            };
            mem::forget(self);
            v
        }
    }


    #[inline]
    fn next_helper(&mut self, front: bool) -> Option<T> {
        while let Some(i) = if front {
            self.iter.next()
        } else {
            self.iter.next_back()
        }
        {
            let v = &mut **self.vec;
            let del = if front {
                &mut self.del_front
            } else {
                &mut self.del_back
            };
            let retained = if front {
                &mut self.retained_front
            } else {
                &mut self.retained_back
            };

            unsafe {
                let e = v.as_mut_ptr().offset(i as isize);
                if (self.f)(&mut *e) {
                    // Compact
                    if *retained > 0 {
                        let start = (i - *retained) as isize;
                        let src = v.as_ptr().offset(start);
                        let dst = v.as_mut_ptr().offset(start - *del as isize);
                        ptr::copy(src, dst, *retained);
                        *retained = 0;
                    }

                    // Process the delete
                    *del += 1;

                    return Some(ptr::read(e));
                } else if *del > 0 {
                    *retained += 1;
                }
            }
        }
        None
    }
}

impl<'a, T: 'a, F: FnMut(&mut T) -> bool> Drop for ExtractImpl<'a, T, F> {
    fn drop(&mut self) {
        if self.drain {
            while let Some(_) = self.next_helper(true) {}
        }

        // Let's look at our array
        // [ start_block  junk_block  middle_block  junk_block  end_block ]
        //
        // the start block consists of 2 parts:
        //   items before the slice Extract is operating on
        //   items that have been retained from `next` and compacted to the front
        // the middle block consist of 3 parts:
        //   items retained from `next` awaiting compaction
        //   items which have not been accessed by the iterator
        //   items retained from `next_back` awaiting compaction
        // the end block consists of 2 parts:
        //   items that have been retained from `next_back`
        //   items after the slice Extract is operating on
        // the junk blocks are invalid portions of the array, due to elements being extracted
        //
        // We need to compact the array by using `ptr:copy` to move the middle and end blocks
        // closer to the start

        // So first let's get the offset of `middle_block`, this will be our first source index
        // We can find this by taking the start of the unaccessed portion of the iterator, and
        // subtracting the number of retained items awaiting compaction
        let middle_block_offset = self.iter.start - self.retained_front;

        // Now let's find the the offset of the first `junk_block`, this will be our first
        // destination index. We can find this by taking the middle_block offset, and subtracting
        // the number of extracted items. This offset is also the size of the start_block which
        // will be useful later.
        let junk_offset = middle_block_offset - self.del_front;
        let start_block_size = junk_offset;

        // Calculate the size of `middle_block`
        let middle_block_size = self.retained_front + (self.iter.end - self.iter.start) +
            self.retained_back;

        // Compact `middle_block`
        unsafe {
            let src = self.vec.as_ptr().offset(middle_block_offset as isize);
            let dst = self.vec.as_mut_ptr().offset(junk_offset as isize);
            ptr::copy(src, dst, middle_block_size);
        }

        // Now let's get the offset of `hi`, this will be our second source index
        // We can find this by taking the end of the unaccessed portion of the the iterator,
        // adding the number of retained and junk items
        let end_block_offset = self.iter.end + self.retained_back + self.del_back;

        // Our second destination is just our first destination, offset by how much we moved
        let junk_offset = junk_offset + middle_block_size;

        // Since we're just copying to the end of the array, the size is just `len - offset`
        let end_block_size = self.len - end_block_offset;

        // Compact `end_block`
        unsafe {
            let src = self.vec.as_ptr().offset(end_block_offset as isize);
            let dst = self.vec.as_mut_ptr().offset(junk_offset as isize);
            ptr::copy(src, dst, end_block_size);
        }

        // Set the length
        unsafe {
            self.vec.set_len(
                start_block_size + middle_block_size +
                    end_block_size,
            );
        }
    }
}

pub mod option1 {
    use std::ops::RangeBounds;
    use std::vec;

    use super::ExtractImpl;

    pub struct Vec<T>(vec::Vec<T>);

    /// An extracting iterator for `Vec<T>`.
    pub struct Extract<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    impl<T> Vec<T> {
        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector that satisfy the predicate, and removes the yielded
        /// items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `Extract` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract(0..4, |x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract<R: RangeBounds<usize>, F>(&mut self, range: R, f: F) -> Extract<T, F>
        where
            F: FnMut(&mut T) -> bool,
        {
            Extract(ExtractImpl::new(&mut self.0, range, f))
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for Extract<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for Extract<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for Extract<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for Extract<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }
}

pub mod option2 {
    use std::ops::RangeBounds;
    use std::vec;

    use super::ExtractImpl;

    pub struct Vec<T>(vec::Vec<T>);

    /// An extracting iterator for `Vec<T>`.
    pub struct Extract<'a, T: 'a>(ExtractImpl<'a, T, fn(&mut T) -> bool>);

    /// A conditional extracting iterator for `Vec<T>`.
    pub struct ExtractIf<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    /// A conditional draining iterator for `Vec<T>`.
    pub struct DrainIf<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    impl<T> Vec<T> {
        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector, and removes the yielded items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `Extract` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract(0..4).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract<R: RangeBounds<usize>>(&mut self, range: R) -> Extract<T> {
            fn always<T>(_: &mut T) -> bool {
                true
            }
            Extract(ExtractImpl::new(&mut self.0, range, always))
        }

        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector that satisfy the predicate, and removes the yielded
        /// items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `ExtractIf` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract_if(0..4, |x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract_if<R, F>(&mut self, range: R, f: F) -> ExtractIf<T, F>
        where
            R: RangeBounds<usize>,
            F: FnMut(&mut T) -> bool,
        {
            ExtractIf(ExtractImpl::new(&mut self.0, range, f))
        }

        /// Create a draining iterator that removes items in the specified range in
        /// the vector that satisfy the predicate and yields the removed items.
        ///
        /// Note 1: The element range is removed even if the iterator is only
        /// partially consumed or not consumed at all.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `DrainIf` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.drain_if(0..4, |x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn drain_if<R, F>(&mut self, range: R, f: F) -> DrainIf<T, F>
        where
            R: RangeBounds<usize>,
            F: FnMut(&mut T) -> bool,
        {
            let mut v = ExtractImpl::new(&mut self.0, range, f);
            v.set_drain(true);
            DrainIf(v)
        }
    }


    unsafe impl<'a, T: Sync> Sync for Extract<'a, T> {}
    unsafe impl<'a, T: Send> Send for Extract<'a, T> {}

    impl<'a, T> Iterator for Extract<'a, T> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T> DoubleEndedIterator for Extract<'a, T> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for ExtractIf<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for ExtractIf<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for ExtractIf<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for ExtractIf<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for DrainIf<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for DrainIf<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for DrainIf<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for DrainIf<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }
}

pub mod option3 {
    use std::ops::RangeBounds;
    use std::vec;

    use super::ExtractImpl;

    pub struct Vec<T>(vec::Vec<T>);

    /// An extracting iterator for `Vec<T>`.
    pub struct Extract<'a, T: 'a>(ExtractImpl<'a, T, fn(&mut T) -> bool>);

    /// A conditional extracting iterator for `Vec<T>`.
    pub struct ExtractWhen<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    /// A conditional draining iterator for `Vec<T>`.
    pub struct DrainWhen<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    impl<T> Vec<T> {
        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector, and removes the yielded items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `Extract` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract(0..4).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract<R: RangeBounds<usize>>(&mut self, range: R) -> Extract<T> {
            fn always<T>(_: &mut T) -> bool {
                true
            }
            Extract(ExtractImpl::new(&mut self.0, range, always))
        }

        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector that satisfy the predicate, and removes the yielded
        /// items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `ExtractWhen` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract_when(0..4, |x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract_when<R, F>(&mut self, range: R, f: F) -> ExtractWhen<T, F>
        where
            R: RangeBounds<usize>,
            F: FnMut(&mut T) -> bool,
        {
            ExtractWhen(ExtractImpl::new(&mut self.0, range, f))
        }

        /// Create a draining iterator that removes items in the specified range in
        /// the vector that satisfy the predicate and yields the removed items.
        ///
        /// Note 1: The element range is removed even if the iterator is only
        /// partially consumed or not consumed at all.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `DrainWhen` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.drain_when(0..4, |x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn drain_when<R, F>(&mut self, range: R, f: F) -> DrainWhen<T, F>
        where
            R: RangeBounds<usize>,
            F: FnMut(&mut T) -> bool,
        {
            let mut v = ExtractImpl::new(&mut self.0, range, f);
            v.set_drain(true);
            DrainWhen(v)
        }
    }


    unsafe impl<'a, T: Sync> Sync for Extract<'a, T> {}
    unsafe impl<'a, T: Send> Send for Extract<'a, T> {}

    impl<'a, T> Iterator for Extract<'a, T> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T> DoubleEndedIterator for Extract<'a, T> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for ExtractWhen<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for ExtractWhen<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for ExtractWhen<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for ExtractWhen<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for DrainWhen<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for DrainWhen<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for DrainWhen<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for DrainWhen<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }
}

pub mod option4 {
    use std::ops::RangeBounds;
    use std::vec;

    use super::ExtractImpl;

    pub struct Vec<T>(vec::Vec<T>);

    /// An extracting iterator for `Vec<T>`.
    pub struct Extract<'a, T: 'a>(ExtractImpl<'a, T, fn(&mut T) -> bool>);

    /// A conditional extracting iterator for `Vec<T>`.
    pub struct ExtractWhen<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    /// A draining iterator for `Vec<T>`.
    pub struct Drain<'a, T: 'a>(ExtractImpl<'a, T, fn(&mut T) -> bool>);

    /// A conditional draining iterator for `Vec<T>`.
    pub struct DrainWhen<'a, T: 'a, F: FnMut(&mut T) -> bool>(ExtractImpl<'a, T, F>);

    fn always<T>(_: &mut T) -> bool {
        true
    }

    impl<T> Vec<T> {
        /// Creates a draining iterator that removes the specified range in the vector
        /// and yields the removed items.
        ///
        /// Note 1: The element range is removed even if the iterator is only
        /// partially consumed or not consumed at all.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector
        /// if the `Drain` value is leaked.
        ///
        /// # Panics
        ///
        /// Panics if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// # Examples
        ///
        /// ```
        /// let mut v = vec![1, 2, 3];
        /// let u: Vec<_> = v.drain(1..).collect();
        /// assert_eq!(v, &[1]);
        /// assert_eq!(u, &[2, 3]);
        ///
        /// // A full range clears the vector
        /// v.drain(..);
        /// assert_eq!(v, &[]);
        /// ```
        pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<T> {
            let mut v = Drain(ExtractImpl::new(&mut self.0, range, always));
            v.0.set_drain(true);
            v
        }

        /// Create an extracting iterator that yields elements from the specified
        /// range in the vector, and removes the yielded items.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `Extract` value is leaked.
        ///
        /// **Panics** if the starting point is greater than the end point or if
        /// the end point is greater than the length of the vector.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract(0..4).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn extract<R: RangeBounds<usize>>(&mut self, range: R) -> Extract<T> {
            Extract(ExtractImpl::new(&mut self.0, range, always))
        }
    }

    impl<'a, T> Drain<'a, T> {
        /// Transform this iterator into one that requires elements satisfy a
        /// predicate before being removed.
        ///
        /// Note 1: The element range is removed even if the iterator is only
        /// partially consumed or not consumed at all.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `DrainWhen` value is leaked.
        ///
        /// ```
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.drain(0..4).when(|x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn when<F: FnMut(&mut T) -> bool>(self, f: F) -> DrainWhen<'a, T, F> {
            DrainWhen(self.0.change_filter(f))
        }

        /// Transform this iterator into one that `extract`s (the element range is
        /// only removed when the iterator is consumed).
        pub fn extract(mut self) -> Extract<'a, T> {
            self.0.set_drain(false);
            Extract(self.0)
        }
    }

    impl<'a, T> Extract<'a, T> {
        /// Transform this iterator into one that requires elements satisfy a
        /// predicate before being removed.
        ///
        /// Note 1: Unaccessed elements are not removed and remain in the vector.
        ///
        /// Note 2: It is unspecified how many elements are removed from the vector,
        /// if the `ExtractWhen` value is leaked.
        ///
        /// ```
        /// use arrayvec::ArrayVec;
        ///
        /// let mut v = vec!([1, 2, 3, 2]);
        /// let u: Vec<_> = v.extract(0..4).when(|x| *x == 2).collect();
        /// assert_eq!(v, &[1, 3]);
        /// assert_eq!(u, &[2, 2]);
        /// ```
        pub fn when<F: FnMut(&mut T) -> bool>(self, f: F) -> ExtractWhen<'a, T, F> {
            ExtractWhen(self.0.change_filter(f))
        }

        /// Transform this iterator into one that `drain`s (the element range is
        /// removed even if the iterator is only partially consumed or not consumed
        /// at all).
        pub fn drain(mut self) -> Drain<'a, T> {
            self.0.set_drain(true);
            Drain(self.0)
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DrainWhen<'a, T, F> {
        /// Transform this iterator into one without a predicate.
        pub fn every(self) -> Drain<'a, T> {
            Drain(self.0.change_filter(always))
        }

        /// Transform this iterator into one that `extract`s (the element range is
        /// only removed when the iterator is consumed).
        pub fn extract(mut self) -> ExtractWhen<'a, T, F> {
            self.0.set_drain(false);
            ExtractWhen(self.0)
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> ExtractWhen<'a, T, F> {
        /// Transform this iterator into one without a predicate.
        pub fn every(self) -> Extract<'a, T> {
            Extract(self.0.change_filter(always))
        }

        /// Transform this iterator into one that `drain`s (the element range is
        /// removed even if the iterator is only partially consumed or not consumed
        /// at all).
        pub fn drain(mut self) -> DrainWhen<'a, T, F> {
            self.0.set_drain(false);
            DrainWhen(self.0)
        }
    }

    unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
    unsafe impl<'a, T: Send> Send for Drain<'a, T> {}

    impl<'a, T> Iterator for Drain<'a, T> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for DrainWhen<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for DrainWhen<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for DrainWhen<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for DrainWhen<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync> Sync for Extract<'a, T> {}
    unsafe impl<'a, T: Send> Send for Extract<'a, T> {}

    impl<'a, T> Iterator for Extract<'a, T> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T> DoubleEndedIterator for Extract<'a, T> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }

    unsafe impl<'a, T: Sync, F: FnMut(&mut T) -> bool> Sync for ExtractWhen<'a, T, F> {}
    unsafe impl<'a, T: Send, F: FnMut(&mut T) -> bool> Send for ExtractWhen<'a, T, F> {}

    impl<'a, T, F: FnMut(&mut T) -> bool> Iterator for ExtractWhen<'a, T, F> {
        type Item = T;

        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            self.0.next_helper(true)
        }

        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (0, Some(self.0.iter.len()))
        }
    }

    impl<'a, T, F: FnMut(&mut T) -> bool> DoubleEndedIterator for ExtractWhen<'a, T, F> {
        #[inline]
        fn next_back(&mut self) -> Option<Self::Item> {
            self.0.next_helper(false)
        }
    }
}