// vector header.
// Copyright (c) 1994,1995,1996 by ObjectSpace, Inc.  All rights reserved.
// Copyright (c) 1994,1995 by Hewlett-Packard Company.  All rights reserved.
// Email: sales@objectspace.com, ccs.support@objectspace.com


#ifndef OS_OSSTD_VECTOR_H
#define OS_OSSTD_VECTOR_H

#include <ospace/osstd/common.h>

#include <ospace/osstd/iterator.h>
#include <ospace/osstd/basalgo.h>
#include <ospace/osstd/rawalgo.h>
#include <ospace/osstd/allocate.h>
#include <ospace/osstd/stdex.h>


#ifdef OS_OSPACE_STD_NAMESPACE
  namespace os_std
    {
#endif

#if ( _MSC_VER == 1010 )
# pragma warning ( disable : 4237 )
#endif


OS_VCC_PUBLIC_STD void OS_BCC_PUBLIC_STD os_throw_out_of_range();


// Error map:
//   OPERATION             EVENT
//   constructors          out of storage
//   insert()              out of storage
//   push_back()           out of storage
//   reserve()             out of storage
//   operator=             out of storage
//   operator[]            illegal n
//   front()               empty
//   back()                empty
//   pop_back()            empty


#ifdef Allocator
# define AllocatorSet
#elif ( defined OS_NO_ALLOCATORS )
# define Allocator os_allocator
#endif

#ifdef OS_NO_ALLOCATORS
  template< class T >
#else
  template< class T, class Allocator = os_allocator< T > >
#endif
class os_vector
  {
  public:
    typedef T                        value_type;
    typedef OS_REFERENCE( T )        reference;
    typedef OS_CONST_REFERENCE( T )  const_reference;
    typedef OS_SIZE_TYPE( T )        size_type;
    typedef OS_DIFF_TYPE( T )        difference_type;
    typedef OS_ALLOCATOR( T )        allocator_type;

    typedef T*        pointer;
    typedef const T*  const_pointer;

    typedef T*        iterator;
    typedef const T*  const_iterator;

    typedef os_reverse_iterator
      <
      T*,
      T,
      OS_REFERENCE( T ),
      T*,
      OS_DIFF_TYPE( T )
      >  reverse_iterator;
    typedef os_reverse_iterator
      <
      const T*,
      T,
      OS_CONST_REFERENCE( T ),
      const T*,
      OS_DIFF_TYPE( T )
      >  const_reverse_iterator;

    // Construct me to be an empty vector.
    os_vector() :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_()
      {
      }

    // Construct me to be an empty vector.
    explicit os_vector( const OS_ALLOCATOR( T ) & alloc ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      }

    // Construct me to contain `n` ( >0 ) elements. Each element will be
    // a copy of `value`.
    os_vector
      (
      size_type n,
      const T& value, // = T()
      const OS_ALLOCATOR( T ) & alloc // = OS_ALLOCATOR( T )()
      ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( n, value );
      }

    os_vector ( size_type n, const T& value ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_()
      {
      assign( n, value );
      }

    os_vector ( size_type n ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_()
      {
      assign( n, T() );
      }


    // Construct me to contain copies of all the elements in `original`.
    os_vector( const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & original ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( original.get_allocator() )
      {
      assign( original.begin(), original.end() );
      }

    // Construct me to contain all of the elements in the
    // range [`first`, `last`).
#   ifdef OS_NO_MEMBER_TEMPLATES
      os_vector
        (
        const_iterator first,
        const_iterator last,
        const OS_ALLOCATOR( T ) & alloc = OS_ALLOCATOR( T )()
        ) :
#   else
      template< class InIt >
      os_vector
        (
        InIt first,
        InIt last,
        const OS_ALLOCATOR( T ) & alloc = OS_ALLOCATOR( T )()
        ) :
#   endif
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( first, last );
      }

    // Destroy me.
    ~os_vector()
      {
      clear();
      }

    // Replace my contents with a copy of the elements in `original`,
    // resizing if necessary.
    os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & operator=
      (
      const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & original
      );

    // Remove all my current elements, and then insert the elements
    // in range [`first`, `last`).
    void assign( const_iterator first, const_iterator last )
      {
      if ( first == begin() )
        erase( begin() + ( last - first ), end() );
      else
        assign_aux( first, last );
      }

#   ifndef OS_NO_MEMBER_TEMPLATES
      // Remove all my current elements, and then insert the elements
      // in range [`first`, `last`).
      template< class InIt >
      void assign( InIt first, InIt last )
        {
        assign_aux( first, last );
        }
#   endif

    // Remove all my current elements, and then insert `n` copies of
    // `value`.
    void assign( size_type n, const T& value );

#   ifndef OS_ANSI
      void assign( size_type n )
        {
        assign( n, T() );
        }
#   endif

    // Return a copy of the allocator I am using.
    allocator_type get_allocator() const
      {
      return alloc_;
      }

    // Return a random access iterator positioned at my first element.
    iterator begin()
      {
      return start_;
      }

    // Return a constant random access iterator positioned at my first
    // element.
    const_iterator begin() const
      {
      return start_;
      }

    // Return a random access iterator positioned immediately after my
    // last element.
    iterator end()
      {
      return finish_;
      }

    // Return a constant random access iterator positioned immediately after
    // my last element.
    const_iterator end() const
      {
      return finish_;
      }

    // Return a random access reverse iterator positioned immediately after
    // my last element.
    reverse_iterator rbegin()
      {
      return reverse_iterator( end() );
      }

    // Return a constant random access reverse iterator positioned
    // immediately after my last element.
    const_reverse_iterator rbegin() const
      {
      return const_reverse_iterator( end() );
      }

    // Return a random access reverse iterator positioned at my first
    // element.
    reverse_iterator rend()
      {
      return reverse_iterator( begin() );
      }

    // Return a constant random access reverse iterator positioned at my
    // first element.
    const_reverse_iterator rend() const
      {
      return const_reverse_iterator( begin() );
      }

    // Return the number of elements that I contain.
    size_type size() const
      {
      return end() - begin();
      }

    // Return the maximum number of elements that I can contain.
    size_type max_size() const
      {
      return alloc_.max_size();
      }

    // Cause myself to hold `n` elements, using `value` to expand
    // myself if necessary.
    void resize( size_type n, T value )
      {
      if ( n > size() )
        insert( end(), n - size(), value );
      else
        erase( begin() + n, end() );
      }

    // Cause myself to hold `n` elements using the default constructor
    // to expand myself if necessary.
    void resize( size_type n )
      {
      resize( n, T() );
      }

    // Return the number of elements that I can contain without allocating
    // more memory.
    size_type capacity() const
      {
      return end_of_storage_ - start_;
      }

    // Return true if I contain no elements.
    bool empty() const
      {
      return begin() == end();
      }

    // Change my capacity to be at least `n`.  Does not affect my
    // current size.
    void reserve( size_type n );

    // Return a reference to my `n`th element.
    reference operator[]( size_type n )
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      OS_ASSERT_INDEX_OK( n, 0, size() - 1 )
      return *( begin() + n );
      }

    // Return a constant reference to my `n`th element.
    const_reference operator[]( size_type n ) const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      OS_ASSERT_INDEX_OK( n, 0, size() - 1 )
      return *( begin() + n );
      }

    // Return a reference to my `n`th element.
    reference at( size_type n )
      {
      if ( n >= size() )
        os_throw_out_of_range();
      return *( begin() + n );
      }

    // Return a constant reference to my `n`th element.
    const_reference at( size_type n ) const
      {
      if ( n >= size() )
        os_throw_out_of_range();
      return *( begin() + n );
      }

    // Return a reference to my first element.
    reference front()
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *begin();
      }

    // Return a constant reference to my first element.
    const_reference front() const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *begin();
      }

    // Return a reference to my last element.
    reference back()
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *( end() - 1 );
      }

    // Return a constant reference to my last element.
    const_reference back() const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *( end() - 1 );
      }

    // Add `value` at my end.
    void push_back( const_reference value )
      {
      if ( finish_ != end_of_storage_ )
        {
        alloc_.construct( finish_, value );
        ++finish_;
        }
      else
        insert_aux( end(), value );
      }

    // Erase my last element.
    void pop_back()
      {
      OS_ASSERT_NOT_EMPTY_ELSE( empty() )
        {
        --finish_; // not on a single line due to Borland problem
        alloc_.destroy( finish_ );
        }
      }

    // Insert `value` at `pos` and return an iterator pointing to the new
    // element's position.
    iterator insert( iterator pos, const T& value )
      {
      size_type n = pos - begin();
      if ( finish_ != end_of_storage_ && pos == finish_ )
        {
        alloc_.construct( finish_, value );
        ++finish_;
        }
      else
        insert_aux( pos, value );
      return begin() + n;
      }

    // Insert an element constructed with the default constructor at `pos` and
    // return an iterator pointing to the new element's position.
    // not standard, left for backward compatibility
#   ifndef OS_ANSI
     iterator insert( iterator pos )
       {
       return insert( pos, T() );
       }
#   endif


    // Insert `n` copies of `value` at `pos`.
    void insert( iterator pos, size_type n, const T& value );

    // Insert copies of the elements in range [`first`, `last`) at `pos`.
#   ifdef OS_NO_MEMBER_TEMPLATES
      void insert( iterator pos, const_iterator first, const_iterator last );
#   else
      template< class InIt >
      void insert( iterator pos, InIt first, InIt last );
#   endif

    // Erase the element at `pos`.
    iterator erase( iterator pos )
      {
      if ( !( pos + 1 == end() ) )
        copy( pos + 1, end(), pos );
      pop_back();
      return pos;
      }

    // Erase the elements in range [`first`, `last`).
    iterator erase( iterator first, iterator last )
      {
      iterator i = copy( last, end(), first );
      destroy( i, finish_, alloc_ );
      finish_ = finish_ - ( last - first );
      return first;
      }

    // Swap my contents with those of `original`.
    void swap( os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & original )
      {
      if ( !(alloc_ == original.alloc_ ) )
        {
        os_vector OS_ALLOCATE_ARG_2( T, Allocator ) tmp( *this );
        assign( original.begin(), original.end() );
        original.assign( tmp.begin(), tmp.end() );
        }
      else
        {
#       ifdef OS_OSPACE_STD_NAMESPACE
          OS_STD swap( start_, original.start_ );
          OS_STD swap( finish_, original.finish_ );
          OS_STD swap( end_of_storage_, original.end_of_storage_ );
          OS_STD swap( alloc_, original.alloc_ );
#       else
          ::swap( start_, original.start_ );
          ::swap( finish_, original.finish_ );
          ::swap( end_of_storage_, original.end_of_storage_ );
          ::swap( alloc_, original.alloc_ );
#       endif
        }
      }

    // Erase all of my elements.
    void clear()
      {
      if ( start_ )
        {
        destroy( start_, finish_, alloc_ );
        alloc_.deallocate( start_ );
        }
      start_ = finish_ = end_of_storage_ = 0;
      }

  protected:
    void insert_aux( T* pos, const T& value );

#   ifdef OS_NO_MEMBER_TEMPLATES
      void assign_aux( const_iterator first, const_iterator last );
#   else
      template< class InIt >
      void assign_aux( InIt first, InIt last );
#   endif

  private:
    // Data members.
    iterator start_;
    iterator finish_;
    iterator end_of_storage_;
    allocator_type alloc_;

# ifndef OS_ANSI
  public:
    // Construct me to contain n ( >0 ) elements. Each element will be
    // default constructed.
    // This remains for compatibility.  It will be removed in a future release.
    os_vector
      (
      const OS_ALLOCATOR( T ) & alloc,
      size_type n
      ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( n, T() );
      }

    // Construct me to contain n ( >0 ) elements. Each element will be
    // a copy of `value`.
    // This remains for compatibility.  It will be removed in a future release.
    os_vector
      (
      const OS_ALLOCATOR( T ) & alloc,
      size_type n,
      const T& value
      ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( n, value );
      }

    // Construct me to contain copies of all the elements in `original`.
    // This remains for compatibility.  It will be removed in a future release.
    os_vector
      (
      const OS_ALLOCATOR( T ) & alloc,
      const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & original
      ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( original.begin(), original.end() );
      }

    // Construct me to contain all of the elements in the
    // range [`first`, `last`).
    // This remains for compatibility.  It will be removed in a future release.
    os_vector
      (
      const OS_ALLOCATOR( T ) & alloc,
      const_iterator first,
      const_iterator last
      ) :
      start_( 0 ),
      finish_( 0 ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      assign( first, last );
      }

    // Erase all of my elements.
    // This remains for compatibility.  It will be removed in a future release.
    void erase()
      {
      clear();
      }
# endif
  };


// Return `true` if `x` and `y` are equivilant.
template OS_ALLOCATE_DEF_2( T, Allocator )
inline bool
operator==
  (
  const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & x,
  const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & y
  )
  {
  return x.size() == y.size() && equal( x.begin (), x.end(), y.begin() );
  }


// Return `true` if `x` is lexicographically less than `y`.
template OS_ALLOCATE_DEF_2( T, Allocator )
inline bool
operator<
  (
  const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & x,
  const os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & y
  )
  {
  return lexicographical_compare( x.begin (), x.end(), y.begin(), y.end() );
  }


// Swap the contents of `x` and `y`.
template OS_ALLOCATE_DEF_2( T, Allocator )
inline void
swap
  (
  os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & x,
  os_vector OS_ALLOCATE_ARG_2( T, Allocator ) & y
  )
  {
  x.swap( y );
  }



#ifndef OS_BAD_INLINING


#if ( !defined OS_NO_BOOL )

#define OS_WORD_BIT (int( CHAR_BIT * sizeof( unsigned int ) ))

#if defined OS_NO_ALLOCATORS
# define OS_BOOL_ARG  < bool >
#else
# define OS_BOOL_ARG  < bool, os_allocator< bool > >
#endif


class os_bool_reference
  {
  friend class os_vector OS_BOOL_ARG;
  friend class os_bool_iterator;
  friend class os_const_bool_iterator;

  public:
    // Become a copy of `original`.
    os_bool_reference( const os_bool_reference& original ) :
      ptr_( original.ptr_ ),
      mask_( original.mask_ )
      {
      }

    // Reference the same boolean as `original`.
    os_bool_reference& operator=( const os_bool_reference& original )
      {
      return *this = bool( original );
      }

    // Destroy myself.
    ~os_bool_reference()
      {
      }

    // Return myself converted into a boolean.
    operator bool() const
      {
      return !( !( *ptr_ & mask_ ) );
      }

    // Set my associated boolean to `value`.
    os_bool_reference& operator=( bool value )
      {
      if ( value )
        *ptr_ |= mask_;
      else
        *ptr_ &= ~mask_;
      return *this;
      }

    // Invert my boolean.
    void flip()
      {
      *ptr_ ^= mask_;
      }

  protected:
    os_bool_reference() :
      ptr_( 0 ),
      mask_( 0 )
      {
      }

    os_bool_reference( unsigned int* ptr, unsigned int mask ) :
      ptr_( ptr ),
      mask_( mask )
      {
      }

    unsigned int* ptr_;
    unsigned int mask_;
  };


// Swap the bits referenced by `x` and `y`.
inline void
swap( os_bool_reference& x, os_bool_reference& y )
  {
  bool tmp = x;
  x = y;
  y = tmp;
  }





class os_bool_iterator :
  public os_random_access_iterator< bool, ptrdiff_t >
  {
  friend class os_vector OS_BOOL_ARG;
  friend class os_const_bool_iterator;

  public:
    // Construct me with no associated position.
    os_bool_iterator() :
      ref_( 0, 0 ),
      offset_( 0 )
      {
      }

    // Construct me with with index `y` into `x`.
    os_bool_iterator( unsigned int* x, unsigned int y ) :
      ref_( x, 1U << y ),
      offset_( y )
      {
      }

#   ifdef OS_EXPLICIT_COPY_HACK
      // Construct me with the same position as `original`.
      os_bool_iterator( const os_bool_iterator& original ) :
        ref_( original.ref_ ),
        offset_( original.offset_ )
        {
        }
#   endif

    // Assign me to have the same position as `original`.
    os_bool_iterator& operator=( const os_bool_iterator& original )
      {
      ref_.ptr_ = original.ref_.ptr_;
      ref_.mask_ = original.ref_.mask_;
      offset_ = original.offset_;
      return *this;
      }

    // Return a reference to the boolean that I'm associated with.
    os_bool_reference& operator*() const
      {
      return (os_bool_reference&)ref_;
      }

    // Return a handle to the boolean that I'm associated with.
    os_bool_reference* operator->() const
      {
      return &( operator*() );
      }

    // Advance one element and return my new value.
    os_bool_iterator& operator++()
      {
      bump_up();
      return *this;
      }

    // Advance one element and return my previous value.
    os_bool_iterator operator++( int )
      {
      os_bool_iterator tmp = *this;
      bump_up();
      return tmp;
      }

    // Retreat one element and return my new value.
    os_bool_iterator& operator--()
      {
      bump_down();
      return *this;
      }

    // Retreat one element and return my previous value.
    os_bool_iterator operator--( int )
      {
      os_bool_iterator tmp = *this;
      bump_down();
      return tmp;
      }

    // Advance by `n` elements and return my new value.
    os_bool_iterator& operator+=( ptrdiff_t n )
      {
      ptrdiff_t i = n + offset_;
      ref_.ptr_ += i / OS_WORD_BIT;
      i %= OS_WORD_BIT;
      if ( i < 0 )
        {
        offset_ = i + OS_WORD_BIT;
        --ref_.ptr_;
        }
      else
        {
        offset_ = i;
        }
      //ref_ = os_bool_reference( ref_.ptr_, 1U << offset_ );
      ref_.mask_ = (1U << offset_);
      return *this;
      }

    // Retreat by `n` elements and return my new value.
    os_bool_iterator& operator-=( ptrdiff_t n )
      {
      return *this += -n;
      }

    // Return a random access iterator positioned `n` elements ahead of my
    // current position.
    os_bool_iterator operator+( ptrdiff_t n ) const
      {
      os_bool_iterator tmp = *this;
      return tmp += n;
      }

    // Return a random access iterator positioned `n` elements before my
    // current position.
    os_bool_iterator operator-( ptrdiff_t n ) const
      {
      os_bool_iterator tmp = *this;
      return tmp -= n;
      }

    // Return the distance between `iter` and myself.
    ptrdiff_t operator-( const os_bool_iterator& iter ) const
      {
      return
        OS_WORD_BIT * (ref_.ptr_ - iter.ref_.ptr_) + offset_ - iter.offset_;
      }

    // Return a reference to the element that is `n` elements ahead of my
    // current position.
    os_bool_reference operator[]( ptrdiff_t n ) const
      {
      return *(*this + n);
      }

    // Return true if my position is the same as `iter`s.
    bool operator==( const os_bool_iterator& iter ) const
      {
      return ref_.ptr_ == iter.ref_.ptr_ && offset_ == iter.offset_;
      }

    // Return `true` if my position is less than `iter`s.
    bool operator<( os_bool_iterator iter ) const
      {
      return
        ref_.ptr_ < iter.ref_.ptr_ || (ref_.ptr_ == iter.ref_.ptr_ && offset_ < iter.offset_);
      }

    bool operator!=( const os_bool_iterator& iter ) const
      {
      return !(*this == iter);
      }

    bool operator>( const os_bool_iterator& iter ) const
      {
      return iter < *this;
      }

    bool operator<=( const os_bool_iterator& iter ) const
      {
      return !(iter < *this);
      }

    bool operator>=( const os_bool_iterator& iter ) const
      {
      return !(*this < iter);
      }

  protected:
    void bump_up()
      {
      if ( offset_ == OS_WORD_BIT - 1 )
        {
        offset_ = 0;
        ++ref_.ptr_;
        }
      else
        ++offset_;
      ref_.mask_ = (1U << offset_);
      }

    void bump_down()
      {
      if ( offset_ == 0 )
        {
        offset_ = OS_WORD_BIT - 1;
        --ref_.ptr_;
        }
      else
        --offset_;
      ref_.mask_ = (1U << offset_);
      }

    // Data members.
    mutable os_bool_reference ref_;
    size_t offset_;
  };


// Return my iterator category.
inline os_random_access_iterator_tag
os_iterator_category( const os_bool_iterator& )
  {
  return OS_RANDOM_ACCESS_ITERATOR_TAG;
  }


// Return my value type.
inline bool*
value_type( const os_bool_iterator& )
  {
  return (bool*)0;
  }


// Return my distance type.
inline ptrdiff_t*
distance_type( const os_bool_iterator& )
  {
  return (ptrdiff_t*)0;
  }






class os_const_bool_iterator :
  public os_random_access_iterator< bool, ptrdiff_t >
  {
  friend class os_vector OS_BOOL_ARG;

  public:
    // Construct me with no associated position.
    os_const_bool_iterator() :
      ref_( 0, 0 ),
      offset_( 0 )
      {
      }

    // Construct me with with index `y` into `x`.
    os_const_bool_iterator( unsigned int* x, unsigned int y ) :
      ref_( x, 1U << y ),
      offset_( y )
      {
      }

    // Construct me with the same position as `original`.
    os_const_bool_iterator( const os_bool_iterator& original ) :
      ref_( original.ref_ ),
      offset_( original.offset_ )
      {
      }

#   ifdef OS_EXPLICIT_COPY_HACK
      // Construct me with the same position as `original`.
      os_const_bool_iterator( const os_const_bool_iterator& original ) :
        ref_( original.ref_ ),
        offset_( original.offset_ )
        {
        }
#   endif

    // Assign me to have the same position as `original`.
    os_const_bool_iterator& operator=( const os_const_bool_iterator& original )
      {
      ref_.ptr_ = original.ref_.ptr_;
      ref_.mask_ = original.ref_.mask_;
      offset_ = original.offset_;
      return *this;
      }

    // Return a reference to the boolean that I'm associated with.
    const os_bool_reference& operator*() const
      {
      return ref_;
      }

    // Return a handle to the boolean that I'm associated with.
    const os_bool_reference* operator->() const
      {
      return &( operator*() );
      }

    // Advance one element and return my new value.
    os_const_bool_iterator& operator++()
      {
      bump_up();
      return *this;
      }

    // Advance one element and return my previous value.
    os_const_bool_iterator operator++( int )
      {
      os_const_bool_iterator tmp = *this;
      bump_up();
      return tmp;
      }

    // Retreat one element and return my new value.
    os_const_bool_iterator& operator--()
      {
      bump_down();
      return *this;
      }

    // Retreat one element and return my previous value.
    os_const_bool_iterator operator--( int )
      {
      os_const_bool_iterator tmp = *this;
      bump_down();
      return tmp;
      }

    // Advance by `n` elements and return my new value.
    os_const_bool_iterator& operator+=( ptrdiff_t n )
      {
      ptrdiff_t i = n + offset_;
      ref_.ptr_ += i / OS_WORD_BIT;
      i %= OS_WORD_BIT;
      if ( i < 0 )
        {
        offset_ = i + OS_WORD_BIT;
        --ref_.ptr_;
        }
      else
        {
        offset_ = i;
        }
      //ref_ = os_bool_reference( ref_.ptr_, 1U << offset_ );
      ref_.mask_ = 1U << offset_;
      return *this;
      }

    // Retreat by `n` elements and return my new value.
    os_const_bool_iterator& operator-=( ptrdiff_t n )
      {
      return *this += -n;
      }

    // Return a random access iterator positioned `n` elements ahead of my
    // current position.
    os_const_bool_iterator operator+( ptrdiff_t n ) const
      {
      os_const_bool_iterator tmp = *this;
      return tmp += n;
      }

    // Return a random access iterator positioned `n` elements before my
    // current position.
    os_const_bool_iterator operator-( ptrdiff_t n ) const
      {
      os_const_bool_iterator tmp = *this;
      return tmp -= n;
      }

    // Return the distance between `iter` and myself.
    ptrdiff_t operator-( const os_const_bool_iterator& iter ) const
      {
      return
        OS_WORD_BIT * (ref_.ptr_ - iter.ref_.ptr_) + offset_ - iter.offset_;
      }

    // Return a reference to the element that is `n` elements ahead of my
    // current position.
    os_bool_reference operator[]( ptrdiff_t n ) const
      {
      return *(*this + n);
      }

    // Return true if my position is the same as `iter`s.
    bool operator==( const os_const_bool_iterator& iter ) const
      {
      return ref_.ptr_ == iter.ref_.ptr_ && offset_ == iter.offset_;
      }

    // Return `true` if my position is less than `iter`s.
    bool operator<( os_const_bool_iterator iter ) const
      {
      return
        ref_.ptr_ < iter.ref_.ptr_ || (ref_.ptr_ == iter.ref_.ptr_ && offset_ < iter.offset_);
      }

    bool operator!=( const os_const_bool_iterator& iter ) const
      {
      return !(*this == iter);
      }

    bool operator>( const os_const_bool_iterator& iter ) const
      {
      return iter < *this;
      }

    bool operator<=( const os_const_bool_iterator& iter ) const
      {
      return !(iter < *this);
      }

    bool operator>=( const os_const_bool_iterator& iter ) const
      {
      return !(*this < iter);
      }

  protected:
    void bump_up()
      {
      if ( offset_ == OS_WORD_BIT - 1 )
        {
        offset_ = 0;
        ++ref_.ptr_;
        }
      else
        ++offset_;
      ref_.mask_ = (1U << offset_);
      }

    void bump_down()
      {
      if ( offset_ == 0 )
        {
        offset_ = OS_WORD_BIT - 1;
        --ref_.ptr_;
        }
      else
        --offset_;
      ref_.mask_ = (1U << offset_);
      }

    // Data members.
    os_bool_reference ref_;
    size_t offset_;
  };


// Return my iterator category.
inline os_random_access_iterator_tag
os_iterator_category( const os_const_bool_iterator& )
  {
  return OS_RANDOM_ACCESS_ITERATOR_TAG;
  }


// Return my value type.
inline bool*
value_type( const os_const_bool_iterator& )
  {
  return (bool*)0;
  }


// Return my distance type.
inline ptrdiff_t*
distance_type( const os_const_bool_iterator& )
  {
  return (ptrdiff_t*)0;
  }




template<>
class OS_PUBLIC_STD os_vector OS_BOOL_ARG
{
  public:
    typedef bool                     value_type;
    typedef os_bool_reference        reference;
    typedef const os_bool_reference  const_reference;
    typedef size_t                   size_type;
    typedef ptrdiff_t                difference_type;
    typedef os_allocator< unsigned int >  allocator_type;
    typedef os_bool_iterator iterator;
    typedef os_const_bool_iterator const_iterator;

    typedef os_reverse_iterator
      <
      os_bool_iterator,
      bool,
      os_bool_reference,
      bool*,
      ptrdiff_t
      >  reverse_iterator;
    typedef os_reverse_iterator
      <
      os_const_bool_iterator,
      bool,
      const os_bool_reference,
      const bool*,
      ptrdiff_t
      >  const_reverse_iterator;

     // Construct me to be an empty vector.
    os_vector() :
      start_( os_bool_iterator() ),
      finish_( os_bool_iterator() ),
      end_of_storage_( 0 ),
      alloc_()
      {
      }

#   if ( __SUNPRO_CC == 0x500 )
      // Construct me to be an empty vector. //lg -- added extra hint for Sun CC5 compiler
      explicit os_vector<bool>( const allocator_type& alloc ) :
#   else
      explicit os_vector( const allocator_type& alloc ) :
#   endif
      start_( os_bool_iterator() ),
      finish_( os_bool_iterator() ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      }

    // Return a boolean vector that contains `n` copies of `b`
    // (default `false`).
    os_vector
      (
      size_type n,
      const bool& value = false,        // officially "=bool()", but that means false
      const allocator_type& alloc = allocator_type()
      ) :
      start_( os_bool_iterator() ),
      finish_( os_bool_iterator() ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      initialize( n );
      fill( start_.ref_.ptr_, end_of_storage_, (unsigned int)value ? ~0 : 0 );
      }

    // Construct myself to be a copy of `original`.
    os_vector( const os_vector OS_BOOL_ARG & original )
      {
      initialize( original.size() );
      copy( original.begin(), original.end(), start_ );
      }

    // Construct myself to hold a copy of the elements in the range
    // [`first`, `last`).
#   ifdef OS_NO_MEMBER_TEMPLATES
      os_vector
        (
        const bool* first,
        const bool* last,
        const allocator_type& alloc = allocator_type()
        ) :
        start_( os_bool_iterator() ),
        finish_( os_bool_iterator() ),
        end_of_storage_( 0 ),
        alloc_( alloc )
        {
        size_type n = last - first;
        initialize( n );
        copy( first, last, start_ );
        }

      os_vector
        (
        const_iterator first,
        const_iterator last,
        const allocator_type& alloc = allocator_type()
        ) :
#   else
      template< class InIt >
      os_vector
        (
        InIt first,
        InIt last,
        const allocator_type& alloc = allocator_type()
        ) :
#   endif
      start_( os_bool_iterator() ),
      finish_( os_bool_iterator() ),
      end_of_storage_( 0 ),
      alloc_( alloc )
      {
      size_type n = 0;
      distance( first, last, n );
      initialize( n );
      copy( first, last, start_ );
      }

    // Destroy me.
    ~os_vector()
      {
      clear();
      }

    // Replace my elements by a copy of the elements in `original`.
    os_vector OS_BOOL_ARG & operator=( const os_vector OS_BOOL_ARG & original )
      {
      if ( &original != this )
        {
        if ( original.size() > capacity() )
          {
          clear();
          initialize( original.size() );
          }
        copy( original.begin(), original.end(), begin() );
        finish_ = begin() + original.size();
        }
      return *this;
      }

    // Remove all my current elements, and then insert the elements
    // in range [`first`, `last`).
      void assign( const_iterator first, const_iterator last )
        {
        if ( first == begin() )
          erase( begin() + ( last - first ), end() );
        else
          assign_aux( first, last );
        }

#   ifndef OS_NO_MEMBER_TEMPLATES
      template< class InIt >
      void assign( InIt first, InIt last )
        {
        assign_aux( first, last );
        }
#   endif

    // Remove all my current elements, and then insert `n` copies of
    // `value`.
    void assign( size_type n, const bool& value )
      {
      if ( n > capacity() )
        {
        clear();
        insert( begin(), n, value );
        }
      else if ( size() >= n )
        {
        fill_n( begin(), n, value );
        erase( begin() + n, end() );
        }
      }

    // Return a copy of the allocator I am using.
    allocator_type get_allocator() const
      {
      return alloc_;
      }

    // Return a random access iterator positioned at my first element.
    iterator begin()
      {
      return start_;
      }

    // Return a constant random access iterator positioned at my first
    // element.
    const_iterator begin() const
      {
      return start_;
      }

    // Return a random access iterator positioned immediately after my
    // last element.
    iterator end()
      {
      return finish_;
      }

    // Return a constant random access iterator positioned immediately after
    // my last element.
    const_iterator end() const
      {
      return finish_;
      }

    // Return a random access reverse iterator positioned immediately after
    // my last element.
    reverse_iterator rbegin()
      {
      return reverse_iterator( end() );
      }

    // Return a constant random access reverse iterator positioned
    // immediately after my last element.
    const_reverse_iterator rbegin() const
      {
      return const_reverse_iterator( end() );
      }

    // Return a random access reverse iterator positioned at my first
    // element.
    reverse_iterator rend()
      {
      return reverse_iterator( begin() );
      }

    // Return a constant random access reverse iterator positioned at my
    // first element.
    const_reverse_iterator rend() const
      {
      return const_reverse_iterator( begin() );
      }

    // Return the number of elements that I contain.
    size_type size() const
      {
      return end() - begin();
      }

    // Return the maximum number of elements that I can contain.
    size_type max_size() const
      {
      return alloc_.max_size();
      }

    // Return true if I contain no elements.
    bool empty() const
      {
      return begin() == end();
      }

    // Cause myself to hold `n` elements, using `value` to expand
    // myself if necessary.
    void resize( size_type n, bool value = false )
      {
      if ( n > size() )
        insert( end(), n - size(), value );
      else
        erase( begin() + n, end() );
      }

    // Return the number of elements that I contain without allocating more
    // memory.
    size_type capacity() const
      {
      return os_const_bool_iterator( end_of_storage_, 0 ) - begin();
      }

    // Pre-allocate enough memory so that I can contain `n` elements without
    // allocating more memory.
    void reserve( size_type n )
      {
      if ( capacity() < n )
        {
        unsigned int* q = bit_alloc( n );
        iterator newfinish = copy
          (
          begin(),
          end(),
          os_bool_iterator( q, 0 )
          );
        clear();
        start_ = os_bool_iterator( q, 0 );
        finish_ = newfinish;
        end_of_storage_ = q + (n + OS_WORD_BIT - 1) / OS_WORD_BIT;
        }
      }

    // Return a reference to my `n`th element.
    reference operator[]( size_type n )
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      OS_ASSERT_INDEX_OK( n, 0, size() - 1 )
      return *( begin() + n );
      }

    // Return a constant reference to my `n`th element.
    const_reference operator[]( size_type n ) const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      OS_ASSERT_INDEX_OK( n, 0, size() - 1 )
      return *( begin() + n );
      }

    // Return a reference to my `n`th element.
    reference at( size_type n )
      {
      return operator[]( n );
      }

    // Return a constant reference to my `n`th element.
    const_reference at( size_type n ) const
      {
      return operator[]( n );
      }

    // Return a reference to my first element.
    reference front()
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *begin();
      }

    // Return a constant reference to my first element.
    const_reference front() const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *begin();
      }

    // Return a reference to my last element.
    reference back()
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *( end() - 1 );
      }

    // Return a constant reference to my last element.
    const_reference back() const
      {
      OS_ASSERT_NOT_EMPTY( empty() )
      return *( end() - 1 );
      }

    // Add `value` after my last element.
    void push_back( bool value )
      {
      if ( finish_.ref_.ptr_ != end_of_storage_ )
        {
        *finish_ = value;
        ++finish_;
        }
      else
        insert_aux( end(), value );
      }

    // Erase my last element.
    void pop_back()
      {
      OS_ASSERT_NOT_EMPTY_ELSE( empty() )
        --finish_;
      }

    // Insert `value` after the element with position `pos`. Return a
    // random access iterator positioned at the new element.
    iterator insert( iterator pos, bool value )
      {
      size_type n = pos - begin();
      if ( pos == end() )
        push_back( value );
      else
        insert_aux( pos, value );
      return begin() + n;
      }

    // Insert `n` copies of `value` at `pos`.
    void insert( iterator pos, size_type n, bool value );

    // Insert copies of the elements in range [`first`, `last`) at `pos`.
#   ifdef OS_NO_MEMBER_TEMPLATES
      void insert( iterator pos, const bool* first, const bool* last );
      void insert( iterator pos, const_iterator first, const_iterator last );
#   else
      template< class InIt >
      void insert( iterator pos, InIt first, InIt last );
#   endif

    // Erase the element at `pos`.
    iterator erase( iterator pos )
      {
      if ( !(pos + 1 == end()) )
        copy( pos + 1, end(), pos );
      --finish_;
      return pos;
      }

    // Erase the elements in range [`first`, `last`).
    iterator erase( iterator first, iterator last )
      {
      iterator i = copy( last, end(), first );
      finish_ = finish_ - ( last - first );
      return first;
      }

    // Swap my contents with those of `original`.
    void swap( os_vector OS_BOOL_ARG & original )
      {
#     ifdef OS_OSPACE_STD_NAMESPACE
        OS_STD swap( start_, original.start_ );
        OS_STD swap( finish_, original.finish_ );
        OS_STD swap( end_of_storage_, original.end_of_storage_ );
        OS_STD swap( alloc_, original.alloc_ );
#     else
        // Bug fix
        ::swap( start_, original.start_ );
        ::swap( finish_, original.finish_ );
        ::swap( end_of_storage_, original.end_of_storage_ );
        ::swap( alloc_, original.alloc_ );
#     endif
      }

    void clear()
      {
      destroy( start_.ref_.ptr_, end_of_storage_, alloc_ );
      alloc_.deallocate( start_.ref_.ptr_ );
      start_ = finish_ = os_bool_iterator();
      end_of_storage_ = 0;
      }

  protected:
    unsigned int* bit_alloc( size_type n )
      {
      size_type s = ( n + OS_WORD_BIT - 1 ) / OS_WORD_BIT;
      unsigned int* x = alloc_.allocate( s, this );
      uninitialized_fill_n( x, s, 0 );
      return x;
      }

#   ifdef OS_NO_MEMBER_TEMPLATES
      void assign_aux( const bool* first, const bool* last );
      void assign_aux( const_iterator first, const_iterator last );
#   else
      template< class InIt >
      void assign_aux( InIt first, InIt last );
#   endif

    void initialize( size_type n )
      {
      unsigned int* q = bit_alloc( n );
      end_of_storage_ = q + (n  + OS_WORD_BIT - 1) / OS_WORD_BIT;
      start_ = os_bool_iterator( q, 0 );
      finish_ = start_ + n;
      }

    void insert_aux( iterator position, bool value );

    iterator start_;
    iterator finish_;
    unsigned int* end_of_storage_;
    allocator_type alloc_;
  };

#undef OS_WORD_BIT
#undef OS_BOOL_ARG

#endif // OS_NO_BOOL

#endif // OS_BAD_INLINING


#if ( !defined AllocatorSet )
# undef Allocator
#endif


#ifdef OS_OSPACE_STD_NAMESPACE
    }
#endif

#ifdef OS_NO_AUTO_INSTANTIATE
# include <ospace/osstd/vector.cc>
#endif


#endif // OS_OSSTD_VECTOR_H