aada 0.1.1

//! 基于 Vec 的保序 Map：保持插入顺序并像 map 一样序列化/反序列化。
//!
//! 只在数据加载和保存过程使用，运行时不使用（运行时全走 [`crate::custom_index`] 的类型化索引）。

use std::hash::Hash;

/// 一个简单的基于 Vec 的 Map 实现，主要功能是保持插入顺序并提供类似map的序列化和反序列化，
/// 只在数据加载和保存过程使用，运行时不使用
#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Default)]
pub struct VecMap<K, V> {
    keys: Vec<K>,
    values: Vec<V>,
}

impl<K, V> VecMap<K, V> {
    /// 空容器
    pub fn new() -> Self {
        VecMap {
            keys: Vec::new(),
            values: Vec::new(),
        }
    }

    /// (键, 值) 引用迭代器（插入顺序）
    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.keys.iter().zip(self.values.iter())
    }
    /// 消费自身，返回 (键, 值) 所有权迭代器（插入顺序）
    pub fn into_pairs(self) -> impl Iterator<Item = (K, V)> {
        self.keys.into_iter().zip(self.values)
    }
    /// 按下标取键
    pub fn get_key(&self, idx: usize) -> Option<&K> {
        self.keys.get(idx)
    }
    /// 按下标取值
    pub fn get_value(&self, idx: usize) -> Option<&V> {
        self.values.get(idx)
    }
}
impl<K, V> FromIterator<(K, V)> for VecMap<K, V> {
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
        let mut keys = Vec::new();
        let mut values = Vec::new();

        for (k, v) in iter {
            keys.push(k);
            values.push(v);
        }
        Self { keys, values }
    }
}

impl<K: PartialEq, V> VecMap<K, V> {
    /// 插入（键已存在时覆盖值，不改变插入顺序）
    pub fn insert(&mut self, key: K, value: V) {
        if let Some(pos) = self.keys.iter().position(|k| k == &key) {
            self.values[pos] = value;
        } else {
            self.keys.push(key);
            self.values.push(value);
        }
    }

    /// 按键取值
    pub fn get(&self, key: &K) -> Option<&V> {
        self.keys
            .iter()
            .position(|k| k == key)
            .map(|pos| &self.values[pos])
    }
}
impl<K: Hash + Eq, V> VecMap<K, V> {
    /// 转为 `std::collections::HashMap`
    pub fn into_hashmap(self) -> std::collections::HashMap<K, V> {
        self.into_pairs().collect()
    }
}
impl<K: Ord, V> VecMap<K, V> {
    /// 转为 `std::collections::BTreeMap`（按键排序）
    pub fn into_btreemap(self) -> std::collections::BTreeMap<K, V> {
        self.into_pairs().collect()
    }
}
impl<K: PartialEq, V> std::ops::Index<&K> for VecMap<K, V> {
    type Output = V;
    fn index(&self, index: &K) -> &Self::Output {
        self.get(index).expect("Key not found in VecMap")
    }
}

mod serde {
    /// 这个模块提供VecMap的serde支持，序列化为一个map的形式，反序列化时会保持原有的插入顺序
    use super::VecMap;
    use serde::{Deserialize, Deserializer, Serialize, Serializer};
    impl<K: Serialize, V: Serialize> Serialize for VecMap<K, V> {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: Serializer,
        {
            use serde::ser::SerializeMap;
            let mut map = serializer.serialize_map(Some(self.keys.len()))?;
            for (k, v) in self.iter() {
                map.serialize_entry(k, v)?;
            }
            map.end()
        }
    }
    #[test]
    fn test_vec_map_serialize() {
        let mut map = VecMap::new();
        map.insert("a", 1);
        map.insert("b", 2);
        map.insert("f", 3); // 与自然顺序不一致，测试插入顺序保持
        map.insert("c", 4);
        map.insert("b", 5); // 测试覆盖旧值
        map.insert("z", 6);
        map.insert("h", 2);
        let json = serde_json::to_string(&map).unwrap();
        assert_eq!(json, r#"{"a":1,"b":5,"f":3,"c":4,"z":6,"h":2}"#);
    }

    impl<'de, K: Deserialize<'de> + PartialEq, V: Deserialize<'de>> Deserialize<'de> for VecMap<K, V> {
        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where
            D: Deserializer<'de>,
        {
            use serde::de::{MapAccess, Visitor};
            struct VecMapVisitor<K, V> {
                marker: std::marker::PhantomData<(K, V)>,
            }
            impl<'de, K: Deserialize<'de> + PartialEq, V: Deserialize<'de>> Visitor<'de>
                for VecMapVisitor<K, V>
            {
                type Value = VecMap<K, V>;
                fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
                where
                    M: MapAccess<'de>,
                {
                    let mut map = VecMap::new();
                    while let Some((k, v)) = access.next_entry()? {
                        map.insert(k, v);
                    }
                    Ok(map)
                }

                fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
                    formatter.write_str("a map to deserialize into VecMap")
                }
            }
            deserializer.deserialize_map(VecMapVisitor {
                marker: std::marker::PhantomData,
            })
        }
    }
    #[test]
    fn test_vec_map_deserialize() {
        let json = r#"{"a":1,"b":5,"f":3,"c":4,"z":6,"h":2}"#;
        let map: VecMap<String, i32> = serde_json::from_str(json).unwrap();
        assert_eq!(map.get(&"a".to_string()), Some(&1));
        assert_eq!(map.get(&"b".to_string()), Some(&5));
        assert_eq!(map.get(&"f".to_string()), Some(&3));
        assert_eq!(map.get(&"c".to_string()), Some(&4));
        assert_eq!(map.get(&"z".to_string()), Some(&6));
        assert_eq!(map.get(&"h".to_string()), Some(&2));
        // 测试插入顺序保持
        let keys: Vec<&String> = map.iter().map(|(k, _)| k).collect();
        assert_eq!(
            keys,
            vec![
                &"a".to_string(),
                &"b".to_string(),
                &"f".to_string(),
                &"c".to_string(),
                &"z".to_string(),
                &"h".to_string()
            ]
        );
    }
}