Home | History | Annotate | Download | only in flann 
      1 /***********************************************************************
      2  * Software License Agreement (BSD License)
      3  *
      4  * Copyright 2008-2009  Marius Muja (mariusm (at) cs.ubc.ca). All rights reserved.
      5  * Copyright 2008-2009  David G. Lowe (lowe (at) 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      */
     62     DynamicBitset()
     63     {
     64     }
     65 
     66     /** only constructor we use in our code
     67      * @param sz 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     /** 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 index
     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 index
    110      */
    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      */
    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      */
    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      */
    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      */
    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