/*
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

#![allow(clippy::type_complexity)]
use std::iter::zip;

use anyhow::Result;
use indexed_dict::*;
use rand::rngs::SmallRng;
use rand::{RngExt, SeedableRng};
use sux::prelude::*;

#[test]
#[cfg(feature = "rayon")]
fn test_elias_fano_concurrent() -> Result<()> {
    use rayon::prelude::*;
    use sux::dict::elias_fano::EliasFanoConcurrentBuilder;
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();

        values.sort();

        // create the builder for the "in memory" elias-fano
        let efb = EliasFanoConcurrentBuilder::new(n, u);
        // push concurrently the values
        values
            .par_iter()
            .enumerate()
            .for_each(|(index, value)| unsafe { efb.set(index, *value) });
        // Finish the creation of elias-fano
        let _ef = efb.build();
    }
    Ok(())
}

#[test]
fn test_elias_fano() -> Result<()> {
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();

        values.sort();

        // create the builder for the "in memory" elias-fano
        let mut efb = EliasFanoBuilder::new(n, u);
        // push the values
        for value in values.iter() {
            efb.push(*value);
        }
        // Finish the creation of elias-fano
        let ef = efb.build();

        // Add an index on ones (will make it into an IndexedSeq)
        let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
        // Add an index on zeros (will make it into an IndexedDict + Succ + Pred)
        let ef = unsafe { ef.map_high_bits(SelectZeroAdaptConst::<_, _>::new) };

        for v in 0..u {
            let res = values.binary_search(&v);
            let contains = res.is_ok();
            assert_eq!(ef.contains(v), contains);

            if contains {
                let i = res.unwrap();
                assert_eq!(ef.get(i), v);
                assert_eq!(ef.get(ef.index_of(v).unwrap()), v);
            } else {
                assert_eq!(ef.index_of(v), None);
            }
        }

        // do a fast select
        for (i, v) in values.iter().enumerate() {
            assert_eq!({ ef.get(i) }, *v);
        }

        let mut iterator = ef.iter().enumerate();
        while let Some((i, v)) = iterator.next() {
            assert_eq!(v, values[i]);
            assert_eq!(iterator.len(), ef.len() - i - 1);
        }

        for from in 0..ef.len() {
            let mut iterator = ef.iter_from(from).enumerate();
            while let Some((i, v)) = iterator.next() {
                assert_eq!(v, values[i + from]);
                assert_eq!(iterator.len(), ef.len() - i - from - 1);
            }
        }

        let last = values.last().unwrap();
        let mut lower_bound = 0u64;
        for (i, v) in values.iter().enumerate() {
            if lower_bound > *v {
                continue;
            }
            loop {
                assert!(ef.succ(lower_bound).unwrap() == (i, *v));
                lower_bound += 1;
                if lower_bound > values[i] {
                    break;
                }
            }
        }

        assert_eq!(None, ef.succ(last + 1));

        let mut lower_bound = 0u64;
        for (i, v) in values.iter().enumerate() {
            if lower_bound >= *v {
                continue;
            }
            loop {
                assert!(ef.succ_strict(lower_bound).unwrap() == (i, *v));
                lower_bound += 1;
                if lower_bound >= values[i] {
                    break;
                }
            }
        }

        assert_eq!(None, ef.succ_strict(*last));

        let first = *values.first().unwrap();
        let mut upper_bound = first + 1;
        for (i, v) in values.iter().enumerate() {
            if upper_bound <= *v {
                continue;
            }
            // Skip repeated items as we return the index of the last one
            if i + 1 < values.len() && values[i] == values[i + 1] {
                continue;
            }
            loop {
                assert!(ef.pred_strict(upper_bound).unwrap() == (i, *v));
                upper_bound += 1;
                if i + 1 == values.len() || upper_bound > values[i + 1] {
                    break;
                }
            }
        }

        for upper_bound in 0..first + 1 {
            assert_eq!(None, ef.pred_strict(upper_bound));
        }

        let first = *values.first().unwrap();
        let mut upper_bound = first;
        for (i, v) in values.iter().enumerate() {
            if upper_bound < *v {
                continue;
            }
            // Skip repeated items as we return the index of the last one
            if i + 1 < values.len() && values[i] == values[i + 1] {
                continue;
            }
            loop {
                assert!(ef.pred(upper_bound).unwrap() == (i, *v));
                upper_bound += 1;
                if i + 1 == values.len() || upper_bound >= values[i + 1] {
                    break;
                }
            }
        }

        for upper_bound in 0..first {
            assert_eq!(None, ef.pred(upper_bound));
        }
    }

    Ok(())
}

#[test]
fn test_empty() {
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    assert_eq!(ef.len(), 0);
}

#[test]
#[should_panic]
fn test_empty_access() {
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    assert_eq!(ef.len(), 0);
    ef.get(0);
}

#[test]
#[should_panic]
fn test_too_many_values() {
    let mut efb = EliasFanoBuilder::new(2, 10u64);
    efb.push(0);
    efb.push(1);
    efb.push(2);
}

#[test]
#[should_panic]
fn test_too_few_values() {
    let mut efb = EliasFanoBuilder::new(2, 10u64);
    efb.push(0);
    let _ = efb.build();
}

#[test]
#[should_panic]
fn test_non_monotone() {
    let mut efb = EliasFanoBuilder::new(2, 10u64);
    efb.push(1);
    efb.push(0);
}

#[test]
#[should_panic]
fn test_too_large() {
    let mut efb = EliasFanoBuilder::new(2, 10u64);
    efb.push(11);
}

#[test]
#[should_panic]
fn test_from_non_monotone() {
    let _ef: EliasFano = vec![1, 0].into();
}

#[test]
fn test_extend() {
    let mut efb = EliasFanoBuilder::new(3, 10u64);
    let v = vec![0u64, 1, 2];
    efb.extend(v.clone());
    let ef = efb.build();
    zip(ef.iter(), v.iter()).for_each(|(a, b)| assert_eq!(a, *b));
}

#[cfg(feature = "mmap")]
#[test]
fn test_epserde() -> Result<()> {
    use epserde::prelude::Aligned16;
    use epserde::ser::Serialize;

    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [(100, 1000u64), (100, 100), (1000, 100)] {
        use epserde::utils::AlignedCursor;

        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();

        values.sort();

        // create the builder for the "in memory" elias-fano
        let mut efb = EliasFanoBuilder::new(n, u);
        // push the values
        for value in values.iter() {
            efb.push(*value);
        }
        // Finish the creation of elias-fano
        let ef = unsafe { efb.build().map_high_bits(SelectAdaptConst::<_, _>::new) };

        let mut cursor = <AlignedCursor<Aligned16>>::new();
        let schema = unsafe { ef.serialize_with_schema(&mut cursor) }?;
        println!("{}", schema.to_csv());

        let len = cursor.len();
        cursor.set_position(0);
        let c = unsafe {
            use epserde::deser::Deserialize;

            <EliasFano<
                u64,
                SelectAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>>,
                BitFieldVec<Box<[u64]>>,
            >>::read_mmap(&mut cursor, len, epserde::deser::Flags::empty())
        }?;

        for i in 0..n {
            assert_eq!(ef.get(i), c.uncase().get(i));
        }
    }
    Ok(())
}

#[test]
fn test_convenience_methods() {
    let mut efb = EliasFanoBuilder::new(10, 100u64);
    for i in 0u64..10 {
        efb.push(i * 10);
    }
    let ef = efb.build_with_seq();
    for i in 0..10 {
        assert_eq!(ef.get(i), i as u64 * 10);
    }

    let mut efb = EliasFanoBuilder::new(10, 100u64);
    for i in 0u64..10 {
        efb.push(i * 10);
    }
    let ef = efb.build_with_dict();
    for i in 0..10 {
        assert_eq!(
            unsafe { ef.succ_unchecked::<false>(i as u64 * 10) },
            (i, i as u64 * 10)
        );
    }

    let mut efb = EliasFanoBuilder::new(10, 100u64);
    for i in 0u64..10 {
        efb.push(i * 10);
    }
    let ef = efb.build_with_seq_and_dict();
    for i in 0..10 {
        assert_eq!(ef.get(i), i as u64 * 10);
        assert_eq!(ef.succ(i as u64 * 10).unwrap(), (i, i as u64 * 10));
    }
}

#[test]
fn test_iter_from_succ() -> Result<()> {
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();
        values.sort();

        // Test with EfSeqDict (has both SelectUnchecked and SelectZeroUnchecked)
        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef = efb.build_with_seq_and_dict();

        // Test iter_from_succ: results match succ + iter_from
        for v in 0..=u {
            let succ_result = ef.succ(v);
            let iter_succ_result = ef.iter_from_succ(v);
            match (succ_result, iter_succ_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, iter))) => {
                    assert_eq!(idx, idx2);
                    // The iterator should yield the successor and all subsequent values
                    let collected: Vec<u64> = iter.collect();
                    assert_eq!(collected.len(), n - idx);
                    assert_eq!(collected[0], val);
                    for (i, &cv) in collected.iter().enumerate() {
                        assert_eq!(cv, values[idx + i]);
                    }
                }
                _ => panic!("succ and iter_from_succ disagree for value {v}"),
            }
        }

        // Test iter_from_succ_strict
        for v in 0..=u {
            let succ_result = ef.succ_strict(v);
            let iter_succ_result = ef.iter_from_succ_strict(v);
            match (succ_result, iter_succ_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, iter))) => {
                    assert_eq!(idx, idx2);
                    let collected: Vec<u64> = iter.collect();
                    assert_eq!(collected.len(), n - idx);
                    assert_eq!(collected[0], val);
                    for (i, &cv) in collected.iter().enumerate() {
                        assert_eq!(cv, values[idx + i]);
                    }
                }
                _ => panic!("succ_strict and iter_from_succ_strict disagree for value {v}"),
            }
        }

        // Test with EfDict (only SelectZeroUnchecked, no SelectUnchecked)
        // This tests the inherent unchecked method's weaker bounds
        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef_dict = efb.build_with_dict();

        for v in 0..=u {
            // Use succ_unchecked on EfDict (no Succ trait since no SelectUnchecked)
            // and compare with iter_from_succ_unchecked
            let succ_result = values.partition_point(|&x| x < v);
            if succ_result < n {
                let (idx, iter) = unsafe { ef_dict.iter_from_succ_unchecked::<false>(v) };
                assert_eq!(idx, succ_result);
                let collected: Vec<u64> = iter.collect();
                assert_eq!(collected.len(), n - idx);
                assert_eq!(collected[0], values[succ_result]);
                for (i, &cv) in collected.iter().enumerate() {
                    assert_eq!(cv, values[idx + i]);
                }
            }
        }

        // Test unchecked version directly
        for v in 0..=u {
            if let Some((idx, val)) = ef.succ(v) {
                let (idx2, iter) = unsafe { ef.iter_from_succ_unchecked::<false>(v) };
                assert_eq!(idx, idx2);
                let collected: Vec<u64> = iter.collect();
                assert_eq!(collected[0], val);
            }
        }
    }

    // Test empty sequence
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    assert!(ef.iter_from_succ(0).is_none());
    assert!(ef.iter_from_succ_strict(0).is_none());

    Ok(())
}

#[test]
fn test_iter_back() -> Result<()> {
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();
        values.sort();

        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef = efb.build_with_seq_and_dict();

        // 1. iter_back() yields all elements in backward order
        let rev: Vec<u64> = ef.iter_back().collect();
        let mut expected = values.clone();
        expected.reverse();
        assert_eq!(rev, expected);

        // 2. iter_back_from(k) yields elements k-1, k-2, ..., 0
        for from in 0..=n {
            let rev: Vec<u64> = ef.iter_back_from(from).collect();
            let expected: Vec<u64> = values[..from].iter().copied().rev().collect();
            assert_eq!(rev, expected);
        }

        // 3. iter().backward() at position 0 is empty; iter_from(n).backward() yields all in backward
        let back: Vec<u64> = ef.iter().backward().collect();
        assert!(back.is_empty());

        let back: Vec<u64> = ef.iter_from(n).backward().collect();
        let mut expected = values.clone();
        expected.reverse();
        assert_eq!(back, expected);

        // 4. Round-trip: iter_from(k).backward().forward() yields same as iter_from(k)
        for from in 0..=n {
            let roundtrip: Vec<u64> = ef.iter_from(from).backward().forward().collect();
            let direct: Vec<u64> = ef.iter_from(from).collect();
            assert_eq!(roundtrip, direct);
        }

        // 5. iter_back().forward() yields forward from cursor n (empty)
        let roundtrip: Vec<u64> = ef.iter_back().forward().collect();
        assert!(roundtrip.is_empty());

        // Consuming iter_back fully then forward gives forward from cursor 0 = iter()
        let mut back = ef.iter_back();
        while back.next().is_some() {}
        let roundtrip: Vec<u64> = back.forward().collect();
        let direct: Vec<u64> = ef.iter().collect();
        assert_eq!(roundtrip, direct);

        // 6. ExactSizeIterator::len() is correct throughout iteration
        let mut rev = ef.iter_back();
        for remaining in (0..n).rev() {
            assert_eq!(rev.len(), remaining + 1);
            rev.next();
            assert_eq!(rev.len(), remaining);
        }
        assert_eq!(rev.len(), 0);
        assert!(rev.next().is_none());

        // Test len for iter_from().backward()
        for from in 0..=n {
            let mut back = ef.iter_from(from).backward();
            assert_eq!(back.len(), from);
            for remaining in (0..from).rev() {
                back.next();
                assert_eq!(back.len(), remaining);
            }
        }
    }

    // 7. Works with EfDict (only SelectZeroUnchecked, no SelectUnchecked)
    let mut rng = SmallRng::seed_from_u64(42);
    for (n, u) in [(10, 1000u64), (100, 100)] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();
        values.sort();

        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef = efb.build_with_dict();

        // EfDict has no SelectUnchecked, so iter_from/iter_back_from won't work,
        // but iter_back() should work since it only needs AsRef<[usize]>
        let rev: Vec<u64> = ef.iter_back().collect();
        let mut expected = values.clone();
        expected.reverse();
        assert_eq!(rev, expected);
    }

    // Test empty sequence
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    let rev: Vec<u64> = ef.iter_back().collect();
    assert!(rev.is_empty());
    assert_eq!(ef.iter_back().len(), 0);

    Ok(())
}

#[test]
fn test_iter_back_from_pred() -> Result<()> {
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();
        values.sort();

        // Test with EfSeqDict (has both SelectUnchecked and SelectZeroUnchecked)
        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef = efb.build_with_seq_and_dict();

        // Test iter_back_from_pred: results match pred + backward iteration
        for v in 0..=u {
            let pred_result = ef.pred(v);
            let iter_pred_result = ef.iter_back_from_pred(v);
            match (pred_result, iter_pred_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, iter))) => {
                    assert_eq!(idx, idx2);
                    // The iterator should yield the predecessor and all preceding values
                    let collected: Vec<u64> = iter.collect();
                    assert_eq!(collected.len(), idx + 1);
                    assert_eq!(collected[0], val);
                    for (i, &cv) in collected.iter().enumerate() {
                        assert_eq!(cv, values[idx - i]);
                    }
                }
                _ => panic!("pred and iter_back_from_pred disagree for value {v}"),
            }
        }

        // Test iter_back_from_pred_strict
        for v in 0..=u {
            let pred_result = ef.pred_strict(v);
            let iter_pred_result = ef.iter_back_from_pred_strict(v);
            match (pred_result, iter_pred_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, iter))) => {
                    assert_eq!(idx, idx2);
                    let collected: Vec<u64> = iter.collect();
                    assert_eq!(collected.len(), idx + 1);
                    assert_eq!(collected[0], val);
                    for (i, &cv) in collected.iter().enumerate() {
                        assert_eq!(cv, values[idx - i]);
                    }
                }
                _ => panic!("pred_strict and iter_back_from_pred_strict disagree for value {v}"),
            }
        }

        // Test with EfDict (only SelectZeroUnchecked, no SelectUnchecked)
        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef_dict = efb.build_with_dict();

        for v in 0..=u {
            let pred_idx = values.partition_point(|&x| x <= v);
            if pred_idx > 0 {
                let (idx, iter) = unsafe { ef_dict.iter_back_from_pred_unchecked::<false>(v) };
                assert_eq!(idx, pred_idx - 1);
                let collected: Vec<u64> = iter.collect();
                assert_eq!(collected.len(), idx + 1);
                assert_eq!(collected[0], values[idx]);
                for (i, &cv) in collected.iter().enumerate() {
                    assert_eq!(cv, values[idx - i]);
                }
            }
        }

        // Test unchecked version directly
        for v in 0..=u {
            if let Some((idx, val)) = ef.pred(v) {
                let (idx2, iter) = unsafe { ef.iter_back_from_pred_unchecked::<false>(v) };
                assert_eq!(idx, idx2);
                let collected: Vec<u64> = iter.collect();
                assert_eq!(collected[0], val);
            }
        }
    }

    // Test empty sequence
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    assert!(ef.iter_back_from_pred(0).is_none());
    assert!(ef.iter_back_from_pred_strict(0).is_none());

    Ok(())
}

#[test]
fn test_iter_bidi() -> Result<()> {
    let mut rng = SmallRng::seed_from_u64(0);
    for (n, u) in [
        (10, 1000u64),
        (100, 1000),
        (100, 100),
        (1000, 100),
        (1000, 10),
    ] {
        let mut values = (0..n).map(|_| rng.random_range(0..u)).collect::<Vec<u64>>();
        values.sort();

        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef = efb.build_with_seq_and_dict();

        // Test iter_bidi_from_succ: matches succ, then next/prev work correctly
        for v in 0..=u {
            let succ_result = ef.succ(v);
            let bidi_result = ef.iter_bidi_from_succ(v);
            match (succ_result, bidi_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, mut bidi))) => {
                    assert_eq!(idx, idx2);
                    assert_eq!(bidi.len(), n - idx);
                    // next() yields the successor first
                    assert_eq!(bidi.next(), Some(val));
                    // prev() goes back to the successor
                    assert_eq!(bidi.prev(), Some(val));
                    // next() again yields the successor
                    assert_eq!(bidi.next(), Some(val));
                    // Collect the rest via next()
                    let rest: Vec<u64> = bidi.collect();
                    for (i, &cv) in rest.iter().enumerate() {
                        assert_eq!(cv, values[idx + 1 + i]);
                    }
                }
                _ => panic!("succ and iter_bidi_from_succ disagree for value {v}"),
            }
        }

        // Test iter_bidi_from_succ_strict
        for v in 0..=u {
            let succ_result = ef.succ_strict(v);
            let bidi_result = ef.iter_bidi_from_succ_strict(v);
            match (succ_result, bidi_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, mut bidi))) => {
                    assert_eq!(idx, idx2);
                    assert_eq!(bidi.next(), Some(val));
                }
                _ => panic!("succ_strict and iter_bidi_from_succ_strict disagree for value {v}"),
            }
        }

        // Test iter_bidi_from_pred: matches pred, then next/prev work correctly
        for v in 0..=u {
            let pred_result = ef.pred(v);
            let bidi_result = ef.iter_bidi_from_pred(v);
            match (pred_result, bidi_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, mut bidi))) => {
                    assert_eq!(idx, idx2);
                    assert_eq!(bidi.len(), n - idx);
                    // next() yields the predecessor first
                    assert_eq!(bidi.next(), Some(val));
                    // prev() goes back to the predecessor
                    assert_eq!(bidi.prev(), Some(val));
                    // next() again yields the predecessor
                    assert_eq!(bidi.next(), Some(val));
                    // Collect the rest via next()
                    let rest: Vec<u64> = bidi.collect();
                    for (i, &cv) in rest.iter().enumerate() {
                        assert_eq!(cv, values[idx + 1 + i]);
                    }
                }
                _ => panic!("pred and iter_bidi_from_pred disagree for value {v}"),
            }
        }

        // Test iter_bidi_from_pred_strict
        for v in 0..=u {
            let pred_result = ef.pred_strict(v);
            let bidi_result = ef.iter_bidi_from_pred_strict(v);
            match (pred_result, bidi_result) {
                (None, None) => {}
                (Some((idx, val)), Some((idx2, mut bidi))) => {
                    assert_eq!(idx, idx2);
                    assert_eq!(bidi.next(), Some(val));
                }
                _ => panic!("pred_strict and iter_bidi_from_pred_strict disagree for value {v}"),
            }
        }

        // Test full traversal forward then backward
        if let Some((_, mut bidi)) = ef.iter_bidi_from_succ(0) {
            // Forward
            for &v in &values {
                assert_eq!(bidi.next(), Some(v));
            }
            assert_eq!(bidi.next(), None);
            // Backward
            for i in (0..n).rev() {
                assert_eq!(bidi.prev(), Some(values[i]));
            }
            assert_eq!(bidi.prev(), None);
        }

        // Test with EfDict (only SelectZeroUnchecked)
        let mut efb = EliasFanoBuilder::new(n, u);
        for &v in &values {
            efb.push(v);
        }
        let ef_dict = efb.build_with_dict();

        for v in 0..=u {
            let succ_idx = values.partition_point(|&x| x < v);
            if succ_idx < n {
                let (idx, mut bidi) = unsafe { ef_dict.iter_bidi_from_succ_unchecked::<false>(v) };
                assert_eq!(idx, succ_idx);
                assert_eq!(bidi.next(), Some(values[succ_idx]));
            }

            let pred_idx = values.partition_point(|&x| x <= v);
            if pred_idx > 0 {
                let (idx, mut bidi) = unsafe { ef_dict.iter_bidi_from_pred_unchecked::<false>(v) };
                assert_eq!(idx, pred_idx - 1);
                assert_eq!(bidi.next(), Some(values[pred_idx - 1]));
            }
        }
    }

    // Test empty sequence
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef = efb.build_with_seq_and_dict();
    assert!(ef.iter_bidi_from_succ(0).is_none());
    assert!(ef.iter_bidi_from_succ_strict(0).is_none());
    assert!(ef.iter_bidi_from_pred(0).is_none());
    assert!(ef.iter_bidi_from_pred_strict(0).is_none());

    Ok(())
}

#[test]
fn test_iter_bidi_trait_methods() -> Result<()> {
    let values: Vec<u64> = vec![10, 20, 30, 40, 50];
    let n = values.len();
    let u = 50u64;

    let mut efb = EliasFanoBuilder::new(n, u);
    for &v in &values {
        efb.push(v);
    }
    let ef = efb.build_with_seq_and_dict();

    // --- IntoBidiIterator ---

    // into_iter_bidi (default calls into_iter_bidi_from(0))
    let mut bidi = (&ef).into_iter_bidi();
    assert_eq!(bidi.next(), Some(10u64));
    assert_eq!(bidi.prev(), Some(10u64));
    assert_eq!(bidi.prev(), None);

    // into_iter_bidi_from
    let mut bidi = (&ef).into_iter_bidi_from(2);
    assert_eq!(bidi.next(), Some(30u64));
    assert_eq!(bidi.prev(), Some(30u64));
    assert_eq!(bidi.prev(), Some(20u64));

    // into_iter_bidi_from at end
    let mut bidi = (&ef).into_iter_bidi_from(n);
    assert_eq!(bidi.next(), None);
    assert_eq!(bidi.prev(), Some(50u64));

    // --- Convenience methods ---

    let mut bidi = ef.iter_bidi();
    assert_eq!(bidi.next(), Some(10u64));

    let mut bidi = ef.iter_bidi_from(3);
    assert_eq!(bidi.next(), Some(40u64));
    assert_eq!(bidi.prev(), Some(40u64));
    assert_eq!(bidi.prev(), Some(30u64));

    // --- BidiIterator default methods ---

    // prev_advance_by: success
    #[cfg(feature = "iter_advance_by")]
    {
        let mut bidi = ef.iter_bidi_from(n);
        assert_eq!(bidi.prev_advance_by(3), Ok(()));
        assert_eq!(bidi.prev(), Some(20u64));

        // prev_advance_by: partial failure
        let mut bidi = ef.iter_bidi_from(2);
        let err = bidi.prev_advance_by(5);
        assert!(err.is_err());
        assert_eq!(err.unwrap_err().get(), 3);
    }

    // prev_nth: success
    let mut bidi = ef.iter_bidi_from(n);
    assert_eq!(bidi.prev_nth(2), Some(30u64));

    // prev_nth: past the end
    let mut bidi = ef.iter_bidi_from(2);
    assert_eq!(bidi.prev_nth(5), None);

    // prev_fold
    let bidi = ef.iter_bidi_from(n);
    let sum = bidi.prev_fold(0u64, |acc, x| acc + x);
    assert_eq!(sum, values.iter().sum::<u64>());

    // prev_for_each
    let bidi = ef.iter_bidi_from(n);
    let mut collected = Vec::new();
    bidi.prev_for_each(|x| collected.push(x));
    assert_eq!(collected, vec![50u64, 40, 30, 20, 10]);

    // prev_count
    let bidi = ef.iter_bidi_from(n);
    assert_eq!(bidi.prev_count(), n);

    let bidi = ef.iter_bidi_from(3);
    assert_eq!(bidi.prev_count(), 3);

    // --- ExactSizeBidiIterator ---

    let bidi = ef.iter_bidi_from(2);
    assert_eq!(bidi.prev_len(), 2);

    let bidi = ef.iter_bidi_from(n);
    assert_eq!(bidi.prev_len(), n);

    // --- SwappedIter wrapper ---

    // swap() wraps in SwappedIter, swap() again unwraps
    let bidi = ef.iter_bidi_from(3);
    let mut rev = bidi.swap();
    // SwappedIter::next delegates to inner prev
    assert_eq!(rev.next(), Some(30u64));
    assert_eq!(rev.next(), Some(20u64));
    assert_eq!(rev.next(), Some(10u64));
    assert_eq!(rev.next(), None);

    // SwappedIter::prev delegates to inner next
    let bidi = ef.iter_bidi_from(2);
    let mut rev = bidi.swap();
    assert_eq!(rev.prev(), Some(30u64));
    assert_eq!(rev.prev(), Some(40u64));

    // SwappedIter::swap unwraps back to the original type
    let bidi = ef.iter_bidi_from(2);
    let rev = bidi.swap();
    let mut bidi2 = rev.swap();
    assert_eq!(bidi2.next(), Some(30u64));

    // SwappedIter::size_hint delegates to prev_size_hint
    let bidi = ef.iter_bidi_from(3);
    let rev = bidi.swap();
    assert_eq!(rev.size_hint(), (3, Some(3)));

    // SwappedIter::prev_size_hint delegates to size_hint
    let bidi = ef.iter_bidi_from(3);
    let rev = bidi.swap();
    assert_eq!(rev.prev_size_hint(), (2, Some(2)));

    // SwappedIter::nth delegates to prev_nth
    let bidi = ef.iter_bidi_from(n);
    let mut rev = bidi.swap();
    assert_eq!(rev.nth(1), Some(40u64));

    // SwappedIter::fold delegates to prev_fold
    let bidi = ef.iter_bidi_from(n);
    let rev = bidi.swap();
    #[allow(clippy::unnecessary_fold)]
    let sum = rev.fold(0u64, |acc, x| acc + x);
    assert_eq!(sum, values.iter().sum::<u64>());

    // SwappedIter::for_each delegates to prev_for_each
    let bidi = ef.iter_bidi_from(n);
    let rev = bidi.swap();
    let mut collected = Vec::new();
    rev.for_each(|x| collected.push(x));
    assert_eq!(collected, vec![50u64, 40, 30, 20, 10]);

    // SwappedIter::count delegates to prev_count
    let bidi = ef.iter_bidi_from(n);
    let rev = bidi.swap();
    assert_eq!(rev.count(), n);

    // SwappedIter ExactSizeIterator::len delegates to prev_len
    let bidi = ef.iter_bidi_from(3);
    let rev = bidi.swap();
    assert_eq!(rev.len(), 3);

    // SwappedIter ExactSizeBidiIterator::prev_len delegates to len
    let bidi = ef.iter_bidi_from(3);
    let rev = bidi.swap();
    assert_eq!(rev.prev_len(), 2);

    // SwappedIter::prev_advance_by
    #[cfg(feature = "iter_advance_by")]
    {
        let bidi = ef.iter_bidi_from(2);
        let mut rev = bidi.swap();
        assert_eq!(rev.prev_advance_by(2), Ok(()));
        assert_eq!(rev.prev(), Some(50u64));

        // SwappedIter::prev_advance_by partial failure
        let bidi = ef.iter_bidi_from(2);
        let mut rev = bidi.swap();
        let err = rev.prev_advance_by(5);
        assert!(err.is_err());
        assert_eq!(err.unwrap_err().get(), 2);
    }

    // SwappedIter::prev_nth
    let bidi = ef.iter_bidi_from(1);
    let mut rev = bidi.swap();
    assert_eq!(rev.prev_nth(2), Some(40u64));

    // SwappedIter::prev_fold
    let bidi = ef.iter_bidi_from(0);
    let rev = bidi.swap();
    let sum = rev.prev_fold(0u64, |acc, x| acc + x);
    assert_eq!(sum, values.iter().sum::<u64>());

    // SwappedIter::prev_for_each
    let bidi = ef.iter_bidi_from(0);
    let rev = bidi.swap();
    let mut collected = Vec::new();
    rev.prev_for_each(|x| collected.push(x));
    assert_eq!(collected, values);

    // SwappedIter::prev_count
    let bidi = ef.iter_bidi_from(0);
    let rev = bidi.swap();
    assert_eq!(rev.prev_count(), n);

    // --- Edge cases for into_iter_bidi_from ---

    // Empty EF
    let efb = EliasFanoBuilder::new(0, 10u64);
    let ef_empty = efb.build_with_seq_and_dict();
    let mut bidi = (&ef_empty).into_iter_bidi_from(0);
    assert_eq!(bidi.next(), None);
    assert_eq!(bidi.prev(), None);
    let mut bidi = ef_empty.iter_bidi();
    assert_eq!(bidi.next(), None);

    // from == n (non-empty): prev should work
    let mut bidi = (&ef).into_iter_bidi_from(n);
    assert_eq!(bidi.next(), None);
    assert_eq!(bidi.prev(), Some(50u64));
    assert_eq!(bidi.prev(), Some(40u64));

    // from == n via iter_bidi_from convenience (exercises the select(n-1) branch)
    let mut bidi = ef.iter_bidi_from(n);
    assert_eq!(bidi.prev(), Some(50u64));
    assert_eq!(bidi.next(), Some(50u64));
    assert_eq!(bidi.next(), None);

    // --- Iterator::count() overrides ---

    // Forward iterator count
    assert_eq!(ef.iter().count(), n);
    assert_eq!(ef.iter_from(3).count(), n - 3);
    assert_eq!(ef.iter_from(n).count(), 0);

    // Backward iterator count
    assert_eq!(ef.iter_back().count(), n);
    assert_eq!(ef.iter_back_from(3).count(), 3);
    assert_eq!(ef.iter_back_from(0).count(), 0);

    // Bidi iterator count (forward)
    assert_eq!(ef.iter_bidi().count(), n);
    assert_eq!(ef.iter_bidi_from(2).count(), n - 2);
    assert_eq!(ef.iter_bidi_from(n).count(), 0);

    // Bidi iterator prev_count
    assert_eq!(ef.iter_bidi().prev_count(), 0);
    assert_eq!(ef.iter_bidi_from(3).prev_count(), 3);
    assert_eq!(ef.iter_bidi_from(n).prev_count(), n);

    // --- Iterator::last() overrides ---

    // Forward iterator last
    assert_eq!(ef.iter().last(), Some(50u64));
    assert_eq!(ef.iter_from(3).last(), Some(50u64));
    assert_eq!(ef.iter_from(n).last(), None);

    // Backward iterator last
    assert_eq!(ef.iter_back().last(), Some(10u64));
    assert_eq!(ef.iter_back_from(3).last(), Some(10u64));
    assert_eq!(ef.iter_back_from(0).last(), None);

    // Bidi iterator last (forward)
    assert_eq!(ef.iter_bidi().last(), Some(50u64));
    assert_eq!(ef.iter_bidi_from(2).last(), Some(50u64));
    assert_eq!(ef.iter_bidi_from(n).last(), None);

    // last() after partial consumption
    let mut it = ef.iter();
    it.next();
    assert_eq!(it.last(), Some(50u64));
    let mut it = ef.iter_back();
    it.next();
    assert_eq!(it.last(), Some(10u64));
    let mut it = ef.iter_bidi();
    it.next();
    assert_eq!(it.last(), Some(50u64));

    // --- Trait-level defaults in indexed_dict ---

    // Call the trait methods explicitly to exercise the defaults
    // (EF's inherent methods shadow them in normal usage)
    let succ_result = Succ::iter_bidi_from_succ(&ef, 25);
    assert!(succ_result.is_some());
    let (idx, mut bidi) = succ_result.unwrap();
    assert_eq!(idx, 2);
    assert_eq!(bidi.next(), Some(30u64));

    let succ_strict_result = Succ::iter_bidi_from_succ_strict(&ef, 30);
    assert!(succ_strict_result.is_some());
    let (idx, mut bidi) = succ_strict_result.unwrap();
    assert_eq!(idx, 3);
    assert_eq!(bidi.next(), Some(40u64));

    // Succ trait: no successor case
    assert!(Succ::iter_bidi_from_succ(&ef, 51).is_none());
    assert!(Succ::iter_bidi_from_succ_strict(&ef, 50).is_none());

    let pred_result = Pred::iter_bidi_from_pred(&ef, 35);
    assert!(pred_result.is_some());
    let (idx, mut bidi) = pred_result.unwrap();
    assert_eq!(idx, 2);
    assert_eq!(bidi.next(), Some(30u64));

    let pred_strict_result = Pred::iter_bidi_from_pred_strict(&ef, 30);
    assert!(pred_strict_result.is_some());
    let (idx, mut bidi) = pred_strict_result.unwrap();
    assert_eq!(idx, 1);
    assert_eq!(bidi.next(), Some(20u64));

    // Pred trait: no predecessor case
    assert!(Pred::iter_bidi_from_pred(&ef, 5).is_none());
    assert!(Pred::iter_bidi_from_pred_strict(&ef, 10).is_none());

    Ok(())
}

#[test]
#[should_panic(expected = "Index out of bounds")]
fn test_iter_bidi_from_out_of_bounds() {
    let values: Vec<u64> = vec![10, 20, 30];
    let mut efb = EliasFanoBuilder::new(3, 30u64);
    for &v in &values {
        efb.push(v);
    }
    let ef = efb.build_with_seq_and_dict();
    let _ = ef.iter_bidi_from(4);
}

// ── u128 tests ──────────────────────────────────────────────────────────────

#[test]
fn test_u128_basic() {
    // Values that exceed u64::MAX
    let values: Vec<u128> = vec![
        0,
        1_000_000,
        u64::MAX as u128,
        u64::MAX as u128 + 1,
        u64::MAX as u128 + 1_000_000,
        u128::MAX / 2,
    ];
    let n = values.len();
    let u = *values.last().unwrap();

    let mut efb = EliasFanoBuilder::new(n, u);
    for &v in &values {
        efb.push(v);
    }
    let ef = efb.build();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };

    // Test get
    for (i, &expected) in values.iter().enumerate() {
        assert_eq!(ef.get(i), expected, "get({i}) failed");
    }

    // Test forward iteration
    let collected: Vec<u128> = ef.iter().collect();
    assert_eq!(collected, values);
}

#[test]
fn test_u128_from_slice() {
    let values: Vec<u128> = vec![100, 200, u64::MAX as u128 + 500, u128::MAX / 4];
    let ef: EliasFano<u128> = values.as_slice().into();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };

    for (i, &expected) in values.iter().enumerate() {
        assert_eq!(ef.get(i), expected);
    }
}

#[test]
fn test_u128_iteration() {
    let values: Vec<u128> = vec![
        0,
        42,
        u64::MAX as u128 - 1,
        u64::MAX as u128,
        u64::MAX as u128 + 1,
        u64::MAX as u128 * 2,
    ];
    let n = values.len();
    let u = *values.last().unwrap();

    let mut efb = EliasFanoBuilder::new(n, u);
    for &v in &values {
        efb.push(v);
    }
    let ef = efb.build();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };

    // Forward iteration
    let fwd: Vec<u128> = ef.iter().collect();
    assert_eq!(fwd, values);

    // Iteration from a position
    let from_2: Vec<u128> = ef.iter_from(2).collect();
    assert_eq!(from_2, &values[2..]);

    // Backward iteration
    let ef = unsafe { ef.map_high_bits(SelectZeroAdaptConst::<_, _>::new) };
    let bwd: Vec<u128> = ef.iter_back().collect();
    let mut expected_rev = values.clone();
    expected_rev.reverse();
    assert_eq!(bwd, expected_rev);
}

#[test]
fn test_u128_succ_pred() {
    let values: Vec<u128> = vec![100, u64::MAX as u128, u64::MAX as u128 + 100, u128::MAX / 4];
    let n = values.len();
    let u = *values.last().unwrap();

    let mut efb = EliasFanoBuilder::new(n, u);
    for &v in &values {
        efb.push(v);
    }
    let ef = efb.build();
    // Add select for ones (IndexedSeq) then select for zeros (SuccUnchecked/PredUnchecked)
    let ef = unsafe {
        ef.map_high_bits(SelectAdaptConst::<_, _>::new)
            .map_high_bits(SelectZeroAdaptConst::<_, _>::new)
    };

    // Successor
    let (idx, val) = unsafe { ef.succ_unchecked::<false>(0u128) };
    assert_eq!((idx, val), (0, 100));

    let (idx, val) = unsafe { ef.succ_unchecked::<false>(101u128) };
    assert_eq!((idx, val), (1, u64::MAX as u128));

    let (idx, val) = unsafe { ef.succ_unchecked::<false>(u64::MAX as u128 + 1) };
    assert_eq!((idx, val), (2, u64::MAX as u128 + 100));

    // Predecessor
    let (idx, val) = unsafe { ef.pred_unchecked::<false>(u128::MAX / 4) };
    assert_eq!((idx, val), (3, u128::MAX / 4));

    let (idx, val) = unsafe { ef.pred_unchecked::<false>(u64::MAX as u128 + 50) };
    assert_eq!((idx, val), (1, u64::MAX as u128));
}

#[test]
fn test_u128_empty() {
    let ef: EliasFano<u128> = [].as_slice().into();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
    assert_eq!(ef.len(), 0);
    assert!(ef.iter().next().is_none());
}

#[test]
fn test_u128_single() {
    let val = u128::MAX / 3;
    let ef: EliasFano<u128> = [val].as_slice().into();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
    assert_eq!(ef.len(), 1);
    assert_eq!(ef.get(0), val);
}

#[test]
fn test_u128_duplicates() {
    let val = u64::MAX as u128 + 42;
    let values: Vec<u128> = vec![val, val, val];
    let ef: EliasFano<u128> = values.as_slice().into();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
    for i in 0..3 {
        assert_eq!(ef.get(i), val);
    }
}

#[test]
fn test_u128_extend() {
    let values: Vec<u128> = vec![10, u64::MAX as u128, u64::MAX as u128 + 100];
    let mut efb = EliasFanoBuilder::new(3, u64::MAX as u128 + 100);
    efb.extend(values.clone());
    let ef = efb.build();
    let ef = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _>::new) };
    let collected: Vec<u128> = ef.iter().collect();
    assert_eq!(collected, values);
}
