1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef CHRE_UTIL_HEAP_H_ 18 #define CHRE_UTIL_HEAP_H_ 19 20 #include <cstddef> 21 22 namespace chre { 23 24 /** 25 * An implementation of the heap data structure. To be used as an input 26 * container, it must provide methods size(), swap() and operator[]. 27 * It is recommended to use FixedSizeVector or DynamicVector as the input 28 * container. 29 */ 30 31 /** 32 * Adds an element to the heap. The element must first be placed at the end 33 * of the container. 34 * 35 * @param container The container that is used to store the elements. 36 * @param compare The object that provides the custom ordering of the elements. 37 */ 38 template<typename ContainerType, typename CompareFunction> 39 void push_heap(ContainerType& container, const CompareFunction& compare); 40 41 /** 42 * Removes the first element from the heap and adjusts the heap accordingly. 43 * The element removed is temporarily placed at the end of the container. The 44 * user must call the proper method to remove it. 45 * 46 * @param container The container that is used to store the elements. 47 * @param compare The object that provides the custom ordering of the elements. 48 */ 49 template<typename ContainerType, typename CompareFunction> 50 void pop_heap(ContainerType& container, const CompareFunction& compare); 51 52 /** 53 * Removes an element from the heap and adjusts the heap accordingly. 54 * The element removed is temporarily placed at the end of the container. The 55 * user must call the proper method to remove it. It is illegal to index the 56 * element out of bounds. 57 * 58 * @param container The container that is used to store the elements. 59 * @param index The index of the element to be removed from the heap 60 * @param compare The object that provides the custom ordering of the elements. 61 */ 62 template<typename ContainerType, typename CompareFunction> 63 void remove_heap(ContainerType& container, size_t index, 64 const CompareFunction& compare); 65 66 } // namespace chre 67 68 #include "chre/util/heap_impl.h" 69 70 #endif // CHRE_UTIL_HEAP_H_ 71