| // Copyright 2019 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef SRC_DEVELOPER_DEBUG_SHARED_LARGEST_LESS_OR_EQUAL_H_ |
| #define SRC_DEVELOPER_DEBUG_SHARED_LARGEST_LESS_OR_EQUAL_H_ |
| |
| #include <algorithm> |
| |
| namespace debug { |
| |
| // Returns an iterator pointing to the largest element in [first, last) less than or equal to the |
| // given |val|. As with std::lower_bound, the range [first, last) must be sorted according to |
| // the |less| comparator. |
| // |
| // If the query matches exactly a sequence of equal items, the first duplicate will be returned. If |
| // the query value matches a sequence of duplicates and does not exactly equal to them (it's |
| // returning the previous item), the last of the sequence will be returned. |
| // |
| // For example, if you had a sorted range of addresses and you want to know which one begins the |
| // range which an address falls into: |
| // |
| // std::vector<AddressRecord> ranges; |
| // int64_t address; |
| // |
| // auto found = LargestLessOrEqual( |
| // ranges.begin(), ranges.end(), address, |
| // [](const AddressRecord& record, uint64_t addr) { return record.addr < addr; }, |
| // [](const AddressRecord& record, uint64_t addr) { return record.addr == addr; }); |
| // |
| // For simple types, you can pass |std::less<T>()| and |std::equal_to<T>()| from <functional> for |
| // the comparators. |
| template <class BidirectionalIterator, class T, class CompareLess, class CompareEqual> |
| BidirectionalIterator LargestLessOrEqual(BidirectionalIterator first, BidirectionalIterator last, |
| const T& val, CompareLess less, CompareEqual equals) { |
| if (first == last) |
| return last; // Nothing to return. |
| |
| auto lower_bound = std::lower_bound(first, last, val, less); |
| |
| if (lower_bound != last && equals(*lower_bound, val)) |
| return lower_bound; // Got an exact match. |
| |
| // Otherwise, the result is the previous item in the range. |
| if (lower_bound == first) |
| return last; // No previous item, |val| is before the range. |
| return --lower_bound; |
| } |
| |
| } // namespace debug |
| |
| #endif // SRC_DEVELOPER_DEBUG_SHARED_LARGEST_LESS_OR_EQUAL_H_ |