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_IMPL_H_ 18 #define CHRE_UTIL_HEAP_IMPL_H_ 19 20 #include <utility> 21 22 #include "chre/platform/assert.h" 23 #include "chre/util/dynamic_vector.h" 24 #include "chre/util/fixed_size_vector.h" 25 26 namespace chre { 27 28 namespace { 29 30 template<typename ContainerType, typename CompareFunction> 31 void siftUp(ContainerType& container, size_t index, 32 const CompareFunction& compare) { 33 CHRE_ASSERT(index < container.size()); 34 size_t current = index; 35 while (current > 0) { 36 size_t parent = (current - 1) / 2; 37 if (compare(container[parent], container[current])) { 38 container.swap(parent, current); 39 current = parent; 40 } else { 41 break; 42 } 43 } 44 } 45 46 template<typename ContainerType, typename CompareFunction> 47 void siftDown(ContainerType& container, size_t index, 48 const CompareFunction& compare) { 49 CHRE_ASSERT(index < container.size()); 50 size_t current = index; 51 52 // The last element is to be removed. If that's the element being indexed, 53 // it's a no-op. 54 while (index < container.size() - 1) { 55 size_t child = 2 * current + 1; // left child 56 57 // If there are two children, pick the dominant one. 58 if (child + 1 < container.size() - 1 && 59 compare(container[child], container[child + 1])) { 60 child++; 61 } 62 63 // If the current element is not childless and the dominant child dominates 64 // over it, swap and continue. 65 if (child < container.size() - 1 && 66 compare(container[current], container[child])) { 67 container.swap(current, child); 68 current = child; 69 } else { 70 break; 71 } 72 } 73 } 74 75 } // namespace 76 77 template<typename ContainerType, typename CompareFunction> 78 void push_heap(ContainerType& container, const CompareFunction& compare) { 79 CHRE_ASSERT(container.size() > 0); 80 if (container.size() > 0) { 81 siftUp(container, container.size() - 1, compare); 82 } 83 } 84 85 template<typename ContainerType, typename CompareFunction> 86 void pop_heap(ContainerType& container, const CompareFunction& compare) { 87 CHRE_ASSERT(container.size() > 0); 88 if (container.size() > 0) { 89 container.swap(0, container.size() - 1); 90 siftDown(container, 0, compare); 91 } 92 } 93 94 template<typename ContainerType, typename CompareFunction> 95 void remove_heap(ContainerType& container, size_t index, 96 const CompareFunction& compare) { 97 CHRE_ASSERT(index < container.size()); 98 container.swap(index, container.size() - 1); 99 100 size_t parent = (index - 1) / 2; 101 // When index = 0, it has no parent and can only sift down. 102 if (index > 0 && compare(container[parent], container[index])) { 103 siftUp(container, index, compare); 104 } else { 105 siftDown(container, index, compare); 106 } 107 } 108 109 } // namespace chre 110 111 #endif // CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_ 112
