use crate::prelude::*;
use std::hash::{Hash, DefaultHasher, Hasher};

#[derive(Clone)]
pub struct ValueMap {
    values: Vec<ValueEntry>,
    size: usize,
    used: usize,
}

#[derive(Clone)]
enum ValueEntry {
    Empty,
    Taken((Value, Value)),
    Gravestone(Value),
}

impl Default for ValueMap {
    fn default() -> Self {
        ValueMap {
            values: vec![ValueEntry::Empty; 8],
            size: 8,
            used: 0,
        }
    }
}

impl ValueMap {

    fn get_index(values: &Vec<ValueEntry>, size: usize, key: &Value, hash: usize) -> usize {
        let mut nearest_grave = None;
        let start = hash & size;
        for offset in 0..size {
            let idx = (start + offset) % size;
            match &values[idx] {
                ValueEntry::Empty => return idx,
                ValueEntry::Taken((marker, _)) => {
                    if marker.eq(key) { return idx };
                    continue;
                },
                ValueEntry::Gravestone(grave) => {
                    if grave.eq(key) { return idx };
                    if nearest_grave.is_none() {
                        nearest_grave = Some(idx);
                    }
                    continue;
                },
            }
        }

        match nearest_grave {
            Some(idx) => idx,
            None => panic!("cannot get value map index: full!!!"),
        }
    }

    fn expand(&mut self) -> Result<()> {
        let pairs = self.values.iter()
            .filter_map(|e| {
                match e {
                    ValueEntry::Taken(s) => Some(s.clone()),
                    _ => None
                }
            })
            .collect::<Vec<(Value, Value)>>();

        let new_used = pairs.len();
        let new_size = self.size * 2 + pairs.len();
        let mut new_values = vec![ValueEntry::Empty; new_size];

        for (key, value) in pairs.into_iter() {
            let hash = self.hash(&key)?;
            let idx = ValueMap::get_index(&new_values, new_size, &key, hash);
            new_values[idx] = ValueEntry::Taken((key, value));
        }

        self.used = new_used;
        self.size = new_size;
        self.values = new_values;

        Ok(())
    }

    fn hash(&self, key: &Value) -> Result<usize> {
        let mut hasher = DefaultHasher::new();
        key.try_hash(&mut hasher)?;
        Ok(hasher.finish() as usize)
    }

    pub fn get<'a>(&'a self, key: &Value) -> Result<Option<&'a Value>> {
        let hash = self.hash(key)?;
        let idx = ValueMap::get_index(&self.values, self.size, key, hash);
        match &self.values[idx] {
            ValueEntry::Taken((_, value)) => Ok(Some(value)),
            _ => Ok(None)
        }
    }

    pub fn insert(&mut self, key: Value, value: Value) -> Result<()> {
        if self.used * 3 >= self.size * 2 {
            self.expand()?;
        }
        let key = key.deep_clone();
        let hash = self.hash(&key)?;
        let idx = ValueMap::get_index(&self.values, self.size, &key, hash);
        self.values[idx] = ValueEntry::Taken((key, value));
        self.used += 1;
        Ok(())
    }

    pub fn remove(&mut self, key: &Value) -> Result<Option<Value>> {
        let hash = self.hash(key)?;
        let idx = ValueMap::get_index(&self.values, self.size, key, hash);
        let mut value = ValueEntry::Gravestone(key.clone());
        std::mem::swap(&mut value, &mut self.values[idx]);
        match value {
            ValueEntry::Taken((_, v)) => {
                self.used -= 1;
                Ok(Some(v))
            }
            _ => Ok(None),
        }
    }

    pub fn entries<'a>(&'a self) -> ValueMapIterator<'a> {
        ValueMapIterator::new(self)
    }

    pub fn new() -> Self {
        Self::default()
    }

    pub fn len(&self) -> usize {
        self.used
    }
}

pub struct ValueMapIterator<'a> {
    map: &'a ValueMap,
    index: usize
}

impl<'a> ValueMapIterator<'a> {
    fn new(map: &'a ValueMap) -> Self {
        Self { map, index: 0 }
    }
}

impl<'a> Iterator for ValueMapIterator<'a> {
    type Item = (&'a Value, &'a Value);

    fn next(&mut self) -> Option<Self::Item> {
        let mut idx = self.index;
        loop {
            if idx >= self.map.size {
                return None
            }
            use ValueEntry as E;
            let E::Taken((k, v)) = &self.map.values[idx] else {
                idx += 1;
                continue;
            };

            self.index = idx + 1;
            return Some((k, v))
        }
    }
}

pub trait TryHash {
    fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()>;
}

impl TryHash for Value {
    fn try_hash<H: std::hash::Hasher>(&self, state: &mut H) -> Result<()> {
        use Value::*;
        match self {
            Nil => 0x23845.hash(state),
            Bool(b) => b.hash(state),
            Int(i) => i.hash(state),
            Ratio(r) => r.hash(state),
            Regex(r) => r.as_str().hash(state),
            String(s) => s.hash(state),
            List(l) => {
                for val in l.iter() {
                    val.try_hash(state)?;
                }
            }
            Matrix(m) => {
                m.domain.hash(state);
                m.codomain.hash(state);
                for val in m.values.iter() {
                    val.try_hash(state)?;
                }
            },
            _ => return Err(exception!(HASH_EXCEPTION, "cannot hash {self:?}"))
        };
        Ok(())
    }
}

impl ValueClone for ValueEntry {
    fn deep_clone(&self) -> Self {
        use ValueEntry as E;
        match self {
            E::Empty => E::Empty,
            E::Taken((k, v)) => E::Taken((k.deep_clone(), v.deep_clone())),
            E::Gravestone(g) => E::Gravestone(g.deep_clone()),
        }
    }

    fn shallow_clone(&self) -> Self {
        use ValueEntry as E;
        match self {
            E::Empty => E::Empty,
            E::Taken((k, v)) => E::Taken((k.clone(), v.clone())),
            E::Gravestone(g) => E::Gravestone(g.clone()),
        }
    }
}

impl ValueClone for ValueMap {
    fn deep_clone(&self) -> Self {
        let values = self.values.iter().map(|e| e.deep_clone()).collect();
        Self {
            values,
            size: self.size,
            used: self.used
        }
    }

    fn shallow_clone(&self) -> Self {
        let values = self.values.iter().map(|e| e.clone()).collect();
        Self {
            values,
            size: self.size,
            used: self.used
        }
    }
}