<commit_before>use std::sync::Arc;
use std::cmp;
use std::iter;
pub use super::heap::Heap;

#[derive(Debug)]
pub struct BinomialHeap<T> {
	trees: Vec<Option<Link<T>>>,
}

type Link<T> = Arc<Node<T>>;

#[derive(Clone, Hash, Debug)]
struct Node<T> {
	elem: T,
	children: Vec<Link<T>>,
}

fn link<T: Ord + Clone>(a: &Link<T>, b: &Link<T>) -> Link<T> {
	let (smaller, bigger) = if a.elem < b.elem { (a, b) } else { (b, a) };
	let mut new_children = Vec::with_capacity(smaller.children.len() + 1);
	new_children.extend(smaller.children.iter().cloned());
	new_children.push(bigger.clone());
	Arc::new(Node { elem: smaller.elem.clone(), children: new_children })
}

impl <T: Ord + Clone> Heap<T> for BinomialHeap<T> {
	fn empty() -> Self {
		BinomialHeap { trees: Vec::new() }
	}

	fn is_empty(&self) -> bool {
		self.trees.is_empty()
	}

	fn insert(&self, item: T) -> Self {
		BinomialHeap { trees: vec![
			Some(Arc::new(Node { elem: item, children: Vec::new()}))
		]}.merge(self)
	}

	fn merge<'a>(&self, other: &Self) -> Self {
		let cap = cmp::max(self.trees.len(), other.trees.len()) + 1;
		let mut result: Vec<Option<Link<T>>> = Vec::with_capacity(cap);
		let mut c: Option<Link<T>> = None;

		// Create infinite interator of Option<&Link<T>>
		let iter_self = self.trees.iter().map(Option::as_ref).chain(iter::repeat(None));
		let iter_other = other.trees.iter().map(Option::as_ref).chain(iter::repeat(None));
		// Link trees of equal rank, carrying the added trees up a rank
		for ((a, b), _) in iter_self.zip(iter_other).zip(0..cap) {
			result.push( match (a, b, c.take()) {
				(None, None, None) => None,
				(Some(x), None, None) => Some(x.clone()),
				(None, Some(y), None) => Some(y.clone()),
				(None, None, Some(z)) => Some(z.clone()),
				(Some(x), Some(y), None) => { c = Some(link(x,y)); None }
				(Some(x), None, Some(z)) => { c = Some(link(x,&z)); None }
				(None, Some(y), Some(z)) => { c = Some(link(y,&z)); None }
				(Some(x), Some(y), Some(z)) => { c = Some(link(x,y)); Some(z) }
			});
		}
		if let Some(&None) = result.last() {
			result.pop();
		}
		BinomialHeap { trees: result }<commit_msg>Fixed None for binomial heap<commit_after>use std::sync::Arc;
use std::cmp;
use std::iter;
pub use super::heap::Heap;

#[derive(Debug)]
pub struct BinomialHeap<T> {
	trees: Vec<Option<Link<T>>>,
}

type Link<T> = Arc<Node<T>>;

#[derive(Clone, Hash, Debug)]
struct Node<T> {
	elem: T,
	children: Vec<Link<T>>,
}

fn link<T: Ord + Clone>(a: &Link<T>, b: &Link<T>) -> Link<T> {
	let (smaller, bigger) = if a.elem < b.elem { (a, b) } else { (b, a) };
	let mut new_children = Vec::with_capacity(smaller.children.len() + 1);
	new_children.extend(smaller.children.iter().cloned());
	new_children.push(bigger.clone());
	Arc::new(Node { elem: smaller.elem.clone(), children: new_children })
}

impl <T: Ord + Clone> Heap<T> for BinomialHeap<T> {
	fn empty() -> Self {
		BinomialHeap { trees: Vec::new() }
	}

	fn is_empty(&self) -> bool {
		self.trees.is_empty()
	}

	fn insert(&self, item: T) -> Self {
		BinomialHeap { trees: vec![
			Some(Arc::new(Node { elem: item, children: Vec::new()}))
		]}.merge(self)
	}

	fn merge<'a>(&self, other: &Self) -> Self {
		let cap = cmp::max(self.trees.len(), other.trees.len()) + 1;
		let mut result: Vec<Option<Link<T>>> = Vec::with_capacity(cap);
		let mut c: Option<Link<T>> = None;

		// Create infinite interator of Option<&Link<T>>
		let iter_self = self.trees.iter().map(Option::as_ref).chain(iter::repeat(None));
		let iter_other = other.trees.iter().map(Option::as_ref).chain(iter::repeat(None));
		// Link trees of equal rank, carrying the added trees up a rank
		for ((a, b), _) in iter_self.zip(iter_other).zip(0..cap) {
			result.push( match (a, b, c.take()) {
				(None, None, None) => None,
				(Some(x), None, None) => Some(x.clone()),
				(None, Some(y), None) => Some(y.clone()),
				(None, None, Some(z)) => Some(z.clone()),
				(Some(x), Some(y), None) => { c = Some(link(x,y)); None }
				(Some(x), None, Some(z)) => { c = Some(link(x,&z)); None }
				(None, Some(y), Some(z)) => { c = Some(link(y,&z)); None }
				(Some(x), Some(y), Some(z)) => { c = Some(link(x,y)); Some(z) }
			});
		}
		while let Some(&None) = result.last() {
			result.pop();
		}
		BinomialHeap { trees: result }
{'fraction_non_alphanumeric': 0.22545796148426492, 'fraction_numerical': 0.0014091122592766556, 'mean_word_length': 4.162424242424242, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 79, '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': '3786720', 'n_tokens_mistral': 1789, 'n_tokens_neox': 1680, 'n_words': 384}