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
22namespace 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 */
38template<typename ContainerType, typename CompareFunction>
39void 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 */
49template<typename ContainerType, typename CompareFunction>
50void 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 */
62template<typename ContainerType, typename CompareFunction>
63void 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