mod leonardo;
mod subheap;
mod layout;
use std::fmt::Debug;
use leonardo::leonardo;
use subheap::SubHeapMut;
fn sift_down<T: Ord + Debug>(heap: &mut SubHeapMut<T>) {
let (mut this_value, mut children) = heap.destructure_mut();
loop {
if children.is_none() {
break;
}
let (fst_child, snd_child) = children.unwrap();
let mut next_heap = if fst_child.value() > snd_child.value() {
fst_child
} else {
snd_child
};
if &*this_value >= next_heap.value() {
break;
}
std::mem::swap(this_value, next_heap.value_mut());
match next_heap.into_components() {
(v, n) => {
this_value = v;
children = n;
}
}
}
}
fn restring<T : Ord + Debug>(mut subheap_iter: layout::IterMut<T>) {
match subheap_iter.next() {
Some(mut this_subheap) => {
for mut next_subheap in subheap_iter {
if next_subheap.value() <= this_subheap.value() {
break;
}
std::mem::swap(next_subheap.value_mut(), this_subheap.value_mut());
sift_down(&mut next_subheap);
this_subheap = next_subheap;
}
}
None => {}
}
}
fn balance_after_push<T: Ord + Debug>(heap_data: &mut [T], layout: &layout::Layout) {
assert_eq!(heap_data.len(), layout.len());
sift_down(&mut layout.iter(heap_data).next().unwrap());
restring(layout.iter(heap_data));
}
fn balance_after_pop<T: Ord + Debug>(heap_data: &mut [T], layout: &layout::Layout) {
{
let mut subheap_iter = layout.iter(heap_data);
match (subheap_iter.next(), subheap_iter.next()) {
(Some(fst), Some(snd)) => {
if snd.order - fst.order != 1 {
return
}
}
_ => {
return;
}
}
}
{
let mut subheaps_from_snd = layout.iter(heap_data);
subheaps_from_snd.next();
restring(subheaps_from_snd);
}
{
let subheaps_from_fst = layout.iter(heap_data);
restring(subheaps_from_fst);
}
}
#[derive(Debug)]
pub struct Iter<'a, T: 'a> {
heap_data: &'a mut [T],
layout: layout::Layout,
}
impl<'a, T : Ord + Debug> Iterator for Iter<'a, T>
{
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
self.layout.pop();
if self.heap_data.len() != 0 {
let mut heap_data = std::mem::replace(&mut self.heap_data, &mut []);
let (result, rest_data) = heap_data.split_last_mut().unwrap();
self.heap_data = rest_data;
balance_after_pop(self.heap_data, &self.layout);
Some(&*result)
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.heap_data.len(), Some(self.heap_data.len()))
}
}
#[derive(Debug)]
pub struct Drain<'a, T: 'a> {
heap: &'a mut LeonardoHeap<T>,
}
impl<'a, T: Ord + Debug> Iterator for Drain<'a, T>
{
type Item = T;
fn next(&mut self) -> Option<T> {
self.heap.pop()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.heap.len(), Some(self.heap.len()))
}
}
#[derive(Debug)]
pub struct LeonardoHeap<T> {
data: Vec<T>,
layout: layout::Layout,
}
impl<T: Ord + Debug> LeonardoHeap<T> {
pub fn new() -> Self {
LeonardoHeap {
data: Vec::new(),
layout: layout::Layout::new(),
}
}
pub fn with_capacity(capacity: usize) -> Self {
LeonardoHeap {
data: Vec::with_capacity(capacity),
layout: layout::Layout::new(),
}
}
pub fn capacity(&self) -> usize {
self.data.capacity()
}
pub fn reserve(&mut self, additional: usize) {
self.data.reserve(additional)
}
pub fn reserve_exact(&mut self, additional: usize) {
self.data.reserve_exact(additional)
}
pub fn shrink_to_fit(&mut self) {
self.data.shrink_to_fit()
}
pub fn retain<F>(&mut self, f: F)
where F: FnMut(&T) -> bool
{
self.data.retain(f);
self.heapify();
}
pub fn clear(&mut self) {
self.data.clear();
self.layout = layout::Layout::new();
}
pub fn len(&self) -> usize {
self.data.len()
}
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
pub fn dedup(&mut self) {
self.sort();
self.data.dedup();
self.heapify();
}
fn heapify(&mut self) {
let mut layout = layout::Layout::new();
for i in 0..self.data.len() {
balance_after_push(&mut self.data[0..i], &layout);
layout.push();
}
}
pub fn sort(&mut self) {
let mut layout = self.layout.clone();
for i in (0..self.data.len()).rev() {
layout.pop();
balance_after_pop(&mut self.data[0..i], &layout);
}
}
pub fn push(&mut self, item: T) {
self.data.push(item);
self.layout.push();
balance_after_push(self.data.as_mut_slice(), &self.layout);
}
pub fn peek(&self) -> Option<&T> {
self.data.get(self.data.len())
}
pub fn pop(&mut self) -> Option<T> {
let result = self.data.pop();
self.layout.pop();
balance_after_pop(self.data.as_mut_slice(), &self.layout);
result
}
pub fn iter(&mut self) -> Iter<T> {
Iter {
heap_data: self.data.as_mut_slice(),
layout: self.layout.clone(),
}
}
pub fn drain(&mut self) -> Drain<T> {
Drain {
heap: self,
}
}
}
#[cfg(test)]
mod tests {
extern crate rand;
use self::rand::Rng;
use layout;
use subheap::SubHeapMut;
use {LeonardoHeap, Iter, restring, sift_down, balance_after_push, balance_after_pop};
#[test]
fn test_sift_down_zero() {
let mut subheap_data = [1];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 0));
assert_eq!(subheap_data, [1]);
}
#[test]
fn test_sift_down_one() {
let mut subheap_data = [1];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 1));
assert_eq!(subheap_data, [1]);
}
#[test]
fn test_sift_down_two() {
let mut subheap_data = [3, 2, 1];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 2));
assert_eq!(subheap_data, [1, 2, 3]);
let mut subheap_data = [3, 5, 4];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 2));
assert_eq!(subheap_data, [3, 4, 5]);
let mut subheap_data = [6, 7, 8];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 2));
assert_eq!(subheap_data, [6, 7, 8]);
}
#[test]
fn test_sift_down_three() {
let mut subheap_data = [1, 2, 3, 4, 5];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [1, 2, 3, 4, 5]);
let mut subheap_data = [1, 2, 3, 5, 4];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [1, 2, 3, 4, 5]);
let mut subheap_data = [1, 2, 5, 4, 3];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [1, 2, 3, 4, 5]);
let mut subheap_data = [2, 3, 5, 4, 1];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [2, 1, 3, 4, 5]);
let mut subheap_data = [3, 2, 5, 4, 1];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [1, 2, 3, 4, 5]);
}
#[test]
fn test_sift_down_sorting() {
let mut subheap_data = [5, 5, 4];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 2));
assert_eq!(subheap_data, [4, 5, 5]);
let mut subheap_data = [1, 2, 4, 4, 3];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 3));
assert_eq!(subheap_data, [1, 2, 3, 4, 4]);
}
#[test]
#[should_panic]
fn test_sift_down_wrong_order() {
let mut subheap_data : [i32; 0] = [];
sift_down(&mut SubHeapMut::new(&mut subheap_data, 0));
}
#[test]
fn test_balance_after_push_first() {
let mut subheap_data = [1];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(1));
assert_eq!(subheap_data, [1]);
}
#[test]
fn test_balance_after_push_second() {
let mut subheap_data = [1, 2];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(2));
assert_eq!(subheap_data, [1, 2]);
let mut subheap_data = [2, 1];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(2));
assert_eq!(subheap_data, [1, 2]);
}
#[test]
fn test_balance_after_push_merge() {
let mut subheap_data = [1, 2, 3];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(3));
assert_eq!(subheap_data, [1, 2, 3]);
let mut subheap_data = [1, 3, 2];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(3));
assert_eq!(subheap_data, [1, 2, 3]);
}
#[test]
#[should_panic]
fn test_balance_after_push_mismatched_lengths() {
let mut subheap_data = [1, 2, 3, 4];
balance_after_push(&mut subheap_data, &layout::Layout::new_from_len(12));
}
#[test]
fn test_balance_after_pop_empty() {
let mut subheap_data : [i32; 0]= [];
balance_after_pop(&mut subheap_data, &layout::Layout::new_from_len(0));
assert_eq!(subheap_data, []);
}
#[test]
fn test_balance_after_pop_one() {
let mut heap_data = [1];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(1));
assert_eq!(heap_data, [1]);
}
#[test]
fn test_balance_after_pop_two() {
let mut heap_data = [1, 2];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(2));
assert_eq!(heap_data, [1, 2]);
let mut heap_data = [2, 1];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(2));
assert_eq!(heap_data, [1, 2]);
}
#[test]
fn test_balance_after_pop_split_heaps() {
let mut heap_data = [1, 2, 3, 4, 5, 6, 7];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
let mut heap_data = [1, 2, 3, 4, 5, 7, 6];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
let mut heap_data = [1, 2, 3, 4, 6, 5, 7];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
let mut heap_data = [1, 2, 3, 4, 7, 5, 6];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
let mut heap_data = [1, 2, 3, 4, 6, 7, 5];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
let mut heap_data = [1, 2, 3, 4, 7, 6, 5];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(7));
assert_eq!(heap_data, [1, 2, 3, 4, 5, 6, 7]);
}
#[test]
fn test_balance_after_pop_restring_after_sift() {
let mut heap_data = [
1, 2, 3, 4, 5, 6, 10, 11, 12,
9, 7, 13,
8
];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(13));
assert_eq!(heap_data, [
1, 2, 3, 4, 5, 6, 9, 10, 11,
8, 7, 12,
13,
]);
}
#[test]
fn test_balance_after_pop_mutiple_layers() {
let mut heap_data = [
3, 0, 5, 1, 9, 2, 6, 7, 10,
4,
8,
];
balance_after_pop(&mut heap_data, &layout::Layout::new_from_len(11));
assert_eq!(heap_data, [
3, 0, 4, 1, 5, 2, 6, 7, 8,
9,
10,
]);
}
#[test]
#[should_panic]
fn test_balance_after_pop_mismatched_lengths() {
let mut subheap_data = [1, 2, 3, 4];
balance_after_pop(&mut subheap_data, &layout::Layout::new_from_len(12));
}
#[test]
fn test_push_pop() {
let mut heap = LeonardoHeap::new();
heap.push(4);
heap.push(1);
heap.push(2);
heap.push(3);
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
}
#[test]
fn test_random() {
let mut rng = rand::thread_rng();
let mut inputs : Vec<i32> = (0..200).collect();
let mut expected = inputs.clone();
expected.sort_by(|a, b| b.cmp(a));
rng.shuffle(inputs.as_mut_slice());
let mut heap = LeonardoHeap::new();
for input in inputs {
heap.push(input.clone());
}
let mut outputs: Vec<i32> = Vec::new();
loop {
match heap.pop() {
Some(output) => {
outputs.push(output);
}
None => {
break;
}
}
}
assert_eq!(outputs, expected);
}
#[test]
fn test_sort_random() {
let mut rng = rand::thread_rng();
let mut inputs : Vec<i32> = (0..200).collect();
let mut expected = inputs.clone();
expected.sort();
rng.shuffle(inputs.as_mut_slice());
let mut heap = LeonardoHeap::new();
for input in &inputs {
heap.push(input.clone());
}
heap.sort();
assert_eq!(heap.data, expected);
}
#[test]
fn test_iter() {
let mut heap = LeonardoHeap::new();
heap.push(4);
heap.push(1);
heap.push(2);
heap.push(3);
let mut heap_iter = heap.iter();
let mut var = 4;
assert_eq!(heap_iter.next(), Some(&var));
var = 3;
assert_eq!(heap_iter.next(), Some(&var));
var = 2;
assert_eq!(heap_iter.next(), Some(&var));
var = 1;
assert_eq!(heap_iter.next(), Some(&var));
}
}