source: NonGTP/Boost/boost/graph/detail/bitset.hpp @ 857

Revision 857, 33.4 KB checked in by igarcia, 19 years ago (diff)
Line 
1// (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify,
2// sell and distribute this software is granted provided this
3// copyright notice appears in all copies. This software is provided
4// "as is" without express or implied warranty, and with no claim as
5// to its suitability for any purpose.
6
7/*
8 * Copyright (c) 1998
9 * Silicon Graphics Computer Systems, Inc.
10 *
11 * Permission to use, copy, modify, distribute and sell this software
12 * and its documentation for any purpose is hereby granted without fee,
13 * provided that the above copyright notice appear in all copies and
14 * that both that copyright notice and this permission notice appear
15 * in supporting documentation.  Silicon Graphics makes no
16 * representations about the suitability of this software for any
17 * purpose.  It is provided "as is" without express or implied warranty.
18 */
19
20#include <boost/config.hpp>
21#include <memory>
22#include <stdexcept>
23#include <algorithm>
24#include <string>
25#include <boost/config.hpp>
26#include <boost/pending/ct_if.hpp>
27#include <boost/graph/detail/bitset_adaptor.hpp>
28
29// This provides versions of std::bitset with both static and dynamic size.
30
31// UNDER CONSTRUCTION
32
33
34// replace this later
35#include <cassert>
36#define BOOST_ASSERT_THROW(expr, except) assert(expr)
37
38namespace boost {
39
40  namespace detail {
41    // structure to aid in counting bits
42    template<bool dummy = true>
43    struct bit_count {
44      static unsigned char value[256];
45    };
46
47    // Mapping from 8 bit unsigned integers to the index of the first bit
48    template<bool dummy = true>
49    struct first_bit_location {
50      static unsigned char value[256];
51    };
52
53    template <typename WordType>  // this size is in bits
54    struct word_traits {
55      typedef WordType word_type;
56      static const std::size_t word_size = CHAR_BIT * sizeof(word_type);
57    };
58   
59    //=========================================================================
60    template <class WordTraits, class SizeType, class Derived>
61    class bitset_base
62      : public bitset_adaptor< SizeType,
63                               bitset_base<WordTraits, SizeType, Derived> >
64    {
65      //    private:
66    public:
67      typedef SizeType size_type;
68      typedef typename WordTraits::word_type word_type;
69
70      static size_type s_which_word(size_type pos) {
71        return pos / WordTraits::word_size;
72      }
73      static size_type s_which_byte(size_type pos) {
74        return (pos % WordTraits::word_size) / CHAR_BIT;
75      }
76      static size_type s_which_bit(size_type pos) {
77        return pos % WordTraits::word_size;
78      }
79      static word_type s_mask_bit(size_type pos) {
80        return (static_cast<word_type>(1)) << s_which_bit(pos);
81      }
82      word_type& m_get_word(size_type pos) {
83        return data()[s_which_word(pos)];
84      }
85      word_type m_get_word(size_type pos) const {
86        return data()[s_which_word(pos)];
87      }
88      word_type& m_hi_word() { return data()[num_words() - 1]; }
89      word_type  m_hi_word() const { return data()[num_words() - 1]; }
90
91      void m_sanitize_highest() {
92        size_type extra_bits = size() % WordTraits::word_size;
93        if (extra_bits)
94          m_hi_word() &= ~((~static_cast<word_type>(0)) << extra_bits);
95      }
96    public:
97
98      class reference {
99        friend class bitset_base;
100
101        word_type *m_word_ptr;
102        size_type m_bit_pos;
103
104        // left undefined
105        reference();
106
107        reference(bitset_base& b, size_type pos ) {
108          m_word_ptr = &b.m_get_word(pos);
109          m_bit_pos = s_which_bit(pos);
110        }
111
112      public:
113        ~reference() {}
114
115        // for b[i] = x;
116        reference& operator=(bool x) {
117          if ( x )
118            *m_word_ptr |= s_mask_bit(m_bit_pos);
119          else
120            *m_word_ptr &= ~s_mask_bit(m_bit_pos);
121
122          return *this;
123        }
124        // for b[i] = b[j];
125        reference& operator=(const reference& j) {
126          if ( (*(j.m_word_ptr) & s_mask_bit(j.m_bit_pos)) )
127            *m_word_ptr |= s_mask_bit(m_bit_pos);
128          else
129            *m_word_ptr &= ~s_mask_bit(m_bit_pos);
130
131          return *this;
132        }
133        // flips the bit
134        bool operator~() const {
135          return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) == 0;
136        }
137        // for x = b[i];
138        operator bool() const {
139          return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) != 0;
140        }
141        // for b[i].flip();
142        reference& flip() {
143          *m_word_ptr ^= s_mask_bit(m_bit_pos);
144          return *this;
145        }
146      };
147
148      void init_from_ulong(unsigned long val) {
149        reset();
150        const size_type n = (std::min)(sizeof(unsigned long) * CHAR_BIT,
151                                     WordTraits::word_size * num_words());
152        for(size_type i = 0; i < n; ++i, val >>= 1)
153          if ( val & 0x1 )
154            m_get_word(i) |= s_mask_bit(i);
155      }
156     
157      // intersection: this = this & x
158      Derived& operator&=(const Derived& x) {
159        for (size_type i = 0; i < num_words(); ++i)
160          data()[i] &= x.data()[i];
161        return static_cast<Derived&>(*this);
162      }
163      // union: this = this | x
164      Derived& operator|=(const Derived& x) {
165        for (size_type i = 0; i < num_words(); ++i)
166          data()[i] |= x.data()[i];
167        return static_cast<Derived&>(*this);
168      }
169      // exclusive or: this = this ^ x
170      Derived& operator^=(const Derived& x) {
171        for (size_type i = 0; i < num_words(); ++i)
172          data()[i] ^= x.data()[i];
173        return static_cast<Derived&>(*this);
174      }
175      // left shift
176      Derived& operator<<=(size_type pos);
177
178      // right shift
179      Derived& operator>>=(size_type pos);
180
181      Derived& set() {
182        for (size_type i = 0; i < num_words(); ++i)
183          data()[i] = ~static_cast<word_type>(0);
184        m_sanitize_highest();
185        return static_cast<Derived&>(*this);
186      }
187
188      Derived& set(size_type pos, int val = true)
189      {
190        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::set(pos,value)"));
191        if (val)
192          m_get_word(pos) |= s_mask_bit(pos);
193        else
194          m_get_word(pos) &= ~s_mask_bit(pos);
195        return static_cast<Derived&>(*this);
196      }
197     
198      Derived& reset() {
199        for (size_type i = 0; i < num_words(); ++i)
200          data()[i] = 0;
201        return static_cast<Derived&>(*this);
202      }
203
204      Derived& reset(size_type pos) {
205        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::reset(pos)"));
206        m_get_word(pos) &= ~s_mask_bit(pos);
207        return static_cast<Derived&>(*this);
208      }
209
210      // compliment
211      Derived operator~() const {
212        return Derived(static_cast<const Derived&>(*this)).flip();
213      }
214     
215      Derived& flip() {
216        for (size_type i = 0; i < num_words(); ++i)
217          data()[i] = ~data()[i];
218        m_sanitize_highest();
219        return static_cast<Derived&>(*this);
220      }
221      Derived& flip(size_type pos) {
222        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::flip(pos)"));
223        m_get_word(pos) ^= s_mask_bit(pos);
224        return static_cast<Derived&>(*this);
225      }
226
227      // element access
228      reference operator[](size_type pos) { return reference(*this, pos); }
229      bool operator[](size_type pos) const { return test(pos); }
230
231      unsigned long to_ulong() const;
232
233      // to_string
234
235     
236      size_type count() const {
237        size_type result = 0;
238        const unsigned char* byte_ptr = (const unsigned char*)data();
239        const unsigned char* end_ptr =
240          (const unsigned char*)(data() + num_words());
241        while ( byte_ptr < end_ptr ) {
242          result += bit_count<>::value[*byte_ptr];
243          byte_ptr++;
244        }
245        return result;
246      }   
247     
248      // size() must be provided by Derived class
249
250      bool operator==(const Derived& x) const {
251        return std::equal(data(), data() + num_words(), x.data());
252      }
253
254      bool operator!=(const Derived& x) const {
255        return ! this->operator==(x);
256      }
257
258      bool test(size_type pos) const {
259        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::test(pos)"));
260        return (m_get_word(pos) & s_mask_bit(pos))
261          != static_cast<word_type>(0);
262      }
263
264      bool any() const {
265        for (size_type i = 0; i < num_words(); ++i) {
266          if ( data()[i] != static_cast<word_type>(0) )
267            return true;
268        }
269        return false;
270      }
271      bool none() const {
272        return !any();
273      }
274
275      Derived operator<<(size_type pos) const
276        { return Derived(static_cast<const Derived&>(*this)) <<= pos; }
277
278      Derived operator>>(size_type pos) const
279        { return Derived(static_cast<const Derived&>(*this)) >>= pos; }
280
281      template <class CharT, class Traits, class Alloc>
282      void m_copy_from_string(const basic_string<CharT,Traits,Alloc>& s,
283                              size_type pos, size_type n)
284      {
285        reset();
286        const size_type nbits = (std::min)(size(), (std::min)(n, s.size() - pos));
287        for (size_type i = 0; i < nbits; ++i) {
288          switch(s[pos + nbits - i - 1]) {
289          case '0':
290            break;
291          case '1':
292            this->set(i);
293            break;
294          default:
295            throw std::invalid_argument
296              ("boost::bitset_base::m_copy_from_string(s, pos, n)");
297          }
298        }
299      }
300
301      template <class CharT, class Traits, class Alloc>
302      void m_copy_to_string(basic_string<CharT, Traits, Alloc>& s) const
303      {
304        s.assign(size(), '0');
305       
306        for (size_type i = 0; i < size(); ++i)
307          if (test(i))
308            s[size() - 1 - i] = '1';
309      }
310
311      //-----------------------------------------------------------------------
312      // Stuff not in std::bitset
313
314      // difference:  this = this - x
315      Derived& operator-=(const Derived& x) {
316        for (size_type i = 0; i < num_words(); ++i)
317          data()[i] &= ~x.data()[i];
318        return static_cast<Derived&>(*this);
319      }
320
321      // this wasn't working, why?
322      int compare_3way(const Derived& x) const {
323        return std::lexicographical_compare_3way
324          (data(), data() + num_words(), x.data(), x.data() + x.num_words());
325      }
326
327      // less-than compare
328      bool operator<(const Derived& x) const {
329        return std::lexicographical_compare
330          (data(), data() + num_words(), x.data(), x.data() + x.num_words());
331      }
332
333      // find the index of the first "on" bit
334      size_type find_first() const;
335
336      // find the index of the next "on" bit after prev
337      size_type find_next(size_type prev) const;
338
339     
340      size_type _Find_first() const { return find_first(); }
341
342      // find the index of the next "on" bit after prev
343      size_type _Find_next(size_type prev) const { return find_next(prev); }
344
345      //    private:
346      word_type* data()
347        { return static_cast<Derived*>(this)->data(); }
348
349      const word_type* data() const
350        { return static_cast<const Derived*>(this)->data(); }
351
352      size_type num_words() const
353        { return static_cast<const Derived*>(this)->num_words(); }
354
355      size_type size() const
356        { return static_cast<const Derived*>(this)->size(); }
357    };
358
359    // 23.3.5.3 bitset operations:
360    template <class W, class S, class D>
361    inline D operator&(const bitset_base<W,S,D>& x,
362                       const bitset_base<W,S,D>& y) {
363      D result(static_cast<const D&>(x));
364      result &= static_cast<const D&>(y);
365      return result;
366    }
367
368    template <class W, class S, class D>
369    inline D operator|(const bitset_base<W,S,D>& x,
370                       const bitset_base<W,S,D>& y) {
371      D result(static_cast<const D&>(x));
372      result |= static_cast<const D&>(y);
373      return result;
374    }
375
376    template <class W, class S, class D>
377    inline D operator^(const bitset_base<W,S,D>& x,
378                       const bitset_base<W,S,D>& y) {
379      D result(static_cast<const D&>(x));
380      result ^= static_cast<const D&>(y);
381      return result;
382    }
383
384    // this one is an extension
385    template <class W, class S, class D>
386    inline D operator-(const bitset_base<W,S,D>& x,
387                       const bitset_base<W,S,D>& y) {
388      D result(static_cast<const D&>(x));
389      result -= static_cast<const D&>(y);
390      return result;
391    }
392
393    template <class W, class S, class D>
394    inline int compare_3way(const bitset_base<W,S,D>& x,
395                            const bitset_base<W,S,D>& y) {
396      return std::lexicographical_compare_3way
397        (x.data(), x.data() + x.num_words(),
398         y.data(), y.data() + y.num_words());
399    }
400
401
402    template <class W, class S, class D>
403    std::istream&
404    operator>>(std::istream& is, bitset_base<W,S,D>& x) {
405      std::string tmp;
406      tmp.reserve(x.size());
407
408      // In new templatized iostreams, use istream::sentry
409      if (is.flags() & ios::skipws) {
410        char c;
411        do
412          is.get(c);
413        while (is && isspace(c));
414        if (is)
415          is.putback(c);
416      }
417
418      for (S i = 0; i < x.size(); ++i) {
419        char c;
420        is.get(c);
421
422        if (!is)
423          break;
424        else if (c != '0' && c != '1') {
425          is.putback(c);
426          break;
427        }
428        else
429          //      tmp.push_back(c);
430          tmp += c;
431      }
432
433      if (tmp.empty())
434        is.clear(is.rdstate() | ios::failbit);
435      else
436        x.m_copy_from_string(tmp, static_cast<S>(0), x.size());
437
438      return is;
439    }
440
441    template <class W, class S, class D>
442    std::ostream& operator<<(std::ostream& os,
443                             const bitset_base<W,S,D>& x) {
444      std::string tmp;
445      x.m_copy_to_string(tmp);
446      return os << tmp;
447    }
448
449    //=========================================================================
450    template <typename WordType = unsigned long,
451              typename SizeType = std::size_t,
452              typename Allocator = std::allocator<WordType>
453             >
454    class dyn_size_bitset
455      : public bitset_base<word_traits<WordType>, SizeType,
456          dyn_size_bitset<WordType,SizeType,Allocator> >
457    {
458      typedef dyn_size_bitset self;
459    public:
460      typedef SizeType size_type;
461    private:
462      typedef word_traits<WordType> WordTraits;
463      static const size_type word_size = WordTraits::word_size;
464
465    public:
466      dyn_size_bitset(unsigned long val,
467                      size_type n,
468                      const Allocator& alloc = Allocator())
469        : m_data(alloc.allocate((n + word_size - 1) / word_size)),
470          m_size(n),
471          m_num_words((n + word_size - 1) / word_size),
472          m_alloc(alloc)
473      {
474        init_from_ulong(val);
475      }
476
477      dyn_size_bitset(size_type n,  // size of the set's "universe"
478                      const Allocator& alloc = Allocator())
479        : m_data(alloc.allocate((n + word_size - 1) / word_size)),
480          m_size(n), m_num_words((n + word_size - 1) / word_size),
481          m_alloc(alloc)
482      { }
483
484      template<class CharT, class Traits, class Alloc>
485      explicit dyn_size_bitset
486        (const basic_string<CharT,Traits,Alloc>& s,
487         std::size_t pos = 0,
488         std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos),
489         const Allocator& alloc = Allocator())
490        : m_data(alloc.allocate((n + word_size - 1) / word_size)),
491          m_size(n), m_num_words((n + word_size - 1) / word_size),
492          m_alloc(alloc)
493      {
494        BOOST_ASSERT_THROW(pos < s.size(), std::out_of_range("dyn_size_bitset::dyn_size_bitset(s,pos,n,alloc)"));
495        m_copy_from_string(s, pos, n);
496      }
497
498      template <typename InputIterator>
499      explicit dyn_size_bitset
500        (InputIterator first, InputIterator last,
501         size_type n,  // size of the set's "universe"
502         const Allocator& alloc = Allocator())
503        : m_data(alloc.allocate((n + word_size - 1) / word_size)),
504          m_size(N), m_num_words((n + word_size - 1) / word_size),
505          m_alloc(alloc)
506      {
507        while (first != last)
508          this->set(*first++);
509      }
510
511      ~dyn_size_bitset() {
512        m_alloc.deallocate(m_data, m_num_words);
513      }
514     
515      size_type size() const { return m_size; }
516
517      // protected:
518      size_type num_words() const { return m_num_words; }
519
520      word_type* data() { return m_data; }
521      const word_type* data() const { return m_data; }
522
523    protected:
524      word_type* m_data;
525      SizeType m_size;
526      SizeType m_num_words;
527      Allocator m_alloc;
528    };
529
530    //=========================================================================
531    template <std::size_t N, typename WordType = unsigned long,
532      typename SizeType = std::size_t>
533    class bitset
534      : public bitset_base<word_traits<WordType>, SizeType,
535          bitset<N, WordType, SizeType> >
536    {
537      typedef bitset self;
538      static const std::size_t word_size = word_traits<WordType>::word_size;
539    public:
540        // 23.3.5.1 constructors:
541      bitset() {
542#if defined(__GNUC__)
543        for (size_type i = 0; i < num_words(); ++i)
544          m_data[i] = static_cast<WordType>(0);
545#endif
546      }
547
548      bitset(unsigned long val) {
549        init_from_ulong(val);
550      }
551
552      template<class CharT, class Traits, class Alloc>
553      explicit bitset
554        (const basic_string<CharT,Traits,Alloc>& s,
555         std::size_t pos = 0,
556         std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos))
557      {
558        BOOST_ASSERT_THROW
559          (pos < s.size(), std::out_of_range("bitset::bitset(s,pos,n)"));
560        m_copy_from_string(s, pos, n);
561      }
562
563      size_type size() const { return N; }
564
565      // protected:
566      size_type num_words() const { return (N + word_size - 1) / word_size; }
567
568      word_type* data() { return m_data; }
569      const word_type* data() const { return m_data; }
570    protected:
571      word_type m_data[(N + word_size - 1) / word_size];
572    };
573
574    //=========================================================================
575    struct select_static_bitset {
576      template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
577      struct bind_ {
578        typedef bitset<N, WordT, SizeT> type;
579      };
580    };
581    struct select_dyn_size_bitset {
582      template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
583      struct bind_ {
584        typedef dyn_size_bitset<WordT, SizeT, Alloc> type;
585      };
586    };
587
588    template <std::size_t N = 0, // 0 means use dynamic
589      typename WordType = unsigned long,
590      typename Size_type = std::size_t,
591      typename Allocator = std::allocator<WordType>
592             >
593    class bitset_generator {
594      typedef typename ct_if<N, select_dyn_size_bitset,
595        select_static_bitset>::type selector;
596    public:
597      typedef typename selector
598        ::template bind_<N, WordType, SizeType, Allocator>::type type;
599    };
600
601
602    //=========================================================================
603    // bitset_base non-inline member function implementations
604
605    template <class WordTraits, class SizeType, class Derived>
606    Derived&
607    bitset_base<WordTraits, SizeType, Derived>::
608    operator<<=(size_type shift)
609    {
610      typedef typename WordTraits::word_type word_type;
611      typedef SizeType size_type;
612      if (shift != 0) {
613        const size_type wshift = shift / WordTraits::word_size;
614        const size_type offset = shift % WordTraits::word_size;
615        const size_type sub_offset = WordTraits::word_size - offset;
616        size_type n = num_words() - 1;
617        for ( ; n > wshift; --n)
618          data()[n] = (data()[n - wshift] << offset) |
619            (data()[n - wshift - 1] >> sub_offset);
620        if (n == wshift)
621          data()[n] = data()[0] << offset;
622        for (size_type n1 = 0; n1 < n; ++n1)
623          data()[n1] = static_cast<word_type>(0);
624      }
625      m_sanitize_highest();
626      return static_cast<Derived&>(*this);
627    } // end operator<<=
628
629
630    template <class WordTraits, class SizeType, class Derived>
631    Derived&
632    bitset_base<WordTraits, SizeType, Derived>::
633    operator>>=(size_type shift)
634    {
635      typedef typename WordTraits::word_type word_type;
636      typedef SizeType size_type;
637      if (shift != 0) {
638        const size_type wshift = shift / WordTraits::word_size;
639        const size_type offset = shift % WordTraits::word_size;
640        const size_type sub_offset = WordTraits::word_size - offset;
641        const size_type limit = num_words() - wshift - 1;
642        size_type n = 0;
643        for ( ; n < limit; ++n)
644          data()[n] = (data()[n + wshift] >> offset) |
645            (data()[n + wshift + 1] << sub_offset);
646        data()[limit] = data()[num_words()-1] >> offset;
647        for (size_type n1 = limit + 1; n1 < num_words(); ++n1)
648          data()[n1] = static_cast<word_type>(0);
649      }
650      m_sanitize_highest();
651      return static_cast<Derived&>(*this);
652    } // end operator>>=
653
654
655    template <class WordTraits, class SizeType, class Derived>
656    unsigned long bitset_base<WordTraits, SizeType, Derived>::
657    to_ulong() const
658    {
659      typedef typename WordTraits::word_type word_type;
660      typedef SizeType size_type;
661      const std::overflow_error
662        overflow("boost::bit_set::operator unsigned long()");
663
664      if (sizeof(word_type) >= sizeof(unsigned long)) {
665        for (size_type i = 1; i < num_words(); ++i)
666          BOOST_ASSERT_THROW(! data()[i], overflow);
667       
668        const word_type mask
669          = static_cast<word_type>(static_cast<unsigned long>(-1));
670        BOOST_ASSERT_THROW(! (data()[0] & ~mask), overflow);
671       
672        return static_cast<unsigned long>(data()[0] & mask);
673      }
674      else { // sizeof(word_type) < sizeof(unsigned long).
675        const size_type nwords =
676          (sizeof(unsigned long) + sizeof(word_type) - 1) / sizeof(word_type);
677
678        size_type min_nwords = nwords;
679        if (num_words() > nwords) {
680          for (size_type i = nwords; i < num_words(); ++i)
681            BOOST_ASSERT_THROW(!data()[i], overflow);
682        }
683        else
684          min_nwords = num_words();
685
686        // If unsigned long is 8 bytes and word_type is 6 bytes, then
687        // an unsigned long consists of all of one word plus 2 bytes
688        // from another word.
689        const size_type part = sizeof(unsigned long) % sizeof(word_type);
690
691#if 0
692        // bug in here?
693        // >> to far?
694        BOOST_ASSERT_THROW((part != 0
695                            && nwords <= num_words()
696                            && (data()[min_nwords - 1] >>
697                                ((sizeof(word_type) - part) * CHAR_BIT)) != 0),
698                           overflow);
699#endif
700
701        unsigned long result = 0;
702        for (size_type i = 0; i < min_nwords; ++i) {
703          result |= static_cast<unsigned long>(
704             data()[i]) << (i * sizeof(word_type) * CHAR_BIT);
705        }
706        return result;
707      }
708    }// end operator unsigned long()
709
710
711    template <class WordTraits, class SizeType, class Derived>
712    SizeType bitset_base<WordTraits,SizeType,Derived>::
713    find_first() const
714    {
715      SizeType not_found = size();
716      for (size_type i = 0; i < num_words(); i++ ) {
717        word_type thisword = data()[i];
718        if ( thisword != static_cast<word_type>(0) ) {
719          // find byte within word
720          for ( std::size_t j = 0; j < sizeof(word_type); j++ ) {
721            unsigned char this_byte
722              = static_cast<unsigned char>(thisword & (~(unsigned char)0));
723            if ( this_byte )
724              return i * WordTraits::word_size + j * CHAR_BIT +
725                first_bit_location<>::value[this_byte];
726
727            thisword >>= CHAR_BIT;
728          }
729        }
730      }
731      // not found, so return an indication of failure.
732      return not_found;
733    }
734
735    template <class WordTraits, class SizeType, class Derived>
736    SizeType bitset_base<WordTraits, SizeType, Derived>::
737    bitset_base<WordTraits,SizeType,Derived>::
738    find_next(size_type prev) const
739    {
740      SizeType not_found = size();
741      // make bound inclusive
742      ++prev;
743
744      // check out of bounds
745      if ( prev >= num_words() * WordTraits::word_size )
746        return not_found;
747
748        // search first word
749      size_type i = s_which_word(prev);
750      word_type thisword = data()[i];
751
752        // mask off bits below bound
753      thisword &= (~static_cast<word_type>(0)) << s_which_bit(prev);
754
755      if ( thisword != static_cast<word_type>(0) ) {
756        // find byte within word
757        // get first byte into place
758        thisword >>= s_which_byte(prev) * CHAR_BIT;
759        for ( size_type j = s_which_byte(prev); j < sizeof(word_type); j++ ) {
760          unsigned char this_byte
761            = static_cast<unsigned char>(thisword & (~(unsigned char)0));
762          if ( this_byte )
763            return i * WordTraits::word_size + j * CHAR_BIT +
764              first_bit_location<>::value[this_byte];
765
766          thisword >>= CHAR_BIT;
767        }
768      }
769
770      // check subsequent words
771      i++;
772      for ( ; i < num_words(); i++ ) {
773        word_type thisword = data()[i];
774        if ( thisword != static_cast<word_type>(0) ) {
775          // find byte within word
776          for ( size_type j = 0; j < sizeof(word_type); j++ ) {
777            unsigned char this_byte
778              = static_cast<unsigned char>(thisword & (~(unsigned char)0));
779            if ( this_byte )
780              return i * WordTraits::word_size + j * CHAR_BIT +
781                first_bit_location<>::value[this_byte];
782
783            thisword >>= CHAR_BIT;
784          }
785        }
786      }
787
788      // not found, so return an indication of failure.
789      return not_found;
790    } // end find_next
791
792
793    template <bool dummy>
794    unsigned char bit_count<dummy>::value[] = {
795      0, /*   0 */ 1, /*   1 */ 1, /*   2 */ 2, /*   3 */ 1, /*   4 */
796      2, /*   5 */ 2, /*   6 */ 3, /*   7 */ 1, /*   8 */ 2, /*   9 */
797      2, /*  10 */ 3, /*  11 */ 2, /*  12 */ 3, /*  13 */ 3, /*  14 */
798      4, /*  15 */ 1, /*  16 */ 2, /*  17 */ 2, /*  18 */ 3, /*  19 */
799      2, /*  20 */ 3, /*  21 */ 3, /*  22 */ 4, /*  23 */ 2, /*  24 */
800      3, /*  25 */ 3, /*  26 */ 4, /*  27 */ 3, /*  28 */ 4, /*  29 */
801      4, /*  30 */ 5, /*  31 */ 1, /*  32 */ 2, /*  33 */ 2, /*  34 */
802      3, /*  35 */ 2, /*  36 */ 3, /*  37 */ 3, /*  38 */ 4, /*  39 */
803      2, /*  40 */ 3, /*  41 */ 3, /*  42 */ 4, /*  43 */ 3, /*  44 */
804      4, /*  45 */ 4, /*  46 */ 5, /*  47 */ 2, /*  48 */ 3, /*  49 */
805      3, /*  50 */ 4, /*  51 */ 3, /*  52 */ 4, /*  53 */ 4, /*  54 */
806      5, /*  55 */ 3, /*  56 */ 4, /*  57 */ 4, /*  58 */ 5, /*  59 */
807      4, /*  60 */ 5, /*  61 */ 5, /*  62 */ 6, /*  63 */ 1, /*  64 */
808      2, /*  65 */ 2, /*  66 */ 3, /*  67 */ 2, /*  68 */ 3, /*  69 */
809      3, /*  70 */ 4, /*  71 */ 2, /*  72 */ 3, /*  73 */ 3, /*  74 */
810      4, /*  75 */ 3, /*  76 */ 4, /*  77 */ 4, /*  78 */ 5, /*  79 */
811      2, /*  80 */ 3, /*  81 */ 3, /*  82 */ 4, /*  83 */ 3, /*  84 */
812      4, /*  85 */ 4, /*  86 */ 5, /*  87 */ 3, /*  88 */ 4, /*  89 */
813      4, /*  90 */ 5, /*  91 */ 4, /*  92 */ 5, /*  93 */ 5, /*  94 */
814      6, /*  95 */ 2, /*  96 */ 3, /*  97 */ 3, /*  98 */ 4, /*  99 */
815      3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */
816      4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */
817      5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */
818      5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */
819      4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */
820      6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */
821      2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */
822      4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */
823      3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */
824      3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */
825      4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */
826      5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */
827      2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */
828      4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */
829      4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */
830      6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */
831      4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */
832      5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */
833      6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */
834      4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */
835      3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */
836      5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */
837      4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */
838      6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */
839      5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */
840      4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */
841      5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */
842      6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */
843      4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */
844      6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */
845      6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */
846      8  /* 255 */
847    }; // end _Bit_count
848
849    template <bool dummy>
850    unsigned char first_bit_location<dummy>::value[] = {
851      0, /*   0 */ 0, /*   1 */ 1, /*   2 */ 0, /*   3 */ 2, /*   4 */
852      0, /*   5 */ 1, /*   6 */ 0, /*   7 */ 3, /*   8 */ 0, /*   9 */
853      1, /*  10 */ 0, /*  11 */ 2, /*  12 */ 0, /*  13 */ 1, /*  14 */
854      0, /*  15 */ 4, /*  16 */ 0, /*  17 */ 1, /*  18 */ 0, /*  19 */
855      2, /*  20 */ 0, /*  21 */ 1, /*  22 */ 0, /*  23 */ 3, /*  24 */
856      0, /*  25 */ 1, /*  26 */ 0, /*  27 */ 2, /*  28 */ 0, /*  29 */
857      1, /*  30 */ 0, /*  31 */ 5, /*  32 */ 0, /*  33 */ 1, /*  34 */
858      0, /*  35 */ 2, /*  36 */ 0, /*  37 */ 1, /*  38 */ 0, /*  39 */
859      3, /*  40 */ 0, /*  41 */ 1, /*  42 */ 0, /*  43 */ 2, /*  44 */
860      0, /*  45 */ 1, /*  46 */ 0, /*  47 */ 4, /*  48 */ 0, /*  49 */
861      1, /*  50 */ 0, /*  51 */ 2, /*  52 */ 0, /*  53 */ 1, /*  54 */
862      0, /*  55 */ 3, /*  56 */ 0, /*  57 */ 1, /*  58 */ 0, /*  59 */
863      2, /*  60 */ 0, /*  61 */ 1, /*  62 */ 0, /*  63 */ 6, /*  64 */
864      0, /*  65 */ 1, /*  66 */ 0, /*  67 */ 2, /*  68 */ 0, /*  69 */
865      1, /*  70 */ 0, /*  71 */ 3, /*  72 */ 0, /*  73 */ 1, /*  74 */
866      0, /*  75 */ 2, /*  76 */ 0, /*  77 */ 1, /*  78 */ 0, /*  79 */
867      4, /*  80 */ 0, /*  81 */ 1, /*  82 */ 0, /*  83 */ 2, /*  84 */
868      0, /*  85 */ 1, /*  86 */ 0, /*  87 */ 3, /*  88 */ 0, /*  89 */
869      1, /*  90 */ 0, /*  91 */ 2, /*  92 */ 0, /*  93 */ 1, /*  94 */
870      0, /*  95 */ 5, /*  96 */ 0, /*  97 */ 1, /*  98 */ 0, /*  99 */
871      2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */
872      0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */
873      1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */
874      0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */
875      3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */
876      0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */
877      1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */
878      0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */
879      2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */
880      0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */
881      1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */
882      0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */
883      5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */
884      0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */
885      1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */
886      0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */
887      2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */
888      0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */
889      1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */
890      0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */
891      3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */
892      0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */
893      1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */
894      0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */
895      2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */
896      0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */
897      1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */
898      0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */
899      4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */
900      0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */
901      1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */
902      0, /* 255 */
903    }; // end _First_one
904
905  } // namespace detail
906
907} // namespace boost
Note: See TracBrowser for help on using the repository browser.