<commit_before>use applied::interval::{Interval, IntervalNode};
use base::{TeardownTree, TeardownTreeInternal, lefti, righti, parenti, Sink};
use base::drivers::{consume_ptr, consume_unchecked};
use base::BulkDeleteCommon;
use base::InternalAccess;
use std::{mem, cmp};

pub trait IntervalTeardownTree<Iv: Interval> {
    fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv>;
    fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>);
}

trait IntervalTreeInternal<Iv: Interval> {
    #[inline] fn update_maxb(&mut self, idx: usize);
}

trait IntervalDeleteRange<Iv: Interval> {
    fn delete_intersecting_ivl_rec<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize,
                                                              min_included: bool, sink: &mut S);
    fn descend_delete_intersecting_ivl_left<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize, with_slot: bool,
                                                                       min_included: bool, sink: &mut S) -> bool;
    fn descend_delete_intersecting_ivl_right<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize, with_slot: bool,
                                                                        min_included: bool, sink: &mut S) -> bool;
}



//trait IntervalDeleteRange<Iv: Interval> {
//    fn delete_with_driver<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S);
//
//    fn delete_range<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S);
//    fn delete_range_loop<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//
//    fn delete_range_min<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//    fn delete_range_max<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//
//    fn descend_delete_left<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize, with_slot: bool) -> bool;
//    fn descend_delete_right<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize, with_slot: bool) -> bool;
//}

trait PlainDelete<Iv: Interval> {
    #[inline] fn delete_idx(&mut self, idx: usize) -> Iv;
    #[inline] fn delete_max(&mut self, idx: usize) -> (Iv, Iv::K);
    #[inline] fn delete_min(&mut self, idx: usize) -> Iv;
}


impl<Iv: Interval> IntervalTreeInternal<Iv> for TeardownTreeInternal<IntervalNode<Iv>> {
    #[inline]
    fn update_maxb(&mut self, idx: usize) {
        let item = self.item_mut_unsafe(idx);

        let left_self_maxb =
            if self.has_left(idx) {
                cmp::max(&self.left(idx).item.maxb, item.ivl.b())
            } else {
                item.ivl.b()
            };
        item.maxb =
            if self.has_right(idx) {
                cmp::max(&self.right(idx).item.maxb, left_self_maxb)
            } else {
                left_self_maxb
            }.clone();
    }

}



impl<Iv: Interval> IntervalTeardownTree<Iv> for TeardownTree<IntervalNode<Iv>> {
    /// Deletes the item with the given key from the tree and returns it (or None).
    // TODO: accepting IntervalNode is super ugly, temporary solution only
    fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv> {
        self.internal().index_of(search).map(|idx| {
            self.internal().delete_idx(idx)
        })
    }

    #[inline]
    fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>) {
        self.internal().delete_intersecting_ivl_rec(search, idx, false, &mut self::IntervalSink { output: output });
    }
}


impl<Iv: Interval> PlainDelete<Iv> for TeardownTreeInternal<IntervalNode<Iv>> {
    #[inline]
    fn delete_idx(&mut self, idx: usize) -> Iv {
        debug_assert!(!self.is_nil(idx));

        let item = self.item_mut_unsafe(idx);

        let replacement: Iv = match (self.has_left(idx), self.has_right(idx)) {
            (false, false) => {
                let item = self.take(idx);
                return item.ivl
            },

            (true, false)  => {
                let (removed, left_maxb) = self.delete_max(lefti(idx));
                item.maxb = left_maxb;
                removed
            },

            (false, true)  => {
//                let (removed, right_maxb) = self.delete_min(righti(idx));
//                item.maxb = right_maxb;
                let removed = self.delete_min(righti(idx));
                if &item.maxb == removed.b() {
                    self.update_maxb(idx)
                } else { // maxb remains the same
                    debug_assert!(removed.b() < &item.maxb);
                }
                removed
            },

            (true, true)   => {
                let (removed, left_maxb) = self.delete_max(lefti(idx));
                if &item.maxb == removed.b() {
                    item.maxb = cmp::max(left_maxb, self.right(idx).item.maxb);
                } else { // maxb remains the same
                    debug_assert!(removed.b() < &item.maxb);
                }
                removed
            },
        };

        mem::replace(&mut item.ivl, replacement)
    }


    /// returns the removed max-item of this subtree and the old maxb (before removal)
    #[inline]
    // we attempt to reduce the number of memory accesses as much as possible; might be overengineered
    fn delete_max(&mut self, idx: usize) -> (Iv, Iv::K) {
        let max_idx = self.find_max(idx);

        let (removed, mut old_maxb, mut new_maxb) = if self.has_left(max_idx) {
            let item = self.item_mut_unsafe(max_idx);
            let (left_max, left_maxb) = self.delete_max(lefti(max_idx));
            let removed = mem::replace(&mut item.ivl, left_max);

            let old_maxb = mem::replace(&mut item.maxb, left_maxb.clone());
            (removed, old_maxb, Some(left_maxb))
        } else {
            let IntervalNode { ivl, maxb:old_maxb } = self.take(max_idx);
            (ivl, old_maxb, None)
        };
<commit_msg>properly update IntervalNode::maxb in PlainDelete for TeardownTreeInternal<commit_after>use applied::interval::{Interval, IntervalNode};
use base::{TeardownTree, TeardownTreeInternal, lefti, righti, parenti, Sink};
use base::drivers::{consume_ptr, consume_unchecked};
use base::BulkDeleteCommon;
use base::InternalAccess;
use std::{mem, cmp};

pub trait IntervalTeardownTree<Iv: Interval> {
    fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv>;
    fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>);
}

trait IntervalTreeInternal<Iv: Interval> {
    #[inline] fn update_maxb(&mut self, idx: usize);

    #[inline] fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv>;

    #[inline] fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>);
}

trait IntervalDeleteRange<Iv: Interval> {
    fn delete_intersecting_ivl_rec<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize,
                                                              min_included: bool, sink: &mut S);
    fn descend_delete_intersecting_ivl_left<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize, with_slot: bool,
                                                                       min_included: bool, sink: &mut S) -> bool;
    fn descend_delete_intersecting_ivl_right<S: Sink<IntervalNode<Iv>>>(&mut self, search: &Iv, idx: usize, with_slot: bool,
                                                                        min_included: bool, sink: &mut S) -> bool;
}



//trait IntervalDeleteRange<Iv: Interval> {
//    fn delete_with_driver<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S);
//
//    fn delete_range<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S);
//    fn delete_range_loop<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//
//    fn delete_range_min<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//    fn delete_range_max<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize);
//
//    fn descend_delete_left<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize, with_slot: bool) -> bool;
//    fn descend_delete_right<S: Sink<IntervalNode<Iv>>>(&mut self, drv: &mut S, idx: usize, with_slot: bool) -> bool;
//}

trait PlainDelete<Iv: Interval> {
    #[inline] fn delete_idx(&mut self, idx: usize) -> Iv;
    #[inline] fn delete_max(&mut self, idx: usize) -> (Iv, Iv::K);
    #[inline] fn delete_min(&mut self, idx: usize) -> Iv;
}


impl<Iv: Interval> IntervalTeardownTree<Iv> for TeardownTree<IntervalNode<Iv>> {
    /// Deletes the item with the given key from the tree and returns it (or None).
    // TODO: accepting IntervalNode is super ugly, temporary solution only
    #[inline]
    fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv> {
        self.internal().delete(search)
    }

    #[inline]
    fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>) {
        self.internal().delete_intersecting(search, idx, output)
    }
}


impl<Iv: Interval> IntervalTreeInternal<Iv> for TeardownTreeInternal<IntervalNode<Iv>> {
    /// Deletes the item with the given key from the tree and returns it (or None).
    // TODO: accepting IntervalNode is super ugly, temporary solution only
    #[inline]
    fn delete(&mut self, search: &IntervalNode<Iv>) -> Option<Iv> {
        self.index_of(search).map(|idx| {
            let removed = self.delete_idx(idx);
            let mut upd_idx = idx;
            while upd_idx != 0 {
                upd_idx = parenti(upd_idx);
                if removed.b() == &self.item(idx).maxb {
                    self.update_maxb(idx);
                } else {
                    break;
                }
            }
            removed
        })
    }

    #[inline]
    fn delete_intersecting(&mut self, search: &Iv, idx: usize, output: &mut Vec<Iv>) {
        self.delete_intersecting_ivl_rec(search, idx, false, &mut self::IntervalSink { output: output });
    }

    #[inline]
    fn update_maxb(&mut self, idx: usize) {
        let item = self.item_mut_unsafe(idx);

        let left_self_maxb =
            if self.has_left(idx) {
                cmp::max(&self.left(idx).item.maxb, item.ivl.b())
            } else {
                item.ivl.b()
            };
        item.maxb =
            if self.has_right(idx) {
                cmp::max(&self.right(idx).item.maxb, left_self_maxb)
            } else {
                left_self_maxb
            }.clone();
    }

}


impl<Iv: Interval> PlainDelete<Iv> for TeardownTreeInternal<IntervalNode<Iv>> {
    #[inline]
    fn delete_idx(&mut self, idx: usize) -> Iv {
        debug_assert!(!self.is_nil(idx));

        let item = self.item_mut_unsafe(idx);

        let replacement: Iv = match (self.has_left(idx), self.has_right(idx)) {
            (false, false) => {
                let item = self.take(idx);
                return item.ivl
            },

            (true, false)  => {
                let (removed, left_maxb) = self.delete_max(lefti(idx));
                item.maxb = left_maxb;
                removed
            },

            (false, true)  => {
//                let (removed, right_maxb) = self.delete_min(righti(idx));
//                item.maxb = right_maxb;
                let removed = self.delete_min(righti(idx));
                if &item.maxb == removed.b() {
                    self.update_maxb(idx)
                } else { // maxb remains the same
                    debug_assert!(removed.b() < &item.maxb);
                }
                removed
            },

            (true, true)   => {
                let (removed, left_maxb) = self.delete_max(lefti(idx));
                if &item.maxb == removed.b() {
                    item.maxb = cmp::max(left_maxb, self.right(idx).item.maxb.clone());
                } else { // maxb remains the same
                    debug_assert!(removed.b() < &item.maxb);
                }
                removed
            },
        };

        mem::replace(&mut item.ivl, replacement)
    }


    /// returns the removed max-item of this subtree and the old maxb (before removal)
    #[inline]
    // we attempt to reduce the number of memory accesses as much as possible; might be overengineered
    fn delete_max(&mut self, idx: usize) -> (Iv, Iv::K) {
        let max_idx = self.find_max(idx);

        let (removed, mut old_maxb, mut new_maxb) = if self.has_left(max_idx) {
            let item = self.item_mut_unsafe(max_idx);
            let (left_max, left_maxb) = self.delete_max(lefti(max_idx));
            let removed = mem::replace(&mut item.ivl, left_max);

            let old_maxb = mem::replace(&mut item.maxb, left_maxb.clone());
            (removed, old_maxb, Some(left_maxb))
        } else {
            let IntervalNode { ivl, maxb:old_maxb } = self.take(max_idx);
            (ivl, old_maxb, None)
        };

{'fraction_non_alphanumeric': 0.13731156760134344, 'fraction_numerical': 7.810669374365383e-05, 'mean_word_length': 2.2154696132596685, 'pattern_counts': {'":': 0, '<': 119, '<?xml version=': 0, '>': 147, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4484998', 'n_tokens_mistral': 4192, 'n_tokens_neox': 4162, 'n_words': 961}