EstervQrCode 1.1.1
Library for qr code manipulation
heap.h
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  *
7  * THE BSD LICENSE
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *************************************************************************/
30 
31 #ifndef OPENCV_FLANN_HEAP_H_
32 #define OPENCV_FLANN_HEAP_H_
33 
35 
36 #include <algorithm>
37 #include <vector>
38 
39 #include <unordered_map>
40 
41 namespace cvflann
42 {
43 
44 // TODO: Define x > y operator and use std::greater<T> instead
45 template <typename T>
46 struct greater
47 {
48  bool operator()(const T& x, const T& y) const
49  {
50  return y < x;
51  }
52 };
53 
61 template <typename T>
62 class Heap
63 {
68  std::vector<T> heap;
69 public:
75  Heap(const int capacity)
76  {
77  reserve(capacity);
78  }
79 
85  Heap(std::vector<T>&& vec)
86  : heap(std::move(vec))
87  {
88  std::make_heap(heap.begin(), heap.end(), greater<T>());
89  }
90 
95  int size() const
96  {
97  return (int)heap.size();
98  }
99 
104  int capacity() const
105  {
106  return (int)heap.capacity();
107  }
108 
114  bool empty()
115  {
116  return heap.empty();
117  }
118 
122  void clear()
123  {
124  heap.clear();
125  }
126 
132  void reserve(const int capacity)
133  {
134  heap.reserve(capacity);
135  }
136 
145  void insert(T value)
146  {
147  /* If heap is full, then return without adding this element. */
148  if (size() == capacity()) {
149  return;
150  }
151 
152  heap.push_back(value);
153  std::push_heap(heap.begin(), heap.end(), greater<T>());
154  }
155 
162  bool popMin(T& value)
163  {
164  if (empty()) {
165  return false;
166  }
167 
168  value = heap[0];
169  std::pop_heap(heap.begin(), heap.end(), greater<T>());
170  heap.pop_back();
171 
172  return true; /* Return old last node. */
173  }
174 
187  template <typename HashableT>
188  static cv::Ptr<Heap<T>> getPooledInstance(
189  const HashableT& poolId, const int capacity, int iterThreshold = 0)
190  {
191  static cv::Mutex mutex;
192  const cv::AutoLock lock(mutex);
193 
194  struct HeapMapValueType {
195  cv::Ptr<Heap<T>> heapPtr;
196  int iterCounter;
197  };
199 
200  static HeapMapType heapsPool;
201  typename HeapMapType::iterator heapIt = heapsPool.find(poolId);
202 
203  if (heapIt == heapsPool.end())
204  {
205  // Construct the heap as it does not already exists
206  HeapMapValueType heapAndTimePair = {cv::makePtr<Heap<T>>(capacity), 0};
207  const std::pair<typename HeapMapType::iterator, bool>& emplaceResult = heapsPool.emplace(poolId, std::move(heapAndTimePair));
208  CV_CheckEQ(static_cast<int>(emplaceResult.second), 1, "Failed to insert the heap into its memory pool");
209  heapIt = emplaceResult.first;
210  }
211  else
212  {
213  CV_CheckEQ(heapIt->second.heapPtr.use_count(), 1, "Cannot modify a heap that is currently accessed by another caller");
214  heapIt->second.heapPtr->clear();
215  heapIt->second.heapPtr->reserve(capacity);
216  heapIt->second.iterCounter = 0;
217  }
218 
219  if (iterThreshold <= 1) {
220  iterThreshold = 2 * cv::getNumThreads();
221  }
222 
223  // Remove heaps that were not reused for more than given iterThreshold
224  typename HeapMapType::iterator cleanupIt = heapsPool.begin();
225  while (cleanupIt != heapsPool.end())
226  {
227  if (cleanupIt->second.iterCounter++ > iterThreshold)
228  {
229  CV_Assert(cleanupIt != heapIt);
230  cleanupIt = heapsPool.erase(cleanupIt);
231  continue;
232  }
233  ++cleanupIt;
234  }
235 
236  return heapIt->second.heapPtr;
237  }
238 };
239 
240 }
241 
243 
244 #endif //OPENCV_FLANN_HEAP_H_
T begin(T... args)
T capacity(T... args)
T clear(T... args)
T empty(T... args)
T end(T... args)
T find(T... args)
InputArrayOfArrays InputArrayOfArrays InputOutputArray InputOutputArray InputOutputArray InputOutputArray Size InputOutputArray InputOutputArray T
Definition: calib3d.hpp:1867
int CvScalar value
Definition: core_c.h:720
CvSize size
Definition: core_c.h:112
const CvArr CvArr * x
Definition: core_c.h:1195
const CvArr * y
Definition: core_c.h:1187
CV_EXPORTS_W int getNumThreads()
Returns the number of threads used by OpenCV for parallel regions.
#define CV_Assert(expr)
Checks a condition at runtime and throws exception if it fails.
Definition: base.hpp:342
T lock(T... args)
T make_heap(T... args)
T move(T... args)
Definition: flann.hpp:60
T pop_back(T... args)
T pop_heap(T... args)
T push_back(T... args)
T push_heap(T... args)
T reserve(T... args)
T size(T... args)
Definition: cvstd_wrapper.hpp:74