git.maemo.org Git - opencv/blob - 3rdparty/flann/util/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 HEAP_H
  32 #define HEAP_H
  33
  34
  35 #include <algorithm>
  36 using namespace std;
  37
  38 namespace flann
  39 {
  40
  41 /**
  42  * Priority Queue Implementation
  43  *
  44  * The priority queue is implemented with a heap.  A heap is a complete
  45  * (full) binary tree in which each parent is less than both of its
  46  * children, but the order of the children is unspecified.
  47  * Note that a heap uses 1-based indexing to allow for power-of-2
  48  * location of parents and children.  We ignore element 0 of Heap array.
  49  */
  50 template <typename T>
  51 class Heap {
  52
  53         /**
  54         * Storage array for the heap.
  55         * Type T must be comparable.
  56         */
  57         T* heap;
  58     int length;
  59
  60         /**
  61          * Number of element in the heap
  62          */
  63         int count;
  64
  65
  66
  67 public:
  68         /**
  69          * Constructor.
  70          *
  71          * Params:
  72          *     size = heap size
  73          */
  74
  75         Heap(int size)
  76         {
  77         length = size+1;
  78                 heap = new T[length];  // heap uses 1-based indexing
  79                 count = 0;
  80         }
  81
  82
  83         /**
  84          * Destructor.
  85          *
  86          */
  87         ~Heap()
  88         {
  89                 delete[] heap;
  90         }
  91
  92         /**
  93          *
  94          * Returns: heap size
  95          */
  96         int size()
  97         {
  98                 return count;
  99         }
 100
 101         /**
 102          * Tests if the heap is empty
 103          *
 104          * Returns: true is heap empty, false otherwise
 105          */
 106         bool empty()
 107         {
 108                 return size()==0;
 109         }
 110
 111         /**
 112          * Clears the heap.
 113          */
 114         void clear()
 115         {
 116                 count = 0;
 117         }
 118
 119
 120         /**
 121          * Insert a new element in the heap.
 122          *
 123          * We select the next empty leaf node, and then keep moving any larger
 124          * parents down until the right location is found to store this element.
 125          *
 126          * Params:
 127          *     value = the new element to be inserted in the heap
 128          */
 129         void insert(T value)
 130         {
 131                 /* If heap is full, then return without adding this element. */
 132                 if (count == length-1) {
 133                         return;
 134                 }
 135
 136                 int loc = ++(count);   /* Remember 1-based indexing. */
 137
 138                 /* Keep moving parents down until a place is found for this node. */
 139                 int par = loc / 2;                 /* Location of parent. */
 140                 while (par > 0  && value < heap[par]) {
 141                         heap[loc] = heap[par];     /* Move parent down to loc. */
 142                         loc = par;
 143                         par = loc / 2;
 144                 }
 145                 /* Insert the element at the determined location. */
 146                 heap[loc] = value;
 147         }
 148
 149
 150
 151         /**
 152          * Returns the node of minimum value from the heap (top of the heap).
 153          *
 154          * Params:
 155          *     value = out parameter used to return the min element
 156          * Returns: false if heap empty
 157          */
 158         bool popMin(T& value)
 159         {
 160                 if (count == 0) {
 161                         return false;
 162                 }
 163
 164                 /* Switch first node with last. */
 165                 swap(heap[1],heap[count]);
 166
 167                 count -= 1;
 168                 heapify(1);      /* Move new node 1 to right position. */
 169
 170                 value = heap[count + 1];
 171                 return true;  /* Return old last node. */
 172         }
 173
 174
 175         /**
 176          * Reorganizes the heap (a parent is smaller than its children)
 177          * starting with a node.
 178          *
 179          * Params:
 180          *     parent = node form which to start heap reorganization.
 181          */
 182         void heapify(int parent)
 183         {
 184                 int minloc = parent;
 185
 186                 /* Check the left child */
 187                 int left = 2 * parent;
 188                 if (left <= count && heap[left] < heap[parent]) {
 189                         minloc = left;
 190                 }
 191
 192                 /* Check the right child */
 193                 int right = left + 1;
 194                 if (right <= count && heap[right] < heap[minloc]) {
 195                         minloc = right;
 196                 }
 197
 198                 /* If a child was smaller, than swap parent with it and Heapify. */
 199                 if (minloc != parent) {
 200                         swap(heap[parent],heap[minloc]);
 201                         heapify(minloc);
 202                 }
 203         }
 204
 205 };
 206
 207 }
 208
 209 #endif //HEAP_H