OpenCV 4.5.3(日本語機械翻訳)
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 namespace cvflann
40{
41
49 template <typename T>
50 class Heap
51{
52
57 std::vector<T> heap;
58 int length;
59
63 int count;
64
65
66
67 public:
75 Heap(int sz)
76 {
77 length = sz;
78 heap.reserve(length);
79 count = 0;
80 }
81
86 int size()
87 {
88 return count;
89 }
90
96 bool empty()
97 {
98 return size()==0;
99 }
100
104 void clear()
105 {
106 heap.clear();
107 count = 0;
108 }
109
110 struct CompareT
111 {
112 bool operator()(const T& t_1, const T& t_2) const
113 {
114 return t_2 < t_1;
115 }
116 };
117
127 void insert(T value)
128 {
129 /* If heap is full, then return without adding this element. */
130 if (count == length) {
131 return;
132 }
133
134 heap.push_back(value);
135 static CompareT compareT;
136 std::push_heap(heap.begin(), heap.end(), compareT);
137 ++count;
138 }
139
140
141
149 bool popMin(T& value)
150 {
151 if (count == 0) {
152 return false;
153 }
154
155 value = heap[0];
156 static CompareT compareT;
157 std::pop_heap(heap.begin(), heap.end(), compareT);
158 heap.pop_back();
159 --count;
160
161 return true; /* Return old last node. */
162 }
163};
164
165}
166
168
169 #endif //OPENCV_FLANN_HEAP_H_
構築: doxygen 1.9.2