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_HEAP_H_ 00032 #define _OPENCV_HEAP_H_ 00033 00034 00035 #include <algorithm> 00036 00037 namespace cvflann 00038 { 00039 00049 template <typename T> 00050 class Heap { 00051 00056 T* heap; 00057 int length; 00058 00062 int count; 00063 00064 00065 00066 public: 00074 Heap(int size) 00075 { 00076 length = size+1; 00077 heap = new T[length]; // heap uses 1-based indexing 00078 count = 0; 00079 } 00080 00081 00086 ~Heap() 00087 { 00088 delete[] heap; 00089 } 00090 00095 int size() 00096 { 00097 return count; 00098 } 00099 00105 bool empty() 00106 { 00107 return size()==0; 00108 } 00109 00113 void clear() 00114 { 00115 count = 0; 00116 } 00117 00118 00128 void insert(T value) 00129 { 00130 /* If heap is full, then return without adding this element. */ 00131 if (count == length-1) { 00132 return; 00133 } 00134 00135 int loc = ++(count); /* Remember 1-based indexing. */ 00136 00137 /* Keep moving parents down until a place is found for this node. */ 00138 int par = loc / 2; /* Location of parent. */ 00139 while (par > 0 && value < heap[par]) { 00140 heap[loc] = heap[par]; /* Move parent down to loc. */ 00141 loc = par; 00142 par = loc / 2; 00143 } 00144 /* Insert the element at the determined location. */ 00145 heap[loc] = value; 00146 } 00147 00148 00149 00157 bool popMin(T& value) 00158 { 00159 if (count == 0) { 00160 return false; 00161 } 00162 00163 /* Switch first node with last. */ 00164 std::swap(heap[1],heap[count]); 00165 00166 count -= 1; 00167 heapify(1); /* Move new node 1 to right position. */ 00168 00169 value = heap[count + 1]; 00170 return true; /* Return old last node. */ 00171 } 00172 00173 00181 void heapify(int parent) 00182 { 00183 int minloc = parent; 00184 00185 /* Check the left child */ 00186 int left = 2 * parent; 00187 if (left <= count && heap[left] < heap[parent]) { 00188 minloc = left; 00189 } 00190 00191 /* Check the right child */ 00192 int right = left + 1; 00193 if (right <= count && heap[right] < heap[minloc]) { 00194 minloc = right; 00195 } 00196 00197 /* If a child was smaller, than swap parent with it and Heapify. */ 00198 if (minloc != parent) { 00199 std::swap(heap[parent],heap[minloc]); 00200 heapify(minloc); 00201 } 00202 } 00203 00204 }; 00205 00206 } // namespace cvflann 00207 00208 #endif //_OPENCV_HEAP_H_