blob: 0423d0f5e650baa8324d7dfe86bcf0572ff9467b [file] [log] [blame] [edit]
// Copyright 2016 The PDFium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
#ifndef CORE_FPDFDOC_CPDF_NUMBERTREE_H_
#define CORE_FPDFDOC_CPDF_NUMBERTREE_H_
#include <optional>
#include "core/fxcrt/retain_ptr.h"
class CPDF_Dictionary;
class CPDF_Object;
// Represents a number tree that allows for sub-linear lookups of tree nodes.
// See ISO 32000-1:2008 spec, section 7.9.7.
class CPDF_NumberTree {
public:
struct KeyValue {
KeyValue(int key, RetainPtr<const CPDF_Object> value);
KeyValue(const KeyValue&) = delete;
KeyValue& operator=(const KeyValue&) = delete;
KeyValue(KeyValue&&) noexcept;
KeyValue& operator=(KeyValue&&) noexcept;
~KeyValue();
int key;
RetainPtr<const CPDF_Object> value;
};
explicit CPDF_NumberTree(RetainPtr<const CPDF_Dictionary> root);
~CPDF_NumberTree();
// Finds the object in the number tree whose key is `num`. Returns nullptr in
// there is no `num` key in the tree.
RetainPtr<const CPDF_Object> LookupValue(int num) const;
// Finds the object in the number tree with the largest key, such that
// `num` >= key. Returns the key/value pair if such a key exists, or
// std::nullopt otherwise.
// Note that this is similar to, but not exactly the same as
// std::lower_bound().
std::optional<KeyValue> GetLowerBound(int num) const;
protected:
RetainPtr<const CPDF_Dictionary> const root_;
};
#endif // CORE_FPDFDOC_CPDF_NUMBERTREE_H_