stl_bvector.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:18k
源码类别:

STL

开发平台:

Visual C++

  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,1997
  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. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_BVECTOR_H
  30. #define __SGI_STL_INTERNAL_BVECTOR_H
  31. __STL_BEGIN_NAMESPACE 
  32. static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int));
  33. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  34. #pragma set woff 1174
  35. #endif
  36. struct __bit_reference {
  37.   unsigned int* p;
  38.   unsigned int mask;
  39.   __bit_reference(unsigned int* x, unsigned int y) : p(x), mask(y) {}
  40. public:
  41.   __bit_reference() : p(0), mask(0) {}
  42.   operator bool() const { return !(!(*p & mask)); }
  43.   __bit_reference& operator=(bool x) {
  44.     if (x)      
  45.       *p |= mask;
  46.     else 
  47.       *p &= ~mask;
  48.     return *this;
  49.   }
  50.   __bit_reference& operator=(const __bit_reference& x) { return *this = bool(x); }
  51.   bool operator==(const __bit_reference& x) const {
  52.     return bool(*this) == bool(x);
  53.   }
  54.   bool operator<(const __bit_reference& x) const {
  55.     return bool(*this) < bool(x);
  56.   }
  57.   void flip() { *p ^= mask; }
  58. };
  59. inline void swap(__bit_reference x, __bit_reference y) {
  60.   bool tmp = x;
  61.   x = y;
  62.   y = tmp;
  63. }
  64. struct __bit_iterator : public random_access_iterator<bool, ptrdiff_t> {
  65.   typedef __bit_reference  reference;
  66.   typedef __bit_reference* pointer;
  67.   typedef __bit_iterator iterator;
  68.   unsigned int* p;
  69.   unsigned int offset;
  70.   void bump_up() {
  71.     if (offset++ == __WORD_BIT - 1) {
  72.       offset = 0;
  73.       ++p;
  74.     }
  75.   }
  76.   void bump_down() {
  77.     if (offset-- == 0) {
  78.       offset = __WORD_BIT - 1;
  79.       --p;
  80.     }
  81.   }
  82.   __bit_iterator() : p(0), offset(0) {}
  83.   __bit_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
  84.   reference operator*() const { return reference(p, 1U << offset); }
  85.   iterator& operator++() {
  86.     bump_up();
  87.     return *this;
  88.   }
  89.   iterator operator++(int) {
  90.     iterator tmp = *this;
  91.     bump_up();
  92.     return tmp;
  93.   }
  94.   iterator& operator--() {
  95.     bump_down();
  96.     return *this;
  97.   }
  98.   iterator operator--(int) {
  99.     iterator tmp = *this;
  100.     bump_down();
  101.     return tmp;
  102.   }
  103.   iterator& operator+=(difference_type i) {
  104.     difference_type n = i + offset;
  105.     p += n / __WORD_BIT;
  106.     n = n % __WORD_BIT;
  107.     if (n < 0) {
  108.       offset = (unsigned int) n + __WORD_BIT;
  109.       --p;
  110.     } else
  111.       offset = (unsigned int) n;
  112.     return *this;
  113.   }
  114.   iterator& operator-=(difference_type i) {
  115.     *this += -i;
  116.     return *this;
  117.   }
  118.   iterator operator+(difference_type i) const {
  119.     iterator tmp = *this;
  120.     return tmp += i;
  121.   }
  122.   iterator operator-(difference_type i) const {
  123.     iterator tmp = *this;
  124.     return tmp -= i;
  125.   }
  126.   difference_type operator-(iterator x) const {
  127.     return __WORD_BIT * (p - x.p) + offset - x.offset;
  128.   }
  129.   reference operator[](difference_type i) { return *(*this + i); }
  130.   bool operator==(const iterator& x) const {
  131.     return p == x.p && offset == x.offset;
  132.   }
  133.   bool operator!=(const iterator& x) const {
  134.     return p != x.p || offset != x.offset;
  135.   }
  136.   bool operator<(iterator x) const {
  137.     return p < x.p || (p == x.p && offset < x.offset);
  138.   }
  139. };
  140. struct __bit_const_iterator
  141.   : public random_access_iterator<bool, ptrdiff_t>
  142. {
  143.   typedef bool                 reference;
  144.   typedef bool                 const_reference;
  145.   typedef const bool*          pointer;
  146.   typedef __bit_const_iterator const_iterator;
  147.   unsigned int* p;
  148.   unsigned int offset;
  149.   void bump_up() {
  150.     if (offset++ == __WORD_BIT - 1) {
  151.       offset = 0;
  152.       ++p;
  153.     }
  154.   }
  155.   void bump_down() {
  156.     if (offset-- == 0) {
  157.       offset = __WORD_BIT - 1;
  158.       --p;
  159.     }
  160.   }
  161.   __bit_const_iterator() : p(0), offset(0) {}
  162.   __bit_const_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
  163.   __bit_const_iterator(const __bit_iterator& x) : p(x.p), offset(x.offset) {}
  164.   const_reference operator*() const {
  165.     return __bit_reference(p, 1U << offset);
  166.   }
  167.   const_iterator& operator++() {
  168.     bump_up();
  169.     return *this;
  170.   }
  171.   const_iterator operator++(int) {
  172.     const_iterator tmp = *this;
  173.     bump_up();
  174.     return tmp;
  175.   }
  176.   const_iterator& operator--() {
  177.     bump_down();
  178.     return *this;
  179.   }
  180.   const_iterator operator--(int) {
  181.     const_iterator tmp = *this;
  182.     bump_down();
  183.     return tmp;
  184.   }
  185.   const_iterator& operator+=(difference_type i) {
  186.     difference_type n = i + offset;
  187.     p += n / __WORD_BIT;
  188.     n = n % __WORD_BIT;
  189.     if (n < 0) {
  190.       offset = (unsigned int) n + __WORD_BIT;
  191.       --p;
  192.     } else
  193.       offset = (unsigned int) n;
  194.     return *this;
  195.   }
  196.   const_iterator& operator-=(difference_type i) {
  197.     *this += -i;
  198.     return *this;
  199.   }
  200.   const_iterator operator+(difference_type i) const {
  201.     const_iterator tmp = *this;
  202.     return tmp += i;
  203.   }
  204.   const_iterator operator-(difference_type i) const {
  205.     const_iterator tmp = *this;
  206.     return tmp -= i;
  207.   }
  208.   difference_type operator-(const_iterator x) const {
  209.     return __WORD_BIT * (p - x.p) + offset - x.offset;
  210.   }
  211.   const_reference operator[](difference_type i) { 
  212.     return *(*this + i); 
  213.   }
  214.   bool operator==(const const_iterator& x) const {
  215.     return p == x.p && offset == x.offset;
  216.   }
  217.   bool operator!=(const const_iterator& x) const {
  218.     return p != x.p || offset != x.offset;
  219.   }
  220.   bool operator<(const_iterator x) const {
  221.     return p < x.p || (p == x.p && offset < x.offset);
  222.   }
  223. };
  224. // The next few lines are confusing.  What we're doing is declaring a
  225. //  partial specialization of vector<T, Alloc> if we have the necessary
  226. //  compiler support.  Otherwise, we define a class bit_vector which uses
  227. //  the default allocator.  In either case, we typedef "data_allocator" 
  228. //  appropriately.
  229. #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NEED_BOOL)
  230. #define __SGI_STL_VECBOOL_TEMPLATE
  231. #define __BVECTOR vector
  232. #else
  233. #undef __SGI_STL_VECBOOL_TEMPLATE
  234. #define __BVECTOR bit_vector
  235. #endif
  236. #      ifdef __SGI_STL_VECBOOL_TEMPLATE
  237.        __STL_END_NAMESPACE
  238. #      include <stl_vector.h>
  239.        __STL_BEGIN_NAMESPACE
  240. template<class Alloc> class vector<bool, Alloc>
  241. #      else /* __SGI_STL_VECBOOL_TEMPLATE */
  242. class bit_vector
  243. #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
  244. {
  245. #      ifdef __SGI_STL_VECBOOL_TEMPLATE
  246.   typedef simple_alloc<unsigned int, Alloc> data_allocator;
  247. #      else /* __SGI_STL_VECBOOL_TEMPLATE */
  248.   typedef simple_alloc<unsigned int, alloc> data_allocator;  
  249. #      endif /* __SGI_STL_VECBOOL_TEMPLATE */
  250. public:
  251.   typedef bool value_type;
  252.   typedef size_t size_type;
  253.   typedef ptrdiff_t difference_type; 
  254.   typedef __bit_reference reference;
  255.   typedef bool const_reference;
  256.   typedef __bit_reference* pointer;
  257.   typedef const bool* const_pointer;
  258.   typedef __bit_iterator                iterator;
  259.   typedef __bit_const_iterator          const_iterator;
  260. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  261.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  262.   typedef reverse_iterator<iterator> reverse_iterator;
  263. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  264.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  265.                            difference_type> const_reverse_iterator;
  266.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  267.           reverse_iterator;
  268. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  269. protected:
  270.   iterator start;
  271.   iterator finish;
  272.   unsigned int* end_of_storage;
  273.   unsigned int* bit_alloc(size_type n) {
  274.     return data_allocator::allocate((n + __WORD_BIT - 1)/__WORD_BIT);
  275.   }
  276.   void deallocate() {
  277.     if (start.p)
  278.       data_allocator::deallocate(start.p, end_of_storage - start.p);
  279.   }
  280.   void initialize(size_type n) {
  281.     unsigned int* q = bit_alloc(n);
  282.     end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  283.     start = iterator(q, 0);
  284.     finish = start + difference_type(n);
  285.   }
  286.   void insert_aux(iterator position, bool x) {
  287.     if (finish.p != end_of_storage) {
  288.       copy_backward(position, finish, finish + 1);
  289.       *position = x;
  290.       ++finish;
  291.     }
  292.     else {
  293.       size_type len = size() ? 2 * size() : __WORD_BIT;
  294.       unsigned int* q = bit_alloc(len);
  295.       iterator i = copy(begin(), position, iterator(q, 0));
  296.       *i++ = x;
  297.       finish = copy(position, end(), i);
  298.       deallocate();
  299.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  300.       start = iterator(q, 0);
  301.     }
  302.   }
  303. #ifdef __STL_MEMBER_TEMPLATES
  304.   template <class InputIterator>
  305.   void initialize_range(InputIterator first, InputIterator last,
  306.                         input_iterator_tag) {
  307.     start = iterator();
  308.     finish = iterator();
  309.     end_of_storage = 0;
  310.     for ( ; first != last; ++first) 
  311.       push_back(*first);
  312.   }
  313.   template <class ForwardIterator>
  314.   void initialize_range(ForwardIterator first, ForwardIterator last,
  315.                         forward_iterator_tag) {
  316.     size_type n = 0;
  317.     distance(first, last, n);
  318.     initialize(n);
  319.     copy(first, last, start);
  320.   }
  321.   template <class InputIterator>
  322.   void insert_range(iterator pos,
  323.                     InputIterator first, InputIterator last,
  324.                     input_iterator_tag) {
  325.     for ( ; first != last; ++first) {
  326.       pos = insert(pos, *first);
  327.       ++pos;
  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 + difference_type(n));
  339.         copy(first, last, position);
  340.         finish += difference_type(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. #endif /* __STL_MEMBER_TEMPLATES */
  355. public:
  356.   iterator begin() { return start; }
  357.   const_iterator begin() const { return start; }
  358.   iterator end() { return finish; }
  359.   const_iterator end() const { return finish; }
  360.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  361.   const_reverse_iterator rbegin() const { 
  362.     return const_reverse_iterator(end()); 
  363.   }
  364.   reverse_iterator rend() { return reverse_iterator(begin()); }
  365.   const_reverse_iterator rend() const { 
  366.     return const_reverse_iterator(begin()); 
  367.   }
  368.   size_type size() const { return size_type(end() - begin()); }
  369.   size_type max_size() const { return size_type(-1); }
  370.   size_type capacity() const {
  371.     return size_type(const_iterator(end_of_storage, 0) - begin());
  372.   }
  373.   bool empty() const { return begin() == end(); }
  374.   reference operator[](size_type n) {
  375.     return *(begin() + difference_type(n));
  376.   }
  377.   const_reference operator[](size_type n) const {
  378.     return *(begin() + difference_type(n));
  379.   }
  380.   __BVECTOR() : start(iterator()), finish(iterator()), end_of_storage(0) {}
  381.   __BVECTOR(size_type n, bool value) {
  382.     initialize(n);
  383.     fill(start.p, end_of_storage, value ? ~0 : 0);
  384.   }
  385.   __BVECTOR(int n, bool value) {
  386.     initialize(n);
  387.     fill(start.p, end_of_storage, value ? ~0 : 0);
  388.   }
  389.   __BVECTOR(long n, bool value) {
  390.     initialize(n);
  391.     fill(start.p, end_of_storage, value ? ~0 : 0);
  392.   }
  393.   explicit __BVECTOR(size_type n) {
  394.     initialize(n);
  395.     fill(start.p, end_of_storage, 0);
  396.   }
  397.   __BVECTOR(const __BVECTOR& x) {
  398.     initialize(x.size());
  399.     copy(x.begin(), x.end(), start);
  400.   }
  401. #ifdef __STL_MEMBER_TEMPLATES
  402.   template <class InputIterator>
  403.   __BVECTOR(InputIterator first, InputIterator last) {
  404.     initialize_range(first, last, iterator_category(first));
  405.   }
  406. #else /* __STL_MEMBER_TEMPLATES */
  407.   __BVECTOR(const_iterator first, const_iterator last) {
  408.     size_type n = 0;
  409.     distance(first, last, n);
  410.     initialize(n);
  411.     copy(first, last, start);
  412.   }
  413.   __BVECTOR(const bool* first, const bool* last) {
  414.     size_type n = 0;
  415.     distance(first, last, n);
  416.     initialize(n);
  417.     copy(first, last, start);
  418.   }
  419. #endif /* __STL_MEMBER_TEMPLATES */
  420.   ~__BVECTOR() { deallocate(); }
  421.   __BVECTOR& operator=(const __BVECTOR& x) {
  422.     if (&x == this) return *this;
  423.     if (x.size() > capacity()) {
  424.       deallocate();
  425.       initialize(x.size());
  426.     }
  427.     copy(x.begin(), x.end(), begin());
  428.     finish = begin() + difference_type(x.size());
  429.     return *this;
  430.   }
  431.   void reserve(size_type n) {
  432.     if (capacity() < n) {
  433.       unsigned int* q = bit_alloc(n);
  434.       finish = copy(begin(), end(), iterator(q, 0));
  435.       deallocate();
  436.       start = iterator(q, 0);
  437.       end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
  438.     }
  439.   }
  440.   reference front() { return *begin(); }
  441.   const_reference front() const { return *begin(); }
  442.   reference back() { return *(end() - 1); }
  443.   const_reference back() const { return *(end() - 1); }
  444.   void push_back(bool x) {
  445.     if (finish.p != end_of_storage)
  446.       *finish++ = x;
  447.     else
  448.       insert_aux(end(), x);
  449.   }
  450.   void swap(__BVECTOR& x) {
  451.     __STD::swap(start, x.start);
  452.     __STD::swap(finish, x.finish);
  453.     __STD::swap(end_of_storage, x.end_of_storage);
  454.   }
  455.   iterator insert(iterator position, bool x = bool()) {
  456.     difference_type n = position - begin();
  457.     if (finish.p != end_of_storage && position == end())
  458.       *finish++ = x;
  459.     else
  460.       insert_aux(position, x);
  461.     return begin() + n;
  462.   }
  463. #ifdef __STL_MEMBER_TEMPLATES
  464.   template <class InputIterator> void insert(iterator position,
  465.                                              InputIterator first,
  466.                                              InputIterator last) {
  467.     insert_range(position, first, last, iterator_category(first));
  468.   }
  469. #else /* __STL_MEMBER_TEMPLATES */
  470.   void insert(iterator position, const_iterator first, 
  471.               const_iterator last) {
  472.     if (first == last) return;
  473.     size_type n = 0;
  474.     distance(first, last, n);
  475.     if (capacity() - size() >= n) {
  476.       copy_backward(position, end(), finish + n);
  477.       copy(first, last, position);
  478.       finish += n;
  479.     }
  480.     else {
  481.       size_type len = size() + max(size(), n);
  482.       unsigned int* q = bit_alloc(len);
  483.       iterator i = copy(begin(), position, iterator(q, 0));
  484.       i = copy(first, last, i);
  485.       finish = copy(position, end(), i);
  486.       deallocate();
  487.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  488.       start = iterator(q, 0);
  489.     }
  490.   }
  491.   void insert(iterator position, const bool* first, const bool* last) {
  492.     if (first == last) return;
  493.     size_type n = 0;
  494.     distance(first, last, n);
  495.     if (capacity() - size() >= n) {
  496.       copy_backward(position, end(), finish + n);
  497.       copy(first, last, position);
  498.       finish += n;
  499.     }
  500.     else {
  501.       size_type len = size() + max(size(), n);
  502.       unsigned int* q = bit_alloc(len);
  503.       iterator i = copy(begin(), position, iterator(q, 0));
  504.       i = copy(first, last, i);
  505.       finish = copy(position, end(), i);
  506.       deallocate();
  507.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  508.       start = iterator(q, 0);
  509.     }
  510.   }
  511. #endif /* __STL_MEMBER_TEMPLATES */
  512.   
  513.   void insert(iterator position, size_type n, bool x) {
  514.     if (n == 0) return;
  515.     if (capacity() - size() >= n) {
  516.       copy_backward(position, end(), finish + difference_type(n));
  517.       fill(position, position + difference_type(n), x);
  518.       finish += difference_type(n);
  519.     }
  520.     else {
  521.       size_type len = size() + max(size(), n);
  522.       unsigned int* q = bit_alloc(len);
  523.       iterator i = copy(begin(), position, iterator(q, 0));
  524.       fill_n(i, n, x);
  525.       finish = copy(position, end(), i + difference_type(n));
  526.       deallocate();
  527.       end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
  528.       start = iterator(q, 0);
  529.     }
  530.   }
  531.   void insert(iterator pos, int n, bool x)  { insert(pos, (size_type)n, x); }
  532.   void insert(iterator pos, long n, bool x) { insert(pos, (size_type)n, x); }
  533.   void pop_back() { --finish; }
  534.   iterator erase(iterator position) {
  535.     if (position + 1 != end())
  536.       copy(position + 1, end(), position);
  537.     --finish;
  538.     return position;
  539.   }
  540.   iterator erase(iterator first, iterator last) {
  541.     finish = copy(last, end(), first);
  542.     return first;
  543.   }
  544.   void resize(size_type new_size, bool x = bool()) {
  545.     if (new_size < size()) 
  546.       erase(begin() + difference_type(new_size), end());
  547.     else
  548.       insert(end(), new_size - size(), x);
  549.   }
  550.   void clear() { erase(begin(), end()); }
  551. };
  552. #ifdef __SGI_STL_VECBOOL_TEMPLATE
  553. typedef vector<bool, alloc> bit_vector;
  554. #else /* __SGI_STL_VECBOOL_TEMPLATE */
  555. inline bool operator==(const bit_vector& x, const bit_vector& y) {
  556.   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  557. }
  558. inline bool operator<(const bit_vector& x, const bit_vector& y) {
  559.   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  560. }
  561. #endif /* __SGI_STL_VECBOOL_TEMPLATE */
  562. #undef __SGI_STL_VECBOOL_TEMPLATE
  563. #undef __BVECTOR
  564. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  565. #pragma reset woff 1174
  566. #endif
  567. __STL_END_NAMESPACE 
  568. #endif /* __SGI_STL_INTERNAL_BVECTOR_H */
  569. // Local Variables:
  570. // mode:C++
  571. // End: