oxidize_pdf/structure/
name_tree.rs

1//! Name tree structure according to ISO 32000-1 Section 7.9.6
2
3use crate::error::{PdfError, Result};
4use crate::objects::{Array, Dictionary, Object, ObjectId};
5use std::collections::BTreeMap;
6
7/// Name tree node
8#[derive(Debug, Clone)]
9pub struct NameTreeNode {
10    /// Names in this node (leaf node)
11    names: Option<BTreeMap<String, Object>>,
12    /// Child nodes (intermediate node)
13    kids: Option<Vec<ObjectId>>,
14    /// Limits [min, max] for this node
15    limits: Option<(String, String)>,
16}
17
18impl NameTreeNode {
19    /// Create leaf node
20    pub fn leaf(names: BTreeMap<String, Object>) -> Self {
21        let limits = if names.is_empty() {
22            None
23        } else {
24            let min = names
25                .keys()
26                .next()
27                .expect("BTreeMap should have at least one key after is_empty check")
28                .clone();
29            let max = names
30                .keys()
31                .last()
32                .expect("BTreeMap should have at least one key after is_empty check")
33                .clone();
34            Some((min, max))
35        };
36
37        Self {
38            names: Some(names),
39            kids: None,
40            limits,
41        }
42    }
43
44    /// Create intermediate node
45    pub fn intermediate(kids: Vec<ObjectId>, limits: (String, String)) -> Self {
46        Self {
47            names: None,
48            kids: Some(kids),
49            limits: Some(limits),
50        }
51    }
52
53    /// Convert to dictionary
54    pub fn to_dict(&self) -> Dictionary {
55        let mut dict = Dictionary::new();
56
57        if let Some(names) = &self.names {
58            // Leaf node - create Names array
59            let mut names_array = Array::new();
60            for (key, value) in names {
61                names_array.push(Object::String(key.clone()));
62                names_array.push(value.clone());
63            }
64            dict.set("Names", Object::Array(names_array.into()));
65        }
66
67        if let Some(kids) = &self.kids {
68            // Intermediate node - create Kids array
69            let kids_array: Array = kids.iter().map(|id| Object::Reference(*id)).collect();
70            dict.set("Kids", Object::Array(kids_array.into()));
71        }
72
73        if let Some((min, max)) = &self.limits {
74            let limits_array = Array::from(vec![
75                Object::String(min.clone()),
76                Object::String(max.clone()),
77            ]);
78            dict.set("Limits", Object::Array(limits_array.into()));
79        }
80
81        dict
82    }
83}
84
85/// Name tree structure
86pub struct NameTree {
87    /// Root node
88    root: NameTreeNode,
89    /// All nodes (for complex trees)
90    #[allow(dead_code)]
91    nodes: BTreeMap<ObjectId, NameTreeNode>,
92}
93
94impl Default for NameTree {
95    fn default() -> Self {
96        Self::new()
97    }
98}
99
100impl NameTree {
101    /// Create new name tree with single leaf node
102    pub fn new() -> Self {
103        Self {
104            root: NameTreeNode::leaf(BTreeMap::new()),
105            nodes: BTreeMap::new(),
106        }
107    }
108
109    /// Add name-value pair
110    pub fn add(&mut self, name: String, value: Object) {
111        if let Some(names) = &mut self.root.names {
112            names.insert(name.clone(), value);
113
114            // Update limits
115            if let Some((min, max)) = &mut self.root.limits {
116                if name < *min {
117                    *min = name.clone();
118                }
119                if name > *max {
120                    *max = name;
121                }
122            } else {
123                self.root.limits = Some((name.clone(), name));
124            }
125        }
126    }
127
128    /// Get value by name
129    pub fn get(&self, name: &str) -> Option<&Object> {
130        self.root.names.as_ref()?.get(name)
131    }
132
133    /// Convert to dictionary
134    pub fn to_dict(&self) -> Dictionary {
135        self.root.to_dict()
136    }
137
138    /// Create from existing dictionary
139    pub fn from_dict(dict: &Dictionary) -> Result<Self> {
140        let mut tree = Self::new();
141
142        if let Some(Object::Array(names_array)) = dict.get("Names") {
143            let items: Vec<&Object> = names_array.iter().collect();
144
145            if items.len() % 2 != 0 {
146                return Err(PdfError::InvalidStructure(
147                    "Names array must have even length".to_string(),
148                ));
149            }
150
151            for i in (0..items.len()).step_by(2) {
152                if let (Object::String(key), value) = (items[i], items[i + 1]) {
153                    let key = key.clone();
154                    tree.add(key, value.clone());
155                }
156            }
157        }
158
159        Ok(tree)
160    }
161}
162
163/// Named destinations
164pub struct NamedDestinations {
165    /// Name tree for destinations
166    tree: NameTree,
167}
168
169impl Default for NamedDestinations {
170    fn default() -> Self {
171        Self::new()
172    }
173}
174
175impl NamedDestinations {
176    /// Create new named destinations
177    pub fn new() -> Self {
178        Self {
179            tree: NameTree::new(),
180        }
181    }
182
183    /// Add named destination
184    pub fn add_destination(&mut self, name: String, destination: Array) {
185        self.tree.add(name, Object::Array(destination.into()));
186    }
187
188    /// Get destination by name
189    pub fn get_destination(&self, name: &str) -> Option<Array> {
190        match self.tree.get(name)? {
191            Object::Array(arr) => Some(Array::from(arr.clone())),
192            _ => None,
193        }
194    }
195
196    /// Convert to dictionary
197    pub fn to_dict(&self) -> Dictionary {
198        self.tree.to_dict()
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use super::*;
205
206    #[test]
207    fn test_name_tree_node_leaf() {
208        let mut names = BTreeMap::new();
209        names.insert("First".to_string(), Object::Integer(1));
210        names.insert("Second".to_string(), Object::Integer(2));
211
212        let node = NameTreeNode::leaf(names);
213        assert!(node.names.is_some());
214        assert!(node.kids.is_none());
215        assert_eq!(
216            node.limits,
217            Some(("First".to_string(), "Second".to_string()))
218        );
219    }
220
221    #[test]
222    fn test_name_tree_add() {
223        let mut tree = NameTree::new();
224        tree.add("Apple".to_string(), Object::Integer(1));
225        tree.add("Banana".to_string(), Object::Integer(2));
226        tree.add("Cherry".to_string(), Object::Integer(3));
227
228        assert_eq!(tree.get("Banana"), Some(&Object::Integer(2)));
229        assert_eq!(
230            tree.root.limits,
231            Some(("Apple".to_string(), "Cherry".to_string()))
232        );
233    }
234
235    #[test]
236    fn test_name_tree_to_dict() {
237        let mut tree = NameTree::new();
238        tree.add("Test".to_string(), Object::Boolean(true));
239
240        let dict = tree.to_dict();
241        assert!(dict.get("Names").is_some());
242    }
243
244    #[test]
245    fn test_named_destinations() {
246        use crate::structure::destination::{Destination, PageDestination};
247
248        let mut dests = NamedDestinations::new();
249        let dest = Destination::fit(PageDestination::PageNumber(0));
250        dests.add_destination("Home".to_string(), dest.to_array());
251
252        let retrieved = dests.get_destination("Home");
253        assert!(retrieved.is_some());
254    }
255
256    #[test]
257    fn test_name_tree_from_dict() {
258        let mut dict = Dictionary::new();
259        let names_array = Array::from(vec![
260            Object::String("First".to_string()),
261            Object::Integer(1),
262            Object::String("Second".to_string()),
263            Object::Integer(2),
264        ]);
265        dict.set("Names", Object::Array(names_array.into()));
266
267        let tree = NameTree::from_dict(&dict).unwrap();
268        assert_eq!(tree.get("First"), Some(&Object::Integer(1)));
269        assert_eq!(tree.get("Second"), Some(&Object::Integer(2)));
270    }
271
272    #[test]
273    fn test_name_tree_node_debug_clone() {
274        let mut names = BTreeMap::new();
275        names.insert("Test".to_string(), Object::Boolean(true));
276        let node = NameTreeNode::leaf(names);
277
278        let debug_str = format!("{node:?}");
279        assert!(debug_str.contains("NameTreeNode"));
280
281        let cloned = node.clone();
282        assert_eq!(cloned.limits, node.limits);
283    }
284
285    #[test]
286    fn test_name_tree_node_intermediate() {
287        let kids = vec![ObjectId::new(10, 0), ObjectId::new(20, 0)];
288        let limits = ("Alpha".to_string(), "Zeta".to_string());
289
290        let node = NameTreeNode::intermediate(kids.clone(), limits.clone());
291        assert!(node.names.is_none());
292        assert_eq!(node.kids, Some(kids));
293        assert_eq!(node.limits, Some(limits));
294    }
295
296    #[test]
297    fn test_name_tree_node_empty_leaf() {
298        let node = NameTreeNode::leaf(BTreeMap::new());
299        assert!(node.names.is_some());
300        assert!(node.limits.is_none());
301
302        let dict = node.to_dict();
303        assert!(dict.get("Names").is_some());
304        assert!(dict.get("Limits").is_none());
305    }
306
307    #[test]
308    fn test_name_tree_node_to_dict_intermediate() {
309        let kids = vec![ObjectId::new(5, 0), ObjectId::new(6, 0)];
310        let limits = ("A".to_string(), "M".to_string());
311        let node = NameTreeNode::intermediate(kids, limits);
312
313        let dict = node.to_dict();
314        assert!(dict.get("Kids").is_some());
315        assert!(dict.get("Limits").is_some());
316        assert!(dict.get("Names").is_none());
317
318        // Verify Kids array
319        match dict.get("Kids") {
320            Some(Object::Array(arr)) => {
321                assert_eq!(arr.len(), 2);
322                assert!(matches!(arr.first(), Some(Object::Reference(_))));
323            }
324            _ => panic!("Kids should be an array"),
325        }
326
327        // Verify Limits array
328        match dict.get("Limits") {
329            Some(Object::Array(arr)) => {
330                assert_eq!(arr.len(), 2);
331                assert_eq!(arr.first(), Some(&Object::String("A".to_string())));
332                assert_eq!(arr.get(1), Some(&Object::String("M".to_string())));
333            }
334            _ => panic!("Limits should be an array"),
335        }
336    }
337
338    #[test]
339    fn test_name_tree_default() {
340        let tree = NameTree::default();
341        assert!(tree.root.names.is_some());
342        assert_eq!(tree.get("anything"), None);
343    }
344
345    #[test]
346    fn test_name_tree_add_updates_limits() {
347        let mut tree = NameTree::new();
348
349        // Add first item
350        tree.add("Middle".to_string(), Object::Integer(1));
351        assert_eq!(
352            tree.root.limits,
353            Some(("Middle".to_string(), "Middle".to_string()))
354        );
355
356        // Add item before
357        tree.add("Beginning".to_string(), Object::Integer(2));
358        assert_eq!(
359            tree.root.limits,
360            Some(("Beginning".to_string(), "Middle".to_string()))
361        );
362
363        // Add item after
364        tree.add("Zulu".to_string(), Object::Integer(3));
365        assert_eq!(
366            tree.root.limits,
367            Some(("Beginning".to_string(), "Zulu".to_string()))
368        );
369    }
370
371    #[test]
372    fn test_name_tree_add_multiple() {
373        let mut tree = NameTree::new();
374
375        // Add items in non-alphabetical order
376        let items = vec![
377            ("Dog", Object::Integer(1)),
378            ("Apple", Object::Integer(2)),
379            ("Cat", Object::Integer(3)),
380            ("Banana", Object::Integer(4)),
381        ];
382
383        for (name, value) in items {
384            tree.add(name.to_string(), value);
385        }
386
387        // Verify all items are retrievable
388        assert_eq!(tree.get("Dog"), Some(&Object::Integer(1)));
389        assert_eq!(tree.get("Apple"), Some(&Object::Integer(2)));
390        assert_eq!(tree.get("Cat"), Some(&Object::Integer(3)));
391        assert_eq!(tree.get("Banana"), Some(&Object::Integer(4)));
392
393        // Verify limits
394        assert_eq!(
395            tree.root.limits,
396            Some(("Apple".to_string(), "Dog".to_string()))
397        );
398    }
399
400    #[test]
401    fn test_name_tree_get_nonexistent() {
402        let mut tree = NameTree::new();
403        tree.add("Exists".to_string(), Object::Boolean(true));
404
405        assert!(tree.get("Exists").is_some());
406        assert!(tree.get("DoesNotExist").is_none());
407    }
408
409    #[test]
410    fn test_name_tree_to_dict_multiple_entries() {
411        let mut tree = NameTree::new();
412        tree.add("First".to_string(), Object::Integer(1));
413        tree.add("Second".to_string(), Object::Integer(2));
414        tree.add("Third".to_string(), Object::Integer(3));
415
416        let dict = tree.to_dict();
417
418        match dict.get("Names") {
419            Some(Object::Array(arr)) => {
420                assert_eq!(arr.len(), 6); // 3 key-value pairs = 6 elements
421                                          // Names array should be: ["First", 1, "Second", 2, "Third", 3]
422                assert_eq!(arr.first(), Some(&Object::String("First".to_string())));
423                assert_eq!(arr.get(1), Some(&Object::Integer(1)));
424                assert_eq!(arr.get(2), Some(&Object::String("Second".to_string())));
425                assert_eq!(arr.get(3), Some(&Object::Integer(2)));
426            }
427            _ => panic!("Names should be an array"),
428        }
429    }
430
431    #[test]
432    fn test_name_tree_from_dict_empty() {
433        let dict = Dictionary::new();
434        let tree = NameTree::from_dict(&dict).unwrap();
435        assert!(tree.root.names.is_some());
436        assert_eq!(tree.get("anything"), None);
437    }
438
439    #[test]
440    fn test_name_tree_from_dict_odd_length_array() {
441        let mut dict = Dictionary::new();
442        let names_array = Array::from(vec![
443            Object::String("First".to_string()),
444            Object::Integer(1),
445            Object::String("Second".to_string()),
446            // Missing value for "Second"
447        ]);
448        dict.set("Names", Object::Array(names_array.into()));
449
450        let result = NameTree::from_dict(&dict);
451        assert!(result.is_err());
452    }
453
454    #[test]
455    fn test_name_tree_from_dict_non_string_keys() {
456        let mut dict = Dictionary::new();
457        let names_array = Array::from(vec![
458            Object::Integer(123), // Not a string
459            Object::Integer(1),
460            Object::String("Valid".to_string()),
461            Object::Integer(2),
462        ]);
463        dict.set("Names", Object::Array(names_array.into()));
464
465        let tree = NameTree::from_dict(&dict).unwrap();
466        // Should only have the valid entry
467        assert_eq!(tree.get("Valid"), Some(&Object::Integer(2)));
468        assert!(tree.get("123").is_none());
469    }
470
471    #[test]
472    fn test_name_tree_from_dict_various_value_types() {
473        let mut dict = Dictionary::new();
474        let names_array = Array::from(vec![
475            Object::String("Bool".to_string()),
476            Object::Boolean(true),
477            Object::String("Real".to_string()),
478            Object::Real(std::f64::consts::PI),
479            Object::String("Ref".to_string()),
480            Object::Reference(ObjectId::new(5, 0)),
481        ]);
482        dict.set("Names", Object::Array(names_array.into()));
483
484        let tree = NameTree::from_dict(&dict).unwrap();
485        assert_eq!(tree.get("Bool"), Some(&Object::Boolean(true)));
486        assert_eq!(tree.get("Real"), Some(&Object::Real(std::f64::consts::PI)));
487        assert_eq!(
488            tree.get("Ref"),
489            Some(&Object::Reference(ObjectId::new(5, 0)))
490        );
491    }
492
493    #[test]
494    fn test_named_destinations_default() {
495        let dests = NamedDestinations::default();
496        assert!(dests.get_destination("anything").is_none());
497    }
498
499    #[test]
500    fn test_named_destinations_add_and_get() {
501        use crate::structure::destination::{Destination, PageDestination};
502
503        let mut dests = NamedDestinations::new();
504
505        // Add various types of destinations
506        let dest1 = Destination::fit(PageDestination::PageNumber(0));
507        let dest2 = Destination::xyz(
508            PageDestination::PageNumber(5),
509            Some(100.0),
510            Some(200.0),
511            None,
512        );
513
514        dests.add_destination("TOC".to_string(), dest1.to_array());
515        dests.add_destination("Chapter1".to_string(), dest2.to_array());
516
517        // Retrieve and verify
518        let toc = dests.get_destination("TOC");
519        assert!(toc.is_some());
520        assert!(toc.unwrap().len() >= 2);
521
522        let ch1 = dests.get_destination("Chapter1");
523        assert!(ch1.is_some());
524        assert!(ch1.unwrap().len() >= 5); // XYZ has 5 elements
525
526        assert!(dests.get_destination("NotFound").is_none());
527    }
528
529    #[test]
530    fn test_named_destinations_to_dict() {
531        use crate::structure::destination::{Destination, PageDestination};
532
533        let mut dests = NamedDestinations::new();
534        let dest = Destination::fit(PageDestination::PageNumber(10));
535        dests.add_destination("Appendix".to_string(), dest.to_array());
536
537        let dict = dests.to_dict();
538        assert!(dict.get("Names").is_some());
539    }
540
541    #[test]
542    fn test_named_destinations_get_non_array_value() {
543        let mut dests = NamedDestinations::new();
544        // Manually add a non-array value to the tree
545        dests.tree.add("Invalid".to_string(), Object::Integer(123));
546
547        // Should return None for non-array values
548        assert!(dests.get_destination("Invalid").is_none());
549    }
550
551    #[test]
552    fn test_name_tree_case_sensitive() {
553        let mut tree = NameTree::new();
554        tree.add("Test".to_string(), Object::Integer(1));
555        tree.add("test".to_string(), Object::Integer(2));
556        tree.add("TEST".to_string(), Object::Integer(3));
557
558        assert_eq!(tree.get("Test"), Some(&Object::Integer(1)));
559        assert_eq!(tree.get("test"), Some(&Object::Integer(2)));
560        assert_eq!(tree.get("TEST"), Some(&Object::Integer(3)));
561    }
562
563    #[test]
564    fn test_name_tree_unicode_names() {
565        let mut tree = NameTree::new();
566        tree.add("café".to_string(), Object::Integer(1));
567        tree.add("naïve".to_string(), Object::Integer(2));
568        tree.add("日本語".to_string(), Object::Integer(3));
569        tree.add("🎉".to_string(), Object::Integer(4));
570
571        assert_eq!(tree.get("café"), Some(&Object::Integer(1)));
572        assert_eq!(tree.get("naïve"), Some(&Object::Integer(2)));
573        assert_eq!(tree.get("日本語"), Some(&Object::Integer(3)));
574        assert_eq!(tree.get("🎉"), Some(&Object::Integer(4)));
575    }
576
577    #[test]
578    fn test_name_tree_empty_string_key() {
579        let mut tree = NameTree::new();
580        tree.add("".to_string(), Object::Boolean(true));
581        tree.add("Normal".to_string(), Object::Boolean(false));
582
583        assert_eq!(tree.get(""), Some(&Object::Boolean(true)));
584        assert_eq!(tree.get("Normal"), Some(&Object::Boolean(false)));
585    }
586
587    #[test]
588    fn test_name_tree_overwrite_value() {
589        let mut tree = NameTree::new();
590        tree.add("Key".to_string(), Object::Integer(1));
591        tree.add("Key".to_string(), Object::Integer(2)); // Overwrite
592
593        assert_eq!(tree.get("Key"), Some(&Object::Integer(2)));
594    }
595
596    #[test]
597    fn test_name_tree_dictionary_values() {
598        let mut tree = NameTree::new();
599
600        let mut dict_value = Dictionary::new();
601        dict_value.set("Type", Object::Name("Test".to_string()));
602        dict_value.set("Count", Object::Integer(42));
603
604        tree.add(
605            "DictEntry".to_string(),
606            Object::Dictionary(dict_value.clone()),
607        );
608
609        match tree.get("DictEntry") {
610            Some(Object::Dictionary(d)) => {
611                assert_eq!(d.get("Type"), Some(&Object::Name("Test".to_string())));
612                assert_eq!(d.get("Count"), Some(&Object::Integer(42)));
613            }
614            _ => panic!("Should get dictionary value"),
615        }
616    }
617
618    #[test]
619    fn test_name_tree_array_values() {
620        let mut tree = NameTree::new();
621
622        let array_value = Array::from(vec![
623            Object::Integer(1),
624            Object::Integer(2),
625            Object::Integer(3),
626        ]);
627
628        tree.add("ArrayEntry".to_string(), Object::Array(array_value.into()));
629
630        match tree.get("ArrayEntry") {
631            Some(Object::Array(arr)) => {
632                assert_eq!(arr.len(), 3);
633                assert_eq!(arr.first(), Some(&Object::Integer(1)));
634            }
635            _ => panic!("Should get array value"),
636        }
637    }
638
639    #[test]
640    fn test_name_tree_btree_ordering() {
641        let mut tree = NameTree::new();
642
643        // Add items in random order
644        let items = ["Zebra", "Alpha", "Mike", "Charlie", "Bravo"];
645        for (i, name) in items.iter().enumerate() {
646            tree.add(name.to_string(), Object::Integer(i as i64));
647        }
648
649        // Convert to dict and check that names are in sorted order
650        let dict = tree.to_dict();
651        match dict.get("Names") {
652            Some(Object::Array(arr)) => {
653                // BTreeMap should maintain sorted order
654                assert_eq!(arr.first(), Some(&Object::String("Alpha".to_string())));
655                assert_eq!(arr.get(2), Some(&Object::String("Bravo".to_string())));
656                assert_eq!(arr.get(4), Some(&Object::String("Charlie".to_string())));
657                assert_eq!(arr.get(6), Some(&Object::String("Mike".to_string())));
658                assert_eq!(arr.get(8), Some(&Object::String("Zebra".to_string())));
659            }
660            _ => panic!("Names should be an array"),
661        }
662    }
663}
oxidize_pdf/structure/name_tree.rs

oxidize_pdf/structure/
name_tree.rs
