1 // Copyright 2016 The PDFium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7 #ifndef CORE_FPDFDOC_CPDF_NUMBERTREE_H_ 8 #define CORE_FPDFDOC_CPDF_NUMBERTREE_H_ 9 10 #include <optional> 11 12 #include "core/fxcrt/retain_ptr.h" 13 14 class CPDF_Dictionary; 15 class CPDF_Object; 16 17 // Represents a number tree that allows for sub-linear lookups of tree nodes. 18 // See ISO 32000-1:2008 spec, section 7.9.7. 19 class CPDF_NumberTree { 20 public: 21 struct KeyValue { 22 KeyValue(int key, RetainPtr<const CPDF_Object> value); 23 KeyValue(const KeyValue&) = delete; 24 KeyValue& operator=(const KeyValue&) = delete; 25 KeyValue(KeyValue&&) noexcept; 26 KeyValue& operator=(KeyValue&&) noexcept; 27 ~KeyValue(); 28 29 int key; 30 RetainPtr<const CPDF_Object> value; 31 }; 32 33 explicit CPDF_NumberTree(RetainPtr<const CPDF_Dictionary> root); 34 ~CPDF_NumberTree(); 35 36 // Finds the object in the number tree whose key is `num`. Returns nullptr in 37 // there is no `num` key in the tree. 38 RetainPtr<const CPDF_Object> LookupValue(int num) const; 39 40 // Finds the object in the number tree with the largest key, such that 41 // `num` >= key. Returns the key/value pair if such a key exists, or 42 // std::nullopt otherwise. 43 // Note that this is similar to, but not exactly the same as 44 // std::lower_bound(). 45 std::optional<KeyValue> GetLowerBound(int num) const; 46 47 protected: 48 RetainPtr<const CPDF_Dictionary> const root_; 49 }; 50 51 #endif // CORE_FPDFDOC_CPDF_NUMBERTREE_H_ 52