<commit_before>use std::collections::BTreeMap;
use index::EntryKey;
use index::Slice;
use std::fmt::Debug;
use std::mem;
use std::sync::Arc;
use std::collections::BTreeSet;
use parking_lot::RwLock;

// LevelTree items cannot been added or removed individually
// Items must been merged from higher level in bulk
// Deletion will be performed when merging to or from higher level tree
// Because tree update will not to be performed in parallel. Unlike memtable, a single r/w lock
// should be sufficient. Thus concurrency control will be simple and efficient.
pub struct LevelTree<S>
    where S: Slice<EntryKey> + SortableEntrySlice
{
    index: BTreeMap<EntryKey, SSIndex<S>>
}

type TombstoneSet = BTreeSet<EntryKey>;

struct SSIndex<S> where S: Slice<EntryKey> + SortableEntrySlice
{
    slice: S,
    tombstones: TombstoneSet
}

pub trait SortableEntrySlice: Sized + Slice<EntryKey>
{
    fn merge_sorted_with(
        &mut self,
        y_slice: &mut [EntryKey],
        xlen: &mut usize,
        ylen: &mut usize,
        xtombstones: &mut TombstoneSet,
        ytombstones: &mut TombstoneSet
    ) -> Self {
        let total_len = *xlen + *ylen;
        let mut x_pos = 0;
        let mut y_pos = 0;
        let mut pos = 0;
        let mut new_x = Self::init();
        let mut new_y = Self::init();
        {
            let mut x_slice = self.as_slice();
            let x_slice_len = x_slice.len();
            debug_assert!(*ylen <= x_slice_len);
            let mut new_slice_x = new_x.as_slice();
            let mut new_slice_y = new_y.as_slice();
            let mut new_x_len = 0;
            let mut new_y_len = 0;
            let mut use_slice_at = | slice: &mut[EntryKey], slice_pos: &mut usize| {
                let item = mem::replace(&mut slice[*slice_pos], EntryKey::default());
                *slice_pos += 1;
                if xtombstones.remove(&item) || ytombstones.remove(&item) {
                    None
                } else {
                    Some(item)
                }
            };
            while pos < total_len {
                let item_or_removed = if x_pos < *xlen && y_pos < *ylen {
                    if x_slice[x_pos] < y_slice[y_pos] {
                        use_slice_at(x_slice, &mut x_pos)
                    } else {
                        use_slice_at(y_slice, &mut y_pos)
                    }
                } else if x_pos < *xlen {
                    use_slice_at(x_slice, &mut x_pos)
                } else if y_pos < *ylen {
                    use_slice_at(y_slice, &mut y_pos)
                } else { unreachable!() };

                if let Some(item) = item_or_removed {
                    if pos < x_slice_len {
                        new_slice_x[pos] = item;
                        new_x_len += 1;
                    } else {
                        new_slice_y[pos - x_slice_len] = item;
                        new_y_len += 1;
                    }
                    pos += 1;
                }
            }
            *xlen = new_x_len;
            *ylen = new_y_len;
        }
        mem::swap(self, &mut new_x);
        return new_y;
    }
}

#[cfg(test)]
mod test {

}<commit_msg>break on search completed<commit_after>use std::collections::BTreeMap;
use index::EntryKey;
use index::Slice;
use std::fmt::Debug;
use std::mem;
use std::sync::Arc;
use std::collections::BTreeSet;
use parking_lot::RwLock;

// LevelTree items cannot been added or removed individually
// Items must been merged from higher level in bulk
// Deletion will be performed when merging to or from higher level tree
// Because tree update will not to be performed in parallel. Unlike memtable, a single r/w lock
// should be sufficient. Thus concurrency control will be simple and efficient.
pub struct LevelTree<S>
    where S: Slice<EntryKey> + SortableEntrySlice
{
    index: BTreeMap<EntryKey, SSIndex<S>>
}

type TombstoneSet = BTreeSet<EntryKey>;

struct SSIndex<S> where S: Slice<EntryKey> + SortableEntrySlice
{
    slice: S,
    tombstones: TombstoneSet
}

pub trait SortableEntrySlice: Sized + Slice<EntryKey>
{
    fn merge_sorted_with(
        &mut self,
        y_slice: &mut [EntryKey],
        xlen: &mut usize,
        ylen: &mut usize,
        xtombstones: &mut TombstoneSet,
        ytombstones: &mut TombstoneSet
    ) -> Self {
        let mut x_pos = 0;
        let mut y_pos = 0;
        let mut pos = 0;
        let mut new_x = Self::init();
        let mut new_y = Self::init();
        {
            let mut x_slice = self.as_slice();
            let x_slice_len = x_slice.len();
            debug_assert!(*ylen <= x_slice_len);
            let mut new_slice_x = new_x.as_slice();
            let mut new_slice_y = new_y.as_slice();
            let mut new_x_len = 0;
            let mut new_y_len = 0;
            let mut use_slice_at = | slice: &mut[EntryKey], slice_pos: &mut usize| {
                let item = mem::replace(&mut slice[*slice_pos], EntryKey::default());
                *slice_pos += 1;
                if xtombstones.remove(&item) || ytombstones.remove(&item) {
                    None
                } else {
                    Some(item)
                }
            };
            while pos < total_len {
                let item_or_removed = if x_pos < *xlen && y_pos < *ylen {
                    if x_slice[x_pos] < y_slice[y_pos] {
                        use_slice_at(x_slice, &mut x_pos)
                    } else {
                        use_slice_at(y_slice, &mut y_pos)
                    }
                } else if x_pos < *xlen {
                    use_slice_at(x_slice, &mut x_pos)
                } else if y_pos < *ylen {
                    use_slice_at(y_slice, &mut y_pos)
                } else {
                    break
                };

                if let Some(item) = item_or_removed {
                    if pos < x_slice_len {
                        new_slice_x[pos] = item;
                        new_x_len += 1;
                    } else {
                        new_slice_y[pos - x_slice_len] = item;
                        new_y_len += 1;
                    }
                    pos += 1;
                }
            }
            *xlen = new_x_len;
            *ylen = new_y_len;
        }
        mem::swap(self, &mut new_x);
        return new_y;
    }
}

#[cfg(test)]
mod test {

}
{'fraction_non_alphanumeric': 0.09720037747719408, 'fraction_numerical': 0.0028310789556464295, 'mean_word_length': 1.572411003236246, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1275003', 'n_tokens_mistral': 2011, 'n_tokens_neox': 1925, 'n_words': 515}