Joe Verbout
/
main
opencv on mbed
Embed:
(wiki syntax)
Show/hide line numbers
heap.h
00001 /*********************************************************************** 00002 * Software License Agreement (BSD License) 00003 * 00004 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. 00005 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved. 00006 * 00007 * THE BSD LICENSE 00008 * 00009 * Redistribution and use in source and binary forms, with or without 00010 * modification, are permitted provided that the following conditions 00011 * are met: 00012 * 00013 * 1. Redistributions of source code must retain the above copyright 00014 * notice, this list of conditions and the following disclaimer. 00015 * 2. Redistributions in binary form must reproduce the above copyright 00016 * notice, this list of conditions and the following disclaimer in the 00017 * documentation and/or other materials provided with the distribution. 00018 * 00019 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 *************************************************************************/ 00030 00031 #ifndef OPENCV_FLANN_HEAP_H_ 00032 #define OPENCV_FLANN_HEAP_H_ 00033 00034 #include <algorithm> 00035 #include <vector> 00036 00037 namespace cvflann 00038 { 00039 00040 /** 00041 * Priority Queue Implementation 00042 * 00043 * The priority queue is implemented with a heap. A heap is a complete 00044 * (full) binary tree in which each parent is less than both of its 00045 * children, but the order of the children is unspecified. 00046 */ 00047 template <typename T> 00048 class Heap 00049 { 00050 00051 /** 00052 * Storage array for the heap. 00053 * Type T must be comparable. 00054 */ 00055 std::vector<T> heap; 00056 int length; 00057 00058 /** 00059 * Number of element in the heap 00060 */ 00061 int count; 00062 00063 00064 00065 public: 00066 /** 00067 * Constructor. 00068 * 00069 * Params: 00070 * sz = heap size 00071 */ 00072 00073 Heap(int sz) 00074 { 00075 length = sz; 00076 heap.reserve(length); 00077 count = 0; 00078 } 00079 00080 /** 00081 * 00082 * Returns: heap size 00083 */ 00084 int size() 00085 { 00086 return count; 00087 } 00088 00089 /** 00090 * Tests if the heap is empty 00091 * 00092 * Returns: true is heap empty, false otherwise 00093 */ 00094 bool empty() 00095 { 00096 return size()==0; 00097 } 00098 00099 /** 00100 * Clears the heap. 00101 */ 00102 void clear() 00103 { 00104 heap.clear(); 00105 count = 0; 00106 } 00107 00108 struct CompareT 00109 { 00110 bool operator()(const T& t_1, const T& t_2) const 00111 { 00112 return t_2 < t_1; 00113 } 00114 }; 00115 00116 /** 00117 * Insert a new element in the heap. 00118 * 00119 * We select the next empty leaf node, and then keep moving any larger 00120 * parents down until the right location is found to store this element. 00121 * 00122 * Params: 00123 * value = the new element to be inserted in the heap 00124 */ 00125 void insert(T value) 00126 { 00127 /* If heap is full, then return without adding this element. */ 00128 if (count == length) { 00129 return; 00130 } 00131 00132 heap.push_back(value); 00133 static CompareT compareT; 00134 std::push_heap(heap.begin(), heap.end(), compareT); 00135 ++count; 00136 } 00137 00138 00139 00140 /** 00141 * Returns the node of minimum value from the heap (top of the heap). 00142 * 00143 * Params: 00144 * value = out parameter used to return the min element 00145 * Returns: false if heap empty 00146 */ 00147 bool popMin(T& value) 00148 { 00149 if (count == 0) { 00150 return false; 00151 } 00152 00153 value = heap[0]; 00154 static CompareT compareT; 00155 std::pop_heap(heap.begin(), heap.end(), compareT); 00156 heap.pop_back(); 00157 --count; 00158 00159 return true; /* Return old last node. */ 00160 } 00161 }; 00162 00163 } 00164 00165 #endif //OPENCV_FLANN_HEAP_H_ 00166
Generated on Tue Jul 12 2022 16:42:38 by 1.7.2