//
// rc-dlist-deque - doubly linked list for Rust -- tests module
//
//  Copyright (C) 2019-2022 Ian Jackson
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.

//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.


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), {
            
            // check that .iter() works and enumerates
            let mut counted = 0;
            for (i,c) in l.iter().enumerate() {
                assert!(Rc::ptr_eq(
                    &c,
                    &copies[i],
                ));
                counted += 1;
            }
            assert_eq!(counted, count);

            // check that .cursor() works
            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 }
                        ])
                    )
                }
            }

            // check that walk works
            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);
        }}
    }}
}

// ----- List1 -----

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);
    }
}