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

oxidize_pdf/structure/
name_tree.rs
