//! Merkle nibble types.

use std::{cmp::min, hash::Hash};

use rlp::{Rlp, RlpStream};

use crate::Result;

/// Represents a nibble. A 16-variant value.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Nibble {
    N0,
    N1,
    N2,
    N3,
    N4,
    N5,
    N6,
    N7,
    N8,
    N9,
    N10,
    N11,
    N12,
    N13,
    N14,
    N15,
}

impl From<usize> for Nibble {
    fn from(val: usize) -> Nibble {
        match val {
            0 => Nibble::N0,
            1 => Nibble::N1,
            2 => Nibble::N2,
            3 => Nibble::N3,
            4 => Nibble::N4,
            5 => Nibble::N5,
            6 => Nibble::N6,
            7 => Nibble::N7,
            8 => Nibble::N8,
            9 => Nibble::N9,
            10 => Nibble::N10,
            11 => Nibble::N11,
            12 => Nibble::N12,
            13 => Nibble::N13,
            14 => Nibble::N14,
            15 => Nibble::N15,
            _ => panic!(),
        }
    }
}

impl Into<usize> for Nibble {
    fn into(self) -> usize {
        match self {
            Nibble::N0 => 0,
            Nibble::N1 => 1,
            Nibble::N2 => 2,
            Nibble::N3 => 3,
            Nibble::N4 => 4,
            Nibble::N5 => 5,
            Nibble::N6 => 6,
            Nibble::N7 => 7,
            Nibble::N8 => 8,
            Nibble::N9 => 9,
            Nibble::N10 => 10,
            Nibble::N11 => 11,
            Nibble::N12 => 12,
            Nibble::N13 => 13,
            Nibble::N14 => 14,
            Nibble::N15 => 15,
        }
    }
}

impl From<u8> for Nibble {
    fn from(val: u8) -> Nibble {
        match val {
            0 => Nibble::N0,
            1 => Nibble::N1,
            2 => Nibble::N2,
            3 => Nibble::N3,
            4 => Nibble::N4,
            5 => Nibble::N5,
            6 => Nibble::N6,
            7 => Nibble::N7,
            8 => Nibble::N8,
            9 => Nibble::N9,
            10 => Nibble::N10,
            11 => Nibble::N11,
            12 => Nibble::N12,
            13 => Nibble::N13,
            14 => Nibble::N14,
            15 => Nibble::N15,
            _ => panic!(),
        }
    }
}

impl Into<u8> for Nibble {
    fn into(self) -> u8 {
        match self {
            Nibble::N0 => 0,
            Nibble::N1 => 1,
            Nibble::N2 => 2,
            Nibble::N3 => 3,
            Nibble::N4 => 4,
            Nibble::N5 => 5,
            Nibble::N6 => 6,
            Nibble::N7 => 7,
            Nibble::N8 => 8,
            Nibble::N9 => 9,
            Nibble::N10 => 10,
            Nibble::N11 => 11,
            Nibble::N12 => 12,
            Nibble::N13 => 13,
            Nibble::N14 => 14,
            Nibble::N15 => 15,
        }
    }
}

/// A nibble type.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NibbleType {
    Leaf,
    Extension,
}

/// A nibble vector.
pub type NibbleVec = Vec<Nibble>;
/// A nibble slice.
pub type NibbleSlice<'a> = &'a [Nibble];

/// Given a key, return the corresponding nibble.
pub fn from_key(key: &[u8]) -> NibbleVec {
    let mut vec = NibbleVec::new();

    for i in 0..(key.len() * 2) {
        if i & 1 == 0 {
            // even
            vec.push(((key[i / 2] & 0xf0) >> 4).into());
        } else {
            vec.push((key[i / 2] & 0x0f).into());
        }
    }

    vec
}

/// Given a nibble, return the corresponding key.
pub fn into_key(nibble: NibbleSlice) -> Vec<u8> {
    let mut ret = Vec::new();

    for i in 0..nibble.len() {
        if i & 1 == 0 {
            // even
            let value: u8 = nibble[i].into();
            ret.push(value << 4);
        } else {
            let value: u8 = nibble[i].into();
            ret[i / 2] |= value;
        }
    }

    ret
}

/// Decode a nibble from RLP.
pub fn decode(rlp: &Rlp) -> Result<(NibbleVec, NibbleType)> {
    let mut vec = NibbleVec::new();

    let data = rlp.data()?;
    let start_odd = data[0] & 0b00010000 == 0b00010000;
    let start_index = if start_odd { 1 } else { 2 };
    let is_leaf = data[0] & 0b00100000 == 0b00100000;

    let len = data.len() * 2;

    for i in start_index..len {
        if i & 1 == 0 {
            // even
            vec.push(((data[i / 2] & 0xf0) >> 4).into());
        } else {
            vec.push((data[i / 2] & 0x0f).into());
        }
    }

    Ok((
        vec,
        if is_leaf {
            NibbleType::Leaf
        } else {
            NibbleType::Extension
        },
    ))
}

/// Encode a nibble into the given RLP stream.
pub fn encode(vec: NibbleSlice, typ: NibbleType, s: &mut RlpStream) {
    let mut ret: Vec<u8> = Vec::new();

    if vec.len() & 1 == 0 {
        // even
        ret.push(0b00000000);

        for (i, val) in vec.iter().enumerate() {
            if i & 1 == 0 {
                let v: u8 = (*val).into();
                ret.push(v << 4);
            } else {
                let end = ret.len() - 1;
                let v: u8 = (*val).into();
                ret[end] |= v;
            }
        }
    } else {
        ret.push(0b00010000);

        for (i, val) in vec.iter().enumerate() {
            if i & 1 == 0 {
                let end = ret.len() - 1;
                let v: u8 = (*val).into();
                ret[end] |= v;
            } else {
                let v: u8 = (*val).into();
                ret.push(v << 4);
            }
        }
    }

    ret[0] |= match typ {
        NibbleType::Leaf => 0b00100000,
        NibbleType::Extension => 0b00000000,
    };

    s.append(&ret);
}

/// Common prefix for two nibbles.
pub fn common<'a, 'b>(a: NibbleSlice<'a>, b: NibbleSlice<'b>) -> NibbleSlice<'a> {
    let mut common_len = 0;

    for i in 0..min(a.len(), b.len()) {
        if a[i] == b[i] {
            common_len += 1;
        } else {
            break;
        }
    }

    &a[0..common_len]
}

/// Common prefix for two nibbles. Return the sub nibbles.
pub fn common_with_sub<'a, 'b>(
    a: NibbleSlice<'a>,
    b: NibbleSlice<'b>,
) -> (NibbleSlice<'a>, NibbleVec, NibbleVec) {
    let common = common(a, b);
    let asub = a[common.len()..].into();
    let bsub = b[common.len()..].into();

    (common, asub, bsub)
}

/// Common prefix for all provided nibbles.
pub fn common_all<'a, T: Iterator<Item = NibbleSlice<'a>>>(mut iter: T) -> NibbleSlice<'a> {
    let first = match iter.next() {
        Some(val) => val,
        None => return &[],
    };
    let second = match iter.next() {
        Some(val) => val,
        None => return first,
    };

    let mut common_cur = common(first, second);
    for key in iter {
        common_cur = common(common_cur, key);
    }

    common_cur
}

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

    #[test]
    fn from_into_key() {
        let key = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 244, 233, 188];

        assert_eq!(key, into_key(&from_key(&key)));
    }
}