heap.h
Go to the documentation of this file.
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 
34 #include <algorithm>
35 #include <vector>
36 
37 namespace cvflann
38 {
39 
47 template <typename T>
48 class Heap
49 {
50 
55  std::vector<T> heap;
56  int length;
57 
61  int count;
62 
63 
64 
65 public:
73  Heap(int sz)
74  {
75  length = sz;
76  heap.reserve(length);
77  count = 0;
78  }
79 
84  int size()
85  {
86  return count;
87  }
88 
94  bool empty()
95  {
96  return size()==0;
97  }
98 
102  void clear()
103  {
104  heap.clear();
105  count = 0;
106  }
107 
108  struct CompareT
109  {
110  bool operator()(const T& t_1, const T& t_2) const
111  {
112  return t_2 < t_1;
113  }
114  };
115 
125  void insert(T value)
126  {
127  /* If heap is full, then return without adding this element. */
128  if (count == length) {
129  return;
130  }
131 
132  heap.push_back(value);
133  static CompareT compareT;
134  std::push_heap(heap.begin(), heap.end(), compareT);
135  ++count;
136  }
137 
138 
139 
147  bool popMin(T& value)
148  {
149  if (count == 0) {
150  return false;
151  }
152 
153  value = heap[0];
154  static CompareT compareT;
155  std::pop_heap(heap.begin(), heap.end(), compareT);
156  heap.pop_back();
157  --count;
158 
159  return true; /* Return old last node. */
160  }
161 };
162 
163 }
164 
165 #endif //OPENCV_FLANN_HEAP_H_
void clear()
Definition: heap.h:102
void insert(T value)
Definition: heap.h:125
bool empty()
Definition: heap.h:94
const CvMat const CvMat const CvMat CvMat CvMat CvMat CvMat CvSize CvMat CvMat * T
Definition: calib3d.hpp:270
Definition: heap.h:108
GLuint GLuint GLsizei count
Definition: core_c.h:973
GLuint GLsizei GLsizei * length
int size()
Definition: heap.h:84
Heap(int sz)
Definition: heap.h:73
GLsizei const GLfloat * value
Definition: core_c.h:341
bool operator()(const T &t_1, const T &t_2) const
Definition: heap.h:110
Definition: heap.h:48
bool popMin(T &value)
Definition: heap.h:147