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 /***********************************************************************
32  * Author: Vincent Rabaud
33  *************************************************************************/
34 
35 #ifndef OPENCV_FLANN_DYNAMIC_BITSET_H_
36 #define OPENCV_FLANN_DYNAMIC_BITSET_H_
37 
38 #ifndef FLANN_USE_BOOST
39 #  define FLANN_USE_BOOST 0
40 #endif
41 //#define FLANN_USE_BOOST 1
42 #if FLANN_USE_BOOST
43 #include <boost/dynamic_bitset.hpp>
44 typedef boost::dynamic_bitset<> DynamicBitset;
45 #else
46 
47 #include <limits.h>
48 
49 #include "dist.h"
50 
51 namespace cvflann {
52 
53 /** Class re-implementing the boost version of it
54  * This helps not depending on boost, it also does not do the bound checks
55  * and has a way to reset a block for speed
56  */
57 class DynamicBitset
58 {
59 public:
60     /** default constructor
61      */
DynamicBitset()62     DynamicBitset()
63     {
64     }
65 
66     /** only constructor we use in our code
67      * @param sz the size of the bitset (in bits)
68      */
DynamicBitset(size_t sz)69     DynamicBitset(size_t sz)
70     {
71         resize(sz);
72         reset();
73     }
74 
75     /** Sets all the bits to 0
76      */
clear()77     void clear()
78     {
79         std::fill(bitset_.begin(), bitset_.end(), 0);
80     }
81 
82     /** @brief checks if the bitset is empty
83      * @return true if the bitset is empty
84      */
empty()85     bool empty() const
86     {
87         return bitset_.empty();
88     }
89 
90     /** set all the bits to 0
91      */
reset()92     void reset()
93     {
94         std::fill(bitset_.begin(), bitset_.end(), 0);
95     }
96 
97     /** @brief set one bit to 0
98      * @param index
99      */
reset(size_t index)100     void reset(size_t index)
101     {
102         bitset_[index / cell_bit_size_] &= ~(size_t(1) << (index % cell_bit_size_));
103     }
104 
105     /** @brief sets a specific bit to 0, and more bits too
106      * This function is useful when resetting a given set of bits so that the
107      * whole bitset ends up being 0: if that's the case, we don't care about setting
108      * other bits to 0
109      * @param index
110      */
reset_block(size_t index)111     void reset_block(size_t index)
112     {
113         bitset_[index / cell_bit_size_] = 0;
114     }
115 
116     /** resize the bitset so that it contains at least sz bits
117      * @param sz
118      */
resize(size_t sz)119     void resize(size_t sz)
120     {
121         size_ = sz;
122         bitset_.resize(sz / cell_bit_size_ + 1);
123     }
124 
125     /** set a bit to true
126      * @param index the index of the bit to set to 1
127      */
set(size_t index)128     void set(size_t index)
129     {
130         bitset_[index / cell_bit_size_] |= size_t(1) << (index % cell_bit_size_);
131     }
132 
133     /** gives the number of contained bits
134      */
size()135     size_t size() const
136     {
137         return size_;
138     }
139 
140     /** check if a bit is set
141      * @param index the index of the bit to check
142      * @return true if the bit is set
143      */
test(size_t index)144     bool test(size_t index) const
145     {
146         return (bitset_[index / cell_bit_size_] & (size_t(1) << (index % cell_bit_size_))) != 0;
147     }
148 
149 private:
150     std::vector<size_t> bitset_;
151     size_t size_;
152     static const unsigned int cell_bit_size_ = CHAR_BIT * sizeof(size_t);
153 };
154 
155 } // namespace cvflann
156 
157 #endif
158 
159 #endif // OPENCV_FLANN_DYNAMIC_BITSET_H_
160