Add iterators to name/number tree helpers

3 files changed, 309 insertions, 6 deletions

diff --git a/libtests/nntree.cc b/libtests/nntree.cc
index 49081405..7ef069c3 100644
--- a/libtests/nntree.cc
+++ b/libtests/nntree.cc
@@ -1,8 +1,11 @@
 #include <qpdf/QPDFNumberTreeObjectHelper.hh>
+#include <qpdf/QPDFNameTreeObjectHelper.hh>
 #include <qpdf/QPDF.hh>
 #include <qpdf/QUtil.hh>
 #include <iostream>
 
+static bool any_failures = false;
+
 bool report(QPDFObjectHandle oh, long long item, long long exp_item)
 {
     QPDFNumberTreeObjectHelper nh(oh);
@@ -56,7 +59,7 @@ bool report(QPDFObjectHandle oh, long long item, long long exp_item)
     return failed;
 }
 
-int main()
+void test_bsearch()
 {
     QPDF q;
     q.emptyPDF();
@@ -78,8 +81,7 @@ int main()
         return node;
     };
 
-    bool any_failures = false;
-    auto r = [&any_failures](QPDFObjectHandle& oh, int item, int exp) {
+    auto r = [](QPDFObjectHandle& oh, int item, int exp) {
         if (report(oh, item, exp))
         {
             any_failures = true;
@@ -119,6 +121,133 @@ int main()
 
     if (! any_failures)
     {
-        std::cout << "all tests passed" << std::endl;
+        std::cout << "bsearch tests passed" << std::endl;
+    }
+}
+
+QPDFObjectHandle new_node(QPDF& q, std::string const& key)
+{
+    auto dict = QPDFObjectHandle::newDictionary();
+    dict.replaceKey(key, QPDFObjectHandle::newArray());
+    return q.makeIndirectObject(dict);
+}
+
+static void check_find(QPDFNameTreeObjectHelper& nh,
+                       std::string const& key, bool prev_if_not_found)
+{
+    auto i = nh.find(key, prev_if_not_found);
+    std::cout << "find " << key << " (" << prev_if_not_found << "): ";
+    if (i == nh.end())
+    {
+        std::cout << "not found";
+    }
+    else
+    {
+        std::cout << (*i).first << " -> " << (*i).second.unparse();
+    }
+    std::cout << std::endl;
+}
+
+void test_depth()
+{
+    int constexpr NITEMS = 3;
+    QPDF q;
+    q.emptyPDF();
+    auto root = q.getRoot();
+    auto n0 = new_node(q, "/Kids");
+    root.replaceKey("/NT", n0);
+    auto k0 = root.getKey("/NT").getKey("/Kids");
+    for (int i1 = 0; i1 < NITEMS; ++i1)
+    {
+        auto n1 = new_node(q, "/Kids");
+        k0.appendItem(n1);
+        auto k1 = n1.getKey("/Kids");
+        for (int i2 = 0; i2 < NITEMS; ++i2)
+        {
+            auto n2 = new_node(q, "/Kids");
+            k1.appendItem(n2);
+            auto k2 = n2.getKey("/Kids");
+            for (int i3 = 0; i3 < NITEMS; ++i3)
+            {
+                auto n3 = new_node(q, "/Names");
+                k2.appendItem(n3);
+                auto items = n3.getKey("/Names");
+                std::string first;
+                std::string last;
+                for (int i4 = 0; i4 < NITEMS; ++i4)
+                {
+                    int val = (((((i1
+                                   * NITEMS) + i2)
+                                 * NITEMS) + i3)
+                               * NITEMS) + i4;
+                    std::string str = QUtil::int_to_string(10 * val, 6);
+                    items.appendItem(
+                        QPDFObjectHandle::newString(str));
+                    items.appendItem(
+                        QPDFObjectHandle::newString("val " + str));
+                    if (i4 == 0)
+                    {
+                        first = str;
+                    }
+                    else if (i4 == NITEMS - 1)
+                    {
+                        last = str;
+                    }
+                }
+                auto limits = QPDFObjectHandle::newArray();
+                n3.replaceKey("/Limits", limits);
+                limits.appendItem(QPDFObjectHandle::newString(first));
+                limits.appendItem(QPDFObjectHandle::newString(last));
+            }
+            auto limits = QPDFObjectHandle::newArray();
+            n2.replaceKey("/Limits", limits);
+            limits.appendItem(k2.getArrayItem(0)
+                              .getKey("/Limits")
+                              .getArrayItem(0));
+            limits.appendItem(k2.getArrayItem(NITEMS - 1)
+                              .getKey("/Limits")
+                              .getArrayItem(1));
+        }
+        auto limits = QPDFObjectHandle::newArray();
+        n1.replaceKey("/Limits", limits);
+        limits.appendItem(k1.getArrayItem(0)
+                          .getKey("/Limits")
+                          .getArrayItem(0));
+        limits.appendItem(k1.getArrayItem(NITEMS - 1)
+                          .getKey("/Limits")
+                          .getArrayItem(1));
     }
+
+    QPDFNameTreeObjectHelper nh(n0);
+    std::cout << "--- forward ---" << std::endl;
+    for (auto i: nh)
+    {
+        std::cout << i.first << " -> "
+                  << i.second.unparse() << std::endl;
+    }
+    std::cout << "--- backward ---" << std::endl;
+    for (auto i = nh.last(); i.valid(); --i)
+    {
+        std::cout << (*i).first << " -> "
+                  << (*i).second.unparse() << std::endl;
+    }
+
+    // Find
+    check_find(nh, "000300", false);
+    check_find(nh, "000305", true);
+    check_find(nh, "000305", false);
+    check_find(nh, "00000", false);
+    check_find(nh, "00000", true);
+    check_find(nh, "000800", false);
+    check_find(nh, "000805", false);
+    check_find(nh, "000805", true);
+}
+
+int main()
+{
+    test_bsearch();
+    test_depth();
+
+    return 0;
 }
+
diff --git a/libtests/qtest/nntree.test b/libtests/qtest/nntree.test
index 647ab24f..a1dcb957 100644
--- a/libtests/qtest/nntree.test
+++ b/libtests/qtest/nntree.test
@@ -3,14 +3,15 @@ require 5.008;
 use warnings;
 use strict;
 
+chdir("nntree") or die "chdir testdir failed: $!\n";
+
 require TestDriver;
 
 my $td = new TestDriver('nntree');
 
 $td->runtest("nntree",
 	     {$td->COMMAND => "nntree"},
-	     {$td->STRING => "all tests passed\n",
-	      $td->EXIT_STATUS => 0},
+	     {$td->FILE => "nntree.out", $td->EXIT_STATUS => 0},
 	     $td->NORMALIZE_NEWLINES);
 
 $td->report(1);
diff --git a/libtests/qtest/nntree/nntree.out b/libtests/qtest/nntree/nntree.out
new file mode 100644
index 00000000..b5212ba7
--- /dev/null
+++ b/libtests/qtest/nntree/nntree.out
@@ -0,0 +1,173 @@
+bsearch tests passed
+--- forward ---
+000000 -> (val 000000)
+000010 -> (val 000010)
+000020 -> (val 000020)
+000030 -> (val 000030)
+000040 -> (val 000040)
+000050 -> (val 000050)
+000060 -> (val 000060)
+000070 -> (val 000070)
+000080 -> (val 000080)
+000090 -> (val 000090)
+000100 -> (val 000100)
+000110 -> (val 000110)
+000120 -> (val 000120)
+000130 -> (val 000130)
+000140 -> (val 000140)
+000150 -> (val 000150)
+000160 -> (val 000160)
+000170 -> (val 000170)
+000180 -> (val 000180)
+000190 -> (val 000190)
+000200 -> (val 000200)
+000210 -> (val 000210)
+000220 -> (val 000220)
+000230 -> (val 000230)
+000240 -> (val 000240)
+000250 -> (val 000250)
+000260 -> (val 000260)
+000270 -> (val 000270)
+000280 -> (val 000280)
+000290 -> (val 000290)
+000300 -> (val 000300)
+000310 -> (val 000310)
+000320 -> (val 000320)
+000330 -> (val 000330)
+000340 -> (val 000340)
+000350 -> (val 000350)
+000360 -> (val 000360)
+000370 -> (val 000370)
+000380 -> (val 000380)
+000390 -> (val 000390)
+000400 -> (val 000400)
+000410 -> (val 000410)
+000420 -> (val 000420)
+000430 -> (val 000430)
+000440 -> (val 000440)
+000450 -> (val 000450)
+000460 -> (val 000460)
+000470 -> (val 000470)
+000480 -> (val 000480)
+000490 -> (val 000490)
+000500 -> (val 000500)
+000510 -> (val 000510)
+000520 -> (val 000520)
+000530 -> (val 000530)
+000540 -> (val 000540)
+000550 -> (val 000550)
+000560 -> (val 000560)
+000570 -> (val 000570)
+000580 -> (val 000580)
+000590 -> (val 000590)
+000600 -> (val 000600)
+000610 -> (val 000610)
+000620 -> (val 000620)
+000630 -> (val 000630)
+000640 -> (val 000640)
+000650 -> (val 000650)
+000660 -> (val 000660)
+000670 -> (val 000670)
+000680 -> (val 000680)
+000690 -> (val 000690)
+000700 -> (val 000700)
+000710 -> (val 000710)
+000720 -> (val 000720)
+000730 -> (val 000730)
+000740 -> (val 000740)
+000750 -> (val 000750)
+000760 -> (val 000760)
+000770 -> (val 000770)
+000780 -> (val 000780)
+000790 -> (val 000790)
+000800 -> (val 000800)
+--- backward ---
+000800 -> (val 000800)
+000790 -> (val 000790)
+000780 -> (val 000780)
+000770 -> (val 000770)
+000760 -> (val 000760)
+000750 -> (val 000750)
+000740 -> (val 000740)
+000730 -> (val 000730)
+000720 -> (val 000720)
+000710 -> (val 000710)
+000700 -> (val 000700)
+000690 -> (val 000690)
+000680 -> (val 000680)
+000670 -> (val 000670)
+000660 -> (val 000660)
+000650 -> (val 000650)
+000640 -> (val 000640)
+000630 -> (val 000630)
+000620 -> (val 000620)
+000610 -> (val 000610)
+000600 -> (val 000600)
+000590 -> (val 000590)
+000580 -> (val 000580)
+000570 -> (val 000570)
+000560 -> (val 000560)
+000550 -> (val 000550)
+000540 -> (val 000540)
+000530 -> (val 000530)
+000520 -> (val 000520)
+000510 -> (val 000510)
+000500 -> (val 000500)
+000490 -> (val 000490)
+000480 -> (val 000480)
+000470 -> (val 000470)
+000460 -> (val 000460)
+000450 -> (val 000450)
+000440 -> (val 000440)
+000430 -> (val 000430)
+000420 -> (val 000420)
+000410 -> (val 000410)
+000400 -> (val 000400)
+000390 -> (val 000390)
+000380 -> (val 000380)
+000370 -> (val 000370)
+000360 -> (val 000360)
+000350 -> (val 000350)
+000340 -> (val 000340)
+000330 -> (val 000330)
+000320 -> (val 000320)
+000310 -> (val 000310)
+000300 -> (val 000300)
+000290 -> (val 000290)
+000280 -> (val 000280)
+000270 -> (val 000270)
+000260 -> (val 000260)
+000250 -> (val 000250)
+000240 -> (val 000240)
+000230 -> (val 000230)
+000220 -> (val 000220)
+000210 -> (val 000210)
+000200 -> (val 000200)
+000190 -> (val 000190)
+000180 -> (val 000180)
+000170 -> (val 000170)
+000160 -> (val 000160)
+000150 -> (val 000150)
+000140 -> (val 000140)
+000130 -> (val 000130)
+000120 -> (val 000120)
+000110 -> (val 000110)
+000100 -> (val 000100)
+000090 -> (val 000090)
+000080 -> (val 000080)
+000070 -> (val 000070)
+000060 -> (val 000060)
+000050 -> (val 000050)
+000040 -> (val 000040)
+000030 -> (val 000030)
+000020 -> (val 000020)
+000010 -> (val 000010)
+000000 -> (val 000000)
+find 000300 (0): 000300 -> (val 000300)
+find 000305 (1): 000300 -> (val 000300)
+find 000305 (0): not found
+find 00000 (0): not found
+find 00000 (1): not found
+find 000800 (0): 000800 -> (val 000800)
+find 000805 (0): not found
+find 000805 (1): 000800 -> (val 000800)