libstdc++/stl/bvector.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 // vector<bool> is replaced by bit_vector at present because partial
  28 // specialization is not yet implemented.
  29
  30 #ifndef __SGI_STL_BVECTOR_H
  31 #define __SGI_STL_BVECTOR_H
  32
  33 #include <stddef.h>
  34 #include <algobase.h>
  35 #include <alloc.h>
  36
  37
  38 #define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int)))
  39
  40 class bit_vector {
  41 public:
  42     typedef bool value_type;
  43     typedef size_t size_type;
  44     typedef ptrdiff_t difference_type;
  45
  46     class iterator;
  47     class const_iterator;
  48
  49     class reference {
  50       friend class iterator;
  51       friend class const_iterator;
  52     protected:
  53         unsigned int* p;
  54         unsigned int mask;
  55         reference(unsigned int* x, unsigned int y) : p(x), mask(y) {}
  56     public:
  57         reference() : p(0), mask(0) {}
  58         operator bool() const { return !(!(*p & mask)); }
  59         reference& operator=(bool x) {
  60             if (x)
  61                 *p |= mask;
  62             else
  63                 *p &= ~mask;
  64             return *this;
  65         }
  66         reference& operator=(const reference& x) { return *this = bool(x); }
  67         bool operator==(const reference& x) const {
  68             return bool(*this) == bool(x);
  69         }
  70         bool operator<(const reference& x) const {
  71             return bool(*this) < bool(x);
  72         }
  73         void flip() { *p ^= mask; }
  74     };
  75
  76     typedef bool const_reference;
  77
  78     typedef reference bit_reference;
  79     typedef const_reference bit_const_reference;
  80
  81     class iterator : public random_access_iterator<bool, difference_type> {
  82       friend class bit_vector;
  83       friend class const_iterator;
  84     public:
  85       typedef bit_reference reference;
  86     protected:
  87         unsigned int* p;
  88         unsigned int offset;
  89         void bump_up() {
  90             if (offset++ == __WORD_BIT - 1) {
  91                 offset = 0;
  92                 ++p;
  93             }
  94         }
  95     void bump_down() {
  96         if (offset-- == 0) {
  97             offset = __WORD_BIT - 1;
  98             --p;
  99         }
 100     }
 101     public:
 102         iterator() : p(0), offset(0) {}
 103         iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
 104         reference operator*() const { return reference(p, 1U << offset); }
 105         iterator& operator++() {
 106             bump_up();
 107             return *this;
 108         }
 109         iterator operator++(int) {
 110             iterator tmp = *this;
 111             bump_up();
 112             return tmp;
 113         }
 114         iterator& operator--() {
 115             bump_down();
 116             return *this;
 117         }
 118         iterator operator--(int) {
 119             iterator tmp = *this;
 120             bump_down();
 121             return tmp;
 122         }
 123         iterator& operator+=(difference_type i) {
 124             difference_type n = i + offset;
 125             p += n / __WORD_BIT;
 126             n = n % __WORD_BIT;
 127             if (n < 0) {
 128                 offset = n + __WORD_BIT;
 129                 --p;
 130             } else
 131                 offset = n;
 132             return *this;
 133         }
 134         iterator& operator-=(difference_type i) {
 135             *this += -i;
 136             return *this;
 137         }
 138         iterator operator+(difference_type i) const {
 139             iterator tmp = *this;
 140             return tmp += i;
 141         }
 142         iterator operator-(difference_type i) const {
 143             iterator tmp = *this;
 144             return tmp -= i;
 145         }
 146         difference_type operator-(iterator x) const {
 147             return __WORD_BIT * (p - x.p) + offset - x.offset;
 148         }
 149         reference operator[](difference_type i) { return *(*this + i); }
 150         bool operator==(const iterator& x) const {
 151             return p == x.p && offset == x.offset;
 152         }
 153         bool operator!=(const iterator& x) const {
 154             return p != x.p || offset != x.offset;
 155         }
 156         bool operator<(iterator x) const {
 157             return p < x.p || (p == x.p && offset < x.offset);
 158         }
 159     };
 160
 161     class const_iterator : public random_access_iterator<bool, difference_type>
 162     {
 163       friend class bit_vector;
 164     public:
 165       typedef bit_const_reference reference;
 166     protected:
 167         unsigned int* p;
 168         unsigned int offset;
 169         void bump_up() {
 170             if (offset++ == __WORD_BIT - 1) {
 171                 offset = 0;
 172                 ++p;
 173             }
 174         }
 175     void bump_down() {
 176         if (offset-- == 0) {
 177             offset = __WORD_BIT - 1;
 178             --p;
 179         }
 180     }
 181     public:
 182         const_iterator() : p(0), offset(0) {}
 183         const_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
 184         const_iterator(const iterator& x) : p(x.p), offset(x.offset) {}
 185         const_reference operator*() const {
 186             return bit_vector::reference(p, 1U << offset);
 187         }
 188         const_iterator& operator++() {
 189             bump_up();
 190             return *this;
 191         }
 192         const_iterator operator++(int) {
 193             const_iterator tmp = *this;
 194             bump_up();
 195             return tmp;
 196         }
 197         const_iterator& operator--() {
 198             bump_down();
 199             return *this;
 200         }
 201         const_iterator operator--(int) {
 202             const_iterator tmp = *this;
 203             bump_down();
 204             return tmp;
 205         }
 206         const_iterator& operator+=(difference_type i) {
 207             difference_type n = i + offset;
 208             p += n / __WORD_BIT;
 209             n = n % __WORD_BIT;
 210             if (n < 0) {
 211                 offset = n + __WORD_BIT;
 212                 --p;
 213             } else
 214                 offset = n;
 215             return *this;
 216         }
 217         const_iterator& operator-=(difference_type i) {
 218             *this += -i;
 219             return *this;
 220         }
 221         const_iterator operator+(difference_type i) const {
 222             const_iterator tmp = *this;
 223             return tmp += i;
 224         }
 225         const_iterator operator-(difference_type i) const {
 226             const_iterator tmp = *this;
 227             return tmp -= i;
 228         }
 229         difference_type operator-(const_iterator x) const {
 230             return __WORD_BIT * (p - x.p) + offset - x.offset;
 231         }
 232         const_reference operator[](difference_type i) {
 233             return *(*this + i);
 234         }
 235         bool operator==(const const_iterator& x) const {
 236             return p == x.p && offset == x.offset;
 237         }
 238         bool operator!=(const const_iterator& x) const {
 239             return p != x.p || offset != x.offset;
 240         }
 241         bool operator<(const_iterator x) const {
 242             return p < x.p || (p == x.p && offset < x.offset);
 243         }
 244     };
 245
 246     typedef reverse_iterator<const_iterator, value_type, const_reference,
 247                              difference_type> const_reverse_iterator;
 248     typedef reverse_iterator<iterator, value_type, reference, difference_type>
 249         reverse_iterator;
 250
 251 protected:
 252     typedef simple_alloc<unsigned int, alloc> data_allocator;
 253     iterator start;
 254     iterator finish;
 255     unsigned int* end_of_storage;
 256     unsigned int* bit_alloc(size_type n) {
 257         return data_allocator::allocate((n + __WORD_BIT - 1)/__WORD_BIT);
 258     }
 259     void deallocate() {
 260       if (start.p)
 261         data_allocator::deallocate(start.p, end_of_storage - start.p);
 262     }
 263     void initialize(size_type n) {
 264         unsigned int* q = bit_alloc(n);
 265         end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
 266         start = iterator(q, 0);
 267         finish = start + n;
 268     }
 269     void insert_aux(iterator position, bool x) {
 270       if (finish.p != end_of_storage) {
 271         copy_backward(position, finish, finish + 1);
 272         *position = x;
 273         ++finish;
 274       } else {
 275         size_type len = size() ? 2 * size() : __WORD_BIT;
 276         unsigned int* q = bit_alloc(len);
 277         iterator i = copy(begin(), position, iterator(q, 0));
 278         *i++ = x;
 279         finish = copy(position, end(), i);
 280         deallocate();
 281         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
 282         start = iterator(q, 0);
 283       }
 284     }
 285
 286 #ifdef __STL_MEMBER_TEMPLATES
 287     template <class InputIterator>
 288     void initialize_range(InputIterator first, InputIterator last,
 289                           input_iterator_tag) {
 290       start = iterator();
 291       finish = iterator();
 292       end_of_storage = 0;
 293       for ( ; first != last; ++first)
 294         push_back(*first);
 295     }
 296
 297     template <class ForwardIterator>
 298     void initialize_range(ForwardIterator first, ForwardIterator last,
 299                           forward_iterator_tag) {
 300       size_type n = 0;
 301       distance(first, last, n);
 302       initialize(n);
 303       copy(first, last, start);
 304     }
 305
 306     template <class BidirectionalIterator>
 307     void initialize_range(BidirectionalIterator first,
 308                           BidirectionalIterator last,
 309                           bidirectional_iterator_tag) {
 310       initialize_range(first, last, forward_iterator_tag());
 311     }
 312
 313     template <class RandomAccessIterator>
 314     void initialize_range(RandomAccessIterator first,
 315                           RandomAccessIterator last,
 316                           random_access_iterator_tag) {
 317       initialize_range(first, last, forward_iterator_tag());
 318     }
 319
 320     template <class InputIterator>
 321     void insert_range(iterator pos,
 322                       InputIterator first, InputIterator last,
 323                       input_iterator_tag) {
 324       for ( ; first != last; ++first) {
 325         pos = insert(pos, *first);
 326         ++pos;
 327       }
 328     }
 329
 330     template <class ForwardIterator>
 331     void insert_range(iterator position,
 332                       ForwardIterator first, ForwardIterator last,
 333                       forward_iterator_tag) {
 334       if (first != last) {
 335         size_type n = 0;
 336         distance(first, last, n);
 337         if (capacity() - size() >= n) {
 338           copy_backward(position, end(), finish + n);
 339           copy(first, last, position);
 340           finish += n;
 341         }
 342         else {
 343           size_type len = size() + max(size(), n);
 344           unsigned int* q = bit_alloc(len);
 345           iterator i = copy(begin(), position, iterator(q, 0));
 346           i = copy(first, last, i);
 347           finish = copy(position, end(), i);
 348           deallocate();
 349           end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
 350           start = iterator(q, 0);
 351         }
 352       }
 353     }
 354
 355     template <class BidirectionalIterator>
 356     void insert_range(iterator pos,
 357                       BidirectionalIterator first, BidirectionalIterator last,
 358                       bidirectional_iterator_tag) {
 359       insert_range(pos, first, last, forward_iterator_tag());
 360     }
 361
 362     template <class RandomAccessIterator>
 363     void insert_range(iterator pos,
 364                       RandomAccessIterator first, RandomAccessIterator last,
 365                       random_access_iterator_tag) {
 366       insert_range(pos, first, last, forward_iterator_tag());
 367     }
 368
 369 #endif /* __STL_MEMBER_TEMPLATES */
 370
 371     typedef bit_vector self;
 372 public:
 373     iterator begin() { return start; }
 374     const_iterator begin() const { return start; }
 375     iterator end() { return finish; }
 376     const_iterator end() const { return finish; }
 377
 378     reverse_iterator rbegin() { return reverse_iterator(end()); }
 379     const_reverse_iterator rbegin() const {
 380         return const_reverse_iterator(end());
 381     }
 382     reverse_iterator rend() { return reverse_iterator(begin()); }
 383     const_reverse_iterator rend() const {
 384         return const_reverse_iterator(begin());
 385     }
 386
 387     size_type size() const { return size_type(end() - begin()); }
 388     size_type max_size() const { return size_type(-1); }
 389     size_type capacity() const {
 390         return size_type(const_iterator(end_of_storage, 0) - begin());
 391     }
 392     bool empty() const { return begin() == end(); }
 393     reference operator[](size_type n) { return *(begin() + n); }
 394     const_reference operator[](size_type n) const { return *(begin() + n); }
 395     bit_vector() : start(iterator()), finish(iterator()), end_of_storage(0) {}
 396     bit_vector(size_type n, bool value) {
 397         initialize(n);
 398         fill(start.p, end_of_storage, value ? ~0 : 0);
 399     }
 400     bit_vector(int n, bool value) {
 401         initialize(n);
 402         fill(start.p, end_of_storage, value ? ~0 : 0);
 403     }
 404     bit_vector(long n, bool value) {
 405         initialize(n);
 406         fill(start.p, end_of_storage, value ? ~0 : 0);
 407     }
 408     explicit bit_vector(size_type n) {
 409         initialize(n);
 410         fill(start.p, end_of_storage, 0);
 411     }
 412     bit_vector(const self& x) {
 413         initialize(x.size());
 414         copy(x.begin(), x.end(), start);
 415     }
 416
 417 #ifdef __STL_MEMBER_TEMPLATES
 418     template <class InputIterator>
 419     bit_vector(InputIterator first, InputIterator last) {
 420         initialize_range(first, last, iterator_category(first));
 421     }
 422 #else /* __STL_MEMBER_TEMPLATES */
 423     bit_vector(const_iterator first, const_iterator last) {
 424         size_type n = 0;
 425         distance(first, last, n);
 426         initialize(n);
 427         copy(first, last, start);
 428     }
 429     bit_vector(const bool* first, const bool* last) {
 430         size_type n = 0;
 431         distance(first, last, n);
 432         initialize(n);
 433         copy(first, last, start);
 434     }
 435 #endif /* __STL_MEMBER_TEMPLATES */
 436
 437     ~bit_vector() { deallocate(); }
 438     self& operator=(const self& x) {
 439         if (&x == this) return *this;
 440         if (x.size() > capacity()) {
 441             deallocate();
 442             initialize(x.size());
 443         }
 444         copy(x.begin(), x.end(), begin());
 445         finish = begin() + x.size();
 446         return *this;
 447     }
 448     void reserve(size_type n) {
 449         if (capacity() < n) {
 450             unsigned int* q = bit_alloc(n);
 451             finish = copy(begin(), end(), iterator(q, 0));
 452             deallocate();
 453             start = iterator(q, 0);
 454             end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
 455         }
 456     }
 457     reference front() { return *begin(); }
 458     const_reference front() const { return *begin(); }
 459     reference back() { return *(end() - 1); }
 460     const_reference back() const { return *(end() - 1); }
 461     void push_back(bool x) {
 462         if (finish.p != end_of_storage)
 463             *finish++ = x;
 464         else
 465             insert_aux(end(), x);
 466     }
 467     void swap(bit_vector& x) {
 468         ::swap(start, x.start);
 469         ::swap(finish, x.finish);
 470         ::swap(end_of_storage, x.end_of_storage);
 471     }
 472     iterator insert(iterator position, bool x = bool()) {
 473         size_type n = position - begin();
 474         if (finish.p != end_of_storage && position == end())
 475             *finish++ = x;
 476         else
 477             insert_aux(position, x);
 478         return begin() + n;
 479     }
 480
 481 #ifdef __STL_MEMBER_TEMPLATES
 482     template <class InputIterator> void insert(iterator position,
 483                                                InputIterator first,
 484                                                InputIterator last) {
 485       insert_range(position, first, last, iterator_category(first));
 486     }
 487 #else /* __STL_MEMBER_TEMPLATES */
 488     void insert(iterator position, const_iterator first,
 489                 const_iterator last) {
 490       if (first == last) return;
 491       size_type n = 0;
 492       distance(first, last, n);
 493       if (capacity() - size() >= n) {
 494         copy_backward(position, end(), finish + n);
 495         copy(first, last, position);
 496         finish += n;
 497       } else {
 498         size_type len = size() + max(size(), n);
 499         unsigned int* q = bit_alloc(len);
 500         iterator i = copy(begin(), position, iterator(q, 0));
 501         i = copy(first, last, i);
 502         finish = copy(position, end(), i);
 503         deallocate();
 504         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
 505         start = iterator(q, 0);
 506       }
 507     }
 508
 509     void insert(iterator position, const bool* first, const bool* last) {
 510       if (first == last) return;
 511       size_type n = 0;
 512       distance(first, last, n);
 513       if (capacity() - size() >= n) {
 514         copy_backward(position, end(), finish + n);
 515         copy(first, last, position);
 516         finish += n;
 517       } else {
 518         size_type len = size() + max(size(), n);
 519         unsigned int* q = bit_alloc(len);
 520         iterator i = copy(begin(), position, iterator(q, 0));
 521         i = copy(first, last, i);
 522         finish = copy(position, end(), i);
 523         deallocate();
 524         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
 525         start = iterator(q, 0);
 526       }
 527     }
 528 #endif /* __STL_MEMBER_TEMPLATES */
 529
 530     void insert(iterator position, size_type n, bool x) {
 531       if (n == 0) return;
 532       if (capacity() - size() >= n) {
 533         copy_backward(position, end(), finish + n);
 534         fill(position, position + n, x);
 535         finish += n;
 536       } else {
 537         size_type len = size() + max(size(), n);
 538         unsigned int* q = bit_alloc(len);
 539         iterator i = copy(begin(), position, iterator(q, 0));
 540         fill_n(i, n, x);
 541         finish = copy(position, end(), i + n);
 542         deallocate();
 543         end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
 544         start = iterator(q, 0);
 545       }
 546     }
 547
 548     void insert(iterator pos, int n, bool x)  { insert(pos, (size_type)n, x); }
 549     void insert(iterator pos, long n, bool x) { insert(pos, (size_type)n, x); }
 550
 551     void pop_back() { --finish; }
 552     void erase(iterator position) {
 553         if (position + 1 != end())
 554             copy(position + 1, end(), position);
 555         --finish;
 556     }
 557     void erase(iterator first, iterator last) {
 558         finish = copy(last, end(), first);
 559     }
 560     void resize(size_type new_size, bool x = bool()) {
 561       if (new_size < size())
 562         erase(begin() + new_size, end());
 563       else
 564         insert(end(), new_size - size(), x);
 565     }
 566     void clear() { erase(begin(), end()); }
 567 };
 568
 569 inline bool operator==(const bit_vector& x, const bit_vector& y) {
 570     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
 571 }
 572
 573 inline bool operator<(const bit_vector& x, const bit_vector& y) {
 574     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
 575 }
 576
 577 inline void swap(bit_vector::reference x, bit_vector::reference y) {
 578     bool tmp = x;
 579     x = y;
 580     y = tmp;
 581 }
 582
 583 #undef __WORD_BIT
 584
 585 #endif /* __SGI_STL_BVECTOR_H */