include/opencv2/flann/heap.h
Go to the documentation of this file.
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_