Add iterators to name/number tree helpers

10 files changed, 628 insertions, 45 deletions

diff --git a/include/qpdf/QPDFNameTreeObjectHelper.hh b/include/qpdf/QPDFNameTreeObjectHelper.hh
index 255ff24e..f94d34cf 100644
--- a/include/qpdf/QPDFNameTreeObjectHelper.hh
+++ b/include/qpdf/QPDFNameTreeObjectHelper.hh
@@ -26,6 +26,7 @@
 #include <qpdf/QPDFObjGen.hh>
 #include <map>
 #include <memory>
+#include <iterator>
 
 #include <qpdf/DLL.h>
 
@@ -35,6 +36,8 @@
 // normalized for lookup purposes.
 
 class NNTreeImpl;
+class NNTreeIterator;
+class NNTreeDetails;
 
 class QPDFNameTreeObjectHelper: public QPDFObjectHelper
 {
@@ -54,6 +57,66 @@ class QPDFNameTreeObjectHelper: public QPDFObjectHelper
     QPDF_DLL
     bool findObject(std::string const& utf8, QPDFObjectHandle& oh);
 
+    class iterator: public std::iterator<
+        std::bidirectional_iterator_tag,
+        std::pair<std::string, QPDFObjectHandle>,
+        void,
+        std::pair<std::string, QPDFObjectHandle>*,
+        std::pair<std::string, QPDFObjectHandle>>
+    {
+        friend class QPDFNameTreeObjectHelper;
+      public:
+        QPDF_DLL
+        bool valid() const;
+        QPDF_DLL
+        iterator& operator++();
+        QPDF_DLL
+        iterator operator++(int)
+        {
+            iterator t = *this;
+            ++(*this);
+            return t;
+        }
+        QPDF_DLL
+        iterator& operator--();
+        QPDF_DLL
+        iterator operator--(int)
+        {
+            iterator t = *this;
+            --(*this);
+            return t;
+        }
+        QPDF_DLL
+        reference operator*();
+        QPDF_DLL
+        bool operator==(iterator const& other) const;
+        QPDF_DLL
+        bool operator!=(iterator const& other) const
+        {
+            return ! operator==(other);
+        }
+
+      private:
+        iterator(std::shared_ptr<NNTreeIterator> const&);
+        std::shared_ptr<NNTreeIterator> impl;
+    };
+
+    // The iterator looks like map iterator, so i.first is a string
+    // and i.second is a QPDFObjectHandle.
+    QPDF_DLL
+    iterator begin() const;
+    QPDF_DLL
+    iterator end() const;
+    // Return a bidirectional iterator that points to the last item.
+    QPDF_DLL
+    iterator last() const;
+
+    // Find the entry with the given key. If return_prev_if_not_found
+    // is true and the item is not found, return the next lower item.
+    QPDF_DLL
+    iterator find(std::string const& key,
+                  bool return_prev_if_not_found = false);
+
     // Return the contents of the name tree as a map. Note that name
     // trees may be very large, so this may use a lot of RAM. It is
     // more efficient to use QPDFNameTreeObjectHelper's iterator.
diff --git a/include/qpdf/QPDFNumberTreeObjectHelper.hh b/include/qpdf/QPDFNumberTreeObjectHelper.hh
index 7fb9195c..393e8dba 100644
--- a/include/qpdf/QPDFNumberTreeObjectHelper.hh
+++ b/include/qpdf/QPDFNumberTreeObjectHelper.hh
@@ -33,6 +33,8 @@
 // PDF spec (ISO 32000) for a description of number trees.
 
 class NNTreeImpl;
+class NNTreeIterator;
+class NNTreeDetails;
 
 class QPDFNumberTreeObjectHelper: public QPDFObjectHelper
 {
@@ -73,6 +75,65 @@ class QPDFNumberTreeObjectHelper: public QPDFObjectHelper
     bool findObjectAtOrBelow(numtree_number idx, QPDFObjectHandle& oh,
                              numtree_number& offset);
 
+    class iterator: public std::iterator<
+        std::bidirectional_iterator_tag,
+        std::pair<numtree_number, QPDFObjectHandle>,
+        void,
+        std::pair<numtree_number, QPDFObjectHandle>*,
+        std::pair<numtree_number, QPDFObjectHandle>>
+    {
+        friend class QPDFNumberTreeObjectHelper;
+      public:
+        QPDF_DLL
+        bool valid() const;
+        QPDF_DLL
+        iterator& operator++();
+        QPDF_DLL
+        iterator operator++(int)
+        {
+            iterator t = *this;
+            ++(*this);
+            return t;
+        }
+        QPDF_DLL
+        iterator& operator--();
+        QPDF_DLL
+        iterator operator--(int)
+        {
+            iterator t = *this;
+            --(*this);
+            return t;
+        }
+        QPDF_DLL
+        reference operator*();
+        QPDF_DLL
+        bool operator==(iterator const& other) const;
+        QPDF_DLL
+        bool operator!=(iterator const& other) const
+        {
+            return ! operator==(other);
+        }
+
+      private:
+        iterator(std::shared_ptr<NNTreeIterator> const&);
+        std::shared_ptr<NNTreeIterator> impl;
+    };
+
+    // The iterator looks like map iterator, so i.first is a string
+    // and i.second is a QPDFObjectHandle.
+    QPDF_DLL
+    iterator begin() const;
+    QPDF_DLL
+    iterator end() const;
+    // Return a bidirectional iterator that points to the last item.
+    QPDF_DLL
+    iterator last() const;
+
+    // Find the entry with the given key. If return_prev_if_not_found
+    // is true and the item is not found, return the next lower item.
+    QPDF_DLL
+    iterator find(numtree_number key, bool return_prev_if_not_found = false);
+
     // Return the contents of the number tree as a map. Note that
     // number trees may be very large, so this may use a lot of RAM.
     // It is more efficient to use QPDFNumberTreeObjectHelper's
diff --git a/libqpdf/QPDFNameTreeObjectHelper.cc b/libqpdf/QPDFNameTreeObjectHelper.cc
index 07a8ad02..f7576e94 100644
--- a/libqpdf/QPDFNameTreeObjectHelper.cc
+++ b/libqpdf/QPDFNameTreeObjectHelper.cc
@@ -48,19 +48,85 @@ QPDFNameTreeObjectHelper::~QPDFNameTreeObjectHelper()
 {
 }
 
+QPDFNameTreeObjectHelper::iterator::iterator(
+    std::shared_ptr<NNTreeIterator> const& i) :
+    impl(i)
+{
+}
+
+bool
+QPDFNameTreeObjectHelper::iterator::valid() const
+{
+    return impl->valid();
+}
+
+QPDFNameTreeObjectHelper::iterator&
+QPDFNameTreeObjectHelper::iterator::operator++()
+{
+    ++(*impl);
+    return *this;
+}
+
+QPDFNameTreeObjectHelper::iterator&
+QPDFNameTreeObjectHelper::iterator::operator--()
+{
+    --(*impl);
+    return *this;
+}
+
+QPDFNameTreeObjectHelper::iterator::reference
+QPDFNameTreeObjectHelper::iterator::operator*()
+{
+    auto p = **impl;
+    return std::make_pair(p.first.getUTF8Value(), p.second);
+}
+
+bool
+QPDFNameTreeObjectHelper::iterator::operator==(iterator const& other) const
+{
+    return *(impl) == *(other.impl);
+}
+
+QPDFNameTreeObjectHelper::iterator
+QPDFNameTreeObjectHelper::begin() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->begin()));
+}
+
+QPDFNameTreeObjectHelper::iterator
+QPDFNameTreeObjectHelper::end() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->end()));
+}
+
+QPDFNameTreeObjectHelper::iterator
+QPDFNameTreeObjectHelper::last() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->last()));
+}
+
+QPDFNameTreeObjectHelper::iterator
+QPDFNameTreeObjectHelper::find(std::string const& key,
+                               bool return_prev_if_not_found)
+{
+    auto i = this->m->impl->find(QPDFObjectHandle::newUnicodeString(key),
+                                 return_prev_if_not_found);
+    return iterator(std::make_shared<NNTreeIterator>(i));
+}
+
 bool
 QPDFNameTreeObjectHelper::hasName(std::string const& name)
 {
-    auto i = this->m->impl->find(QPDFObjectHandle::newUnicodeString(name));
-    return (i != this->m->impl->end());
+    auto i = find(name);
+    return (i != end());
 }
 
 bool
 QPDFNameTreeObjectHelper::findObject(
     std::string const& name, QPDFObjectHandle& oh)
 {
-    auto i = this->m->impl->find(QPDFObjectHandle::newUnicodeString(name));
-    if (i == this->m->impl->end())
+    auto i = find(name);
+    if (i == end())
     {
         return false;
     }
@@ -72,11 +138,6 @@ std::map<std::string, QPDFObjectHandle>
 QPDFNameTreeObjectHelper::getAsMap() const
 {
     std::map<std::string, QPDFObjectHandle> result;
-    for (auto i: *(this->m->impl))
-    {
-        result.insert(
-            std::make_pair(i.first.getUTF8Value(),
-                           i.second));
-    }
+    result.insert(begin(), end());
     return result;
 }
diff --git a/libqpdf/QPDFNumberTreeObjectHelper.cc b/libqpdf/QPDFNumberTreeObjectHelper.cc
index fa9a0c71..6371287f 100644
--- a/libqpdf/QPDFNumberTreeObjectHelper.cc
+++ b/libqpdf/QPDFNumberTreeObjectHelper.cc
@@ -44,41 +44,107 @@ QPDFNumberTreeObjectHelper::QPDFNumberTreeObjectHelper(QPDFObjectHandle oh) :
 {
 }
 
+QPDFNumberTreeObjectHelper::iterator::iterator(
+    std::shared_ptr<NNTreeIterator> const& i) :
+    impl(i)
+{
+}
+
+bool
+QPDFNumberTreeObjectHelper::iterator::valid() const
+{
+    return impl->valid();
+}
+
+QPDFNumberTreeObjectHelper::iterator&
+QPDFNumberTreeObjectHelper::iterator::operator++()
+{
+    ++(*impl);
+    return *this;
+}
+
+QPDFNumberTreeObjectHelper::iterator&
+QPDFNumberTreeObjectHelper::iterator::operator--()
+{
+    --(*impl);
+    return *this;
+}
+
+QPDFNumberTreeObjectHelper::iterator::reference
+QPDFNumberTreeObjectHelper::iterator::operator*()
+{
+    auto p = **impl;
+    return std::make_pair(p.first.getIntValue(), p.second);
+}
+
+bool
+QPDFNumberTreeObjectHelper::iterator::operator==(iterator const& other) const
+{
+    return *(impl) == *(other.impl);
+}
+
+QPDFNumberTreeObjectHelper::iterator
+QPDFNumberTreeObjectHelper::begin() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->begin()));
+}
+
+QPDFNumberTreeObjectHelper::iterator
+QPDFNumberTreeObjectHelper::end() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->end()));
+}
+
+QPDFNumberTreeObjectHelper::iterator
+QPDFNumberTreeObjectHelper::last() const
+{
+    return iterator(std::make_shared<NNTreeIterator>(this->m->impl->last()));
+}
+
+QPDFNumberTreeObjectHelper::iterator
+QPDFNumberTreeObjectHelper::find(numtree_number key,
+                                 bool return_prev_if_not_found)
+{
+    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(key),
+                                 return_prev_if_not_found);
+    return iterator(std::make_shared<NNTreeIterator>(i));
+}
+
 QPDFNumberTreeObjectHelper::numtree_number
 QPDFNumberTreeObjectHelper::getMin()
 {
-    auto i = this->m->impl->begin();
-    if (i == this->m->impl->end())
+    auto i = begin();
+    if (i == end())
     {
         return 0;
     }
-    return (*i).first.getIntValue();
+    return (*i).first;
 }
 
 QPDFNumberTreeObjectHelper::numtree_number
 QPDFNumberTreeObjectHelper::getMax()
 {
-    auto i = this->m->impl->last();
-    if (i == this->m->impl->end())
+    auto i = last();
+    if (i == end())
     {
         return 0;
     }
-    return (*i).first.getIntValue();
+    return (*i).first;
 }
 
 bool
 QPDFNumberTreeObjectHelper::hasIndex(numtree_number idx)
 {
-    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx));
-    return (i != this->m->impl->end());
+    auto i = find(idx);
+    return (i != this->end());
 }
 
 bool
 QPDFNumberTreeObjectHelper::findObject(
     numtree_number idx, QPDFObjectHandle& oh)
 {
-    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx));
-    if (i == this->m->impl->end())
+    auto i = find(idx);
+    if (i == end())
     {
         return false;
     }
@@ -91,13 +157,13 @@ QPDFNumberTreeObjectHelper::findObjectAtOrBelow(
     numtree_number idx, QPDFObjectHandle& oh,
     numtree_number& offset)
 {
-    auto i = this->m->impl->find(QPDFObjectHandle::newInteger(idx), true);
-    if (i == this->m->impl->end())
+    auto i = find(idx, true);
+    if (i == end())
     {
         return false;
     }
     oh = (*i).second;
-    offset = idx - (*i).first.getIntValue();
+    offset = idx - (*i).first;
     return true;
 }
 
@@ -105,11 +171,6 @@ std::map<QPDFNumberTreeObjectHelper::numtree_number, QPDFObjectHandle>
 QPDFNumberTreeObjectHelper::getAsMap() const
 {
     std::map<numtree_number, QPDFObjectHandle> result;
-    for (auto i: *(this->m->impl))
-    {
-        result.insert(
-            std::make_pair(i.first.getIntValue(),
-                           i.second));
-    }
+    result.insert(begin(), end());
     return result;
 }
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)
diff --git a/qpdf/qtest/qpdf/name-tree.out b/qpdf/qtest/qpdf/name-tree.out
index c50e8806..46855b71 100644
--- a/qpdf/qtest/qpdf/name-tree.out
+++ b/qpdf/qtest/qpdf/name-tree.out
@@ -7,4 +7,13 @@
 20 twenty -> twenty.
 22 twenty-two -> twenty-two!
 29 twenty-nine -> twenty-nine!
+01 one -> one!
+06 σιχ -> six!
+07 sev•n -> seven!
+11 elephant -> elephant?
+12 twelve -> twelve!
+15 fifteen -> fifteen!
+20 twenty -> twenty.
+22 twenty-two -> twenty-two!
+29 twenty-nine -> twenty-nine!
 test 48 done
diff --git a/qpdf/qtest/qpdf/number-tree.out b/qpdf/qtest/qpdf/number-tree.out
index b4b16535..cc07526d 100644
--- a/qpdf/qtest/qpdf/number-tree.out
+++ b/qpdf/qtest/qpdf/number-tree.out
@@ -12,4 +12,18 @@
 22 twenty-two
 23 twenty-three
 29 twenty-nine
+1 one
+2 two
+3 three
+5 five
+6 six
+9 nine
+11 elephant
+12 twelve
+15 fifteen
+19 nineteen
+20 twenty
+22 twenty-two
+23 twenty-three
+29 twenty-nine
 test 46 done
diff --git a/qpdf/test_driver.cc b/qpdf/test_driver.cc
index 1be7fbaf..0a55f3ce 100644
--- a/qpdf/test_driver.cc
+++ b/qpdf/test_driver.cc
@@ -1749,13 +1749,17 @@ void runtest(int n, char const* filename1, char const* arg2)
         // number-tree.pdf
         QPDFObjectHandle qtest = pdf.getTrailer().getKey("/QTest");
         QPDFNumberTreeObjectHelper ntoh(qtest);
+        for (auto iter: ntoh)
+        {
+            std::cout << iter.first << " "
+                      << iter.second.getStringValue()
+                      << std::endl;
+        }
         QPDFNumberTreeObjectHelper::idx_map ntoh_map = ntoh.getAsMap();
-        for (QPDFNumberTreeObjectHelper::idx_map::iterator iter =
-                 ntoh_map.begin();
-             iter != ntoh_map.end(); ++iter)
+        for (auto& iter: ntoh_map)
         {
-            std::cout << (*iter).first << " "
-                      << (*iter).second.getStringValue()
+            std::cout << iter.first << " "
+                      << iter.second.getStringValue()
                       << std::endl;
         }
         assert(1 == ntoh.getMin());
@@ -1793,13 +1797,17 @@ void runtest(int n, char const* filename1, char const* arg2)
         // name-tree.pdf
         QPDFObjectHandle qtest = pdf.getTrailer().getKey("/QTest");
         QPDFNameTreeObjectHelper ntoh(qtest);
+        for (auto iter: ntoh)
+        {
+            std::cout << iter.first << " -> "
+                      << iter.second.getStringValue()
+                      << std::endl;
+        }
         std::map<std::string, QPDFObjectHandle> ntoh_map = ntoh.getAsMap();
-        for (std::map<std::string, QPDFObjectHandle>::iterator iter =
-                 ntoh_map.begin();
-             iter != ntoh_map.end(); ++iter)
+        for (auto& iter: ntoh_map)
         {
-            std::cout << (*iter).first << " -> "
-                      << (*iter).second.getStringValue()
+            std::cout << iter.first << " -> "
+                      << iter.second.getStringValue()
                       << std::endl;
         }
         assert(ntoh.hasName("11 elephant"));
@@ -1809,6 +1817,9 @@ void runtest(int n, char const* filename1, char const* arg2)
         assert(! ntoh.findObject("potato", oh));
         assert(ntoh.findObject("07 sev\xe2\x80\xa2n", oh));
         assert("seven!" == oh.getStringValue());
+        auto last = ntoh.last();
+        assert((*last).first == "29 twenty-nine");
+        assert((*last).second.getUTF8Value() == "twenty-nine!");
     }
     else if (n == 49)
     {