NNTree.hh
3.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#ifndef NNTREE_HH
#define NNTREE_HH
#include <qpdf/QPDF.hh>
#include <qpdf/QPDFObjectHandle.hh>
#include <iterator>
#include <list>
#include <memory>
class NNTreeDetails
{
public:
virtual std::string const& itemsKey() const = 0;
virtual bool keyValid(QPDFObjectHandle) const = 0;
virtual int compareKeys(QPDFObjectHandle, QPDFObjectHandle) const = 0;
};
class NNTreeImpl;
class NNTreeIterator
{
friend class NNTreeImpl;
public:
typedef std::pair<QPDFObjectHandle, QPDFObjectHandle> T;
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = long;
using pointer = T*;
using reference = T&;
virtual ~NNTreeIterator() = default;
bool valid() const;
NNTreeIterator& operator++();
NNTreeIterator
operator++(int)
{
NNTreeIterator t = *this;
++(*this);
return t;
}
NNTreeIterator& operator--();
NNTreeIterator
operator--(int)
{
NNTreeIterator t = *this;
--(*this);
return t;
}
reference operator*();
pointer operator->();
bool operator==(NNTreeIterator const& other) const;
bool
operator!=(NNTreeIterator const& other) const
{
return !operator==(other);
}
void insertAfter(QPDFObjectHandle key, QPDFObjectHandle value);
void remove();
private:
class PathElement
{
public:
PathElement(QPDFObjectHandle const& node, int kid_number);
QPDFObjectHandle node;
int kid_number;
};
NNTreeIterator(NNTreeImpl& impl);
void updateIValue(bool allow_invalid = true);
bool deepen(QPDFObjectHandle node, bool first, bool allow_empty);
void setItemNumber(QPDFObjectHandle const& node, int);
void addPathElement(QPDFObjectHandle const& node, int kid_number);
QPDFObjectHandle getNextKid(PathElement& element, bool backward);
void increment(bool backward);
void resetLimits(QPDFObjectHandle node, std::list<PathElement>::iterator parent);
void split(QPDFObjectHandle to_split, std::list<PathElement>::iterator parent);
std::list<PathElement>::iterator lastPathElement();
NNTreeImpl& impl;
std::list<PathElement> path;
QPDFObjectHandle node;
int item_number{-1};
value_type ivalue;
};
class NNTreeImpl
{
friend class NNTreeIterator;
public:
typedef NNTreeIterator iterator;
NNTreeImpl(NNTreeDetails const&, QPDF&, QPDFObjectHandle&, bool auto_repair = true);
iterator begin();
iterator end();
iterator last();
iterator find(QPDFObjectHandle key, bool return_prev_if_not_found = false);
iterator insertFirst(QPDFObjectHandle key, QPDFObjectHandle value);
iterator insert(QPDFObjectHandle key, QPDFObjectHandle value);
bool remove(QPDFObjectHandle key, QPDFObjectHandle* value = nullptr);
// Change the split threshold for easier testing. There's no real reason to expose this to
// downstream tree helpers, but it has to be public so we can call it from the test suite.
void setSplitThreshold(int split_threshold);
private:
void repair();
iterator findInternal(QPDFObjectHandle key, bool return_prev_if_not_found = false);
int withinLimits(QPDFObjectHandle key, QPDFObjectHandle node);
int binarySearch(
QPDFObjectHandle key,
QPDFObjectHandle items,
int num_items,
bool return_prev_if_not_found,
int (NNTreeImpl::*compare)(QPDFObjectHandle& key, QPDFObjectHandle& arr, int item));
int compareKeyItem(QPDFObjectHandle& key, QPDFObjectHandle& items, int idx);
int compareKeyKid(QPDFObjectHandle& key, QPDFObjectHandle& items, int idx);
void warn(QPDFObjectHandle& node, std::string const& msg);
void error(QPDFObjectHandle& node, std::string const& msg);
NNTreeDetails const& details;
QPDF& qpdf;
int split_threshold{32};
QPDFObjectHandle oh;
bool auto_repair{true};
size_t error_count{0};
};
#endif // NNTREE_HH