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