Home | History | Annotate | Download | only in util 
      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_PRIORITY_QUEUE_IMPL_H_
     18 #define CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
     19 
     20 #include <utility>
     21 
     22 #include "chre/platform/assert.h"
     23 #include "chre/util/dynamic_vector.h"
     24 #include "chre/util/heap.h"
     25 
     26 namespace chre {
     27 
     28 template<typename ElementType, typename CompareFunction>
     29 PriorityQueue<ElementType, CompareFunction>::PriorityQueue() {}
     30 
     31 template<typename ElementType, typename CompareFunction>
     32 PriorityQueue<ElementType, CompareFunction>::PriorityQueue(
     33     const CompareFunction& compare)
     34     : mCompare(compare) {}
     35 
     36 template<typename ElementType, typename CompareFunction>
     37 size_t PriorityQueue<ElementType, CompareFunction>::size() const {
     38   return mData.size();
     39 }
     40 
     41 template<typename ElementType, typename CompareFunction>
     42 size_t PriorityQueue<ElementType, CompareFunction>::capacity() const {
     43   return mData.capacity();
     44 }
     45 
     46 template<typename ElementType, typename CompareFunction>
     47 bool PriorityQueue<ElementType, CompareFunction>::empty() const {
     48   return mData.empty();
     49 }
     50 
     51 template<typename ElementType, typename CompareFunction>
     52 bool PriorityQueue<ElementType, CompareFunction>::push(
     53     const ElementType& element) {
     54   bool success = mData.push_back(element);
     55   if (success) {
     56     push_heap(mData, mCompare);
     57   }
     58   return success;
     59 }
     60 
     61 template<typename ElementType, typename CompareFunction>
     62 template<typename... Args>
     63 bool PriorityQueue<ElementType, CompareFunction>::emplace(Args&&... args) {
     64   bool success = mData.emplace_back(args...);
     65   if (success) {
     66     push_heap(mData, mCompare);
     67   }
     68   return success;
     69 }
     70 
     71 template<typename ElementType, typename CompareFunction>
     72 ElementType& PriorityQueue<ElementType, CompareFunction>::operator[](
     73     size_t index) {
     74   return mData[index];
     75 }
     76 
     77 template<typename ElementType, typename CompareFunction>
     78 const ElementType& PriorityQueue<ElementType, CompareFunction>::operator[](
     79     size_t index) const {
     80   return mData[index];
     81 }
     82 
     83 template<typename ElementType, typename CompareFunction>
     84 ElementType& PriorityQueue<ElementType, CompareFunction>::top() {
     85   return mData[0];
     86 }
     87 
     88 template<typename ElementType, typename CompareFunction>
     89 const ElementType& PriorityQueue<ElementType, CompareFunction>::top() const {
     90   return mData[0];
     91 }
     92 
     93 template<typename ElementType, typename CompareFunction>
     94 void PriorityQueue<ElementType, CompareFunction>::pop() {
     95   if (mData.size() > 0) {
     96     pop_heap(mData, mCompare);
     97     mData.erase(mData.size() - 1);
     98   }
     99 }
    100 
    101 template<typename ElementType, typename CompareFunction>
    102 void PriorityQueue<ElementType, CompareFunction>::remove(size_t index) {
    103   CHRE_ASSERT(index < mData.size());
    104   if (index < mData.size()) {
    105     remove_heap(mData, index, mCompare);
    106     mData.erase(mData.size() - 1);
    107   }
    108 
    109   // TODO: consider resizing the dynamic array to mData.capacity()/2
    110   // when mData.size() <= mData.capacity()/4.
    111 }
    112 
    113 template<typename ElementType, typename CompareFunction>
    114 typename PriorityQueue<ElementType, CompareFunction>::iterator
    115     PriorityQueue<ElementType, CompareFunction>::begin() {
    116   return mData.begin();
    117 }
    118 
    119 template<typename ElementType, typename CompareFunction>
    120 typename PriorityQueue<ElementType, CompareFunction>::iterator
    121     PriorityQueue<ElementType, CompareFunction>::end() {
    122   return mData.end();
    123 }
    124 
    125 template<typename ElementType, typename CompareFunction>
    126 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
    127     PriorityQueue<ElementType, CompareFunction>::begin() const {
    128   return cbegin();
    129 }
    130 
    131 template<typename ElementType, typename CompareFunction>
    132 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
    133     PriorityQueue<ElementType, CompareFunction>::end() const {
    134   return cend();
    135 }
    136 
    137 template<typename ElementType, typename CompareFunction>
    138 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
    139     PriorityQueue<ElementType, CompareFunction>::cbegin() const {
    140   return mData.cbegin();
    141 }
    142 
    143 template<typename ElementType, typename CompareFunction>
    144 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
    145     PriorityQueue<ElementType, CompareFunction>::cend() const {
    146   return mData.cend();
    147 }
    148 
    149 }  // namespace chre
    150 
    151 #endif  // CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
    152