modules/flann/include/opencv2/flann/dynamic_bitset.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 /***********************************************************************
  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     /** @param default constructor
  61      */
  62     DynamicBitset()
  63     {
  64     }
  65
  66     /** @param only constructor we use in our code
  67      * @param the size of the bitset (in bits)
  68      */
  69     DynamicBitset(size_t sz)
  70     {
  71         resize(sz);
  72         reset();
  73     }
  74
  75     /** Sets all the bits to 0
  76      */
  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      */
  85     bool empty() const
  86     {
  87         return bitset_.empty();
  88     }
  89
  90     /** @param set all the bits to 0
  91      */
  92     void reset()
  93     {
  94         std::fill(bitset_.begin(), bitset_.end(), 0);
  95     }
  96
  97     /** @brief set one bit to 0
  98      * @param
  99      */
 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
 110      */
 111     void reset_block(size_t index)
 112     {
 113         bitset_[index / cell_bit_size_] = 0;
 114     }
 115
 116     /** @param resize the bitset so that it contains at least size bits
 117      * @param size
 118      */
 119     void resize(size_t sz)
 120     {
 121         size_ = sz;
 122         bitset_.resize(sz / cell_bit_size_ + 1);
 123     }
 124
 125     /** @param set a bit to true
 126      * @param index the index of the bit to set to 1
 127      */
 128     void set(size_t index)
 129     {
 130         bitset_[index / cell_bit_size_] |= size_t(1) << (index % cell_bit_size_);
 131     }
 132
 133     /** @param gives the number of contained bits
 134      */
 135     size_t size() const
 136     {
 137         return size_;
 138     }
 139
 140     /** @param 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      */
 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_