<commit_before>use std::iter::{ IntoIterator };
use std::slice;
use std::cmp::Ordering;

use num::traits::{ Zero, Bounded };

use iter::{ self, Iter, UnionIter, IntersectionIter, DifferenceIter, SymmetricDifferenceIter };
use container::{ Container };
use util::{ self, Halveable, ExtInt };

use RoaringBitmap as RB;

#[inline]
pub fn new<Size: ExtInt + Halveable>() -> RB<Size> {
    RB { containers: Vec::new() }
}

pub fn insert<Size: ExtInt + Halveable>(this: &mut RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    let container = match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => &mut this.containers[loc],
        Err(loc) => {
            this.containers.insert(loc, Container::new(key));
            &mut this.containers[loc]
        },
    };
    container.insert(index)
}

pub fn remove<Size: ExtInt + Halveable>(this: &mut RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => {
            if this.containers[loc].remove(index) {
                if this.containers[loc].len() == Zero::zero() {
                    this.containers.remove(loc);
                }
                true
            } else {
                false
            }
        }
        _ => false,
    }
}

pub fn contains<Size: ExtInt + Halveable>(this: &RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => this.containers[loc].contains(index),
        Err(_) => false,
    }
}

#[inline]
pub fn clear<Size: ExtInt + Halveable>(this: &mut RB<Size>) {
    this.containers.clear();
}

#[inline]
pub fn is_empty<Size: ExtInt + Halveable>(this: &RB<Size>) -> bool {
    this.containers.is_empty()
}

pub fn len<Size: ExtInt + Halveable>(this: &RB<Size>) -> Size {
    this.containers
        .iter()
        .map(|container| container.len())
        .fold(Zero::zero(), |sum: Size, len| sum + util::cast(len))
}

#[inline]
pub fn iter<'a, Size: ExtInt + Halveable>(this: &'a RB<Size>) -> Iter<'a, Size> where <Size as Halveable>::HalfSize : 'a {
    iter::new(this.containers.iter())
}

fn pairs<'a, Size: ExtInt + Halveable>(this: &'a RB<Size>, other: &'a RB<Size>) -> Pairs<'a, Size> where <Size as Halveable>::HalfSize : 'a {
    Pairs::new(this.containers.iter(), other.containers.iter())
}

pub fn is_disjoint<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    pairs(this, other)
        .filter(|&(c1, c2)| c1.is_some() && c2.is_some())
        .all(|(c1, c2)| c1.unwrap().is_disjoint(c2.unwrap()))
}

pub fn is_subset<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    for pair in pairs(this, other) {
        match pair {
            (None, _) => { return true; },
            (_, None) => { return false; },
            (Some(c1), Some(c2)) => if !c1.is_subset(c2) { return false; },
        }
    }
    true
}

pub fn is_subset_opt<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    let tv = &this.containers;
    let ov = &other.containers;
    let tlen = tv.len();
    let olen = ov.len();
    if tlen > olen { return false; }
    let mut ti = 0;
    let mut oi = 0;
    loop {
        let tc = &tv[ti];
        let oc = &ov[oi];
        match tc.key().cmp(&oc.key()) {
            Ordering::Less => { return false; },
            Ordering::Equal => {
                if !tc.is_subset(&oc) { return false; }
                ti += 1;
                if ti >= tlen { return true; }
            },
            Ordering::Greater => (),<commit_msg>fixed error in is_subset I introduced prior :-/<commit_after>use std::iter::{ IntoIterator };
use std::slice;
use std::cmp::Ordering;

use num::traits::{ Zero, Bounded };

use iter::{ self, Iter, UnionIter, IntersectionIter, DifferenceIter, SymmetricDifferenceIter };
use container::{ Container };
use util::{ self, Halveable, ExtInt };

use RoaringBitmap as RB;

#[inline]
pub fn new<Size: ExtInt + Halveable>() -> RB<Size> {
    RB { containers: Vec::new() }
}

pub fn insert<Size: ExtInt + Halveable>(this: &mut RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    let container = match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => &mut this.containers[loc],
        Err(loc) => {
            this.containers.insert(loc, Container::new(key));
            &mut this.containers[loc]
        },
    };
    container.insert(index)
}

pub fn remove<Size: ExtInt + Halveable>(this: &mut RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => {
            if this.containers[loc].remove(index) {
                if this.containers[loc].len() == Zero::zero() {
                    this.containers.remove(loc);
                }
                true
            } else {
                false
            }
        }
        _ => false,
    }
}

pub fn contains<Size: ExtInt + Halveable>(this: &RB<Size>, value: Size) -> bool {
    let (key, index) = value.split();
    match this.containers.binary_search_by(|container| container.key().cmp(&key)) {
        Ok(loc) => this.containers[loc].contains(index),
        Err(_) => false,
    }
}

#[inline]
pub fn clear<Size: ExtInt + Halveable>(this: &mut RB<Size>) {
    this.containers.clear();
}

#[inline]
pub fn is_empty<Size: ExtInt + Halveable>(this: &RB<Size>) -> bool {
    this.containers.is_empty()
}

pub fn len<Size: ExtInt + Halveable>(this: &RB<Size>) -> Size {
    this.containers
        .iter()
        .map(|container| container.len())
        .fold(Zero::zero(), |sum: Size, len| sum + util::cast(len))
}

#[inline]
pub fn iter<'a, Size: ExtInt + Halveable>(this: &'a RB<Size>) -> Iter<'a, Size> where <Size as Halveable>::HalfSize : 'a {
    iter::new(this.containers.iter())
}

fn pairs<'a, Size: ExtInt + Halveable>(this: &'a RB<Size>, other: &'a RB<Size>) -> Pairs<'a, Size> where <Size as Halveable>::HalfSize : 'a {
    Pairs::new(this.containers.iter(), other.containers.iter())
}

pub fn is_disjoint<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    pairs(this, other)
        .filter(|&(c1, c2)| c1.is_some() && c2.is_some())
        .all(|(c1, c2)| c1.unwrap().is_disjoint(c2.unwrap()))
}

pub fn is_subset<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    for pair in pairs(this, other) {
        match pair {
            (None, _) => (),
            (_, None) => { return false; },
            (Some(c1), Some(c2)) => if !c1.is_subset(c2) { return false; },
        }
    }
    true
}

pub fn is_subset_opt<Size: ExtInt + Halveable>(this: &RB<Size>, other: &RB<Size>) -> bool {
    let tv = &this.containers;
    let ov = &other.containers;
    let tlen = tv.len();
    let olen = ov.len();
    if tlen > olen { return false; }
    let mut ti = 0;
    let mut oi = 0;
    loop {
        let tc = &tv[ti];
        let oc = &ov[oi];
        match tc.key().cmp(&oc.key()) {
            Ordering::Less => { return false; },
            Ordering::Equal => {
                if !tc.is_subset(&oc) { return false; }
                ti += 1;
                if ti >= tlen { return true; }
            },
            Ordering::Greater => (),
{'fraction_non_alphanumeric': 0.17867666755960354, 'fraction_numerical': 0.004018215912135012, 'mean_word_length': 2.588178760211437, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 117, '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': '7501296', 'n_tokens_mistral': 2569, 'n_tokens_neox': 2552, 'n_words': 593}