//! `morton_encoding` is a crate that helps interleave the bits of numbers, 
//! (called "co-ordinates" in the source code)
//! thereby creating a so-called "Morton encoding" (also known as a 
//! "Z-order encoding") in whose final result ("key")
//! all bits of the same significance are together.
//! This is helpful for linearising the points of data structures whilst preserving
//! some measure of locality. Z-order encoding isn't as good at preserving 
//! locality as Hilbert encoding, but it is much easier to compute.
//! 
//! The functions contained herein are broadly split into four categories:
//! * "Bloating functions", that interleave a number's bits with zeroes;
//! * "Shrinking functions", that perform the opposite operation;
//! * "Morton encoding functions", that interleave some numbers'
//! bits with each other;
//! * "Morton decoding functions", that perform the opposite operation.
//! 
//! For more detailed information, 
//! please refer to each individual function's documentation.
//TODO: Release!

type SizeRatio = core::num::NonZeroUsize;

use num_traits::ToPrimitive;
use num::traits::int::PrimInt;
use std::convert::From;
use std::ops::BitOrAssign;
use std::ops::BitAndAssign;
use std::ops::ShlAssign;
use num::BigUint;

/// A convenience function for persuading the compiler that a non-zero value is, in fact, non-zero.
/// 
/// Will panic if used called with a zero.
pub fn nz(x: usize) -> SizeRatio {SizeRatio::new(x).unwrap()}

/// A convenience function for converting primitive values to BigUints.
/// 
/// Will fail to compile if called with a literal that's not explicitly declared as unsigned.
pub fn tobuint<Coor>(x: Coor) -> BigUint 
    where Coor:num::Unsigned, num::BigUint: std::convert::From<Coor>{BigUint::from(x)}

fn size_ratio<A, B> () -> SizeRatio 
where A: From<B>
{
    nz(std::mem::size_of::<A>() / std::mem::size_of::<B>())
}

fn fits_n_times<A, B> (n: SizeRatio) -> bool {
    std::mem::size_of::<A>() >= n.get()*std::mem::size_of::<B>()
}

fn step_amount<Coor> () -> u32 {
    let ceil_of_log2_of_coor_bits = (std::mem::size_of::<Coor>() * 8).next_power_of_two().trailing_zeros();
    ceil_of_log2_of_coor_bits
}

fn get_mask<Key> (step_number: usize, siz_rat: SizeRatio) -> Key 
where Key: PrimInt + BitOrAssign + ShlAssign<usize>
{
    let siz_rat = siz_rat.get();
    let key_bits = std::mem::size_of::<Key>() * 8;
    let tentative_mask = {
        let one_1 = Key::one();
        let amount_of_1s_per_pattern = 1<<step_number;
        let pattern = (one_1 << amount_of_1s_per_pattern) - one_1;
        let mut insert_patterns_here: Key = pattern;
        let pattern_length = siz_rat * amount_of_1s_per_pattern;
        let amt_of_patterns_that_fit_in_key = key_bits / pattern_length;
        let amt_of_patterns_we_still_need_to_insert = amt_of_patterns_that_fit_in_key - 1;
        for _ in 0..amt_of_patterns_we_still_need_to_insert {
            insert_patterns_here <<= pattern_length;
            insert_patterns_here |= pattern;
        }
        insert_patterns_here
    };
    
    let usize_bits = 8*(std::mem::size_of::<usize>() as u32);
    let num_of_bits_after_first_set = usize_bits - siz_rat.leading_zeros() - 1;
    let masking_is_necessary = (step_number as u32) % num_of_bits_after_first_set == 0;
    if masking_is_necessary {
        tentative_mask
    } else {
        Key::max_value()
    }
}

use num_traits::identities::One;
fn get_mask_biguint (step_number: usize, siz_rat: SizeRatio, key_bits: usize) -> Option<num::BigUint> {

    let siz_rat = siz_rat.get();
    let tentative_mask = {
        let one_1 = BigUint::one();
        let amount_of_1s_per_pattern = 1<<step_number;
        let pattern = (one_1 << amount_of_1s_per_pattern) - BigUint::one();
        let mut insert_patterns_here = pattern.clone();
        let pattern_length = siz_rat * amount_of_1s_per_pattern;
        let amt_of_patterns_that_fit_in_key = key_bits / pattern_length;
        let amt_of_patterns_we_still_need_to_insert = amt_of_patterns_that_fit_in_key - 1;
        for _ in 0..amt_of_patterns_we_still_need_to_insert {
            insert_patterns_here <<= pattern_length;
            insert_patterns_here |= pattern.clone();
        }        insert_patterns_here    };

    let divisor = 8*(std::mem::size_of::<usize>() as u32) - siz_rat.leading_zeros() - 1;
    if (step_number as u32) % divisor != 0 {
        None
    } else {
        Some(tentative_mask)
    }
}


/// Guarantees that a given data structure is suitable for a Morton Key.
/// 
/// Essentially, it guarantees that a) it behaves as if it's an integer and b) that it's larger than the relevant coordinate.
pub trait ValidKey<Coor>: PrimInt + From<Coor> + BitOrAssign + BitAndAssign + ShlAssign<usize> {}
/// All primitive int types are suitable for Morton Keys.
impl<Coor, Key: PrimInt + From<Coor> + BitOrAssign + BitAndAssign + ShlAssign<usize>> ValidKey<Coor> for Key {}

/// "Bloats" a given number, interleaving its bits with an automatically-computed number of zeroes.
/// 
/// The size ratio for the "bloating" is computed as the ratio of the sizes of the provided types.
/// 
/// Never panics.
/// # Examples
/// ```
/// # use morton_encoding::bloat;
/// assert_eq!(bloat::<u8, u32>(0xFF), 0x1111_1111);
/// assert_eq!(bloat::<_, u64>(0x1111_1111u32), 0x0101_0101_0101_0101);
/// ```
pub fn bloat<Coor, Key>(x: Coor) -> Key
where Coor: ToPrimitive, Key: ValidKey<Coor>,
{  
    bloat_custom(x, size_ratio::<Key, Coor>())
}
 
/// "Bloats" a given number, interleaving its bits with a user-provided number of zeroes.
/// 
/// Each input bit is interleaved with `siz_rat - 1` zeroes.
/// 
/// This function is preferable when the size ratio can be computed statically, as it may panic otherwise.
/// 
/// # Panics
/// 
/// As this function is meant to be used with statically computable size ratios, it will panic if the provided `Key` type is not large enough to fit `siz_rat` `Coor` types. If the size ratio is computed at runtime, the checked version of this function (namely `bloat_custom_checked`) should be used instead.
/// # Examples
/// ```
/// # use morton_encoding::bloat_custom;
/// # use morton_encoding::nz;
/// assert_eq!(bloat_custom::<_, u32>(0x55u8, nz(3)), 0x041041);
/// ```
pub fn bloat_custom<Coor, Key>(x: Coor, siz_rat: SizeRatio) -> Key
where Coor: ToPrimitive, Key: ValidKey<Coor>,
{
    bloat_custom_checked(x, siz_rat).unwrap()
}
 
/// "Bloats" a given number, interleaving its bits with a user-provided number of zeroes. Returns an `Option`.
/// 
///  Each input bit is interleaved with `siz_rat - 1` zeroes. Alternatively, if the provided `Key` type is too small to fit `siz_rat` `Coor` numbers inside it, a `None` is returned .
/// 
/// This function is preferable when the size ratio is computed at run-time.
///  
/// # Examples
/// ```
/// # use morton_encoding::bloat_custom_checked;
/// # use morton_encoding::nz;
/// assert_eq!(bloat_custom_checked(0xFFFFu16, nz(2)), Some(0x55555555u32));
/// assert_eq!(bloat_custom_checked::<u16, u32>(0xFFFF, nz(3)), None);
/// ```
pub fn bloat_custom_checked<Coor, Key>(x: Coor, siz_rat: SizeRatio) -> Option<Key>
where Coor: ToPrimitive, Key: ValidKey<Coor>,
{
    if !fits_n_times::<Key, Coor>(siz_rat) {return None;}

    let mut result: Key = From::from(x);
    if siz_rat.get() == 1 {
        return Some(result);
    }

    let shift_bitor_mask = |x: &mut Key, y| {
        let shift_amt = (siz_rat.get() - 1) << y;
        *x |= *x << shift_amt;
        (*x) &= get_mask(y, siz_rat)
    };
    
    (0..step_amount::<Coor>())
        .rev()
        .for_each(|q| shift_bitor_mask(&mut result, q as usize));
        
    Some(result)
}

/// "Bloats" a given number to an arbitrarily large BigUint.
/// 
/// Each bit of the input is interleaved with `siz_rat - 1` zeroes.
/// 
/// This function assumes that the user will not need to use numbers larger than `usize::max_value()` bytes in size.
/// 
/// # Examples
/// ```
/// # use morton_encoding::bloat_custom_biguint;
/// # use morton_encoding::nz;
/// # use morton_encoding::tobuint;
/// # use num::BigUint;
/// assert_eq!(bloat_custom_biguint(1u32, nz(2)), tobuint(1u8));
/// assert_eq!(bloat_custom_biguint(u128::max_value(), nz(32)), BigUint::new(vec!(1u32; 128)));
/// ```
pub fn bloat_custom_biguint<Coor>(x: Coor, siz_rat: SizeRatio) -> num::BigUint
where
    Coor: num_traits::ToPrimitive,
    num::BigUint: std::convert::From<Coor>
{
    let coor_siz = std::mem::size_of::<Coor>();
    let key_siz = coor_siz * siz_rat.get();
    
    let mut result = num::BigUint::from(x);
    if siz_rat.get() == 1 {
        return result;
    }

    let shift_bitor_mask = |x: &mut num::BigUint, y| {
        let shift_amt = (siz_rat.get() - 1) << y;
        *x |= ((*x).clone()) << shift_amt;
        let maybe_mask = get_mask_biguint(y, siz_rat, key_siz*8);
        if maybe_mask.is_some() {(*x) &= maybe_mask.unwrap();}
    };

    let op_amt = coor_siz.next_power_of_two().trailing_zeros() + 3;
    (0..op_amt)
        .rev()
        .for_each(|q| shift_bitor_mask(&mut result, q as usize));
    result
}

/// "Shrinks" a given number, only keeping an automatically-computed amount of its bits.
/// 
/// The 0th bit is always kept, and so is every `siz_rat`th bit thereafter. All other bits are lost.
/// 
/// This function sanitises its input, so the bits that are thrown away do not need to be cleared by the user.
/// 
/// The size ratio for the "shrinking" is computed as the ratio of the sizes of the provided types.
/// 
/// Never panics.
/// # Examples
/// ```
/// # use morton_encoding::shrink;
/// assert_eq!(shrink::<u8, u32>(0x1111_1111), 0xFF);
/// assert_eq!(shrink::<u32, u64>(0xA1A1_A1A1_A1A1_A1A1), 0x1111_1111);
/// ```
pub fn shrink<Coor, Key>(x: Key) -> Coor
where Coor: ToPrimitive + PrimInt, Key: ValidKey<Coor>,
{
    shrink_custom(x, size_ratio::<Key, Coor>())
}

/// "Shrinks" a given number, only keeping a user-provided amount of its bits.
/// 
/// The 0th bit is always kept, and so is every `siz_rat`th bit thereafter. All other bits are lost.
/// 
/// This function is preferable when the size ratio can be computed statically, as it may panic otherwise. 
/// 
/// This function sanitises its input, so the bits that are thrown away do not need to be cleared by the user.
/// 
/// # Panics
/// 
/// As this function is meant to be used with statically computable size ratios, it will panic if the provided `Key` type is not large enough to fit `siz_rat` `Coor` types. If the size ratio is computed at runtime, the checked version of this function (namely `shrink_custom_checked`) should be used instead.
/// 
/// # Examples
/// ```
/// # use morton_encoding::shrink_custom;
/// # use morton_encoding::nz;
/// assert_eq!(shrink_custom::<u8, u32>(0x145145, nz(3)), 0x55);
/// ```
pub fn shrink_custom<Coor, Key>(x: Key, siz_rat: SizeRatio) -> Coor
where Coor: ToPrimitive + PrimInt, Key: ValidKey<Coor>,
{
    shrink_custom_checked(x, siz_rat).unwrap()
}

/// "Shrinks" a given number, only keeping a user-provided amount of its bits. Returns an `Option`.
/// 
/// The 0th bit is always kept, and so is every `siz_rat`th bit thereafter. All other bits are lost. Alternatively, if the provided `Key` type is too small to fit `siz_rat` `Coor` numbers inside it, a `None` is returned .
/// 
/// This function is preferable when the size ratio is computed at run-time.
/// 
/// This function sanitises its input, so the bits that are thrown away do not need to be cleared by the user.
/// 
/// # Examples
/// ```
/// # use morton_encoding::shrink_custom_checked;
/// # use morton_encoding::nz;
/// assert_eq!(shrink_custom_checked::<u16, u32>(0xFFFF_FFFF, nz(2)), Some(0xFFFF));
/// assert_eq!(shrink_custom_checked::<u16, u32>(0x185185, nz(3)), None);
/// ```
pub fn shrink_custom_checked<Coor, Key>(x: Key, siz_rat: SizeRatio) -> Option<Coor>
where Coor: ToPrimitive + PrimInt, Key: ValidKey<Coor>,
{
    if !fits_n_times::<Key, Coor>(siz_rat) {return None;}

    let mut result: Key = x;
    if siz_rat.get() == 1 {
        return Coor::from(result);
    }

    let shift_bitor_mask = |x: &mut Key, y| {
        (*x) &= get_mask(y, siz_rat);
        let shift_amt = (siz_rat.get() - 1) << y;
        *x |= *x >> shift_amt;
    };

    (0..step_amount::<Coor>())
        .for_each(|q| shift_bitor_mask(&mut result, q as usize));
    
    Coor::from(result & (From::from(Coor::max_value())))
}

/// "Shrinks" a given number from an arbitrarily large BigUint.
/// 
/// The 0th bit is always kept, as is every `siz_rat`th bit thereafter.
/// 
/// This function sanitises its input, such that the bits that are thrown away do not need to be cleared by the user. It is also assumed that the user will not need to use numbers larger than `usize::max_value()` bytes in size.
/// 
/// # Examples
/// ```
/// # use morton_encoding::shrink_custom_biguint;
/// # use morton_encoding::nz;
/// # use morton_encoding::tobuint;
/// assert_eq!(shrink_custom_biguint(tobuint(1u8), nz(2)), tobuint(1u8));
/// assert_eq!(shrink_custom_biguint(num::BigUint::new(vec!(3u32; 128)), nz(32)), num::BigUint::new(vec!(u32::max_value(); 4)));
/// ```
pub fn shrink_custom_biguint(x: BigUint, siz_rat: SizeRatio) -> num::BigUint
where
{
    let key_bits = x.bits() + siz_rat.get() - 1;
    let coor_bits = key_bits / siz_rat.get();
    let key_bits = coor_bits * siz_rat.get();
    
    let mut result = x;
    if siz_rat.get() == 1 {
        return result;
    }

    let shift_bitor_mask = |x: &mut BigUint, y| {
        let maybe_mask = get_mask_biguint(y, siz_rat, key_bits);
        if maybe_mask.is_some() {(*x) &= maybe_mask.unwrap();}
        //dbg!(x);
        let shift_amt = (siz_rat.get() - 1) << y;
        *x |= ((*x).clone()) >> shift_amt;
    };

    let step_amount = coor_bits.next_power_of_two().trailing_zeros();
    (0..step_amount)
        .for_each(|q| shift_bitor_mask(&mut result, q as usize));
    
    let mut final_mask = BigUint::one();
    final_mask <<= coor_bits;
    final_mask -= BigUint::one();
    
    //dbg!(final_mask.clone());
    //dbg!(result.clone());
        
    result & final_mask
}

/// Receives an iterator of `Coor` values and encodes them all in a `Key` value.
/// 
/// Meant to be used with statically-known iterator lengths. If that is not the case, the checked version of this function (`morton_encode_checked`) should be used instead.
/// 
/// # Panics
/// 
/// This function will panic if the `Key` value provided does not have enough length for all the values in the iterator.
/// 
/// # Examples
/// ```
/// # use morton_encoding::morton_encode;
/// let input = vec!(0u8, 255);
/// let result: u16 = morton_encode(input);
/// assert_eq!(result, 0x5555);
/// ```
pub fn morton_encode<Coor, Key, Coors>(coors: Coors) -> Key
where Coor: ToPrimitive, Key: ValidKey<Coor>,
      Coors: IntoIterator<Item = Coor>,
      <Coors as std::iter::IntoIterator>::IntoIter: ExactSizeIterator,
{
    morton_encode_checked(coors).unwrap()
}

/// Receives an iterator of `Coor` values and encodes them all in a `Option<Key>` value.
/// 
/// Returns a `None` if the iterator is empty, or if it is too large for all the `Coor` values contained within to fit inside a `Key` type.
/// 
/// # Examples
/// ```
/// # use morton_encoding::morton_encode_checked;
/// assert_eq!(morton_encode_checked(vec!(1u8, 1)), Some(3u16));
/// assert_eq!(morton_encode_checked::<u16, u32, Vec<u16>>(vec!()), None);
/// assert_eq!(morton_encode_checked::<_, u16, _>(vec!(0u8, 255, 200)), None);
/// ```
pub fn morton_encode_checked<Coor, Key, Coors>(coors: Coors) -> Option<Key>
where Coor: ToPrimitive, Key: ValidKey<Coor>,
      Coors: IntoIterator<Item = Coor>,
      <Coors as std::iter::IntoIterator>::IntoIter: ExactSizeIterator,
{
    let iterator = coors.into_iter();
    let siz_rat = SizeRatio::new(iterator.len());
    if siz_rat.map(|sr| !fits_n_times::<Key, Coor>(sr)).unwrap_or(true) {return None;}
    let bloat_fn = |x: Coor| bloat_custom::<Coor, Key>(x, siz_rat.unwrap());
    Some(iterator.map(bloat_fn).fold(Key::zero(), |acc, x| (acc << 1) | x))
}

/// Receives an iterator of `Coor` values and encodes them all in a `BigUint`.
/// 
/// # Examples
/// ```
/// # use morton_encoding::morton_encode_biguint;
/// # use morton_encoding::nz;
/// # use morton_encoding::tobuint;
/// let input = vec!(0u8, 255u8);
/// let result = morton_encode_biguint(input);
/// assert_eq!(result, tobuint(0x5555u16));
/// ```
pub fn morton_encode_biguint<Coor, Coors>(coors: Coors) -> BigUint
where Coor: ToPrimitive,
      num::BigUint: std::convert::From<Coor>,
      Coors: IntoIterator<Item = Coor>,
      <Coors as std::iter::IntoIterator>::IntoIter: ExactSizeIterator,
{
    let zero = BigUint::new(vec!(0u32));
    let iterator = coors.into_iter();
    let siz_rat = SizeRatio::new(iterator.len());
    if siz_rat.is_none() {return zero;} 
    let bloat_fn = |x: Coor| bloat_custom_biguint::<Coor>(x, siz_rat.unwrap());
    iterator.map(bloat_fn).fold(zero, |acc, x| (acc << 1) | x)
}

/// Receives a `Key` value and returns an iterator of `Coor` values that were decoded from it.
/// 
/// Returns an empty iterator if the `Key` value is too small for so many `Coor` values.
/// 
/// # Examples
/// ```
/// # use morton_encoding::morton_decode;
/// # use morton_encoding::morton_encode;
/// # use morton_encoding::nz;
/// assert_eq!(morton_decode::<_, _, Vec<u8>>(3u16, nz(2)), vec!(1, 1));
/// assert_eq!(morton_decode::<u16, u32, Vec<u16>>(0, nz(4)), vec!());
/// let input = vec!(1u8, 2);
/// let encoded_input: u16 = morton_encode(input.clone());
/// let reassembled_input: Vec<u8> = morton_decode(encoded_input, nz(2));
/// assert_eq!(input, reassembled_input);
/// ```
pub fn morton_decode<Coor, Key, Coors>(key: Key, siz_rat: SizeRatio) -> Coors
where Coor: ToPrimitive + PrimInt, Key: ValidKey<Coor>,
      Coors: std::iter::FromIterator<Coor>
{
    if !fits_n_times::<Key, Coor>(siz_rat) {
        std::iter::empty().collect::<Coors>()
    } else {
        let shrink_fn = |x: Key| shrink_custom::<Coor, Key>(x, siz_rat);
        let siz_rat = siz_rat.get();
        (0..siz_rat).map(|x| key>>(siz_rat - (x+1))).map(shrink_fn).collect::<Coors>()
}}

/// Receives a `BigUint` value and returns an iterator of `BigUint` values that were decoded from it.
/// 
/// # Examples
/// ```
/// # use morton_encoding::morton_decode_biguint;
/// # use morton_encoding::morton_encode_biguint;
/// # use morton_encoding::nz;
/// # use morton_encoding::tobuint;
/// assert_eq!(morton_decode_biguint::<Vec<_>>(tobuint(3u8), nz(2)), vec!(tobuint(1u8); 2));
/// let input = vec!(tobuint(1u8), tobuint(2u8));
/// let encoded_input = morton_encode_biguint(input.clone());
/// let reassembled_input: Vec<_> = morton_decode_biguint(encoded_input, nz(2));
/// assert_eq!(input, reassembled_input);
/// ```
pub fn morton_decode_biguint<Coors>(key: BigUint, siz_rat: SizeRatio) -> Coors
where Coors: std::iter::FromIterator<BigUint> +  IntoIterator<Item = BigUint>,
      <Coors as std::iter::IntoIterator>::IntoIter: ExactSizeIterator,
{
    let shrink_fn = |x: BigUint| shrink_custom_biguint(x, siz_rat);
    let siz_rat = siz_rat.get();
    (0..siz_rat).map(|x| key.clone()>>(siz_rat - (x+1))).map(shrink_fn).collect::<Coors>()
}

macro_rules! doc_comment {
    ($x:expr) => {
        #[doc = $x]
        extern {}
    };
    ($x:expr, $($tt:tt)*) => {
        #[doc = $x]
        $($tt)*
    };
}

macro_rules! make_new_functions {
    ($encod: ident, $decod: ident, $t1: ty, $t2: ty, $siz_rat: expr) => {
    
        doc_comment!{concat!("Encodes an array of ", stringify!($siz_rat), " ", stringify!($t1), " values ([", stringify!($t1), "; ", stringify!($siz_rat), "]), producing a ", stringify!($t2), " value as the result."),
        
        pub fn $encod (x: [$t1; $siz_rat]) -> $t2 {
            let bloat_fn = |m: &$t1| bloat_custom::<$t1, $t2>(*m, nz($siz_rat));
            x.iter().map(bloat_fn).fold(0, |acc, x| (acc << 1) | x)
        }}
        
        doc_comment!{concat!("Decodes a ", stringify!($t2), " value, producing an array of ", stringify!($siz_rat), " ", stringify!($t1), " values ([", stringify!($t1), "; ", stringify!($siz_rat), "]) as the result."),
        
        pub fn $decod (x: $t2) -> [$t1; $siz_rat] {
            let mut result: [$t1; $siz_rat] = [0; $siz_rat];
            for i in 0..$siz_rat {
                result[$siz_rat - (i+1)] = shrink_custom(x>>i, nz($siz_rat));
            }
            result
}}}}

make_new_functions!(morton_encode_u8_2d  , morton_decode_u8_2d  ,   u8, u16  , 2);
make_new_functions!(morton_encode_u8_3d  , morton_decode_u8_3d  ,   u8, u32  , 3);
make_new_functions!(morton_encode_u8_4d  , morton_decode_u8_4d  ,   u8, u32  , 4);
make_new_functions!(morton_encode_u8_5d  , morton_decode_u8_5d  ,   u8, u64  , 5);
make_new_functions!(morton_encode_u8_6d  , morton_decode_u8_6d  ,   u8, u64  , 6);
make_new_functions!(morton_encode_u8_7d  , morton_decode_u8_7d  ,   u8, u64  , 7);
make_new_functions!(morton_encode_u8_8d  , morton_decode_u8_8d  ,   u8, u64  , 8);
make_new_functions!(morton_encode_u8_9d  , morton_decode_u8_9d  ,   u8, u128, 9);
make_new_functions!(morton_encode_u8_10d, morton_decode_u8_10d, u8, u128, 10);
make_new_functions!(morton_encode_u8_11d, morton_decode_u8_11d, u8, u128, 11);
make_new_functions!(morton_encode_u8_12d, morton_decode_u8_12d, u8, u128, 12);
make_new_functions!(morton_encode_u8_13d, morton_decode_u8_13d, u8, u128, 13);
make_new_functions!(morton_encode_u8_14d, morton_decode_u8_14d, u8, u128, 14);
make_new_functions!(morton_encode_u8_15d, morton_decode_u8_15d, u8, u128, 15);
make_new_functions!(morton_encode_u8_16d, morton_decode_u8_16d, u8, u128, 16);
make_new_functions!(morton_encode_u16_2d, morton_decode_u16_2d, u16, u32  , 2);
make_new_functions!(morton_encode_u16_3d, morton_decode_u16_3d, u16, u64  , 3);
make_new_functions!(morton_encode_u16_4d, morton_decode_u16_4d, u16, u64  , 4);
make_new_functions!(morton_encode_u16_5d, morton_decode_u16_5d, u16, u128, 5);
make_new_functions!(morton_encode_u16_6d, morton_decode_u16_6d, u16, u128, 6);
make_new_functions!(morton_encode_u16_7d, morton_decode_u16_7d, u16, u128, 7);
make_new_functions!(morton_encode_u16_8d, morton_decode_u16_8d, u16, u128, 8);
make_new_functions!(morton_encode_u32_2d, morton_decode_u32_2d, u32, u64  , 2);
make_new_functions!(morton_encode_u32_3d, morton_decode_u32_3d, u32, u128, 3);
make_new_functions!(morton_encode_u32_4d, morton_decode_u32_4d, u32, u128, 4);
make_new_functions!(morton_encode_u64_2d, morton_decode_u64_2d, u64, u128, 2);



#[cfg(test)]
mod tests {
    use super::*;

    fn fmt_bin<T>(x: T) -> std::string::String
    where
        T: std::fmt::Binary,
    {
        let size = std::mem::size_of::<T>();
        if size == 16 {
            format!("{:#0130b}", x)
        } else if size == 8 {
            format!("{:#066b}", x)
        } else if size == 4 {
            format!("{:#034b}", x)
        } else if size == 2 {
            format!("{:#018b}", x)
        } else if size == 1 {
            format!("{:#010b}", x)
        } else {
            format!("{:#b}", x)
        }
    }

    fn bloat_slow_custom<Coor, Key>(x: Coor, siz_rat: SizeRatio) -> Key
    where Coor: ToPrimitive + PrimInt + std::fmt::Binary + std::ops::BitAnd,
            Key: ValidKey<Coor>,
            <Key as num_traits::Num>::FromStrRadixErr: std::fmt::Debug,
    {
        let coor_siz = std::mem::size_of::<Coor>();
        let coor_bits = coor_siz*8;
        let key_siz = std::mem::size_of::<Key>();
        let siz_rat = siz_rat.get();
        if siz_rat == 1 {
            return std::convert::From::from(x);
        }
        assert!(siz_rat >= 1 && coor_siz*siz_rat <= key_siz);
        let key_zero = Key::zero();
        let coor_zero = Coor::zero();
        let mut result = key_zero;
        let get_mask_key = |b| (Key::one())<<(b*siz_rat);
        let get_mask_coor = |b| (Coor::one())<<b;
        let tst_bit = |a: Coor, b| (a & get_mask_coor(b)) != coor_zero;
        let set_bit = |a: &mut Key, b| (*a) |= get_mask_key(b);
        for bit_examined in 0..coor_bits {
            if tst_bit(x, bit_examined) {set_bit(&mut result, bit_examined)}
        }
        result
    }

    const MAX_BITS: u8 = 20;

    fn test_all_possible_values<Coor, Key>(siz_rat: Option<usize>)
    where
        Coor: num_traits::ToPrimitive + std::fmt::Binary + std::ops::BitAnd + num::traits::PrimInt + std::fmt::Display + std::fmt::Debug,
        rand::distributions::Standard: rand::distributions::Distribution<Coor>,
        Key: num::traits::int::PrimInt
            + std::convert::From<Coor>
            + std::ops::BitOrAssign
            + std::ops::BitAndAssign
            + std::fmt::Binary
            + std::ops::ShlAssign<usize>,
        <Key as num_traits::Num>::FromStrRadixErr: std::fmt::Debug,
        u128: std::convert::From<Coor>,
    {
        let siz_rat = siz_rat.and_then(|x| SizeRatio::new(x)).unwrap_or (size_ratio::<Key, Coor>());
        let testing_function = |x| bloat_slow_custom::<Coor, Key>(x, siz_rat);
        let function_under_test = |x| bloat_custom::<Coor, Key>(x, siz_rat);
        let limit = std::cmp::min(u128::from(Coor::max_value()), 1u128 << MAX_BITS);
        let limit = limit as usize;
        for x in 0..=limit {
            let x_ = Coor::from(x).expect("Coor and usize incompatible.");
            if x%(1<<26) == 0 && x!=0 {dbg!(x>>26);}
            let fn2 = function_under_test(x_);
            let fn1 = testing_function(x_);
            if fn1 != fn2 {
                panic!(
                    "x = {} \ntesting_function = {}, \nfunction_under_test = {}",
                    x,
                    fmt_bin(fn1),
                    fmt_bin(fn2)
                )
            }
            if x_ != shrink_custom(fn2, siz_rat) {
                panic!(
                    "x = {} \nBloated = {}, \nShrunk = {}",
                    x,
                    fmt_bin(fn2),
                    shrink_custom(fn2, siz_rat)
                )
            }
            if x%16 == 0 {
                let input = (0..siz_rat.get()).map(|_| rand::random::<Coor>()).collect::<Vec<Coor>>();
                let encoded_input: Key = morton_encode(input.clone());
                let reinstated_input: Vec<Coor> = morton_decode(encoded_input, siz_rat);
                assert_eq!(input, reinstated_input);
            }
        }
    }

    #[test]    fn test_u8_u16    () {        test_all_possible_values::<u8, u16>    (None);         }
    #[test]    fn test_u8_u24    () {        test_all_possible_values::<u8, u32>    (Some(3));    }
    #[test]    fn test_u8_u32    () {        test_all_possible_values::<u8, u32>    (None);         }
    #[test]    fn test_u8_u40    () {        test_all_possible_values::<u8, u64>    (Some(5));    }
    #[test]    fn test_u8_u48    () {        test_all_possible_values::<u8, u64>    (Some(6));    }
    #[test]    fn test_u8_u56    () {        test_all_possible_values::<u8, u64>    (Some(7));    }
    #[test]    fn test_u8_u64    () {        test_all_possible_values::<u8, u64>    (None);         }
    #[test]    fn test_u8_u72    () {        test_all_possible_values::<u8, u128>  (Some(9));    }
    #[test]    fn test_u8_u80    () {        test_all_possible_values::<u8, u128>  (Some(10));  }
    #[test]    fn test_u8_u88    () {        test_all_possible_values::<u8, u128>  (Some(11));  }
    #[test]    fn test_u8_u96    () {        test_all_possible_values::<u8, u128>  (Some(12));  }
    #[test]    fn test_u8_u104  () {        test_all_possible_values::<u8, u128>  (Some(13));  }
    #[test]    fn test_u8_u112  () {        test_all_possible_values::<u8, u128>  (Some(14));  }
    #[test]    fn test_u8_u120  () {        test_all_possible_values::<u8, u128>  (Some(15));  }
    #[test]    fn test_u8_u128  () {        test_all_possible_values::<u8, u128>  (None);         }
    #[test]    fn test_u16_u32  () {        test_all_possible_values::<u16, u32>  (None);         }
    #[test]    fn test_u16_u48  () {        test_all_possible_values::<u16, u64>  (Some(3));    }
    #[test]    fn test_u16_u64  () {        test_all_possible_values::<u16, u64>  (None);         }
    #[test]    fn test_u16_u80  () {        test_all_possible_values::<u16, u128>(Some(5));    }
    #[test]    fn test_u16_u96  () {        test_all_possible_values::<u16, u128>(Some(6));    }
    #[test]    fn test_u16_u112() {        test_all_possible_values::<u16, u128>(Some(7));    }
    #[test]    fn test_u16_u128() {        test_all_possible_values::<u16, u128>(None);         }
    #[test]    fn test_u32_u64  () {        test_all_possible_values::<u32, u64>  (None);         }
    #[test]    fn test_u32_u96  () {        test_all_possible_values::<u32, u128>(Some(3));    }
    #[test]    fn test_u32_u128() {        test_all_possible_values::<u32, u128>(None);         }
    #[test]    fn test_u64_u128() {        test_all_possible_values::<u64, u128>(None);         }
    
    macro_rules! test_functions {
        ($encod: ident, $decod: ident, $t1: ty, $t2: ty, $siz_rat: expr) => {
            for _ in 0..(1<<(MAX_BITS-3)){
                let mut input: [$t1; $siz_rat] = [0; $siz_rat];
                for m in 0..$siz_rat {
                    input[m] = rand::random::<$t1>();
                }
                let tmp = $encod(input);
                assert_eq!(input, $decod(tmp));
            }
        }
    }
    #[test] fn test_all_spec_funcs() {
        test_functions!(morton_encode_u8_2d  , morton_decode_u8_2d  ,   u8, u16  , 2);
        test_functions!(morton_encode_u8_3d  , morton_decode_u8_3d  ,   u8, u32  , 3);
        test_functions!(morton_encode_u8_4d  , morton_decode_u8_4d  ,   u8, u32  , 4);
        test_functions!(morton_encode_u8_5d  , morton_decode_u8_5d  ,   u8, u64  , 5);
        test_functions!(morton_encode_u8_6d  , morton_decode_u8_6d  ,   u8, u64  , 6);
        test_functions!(morton_encode_u8_7d  , morton_decode_u8_7d  ,   u8, u64  , 7);
        test_functions!(morton_encode_u8_8d  , morton_decode_u8_8d  ,   u8, u64  , 8);
        test_functions!(morton_encode_u8_9d  , morton_decode_u8_9d  , u8, u128  , 9);
        test_functions!(morton_encode_u8_10d, morton_decode_u8_10d, u8, u128, 10);
        test_functions!(morton_encode_u8_11d, morton_decode_u8_11d, u8, u128, 11);
        test_functions!(morton_encode_u8_12d, morton_decode_u8_12d, u8, u128, 12);
        test_functions!(morton_encode_u8_13d, morton_decode_u8_13d, u8, u128, 13);
        test_functions!(morton_encode_u8_14d, morton_decode_u8_14d, u8, u128, 14);
        test_functions!(morton_encode_u8_15d, morton_decode_u8_15d, u8, u128, 15);
        test_functions!(morton_encode_u8_16d, morton_decode_u8_16d, u8, u128, 16);
        test_functions!(morton_encode_u16_2d, morton_decode_u16_2d, u16, u32  , 2);
        test_functions!(morton_encode_u16_3d, morton_decode_u16_3d, u16, u64  , 3);
        test_functions!(morton_encode_u16_4d, morton_decode_u16_4d, u16, u64  , 4);
        test_functions!(morton_encode_u16_5d, morton_decode_u16_5d, u16, u128, 5);
        test_functions!(morton_encode_u16_6d, morton_decode_u16_6d, u16, u128, 6);
        test_functions!(morton_encode_u16_7d, morton_decode_u16_7d, u16, u128, 7);
        test_functions!(morton_encode_u16_8d, morton_decode_u16_8d, u16, u128, 8);
        test_functions!(morton_encode_u32_2d, morton_decode_u32_2d, u32, u64  , 2);
        test_functions!(morton_encode_u32_3d, morton_decode_u32_3d, u32, u128, 3);
        test_functions!(morton_encode_u32_4d, morton_decode_u32_4d, u32, u128, 4);
        test_functions!(morton_encode_u64_2d, morton_decode_u64_2d, u64, u128, 2);
    }
}
