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 
Heap(int sz)73     Heap(int sz)
74     {
75         length = sz;
76         heap.reserve(length);
77         count = 0;
78     }
79 
80     /**
81      *
82      * Returns: heap size
83      */
size()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      */
empty()94     bool empty()
95     {
96         return size()==0;
97     }
98 
99     /**
100      * Clears the heap.
101      */
clear()102     void clear()
103     {
104         heap.clear();
105         count = 0;
106     }
107 
108     struct CompareT
109     {
operatorCompareT110         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      */
insert(T value)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      */
popMin(T & value)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_
166