From 5f0708418a0a9cbacc033f52efc11c759120fd09 Mon Sep 17 00:00:00 2001 From: Jay Berkenbilt Date: Sat, 16 Jan 2021 12:11:17 -0500 Subject: Add iterators to name/number tree helpers --- libtests/nntree.cc | 137 ++++++++++++++++++++++++++++++- libtests/qtest/nntree.test | 5 +- libtests/qtest/nntree/nntree.out | 173 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 309 insertions(+), 6 deletions(-) create mode 100644 libtests/qtest/nntree/nntree.out (limited to 'libtests') 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 +#include #include #include #include +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) -- cgit v1.2.3-54-g00ecf