//! QPDF Name Tree helper (PDF spec section 7.9.6)
//!
//! Name Trees map string keys to PDF objects. They have:
//! - **Names**: array of alternating key-value pairs (string, object) in leaf nodes
//! - **Kids**: array of references to child nodes in intermediate nodes
//! - **Limits**: array [min_key, max_key] for range of keys in node or descendants

use std::collections::HashMap;

use crate::pdf::object::{Array, Dict, Name, ObjRef, Object, PdfString};

/// Helper for reading PDF Name Tree nodes.
///
/// Wraps a dictionary that represents a Name Tree node (leaf or intermediate).
/// Supports both flat (single-node) and hierarchical (multi-node) trees.
#[derive(Debug)]
pub struct NameTreeHelper<'a> {
    dict: &'a Dict,
}

impl<'a> NameTreeHelper<'a> {
    /// Create a helper for the given Name Tree dictionary.
    pub fn new(dict: &'a Dict) -> Self {
        Self { dict }
    }

    /// Look up a name in the tree. Resolves indirect references via `objects`.
    pub fn get(&self, key: &str, objects: &HashMap<ObjRef, Object>) -> Option<Object> {
        if let Some(names) = self
            .dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
        {
            // Leaf node: search Names array (alternating key, value)
            Self::search_names_array(names, key)
        } else if let Some(kids) = self.dict.get(&Name::new("Kids")).and_then(Object::as_array) {
            // Intermediate node: find child by Limits, recurse
            for kid in kids {
                let kid_ref = kid.as_obj_ref()?;
                let kid_obj = objects.get(&kid_ref)?;
                let kid_dict = kid_obj.as_dict()?;
                let helper = NameTreeHelper::new(kid_dict);
                if let Some(value) = helper.get(key, objects) {
                    return Some(value);
                }
            }
            None
        } else {
            None
        }
    }

    /// Get all key-value pairs from the tree, in sorted order.
    pub fn get_all_entries(&self, objects: &HashMap<ObjRef, Object>) -> Vec<(String, Object)> {
        if let Some(names) = self
            .dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
        {
            // Leaf node: collect from Names array
            Self::collect_from_names_array(names)
        } else if let Some(kids) = self.dict.get(&Name::new("Kids")).and_then(Object::as_array) {
            // Intermediate node: recurse into each child
            let mut entries = Vec::new();
            for kid in kids {
                let kid_ref = match kid.as_obj_ref() {
                    Some(r) => r,
                    None => continue,
                };
                let kid_obj = match objects.get(&kid_ref) {
                    Some(o) => o,
                    None => continue,
                };
                let kid_dict = match kid_obj.as_dict() {
                    Some(d) => d,
                    None => continue,
                };
                let helper = NameTreeHelper::new(kid_dict);
                entries.extend(helper.get_all_entries(objects));
            }
            entries
        } else {
            Vec::new()
        }
    }

    /// Check if the tree contains the given key.
    pub fn has_key(&self, key: &str, objects: &HashMap<ObjRef, Object>) -> bool {
        self.get(key, objects).is_some()
    }

    /// Get the Limits array as (min_key, max_key) if present.
    pub fn limits(&self) -> Option<(String, String)> {
        let limits = self
            .dict
            .get(&Name::new("Limits"))
            .and_then(Object::as_array)?;
        if limits.len() >= 2 {
            let min_key = limits[0]
                .as_string()
                .and_then(|s| s.as_str().map(String::from))?;
            let max_key = limits[1]
                .as_string()
                .and_then(|s| s.as_str().map(String::from))?;
            Some((min_key, max_key))
        } else {
            None
        }
    }

    fn search_names_array(names: &Array, key: &str) -> Option<Object> {
        let mut i = 0;
        while i + 1 < names.len() {
            let k = names[i].as_string().and_then(|s| s.as_str())?;
            if k == key {
                return Some(names[i + 1].clone());
            }
            i += 2;
        }
        None
    }

    fn collect_from_names_array(names: &Array) -> Vec<(String, Object)> {
        let mut entries = Vec::new();
        let mut i = 0;
        while i + 1 < names.len() {
            if let Some(k) = names[i]
                .as_string()
                .and_then(|s| s.as_str().map(String::from))
            {
                entries.push((k, names[i + 1].clone()));
            }
            i += 2;
        }
        entries
    }
}

/// Helper for mutating PDF Name Tree nodes (flat trees with Names array only).
///
/// Supports insert and remove on leaf nodes. For hierarchical trees,
/// use the immutable helper to locate the leaf, then wrap that dict.
#[derive(Debug)]
pub struct NameTreeHelperMut<'a> {
    dict: &'a mut Dict,
}

impl<'a> NameTreeHelperMut<'a> {
    /// Create a mutable helper for the given Name Tree dictionary.
    pub fn new(dict: &'a mut Dict) -> Self {
        Self { dict }
    }

    /// Insert a key-value pair into the flat Names array.
    /// Maintains sorted order by key. Replaces existing value if key exists.
    pub fn insert(&mut self, key: &str, value: Object) {
        let names = self
            .dict
            .entry(Name::new("Names"))
            .or_insert_with(|| Object::Array(Vec::new()));
        let arr = match names.as_array_mut() {
            Some(a) => a,
            None => return,
        };

        let key_obj = Object::String(PdfString::new(key.as_bytes().to_vec()));

        // Find insertion point (binary search for sorted order)
        let mut i = 0;
        while i < arr.len() {
            if let Some(k) = arr[i].as_string().and_then(|s| s.as_str()) {
                match k.cmp(key) {
                    std::cmp::Ordering::Equal => {
                        arr[i + 1] = value.clone();
                        self.update_limits();
                        return;
                    }
                    std::cmp::Ordering::Greater => break,
                    std::cmp::Ordering::Less => {}
                }
            }
            i += 2;
        }

        arr.insert(i, key_obj);
        arr.insert(i + 1, value);
        self.update_limits();
    }

    /// Remove a key from the flat Names array. Returns the value if found.
    pub fn remove(&mut self, key: &str) -> Option<Object> {
        let arr = self
            .dict
            .get_mut(&Name::new("Names"))
            .and_then(Object::as_array_mut)?;
        let mut i = 0;
        while i + 1 < arr.len() {
            if arr[i].as_string().and_then(|s| s.as_str()) == Some(key) {
                let value = arr.remove(i + 1);
                arr.remove(i);
                self.update_limits();
                return Some(value);
            }
            i += 2;
        }
        None
    }

    fn update_limits(&mut self) {
        let arr = match self
            .dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
        {
            Some(a) => a,
            None => return,
        };
        if arr.len() >= 2 {
            let min = arr[0]
                .as_string()
                .and_then(|s| s.as_str().map(String::from));
            let last_key_idx = arr.len() - 2;
            let max = arr[last_key_idx]
                .as_string()
                .and_then(|s| s.as_str().map(String::from));
            if let (Some(min), Some(max)) = (min, max) {
                self.dict.insert(
                    Name::new("Limits"),
                    Object::Array(vec![
                        Object::String(PdfString::new(min.into_bytes())),
                        Object::String(PdfString::new(max.into_bytes())),
                    ]),
                );
            }
        } else {
            self.dict.remove(&Name::new("Limits"));
        }
    }
}

/// Build a Name Tree dictionary from flat entries.
///
/// Entries are sorted by key. Produces a single-node tree with Names and Limits.
pub fn build_name_tree(entries: Vec<(String, Object)>) -> Object {
    let mut sorted = entries;
    sorted.sort_by(|a, b| a.0.cmp(&b.0));

    let mut names = Array::new();
    let mut min_key: Option<String> = None;
    let mut max_key: Option<String> = None;

    for (k, v) in sorted {
        if min_key.is_none() {
            min_key = Some(k.clone());
        }
        max_key = Some(k.clone());
        names.push(Object::String(PdfString::new(k.into_bytes())));
        names.push(v);
    }

    let mut dict = Dict::new();
    dict.insert(Name::new("Names"), Object::Array(names));
    if let (Some(min), Some(max)) = (min_key, max_key) {
        dict.insert(
            Name::new("Limits"),
            Object::Array(vec![
                Object::String(PdfString::new(min.into_bytes())),
                Object::String(PdfString::new(max.into_bytes())),
            ]),
        );
    }

    Object::Dict(dict)
}

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

    fn make_objects() -> HashMap<ObjRef, Object> {
        HashMap::new()
    }

    #[test]
    fn test_name_tree_helper_new() {
        let dict = Dict::new();
        let helper = NameTreeHelper::new(&dict);
        assert!(helper.limits().is_none());
    }

    #[test]
    fn test_name_tree_helper_limits() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Limits"),
            Object::Array(vec![
                Object::String(PdfString::new(b"Alice".to_vec())),
                Object::String(PdfString::new(b"Bob".to_vec())),
            ]),
        );
        let helper = NameTreeHelper::new(&dict);
        let (min, max) = helper.limits().unwrap();
        assert_eq!(min, "Alice");
        assert_eq!(max, "Bob");
    }

    #[test]
    fn test_name_tree_helper_limits_invalid() {
        let mut dict = Dict::new();
        dict.insert(Name::new("Limits"), Object::Array(vec![]));
        let helper = NameTreeHelper::new(&dict);
        assert!(helper.limits().is_none());
    }

    #[test]
    fn test_name_tree_helper_get_leaf() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"alpha".to_vec())),
                Object::Int(1),
                Object::String(PdfString::new(b"beta".to_vec())),
                Object::Int(2),
                Object::String(PdfString::new(b"gamma".to_vec())),
                Object::Int(3),
            ]),
        );
        let helper = NameTreeHelper::new(&dict);
        let objects = make_objects();

        assert_eq!(
            helper.get("alpha", &objects).and_then(|o| o.as_int()),
            Some(1)
        );
        assert_eq!(
            helper.get("beta", &objects).and_then(|o| o.as_int()),
            Some(2)
        );
        assert_eq!(
            helper.get("gamma", &objects).and_then(|o| o.as_int()),
            Some(3)
        );
        assert!(helper.get("delta", &objects).is_none());
        assert!(helper.get("", &objects).is_none());
    }

    #[test]
    fn test_name_tree_helper_get_hierarchical() {
        let mut leaf = Dict::new();
        leaf.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"x".to_vec())),
                Object::Int(42),
            ]),
        );
        leaf.insert(
            Name::new("Limits"),
            Object::Array(vec![
                Object::String(PdfString::new(b"x".to_vec())),
                Object::String(PdfString::new(b"x".to_vec())),
            ]),
        );

        let leaf_ref = ObjRef::new(10, 0);
        let mut root = Dict::new();
        root.insert(
            Name::new("Kids"),
            Object::Array(vec![Object::Ref(leaf_ref)]),
        );

        let mut objects = HashMap::new();
        objects.insert(leaf_ref, Object::Dict(leaf));

        let helper = NameTreeHelper::new(&root);
        assert_eq!(helper.get("x", &objects).and_then(|o| o.as_int()), Some(42));
        assert!(helper.get("y", &objects).is_none());
    }

    #[test]
    fn test_name_tree_helper_get_all_entries_leaf() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"a".to_vec())),
                Object::Int(1),
                Object::String(PdfString::new(b"b".to_vec())),
                Object::Int(2),
            ]),
        );
        let helper = NameTreeHelper::new(&dict);
        let objects = make_objects();
        let entries = helper.get_all_entries(&objects);
        assert_eq!(entries.len(), 2);
        assert_eq!(entries[0].0, "a");
        assert_eq!(entries[0].1.as_int(), Some(1));
        assert_eq!(entries[1].0, "b");
        assert_eq!(entries[1].1.as_int(), Some(2));
    }

    #[test]
    fn test_name_tree_helper_get_all_entries_empty() {
        let dict = Dict::new();
        let helper = NameTreeHelper::new(&dict);
        let objects = make_objects();
        assert!(helper.get_all_entries(&objects).is_empty());
    }

    #[test]
    fn test_name_tree_helper_has_key() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"foo".to_vec())),
                Object::Null,
            ]),
        );
        let helper = NameTreeHelper::new(&dict);
        let objects = make_objects();
        assert!(helper.has_key("foo", &objects));
        assert!(!helper.has_key("bar", &objects));
    }

    #[test]
    fn test_name_tree_helper_mut_new() {
        let mut dict = Dict::new();
        let _helper = NameTreeHelperMut::new(&mut dict);
    }

    #[test]
    fn test_name_tree_helper_mut_insert() {
        let mut dict = Dict::new();
        dict.insert(Name::new("Names"), Object::Array(Vec::new()));

        {
            let mut helper = NameTreeHelperMut::new(&mut dict);
            helper.insert("b", Object::Int(2));
            helper.insert("a", Object::Int(1));
            helper.insert("c", Object::Int(3));
        }

        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert_eq!(names.len(), 6); // a,1, b,2, c,3
        assert_eq!(names[0].as_string().and_then(|s| s.as_str()), Some("a"));
        assert_eq!(names[1].as_int(), Some(1));
        assert_eq!(names[2].as_string().and_then(|s| s.as_str()), Some("b"));
        assert_eq!(names[3].as_int(), Some(2));
        assert_eq!(names[4].as_string().and_then(|s| s.as_str()), Some("c"));
        assert_eq!(names[5].as_int(), Some(3));
    }

    #[test]
    fn test_name_tree_helper_mut_insert_replace() {
        let mut dict = Dict::new();
        dict.insert(Name::new("Names"), Object::Array(Vec::new()));

        {
            let mut helper = NameTreeHelperMut::new(&mut dict);
            helper.insert("key", Object::Int(1));
            helper.insert("key", Object::Int(99));
        }

        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert_eq!(names.len(), 2);
        assert_eq!(names[1].as_int(), Some(99));
    }

    #[test]
    fn test_name_tree_helper_mut_remove() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"a".to_vec())),
                Object::Int(1),
                Object::String(PdfString::new(b"b".to_vec())),
                Object::Int(2),
            ]),
        );

        {
            let mut helper = NameTreeHelperMut::new(&mut dict);
            let removed = helper.remove("b");
            assert_eq!(removed.and_then(|o| o.as_int()), Some(2));
        }

        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert_eq!(names.len(), 2);
        assert_eq!(names[0].as_string().and_then(|s| s.as_str()), Some("a"));
        assert_eq!(names[1].as_int(), Some(1));
    }

    #[test]
    fn test_name_tree_helper_mut_remove_nonexistent() {
        let mut dict = Dict::new();
        dict.insert(
            Name::new("Names"),
            Object::Array(vec![
                Object::String(PdfString::new(b"a".to_vec())),
                Object::Int(1),
            ]),
        );

        {
            let mut helper = NameTreeHelperMut::new(&mut dict);
            assert!(helper.remove("b").is_none());
        }

        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert_eq!(names.len(), 2);
    }

    #[test]
    fn test_name_tree_helper_mut_remove_empty() {
        let mut dict = Dict::new();
        let mut helper = NameTreeHelperMut::new(&mut dict);
        assert!(helper.remove("x").is_none());
    }

    #[test]
    fn test_build_name_tree() {
        let entries = vec![
            ("z".to_string(), Object::Int(3)),
            ("a".to_string(), Object::Int(1)),
            ("m".to_string(), Object::Int(2)),
        ];
        let obj = build_name_tree(entries);
        let dict = obj.as_dict().unwrap();

        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert_eq!(names[0].as_string().and_then(|s| s.as_str()), Some("a"));
        assert_eq!(names[1].as_int(), Some(1));
        assert_eq!(names[2].as_string().and_then(|s| s.as_str()), Some("m"));
        assert_eq!(names[3].as_int(), Some(2));
        assert_eq!(names[4].as_string().and_then(|s| s.as_str()), Some("z"));
        assert_eq!(names[5].as_int(), Some(3));

        let (min, max) = NameTreeHelper::new(dict).limits().unwrap();
        assert_eq!(min, "a");
        assert_eq!(max, "z");
    }

    #[test]
    fn test_build_name_tree_empty() {
        let obj = build_name_tree(Vec::new());
        let dict = obj.as_dict().unwrap();
        assert!(dict.contains_key(&Name::new("Names")));
        assert!(!dict.contains_key(&Name::new("Limits")));
        let names = dict
            .get(&Name::new("Names"))
            .and_then(Object::as_array)
            .unwrap();
        assert!(names.is_empty());
    }

    #[test]
    fn test_build_name_tree_single() {
        let obj = build_name_tree(vec![("only".to_string(), Object::Bool(true))]);
        let dict = obj.as_dict().unwrap();
        let (min, max) = NameTreeHelper::new(dict).limits().unwrap();
        assert_eq!(min, "only");
        assert_eq!(max, "only");
    }

    #[test]
    fn test_roundtrip_build_and_get() {
        let entries = vec![
            (
                "k1".to_string(),
                Object::String(PdfString::new(b"v1".to_vec())),
            ),
            ("k2".to_string(), Object::Name(Name::new("V2"))),
        ];
        let obj = build_name_tree(entries);
        let dict = obj.as_dict().unwrap();
        let helper = NameTreeHelper::new(dict);
        let objects = make_objects();

        assert_eq!(
            helper
                .get("k1", &objects)
                .and_then(|o| o.as_string().map(|s| s.as_bytes().to_vec())),
            Some(b"v1".to_vec())
        );
        assert_eq!(
            helper
                .get("k2", &objects)
                .and_then(|o| o.as_name().map(|n| n.as_str().to_string())),
            Some("V2".to_string())
        );
    }
}
