use core::mem::MaybeUninit;

#[derive(PartialEq, Eq, PartialOrd, Ord)]

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]

        if let Some((k, v, _)) = m.ins {

        if let Some((k, v)) = m.ins {

            return Ok(Op::Put(if let Some((k, v, r)) = m.modified.ins {

            return Ok(Op::Put(if let Some((k, v)) = m.modified.ins {

                    r,

                    m.modified.r,

        if m.modified.c0.is_leaf {
            rebalance::<_, _, _, Leaf>(txn, m)

        if m.mod_is_left {
            if m.modified.c0.is_leaf {
                rebalance_left::<_, _, _, Leaf>(txn, m)
            } else {
                rebalance_left::<_, _, _, Internal>(txn, m)
            }

            rebalance::<_, _, _, Internal>(txn, m)

            if m.modified.c0.is_leaf {
                rebalance_right::<_, _, _, Leaf>(txn, m)
            } else {
                rebalance_right::<_, _, _, Internal>(txn, m)
            }

            debug!("set_cursor, {:?} lookup = {:?}", page.offset, lookup);

    if let Some((k, v, r)) = m.ins {
        alloc::<_, _, _, L>(new, &*k, &*v, m.l, r, n);

    if let Some((k, v)) = m.ins {
        alloc::<_, _, _, L>(new, &*k, &*v, m.l, m.r, n);

fn rebalance<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

fn rebalance_left<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(

    assert!(m.mod_is_left);
    // First element of the right page. We'll rotate it to the left
    // page.

    let new_left = if header(m.modified.page.as_page()).is_dirty() {
        let mut page = unsafe { core::mem::transmute(m.modified.page) };
        let mut n = m.modified.c1.total as isize;
        alloc::<T, K, V, L>(&mut page, m.mid.0, m.mid.1, 0, rl, &mut n);
        page

    let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };
    freed[0] = m.modified.page.offset | b;
    let mut new_left = if let Some((k, v)) = m.modified.ins {
        if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(
            txn,
            m.modified.page,
            m.modified.mutable,
            &m.modified.c1,
            &*k,
            &*v,
            m.modified.l,
            m.modified.r,
        )? {
            page
        } else {
            unreachable!()
        }

        let mut new = txn.alloc_page()?;
        <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);
        let s = L::offset_slice::<T, K, V>(m.modified.page.as_page());
        let mut n = 0;
        clone::<T, K, V, L>(m.modified.page.as_page(), &mut new, s, &mut n);
        alloc::<T, K, V, L>(&mut new, m.mid.0, m.mid.1, 0, rl, &mut n);

        <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?
    };
    let mut n = header(new_left.0.as_page()).n() as isize;
    alloc::<T, K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);

        let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };
        freed[0] = m.modified.page.offset | b;
        new

    let right_hdr = header(m.other.as_page());
    let (new_right, k, v) = match fixed_size::<T, K, V>() {
        Some(f) if r == 0 && right_hdr.is_dirty() => {
            // Rewrite the deleted element at the end of the page, so that
            // the pointer is still valid.
            let data = m.other.data;
            let mut other = MutPage(m.other);
            let right_hdr = header_mut(&mut other);
            let al = K::ALIGN.max(V::ALIGN);
            let hdr_size = (HDR + al - 1) & !(al - 1);
            let n = right_hdr.n() as usize;
            right_hdr.decr(f);
            right_hdr.set_n((n - 1) as u16);
            let mut t: MaybeUninit<Tuple<K, V>> = MaybeUninit::uninit();
            unsafe {
                core::ptr::copy_nonoverlapping(
                    data.add(hdr_size) as *mut Tuple<K, V>,
                    t.as_mut_ptr(),
                    1
                );
                core::ptr::copy(
                    data.add(hdr_size + f) as *const Tuple<K, V>,
                    data.add(hdr_size) as *mut Tuple<K, V>,
                    n-1
                );
                let last = data.add(hdr_size + f * (n-1)) as *mut Tuple<K, V>;
                core::ptr::copy_nonoverlapping(
                    t.as_ptr(),
                    last,
                    1
                );
                debug!("tuple = {:?}", t.assume_init());
                (other, &(&*last).k, &(&*last).v)
            }
        }
        _ => unsafe {
            (<Page<K, V>>::del(txn, m.other, &rc, r)?,
             core::mem::transmute(k),
             core::mem::transmute(v))
        }

    let new_right = <Page<K, V>>::del(txn, m.other, &rc, r)?;

fn rebalance_right<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
    txn: &mut T,
    m: &mut Concat<'a, T, K, V, Page<K, V>>,
) -> Result<Op<'a, T, K, V>, T::Error> {
    assert!(!m.mod_is_left);
    // Take the last element of the left page.
    let lc = <Page<K, V>>::last_cursor(m.other.as_page());
    let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &lc) };

    // First element of the right page.
    let rc = <Page<K, V>>::first_cursor(m.modified.page.as_page());
    let rl = <Page<K, V>>::left_child(m.modified.page.as_page(), &rc);
    let mut freed = [0, 0];
    let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };
    freed[0] = m.modified.page.offset | b;
    let mut new_right = if let Some((k, v)) = m.modified.ins {
        if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::replace(
            txn,
            m.modified.page,
            m.modified.mutable,
            &m.modified.c1,
            &*k,
            &*v,
            m.modified.l,
            m.modified.r,
        )? {
            page
        } else {
            unreachable!()
        }
    } else {
        <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?
    };
    if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::put(
        txn,
        new_right.0,
        true,
        &rc,
        m.mid.0,
        m.mid.1,
        r0,
        rl,
    )? {
        new_right = page
    } else {
        unreachable!()
    };
    let new_left = <Page<K, V>>::del(txn, m.other, &lc, 0)?;
    if new_left.0.offset != m.other.offset {
        let hdr = &*header(m.other.as_page());
        let b = if hdr.is_dirty() { 1 } else { 0 };
        freed[1] = m.other.offset | b
    }
    Ok(Op::Rebalanced {
        l: new_left.0.offset,
        r: new_right.0.offset,
        k: unsafe { core::mem::transmute(k0) },
        v: unsafe { core::mem::transmute(v0) },
        freed,
    })
}

        if let Some((k, v, r)) = m.ins {

        if let Some((k, v)) = m.ins {

                Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)

                Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)

                Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)

                Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)

            } else {

            } else if m.l > 0 {

            } else {
                let mut c1 = m.c1.clone();
                Self::move_next(m.page.as_page(), &mut c1);
                Ok(Put::Ok(Self::update_left_child(txn, m.page, m.mutable, &c1, m.r)?))

    // Replace the left child of c1's last element with `r`.
    pub r: u64,

    pub ins: Option<(&'a K, &'a V, u64)>,

    pub ins: Option<(&'a K, &'a V)>,

        r: 0,

        debug!("decr_rc");

        debug!("/decr_rc");

    if p0 < cursor.pointer && cursor.pointer >= cursor.first_rc_level {

    debug!("pointer = {:?}", cursor.pointer);
    let mut k0 = MaybeUninit::uninit();
    let mut v0 = MaybeUninit::uninit();
    if p0 < cursor.pointer {

            for o in (&*k).page_offsets().chain((&*v).page_offsets()) {
                txn.incr_rc(o)?;

            if cursor.pointer >= cursor.first_rc_level {
                for o in (&*k).page_offsets().chain((&*v).page_offsets()) {
                    txn.incr_rc(o)?;
                }

            core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);
            core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);

    debug!("cursor.pointer = {:?}", cursor.pointer);

            concat(txn, curs, if p == p0 { Some(&curs0) } else { None }, last_op)?

            let kv = if p == p0 {
                unsafe { Some((
                    &*k0.as_ptr(),
                    &*v0.as_ptr()
                )) }
            } else {
                None
            };
            concat(txn, curs, kv, last_op)?

        debug!("candidate: {:?}", concat);

        debug!("page = {:?}, c0 = {:?}, c1 = {:?}", curs.page.offset, c0, c1);
        debug!("concat = {:?}" ,concat);

        debug!("merge = {:?}", merge);

        debug!("merge: {:?}", merge);

                    r: 0,

                    ins: Some((k, v, r)),

                    r,
                    ins: Some((k, v)),

                let (l, r, ins, skip_first) = if cursor.pointer == p0 {
                    let l = P::left_child(page.0.as_page(), &c1);
                    let k = unsafe { &*k0.as_ptr() };
                    let v = unsafe { &*v0.as_ptr() };
                    (l, page.0.offset, Some((k, v)), true)
                } else if concat.mod_is_left {
                    (page.0.offset, 0, None, false)
                } else {
                    (0, page.0.offset, None, false)
                };

                    l: page.0.offset,
                    ins: None,

                    l,
                    r,
                    ins,

                    skip_first: false,

                    skip_first,

                // Here, if we are at cursor.pointer == p0, the
                // replacement has been either inserted into one of
                // {left, right}, or is the split key/value
                // itself. Therefore, we just have to delete the
                // key/value selected for deletion in page p0 (the
                // current page).

                    ins: Some((split_key, split_value, right.0.offset)),

                    r: right.0.offset,
                    ins: Some((split_key, split_value)),

                    skip_first: false,

                    skip_first: cursor.pointer == p0,

                if cursor.pointer + 1 >= cursor.first_rc_level {

                // If the split key is the replacement element, we
                // have already increased its counter when we deleted
                // it from its original position at the bottom of the
                // tree.
                if cursor.pointer + 1 >= cursor.first_rc_level && (split_key as *const K) != k0.as_ptr() {

    debug!("find_min: {:?} {:?} {:?}", cur.page, cursor.pointer, left_page);

    debug!("find_min: cursor.pointer = {:?}", cursor.pointer);

    curs0: Option<&PageCursor<T, K, V, P>>,

    curs0: Option<(&'a K, &'a V)>,

    if let Some(curs0) = curs0 {

    if let Some((k0, v0)) = curs0 {

        let (k, v, _) =
            unsafe { P::unchecked_current(curs0.page.as_page(), curs0.cursor.as_ref().unwrap()) };

            mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v)) },

            mid: (k0, v0),

            // Not the last element of the page.

            // Last element of the page.

use log::*;

    /*

    let d = 10;
    for i in 0..d {
        debug!("deleting {:?}", (i*i)%1_000_000);
        debug::debug(&txn, &db, &format!("debug{}", i), true);
        del(&mut txn, &mut db, &((i * i) % 1_000_000), None).unwrap();
    }
    debug::debug(&txn, &db, "debug_final", true);
    txn.commit().unwrap();
     */

pub fn del_mid() {
    type B = btree::page::Page<u64, ()>;
    env_logger::try_init().unwrap_or(());
    let env = Env::new_anon(409600000).unwrap();
    let mut txn = Env::mut_txn_begin(&env).unwrap();
    let mut db: Db<_, u64, (), B> = create_db(&mut txn).unwrap();
    let n = 2_000 as u64;
    let now = std::time::SystemTime::now();
    let mut values = Vec::with_capacity(n as usize);
    for i in 0..n - 1 {
        if put(&mut txn, &mut db, &i, &()).unwrap() {
            values.push(i);
        }
    }
    debug!("==============================");
    debug::debug(&txn, &db, "debug_pre", true);
    del(&mut txn, &mut db, &1274, None).unwrap();
    debug::debug(&txn, &db, "debug_post", true);
    debug!("==============================");
    del(&mut txn, &mut db, &1529, None).unwrap();
    debug::debug(&txn, &db, "debug_post2", true);
    assert!(!del(&mut txn, &mut db, &(n + 1), None).unwrap());
    // for i in 0..400 {
    //     debug!("============== {:?}", i);
    //     del(&mut txn, &mut db, &i, None).unwrap();
    // }
}
#[test]

    let n = 1000 as u64;

    let n = 2_000 as u64;

    debug!("==============================");
    debug::debug(&txn, &db, "debug_pre", true);
    del(&mut txn, &mut db, &1019, None).unwrap();
    debug::debug(&txn, &db, "debug_post", true);
    for i in 0..512 {
        debug!("============== {:?}", i);
        del(&mut txn, &mut db, &i, None).unwrap();
    }
    debug!("================= done");
    let _db3 = fork_db(&mut txn, &db).unwrap();
    for i in 1530..1531 {
        debug!("============== {:?}", i);
        debug::debug(&txn, &db, "debug_pre", true);
        del(&mut txn, &mut db, &i, None).unwrap();
        debug::debug(&txn, &db, "debug_post", true);
    }
    debug!("================= done");