1 // Copyright 2018 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ASTC_CODEC_BASE_BOTTOM_N_H_ 16 #define ASTC_CODEC_BASE_BOTTOM_N_H_ 17 18 #include <algorithm> 19 #include <functional> 20 #include <vector> 21 22 namespace astc_codec { 23 namespace base { 24 25 // Used to aggregate the lowest N values of data supplied. 26 template<typename T, typename CompareFn = std::less<T>> 27 class BottomN { 28 public: 29 typedef std::vector<T> ContainerType; 30 31 // Creates an empty BottomN with limit |max_size|. BottomN(size_t max_size)32 BottomN(size_t max_size) : max_size_(max_size) { } 33 Empty()34 bool Empty() const { return data_.empty(); } Size()35 size_t Size() const { return data_.size(); } 36 Top()37 const T& Top() const { return data_.front(); } 38 Push(const T & value)39 void Push(const T& value) { 40 if (data_.size() < max_size_ || compare_(value, Top())) { 41 data_.push_back(value); 42 std::push_heap(data_.begin(), data_.end(), compare_); 43 44 if (Size() > max_size_) { 45 PopTop(); 46 } 47 } 48 } 49 Pop()50 std::vector<T> Pop() { 51 const size_t len = Size(); 52 std::vector<T> result(len); 53 54 for (size_t i = 0; i < len; ++i) { 55 result[len - i - 1] = PopTop(); 56 } 57 58 return result; 59 } 60 61 private: PopTop()62 T PopTop() { 63 std::pop_heap(data_.begin(), data_.end(), compare_); 64 T result = data_.back(); 65 data_.pop_back(); 66 return result; 67 } 68 69 ContainerType data_; 70 CompareFn compare_; 71 72 const size_t max_size_; 73 }; 74 75 } // namespace base 76 } // namespace astc_codec 77 78 #endif // ASTC_CODEC_BASE_BOTTOM_N_H_ 79