use super::*;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::cell::RefCell;
type Tracker = HashSet<usize>;
type TrackerRef = Rc<RefCell<Tracker>>;
type S = TestSelector;
struct TestNodeData {
v : usize,
tracker : TrackerRef,
}
struct TestNode {
data : RefCell<TestNodeData>,
ll : Link<TestNode, S>,
}
DlistDefineStaticSelector!(TestSelector, TestNode [ .ll ]);
type TestList = List<TestNode,S>;
impl TestNodeData {
fn new(v : usize, tracker : &TrackerRef) -> Self {
println!("creating node {}", v);
let inserted = tracker.borrow_mut().insert(v);
assert!(inserted);
TestNodeData { v, tracker : tracker.clone() }
}
}
impl Drop for TestNode {
fn drop(&mut self) {
let data = self.data.borrow();
println!("dropping node {}", data.v);
for p in &self.ll.pn { assert!(clone_option_cell(p).is_none()); }
let removed = data.tracker.borrow_mut().remove(&data.v);
assert!(removed);
}
}
fn cursor_val(c : &Cursor<TestNode,S>) -> isize {
c.as_ref().map_or(
-1,
|p| p.node.data.borrow().v as isize
)
}
fn require_eq(a : &Cursor<TestNode,S>, b : &Cursor<TestNode,S>,
context : &str) {
if Pointer::cursor_eq(a,b) { return }
panic!("at {}, {} != {}",
context, cursor_val(a), cursor_val(b));
}
fn consistency(l : &TestList, expect : &[usize]) {
println!("consistency expect={:?} ht={:?}",
expect,
l.ht.iter().map(cursor_val).collect::<Vec<_>>());
let mut vd : VecDeque<Cursor<TestNode,S>>
= VecDeque::with_capacity(3);
for _i in 0..2 { vd.push_back(None) }
vd.push_back(end!(l,HEAD^false).clone());
let mut i = 0;
loop {
let n = vd[2].clone();
vd.pop_front();
vd.push_back(n.as_ref().map_or(
None,
|n| get!(n,NEXT^false).clone()
));
let vdp : Vec<_> =vd.iter().map(|e| cursor_val(&e)).collect();
println!("consistency i={} vd={:?} pn={:?}",
i, &vdp,
match &vd[1] {
None => vec![],
Some(ref p) =>
p.ll.pn.iter()
.map(clone_option_cell)
.map(|x| cursor_val(&x))
.collect::<Vec<_>>()
}
);
if let Some(mid) = &n {
require_eq(&vd[0], &get!(mid,PREV^false), "L");
require_eq(&vd[2], &get!(mid,NEXT^false), "R");
assert_eq!(mid.data.borrow().v, expect[i]);
} else {
break
}
i += 1;
}
require_eq(&vd[0], &end!(l,TAIL^false), "T");
assert_eq!(i, expect.len());
}
macro_rules! extprep {
{ $l:ident, $tracker:ident, $expect:ident, $count:expr,
{ $($setup:tt)* },
$copy:expr,
$body:tt
} => {
let $tracker = Rc::new(RefCell::new(Tracker::new()));
{
let mut $expect = Vec::new();
$($setup)*
let mut $l : List<TestNode,S> = List::new();
for i in 0..$count {
let data = RefCell::new(
TestNodeData::new(i, &$tracker)
);
let n = Rc::new(TestNode {
data,
ll : Link::new()
});
$l.push_back(&From::from(&n));
$expect.push(i);
$copy(n);
}
consistency(&$l, &$expect);
{ $body }
}
assert!($tracker.borrow().is_empty());
}
}
macro_rules! stdprep {
{ $l:ident, $tracker:ident, $expect:ident, $count:expr,
$body:tt
} => {
extprep!{ $l, $tracker, $expect, $count,
{ }, |_|(), $body }
}
}
const NEWNODE : usize = 9;
fn newnode(tracker : &Rc<RefCell<Tracker>>)
-> Pointer<TestNode,TestSelector>
{
From::from(Rc::new(
TestNode {
data : RefCell::new(TestNodeData::new(NEWNODE, tracker)),
ll : Link::new(),
}
))
}
fn atpos(l : &TestList, pos : usize) -> Pointer<TestNode,S> {
let mut c = l.iter();
for _ in 0..pos { c.walk(false); }
c.cursor().unwrap()
}
#[test]
fn first_last() {
for count in 0..3 {
println!("first_last count={}",count);
stdprep!{l, tracker, expect, count, {
let t = l.first();
assert_eq!( t.map(|p| p.data.borrow().v),
if count>0 { Some(0) } else { None } );
let t = l.last();
assert_eq!( t.map(|p| p.data.borrow().v),
if count>0 { Some(count-1) } else { None } );
}}
}
}
#[test]
fn cursor() {
for count in 0..3 {
println!("cursor count={}",count);
extprep!{ l, tracker, expect, count, {
let mut copies = Vec::new();
}, |n| copies.push(n), {
let mut counted = 0;
for (i,c) in l.iter().enumerate() {
assert!(Rc::ptr_eq(
&c,
&copies[i],
));
counted += 1;
}
assert_eq!(counted, count);
for &tail in &[false,true] {
let c = l.first_last(tail);
if count==0 {
assert!(c.is_none());
} else {
assert!(Rc::ptr_eq(
&c.unwrap(),
&copies[
if !tail { 0 } else { count-1 }
])
)
}
}
for i in 0..(count as isize) {
for &rev in &[false,true] {
let mut c = Pointer::with_selector(
&copies[i as usize],
TestSelector{}
).iter_at();
c.walk(rev);
let ni = i + 1 - 2*(rev as isize);
let exp =
&if ni<0 || ni>=(count as isize) {
None
} else {
Some( From::from(
&copies[ni as usize]
))
};
assert!(Pointer::cursor_eq( &c, &exp ));
}
}
}}
}
}
#[test]
fn iter() {
for count in 0..2 {
println!("iter count={}",count);
stdprep!{ l, tracker, expect, count, {
let mut i = 0;
for n in &l {
assert_eq!( n.data.borrow().v,
expect[i] );
i += 1;
}
assert_eq!(i, count);
}}
}
}
#[test]
fn ptr_eq() {
stdprep!{ l, tracker, expect, 2, {
let p = l.first();
let q = l.last();
let n = None;
assert!( Pointer::cursor_eq(&p,&p) );
assert!( Pointer::cursor_eq(&n,&n) );
assert!( !Pointer::cursor_eq(&p,&q) );
assert!( !Pointer::cursor_eq(&p,&n) );
}}
}
#[test]
fn insert() {
for count in 1..5 {
for pos in 0..count {
for &after in &[false,true] {
println!("insert count={} pos={} after={}",count,pos,after);
stdprep!{ l, tracker, expect, count, {
let c = atpos(&l,pos);
let nn = newnode(&tracker);
l.insert(&nn, &c, after);
expect.insert(pos + (after as usize), NEWNODE);
consistency(&l, &expect);
}}
}}}
}
#[test]
fn remove() {
for count in 1..5 {
for pos in 0..count {
println!("remove count={} pos={}",count,pos);
stdprep!{ l, tracker, expect, count, {
let c = atpos(&l,pos);
l.remove(&c);
expect.remove(pos);
consistency(&l, &expect);
}}
}}
}
#[test]
fn push_at() {
for count in 0..3 {
for &tail in &[false,true] {
println!("push_at count={} tail={}",count,tail);
stdprep!{ l, tracker, expect, count, {
let nn = newnode(&tracker);
l.push_at(&nn, tail);
if tail {
expect.push(NEWNODE);
} else {
expect.insert(0, NEWNODE);
}
consistency(&l, &expect);
}}
}}
}
#[test]
fn pop_at() {
for count in 0..2 {
for &tail in &[false,true] {
println!("pop_at count={} tail={}",count,tail);
stdprep!{ l, tracker, expect, count, {
let exp = l.first_last(tail);
let got = l.pop_at(tail);
assert_eq!( got.as_ref().map(|n| n.data.borrow().v),
exp.as_ref().map(|n| n.data.borrow().v) );
if tail { expect.pop(); }
else { if count > 0 { expect.remove(0); } }
consistency(&l, &expect);
}}
}}
}
struct TestNode1 {
v : usize,
}
#[test]
fn construct_1() {
let mut l : List1<TestNode1> = List::new();
let mut count = 0;
let mut tn = ||{
let r = TestNode1 { v : count };
count += 1;
r
};
type P = Pointer1<TestNode1>;
type C = Cursor1<TestNode1>;
macro_rules! push_P {
($p:expr) => {
let p : P = $p;
l.push_back(&p);
}
}
push_P!( Pointer1::from_data(Node1::new(tn()), Default::default()) );
push_P!( From::from( tn() ) );
push_P!( From::from( Node1::new( tn() )) );
push_P!( Node1::pointer( tn() ) );
push_P!( Pointer1::new( &Rc::new( Node1::new( tn() ))) );
for (i,n) in l.iter().enumerate() {
assert_eq!(n.v, i);
}
}