[rustc.git] / src / libcollections / tests / binary_heap.rs

// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use std::panic;
use std::collections::BinaryHeap;
use std::collections::binary_heap::{Drain, PeekMut};

#[test]
fn test_iterator() {
    let data = vec![5, 9, 3];
    let iterout = [9, 5, 3];
    let heap = BinaryHeap::from(data);
    let mut i = 0;
    for el in &heap {
        assert_eq!(*el, iterout[i]);
        i += 1;
    }
}

#[test]
fn test_iterator_reverse() {
    let data = vec![5, 9, 3];
    let iterout = vec![3, 5, 9];
    let pq = BinaryHeap::from(data);

    let v: Vec<_> = pq.iter().rev().cloned().collect();
    assert_eq!(v, iterout);
}

#[test]
fn test_move_iter() {
    let data = vec![5, 9, 3];
    let iterout = vec![9, 5, 3];
    let pq = BinaryHeap::from(data);

    let v: Vec<_> = pq.into_iter().collect();
    assert_eq!(v, iterout);
}

#[test]
fn test_move_iter_size_hint() {
    let data = vec![5, 9];
    let pq = BinaryHeap::from(data);

    let mut it = pq.into_iter();

    assert_eq!(it.size_hint(), (2, Some(2)));
    assert_eq!(it.next(), Some(9));

    assert_eq!(it.size_hint(), (1, Some(1)));
    assert_eq!(it.next(), Some(5));

    assert_eq!(it.size_hint(), (0, Some(0)));
    assert_eq!(it.next(), None);
}

#[test]
fn test_move_iter_reverse() {
    let data = vec![5, 9, 3];
    let iterout = vec![3, 5, 9];
    let pq = BinaryHeap::from(data);

    let v: Vec<_> = pq.into_iter().rev().collect();
    assert_eq!(v, iterout);
}

#[test]
fn test_peek_and_pop() {
    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
    let mut sorted = data.clone();
    sorted.sort();
    let mut heap = BinaryHeap::from(data);
    while !heap.is_empty() {
        assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
        assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
    }
}

#[test]
fn test_peek_mut() {
    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
    let mut heap = BinaryHeap::from(data);
    assert_eq!(heap.peek(), Some(&10));
    {
        let mut top = heap.peek_mut().unwrap();
        *top -= 2;
    }
    assert_eq!(heap.peek(), Some(&9));
}

#[test]
fn test_peek_mut_pop() {
    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
    let mut heap = BinaryHeap::from(data);
    assert_eq!(heap.peek(), Some(&10));
    {
        let mut top = heap.peek_mut().unwrap();
        *top -= 2;
        assert_eq!(PeekMut::pop(top), 8);
    }
    assert_eq!(heap.peek(), Some(&9));
}

#[test]
fn test_push() {
    let mut heap = BinaryHeap::from(vec![2, 4, 9]);
    assert_eq!(heap.len(), 3);
    assert!(*heap.peek().unwrap() == 9);
    heap.push(11);
    assert_eq!(heap.len(), 4);
    assert!(*heap.peek().unwrap() == 11);
    heap.push(5);
    assert_eq!(heap.len(), 5);
    assert!(*heap.peek().unwrap() == 11);
    heap.push(27);
    assert_eq!(heap.len(), 6);
    assert!(*heap.peek().unwrap() == 27);
    heap.push(3);
    assert_eq!(heap.len(), 7);
    assert!(*heap.peek().unwrap() == 27);
    heap.push(103);
    assert_eq!(heap.len(), 8);
    assert!(*heap.peek().unwrap() == 103);
}

#[test]
fn test_push_unique() {
    let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
    assert_eq!(heap.len(), 3);
    assert!(*heap.peek().unwrap() == box 9);
    heap.push(box 11);
    assert_eq!(heap.len(), 4);
    assert!(*heap.peek().unwrap() == box 11);
    heap.push(box 5);
    assert_eq!(heap.len(), 5);
    assert!(*heap.peek().unwrap() == box 11);
    heap.push(box 27);
    assert_eq!(heap.len(), 6);
    assert!(*heap.peek().unwrap() == box 27);
    heap.push(box 3);
    assert_eq!(heap.len(), 7);
    assert!(*heap.peek().unwrap() == box 27);
    heap.push(box 103);
    assert_eq!(heap.len(), 8);
    assert!(*heap.peek().unwrap() == box 103);
}

fn check_to_vec(mut data: Vec<i32>) {
    let heap = BinaryHeap::from(data.clone());
    let mut v = heap.clone().into_vec();
    v.sort();
    data.sort();

    assert_eq!(v, data);
    assert_eq!(heap.into_sorted_vec(), data);
}

#[test]
fn test_to_vec() {
    check_to_vec(vec![]);
    check_to_vec(vec![5]);
    check_to_vec(vec![3, 2]);
    check_to_vec(vec![2, 3]);
    check_to_vec(vec![5, 1, 2]);
    check_to_vec(vec![1, 100, 2, 3]);
    check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
    check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
    check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
    check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
    check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
    check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
}

#[test]
fn test_empty_pop() {
    let mut heap = BinaryHeap::<i32>::new();
    assert!(heap.pop().is_none());
}

#[test]
fn test_empty_peek() {
    let empty = BinaryHeap::<i32>::new();
    assert!(empty.peek().is_none());
}

#[test]
fn test_empty_peek_mut() {
    let mut empty = BinaryHeap::<i32>::new();
    assert!(empty.peek_mut().is_none());
}

#[test]
fn test_from_iter() {
    let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];

    let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();

    for &x in &xs {
        assert_eq!(q.pop().unwrap(), x);
    }
}

#[test]
fn test_drain() {
    let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();

    assert_eq!(q.drain().take(5).count(), 5);

    assert!(q.is_empty());
}

#[test]
fn test_extend_ref() {
    let mut a = BinaryHeap::new();
    a.push(1);
    a.push(2);

    a.extend(&[3, 4, 5]);

    assert_eq!(a.len(), 5);
    assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);

    let mut a = BinaryHeap::new();
    a.push(1);
    a.push(2);
    let mut b = BinaryHeap::new();
    b.push(3);
    b.push(4);
    b.push(5);

    a.extend(&b);

    assert_eq!(a.len(), 5);
    assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
}

#[test]
fn test_append() {
    let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
    let mut b = BinaryHeap::from(vec![-20, 5, 43]);

    a.append(&mut b);

    assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
    assert!(b.is_empty());
}

#[test]
fn test_append_to_empty() {
    let mut a = BinaryHeap::new();
    let mut b = BinaryHeap::from(vec![-20, 5, 43]);

    a.append(&mut b);

    assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
    assert!(b.is_empty());
}

#[test]
fn test_extend_specialization() {
    let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
    let b = BinaryHeap::from(vec![-20, 5, 43]);

    a.extend(b);

    assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
}

#[test]
fn test_placement() {
    let mut a = BinaryHeap::new();
    &mut a <- 2;
    &mut a <- 4;
    &mut a <- 3;
    assert_eq!(a.peek(), Some(&4));
    assert_eq!(a.len(), 3);
    &mut a <- 1;
    assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
}

#[test]
fn test_placement_panic() {
    let mut heap = BinaryHeap::from(vec![1, 2, 3]);
    fn mkpanic() -> usize { panic!() }
    let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { &mut heap <- mkpanic(); }));
    assert_eq!(heap.len(), 3);
}

#[allow(dead_code)]
fn assert_covariance() {
    fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
        d
    }
}
Commit	Line	Data
c34b1796 AL	1	// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
	2	// file at the top-level directory of this distribution and at
	3	// http://rust-lang.org/COPYRIGHT.
	4	//
	5	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	6	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	7	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	8	// option. This file may not be copied, modified, or distributed
	9	// except according to those terms.
	10
32a655c1	11	use std::panic;
c34b1796	12	use std::collections::BinaryHeap;
32a655c1	13	use std::collections::binary_heap::{Drain, PeekMut};
c34b1796 AL	14
	15	#[test]
	16	fn test_iterator() {
	17	let data = vec![5, 9, 3];
	18	let iterout = [9, 5, 3];
9cc50fc6	19	let heap = BinaryHeap::from(data);
c34b1796 AL	20	let mut i = 0;
	21	for el in &heap {
	22	assert_eq!(*el, iterout[i]);
	23	i += 1;
	24	}
	25	}
	26
	27	#[test]
	28	fn test_iterator_reverse() {
	29	let data = vec![5, 9, 3];
	30	let iterout = vec![3, 5, 9];
9cc50fc6	31	let pq = BinaryHeap::from(data);
c34b1796 AL	32
	33	let v: Vec<_> = pq.iter().rev().cloned().collect();
	34	assert_eq!(v, iterout);
	35	}
	36
	37	#[test]
	38	fn test_move_iter() {
	39	let data = vec![5, 9, 3];
	40	let iterout = vec![9, 5, 3];
9cc50fc6	41	let pq = BinaryHeap::from(data);
c34b1796 AL	42
	43	let v: Vec<_> = pq.into_iter().collect();
	44	assert_eq!(v, iterout);
	45	}
	46
	47	#[test]
	48	fn test_move_iter_size_hint() {
	49	let data = vec![5, 9];
9cc50fc6	50	let pq = BinaryHeap::from(data);
c34b1796 AL	51
	52	let mut it = pq.into_iter();
	53
	54	assert_eq!(it.size_hint(), (2, Some(2)));
	55	assert_eq!(it.next(), Some(9));
	56
	57	assert_eq!(it.size_hint(), (1, Some(1)));
	58	assert_eq!(it.next(), Some(5));
	59
	60	assert_eq!(it.size_hint(), (0, Some(0)));
	61	assert_eq!(it.next(), None);
	62	}
	63
	64	#[test]
	65	fn test_move_iter_reverse() {
	66	let data = vec![5, 9, 3];
	67	let iterout = vec![3, 5, 9];
9cc50fc6	68	let pq = BinaryHeap::from(data);
c34b1796 AL	69
	70	let v: Vec<_> = pq.into_iter().rev().collect();
	71	assert_eq!(v, iterout);
	72	}
	73
	74	#[test]
	75	fn test_peek_and_pop() {
	76	let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
	77	let mut sorted = data.clone();
	78	sorted.sort();
9cc50fc6	79	let mut heap = BinaryHeap::from(data);
c34b1796 AL	80	while !heap.is_empty() {
	81	assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
	82	assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
	83	}
	84	}
	85
3157f602 XL	86	#[test]
	87	fn test_peek_mut() {
	88	let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
	89	let mut heap = BinaryHeap::from(data);
	90	assert_eq!(heap.peek(), Some(&10));
	91	{
	92	let mut top = heap.peek_mut().unwrap();
	93	*top -= 2;
	94	}
	95	assert_eq!(heap.peek(), Some(&9));
	96	}
	97
32a655c1 SL	98	#[test]
	99	fn test_peek_mut_pop() {
	100	let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
	101	let mut heap = BinaryHeap::from(data);
	102	assert_eq!(heap.peek(), Some(&10));
	103	{
	104	let mut top = heap.peek_mut().unwrap();
	105	*top -= 2;
	106	assert_eq!(PeekMut::pop(top), 8);
	107	}
	108	assert_eq!(heap.peek(), Some(&9));
	109	}
	110
c34b1796 AL	111	#[test]
c34b1796 AL	112	fn test_push() {
9cc50fc6	113	let mut heap = BinaryHeap::from(vec![2, 4, 9]);
c34b1796 AL	114	assert_eq!(heap.len(), 3);
	115	assert!(*heap.peek().unwrap() == 9);
	116	heap.push(11);
	117	assert_eq!(heap.len(), 4);
	118	assert!(*heap.peek().unwrap() == 11);
	119	heap.push(5);
	120	assert_eq!(heap.len(), 5);
	121	assert!(*heap.peek().unwrap() == 11);
	122	heap.push(27);
	123	assert_eq!(heap.len(), 6);
	124	assert!(*heap.peek().unwrap() == 27);
	125	heap.push(3);
	126	assert_eq!(heap.len(), 7);
	127	assert!(*heap.peek().unwrap() == 27);
	128	heap.push(103);
	129	assert_eq!(heap.len(), 8);
	130	assert!(*heap.peek().unwrap() == 103);
	131	}
	132
	133	#[test]
	134	fn test_push_unique() {
9cc50fc6	135	let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
c34b1796 AL	136	assert_eq!(heap.len(), 3);
	137	assert!(*heap.peek().unwrap() == box 9);
	138	heap.push(box 11);
	139	assert_eq!(heap.len(), 4);
	140	assert!(*heap.peek().unwrap() == box 11);
	141	heap.push(box 5);
	142	assert_eq!(heap.len(), 5);
	143	assert!(*heap.peek().unwrap() == box 11);
	144	heap.push(box 27);
	145	assert_eq!(heap.len(), 6);
	146	assert!(*heap.peek().unwrap() == box 27);
	147	heap.push(box 3);
	148	assert_eq!(heap.len(), 7);
	149	assert!(*heap.peek().unwrap() == box 27);
	150	heap.push(box 103);
	151	assert_eq!(heap.len(), 8);
	152	assert!(*heap.peek().unwrap() == box 103);
	153	}
	154
c34b1796	155	fn check_to_vec(mut data: Vec<i32>) {
9cc50fc6	156	let heap = BinaryHeap::from(data.clone());
c34b1796 AL	157	let mut v = heap.clone().into_vec();
	158	v.sort();
	159	data.sort();
	160
	161	assert_eq!(v, data);
	162	assert_eq!(heap.into_sorted_vec(), data);
	163	}
	164
	165	#[test]
	166	fn test_to_vec() {
	167	check_to_vec(vec![]);
	168	check_to_vec(vec![5]);
	169	check_to_vec(vec![3, 2]);
	170	check_to_vec(vec![2, 3]);
	171	check_to_vec(vec![5, 1, 2]);
	172	check_to_vec(vec![1, 100, 2, 3]);
	173	check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
	174	check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
	175	check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
	176	check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
	177	check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
	178	check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
	179	check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
	180	}
	181
	182	#[test]
	183	fn test_empty_pop() {
	184	let mut heap = BinaryHeap::<i32>::new();
	185	assert!(heap.pop().is_none());
	186	}
	187
	188	#[test]
	189	fn test_empty_peek() {
	190	let empty = BinaryHeap::<i32>::new();
	191	assert!(empty.peek().is_none());
	192	}
	193
3157f602 XL	194	#[test]
	195	fn test_empty_peek_mut() {
	196	let mut empty = BinaryHeap::<i32>::new();
	197	assert!(empty.peek_mut().is_none());
	198	}
	199
c34b1796 AL	200	#[test]
	201	fn test_from_iter() {
	202	let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
	203
	204	let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
	205
	206	for &x in &xs {
	207	assert_eq!(q.pop().unwrap(), x);
	208	}
	209	}
	210
	211	#[test]
	212	fn test_drain() {
	213	let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
	214
	215	assert_eq!(q.drain().take(5).count(), 5);
	216
	217	assert!(q.is_empty());
	218	}
62682a34 SL	219
	220	#[test]
	221	fn test_extend_ref() {
	222	let mut a = BinaryHeap::new();
	223	a.push(1);
	224	a.push(2);
	225
	226	a.extend(&[3, 4, 5]);
	227
	228	assert_eq!(a.len(), 5);
	229	assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
	230
	231	let mut a = BinaryHeap::new();
	232	a.push(1);
	233	a.push(2);
	234	let mut b = BinaryHeap::new();
	235	b.push(3);
	236	b.push(4);
	237	b.push(5);
	238
	239	a.extend(&b);
	240
	241	assert_eq!(a.len(), 5);
	242	assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
	243	}
a7813a04 XL	244
	245	#[test]
	246	fn test_append() {
	247	let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
	248	let mut b = BinaryHeap::from(vec![-20, 5, 43]);
	249
	250	a.append(&mut b);
	251
	252	assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
	253	assert!(b.is_empty());
	254	}
	255
	256	#[test]
	257	fn test_append_to_empty() {
	258	let mut a = BinaryHeap::new();
	259	let mut b = BinaryHeap::from(vec![-20, 5, 43]);
	260
	261	a.append(&mut b);
	262
	263	assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
	264	assert!(b.is_empty());
	265	}
	266
	267	#[test]
	268	fn test_extend_specialization() {
	269	let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
	270	let b = BinaryHeap::from(vec![-20, 5, 43]);
	271
	272	a.extend(b);
	273
	274	assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
	275	}
5bcae85e	276
32a655c1 SL	277	#[test]
	278	fn test_placement() {
	279	let mut a = BinaryHeap::new();
	280	&mut a <- 2;
	281	&mut a <- 4;
	282	&mut a <- 3;
	283	assert_eq!(a.peek(), Some(&4));
	284	assert_eq!(a.len(), 3);
	285	&mut a <- 1;
	286	assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
	287	}
	288
	289	#[test]
	290	fn test_placement_panic() {
	291	let mut heap = BinaryHeap::from(vec![1, 2, 3]);
	292	fn mkpanic() -> usize { panic!() }
	293	let _ = panic::catch_unwind(panic::AssertUnwindSafe(\|\| { &mut heap <- mkpanic(); }));
	294	assert_eq!(heap.len(), 3);
	295	}
	296
5bcae85e SL	297	#[allow(dead_code)]
5bcae85e SL	298	fn assert_covariance() {
c30ab7b3 SL	299	fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
	300	d
	301	}
5bcae85e	302	}