Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

include/opencv2/flann/heap.h@0:0e0631af0305, 2021-01-29 (annotated)

Committer:
RyoheiHagimoto
Date:
Fri Jan 29 04:53:38 2021 +0000
Revision:
0:0e0631af0305
copied from https://github.com/d-kato/opencv-lib.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
RyoheiHagimoto 0:0e0631af0305 1 /***********************************************************************
RyoheiHagimoto 0:0e0631af0305 2 * Software License Agreement (BSD License)
RyoheiHagimoto 0:0e0631af0305 3 *
RyoheiHagimoto 0:0e0631af0305 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
RyoheiHagimoto 0:0e0631af0305 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
RyoheiHagimoto 0:0e0631af0305 6 *
RyoheiHagimoto 0:0e0631af0305 7 * THE BSD LICENSE
RyoheiHagimoto 0:0e0631af0305 8 *
RyoheiHagimoto 0:0e0631af0305 9 * Redistribution and use in source and binary forms, with or without
RyoheiHagimoto 0:0e0631af0305 10 * modification, are permitted provided that the following conditions
RyoheiHagimoto 0:0e0631af0305 11 * are met:
RyoheiHagimoto 0:0e0631af0305 12 *
RyoheiHagimoto 0:0e0631af0305 13 * 1. Redistributions of source code must retain the above copyright
RyoheiHagimoto 0:0e0631af0305 14 * notice, this list of conditions and the following disclaimer.
RyoheiHagimoto 0:0e0631af0305 15 * 2. Redistributions in binary form must reproduce the above copyright
RyoheiHagimoto 0:0e0631af0305 16 * notice, this list of conditions and the following disclaimer in the
RyoheiHagimoto 0:0e0631af0305 17 * documentation and/or other materials provided with the distribution.
RyoheiHagimoto 0:0e0631af0305 18 *
RyoheiHagimoto 0:0e0631af0305 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
RyoheiHagimoto 0:0e0631af0305 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
RyoheiHagimoto 0:0e0631af0305 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
RyoheiHagimoto 0:0e0631af0305 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
RyoheiHagimoto 0:0e0631af0305 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
RyoheiHagimoto 0:0e0631af0305 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
RyoheiHagimoto 0:0e0631af0305 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
RyoheiHagimoto 0:0e0631af0305 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
RyoheiHagimoto 0:0e0631af0305 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
RyoheiHagimoto 0:0e0631af0305 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
RyoheiHagimoto 0:0e0631af0305 29 *************************************************************************/
RyoheiHagimoto 0:0e0631af0305 30
RyoheiHagimoto 0:0e0631af0305 31 #ifndef OPENCV_FLANN_HEAP_H_
RyoheiHagimoto 0:0e0631af0305 32 #define OPENCV_FLANN_HEAP_H_
RyoheiHagimoto 0:0e0631af0305 33
RyoheiHagimoto 0:0e0631af0305 34 #include <algorithm>
RyoheiHagimoto 0:0e0631af0305 35 #include <vector>
RyoheiHagimoto 0:0e0631af0305 36
RyoheiHagimoto 0:0e0631af0305 37 namespace cvflann
RyoheiHagimoto 0:0e0631af0305 38 {
RyoheiHagimoto 0:0e0631af0305 39
RyoheiHagimoto 0:0e0631af0305 40 /**
RyoheiHagimoto 0:0e0631af0305 41 * Priority Queue Implementation
RyoheiHagimoto 0:0e0631af0305 42 *
RyoheiHagimoto 0:0e0631af0305 43 * The priority queue is implemented with a heap. A heap is a complete
RyoheiHagimoto 0:0e0631af0305 44 * (full) binary tree in which each parent is less than both of its
RyoheiHagimoto 0:0e0631af0305 45 * children, but the order of the children is unspecified.
RyoheiHagimoto 0:0e0631af0305 46 */
RyoheiHagimoto 0:0e0631af0305 47 template <typename T>
RyoheiHagimoto 0:0e0631af0305 48 class Heap
RyoheiHagimoto 0:0e0631af0305 49 {
RyoheiHagimoto 0:0e0631af0305 50
RyoheiHagimoto 0:0e0631af0305 51 /**
RyoheiHagimoto 0:0e0631af0305 52 * Storage array for the heap.
RyoheiHagimoto 0:0e0631af0305 53 * Type T must be comparable.
RyoheiHagimoto 0:0e0631af0305 54 */
RyoheiHagimoto 0:0e0631af0305 55 std::vector<T> heap;
RyoheiHagimoto 0:0e0631af0305 56 int length;
RyoheiHagimoto 0:0e0631af0305 57
RyoheiHagimoto 0:0e0631af0305 58 /**
RyoheiHagimoto 0:0e0631af0305 59 * Number of element in the heap
RyoheiHagimoto 0:0e0631af0305 60 */
RyoheiHagimoto 0:0e0631af0305 61 int count;
RyoheiHagimoto 0:0e0631af0305 62
RyoheiHagimoto 0:0e0631af0305 63
RyoheiHagimoto 0:0e0631af0305 64
RyoheiHagimoto 0:0e0631af0305 65 public:
RyoheiHagimoto 0:0e0631af0305 66 /**
RyoheiHagimoto 0:0e0631af0305 67 * Constructor.
RyoheiHagimoto 0:0e0631af0305 68 *
RyoheiHagimoto 0:0e0631af0305 69 * Params:
RyoheiHagimoto 0:0e0631af0305 70 * sz = heap size
RyoheiHagimoto 0:0e0631af0305 71 */
RyoheiHagimoto 0:0e0631af0305 72
RyoheiHagimoto 0:0e0631af0305 73 Heap(int sz)
RyoheiHagimoto 0:0e0631af0305 74 {
RyoheiHagimoto 0:0e0631af0305 75 length = sz;
RyoheiHagimoto 0:0e0631af0305 76 heap.reserve(length);
RyoheiHagimoto 0:0e0631af0305 77 count = 0;
RyoheiHagimoto 0:0e0631af0305 78 }
RyoheiHagimoto 0:0e0631af0305 79
RyoheiHagimoto 0:0e0631af0305 80 /**
RyoheiHagimoto 0:0e0631af0305 81 *
RyoheiHagimoto 0:0e0631af0305 82 * Returns: heap size
RyoheiHagimoto 0:0e0631af0305 83 */
RyoheiHagimoto 0:0e0631af0305 84 int size()
RyoheiHagimoto 0:0e0631af0305 85 {
RyoheiHagimoto 0:0e0631af0305 86 return count;
RyoheiHagimoto 0:0e0631af0305 87 }
RyoheiHagimoto 0:0e0631af0305 88
RyoheiHagimoto 0:0e0631af0305 89 /**
RyoheiHagimoto 0:0e0631af0305 90 * Tests if the heap is empty
RyoheiHagimoto 0:0e0631af0305 91 *
RyoheiHagimoto 0:0e0631af0305 92 * Returns: true is heap empty, false otherwise
RyoheiHagimoto 0:0e0631af0305 93 */
RyoheiHagimoto 0:0e0631af0305 94 bool empty()
RyoheiHagimoto 0:0e0631af0305 95 {
RyoheiHagimoto 0:0e0631af0305 96 return size()==0;
RyoheiHagimoto 0:0e0631af0305 97 }
RyoheiHagimoto 0:0e0631af0305 98
RyoheiHagimoto 0:0e0631af0305 99 /**
RyoheiHagimoto 0:0e0631af0305 100 * Clears the heap.
RyoheiHagimoto 0:0e0631af0305 101 */
RyoheiHagimoto 0:0e0631af0305 102 void clear()
RyoheiHagimoto 0:0e0631af0305 103 {
RyoheiHagimoto 0:0e0631af0305 104 heap.clear();
RyoheiHagimoto 0:0e0631af0305 105 count = 0;
RyoheiHagimoto 0:0e0631af0305 106 }
RyoheiHagimoto 0:0e0631af0305 107
RyoheiHagimoto 0:0e0631af0305 108 struct CompareT
RyoheiHagimoto 0:0e0631af0305 109 {
RyoheiHagimoto 0:0e0631af0305 110 bool operator()(const T& t_1, const T& t_2) const
RyoheiHagimoto 0:0e0631af0305 111 {
RyoheiHagimoto 0:0e0631af0305 112 return t_2 < t_1;
RyoheiHagimoto 0:0e0631af0305 113 }
RyoheiHagimoto 0:0e0631af0305 114 };
RyoheiHagimoto 0:0e0631af0305 115
RyoheiHagimoto 0:0e0631af0305 116 /**
RyoheiHagimoto 0:0e0631af0305 117 * Insert a new element in the heap.
RyoheiHagimoto 0:0e0631af0305 118 *
RyoheiHagimoto 0:0e0631af0305 119 * We select the next empty leaf node, and then keep moving any larger
RyoheiHagimoto 0:0e0631af0305 120 * parents down until the right location is found to store this element.
RyoheiHagimoto 0:0e0631af0305 121 *
RyoheiHagimoto 0:0e0631af0305 122 * Params:
RyoheiHagimoto 0:0e0631af0305 123 * value = the new element to be inserted in the heap
RyoheiHagimoto 0:0e0631af0305 124 */
RyoheiHagimoto 0:0e0631af0305 125 void insert(T value)
RyoheiHagimoto 0:0e0631af0305 126 {
RyoheiHagimoto 0:0e0631af0305 127 /* If heap is full, then return without adding this element. */
RyoheiHagimoto 0:0e0631af0305 128 if (count == length) {
RyoheiHagimoto 0:0e0631af0305 129 return;
RyoheiHagimoto 0:0e0631af0305 130 }
RyoheiHagimoto 0:0e0631af0305 131
RyoheiHagimoto 0:0e0631af0305 132 heap.push_back(value);
RyoheiHagimoto 0:0e0631af0305 133 static CompareT compareT;
RyoheiHagimoto 0:0e0631af0305 134 std::push_heap(heap.begin(), heap.end(), compareT);
RyoheiHagimoto 0:0e0631af0305 135 ++count;
RyoheiHagimoto 0:0e0631af0305 136 }
RyoheiHagimoto 0:0e0631af0305 137
RyoheiHagimoto 0:0e0631af0305 138
RyoheiHagimoto 0:0e0631af0305 139
RyoheiHagimoto 0:0e0631af0305 140 /**
RyoheiHagimoto 0:0e0631af0305 141 * Returns the node of minimum value from the heap (top of the heap).
RyoheiHagimoto 0:0e0631af0305 142 *
RyoheiHagimoto 0:0e0631af0305 143 * Params:
RyoheiHagimoto 0:0e0631af0305 144 * value = out parameter used to return the min element
RyoheiHagimoto 0:0e0631af0305 145 * Returns: false if heap empty
RyoheiHagimoto 0:0e0631af0305 146 */
RyoheiHagimoto 0:0e0631af0305 147 bool popMin(T& value)
RyoheiHagimoto 0:0e0631af0305 148 {
RyoheiHagimoto 0:0e0631af0305 149 if (count == 0) {
RyoheiHagimoto 0:0e0631af0305 150 return false;
RyoheiHagimoto 0:0e0631af0305 151 }
RyoheiHagimoto 0:0e0631af0305 152
RyoheiHagimoto 0:0e0631af0305 153 value = heap[0];
RyoheiHagimoto 0:0e0631af0305 154 static CompareT compareT;
RyoheiHagimoto 0:0e0631af0305 155 std::pop_heap(heap.begin(), heap.end(), compareT);
RyoheiHagimoto 0:0e0631af0305 156 heap.pop_back();
RyoheiHagimoto 0:0e0631af0305 157 --count;
RyoheiHagimoto 0:0e0631af0305 158
RyoheiHagimoto 0:0e0631af0305 159 return true; /* Return old last node. */
RyoheiHagimoto 0:0e0631af0305 160 }
RyoheiHagimoto 0:0e0631af0305 161 };
RyoheiHagimoto 0:0e0631af0305 162
RyoheiHagimoto 0:0e0631af0305 163 }
RyoheiHagimoto 0:0e0631af0305 164
RyoheiHagimoto 0:0e0631af0305 165 #endif //OPENCV_FLANN_HEAP_H_