use std::assert_eq;
use std::clone::Clone;
use std::cmp::Ord;
use std::cmp::PartialEq;
use std::cmp::PartialOrd;
use std::convert::identity;
use std::convert::From;
use std::default::Default;
use std::format;
use std::iter::Iterator;
use std::option::Option;
use std::option::Option::None;
use std::option::Option::Some;
use std::print;
use std::println;
use std::string::String;
use std::vec::Vec;

use clap::clap_derive::ArgEnum;
use clap::ArgAction;
use clap::Parser;
use project::datastructures::heap::Heap;
use project::datastructures::heap::MaxH;
use project::datastructures::heap::MinH;
use project::datastructures::linear::LLQueue;
use project::datastructures::linear::LLStack;
use project::datastructures::linear::CDLL;
use project::datastructures::linear::CSLL;
use project::datastructures::linear::DLL;
use project::datastructures::linear::LL;
use project::datastructures::linear::SLL;
use project::datastructures::trees::AVL;
use project::datastructures::trees::BST;
use rand::distributions::Distribution;
use rand::distributions::Uniform;
use rand::rngs::OsRng;

#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, ArgEnum)]
enum Algorithm {
    AVL,
    BST,
    CDLL,
    CSLL,
    DLL,
    SLL,
    LLQueue,
    LLStack,
    MinH,
    MaxH,
}

/// Perform random insertions and deletions of random integers
/// into a data-structure
/// until it fits the desired size,
/// performing integrity checks
/// after each mutation of the data-structure.
///
/// If this program is ran for sufficiently large sizes
/// and is given enough time,
/// it should eventually proof a correct behavior
/// of the data-structure in all possible cases for the given size.
///
/// See: <https://en.wikipedia.org/wiki/Fuzzing>
#[derive(Parser)]
#[clap(author)]
#[clap(name = "Fuzzing")]
#[clap(version)]
#[clap(term_width = 80)]
struct CLI {
    /// Algorithm to use.
    #[clap(arg_enum, value_parser)]
    algorithm: Algorithm,

    /// Target size of the data-structure to generate.
    #[clap()]
    size: usize,

    /// Pretty print the data-structure to the terminal.
    #[clap(short, long, action = ArgAction::SetTrue)]
    verbose: bool,
}

fn main() {
    let args = CLI::parse();

    let mut fuzzer = Fuzzer::from(args.algorithm);
    let mut witness = Witness {
        algorithm: args.algorithm,
        elements: Vec::with_capacity(args.size),
    };

    let mut random_generator = OsRng;
    let mut random_values =
        Uniform::new_inclusive(1, args.size).sample_iter(&mut random_generator);

    while witness.elements.len() < args.size {
        let value = random_values.next().unwrap();

        if rand::random::<bool>() {
            fuzzer.insert(value);
            witness.insert(value);
        } else {
            assert_eq!(fuzzer.delete(&value), witness.delete(&value));
        }

        if args.verbose {
            println!();
            match &fuzzer {
                Fuzzer::AVL(avl) => avl.pretty_print(),
                Fuzzer::BST(bst) => bst.pretty_print(),
                Fuzzer::CDLL(cdll) => cdll.print(),
                Fuzzer::CSLL(csll) => csll.print(),
                Fuzzer::DLL(dll) => dll.print(),
                Fuzzer::SLL(sll) => sll.print(),
                Fuzzer::LLQueue(ll) => ll.print(),
                Fuzzer::LLStack(ll) => ll.print(),
                Fuzzer::MaxH(heap) => {
                    println!("{:?}", heap.get_elements())
                },
                Fuzzer::MinH(heap) => {
                    println!("{:?}", heap.get_elements())
                },
            }
        }

        // Integrity check
        assert_eq!(
            fuzzer.elements(),
            witness.elements.iter().collect::<Vec<&usize>>()
        );
    }
}

enum Fuzzer {
    AVL(AVL<usize>),
    BST(BST<usize>),
    CDLL(CDLL<usize>),
    CSLL(CSLL<usize>),
    DLL(DLL<usize>),
    SLL(SLL<usize>),
    LLQueue(LLQueue<usize>),
    LLStack(LLStack<usize>),
    MinH(MinH<usize>),
    MaxH(MaxH<usize>),
}

impl From<Algorithm> for Fuzzer {
    fn from(algorithm: Algorithm) -> Self {
        match algorithm {
            Algorithm::AVL => Fuzzer::AVL(AVL::default()),
            Algorithm::BST => Fuzzer::BST(BST::default()),
            Algorithm::CDLL => Fuzzer::CDLL(CDLL::default()),
            Algorithm::CSLL => Fuzzer::CSLL(CSLL::default()),
            Algorithm::DLL => Fuzzer::DLL(DLL::default()),
            Algorithm::SLL => Fuzzer::SLL(SLL::default()),
            Algorithm::LLStack => Fuzzer::LLStack(LLStack::default()),
            Algorithm::LLQueue => Fuzzer::LLQueue(LLQueue::default()),
            Algorithm::MinH => Fuzzer::MinH(MinH::default()),
            Algorithm::MaxH => Fuzzer::MaxH(MaxH::default()),
        }
    }
}

impl Fuzzer {
    fn insert(&mut self, data: usize) {
        match self {
            Fuzzer::AVL(avl) => {
                print!("Insert({data}), ");
                avl.insert(data);
            },
            Fuzzer::BST(bst) => {
                print!("Insert({data}), ");
                bst.insert(data)
            },
            Fuzzer::CDLL(cdll) => {
                print!("InsertSorted({data}), ");
                cdll.insert_sorted(data)
            },
            Fuzzer::CSLL(csll) => {
                print!("InsertSorted({data}), ");
                csll.insert_sorted(data)
            },
            Fuzzer::DLL(dll) => {
                print!("InsertSorted({data}), ");
                dll.insert_sorted(data)
            },
            Fuzzer::SLL(sll) => {
                print!("InsertSorted({data}), ");
                sll.insert_sorted(data)
            },
            Fuzzer::LLQueue(ll) => {
                print!("Push({data}), ");
                ll.push(data)
            },
            Fuzzer::LLStack(ll) => {
                print!("Push({data}), ");
                ll.push(data)
            },
            Fuzzer::MinH(heap) => {
                print!("Insert({data}), ");
                heap.insert(data)
            },
            Fuzzer::MaxH(heap) => {
                print!("Insert({data}), ");
                heap.insert(data)
            },
        }
    }

    fn delete(&mut self, data: &usize) -> Option<usize> {
        match self {
            Fuzzer::AVL(avl) => {
                print!("Delete({data}), ");
                avl.delete(data)
            },
            Fuzzer::BST(bst) => {
                print!("Delete({data}), ");
                bst.delete(data)
            },
            Fuzzer::CDLL(cdll) => {
                print!("Delete({data}), ");
                cdll.delete(data)
            },
            Fuzzer::CSLL(csll) => {
                print!("Delete({data}), ");
                csll.delete(data)
            },
            Fuzzer::DLL(dll) => {
                print!("Delete({data}), ");
                dll.delete(data)
            },
            Fuzzer::SLL(sll) => {
                print!("Delete({data}), ");
                sll.delete(data)
            },

            Fuzzer::LLQueue(ll) => {
                print!("Pop(), ");
                ll.pop()
            },
            Fuzzer::LLStack(ll) => {
                print!("Pop(), ");
                ll.pop()
            },
            Fuzzer::MinH(heap) => {
                print!("Remove(), ");
                heap.remove()
            },
            Fuzzer::MaxH(heap) => {
                print!("Remove(), ");
                heap.remove()
            },
        }
    }

    fn elements(&self) -> Vec<&usize> {
        match self {
            Fuzzer::AVL(avl) => avl.traverse_in_order(),
            Fuzzer::BST(bst) => bst.traverse_in_order(),
            Fuzzer::CDLL(cdll) => cdll.iter_once().collect(),
            Fuzzer::CSLL(csll) => csll.iter_once().collect(),
            Fuzzer::DLL(dll) => dll.iter_once().collect(),
            Fuzzer::SLL(sll) => sll.iter_once().collect(),
            Fuzzer::LLQueue(ll) => ll.iter_once().collect(),
            Fuzzer::LLStack(ll) => ll.iter_once().collect(),
            Fuzzer::MinH(heap) => {
                let mut elements: Vec<&usize> =
                    heap.get_elements().iter().collect();
                elements.sort();
                elements
            },
            Fuzzer::MaxH(heap) => {
                let mut elements: Vec<&usize> =
                    heap.get_elements().iter().collect();
                elements.sort_by(|a, b| a.cmp(b));
                elements
            },
        }
    }
}

struct Witness {
    algorithm: Algorithm,
    elements: Vec<usize>,
}

impl Witness {
    fn insert(&mut self, value: usize) {
        match self.algorithm {
            Algorithm::AVL
            | Algorithm::BST
            | Algorithm::CDLL
            | Algorithm::CSLL
            | Algorithm::DLL
            | Algorithm::SLL
            | Algorithm::MinH
            | Algorithm::MaxH => {
                self.elements.insert(
                    self.elements
                        .binary_search(&value)
                        .map_or_else(identity, identity),
                    value,
                );
            },
            Algorithm::LLQueue => {
                self.elements.push(value);
            },
            Algorithm::LLStack => {
                self.elements.insert(0, value);
            },
        }
    }

    fn delete(&mut self, value: &usize) -> Option<usize> {
        match self.algorithm {
            Algorithm::AVL
            | Algorithm::BST
            | Algorithm::CDLL
            | Algorithm::CSLL
            | Algorithm::DLL
            | Algorithm::SLL => {
                self.elements
                    .binary_search(&value)
                    .ok()
                    .map(|index| self.elements.remove(index))
            },
            Algorithm::LLQueue | Algorithm::LLStack => {
                if self.elements.is_empty() {
                    None
                } else {
                    Some(self.elements.remove(0))
                }
            },
            Algorithm::MinH => {
                self.elements
                    .iter()
                    .enumerate()
                    .min_by(|a, b| a.1.cmp(b.1))
                    .map(|(i, _)| i)
                    .map(|i| self.elements.remove(i))
            },
            Algorithm::MaxH => {
                self.elements
                    .iter()
                    .enumerate()
                    .max_by(|a, b| a.1.cmp(b.1))
                    .map(|(i, _)| i)
                    .map(|i| self.elements.remove(i))
            },
        }
    }
}