dynamic_bitset.h

00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *************************************************************************/
00030 
00031 /***********************************************************************
00032  * Author: Vincent Rabaud
00033  *************************************************************************/
00034 
00035 #ifndef OPENCV_FLANN_DYNAMIC_BITSET_H_
00036 #define OPENCV_FLANN_DYNAMIC_BITSET_H_
00037 
00038 #ifndef FLANN_USE_BOOST
00039 #  define FLANN_USE_BOOST 0
00040 #endif
00041 //#define FLANN_USE_BOOST 1
00042 #if FLANN_USE_BOOST
00043 #include <boost/dynamic_bitset.hpp>
00044 typedef boost::dynamic_bitset<> DynamicBitset;
00045 #else
00046 
00047 #include <limits.h>
00048 
00049 #include "dist.h"
00050 
00051 namespace cvflann {
00052 
00053 /** Class re-implementing the boost version of it
00054  * This helps not depending on boost, it also does not do the bound checks
00055  * and has a way to reset a block for speed
00056  */
00057 class DynamicBitset
00058 {
00059 public:
00060     /** default constructor
00061      */
00062     DynamicBitset()
00063     {
00064     }
00065 
00066     /** only constructor we use in our code
00067      * @param sz the size of the bitset (in bits)
00068      */
00069     DynamicBitset(size_t sz)
00070     {
00071         resize(sz);
00072         reset();
00073     }
00074 
00075     /** Sets all the bits to 0
00076      */
00077     void clear()
00078     {
00079         std::fill(bitset_.begin(), bitset_.end(), 0);
00080     }
00081 
00082     /** @brief checks if the bitset is empty
00083      * @return true if the bitset is empty
00084      */
00085     bool empty() const
00086     {
00087         return bitset_.empty();
00088     }
00089 
00090     /** set all the bits to 0
00091      */
00092     void reset()
00093     {
00094         std::fill(bitset_.begin(), bitset_.end(), 0);
00095     }
00096 
00097     /** @brief set one bit to 0
00098      * @param index
00099      */
00100     void reset(size_t index)
00101     {
00102         bitset_[index / cell_bit_size_] &= ~(size_t(1) << (index % cell_bit_size_));
00103     }
00104 
00105     /** @brief sets a specific bit to 0, and more bits too
00106      * This function is useful when resetting a given set of bits so that the
00107      * whole bitset ends up being 0: if that's the case, we don't care about setting
00108      * other bits to 0
00109      * @param index
00110      */
00111     void reset_block(size_t index)
00112     {
00113         bitset_[index / cell_bit_size_] = 0;
00114     }
00115 
00116     /** resize the bitset so that it contains at least sz bits
00117      * @param sz
00118      */
00119     void resize(size_t sz)
00120     {
00121         size_ = sz;
00122         bitset_.resize(sz / cell_bit_size_ + 1);
00123     }
00124 
00125     /** set a bit to true
00126      * @param index the index of the bit to set to 1
00127      */
00128     void set(size_t index)
00129     {
00130         bitset_[index / cell_bit_size_] |= size_t(1) << (index % cell_bit_size_);
00131     }
00132 
00133     /** gives the number of contained bits
00134      */
00135     size_t size() const
00136     {
00137         return size_;
00138     }
00139 
00140     /** check if a bit is set
00141      * @param index the index of the bit to check
00142      * @return true if the bit is set
00143      */
00144     bool test(size_t index) const
00145     {
00146         return (bitset_[index / cell_bit_size_] & (size_t(1) << (index % cell_bit_size_))) != 0;
00147     }
00148 
00149 private:
00150     std::vector<size_t> bitset_;
00151     size_t size_;
00152     static const unsigned int cell_bit_size_ = CHAR_BIT * sizeof(size_t);
00153 };
00154 
00155 } // namespace cvflann
00156 
00157 #endif
00158 
00159 #endif // OPENCV_FLANN_DYNAMIC_BITSET_H_