modules/flann/include/opencv2/flann/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
  34 #include <algorithm>
  35 #include <vector>
  36
  37 namespace cvflann
  38 {
  39
  40 /**
  41  * Priority Queue Implementation
  42  *
  43  * The priority queue is implemented with a heap.  A heap is a complete
  44  * (full) binary tree in which each parent is less than both of its
  45  * children, but the order of the children is unspecified.
  46  */
  47 template <typename T>
  48 class Heap
  49 {
  50
  51     /**
  52      * Storage array for the heap.
  53      * Type T must be comparable.
  54      */
  55     std::vector<T> heap;
  56     int length;
  57
  58     /**
  59      * Number of element in the heap
  60      */
  61     int count;
  62
  63
  64
  65 public:
  66     /**
  67      * Constructor.
  68      *
  69      * Params:
  70      *     sz = heap size
  71      */
  72
  73     Heap(int sz)
  74     {
  75         length = sz;
  76         heap.reserve(length);
  77         count = 0;
  78     }
  79
  80     /**
  81      *
  82      * Returns: heap size
  83      */
  84     int size()
  85     {
  86         return count;
  87     }
  88
  89     /**
  90      * Tests if the heap is empty
  91      *
  92      * Returns: true is heap empty, false otherwise
  93      */
  94     bool empty()
  95     {
  96         return size()==0;
  97     }
  98
  99     /**
 100      * Clears the heap.
 101      */
 102     void clear()
 103     {
 104         heap.clear();
 105         count = 0;
 106     }
 107
 108     struct CompareT
 109     {
 110         bool operator()(const T& t_1, const T& t_2) const
 111         {
 112             return t_2 < t_1;
 113         }
 114     };
 115
 116     /**
 117      * Insert a new element in the heap.
 118      *
 119      * We select the next empty leaf node, and then keep moving any larger
 120      * parents down until the right location is found to store this element.
 121      *
 122      * Params:
 123      *     value = the new element to be inserted in the heap
 124      */
 125     void insert(T value)
 126     {
 127         /* If heap is full, then return without adding this element. */
 128         if (count == length) {
 129             return;
 130         }
 131
 132         heap.push_back(value);
 133         static CompareT compareT;
 134         std::push_heap(heap.begin(), heap.end(), compareT);
 135         ++count;
 136     }
 137
 138
 139
 140     /**
 141      * Returns the node of minimum value from the heap (top of the heap).
 142      *
 143      * Params:
 144      *     value = out parameter used to return the min element
 145      * Returns: false if heap empty
 146      */
 147     bool popMin(T& value)
 148     {
 149         if (count == 0) {
 150             return false;
 151         }
 152
 153         value = heap[0];
 154         static CompareT compareT;
 155         std::pop_heap(heap.begin(), heap.end(), compareT);
 156         heap.pop_back();
 157         --count;
 158
 159         return true;  /* Return old last node. */
 160     }
 161 };
 162
 163 }
 164
 165 #endif //OPENCV_FLANN_HEAP_H_