1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/graph/detail/bitset.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,910 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 Jeremy G. Siek
1.6 +// Authors: Jeremy G. Siek
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +/*
1.14 + * Copyright (c) 1998
1.15 + * Silicon Graphics Computer Systems, Inc.
1.16 + *
1.17 + * Permission to use, copy, modify, distribute and sell this software
1.18 + * and its documentation for any purpose is hereby granted without fee,
1.19 + * provided that the above copyright notice appear in all copies and
1.20 + * that both that copyright notice and this permission notice appear
1.21 + * in supporting documentation. Silicon Graphics makes no
1.22 + * representations about the suitability of this software for any
1.23 + * purpose. It is provided "as is" without express or implied warranty.
1.24 + */
1.25 +
1.26 +#include <boost/config.hpp>
1.27 +#include <memory>
1.28 +#include <stdexcept>
1.29 +#include <algorithm>
1.30 +#include <string>
1.31 +#include <boost/config.hpp>
1.32 +#include <boost/pending/ct_if.hpp>
1.33 +#include <boost/graph/detail/bitset_adaptor.hpp>
1.34 +
1.35 +// This provides versions of std::bitset with both static and dynamic size.
1.36 +
1.37 +// UNDER CONSTRUCTION
1.38 +
1.39 +
1.40 +// replace this later
1.41 +#include <cassert>
1.42 +#define BOOST_ASSERT_THROW(expr, except) assert(expr)
1.43 +
1.44 +namespace boost {
1.45 +
1.46 + namespace detail {
1.47 + // structure to aid in counting bits
1.48 + template<bool dummy = true>
1.49 + struct bit_count {
1.50 + static unsigned char value[256];
1.51 + };
1.52 +
1.53 + // Mapping from 8 bit unsigned integers to the index of the first bit
1.54 + template<bool dummy = true>
1.55 + struct first_bit_location {
1.56 + static unsigned char value[256];
1.57 + };
1.58 +
1.59 + template <typename WordType> // this size is in bits
1.60 + struct word_traits {
1.61 + typedef WordType word_type;
1.62 + static const std::size_t word_size = CHAR_BIT * sizeof(word_type);
1.63 + };
1.64 +
1.65 + //=========================================================================
1.66 + template <class WordTraits, class SizeType, class Derived>
1.67 + class bitset_base
1.68 + : public bitset_adaptor< SizeType,
1.69 + bitset_base<WordTraits, SizeType, Derived> >
1.70 + {
1.71 + // private:
1.72 + public:
1.73 + typedef SizeType size_type;
1.74 + typedef typename WordTraits::word_type word_type;
1.75 +
1.76 + static size_type s_which_word(size_type pos) {
1.77 + return pos / WordTraits::word_size;
1.78 + }
1.79 + static size_type s_which_byte(size_type pos) {
1.80 + return (pos % WordTraits::word_size) / CHAR_BIT;
1.81 + }
1.82 + static size_type s_which_bit(size_type pos) {
1.83 + return pos % WordTraits::word_size;
1.84 + }
1.85 + static word_type s_mask_bit(size_type pos) {
1.86 + return (static_cast<word_type>(1)) << s_which_bit(pos);
1.87 + }
1.88 + word_type& m_get_word(size_type pos) {
1.89 + return data()[s_which_word(pos)];
1.90 + }
1.91 + word_type m_get_word(size_type pos) const {
1.92 + return data()[s_which_word(pos)];
1.93 + }
1.94 + word_type& m_hi_word() { return data()[num_words() - 1]; }
1.95 + word_type m_hi_word() const { return data()[num_words() - 1]; }
1.96 +
1.97 + void m_sanitize_highest() {
1.98 + size_type extra_bits = size() % WordTraits::word_size;
1.99 + if (extra_bits)
1.100 + m_hi_word() &= ~((~static_cast<word_type>(0)) << extra_bits);
1.101 + }
1.102 + public:
1.103 +
1.104 + class reference {
1.105 + friend class bitset_base;
1.106 +
1.107 + word_type *m_word_ptr;
1.108 + size_type m_bit_pos;
1.109 +
1.110 + // left undefined
1.111 + reference();
1.112 +
1.113 + reference(bitset_base& b, size_type pos ) {
1.114 + m_word_ptr = &b.m_get_word(pos);
1.115 + m_bit_pos = s_which_bit(pos);
1.116 + }
1.117 +
1.118 + public:
1.119 + ~reference() {}
1.120 +
1.121 + // for b[i] = x;
1.122 + reference& operator=(bool x) {
1.123 + if ( x )
1.124 + *m_word_ptr |= s_mask_bit(m_bit_pos);
1.125 + else
1.126 + *m_word_ptr &= ~s_mask_bit(m_bit_pos);
1.127 +
1.128 + return *this;
1.129 + }
1.130 + // for b[i] = b[j];
1.131 + reference& operator=(const reference& j) {
1.132 + if ( (*(j.m_word_ptr) & s_mask_bit(j.m_bit_pos)) )
1.133 + *m_word_ptr |= s_mask_bit(m_bit_pos);
1.134 + else
1.135 + *m_word_ptr &= ~s_mask_bit(m_bit_pos);
1.136 +
1.137 + return *this;
1.138 + }
1.139 + // flips the bit
1.140 + bool operator~() const {
1.141 + return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) == 0;
1.142 + }
1.143 + // for x = b[i];
1.144 + operator bool() const {
1.145 + return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) != 0;
1.146 + }
1.147 + // for b[i].flip();
1.148 + reference& flip() {
1.149 + *m_word_ptr ^= s_mask_bit(m_bit_pos);
1.150 + return *this;
1.151 + }
1.152 + };
1.153 +
1.154 + void init_from_ulong(unsigned long val) {
1.155 + reset();
1.156 + const size_type n = (std::min)(sizeof(unsigned long) * CHAR_BIT,
1.157 + WordTraits::word_size * num_words());
1.158 + for(size_type i = 0; i < n; ++i, val >>= 1)
1.159 + if ( val & 0x1 )
1.160 + m_get_word(i) |= s_mask_bit(i);
1.161 + }
1.162 +
1.163 + // intersection: this = this & x
1.164 + Derived& operator&=(const Derived& x) {
1.165 + for (size_type i = 0; i < num_words(); ++i)
1.166 + data()[i] &= x.data()[i];
1.167 + return static_cast<Derived&>(*this);
1.168 + }
1.169 + // union: this = this | x
1.170 + Derived& operator|=(const Derived& x) {
1.171 + for (size_type i = 0; i < num_words(); ++i)
1.172 + data()[i] |= x.data()[i];
1.173 + return static_cast<Derived&>(*this);
1.174 + }
1.175 + // exclusive or: this = this ^ x
1.176 + Derived& operator^=(const Derived& x) {
1.177 + for (size_type i = 0; i < num_words(); ++i)
1.178 + data()[i] ^= x.data()[i];
1.179 + return static_cast<Derived&>(*this);
1.180 + }
1.181 + // left shift
1.182 + Derived& operator<<=(size_type pos);
1.183 +
1.184 + // right shift
1.185 + Derived& operator>>=(size_type pos);
1.186 +
1.187 + Derived& set() {
1.188 + for (size_type i = 0; i < num_words(); ++i)
1.189 + data()[i] = ~static_cast<word_type>(0);
1.190 + m_sanitize_highest();
1.191 + return static_cast<Derived&>(*this);
1.192 + }
1.193 +
1.194 + Derived& set(size_type pos, int val = true)
1.195 + {
1.196 + BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::set(pos,value)"));
1.197 + if (val)
1.198 + m_get_word(pos) |= s_mask_bit(pos);
1.199 + else
1.200 + m_get_word(pos) &= ~s_mask_bit(pos);
1.201 + return static_cast<Derived&>(*this);
1.202 + }
1.203 +
1.204 + Derived& reset() {
1.205 + for (size_type i = 0; i < num_words(); ++i)
1.206 + data()[i] = 0;
1.207 + return static_cast<Derived&>(*this);
1.208 + }
1.209 +
1.210 + Derived& reset(size_type pos) {
1.211 + BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::reset(pos)"));
1.212 + m_get_word(pos) &= ~s_mask_bit(pos);
1.213 + return static_cast<Derived&>(*this);
1.214 + }
1.215 +
1.216 + // compliment
1.217 + Derived operator~() const {
1.218 + return Derived(static_cast<const Derived&>(*this)).flip();
1.219 + }
1.220 +
1.221 + Derived& flip() {
1.222 + for (size_type i = 0; i < num_words(); ++i)
1.223 + data()[i] = ~data()[i];
1.224 + m_sanitize_highest();
1.225 + return static_cast<Derived&>(*this);
1.226 + }
1.227 + Derived& flip(size_type pos) {
1.228 + BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::flip(pos)"));
1.229 + m_get_word(pos) ^= s_mask_bit(pos);
1.230 + return static_cast<Derived&>(*this);
1.231 + }
1.232 +
1.233 + // element access
1.234 + reference operator[](size_type pos) { return reference(*this, pos); }
1.235 + bool operator[](size_type pos) const { return test(pos); }
1.236 +
1.237 + unsigned long to_ulong() const;
1.238 +
1.239 + // to_string
1.240 +
1.241 +
1.242 + size_type count() const {
1.243 + size_type result = 0;
1.244 + const unsigned char* byte_ptr = (const unsigned char*)data();
1.245 + const unsigned char* end_ptr =
1.246 + (const unsigned char*)(data() + num_words());
1.247 + while ( byte_ptr < end_ptr ) {
1.248 + result += bit_count<>::value[*byte_ptr];
1.249 + byte_ptr++;
1.250 + }
1.251 + return result;
1.252 + }
1.253 +
1.254 + // size() must be provided by Derived class
1.255 +
1.256 + bool operator==(const Derived& x) const {
1.257 + return std::equal(data(), data() + num_words(), x.data());
1.258 + }
1.259 +
1.260 + bool operator!=(const Derived& x) const {
1.261 + return ! this->operator==(x);
1.262 + }
1.263 +
1.264 + bool test(size_type pos) const {
1.265 + BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::test(pos)"));
1.266 + return (m_get_word(pos) & s_mask_bit(pos))
1.267 + != static_cast<word_type>(0);
1.268 + }
1.269 +
1.270 + bool any() const {
1.271 + for (size_type i = 0; i < num_words(); ++i) {
1.272 + if ( data()[i] != static_cast<word_type>(0) )
1.273 + return true;
1.274 + }
1.275 + return false;
1.276 + }
1.277 + bool none() const {
1.278 + return !any();
1.279 + }
1.280 +
1.281 + Derived operator<<(size_type pos) const
1.282 + { return Derived(static_cast<const Derived&>(*this)) <<= pos; }
1.283 +
1.284 + Derived operator>>(size_type pos) const
1.285 + { return Derived(static_cast<const Derived&>(*this)) >>= pos; }
1.286 +
1.287 + template <class CharT, class Traits, class Alloc>
1.288 + void m_copy_from_string(const basic_string<CharT,Traits,Alloc>& s,
1.289 + size_type pos, size_type n)
1.290 + {
1.291 + reset();
1.292 + const size_type nbits = (std::min)(size(), (std::min)(n, s.size() - pos));
1.293 + for (size_type i = 0; i < nbits; ++i) {
1.294 + switch(s[pos + nbits - i - 1]) {
1.295 + case '0':
1.296 + break;
1.297 + case '1':
1.298 + this->set(i);
1.299 + break;
1.300 + default:
1.301 + throw std::invalid_argument
1.302 + ("boost::bitset_base::m_copy_from_string(s, pos, n)");
1.303 + }
1.304 + }
1.305 + }
1.306 +
1.307 + template <class CharT, class Traits, class Alloc>
1.308 + void m_copy_to_string(basic_string<CharT, Traits, Alloc>& s) const
1.309 + {
1.310 + s.assign(size(), '0');
1.311 +
1.312 + for (size_type i = 0; i < size(); ++i)
1.313 + if (test(i))
1.314 + s[size() - 1 - i] = '1';
1.315 + }
1.316 +
1.317 + //-----------------------------------------------------------------------
1.318 + // Stuff not in std::bitset
1.319 +
1.320 + // difference: this = this - x
1.321 + Derived& operator-=(const Derived& x) {
1.322 + for (size_type i = 0; i < num_words(); ++i)
1.323 + data()[i] &= ~x.data()[i];
1.324 + return static_cast<Derived&>(*this);
1.325 + }
1.326 +
1.327 + // this wasn't working, why?
1.328 + int compare_3way(const Derived& x) const {
1.329 + return std::lexicographical_compare_3way
1.330 + (data(), data() + num_words(), x.data(), x.data() + x.num_words());
1.331 + }
1.332 +
1.333 + // less-than compare
1.334 + bool operator<(const Derived& x) const {
1.335 + return std::lexicographical_compare
1.336 + (data(), data() + num_words(), x.data(), x.data() + x.num_words());
1.337 + }
1.338 +
1.339 + // find the index of the first "on" bit
1.340 + size_type find_first() const;
1.341 +
1.342 + // find the index of the next "on" bit after prev
1.343 + size_type find_next(size_type prev) const;
1.344 +
1.345 +
1.346 + size_type _Find_first() const { return find_first(); }
1.347 +
1.348 + // find the index of the next "on" bit after prev
1.349 + size_type _Find_next(size_type prev) const { return find_next(prev); }
1.350 +
1.351 + // private:
1.352 + word_type* data()
1.353 + { return static_cast<Derived*>(this)->data(); }
1.354 +
1.355 + const word_type* data() const
1.356 + { return static_cast<const Derived*>(this)->data(); }
1.357 +
1.358 + size_type num_words() const
1.359 + { return static_cast<const Derived*>(this)->num_words(); }
1.360 +
1.361 + size_type size() const
1.362 + { return static_cast<const Derived*>(this)->size(); }
1.363 + };
1.364 +
1.365 + // 23.3.5.3 bitset operations:
1.366 + template <class W, class S, class D>
1.367 + inline D operator&(const bitset_base<W,S,D>& x,
1.368 + const bitset_base<W,S,D>& y) {
1.369 + D result(static_cast<const D&>(x));
1.370 + result &= static_cast<const D&>(y);
1.371 + return result;
1.372 + }
1.373 +
1.374 + template <class W, class S, class D>
1.375 + inline D operator|(const bitset_base<W,S,D>& x,
1.376 + const bitset_base<W,S,D>& y) {
1.377 + D result(static_cast<const D&>(x));
1.378 + result |= static_cast<const D&>(y);
1.379 + return result;
1.380 + }
1.381 +
1.382 + template <class W, class S, class D>
1.383 + inline D operator^(const bitset_base<W,S,D>& x,
1.384 + const bitset_base<W,S,D>& y) {
1.385 + D result(static_cast<const D&>(x));
1.386 + result ^= static_cast<const D&>(y);
1.387 + return result;
1.388 + }
1.389 +
1.390 + // this one is an extension
1.391 + template <class W, class S, class D>
1.392 + inline D operator-(const bitset_base<W,S,D>& x,
1.393 + const bitset_base<W,S,D>& y) {
1.394 + D result(static_cast<const D&>(x));
1.395 + result -= static_cast<const D&>(y);
1.396 + return result;
1.397 + }
1.398 +
1.399 + template <class W, class S, class D>
1.400 + inline int compare_3way(const bitset_base<W,S,D>& x,
1.401 + const bitset_base<W,S,D>& y) {
1.402 + return std::lexicographical_compare_3way
1.403 + (x.data(), x.data() + x.num_words(),
1.404 + y.data(), y.data() + y.num_words());
1.405 + }
1.406 +
1.407 +
1.408 + template <class W, class S, class D>
1.409 + std::istream&
1.410 + operator>>(std::istream& is, bitset_base<W,S,D>& x) {
1.411 + std::string tmp;
1.412 + tmp.reserve(x.size());
1.413 +
1.414 + // In new templatized iostreams, use istream::sentry
1.415 + if (is.flags() & ios::skipws) {
1.416 + char c;
1.417 + do
1.418 + is.get(c);
1.419 + while (is && isspace(c));
1.420 + if (is)
1.421 + is.putback(c);
1.422 + }
1.423 +
1.424 + for (S i = 0; i < x.size(); ++i) {
1.425 + char c;
1.426 + is.get(c);
1.427 +
1.428 + if (!is)
1.429 + break;
1.430 + else if (c != '0' && c != '1') {
1.431 + is.putback(c);
1.432 + break;
1.433 + }
1.434 + else
1.435 + // tmp.push_back(c);
1.436 + tmp += c;
1.437 + }
1.438 +
1.439 + if (tmp.empty())
1.440 + is.clear(is.rdstate() | ios::failbit);
1.441 + else
1.442 + x.m_copy_from_string(tmp, static_cast<S>(0), x.size());
1.443 +
1.444 + return is;
1.445 + }
1.446 +
1.447 + template <class W, class S, class D>
1.448 + std::ostream& operator<<(std::ostream& os,
1.449 + const bitset_base<W,S,D>& x) {
1.450 + std::string tmp;
1.451 + x.m_copy_to_string(tmp);
1.452 + return os << tmp;
1.453 + }
1.454 +
1.455 + //=========================================================================
1.456 + template <typename WordType = unsigned long,
1.457 + typename SizeType = std::size_t,
1.458 + typename Allocator = std::allocator<WordType>
1.459 + >
1.460 + class dyn_size_bitset
1.461 + : public bitset_base<word_traits<WordType>, SizeType,
1.462 + dyn_size_bitset<WordType,SizeType,Allocator> >
1.463 + {
1.464 + typedef dyn_size_bitset self;
1.465 + public:
1.466 + typedef SizeType size_type;
1.467 + private:
1.468 + typedef word_traits<WordType> WordTraits;
1.469 + static const size_type word_size = WordTraits::word_size;
1.470 +
1.471 + public:
1.472 + dyn_size_bitset(unsigned long val,
1.473 + size_type n,
1.474 + const Allocator& alloc = Allocator())
1.475 + : m_data(alloc.allocate((n + word_size - 1) / word_size)),
1.476 + m_size(n),
1.477 + m_num_words((n + word_size - 1) / word_size),
1.478 + m_alloc(alloc)
1.479 + {
1.480 + init_from_ulong(val);
1.481 + }
1.482 +
1.483 + dyn_size_bitset(size_type n, // size of the set's "universe"
1.484 + const Allocator& alloc = Allocator())
1.485 + : m_data(alloc.allocate((n + word_size - 1) / word_size)),
1.486 + m_size(n), m_num_words((n + word_size - 1) / word_size),
1.487 + m_alloc(alloc)
1.488 + { }
1.489 +
1.490 + template<class CharT, class Traits, class Alloc>
1.491 + explicit dyn_size_bitset
1.492 + (const basic_string<CharT,Traits,Alloc>& s,
1.493 + std::size_t pos = 0,
1.494 + std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos),
1.495 + const Allocator& alloc = Allocator())
1.496 + : m_data(alloc.allocate((n + word_size - 1) / word_size)),
1.497 + m_size(n), m_num_words((n + word_size - 1) / word_size),
1.498 + m_alloc(alloc)
1.499 + {
1.500 + BOOST_ASSERT_THROW(pos < s.size(), std::out_of_range("dyn_size_bitset::dyn_size_bitset(s,pos,n,alloc)"));
1.501 + m_copy_from_string(s, pos, n);
1.502 + }
1.503 +
1.504 + template <typename InputIterator>
1.505 + explicit dyn_size_bitset
1.506 + (InputIterator first, InputIterator last,
1.507 + size_type n, // size of the set's "universe"
1.508 + const Allocator& alloc = Allocator())
1.509 + : m_data(alloc.allocate((n + word_size - 1) / word_size)),
1.510 + m_size(N), m_num_words((n + word_size - 1) / word_size),
1.511 + m_alloc(alloc)
1.512 + {
1.513 + while (first != last)
1.514 + this->set(*first++);
1.515 + }
1.516 +
1.517 + ~dyn_size_bitset() {
1.518 + m_alloc.deallocate(m_data, m_num_words);
1.519 + }
1.520 +
1.521 + size_type size() const { return m_size; }
1.522 +
1.523 + // protected:
1.524 + size_type num_words() const { return m_num_words; }
1.525 +
1.526 + word_type* data() { return m_data; }
1.527 + const word_type* data() const { return m_data; }
1.528 +
1.529 + protected:
1.530 + word_type* m_data;
1.531 + SizeType m_size;
1.532 + SizeType m_num_words;
1.533 + Allocator m_alloc;
1.534 + };
1.535 +
1.536 + //=========================================================================
1.537 + template <std::size_t N, typename WordType = unsigned long,
1.538 + typename SizeType = std::size_t>
1.539 + class bitset
1.540 + : public bitset_base<word_traits<WordType>, SizeType,
1.541 + bitset<N, WordType, SizeType> >
1.542 + {
1.543 + typedef bitset self;
1.544 + static const std::size_t word_size = word_traits<WordType>::word_size;
1.545 + public:
1.546 + // 23.3.5.1 constructors:
1.547 + bitset() {
1.548 +#if defined(__GNUC__)
1.549 + for (size_type i = 0; i < num_words(); ++i)
1.550 + m_data[i] = static_cast<WordType>(0);
1.551 +#endif
1.552 + }
1.553 +
1.554 + bitset(unsigned long val) {
1.555 + init_from_ulong(val);
1.556 + }
1.557 +
1.558 + template<class CharT, class Traits, class Alloc>
1.559 + explicit bitset
1.560 + (const basic_string<CharT,Traits,Alloc>& s,
1.561 + std::size_t pos = 0,
1.562 + std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos))
1.563 + {
1.564 + BOOST_ASSERT_THROW
1.565 + (pos < s.size(), std::out_of_range("bitset::bitset(s,pos,n)"));
1.566 + m_copy_from_string(s, pos, n);
1.567 + }
1.568 +
1.569 + size_type size() const { return N; }
1.570 +
1.571 + // protected:
1.572 + size_type num_words() const { return (N + word_size - 1) / word_size; }
1.573 +
1.574 + word_type* data() { return m_data; }
1.575 + const word_type* data() const { return m_data; }
1.576 + protected:
1.577 + word_type m_data[(N + word_size - 1) / word_size];
1.578 + };
1.579 +
1.580 + //=========================================================================
1.581 + struct select_static_bitset {
1.582 + template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
1.583 + struct bind_ {
1.584 + typedef bitset<N, WordT, SizeT> type;
1.585 + };
1.586 + };
1.587 + struct select_dyn_size_bitset {
1.588 + template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
1.589 + struct bind_ {
1.590 + typedef dyn_size_bitset<WordT, SizeT, Alloc> type;
1.591 + };
1.592 + };
1.593 +
1.594 + template <std::size_t N = 0, // 0 means use dynamic
1.595 + typename WordType = unsigned long,
1.596 + typename Size_type = std::size_t,
1.597 + typename Allocator = std::allocator<WordType>
1.598 + >
1.599 + class bitset_generator {
1.600 + typedef typename ct_if<N, select_dyn_size_bitset,
1.601 + select_static_bitset>::type selector;
1.602 + public:
1.603 + typedef typename selector
1.604 + ::template bind_<N, WordType, SizeType, Allocator>::type type;
1.605 + };
1.606 +
1.607 +
1.608 + //=========================================================================
1.609 + // bitset_base non-inline member function implementations
1.610 +
1.611 + template <class WordTraits, class SizeType, class Derived>
1.612 + Derived&
1.613 + bitset_base<WordTraits, SizeType, Derived>::
1.614 + operator<<=(size_type shift)
1.615 + {
1.616 + typedef typename WordTraits::word_type word_type;
1.617 + typedef SizeType size_type;
1.618 + if (shift != 0) {
1.619 + const size_type wshift = shift / WordTraits::word_size;
1.620 + const size_type offset = shift % WordTraits::word_size;
1.621 + const size_type sub_offset = WordTraits::word_size - offset;
1.622 + size_type n = num_words() - 1;
1.623 + for ( ; n > wshift; --n)
1.624 + data()[n] = (data()[n - wshift] << offset) |
1.625 + (data()[n - wshift - 1] >> sub_offset);
1.626 + if (n == wshift)
1.627 + data()[n] = data()[0] << offset;
1.628 + for (size_type n1 = 0; n1 < n; ++n1)
1.629 + data()[n1] = static_cast<word_type>(0);
1.630 + }
1.631 + m_sanitize_highest();
1.632 + return static_cast<Derived&>(*this);
1.633 + } // end operator<<=
1.634 +
1.635 +
1.636 + template <class WordTraits, class SizeType, class Derived>
1.637 + Derived&
1.638 + bitset_base<WordTraits, SizeType, Derived>::
1.639 + operator>>=(size_type shift)
1.640 + {
1.641 + typedef typename WordTraits::word_type word_type;
1.642 + typedef SizeType size_type;
1.643 + if (shift != 0) {
1.644 + const size_type wshift = shift / WordTraits::word_size;
1.645 + const size_type offset = shift % WordTraits::word_size;
1.646 + const size_type sub_offset = WordTraits::word_size - offset;
1.647 + const size_type limit = num_words() - wshift - 1;
1.648 + size_type n = 0;
1.649 + for ( ; n < limit; ++n)
1.650 + data()[n] = (data()[n + wshift] >> offset) |
1.651 + (data()[n + wshift + 1] << sub_offset);
1.652 + data()[limit] = data()[num_words()-1] >> offset;
1.653 + for (size_type n1 = limit + 1; n1 < num_words(); ++n1)
1.654 + data()[n1] = static_cast<word_type>(0);
1.655 + }
1.656 + m_sanitize_highest();
1.657 + return static_cast<Derived&>(*this);
1.658 + } // end operator>>=
1.659 +
1.660 +
1.661 + template <class WordTraits, class SizeType, class Derived>
1.662 + unsigned long bitset_base<WordTraits, SizeType, Derived>::
1.663 + to_ulong() const
1.664 + {
1.665 + typedef typename WordTraits::word_type word_type;
1.666 + typedef SizeType size_type;
1.667 + const std::overflow_error
1.668 + overflow("boost::bit_set::operator unsigned long()");
1.669 +
1.670 + if (sizeof(word_type) >= sizeof(unsigned long)) {
1.671 + for (size_type i = 1; i < num_words(); ++i)
1.672 + BOOST_ASSERT_THROW(! data()[i], overflow);
1.673 +
1.674 + const word_type mask
1.675 + = static_cast<word_type>(static_cast<unsigned long>(-1));
1.676 + BOOST_ASSERT_THROW(! (data()[0] & ~mask), overflow);
1.677 +
1.678 + return static_cast<unsigned long>(data()[0] & mask);
1.679 + }
1.680 + else { // sizeof(word_type) < sizeof(unsigned long).
1.681 + const size_type nwords =
1.682 + (sizeof(unsigned long) + sizeof(word_type) - 1) / sizeof(word_type);
1.683 +
1.684 + size_type min_nwords = nwords;
1.685 + if (num_words() > nwords) {
1.686 + for (size_type i = nwords; i < num_words(); ++i)
1.687 + BOOST_ASSERT_THROW(!data()[i], overflow);
1.688 + }
1.689 + else
1.690 + min_nwords = num_words();
1.691 +
1.692 + // If unsigned long is 8 bytes and word_type is 6 bytes, then
1.693 + // an unsigned long consists of all of one word plus 2 bytes
1.694 + // from another word.
1.695 + const size_type part = sizeof(unsigned long) % sizeof(word_type);
1.696 +
1.697 +#if 0
1.698 + // bug in here?
1.699 + // >> to far?
1.700 + BOOST_ASSERT_THROW((part != 0
1.701 + && nwords <= num_words()
1.702 + && (data()[min_nwords - 1] >>
1.703 + ((sizeof(word_type) - part) * CHAR_BIT)) != 0),
1.704 + overflow);
1.705 +#endif
1.706 +
1.707 + unsigned long result = 0;
1.708 + for (size_type i = 0; i < min_nwords; ++i) {
1.709 + result |= static_cast<unsigned long>(
1.710 + data()[i]) << (i * sizeof(word_type) * CHAR_BIT);
1.711 + }
1.712 + return result;
1.713 + }
1.714 + }// end operator unsigned long()
1.715 +
1.716 +
1.717 + template <class WordTraits, class SizeType, class Derived>
1.718 + SizeType bitset_base<WordTraits,SizeType,Derived>::
1.719 + find_first() const
1.720 + {
1.721 + SizeType not_found = size();
1.722 + for (size_type i = 0; i < num_words(); i++ ) {
1.723 + word_type thisword = data()[i];
1.724 + if ( thisword != static_cast<word_type>(0) ) {
1.725 + // find byte within word
1.726 + for ( std::size_t j = 0; j < sizeof(word_type); j++ ) {
1.727 + unsigned char this_byte
1.728 + = static_cast<unsigned char>(thisword & (~(unsigned char)0));
1.729 + if ( this_byte )
1.730 + return i * WordTraits::word_size + j * CHAR_BIT +
1.731 + first_bit_location<>::value[this_byte];
1.732 +
1.733 + thisword >>= CHAR_BIT;
1.734 + }
1.735 + }
1.736 + }
1.737 + // not found, so return an indication of failure.
1.738 + return not_found;
1.739 + }
1.740 +
1.741 + template <class WordTraits, class SizeType, class Derived>
1.742 + SizeType bitset_base<WordTraits, SizeType, Derived>::
1.743 + bitset_base<WordTraits,SizeType,Derived>::
1.744 + find_next(size_type prev) const
1.745 + {
1.746 + SizeType not_found = size();
1.747 + // make bound inclusive
1.748 + ++prev;
1.749 +
1.750 + // check out of bounds
1.751 + if ( prev >= num_words() * WordTraits::word_size )
1.752 + return not_found;
1.753 +
1.754 + // search first word
1.755 + size_type i = s_which_word(prev);
1.756 + word_type thisword = data()[i];
1.757 +
1.758 + // mask off bits below bound
1.759 + thisword &= (~static_cast<word_type>(0)) << s_which_bit(prev);
1.760 +
1.761 + if ( thisword != static_cast<word_type>(0) ) {
1.762 + // find byte within word
1.763 + // get first byte into place
1.764 + thisword >>= s_which_byte(prev) * CHAR_BIT;
1.765 + for ( size_type j = s_which_byte(prev); j < sizeof(word_type); j++ ) {
1.766 + unsigned char this_byte
1.767 + = static_cast<unsigned char>(thisword & (~(unsigned char)0));
1.768 + if ( this_byte )
1.769 + return i * WordTraits::word_size + j * CHAR_BIT +
1.770 + first_bit_location<>::value[this_byte];
1.771 +
1.772 + thisword >>= CHAR_BIT;
1.773 + }
1.774 + }
1.775 +
1.776 + // check subsequent words
1.777 + i++;
1.778 + for ( ; i < num_words(); i++ ) {
1.779 + word_type thisword = data()[i];
1.780 + if ( thisword != static_cast<word_type>(0) ) {
1.781 + // find byte within word
1.782 + for ( size_type j = 0; j < sizeof(word_type); j++ ) {
1.783 + unsigned char this_byte
1.784 + = static_cast<unsigned char>(thisword & (~(unsigned char)0));
1.785 + if ( this_byte )
1.786 + return i * WordTraits::word_size + j * CHAR_BIT +
1.787 + first_bit_location<>::value[this_byte];
1.788 +
1.789 + thisword >>= CHAR_BIT;
1.790 + }
1.791 + }
1.792 + }
1.793 +
1.794 + // not found, so return an indication of failure.
1.795 + return not_found;
1.796 + } // end find_next
1.797 +
1.798 +
1.799 + template <bool dummy>
1.800 + unsigned char bit_count<dummy>::value[] = {
1.801 + 0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */
1.802 + 2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */
1.803 + 2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */
1.804 + 4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */
1.805 + 2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */
1.806 + 3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */
1.807 + 4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */
1.808 + 3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */
1.809 + 2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */
1.810 + 4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */
1.811 + 3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */
1.812 + 5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */
1.813 + 4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */
1.814 + 2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */
1.815 + 3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */
1.816 + 4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */
1.817 + 2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */
1.818 + 4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */
1.819 + 4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */
1.820 + 6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */
1.821 + 3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */
1.822 + 4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */
1.823 + 5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */
1.824 + 5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */
1.825 + 4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */
1.826 + 6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */
1.827 + 2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */
1.828 + 4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */
1.829 + 3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */
1.830 + 3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */
1.831 + 4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */
1.832 + 5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */
1.833 + 2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */
1.834 + 4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */
1.835 + 4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */
1.836 + 6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */
1.837 + 4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */
1.838 + 5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */
1.839 + 6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */
1.840 + 4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */
1.841 + 3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */
1.842 + 5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */
1.843 + 4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */
1.844 + 6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */
1.845 + 5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */
1.846 + 4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */
1.847 + 5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */
1.848 + 6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */
1.849 + 4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */
1.850 + 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */
1.851 + 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */
1.852 + 8 /* 255 */
1.853 + }; // end _Bit_count
1.854 +
1.855 + template <bool dummy>
1.856 + unsigned char first_bit_location<dummy>::value[] = {
1.857 + 0, /* 0 */ 0, /* 1 */ 1, /* 2 */ 0, /* 3 */ 2, /* 4 */
1.858 + 0, /* 5 */ 1, /* 6 */ 0, /* 7 */ 3, /* 8 */ 0, /* 9 */
1.859 + 1, /* 10 */ 0, /* 11 */ 2, /* 12 */ 0, /* 13 */ 1, /* 14 */
1.860 + 0, /* 15 */ 4, /* 16 */ 0, /* 17 */ 1, /* 18 */ 0, /* 19 */
1.861 + 2, /* 20 */ 0, /* 21 */ 1, /* 22 */ 0, /* 23 */ 3, /* 24 */
1.862 + 0, /* 25 */ 1, /* 26 */ 0, /* 27 */ 2, /* 28 */ 0, /* 29 */
1.863 + 1, /* 30 */ 0, /* 31 */ 5, /* 32 */ 0, /* 33 */ 1, /* 34 */
1.864 + 0, /* 35 */ 2, /* 36 */ 0, /* 37 */ 1, /* 38 */ 0, /* 39 */
1.865 + 3, /* 40 */ 0, /* 41 */ 1, /* 42 */ 0, /* 43 */ 2, /* 44 */
1.866 + 0, /* 45 */ 1, /* 46 */ 0, /* 47 */ 4, /* 48 */ 0, /* 49 */
1.867 + 1, /* 50 */ 0, /* 51 */ 2, /* 52 */ 0, /* 53 */ 1, /* 54 */
1.868 + 0, /* 55 */ 3, /* 56 */ 0, /* 57 */ 1, /* 58 */ 0, /* 59 */
1.869 + 2, /* 60 */ 0, /* 61 */ 1, /* 62 */ 0, /* 63 */ 6, /* 64 */
1.870 + 0, /* 65 */ 1, /* 66 */ 0, /* 67 */ 2, /* 68 */ 0, /* 69 */
1.871 + 1, /* 70 */ 0, /* 71 */ 3, /* 72 */ 0, /* 73 */ 1, /* 74 */
1.872 + 0, /* 75 */ 2, /* 76 */ 0, /* 77 */ 1, /* 78 */ 0, /* 79 */
1.873 + 4, /* 80 */ 0, /* 81 */ 1, /* 82 */ 0, /* 83 */ 2, /* 84 */
1.874 + 0, /* 85 */ 1, /* 86 */ 0, /* 87 */ 3, /* 88 */ 0, /* 89 */
1.875 + 1, /* 90 */ 0, /* 91 */ 2, /* 92 */ 0, /* 93 */ 1, /* 94 */
1.876 + 0, /* 95 */ 5, /* 96 */ 0, /* 97 */ 1, /* 98 */ 0, /* 99 */
1.877 + 2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */
1.878 + 0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */
1.879 + 1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */
1.880 + 0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */
1.881 + 3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */
1.882 + 0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */
1.883 + 1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */
1.884 + 0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */
1.885 + 2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */
1.886 + 0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */
1.887 + 1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */
1.888 + 0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */
1.889 + 5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */
1.890 + 0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */
1.891 + 1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */
1.892 + 0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */
1.893 + 2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */
1.894 + 0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */
1.895 + 1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */
1.896 + 0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */
1.897 + 3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */
1.898 + 0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */
1.899 + 1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */
1.900 + 0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */
1.901 + 2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */
1.902 + 0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */
1.903 + 1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */
1.904 + 0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */
1.905 + 4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */
1.906 + 0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */
1.907 + 1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */
1.908 + 0, /* 255 */
1.909 + }; // end _First_one
1.910 +
1.911 + } // namespace detail
1.912 +
1.913 +} // namespace boost