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

oxidize_pdf/structure/
name_tree.rs
