generic-arraydeque 0.2.0

#[cfg(any(feature = "alloc", feature = "std"))]
use std::{vec, vec::Vec};

use generic_array::typenum::*;

use super::*;

#[allow(unused_macros)]
#[cfg(feature = "std")]
macro_rules! struct_with_counted_drop {
    ($struct_name:ident $(( $( $elt_ty:ty ),+ ))?, $drop_counter:ident $( => $drop_stmt:expr )? ) => {
        thread_local! {static $drop_counter: ::core::cell::Cell<u32> = ::core::cell::Cell::new(0);}

        #[derive(Clone, Debug, PartialEq)]
        struct $struct_name $(( $( $elt_ty ),+ ))?;

        impl ::core::ops::Drop for $struct_name {
            fn drop(&mut self) {
                $drop_counter.set($drop_counter.get() + 1);

                $($drop_stmt(self))?
            }
        }
    };
    ($struct_name:ident $(( $( $elt_ty:ty ),+ ))?, $drop_counter:ident[ $drop_key:expr,$key_ty:ty ] $( => $drop_stmt:expr )? ) => {
        thread_local! {
            static $drop_counter: ::core::cell::RefCell<::std::collections::HashMap<$key_ty, u32>> =
                ::core::cell::RefCell::new(::std::collections::HashMap::new());
        }

        #[derive(Clone, Debug, PartialEq)]
        struct $struct_name $(( $( $elt_ty ),+ ))?;

        impl ::core::ops::Drop for $struct_name {
            fn drop(&mut self) {
                $drop_counter.with_borrow_mut(|counter| {
                    *counter.entry($drop_key(self)).or_default() += 1;
                });

                $($drop_stmt(self))?
            }
        }
    };
}

#[test]
fn test_swap_front_back_remove() {
  fn test(back: bool) {
    // This test checks that every single combination of tail position and length is tested.
    // Capacity 15 should be large enough to cover every case.
    let mut tester = GenericArrayDeque::<_, U15>::new();
    let usable_cap = tester.capacity();
    let final_len = usable_cap / 2;

    for len in 0..final_len {
      let expected: GenericArrayDeque<_, U15> = if back {
        GenericArrayDeque::try_from_exact_iter(0..len).unwrap()
      } else {
        GenericArrayDeque::try_from_exact_iter((0..len).rev()).unwrap()
      };
      for head_pos in 0..usable_cap {
        tester.head = head_pos;
        tester.len = 0;
        if back {
          for i in 0..len * 2 {
            tester.push_front(i);
          }
          for i in 0..len {
            assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
          }
        } else {
          for i in 0..len * 2 {
            tester.push_back(i);
          }
          for i in 0..len {
            let idx = tester.len() - 1 - i;
            assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
          }
        }
        assert!(tester.head <= tester.capacity());
        assert!(tester.len <= tester.capacity());
        assert_eq!(tester, expected);
      }
    }
  }
  test(true);
  test(false);
}

#[test]
fn test_insert() {
  // This test checks that every single combination of tail position, length, and
  // insertion position is tested. Capacity 15 should be large enough to cover every case.

  let mut tester = GenericArrayDeque::<_, U15>::new();
  // can't guarantee we got 15, so have to get what we got.
  // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
  // this test isn't covering what it wants to
  let cap = tester.capacity();

  // len is the length *after* insertion
  let minlen = if cfg!(miri) { cap - 1 } else { 1 }; // Miri is too slow
  for len in minlen..cap {
    // 0, 1, 2, .., len - 1
    let expected = GenericArrayDeque::<_, U15>::try_from_iter((0..).take(len)).unwrap();
    for head_pos in 0..cap {
      for to_insert in 0..len {
        tester.head = head_pos;
        tester.len = 0;
        for i in 0..len {
          if i != to_insert {
            tester.push_back(i);
          }
        }
        tester.insert(to_insert, to_insert);
        assert!(tester.head <= tester.capacity());
        assert!(tester.len <= tester.capacity());
        assert_eq!(tester, expected);
      }
    }
  }
}

#[test]
fn test_get() {
  let mut tester = GenericArrayDeque::<_, U5>::new();
  tester.push_back(1);
  tester.push_back(2);
  tester.push_back(3);

  assert_eq!(tester.len(), 3);

  assert_eq!(tester.get(1), Some(&2));
  assert_eq!(tester.get(2), Some(&3));
  assert_eq!(tester.get(0), Some(&1));
  assert_eq!(tester.get(3), None);

  tester.remove(0);

  assert_eq!(tester.len(), 2);
  assert_eq!(tester.get(0), Some(&2));
  assert_eq!(tester.get(1), Some(&3));
  assert_eq!(tester.get(2), None);
}

#[test]
fn test_get_mut() {
  let mut tester = GenericArrayDeque::<_, U5>::new();
  tester.push_back(1);
  tester.push_back(2);
  tester.push_back(3);

  assert_eq!(tester.len(), 3);

  if let Some(elem) = tester.get_mut(0) {
    assert_eq!(*elem, 1);
    *elem = 10;
  }

  if let Some(elem) = tester.get_mut(2) {
    assert_eq!(*elem, 3);
    *elem = 30;
  }

  assert_eq!(tester.get(0), Some(&10));
  assert_eq!(tester.get(2), Some(&30));
  assert_eq!(tester.get_mut(3), None);

  tester.remove(2);

  assert_eq!(tester.len(), 2);
  assert_eq!(tester.get(0), Some(&10));
  assert_eq!(tester.get(1), Some(&2));
  assert_eq!(tester.get(2), None);
}

#[test]
fn test_swap() {
  let mut tester = GenericArrayDeque::<_, U5>::new();
  tester.push_back(1);
  tester.push_back(2);
  tester.push_back(3);

  assert_eq!(tester, [1, 2, 3]);

  tester.swap(0, 0);
  assert_eq!(tester, [1, 2, 3]);
  tester.swap(0, 1);
  assert_eq!(tester, [2, 1, 3]);
  tester.swap(2, 1);
  assert_eq!(tester, [2, 3, 1]);
  tester.swap(1, 2);
  assert_eq!(tester, [2, 1, 3]);
  tester.swap(0, 2);
  assert_eq!(tester, [3, 1, 2]);
  tester.swap(2, 2);
  assert_eq!(tester, [3, 1, 2]);
}

#[test]
#[should_panic = "assertion failed: j < self.len()"]
fn test_swap_panic() {
  let mut tester = GenericArrayDeque::<_, U5>::new();
  tester.push_back(1);
  tester.push_back(2);
  tester.push_back(3);
  tester.swap(2, 3);
}

#[test]
fn test_contains() {
  let mut tester = GenericArrayDeque::<_, U5>::new();
  tester.push_back(1);
  tester.push_back(2);
  tester.push_back(3);

  assert!(tester.contains(&1));
  assert!(tester.contains(&3));
  assert!(!tester.contains(&0));
  assert!(!tester.contains(&4));
  tester.remove(0);
  assert!(!tester.contains(&1));
  assert!(tester.contains(&2));
  assert!(tester.contains(&3));
}

#[test]
fn test_rotate_left_right() {
  let mut tester: GenericArrayDeque<_, U10> = GenericArrayDeque::try_from_iter(1..=10).unwrap();
  assert_eq!(tester.len(), 10);

  tester.rotate_left(0);
  assert_eq!(tester, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

  tester.rotate_right(0);
  assert_eq!(tester, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

  tester.rotate_left(3);
  assert_eq!(tester, [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]);

  tester.rotate_right(5);
  assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);

  tester.rotate_left(tester.len());
  assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);

  tester.rotate_right(tester.len());
  assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);

  tester.rotate_left(1);
  assert_eq!(tester, [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

#[test]
#[should_panic = "assertion failed: n <= self.len()"]
fn test_rotate_left_panic() {
  let mut tester: GenericArrayDeque<_, U12> = GenericArrayDeque::try_from_iter(1..=10).unwrap();
  tester.rotate_left(tester.len() + 1);
}

#[test]
#[should_panic = "assertion failed: n <= self.len()"]
fn test_rotate_right_panic() {
  let mut tester: GenericArrayDeque<_, U12> = GenericArrayDeque::try_from_iter(1..=10).unwrap();
  tester.rotate_right(tester.len() + 1);
}

#[test]
fn test_binary_search() {
  // If the given VecDeque is not sorted, the returned result is unspecified and meaningless,
  // as this method performs a binary search.

  let tester: GenericArrayDeque<_, U12> =
    GenericArrayDeque::try_from_iter([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]).unwrap();

  assert_eq!(tester.binary_search(&0), Ok(0));
  assert_eq!(tester.binary_search(&5), Ok(5));
  assert_eq!(tester.binary_search(&55), Ok(10));
  assert_eq!(tester.binary_search(&4), Err(5));
  assert_eq!(tester.binary_search(&-1), Err(0));
  assert!(matches!(tester.binary_search(&1), Ok(1..=2)));

  let tester: GenericArrayDeque<_, U15> =
    GenericArrayDeque::try_from_iter([1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]).unwrap();
  assert_eq!(tester.binary_search(&1), Ok(0));
  assert!(matches!(tester.binary_search(&2), Ok(1..=4)));
  assert!(matches!(tester.binary_search(&3), Ok(5..=13)));
  assert_eq!(tester.binary_search(&-2), Err(0));
  assert_eq!(tester.binary_search(&0), Err(0));
  assert_eq!(tester.binary_search(&4), Err(14));
  assert_eq!(tester.binary_search(&5), Err(14));
}

#[test]
fn test_binary_search_by() {
  // If the given VecDeque is not sorted, the returned result is unspecified and meaningless,
  // as this method performs a binary search.

  let tester: GenericArrayDeque<_, U12> =
    GenericArrayDeque::try_from_iter([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]).unwrap();

  assert_eq!(tester.binary_search_by(|x| x.cmp(&0)), Ok(0));
  assert_eq!(tester.binary_search_by(|x| x.cmp(&5)), Ok(5));
  assert_eq!(tester.binary_search_by(|x| x.cmp(&55)), Ok(10));
  assert_eq!(tester.binary_search_by(|x| x.cmp(&4)), Err(5));
  assert_eq!(tester.binary_search_by(|x| x.cmp(&-1)), Err(0));
  assert!(matches!(tester.binary_search_by(|x| x.cmp(&1)), Ok(1..=2)));
}

#[test]
fn test_binary_search_key() {
  // If the given VecDeque is not sorted, the returned result is unspecified and meaningless,
  // as this method performs a binary search.

  let tester: GenericArrayDeque<_, U15> = GenericArrayDeque::try_from_iter([
    (-1, 0),
    (2, 10),
    (6, 5),
    (7, 1),
    (8, 10),
    (10, 2),
    (20, 3),
    (24, 5),
    (25, 18),
    (28, 13),
    (31, 21),
    (32, 4),
    (54, 25),
  ])
  .unwrap();

  assert_eq!(tester.binary_search_by_key(&-1, |&(a, _b)| a), Ok(0));
  assert_eq!(tester.binary_search_by_key(&8, |&(a, _b)| a), Ok(4));
  assert_eq!(tester.binary_search_by_key(&25, |&(a, _b)| a), Ok(8));
  assert_eq!(tester.binary_search_by_key(&54, |&(a, _b)| a), Ok(12));
  assert_eq!(tester.binary_search_by_key(&-2, |&(a, _b)| a), Err(0));
  assert_eq!(tester.binary_search_by_key(&1, |&(a, _b)| a), Err(1));
  assert_eq!(tester.binary_search_by_key(&4, |&(a, _b)| a), Err(2));
  assert_eq!(tester.binary_search_by_key(&13, |&(a, _b)| a), Err(6));
  assert_eq!(tester.binary_search_by_key(&55, |&(a, _b)| a), Err(13));
  assert_eq!(tester.binary_search_by_key(&100, |&(a, _b)| a), Err(13));

  let tester: GenericArrayDeque<_, U15> = GenericArrayDeque::try_from_iter([
    (0, 0),
    (2, 1),
    (6, 1),
    (5, 1),
    (3, 1),
    (1, 2),
    (2, 3),
    (4, 5),
    (5, 8),
    (8, 13),
    (1, 21),
    (2, 34),
    (4, 55),
  ])
  .unwrap();

  assert_eq!(tester.binary_search_by_key(&0, |&(_a, b)| b), Ok(0));
  assert!(matches!(
    tester.binary_search_by_key(&1, |&(_a, b)| b),
    Ok(1..=4)
  ));
  assert_eq!(tester.binary_search_by_key(&8, |&(_a, b)| b), Ok(8));
  assert_eq!(tester.binary_search_by_key(&13, |&(_a, b)| b), Ok(9));
  assert_eq!(tester.binary_search_by_key(&55, |&(_a, b)| b), Ok(12));
  assert_eq!(tester.binary_search_by_key(&-1, |&(_a, b)| b), Err(0));
  assert_eq!(tester.binary_search_by_key(&4, |&(_a, b)| b), Err(7));
  assert_eq!(tester.binary_search_by_key(&56, |&(_a, b)| b), Err(13));
  assert_eq!(tester.binary_search_by_key(&100, |&(_a, b)| b), Err(13));
}

#[test]
fn make_contiguous_big_head() {
  let mut tester = GenericArrayDeque::<_, U15>::new();

  for i in 0..3 {
    tester.push_back(i);
  }

  for i in 3..10 {
    tester.push_front(i);
  }

  // 012......9876543
  assert_eq!(tester.capacity(), 15);
  assert_eq!(
    (&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]),
    tester.as_slices()
  );

  let expected_start = tester.as_slices().1.len();
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]),
    tester.as_slices()
  );
}

#[test]
fn make_contiguous_big_tail() {
  let mut tester = GenericArrayDeque::<_, U15>::new();

  for i in 0..8 {
    tester.push_back(i);
  }

  for i in 8..10 {
    tester.push_front(i);
  }

  // 01234567......98
  let expected_start = 0;
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]),
    tester.as_slices()
  );
}

#[test]
fn make_contiguous_small_free() {
  let mut tester = GenericArrayDeque::<_, U16>::new();

  for i in b'A'..b'I' {
    tester.push_back(i as char);
  }

  for i in b'I'..b'N' {
    tester.push_front(i as char);
  }

  assert_eq!(
    tester,
    ['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
  );

  // ABCDEFGH...MLKJI
  let expected_start = 0;
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (
      &['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_],
      &[] as &[_]
    ),
    tester.as_slices()
  );

  tester.clear();
  for i in b'I'..b'N' {
    tester.push_back(i as char);
  }

  for i in b'A'..b'I' {
    tester.push_front(i as char);
  }

  // IJKLM...HGFEDCBA
  let expected_start = 3;
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (
      &['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_],
      &[] as &[_]
    ),
    tester.as_slices()
  );
}

#[test]
fn make_contiguous_head_to_end() {
  let mut tester = GenericArrayDeque::<_, U16>::new();

  for i in b'A'..b'L' {
    tester.push_back(i as char);
  }

  for i in b'L'..b'Q' {
    tester.push_front(i as char);
  }

  assert_eq!(
    tester,
    ['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
  );

  // ABCDEFGHIJKPONML
  let expected_start = 0;
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (
      &['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'] as &[_],
      &[] as &[_]
    ),
    tester.as_slices()
  );

  tester.clear();
  for i in b'L'..b'Q' {
    tester.push_back(i as char);
  }

  for i in b'A'..b'L' {
    tester.push_front(i as char);
  }

  // LMNOPKJIHGFEDCBA
  let expected_start = 0;
  tester.make_contiguous();
  assert_eq!(tester.head, expected_start);
  assert_eq!(
    (
      &['K', 'J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'L', 'M', 'N', 'O', 'P'] as &[_],
      &[] as &[_]
    ),
    tester.as_slices()
  );
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn make_contiguous_head_to_end_2() {
  // Another test case for #79808, taken from #80293.

  let mut dq = GenericArrayDeque::<_, U6>::try_from_iter(0..6).unwrap();
  dq.pop_front();
  dq.pop_front();
  dq.push_back(6);
  dq.push_back(7);
  dq.push_back(8);
  dq.make_contiguous();
  let collected: Vec<_> = dq.iter().copied().collect();
  assert_eq!(dq.as_slices(), (&collected[..], &[] as &[_]));
}

#[test]
fn test_remove() {
  // This test checks that every single combination of tail position, length, and
  // removal position is tested. Capacity 15 should be large enough to cover every case.

  let mut tester = GenericArrayDeque::<_, U15>::new();
  // can't guarantee we got 15, so have to get what we got.
  // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
  // this test isn't covering what it wants to
  let cap = tester.capacity();

  // len is the length *after* removal
  let minlen = if cfg!(miri) { cap - 2 } else { 0 }; // Miri is too slow
  for len in minlen..cap - 1 {
    // 0, 1, 2, .., len - 1
    let expected = GenericArrayDeque::<_, U15>::try_from_iter((0..).take(len)).unwrap();
    for head_pos in 0..cap {
      for to_remove in 0..=len {
        tester.head = head_pos;
        tester.len = 0;
        for i in 0..len {
          if i == to_remove {
            tester.push_back(1234);
          }
          tester.push_back(i);
        }
        if to_remove == len {
          tester.push_back(1234);
        }
        tester.remove(to_remove);
        assert!(tester.head <= tester.capacity());
        assert!(tester.len <= tester.capacity());
        assert_eq!(tester, expected);
      }
    }
  }
}

#[test]
fn test_range() {
  let mut tester: GenericArrayDeque<_, U7> = GenericArrayDeque::new();

  let cap = tester.capacity();
  let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
  for len in minlen..=cap {
    for head in 0..=cap {
      for start in 0..=len {
        for end in start..=len {
          tester.head = head;
          tester.len = 0;
          for i in 0..len {
            tester.push_back(i);
          }

          // Check that we iterate over the correct values
          let range: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(tester.range(start..end).copied()).unwrap();
          let expected: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(start..end).unwrap();
          assert_eq!(range, expected);
        }
      }
    }
  }
}

#[test]
fn test_range_mut() {
  let mut tester: GenericArrayDeque<_, U7> = GenericArrayDeque::new();

  let cap = tester.capacity();
  for len in 0..=cap {
    for head in 0..=cap {
      for start in 0..=len {
        for end in start..=len {
          tester.head = head;
          tester.len = 0;
          for i in 0..len {
            tester.push_back(i);
          }

          let head_was = tester.head;
          let len_was = tester.len;

          // Check that we iterate over the correct values
          let range: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(tester.range_mut(start..end).map(|v| *v)).unwrap();
          let expected: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(start..end).unwrap();
          assert_eq!(range, expected);

          // We shouldn't have changed the capacity or made the
          // head or tail out of bounds
          assert_eq!(tester.capacity(), cap);
          assert_eq!(tester.head, head_was);
          assert_eq!(tester.len, len_was);
        }
      }
    }
  }
}

#[test]
fn test_drain() {
  let mut tester: GenericArrayDeque<_, U7> = GenericArrayDeque::new();

  let cap = tester.capacity();
  for len in 0..=cap {
    for head in 0..cap {
      for drain_start in 0..=len {
        for drain_end in drain_start..=len {
          tester.head = head;
          tester.len = 0;
          for i in 0..len {
            tester.push_back(i);
          }

          // Check that we drain the correct values
          let drained: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(tester.drain(drain_start..drain_end)).unwrap();
          let drained_expected: GenericArrayDeque<_, U7> =
            GenericArrayDeque::try_from_iter(drain_start..drain_end).unwrap();
          assert_eq!(drained, drained_expected);

          // We shouldn't have changed the capacity or made the
          // head or tail out of bounds
          assert_eq!(tester.capacity(), cap);
          assert!(tester.head <= tester.capacity());
          assert!(tester.len <= tester.capacity());

          // We should see the correct values in the GenericArrayDeque
          let expected: GenericArrayDeque<_, U14> =
            GenericArrayDeque::try_from_iter((0..drain_start).chain(drain_end..len)).unwrap();
          assert_eq!(expected, tester);
        }
      }
    }
  }
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn issue_108453() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<_, U10>::new();

  deque.push_back(1u8);
  deque.push_back(2);
  deque.push_back(3);

  deque.push_front(10);
  deque.push_front(9);

  assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]);
}

#[test]
fn test_split_off() {
  // This test checks that every single combination of tail position, length, and
  // split position is tested. Capacity 15 should be large enough to cover every case.

  let mut tester = GenericArrayDeque::<_, U15>::new();
  // can't guarantee we got 15, so have to get what we got.
  // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
  // this test isn't covering what it wants to
  let cap = tester.capacity();

  // len is the length *before* splitting
  let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
  for len in minlen..cap {
    // index to split at
    for at in 0..=len {
      // 0, 1, 2, .., at - 1 (may be empty)
      let expected_self = GenericArrayDeque::<_, U15>::try_from_iter((0..).take(at)).unwrap();
      // at, at + 1, .., len - 1 (may be empty)
      let expected_other =
        GenericArrayDeque::<_, U15>::try_from_iter((at..).take(len - at)).unwrap();

      for head_pos in 0..cap {
        tester.head = head_pos;
        tester.len = 0;
        for i in 0..len {
          tester.push_back(i);
        }
        let result = tester.split_off(at);
        assert!(tester.head <= tester.capacity());
        assert!(tester.len <= tester.capacity());
        assert!(result.head <= result.capacity());
        assert!(result.len <= result.capacity());
        assert_eq!(tester, expected_self);
        assert_eq!(result, expected_other);
      }
    }
  }
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn test_from_vec() {
  use std::vec::Vec;

  for cap in 0..35 {
    for len in 0..=cap {
      let mut vec = Vec::with_capacity(cap);
      vec.extend(0..len);

      let vd = GenericArrayDeque::<_, U40>::try_from_vec(vec.clone()).unwrap();
      assert_eq!(vd.len(), vec.len());
      assert!(vd.into_iter().eq(vec));
    }
  }
}

#[test]
fn test_extend_basic() {
  test_extend_impl(false);
}

// Regression: `ExactSizeIterator::len()` is a safe trait method — a
// misbehaving impl can advertise a smaller length than it actually yields.
// The bounded-extend paths used to trust that length and write past
// capacity, corrupting `self.len` into UB territory.
#[derive(Debug)]
struct LyingExactSize {
  remaining: usize,
  advertised: usize,
}

impl Iterator for LyingExactSize {
  type Item = i32;

  fn next(&mut self) -> Option<i32> {
    if self.remaining == 0 {
      None
    } else {
      self.remaining -= 1;
      Some(42)
    }
  }
}

impl ExactSizeIterator for LyingExactSize {
  fn len(&self) -> usize {
    self.advertised
  }
}

#[test]
fn try_extend_from_exact_iter_bounds_by_capacity() {
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  assert!(deque
    .try_extend_from_exact_iter(LyingExactSize {
      remaining: 8,
      advertised: 0,
    })
    .is_none());
  assert!(deque.len() <= deque.capacity());
  assert_eq!(deque.len(), 4);
}

#[test]
fn try_from_exact_iter_bounds_by_capacity() {
  let deque = GenericArrayDeque::<i32, U4>::try_from_exact_iter(LyingExactSize {
    remaining: 8,
    advertised: 0,
  })
  .unwrap();
  assert!(deque.len() <= deque.capacity());
  assert_eq!(deque.len(), 4);
}

#[test]
fn test_extend_trusted_len() {
  test_extend_impl(true);
}

fn test_extend_impl(trusted_len: bool) {
  struct VecDequeTester {
    test: GenericArrayDeque<usize, Sum<U8192, U4>>,
    expected: GenericArrayDeque<usize, Sum<U8192, U4>>,
    trusted_len: bool,
  }

  impl VecDequeTester {
    fn new(trusted_len: bool) -> Self {
      Self {
        test: GenericArrayDeque::new(),
        expected: GenericArrayDeque::new(),
        trusted_len,
      }
    }

    fn test_extend<I>(&mut self, iter: I)
    where
      I: Iterator<Item = usize> + ExactSizeIterator + Clone,
    {
      struct BasicIterator<I>(I);
      impl<I> Iterator for BasicIterator<I>
      where
        I: Iterator<Item = usize>,
      {
        type Item = usize;

        fn next(&mut self) -> Option<Self::Item> {
          self.0.next()
        }
      }

      if self.trusted_len {
        self.test.try_extend_from_exact_iter(iter.clone());
      } else {
        self.test.try_extend_from_iter(BasicIterator(iter.clone()));
      }

      for item in iter {
        self.expected.push_back(item);
      }

      assert_eq!(self.test, self.expected);
    }

    fn drain<R: RangeBounds<usize> + Clone>(&mut self, range: R) {
      self.test.drain(range.clone());
      self.expected.drain(range);

      assert_eq!(self.test, self.expected);
    }

    fn clear(&mut self) {
      self.test.clear();
      self.expected.clear();
    }

    fn remaining_capacity(&self) -> usize {
      self.test.capacity() - self.test.len()
    }
  }

  let mut tester = VecDequeTester::new(trusted_len);

  // Initial capacity
  tester.test_extend(0..tester.remaining_capacity());

  // Grow
  tester.test_extend(1024..2048);

  // Wrap around
  tester.drain(..128);

  tester.test_extend(0..tester.remaining_capacity());

  // Continue
  tester.drain(256..);
  tester.test_extend(4096..8196);

  tester.clear();

  // Start again
  tester.test_extend(0..32);
}

#[test]
fn test_from_array() {
  fn test<N: ArrayLength>() {
    let mut array: GenericArray<usize, N> = GenericArray::default();

    for i in 0..N::USIZE {
      array[i] = i;
    }

    let deq: GenericArrayDeque<_, N> = array.into();

    for i in 0..N::USIZE {
      assert_eq!(deq[i], i);
    }

    assert_eq!(deq.len(), N::USIZE);
  }
  test::<U0>();
  test::<U1>();
  test::<U2>();
  test::<U32>();
  test::<U35>();
}

#[test]
#[cfg(any(feature = "alloc", feature = "std"))]
fn test_vec_from_vecdeque() {
  fn create_vec_and_test_convert<CAP: ArrayLength>(offset: usize, len: usize) {
    let mut vd = GenericArrayDeque::<_, CAP>::new();
    for _ in 0..offset {
      vd.push_back(0);
      vd.pop_front();
    }
    let _ = vd.try_extend_from_iter(0..len);

    let vec: Vec<_> = Vec::from(vd.clone());
    assert_eq!(vec.len(), vd.len());
    assert!(vec.into_iter().eq(vd));
  }

  // Miri is too slow
  let max_pwr = if cfg!(miri) { 5 } else { 7 };

  for cap_pwr in 0..max_pwr {
    // Make capacity as a (2^x)-1, so that the ring size is 2^x
    let cap = (2i32.pow(cap_pwr) - 1) as usize;

    // In these cases there is enough free space to solve it with copies
    for len in 0..((cap + 1) / 2) {
      // Test contiguous cases
      for offset in 0..(cap - len) {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }

      // Test cases where block at end of buffer is bigger than block at start
      for offset in (cap - len)..(cap - (len / 2)) {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }

      // Test cases where block at start of buffer is bigger than block at end
      for offset in (cap - (len / 2))..cap {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }
    }

    // Now there's not (necessarily) space to straighten the ring with simple copies,
    // the ring will use swapping when:
    // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
    //  right block size  >   free space    &&      left block size       >    free space
    for len in ((cap + 1) / 2)..cap {
      // Test contiguous cases
      for offset in 0..(cap - len) {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }

      // Test cases where block at end of buffer is bigger than block at start
      for offset in (cap - len)..(cap - (len / 2)) {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }

      // Test cases where block at start of buffer is bigger than block at end
      for offset in (cap - (len / 2))..cap {
        if cfg!(miri) {
          create_vec_and_test_convert::<U5>(offset, len);
        } else {
          create_vec_and_test_convert::<U7>(offset, len);
        }
      }
    }
  }
}

#[test]
#[cfg(any(feature = "alloc", feature = "std"))]
fn test_clone_from() {
  let m = vec![1; 8];
  let n = vec![2; 12];
  let limit = if cfg!(miri) { 4 } else { 8 }; // Miri is too slow
  for pfv in 0..limit {
    for pfu in 0..limit {
      for longer in 0..2 {
        let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
        let mut v = GenericArrayDeque::<_, U12>::try_from(vr.clone()).unwrap();
        for _ in 0..pfv {
          v.push_front(1);
        }
        let mut u = GenericArrayDeque::<_, U12>::try_from(ur.clone()).unwrap();
        for _ in 0..pfu {
          u.push_front(2);
        }
        v.clone_from(&u);
        assert_eq!(&v, &u);
      }
    }
  }
}

#[rustversion::since(1.73)]
#[cfg(feature = "std")]
#[test]
fn test_vec_deque_truncate_drop() {
  struct_with_counted_drop!(Elem, DROPS);

  const LEN: usize = 5;
  for push_front in 0..=LEN {
    let mut tester = GenericArrayDeque::<Elem, U5>::new();
    for index in 0..LEN {
      if index < push_front {
        tester.push_front(Elem);
      } else {
        tester.push_back(Elem);
      }
    }
    assert_eq!(DROPS.get(), 0);
    tester.truncate(3);
    assert_eq!(DROPS.get(), 2);
    tester.truncate(0);
    assert_eq!(DROPS.get(), 5);
    DROPS.set(0);
  }
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn issue_53529() {
  use std::boxed::Box;

  let mut dst = GenericArrayDeque::<_, U4>::new();
  dst.push_front(Box::new(1));
  dst.push_front(Box::new(2));
  assert_eq!(*dst.pop_back().unwrap(), 1);

  let mut src = GenericArrayDeque::<_, U4>::new();
  src.push_front(Box::new(2));
  dst.append(&mut src);
  for a in dst {
    assert_eq!(*a, 2);
  }
}

#[test]
fn issue_80303() {
  use core::{iter, num::Wrapping};

  // This is a valid, albeit rather bad hash function implementation.
  struct SimpleHasher(Wrapping<u64>);

  impl Hasher for SimpleHasher {
    fn finish(&self) -> u64 {
      self.0 .0
    }

    fn write(&mut self, bytes: &[u8]) {
      // This particular implementation hashes value 24 in addition to bytes.
      // Such an implementation is valid as Hasher only guarantees equivalence
      // for the exact same set of calls to its methods.
      for &v in iter::once(&24).chain(bytes) {
        self.0 = Wrapping(31) * self.0 + Wrapping(u64::from(v));
      }
    }
  }

  fn hash_code(value: impl Hash) -> u64 {
    let mut hasher = SimpleHasher(Wrapping(1));
    value.hash(&mut hasher);
    hasher.finish()
  }

  // This creates two deques for which values returned by as_slices
  // method differ.
  let vda = GenericArrayDeque::<u8, U10>::try_from_exact_iter(0..10).unwrap();
  let mut vdb = GenericArrayDeque::<u8, U10>::new();
  assert!(vdb.try_extend_from_iter(5..10).is_none());
  (0..5).rev().for_each(|elem| {
    assert!(vdb.push_front(elem).is_none());
  });
  assert_ne!(vda.as_slices(), vdb.as_slices());
  assert_eq!(vda, vdb);
  assert_eq!(hash_code(vda), hash_code(vdb));
}

#[cfg(all(any(feature = "alloc", feature = "std"), feature = "unstable"))]
#[test]
fn extract_if_test() {
  let mut m = GenericArrayDeque::<u32, U24>::try_from_exact_iter([1, 2, 3, 4, 5, 6]).unwrap();
  let deleted = m.extract_if(.., |v| *v < 4).collect::<Vec<_>>();

  assert_eq!(deleted, &[1, 2, 3]);
  assert_eq!(m, &[4, 5, 6]);
}

#[cfg(all(any(feature = "alloc", feature = "std"), feature = "unstable"))]
#[test]
fn drain_to_empty_test() {
  let mut m = GenericArrayDeque::<u32, U24>::try_from_exact_iter([1, 2, 3, 4, 5, 6]).unwrap();
  let deleted = m.extract_if(.., |_| true).collect::<Vec<u32>>();

  assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
  assert_eq!(m, &[]);
}

#[cfg(feature = "unstable")]
#[test]
fn extract_if_empty() {
  let mut list = GenericArrayDeque::<usize, U4>::new();

  {
    let mut iter = list.extract_if(.., |_| true);
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.size_hint(), (0, Some(0)));
  }

  assert_eq!(list.len(), 0);
  #[cfg(any(feature = "alloc", feature = "std"))]
  assert_eq!(list, vec![]);
}

#[cfg(feature = "unstable")]
#[test]
fn extract_if_zst() {
  let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([(), (), (), (), ()]).unwrap();
  let initial_len = list.len();
  let mut count = 0;

  {
    let mut iter = list.extract_if(.., |_| true);
    assert_eq!(iter.size_hint(), (0, Some(initial_len)));
    while let Some(_) = iter.next() {
      count += 1;
      assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
    }
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.size_hint(), (0, Some(0)));
  }

  assert_eq!(count, initial_len);
  assert_eq!(list.len(), 0);

  #[cfg(any(feature = "alloc", feature = "std"))]
  assert_eq!(list, vec![]);
}

#[cfg(feature = "unstable")]
#[test]
fn extract_if_false() {
  let mut list =
    GenericArrayDeque::<_, U15>::try_from_exact_iter([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).unwrap();

  let initial_len = list.len();
  let mut count = 0;

  {
    let mut iter = list.extract_if(.., |_| false);
    assert_eq!(iter.size_hint(), (0, Some(initial_len)));
    for _ in iter.by_ref() {
      count += 1;
    }
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.size_hint(), (0, Some(0)));
  }

  assert_eq!(count, 0);
  assert_eq!(list.len(), initial_len);
  #[cfg(any(feature = "alloc", feature = "std"))]
  assert_eq!(list, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
}

#[cfg(feature = "unstable")]
#[test]
fn extract_if_true() {
  let mut list =
    GenericArrayDeque::<_, U15>::try_from_exact_iter([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).unwrap();

  let initial_len = list.len();
  let mut count = 0;

  {
    let mut iter = list.extract_if(.., |_| true);
    assert_eq!(iter.size_hint(), (0, Some(initial_len)));
    while let Some(_) = iter.next() {
      count += 1;
      assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
    }
    assert_eq!(iter.size_hint(), (0, Some(0)));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.size_hint(), (0, Some(0)));
  }

  assert_eq!(count, initial_len);
  assert_eq!(list.len(), 0);
  #[cfg(any(feature = "alloc", feature = "std"))]
  assert_eq!(list, vec![]);
}

#[cfg(all(any(feature = "alloc", feature = "std"), feature = "unstable"))]
#[test]
fn extract_if_non_contiguous() {
  use std::{vec, vec::Vec};

  let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([
    1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
  ])
  .unwrap();
  list.rotate_left(3);

  assert!(!list.is_contiguous());
  assert_eq!(
    list,
    [6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39, 1, 2, 4]
  );

  let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
  assert_eq!(removed.len(), 10);
  assert_eq!(removed, vec![6, 18, 20, 22, 24, 26, 34, 36, 2, 4]);

  assert_eq!(list.len(), 14);
  assert_eq!(
    list,
    vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39, 1]
  );
}

#[cfg(all(any(feature = "alloc", feature = "std"), feature = "unstable"))]
#[test]
fn extract_if_complex() {
  use std::{vec, vec::Vec};

  {
    //                [+xxx++++++xxxxx++++x+x++]
    let mut list = GenericArrayDeque::<_, U32>::try_from_exact_iter([
      1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
    ])
    .unwrap();

    let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
    assert_eq!(removed.len(), 10);
    assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);

    assert_eq!(list.len(), 14);
    assert_eq!(
      list,
      vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
    );
  }

  {
    // [xxx++++++xxxxx++++x+x++]
    let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([
      2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
    ])
    .unwrap();

    let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
    assert_eq!(removed.len(), 10);
    assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);

    assert_eq!(list.len(), 13);
    assert_eq!(list, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
  }

  {
    // [xxx++++++xxxxx++++x+x]
    let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([
      2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36,
    ])
    .unwrap();

    let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
    assert_eq!(removed.len(), 10);
    assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);

    assert_eq!(list.len(), 11);
    assert_eq!(list, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
  }

  {
    // [xxxxxxxxxx+++++++++++]
    let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([
      2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
    ])
    .unwrap();

    let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
    assert_eq!(removed.len(), 10);
    assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);

    assert_eq!(list.len(), 10);
    assert_eq!(list, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
  }

  {
    // [+++++++++++xxxxxxxxxx]
    let mut list = GenericArrayDeque::<_, U24>::try_from_exact_iter([
      1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
    ])
    .unwrap();

    let removed = list.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
    assert_eq!(removed.len(), 10);
    assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);

    assert_eq!(list.len(), 10);
    assert_eq!(list, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
  }
}

#[cfg(all(feature = "std", feature = "unstable"))]
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn extract_if_drop_panic_leak() {
  use core::sync::atomic::{AtomicUsize, Ordering::SeqCst};
  use std::panic::{catch_unwind, AssertUnwindSafe};

  /// A blueprint for crash test dummy instances that monitor particular events.
  /// Some instances may be configured to panic at some point.
  /// Events are `clone`, `drop` or some anonymous `query`.
  ///
  /// Crash test dummies are identified and ordered by an id, so they can be used
  /// as keys in a BTreeMap.
  #[derive(Debug)]
  pub(crate) struct CrashTestDummy {
    pub id: usize,
    cloned: AtomicUsize,
    dropped: AtomicUsize,
    queried: AtomicUsize,
  }

  impl CrashTestDummy {
    /// Creates a crash test dummy design. The `id` determines order and equality of instances.
    pub(crate) fn new(id: usize) -> CrashTestDummy {
      CrashTestDummy {
        id,
        cloned: AtomicUsize::new(0),
        dropped: AtomicUsize::new(0),
        queried: AtomicUsize::new(0),
      }
    }

    /// Creates an instance of a crash test dummy that records what events it experiences
    /// and optionally panics.
    pub(crate) fn spawn(&self, panic: Panic) -> Instance<'_> {
      Instance {
        origin: self,
        panic,
      }
    }

    /// Returns how many times instances of the dummy have been cloned.
    #[allow(unused)]
    pub(crate) fn cloned(&self) -> usize {
      self.cloned.load(SeqCst)
    }

    /// Returns how many times instances of the dummy have been dropped.
    pub(crate) fn dropped(&self) -> usize {
      self.dropped.load(SeqCst)
    }

    /// Returns how many times instances of the dummy have had their `query` member invoked.
    #[allow(unused)]
    pub(crate) fn queried(&self) -> usize {
      self.queried.load(SeqCst)
    }
  }
  #[derive(Debug)]
  pub(crate) struct Instance<'a> {
    origin: &'a CrashTestDummy,
    panic: Panic,
  }

  #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  pub(crate) enum Panic {
    Never,
    InClone,
    InDrop,
    InQuery,
  }

  impl Instance<'_> {
    pub(crate) fn id(&self) -> usize {
      self.origin.id
    }

    /// Some anonymous query, the result of which is already given.
    #[allow(unused)]
    pub(crate) fn query<R>(&self, result: R) -> R {
      self.origin.queried.fetch_add(1, SeqCst);
      if self.panic == Panic::InQuery {
        panic!("panic in `query`");
      }
      result
    }
  }

  impl Clone for Instance<'_> {
    fn clone(&self) -> Self {
      self.origin.cloned.fetch_add(1, SeqCst);
      if self.panic == Panic::InClone {
        panic!("panic in `clone`");
      }
      Self {
        origin: self.origin,
        panic: Panic::Never,
      }
    }
  }

  impl Drop for Instance<'_> {
    fn drop(&mut self) {
      self.origin.dropped.fetch_add(1, SeqCst);
      if self.panic == Panic::InDrop {
        panic!("panic in `drop`");
      }
    }
  }

  #[allow(clippy::non_canonical_partial_ord_impl)]
  impl PartialOrd for Instance<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
      self.id().partial_cmp(&other.id())
    }
  }

  impl core::cmp::Ord for Instance<'_> {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
      self.id().cmp(&other.id())
    }
  }

  impl PartialEq for Instance<'_> {
    fn eq(&self, other: &Self) -> bool {
      self.id().eq(&other.id())
    }
  }

  impl core::cmp::Eq for Instance<'_> {}

  let d0 = CrashTestDummy::new(0);
  let d1 = CrashTestDummy::new(1);
  let d2 = CrashTestDummy::new(2);
  let d3 = CrashTestDummy::new(3);
  let d4 = CrashTestDummy::new(4);
  let d5 = CrashTestDummy::new(5);
  let d6 = CrashTestDummy::new(6);
  let d7 = CrashTestDummy::new(7);
  let mut q = GenericArrayDeque::<_, U8>::new();
  q.push_back(d3.spawn(Panic::Never));
  q.push_back(d4.spawn(Panic::Never));
  q.push_back(d5.spawn(Panic::Never));
  q.push_back(d6.spawn(Panic::Never));
  q.push_back(d7.spawn(Panic::Never));
  q.push_front(d2.spawn(Panic::Never));
  q.push_front(d1.spawn(Panic::InDrop));
  q.push_front(d0.spawn(Panic::Never));

  catch_unwind(AssertUnwindSafe(|| {
    q.extract_if(.., |_| true).for_each(drop)
  }))
  .unwrap_err();

  assert_eq!(d0.dropped(), 1);
  assert_eq!(d1.dropped(), 1);
  assert_eq!(d2.dropped(), 0);
  assert_eq!(d3.dropped(), 0);
  assert_eq!(d4.dropped(), 0);
  assert_eq!(d5.dropped(), 0);
  assert_eq!(d6.dropped(), 0);
  assert_eq!(d7.dropped(), 0);
  drop(q);
  assert_eq!(d2.dropped(), 1);
  assert_eq!(d3.dropped(), 1);
  assert_eq!(d4.dropped(), 1);
  assert_eq!(d5.dropped(), 1);
  assert_eq!(d6.dropped(), 1);
  assert_eq!(d7.dropped(), 1);
}

#[rustversion::since(1.73)]
#[cfg(all(feature = "std", feature = "unstable"))]
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn extract_if_pred_panic_leak() {
  use std::panic::{catch_unwind, AssertUnwindSafe};
  struct_with_counted_drop!(D(u32), DROPS);

  let mut q = GenericArrayDeque::<D, U8>::new();
  q.push_back(D(3));
  q.push_back(D(4));
  q.push_back(D(5));
  q.push_back(D(6));
  q.push_back(D(7));
  q.push_front(D(2));
  q.push_front(D(1));
  q.push_front(D(0));

  _ = catch_unwind(AssertUnwindSafe(|| {
    q.extract_if(.., |item| if item.0 >= 2 { panic!() } else { true })
      .for_each(drop)
  }));

  assert_eq!(DROPS.get(), 2); // 0 and 1
  assert_eq!(q.len(), 6);
}

// ---------------------------------------------------------------------------
// Coverage fillers: hit branches that nominal tests miss.
// ---------------------------------------------------------------------------

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn debug_impl_renders_elements_in_logical_order() {
  let mut deque = GenericArrayDeque::<i32, U8>::new();
  deque.push_back(2);
  deque.push_back(3);
  deque.push_front(1);
  assert_eq!(std::format!("{:?}", deque), "[1, 2, 3]");
}

#[test]
fn default_returns_empty_deque() {
  let deque: GenericArrayDeque<i32, U4> = Default::default();
  assert!(deque.is_empty());
  assert_eq!(deque.capacity(), 4);
}

#[test]
fn partial_eq_rejects_different_lengths() {
  let a = GenericArrayDeque::<i32, U4>::try_from_array([1, 2]).unwrap();
  let b = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  assert!(a != b);
  assert!(b != a);
}

#[test]
fn partial_eq_across_ring_splits() {
  // Non-contiguous `self` with fewer front items than `other`.
  let mut a = GenericArrayDeque::<i32, U6>::new();
  for v in 0..4 {
    a.push_back(v);
  }
  a.pop_front();
  a.push_back(4);
  // a: front=[1,2,3], back=[4]

  let b = GenericArrayDeque::<i32, U6>::try_from_array([1, 2, 3, 4]).unwrap();
  assert!(a == b);
  assert!(b == a);

  // Non-matching element somewhere in the middle.
  let c = GenericArrayDeque::<i32, U6>::try_from_array([1, 2, 9, 4]).unwrap();
  assert!(a != c);
}

#[test]
fn ord_and_partial_ord_use_lexicographic_iter_order() {
  use core::cmp::Ordering;
  let a = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  let b = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 4]).unwrap();
  assert!(a < b);
  assert_eq!(a.cmp(&b), Ordering::Less);
  assert_eq!(a.partial_cmp(&b), Some(Ordering::Less));
  assert_eq!(a.cmp(&a), Ordering::Equal);
}

#[cfg(feature = "std")]
#[test]
fn hash_is_stable_across_layouts() {
  use core::hash::{Hash, Hasher};
  use std::collections::hash_map::DefaultHasher;

  let contiguous = GenericArrayDeque::<i32, U6>::try_from_array([1, 2, 3, 4]).unwrap();
  let mut wrapped = GenericArrayDeque::<i32, U6>::new();
  for v in 0..4 {
    wrapped.push_back(v);
  }
  wrapped.pop_front();
  wrapped.push_back(4);
  // wrapped == [1, 2, 3, 4] logically, but physically split.

  let mut h1 = DefaultHasher::new();
  contiguous.hash(&mut h1);
  let mut h2 = DefaultHasher::new();
  wrapped.hash(&mut h2);
  assert_eq!(h1.finish(), h2.finish());
}

#[test]
fn append_zst_tracks_length() {
  #[derive(Clone, Debug, PartialEq)]
  struct Z;
  let mut a = GenericArrayDeque::<Z, U4>::new();
  a.push_back(Z);
  a.push_back(Z);
  let mut b = GenericArrayDeque::<Z, U4>::new();
  b.push_back(Z);
  assert!(a.append(&mut b));
  assert_eq!(a.len(), 3);
  assert_eq!(b.len(), 0);

  // Overflow path: combined > capacity => false, state unchanged.
  let mut c = GenericArrayDeque::<Z, U4>::new();
  for _ in 0..4 {
    c.push_back(Z);
  }
  let mut d = GenericArrayDeque::<Z, U4>::new();
  d.push_back(Z);
  assert!(!c.append(&mut d));
  assert_eq!(c.len(), 4);
  assert_eq!(d.len(), 1);
}

#[test]
fn binary_search_hits_back_slice_branches() {
  // Force a wrapping layout so that `back` contains later elements.
  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  // Rotate so items split between front and back.
  for _ in 0..3 {
    deque.pop_front();
  }
  for v in 4..8 {
    deque.push_back(v);
  }
  // deque logical: [3, 4, 5, 6, 7], physically wrapped.

  assert_eq!(deque.binary_search(&3), Ok(0));
  // Hit the `Equal` on `back.first()` branch.
  assert!(deque.binary_search(&5).is_ok());
  // Hit the `Less` on `back.first()` branch (target strictly greater).
  assert_eq!(deque.binary_search(&7), Ok(4));
  // Not found, past the end.
  assert_eq!(deque.binary_search(&99), Err(5));
}

#[test]
fn partition_point_splits_across_slices() {
  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  for _ in 0..3 {
    deque.pop_front();
  }
  for v in 4..8 {
    deque.push_back(v);
  }
  // deque logical: [3, 4, 5, 6, 7].
  // Partition point ends up in `back` (after the physical split).
  let idx = deque.partition_point(|&x| x < 6);
  assert_eq!(idx, 3);
  // Partition point that lands in `front` (first condition true for all of back).
  let idx = deque.partition_point(|&x| x < 0);
  assert_eq!(idx, 0);
}

#[test]
fn insert_returns_value_when_full_or_out_of_range() {
  let mut deque = GenericArrayDeque::<i32, U2>::new();
  deque.push_back(1);
  deque.push_back(2);
  assert_eq!(deque.insert(0, 99), Some(99));

  let mut deque = GenericArrayDeque::<i32, U4>::new();
  deque.push_back(1);
  // index > len
  assert_eq!(deque.insert(5, 99), Some(99));
}

#[test]
fn retain_keeps_all_and_drops_all() {
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..5).unwrap();
  deque.retain(|_| true);
  assert_eq!(deque.len(), 5);

  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..5).unwrap();
  deque.retain(|_| false);
  assert!(deque.is_empty());
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn retain_mut_mutates_in_place() {
  use std::{vec, vec::Vec};
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..5).unwrap();
  deque.retain_mut(|x| {
    *x *= 2;
    *x != 4
  });
  // Inputs 0..5 become 0,2,4,6,8; predicate drops the 4.
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![0, 2, 6, 8]);
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn resize_with_rejects_when_over_capacity() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U4>::new();
  // Requested new_len exceeds capacity => false.
  assert!(!deque.resize_with(5, || 0));
  // Succeed at or below capacity.
  assert!(deque.resize_with(3, || 7));
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![7, 7, 7]);
  // Shrink path.
  assert!(deque.resize_with(1, || 0));
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![7]);
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn copy_slice_split_at_exercises_wrap() {
  use std::{vec, vec::Vec};

  // This test exercises `copy_slice`'s wrap branch via `append`.
  let mut dst = GenericArrayDeque::<i32, U8>::new();
  // Advance the head so that appending a slice ends up wrapping.
  for v in 0..6 {
    dst.push_back(v);
  }
  for _ in 0..4 {
    dst.pop_front();
  }
  // dst logical: [4, 5]; head=4, remaining=6.
  let mut src = GenericArrayDeque::<i32, U8>::try_from_array([10, 11, 12, 13, 14]).unwrap();
  assert!(dst.append(&mut src));
  assert_eq!(
    dst.iter().copied().collect::<Vec<_>>(),
    vec![4, 5, 10, 11, 12, 13, 14]
  );
}

// --- wrap_copy branches ---
// wrap_copy chooses one of 8 code paths based on (src_wraps, dst_wraps, dst_after_src).
// Exercise them via `rotate_left` / `rotate_right` / `insert` / `remove` on deques
// whose head position puts the copy in each regime.

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn rotate_left_across_wrap() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..6 {
    deque.push_back(v);
  }
  for _ in 0..3 {
    deque.pop_front();
  }
  for v in 6..10 {
    deque.push_back(v);
  }
  // logical: [3,4,5,6,7,8,9]
  deque.rotate_left(3);
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![6, 7, 8, 9, 3, 4, 5]
  );
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn rotate_right_across_wrap() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..6 {
    deque.push_back(v);
  }
  for _ in 0..3 {
    deque.pop_front();
  }
  for v in 6..10 {
    deque.push_back(v);
  }
  deque.rotate_right(2);
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![8, 9, 3, 4, 5, 6, 7]
  );
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn insert_and_remove_at_every_position_wrapping() {
  use std::vec::Vec;

  // Stress `wrap_copy`'s 8 branches by performing insert/remove at every
  // position on a wrapped deque. Each pair should round-trip.
  for head_pos in 0..8 {
    for at in 0..5 {
      let mut deque = GenericArrayDeque::<i32, U8>::new();
      deque.head = head_pos;
      deque.len = 0;
      for v in 0..5 {
        deque.push_back(v);
      }
      let before: Vec<_> = deque.iter().copied().collect();
      assert_eq!(deque.insert(at, 99), None);
      assert_eq!(deque.remove(at), Some(99));
      let after: Vec<_> = deque.iter().copied().collect();
      assert_eq!(before, after, "head_pos={head_pos}, at={at}");
    }
  }
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn drain_debug_fmt() {
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..4).unwrap();
  let drain = deque.drain(1..3);
  let _ = std::format!("{:?}", drain);
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn iter_debug_fmt_shows_both_slices() {
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  deque.pop_front();
  deque.push_back(4);
  let iter = deque.iter();
  let s = std::format!("{:?}", iter);
  assert!(s.starts_with("Iter("));
  let _ = std::format!("{:?}", deque.iter_mut());
  let _ = std::format!("{:?}", deque.clone().into_iter());
}

#[cfg(feature = "std")]
#[test]
fn range_bounds_invalid_panics() {
  let deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  // Included end == len panics via `slice_index_fail`.
  let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
    #[allow(clippy::reversed_empty_ranges)]
    let _ = deque.range(2..=10);
  }));
  assert!(r.is_err());

  // start > end panics.
  let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
    use core::ops::Bound;
    let _ = deque.range((Bound::Excluded(2), Bound::Included(1)));
  }));
  assert!(r.is_err());
}

// --- Additional coverage: unstable APIs, drain internals, make_contiguous edges ---

#[cfg(feature = "unstable")]
#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn truncate_front_keeps_last_items() {
  use std::{vec, vec::Vec};
  // Build a physically-wrapped deque so both branches of `truncate_front`
  // are reachable: front=[5,6,7], back=[8,9,10,11,12].
  fn wrapped() -> GenericArrayDeque<i32, U8> {
    let mut deque = GenericArrayDeque::<i32, U8>::new();
    for v in 0..8 {
      deque.push_back(v);
    }
    for _ in 0..5 {
      deque.pop_front();
    }
    for v in 8..13 {
      deque.push_back(v);
    }
    deque
  }

  // `len > back.len()` branch: drop part of `front`, keep all of `back`.
  let mut deque = wrapped();
  deque.truncate_front(6);
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![7, 8, 9, 10, 11, 12]
  );

  // `len <= back.len()` branch: drop all of `front` plus part of `back`.
  let mut deque = wrapped();
  deque.truncate_front(3);
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![10, 11, 12]);
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[cfg(feature = "unstable")]
#[test]
fn truncate_front_noop_when_len_not_smaller() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  deque.truncate_front(5);
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
  deque.truncate_front(3);
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
}

#[cfg(feature = "unstable")]
#[test]
fn insert_mut_errors_when_out_of_range_or_full() {
  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2]).unwrap();
  // index > len.
  assert_eq!(deque.insert_mut(5, 99), Err(99));

  let mut full = GenericArrayDeque::<i32, U2>::try_from_array([1, 2]).unwrap();
  // is_full.
  assert_eq!(full.insert_mut(0, 99), Err(99));
}

#[cfg(feature = "unstable")]
#[test]
fn push_mut_variants_return_err_when_full() {
  let mut deque = GenericArrayDeque::<i32, U2>::try_from_array([1, 2]).unwrap();
  assert_eq!(deque.push_back_mut(99), Err(99));
  assert_eq!(deque.push_front_mut(99), Err(99));
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[cfg(feature = "unstable")]
#[test]
fn extend_from_within_rejects_bad_range_and_overflow() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  // Bad range: end past len.
  assert!(!deque.extend_from_within(0..5));
  // Overflow: range fits but cloned items wouldn't.
  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  assert!(!deque.extend_from_within(0..3));
  assert_eq!(deque.len(), 3);

  // Happy path to exercise the clone loop.
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_array([1, 2, 3]).unwrap();
  assert!(deque.extend_from_within(0..2));
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![1, 2, 3, 1, 2]
  );
}

#[cfg(feature = "unstable")]
#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn prepend_from_within_paths() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  assert!(!deque.prepend_from_within(0..5));

  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  assert!(!deque.prepend_from_within(0..3));

  // Happy path spanning the physical wrap so both ranges in
  // `nonoverlapping_ranges` get exercised.
  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  for _ in 0..3 {
    deque.pop_front();
  }
  for v in 4..6 {
    deque.push_back(v);
  }
  // logical: [3, 4, 5]; head != 0.
  assert!(deque.prepend_from_within(0..2));
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![3, 4, 3, 4, 5]
  );
}

#[cfg(feature = "unstable")]
#[test]
fn pop_back_if_covers_both_branches() {
  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3, 4]).unwrap();
  assert_eq!(deque.pop_back_if(|x| *x == 4), Some(4));
  assert_eq!(deque.pop_back_if(|x| *x == 4), None);
  assert_eq!(deque.len(), 3);

  let mut empty = GenericArrayDeque::<i32, U4>::new();
  assert_eq!(empty.pop_back_if(|_| true), None);
}

#[cfg(feature = "unstable")]
#[test]
fn pop_front_if_covers_both_branches() {
  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  assert_eq!(deque.pop_front_if(|x| *x == 1), Some(1));
  assert_eq!(deque.pop_front_if(|x| *x == 1), None);

  let mut empty = GenericArrayDeque::<i32, U4>::new();
  assert_eq!(empty.pop_front_if(|_| true), None);
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn drain_size_hint_and_empty_next_back() {
  use std::{vec, vec::Vec};

  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..4).unwrap();
  {
    let mut drain = deque.drain(1..3);
    assert_eq!(drain.size_hint(), (2, Some(2)));
    assert_eq!(drain.next(), Some(1));
    assert_eq!(drain.size_hint(), (1, Some(1)));
    assert_eq!(drain.next_back(), Some(2));
    assert_eq!(drain.next_back(), None);
    assert_eq!(drain.next(), None);
  }
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![0, 3]);
}

#[cfg(feature = "unstable")]
#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn extract_if_debug_fmt_includes_peek_and_empty() {
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..4).unwrap();
  let extract = deque.extract_if(.., |v| *v % 2 == 0);
  let s = std::format!("{:?}", extract);
  assert!(s.contains("ExtractIf"));
  assert!(s.contains("peek"));
  drop(extract);

  // Also exhaust the iterator so Debug's `None` arm fires.
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..2).unwrap();
  let mut extract = deque.extract_if(.., |_| true);
  assert!(extract.next().is_some());
  assert!(extract.next().is_some());
  let s_empty = std::format!("{:?}", extract);
  assert!(s_empty.contains("ExtractIf"));
}

#[test]
fn with_capacity_noops_for_zsts() {
  // ZST path of `make_contiguous`: resets head to 0 without touching memory.
  #[derive(Clone, PartialEq, Debug)]
  struct Z;
  let mut deque = GenericArrayDeque::<Z, U4>::new();
  deque.push_back(Z);
  deque.push_back(Z);
  deque.push_front(Z);
  assert_eq!(deque.len(), 3);
  let slice = deque.make_contiguous();
  assert_eq!(slice.len(), 3);
}

#[test]
fn iter_exhausts_via_swap_both_directions() {
  // Hit the `None =>` arms of `Iter::next` and `Iter::next_back` that
  // swap `i1` with `i2`. A wrapped deque puts items in both slices.
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  deque.pop_front();
  deque.push_back(4);
  // logical: [1, 2, 3, 4]; front=[1,2,3], back=[4].

  let mut iter = deque.iter();
  assert_eq!(iter.next(), Some(&1));
  assert_eq!(iter.next(), Some(&2));
  assert_eq!(iter.next(), Some(&3));
  // i1 now empty; next pulls from i2 via the swap arm.
  assert_eq!(iter.next(), Some(&4));
  assert_eq!(iter.next(), None);

  let mut iter = deque.iter();
  assert_eq!(iter.next_back(), Some(&4));
  // i2 now empty; next_back pulls from i1 via the swap arm.
  assert_eq!(iter.next_back(), Some(&3));
  assert_eq!(iter.next_back(), Some(&2));
  assert_eq!(iter.next_back(), Some(&1));
  assert_eq!(iter.next_back(), None);
}

#[test]
fn iter_mut_exhausts_via_swap_both_directions() {
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  deque.pop_front();
  deque.push_back(4);

  let mut it = deque.iter_mut();
  assert!(it.next().is_some());
  assert!(it.next().is_some());
  assert!(it.next().is_some());
  assert!(it.next().is_some());
  assert!(it.next().is_none());

  let mut it = deque.iter_mut();
  assert!(it.next_back().is_some());
  assert!(it.next_back().is_some());
  assert!(it.next_back().is_some());
  assert!(it.next_back().is_some());
  assert!(it.next_back().is_none());
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn drain_middle_of_larger_deque_exercises_head_ge_tail() {
  use std::{vec, vec::Vec};

  // `join_head_and_tail_wrapping` picks the shorter of head/tail to move.
  // Drain a range where head_len >= tail_len (hits the else arm with
  // `let (src, dst, len);` on line 277).
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..6).unwrap();
  let drained: Vec<_> = deque.drain(3..5).collect();
  assert_eq!(drained, vec![3, 4]);
  assert_eq!(deque.iter().copied().collect::<Vec<_>>(), vec![0, 1, 2, 5]);
}

#[test]
fn binary_search_hits_every_branch_with_wrapped_deque() {
  // Wrap the buffer so `back.first()` is non-None.
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  deque.pop_front();
  deque.push_back(4);
  // logical: [1, 2, 3, 4]; front=[1,2,3], back=[4].

  // `back.first()` = 4. Equal branch.
  assert_eq!(deque.binary_search(&4), Ok(3));
  // `back.first()` = 4 > 2, so `cmp_back = Greater`; falls through to front.
  assert_eq!(deque.binary_search(&2), Ok(1));
  // Not found, greater than everything => at end.
  assert_eq!(deque.binary_search(&99), Err(4));

  // Construct a scenario where `back.first()` is strictly less than target.
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  // pop/push to get front=[1,2], back=[3,4]... but the buffer size is 4 and
  // only 4 elements fit, so a simpler setup:
  deque.pop_front();
  deque.pop_front();
  deque.push_back(4);
  deque.push_back(5);
  // logical: [2, 3, 4, 5]; front=[2,3], back=[4,5]. back.first()=4 < 5.
  assert_eq!(deque.binary_search(&5), Ok(3));
}

#[test]
fn partition_point_in_back_slice() {
  let mut deque = GenericArrayDeque::<i32, U4>::new();
  for v in 0..4 {
    deque.push_back(v);
  }
  deque.pop_front();
  deque.pop_front();
  deque.push_back(4);
  deque.push_back(5);
  // logical: [2, 3, 4, 5]; front=[2,3], back=[4,5].
  // pred(back[0]=4) = true (if x < 5) → partition point is in back slice.
  assert_eq!(deque.partition_point(|&x| x < 5), 3);
}

#[cfg(feature = "std")]
#[test]
fn append_zst_overflow_panics() {
  // `append`'s ZST fast path runs `self.len.checked_add(other.len)` —
  // force an overflow to hit the `None => panic!` arm.
  #[derive(Clone, Debug, PartialEq)]
  struct Z;
  let mut a = GenericArrayDeque::<Z, U4>::new();
  let mut b = GenericArrayDeque::<Z, U4>::new();
  // Bypass safe API to push `len` above capacity; fine for ZST test since
  // no drop runs and the invariant only matters for non-ZST access.
  a.len = usize::MAX;
  b.len = 1;
  let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
    a.append(&mut b);
  }));
  assert!(r.is_err());
  // Avoid running the test harness's drop for `a` in its corrupted state.
  a.len = 0;
  b.len = 0;
}

#[test]
fn insert_out_of_bounds_returns_value() {
  let mut deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2]).unwrap();
  assert_eq!(deque.insert(10, 99), Some(99));
}

#[cfg(feature = "unstable")]
#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn try_range_excluded_bounds() {
  use core::ops::Bound;
  use std::{vec, vec::Vec};
  // extend_from_within uses `try_range`, which returns `Option` (no panic).
  // Exercise the `Excluded(&start) => start + 1` arm.
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..4).unwrap();
  assert!(deque.extend_from_within((Bound::Excluded(0), Bound::Excluded(3))));
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![0, 1, 2, 3, 1, 2]
  );

  // Excluded start >= end → `try_range` returns None → extend refuses.
  let mut deque = GenericArrayDeque::<i32, U8>::try_from_iter(0..4).unwrap();
  assert!(!deque.extend_from_within((Bound::Excluded(3), Bound::Excluded(3))));
  assert_eq!(deque.len(), 4);
}

#[cfg(feature = "std")]
#[test]
fn range_panics_on_start_past_len() {
  let deque = GenericArrayDeque::<i32, U4>::try_from_array([1, 2, 3]).unwrap();
  // start > len via Bound::Excluded(len+1) → hits `slice_index_fail`'s
  // "start > len" panic arm.
  let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
    use core::ops::Bound;
    #[allow(clippy::reversed_empty_ranges)]
    let _ = deque.range((Bound::Excluded(5usize), Bound::Included(10)));
  }));
  assert!(r.is_err());
}

#[cfg(any(feature = "alloc", feature = "std"))]
#[test]
fn make_contiguous_head_to_end_big_tail() {
  use std::{vec, vec::Vec};

  // Exercise the "free < head_len && free < tail_len" branch where head_len > tail_len.
  let mut deque = GenericArrayDeque::<i32, U8>::new();
  for v in 0..5 {
    deque.push_back(v);
  }
  for _ in 0..2 {
    deque.pop_front();
  }
  for v in 5..8 {
    deque.push_back(v);
  }
  // Now pop_front again to ensure shape.
  // logical: [2,3,4,5,6,7]
  deque.make_contiguous();
  assert_eq!(
    deque.iter().copied().collect::<Vec<_>>(),
    vec![2, 3, 4, 5, 6, 7]
  );
}