/***************************************************************************
 *
 * vector - declarations for the Standard Library vector class
 *
 * $Id: vector,v 1.75 1996/08/28 18:20:41 smithey Exp $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994-1996 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#ifndef __STD_VECTOR__
#define __STD_VECTOR__
//
//
//  Copyright Digital Equipment Corporation 1996. All rights reserved.
//
//  Restricted Rights: Use, duplication, or disclosure by the U.S.
//  Government is subject to restrictions as set forth in subparagraph
//  (c) (1) (ii) of DFARS 252.227-7013, or in FAR 52.227-19, or in FAR
//  52.227-14 Alt. III, as applicable.
//
//  This software is proprietary to and embodies the confidential
//  technology of Digital Equipment Corporation. Possession, use, or
//  copying of this software and media is authorized only pursuant to a
//  valid written license from Digital or an authorized sublicensor.
//
//
#include <stdcomp>
#include <stddefs>

#ifndef _RWSTD_HEADER_REQUIRES_HPP
#include <functional>
#include <iterator>
#include <algorithm>
#include <memory>
#include <stdexcept>
#else
#include <functional.hpp>
#include <iterator.hpp>
#include <algorithm.hpp>
#include <memory.hpp>
#include <stdexcept.hpp>
#endif

#ifndef vector
#define vector vector
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// Note that _RWSTD_SIMPLE_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp).
//
template <class T, class Allocator _RWSTD_SIMPLE_DEFAULT(allocator<T>) >
class vector
{
  public:
    //
    // Types.
    //
    typedef T                                          value_type;
    typedef Allocator                                  allocator_type;
    typedef _TYPENAME _RWSTD_ALLOC_SIZE_TYPE             size_type;
    typedef _TYPENAME _RWSTD_ALLOC_DIFF_TYPE             difference_type;

private:
#ifdef _RWSTD_ALLOCATOR
    typedef Allocator::rebind<T>::other value_alloc_type;
#else
    typedef allocator_interface<Allocator,T> value_alloc_type;
#endif

public:

    typedef _TYPENAME value_alloc_type::pointer          iterator;
    typedef _TYPENAME value_alloc_type::const_pointer    const_iterator;
    typedef _TYPENAME value_alloc_type::reference        reference;
    typedef _TYPENAME value_alloc_type::const_reference  const_reference;
  protected:
    typedef _TYPENAME value_alloc_type::pointer          pointer;
    typedef _TYPENAME value_alloc_type::const_pointer    const_pointer;

  public:

    typedef _STD::reverse_iterator<const_iterator, value_type, const_reference, 
                          const_pointer, difference_type>
                                                       const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator, value_type,
               reference, pointer, difference_type>
                                                       reverse_iterator;
  protected:

    allocator_type          the_allocator;
    iterator start;
    iterator finish;
    iterator end_of_storage;

    void insert_aux (iterator position, const T& x);

    void destroy(iterator start, iterator finish)
    {
       while ( start != finish)
          value_alloc_type(the_allocator).destroy(start++);
    }

  public:
    //
    // construct/copy/destroy
    //
    _EXPLICIT vector (const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) 
          : start(0), finish(0), end_of_storage(0), the_allocator(alloc) 
    { ; }

    //
    // Build a vector of size n with each element set to default for type T.
    // This requires that T have a default constructor.
    //
    _EXPLICIT vector (size_type n, const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
          : the_allocator(alloc)
    {
        start = value_alloc_type(the_allocator).allocate(n,0);
        T value;
        uninitialized_fill_n(start, n, value);
        finish = start + n;
        end_of_storage = finish;
    }
	
    //
    // Build a vector of size n with each element set to copy of value.
    //
    vector (size_type n, const T& value, 
                     const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
          : the_allocator(alloc)
    {
        start = value_alloc_type(the_allocator).allocate(n,0);
        uninitialized_fill_n(start, n, value);
        finish = start + n;
        end_of_storage = finish;
    }
	
#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    vector (void) 
          : start(0), finish(0), end_of_storage(0), the_allocator(Allocator()) 
    { ; }

    _EXPLICIT vector (size_type n)
          : the_allocator(Allocator())
    {
        start = value_alloc_type(the_allocator).allocate(n,0);
        T value;
        uninitialized_fill_n(start, n, value);
        finish = start + n;
        end_of_storage = finish;
    }

    vector (size_type n, const T& value) 
          : the_allocator(Allocator())
    {
        start = value_alloc_type(the_allocator).allocate(n,0);
        uninitialized_fill_n(start, n, value);
        finish = start + n;
        end_of_storage = finish;
    }
#endif

    vector (const vector<T,Allocator>& x)
    {
        the_allocator = x.get_allocator();
        start = value_alloc_type(the_allocator).allocate(x.end() - x.begin(),0);
        finish = uninitialized_copy(x.begin(), x.end(), start);
        end_of_storage = finish;
    }


#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class InputIterator>
    vector (InputIterator first, InputIterator last,
             const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
           : the_allocator(alloc)
     {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        start = value_alloc_type(the_allocator).allocate(n,0);
        finish = uninitialized_copy(first, last, start);
        end_of_storage = finish;
    }

#else
    vector (const_iterator first, const_iterator last,
             const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator()))
           : the_allocator(alloc)
     {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        start = value_alloc_type(the_allocator).allocate(n,0);
        finish = uninitialized_copy(first, last, start);
        end_of_storage = finish;
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    vector (const_iterator first, const_iterator last)
           : the_allocator(Allocator())
     {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        start = value_alloc_type(the_allocator).allocate(n,0);
        finish = uninitialized_copy(first, last, start);
        end_of_storage = finish;
    }
#endif
#endif

    ~vector ()
    { 
        destroy(start, finish); 
        value_alloc_type(the_allocator).deallocate(start);
    }
    vector<T,Allocator>& operator= (const vector<T,Allocator>& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator> 
    void assign (InputIterator first, InputIterator last)
#else
    void assign (const_iterator first, const_iterator last)
#endif
    {
        erase(begin(), end()); insert(begin(), first, last);
    }
    //
    // Assign n copies of default value of type T to vector.
    // This requires that T have a default constructor.
    //
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Size, class T>
    void assign (Size n)
#else
    void assign (size_type n)
#endif
    {
        erase(begin(), end()); insert(begin(), n, T());
    }
    //
    // Assign n copies of t to this vector.
    //
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Size, class T>
    void assign (Size n, const T& t)
#else
    void assign (size_type n, const T& t)
#endif
    {
        erase(begin(), end()); insert(begin(), n, t);
    }
    allocator_type get_allocator() const
    {
        return the_allocator;
    }

    //
    // Iterators.
    //
    iterator       begin ()       { return start;  }
    const_iterator begin () const { return start;  }
    iterator       end ()         { return finish; }
    const_iterator end ()   const { return finish; }

    reverse_iterator rbegin ()
    { 
        reverse_iterator tmp(end()); return tmp;
    }
    const_reverse_iterator rbegin () const
    { 
        const_reverse_iterator tmp(end()); return tmp;
    }
    reverse_iterator rend ()
    { 
        reverse_iterator tmp(begin()); return tmp;
    }
    const_reverse_iterator rend () const
    { 
        const_reverse_iterator tmp(begin()); return tmp;
    }

    //
    // Capacity.
    //
    size_type size ()     const { return size_type(end() - begin()); }
    size_type max_size () const { return value_alloc_type(the_allocator).max_size();   }
    void resize (size_type new_size);
    void resize (size_type new_size, T value);

    size_type capacity () const { return size_type(end_of_storage - begin()); }
    bool      empty ()    const { return begin() == end();                    }
    void reserve (size_type n)
    {
        if (capacity() < n)
        {
            value_alloc_type va(the_allocator);
            iterator tmp = va.allocate(n,start);
            uninitialized_copy(begin(), end(), tmp);
            destroy(start, finish);
            va.deallocate(start);
            finish = tmp + size();
            start = tmp;
            end_of_storage = begin() + n;
        }
    }

    //
    // Element access.
    //
    reference       operator[] (size_type n)       
    {
#ifdef _RWSTD_BOUNDS_CHECKING
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n);
#else
      return *(begin() + n);
#endif
    }
  
    const_reference operator[] (size_type n) const 
    {
#ifdef _RWSTD_BOUNDS_CHECKING
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n);
#else
      return *(begin() + n);
#endif
    }
  
      reference       at (size_type n)               
    { 
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n); 
    }
    const_reference at (size_type n)         const 
    { 
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n); 
    }
    reference       front ()                       { return *begin();       }
    const_reference front ()                 const { return *begin();       }
    reference       back ()                        { return *(end() - 1);   }
    const_reference back ()                  const { return *(end() - 1);   }

    //
    // Modifiers.
    //
    void push_back (const T& x)
    {
        if (finish != end_of_storage)
        {
            value_alloc_type(the_allocator).construct(finish, x); 
            finish++;
        }
        else
            insert_aux(end(), x);
    }
    void pop_back()
    {
        --finish; 
        value_alloc_type(the_allocator).destroy(finish);
    }
    //
    // Insert default value of type T at position.
    // Requires that T have a default constructor.
    //
    iterator insert (iterator position)
    {
        size_type n = position - begin();
        T x;
        if (finish != end_of_storage && position == end())
        {
            value_alloc_type(the_allocator).construct(finish, x); finish++;
        }
        else
            insert_aux(position, x);
        return begin() + n;
    }
    //
    // Insert x at position.
    //
    iterator insert (iterator position, const T& x)
    {
        size_type n = position - begin();
        if (finish != end_of_storage && position == end())
        {
            value_alloc_type(the_allocator).construct(finish, x); finish++;
        }
        else
            insert_aux(position, x);
        return begin() + n;
    }
    void insert (iterator position, size_type n, const T& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);
#else
    void insert (iterator position, const_iterator first, const_iterator last);
#endif

    void swap (vector<T,Allocator>& x)
    {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(start, x.start);
        std::swap(finish, x.finish);
        std::swap(end_of_storage, x.end_of_storage);
        std::swap(the_allocator,x.the_allocator);
#else
        ::swap(start, x.start);
        ::swap(finish, x.finish);
        ::swap(end_of_storage, x.end_of_storage);
        ::swap(the_allocator,x.the_allocator);
#endif
    }
    iterator erase (iterator position)
    {
        if (position + 1 != end()) copy(position + 1, end(), position);
        --finish;
        value_alloc_type(the_allocator).destroy(finish);
        return position;
    }
    iterator erase (iterator first, iterator last)
    {
        iterator i = copy(last, end(), first);
        destroy(i, finish);
        finish = finish - (last - first); 
        return first;
    }
    void clear()
    {
        erase(begin(),end());
    }
};

template <class T, class Allocator>
inline bool operator== (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class T, class Allocator>
inline bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
template <class T, class Allocator>
inline bool operator!= (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return !(x == y);
}

template <class T, class Allocator>
inline bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return y < x;
}

template <class T, class Allocator>
inline bool operator>= (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return !(x < y);
}

template <class T, class Allocator>
inline bool operator<= (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
{
    return !(y <  x);
}
#endif

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
template <class T, class Allocator>
void swap(vector<T,Allocator>& a, vector<T,Allocator>& b)
{
    a.swap(b);
}
#endif

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

/***************************************************************************
 *
 * vector.cc - Non-inline definitions for the Standard Library vector class
 *
 * $Id: vector.cc,v 1.3 1996/08/28 01:31:33 smithey Exp $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994-1996 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/
#include <stdcomp>

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// This requires that T have a default constructor.
//

template <class T, class Allocator>
void vector<T,Allocator>::resize (size_type new_size)
{
    T value;
    if (new_size > size())
        insert(end(), new_size - size(), value);
    else if (new_size < size())
        erase(begin() + new_size, end());
}

template <class T, class Allocator>
void vector<T,Allocator>::resize (size_type new_size, T value)
{
    if (new_size > size())
        insert(end(), new_size - size(), value);
    else if (new_size < size())
        erase(begin() + new_size, end());
}

template <class T, class Allocator>
vector<T,Allocator>& vector<T,Allocator>::operator= (const vector<T,Allocator>& x)
{
    if (&x == this) return *this;
    if (x.size() > capacity())
    {
        destroy(start, finish);
        value_alloc_type va(the_allocator);
        va.deallocate(start);
        start = va.allocate(x.end() - x.begin(),0);
        end_of_storage = uninitialized_copy(x.begin(), x.end(), start);
    }
    else if (size() >= x.size())
    {
        iterator i = copy(x.begin(), x.end(), begin());
        destroy(i, finish);
    }
    else
    {
        copy(x.begin(), x.begin() + size(), begin());
        uninitialized_copy(x.begin() + size(), x.end(), begin() + size());
    }
    finish = begin() + x.size();
    return *this;
}

template <class T, class Allocator>
void vector<T,Allocator>::insert_aux (
       vector<T,Allocator>::iterator position, const T& x)
{
    if (finish != end_of_storage)
    {
        value_alloc_type(the_allocator).construct(finish, *(finish - 1));
        copy_backward(position, finish - 1, finish);
        *position = x;
        ++finish;
    }
    else
    {
        //
        // We always allocate enough space for a number of additional
        // elements in the vector, unless the size of each element is
        // very large.
        //
        value_alloc_type va(the_allocator);
        const size_type CHUNKSIZE = sizeof(T) >= 1024 ? 1 : 1024 / sizeof(T);
        size_type len = size() ? 2 * size() : CHUNKSIZE;
        iterator tmp = va.allocate(len,start);
        uninitialized_copy(begin(), position, tmp);
        va.construct((tmp + (position - begin())), x);
        uninitialized_copy(position, end(), tmp + (position - begin()) + 1); 
        destroy(begin(), end());
        va.deallocate(begin());
        end_of_storage = tmp + len;
        finish = tmp + size() + 1;
        start = tmp;
    }
}

template <class T, class Allocator>
void vector<T,Allocator>::insert (
         vector<T,Allocator>::iterator position, size_type n, const T& x)
{
    if (n == 0) return;
    if ((size_type)(end_of_storage - finish) >= n)
    {
        if ((size_type)(end() - position) > n)
        {
            uninitialized_copy(end() - n, end(), end());
            copy_backward(position, end() - n, end());
#ifdef _RWSTD_FILL_NAME_CLASH
            std_fill(position, position + n, x);
#else
            fill(position, position + n, x);
#endif
        }
        else
        {
            uninitialized_copy(position, end(), position + n);
#ifdef _RWSTD_FILL_NAME_CLASH
            std_fill(position, end(), x);
#else
            fill(position, end(), x);
#endif
            uninitialized_fill_n(end(), n - (end() - position), x);
        }
        finish += n;
    }
    else
    {
        value_alloc_type va(the_allocator);
        size_type len = size() + max(size(), n);
        iterator tmp = va.allocate(len,start);
        uninitialized_copy(begin(), position, tmp);
        uninitialized_fill_n(tmp + (position - begin()), n, x);
        uninitialized_copy(position, end(), tmp + (position - begin() + n));
        destroy(begin(), end());
        va.deallocate(begin());
        end_of_storage = tmp + len;
        finish = tmp + size() + n;
        start = tmp;
    }
}

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class T, class Allocator>
template<class InputIterator>
void vector<T,Allocator>::insert (
                 vector<T,Allocator>::iterator position, 
                 InputIterator first, InputIterator last)
#else
template<class T, class Allocator>
void vector<T,Allocator>::insert (
                        vector<T,Allocator>::iterator position, 
                        const_iterator first,
                        const_iterator last)
#endif
{
    if (first == last) return;
    size_type n;
    __initialize(n, size_type(0));
    distance(first, last, n);
    if ((size_type)(end_of_storage - finish) >= n)
    {
        if ((size_type)(end() - position) > n)
        {
            uninitialized_copy(end() - n, end(), end());
            copy_backward(position, end() - n, end());
            copy(first, last, position);
        }
        else
        {
            uninitialized_copy(position, end(), position + n);
            copy(first, first + (end() - position), position);
            uninitialized_copy(first + (end() - position), last, end());
        }
        finish += n;
    }
    else
    {
        value_alloc_type va(the_allocator);
        size_type len = size() + max(size(), n);
        iterator tmp = va.allocate(len,start);
        uninitialized_copy(begin(), position, tmp);
        uninitialized_copy(first, last, tmp + (position - begin()));
        uninitialized_copy(position, end(), tmp + (position - begin() + n));
        destroy(begin(), end());
        va.deallocate(begin());
        end_of_storage = tmp + len;
        finish = tmp + size() + n;
        start = tmp;
    }
}



#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// If bool is a builtin type, we provide a vector<bool,allocator> specialization.
// We do not provide the allocator interface for this specialization.
//
#ifndef _RWSTD_NO_BOOL

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

class _RWSTDExport vector<bool, allocator<bool> >
{
  public:
    //
    // types
    //
    typedef allocator<bool>                             allocator_type;
    typedef bool                                        value_type;

  private:
#ifdef _RWSTD_ALLOCATOR
    typedef allocator<bool>::rebind<unsigned int>::other value_alloc_type;
#else
    typedef allocator_interface<allocator_type,unsigned int> value_alloc_type;
#endif

  public:
#ifdef _RWSTD_NO_EMBEDDED_TYPEDEF
    typedef allocator<bool>::size_type               size_type;
    typedef allocator<bool>::difference_type         difference_type;
#else
    typedef allocator_type::size_type          size_type;
    typedef allocator_type::difference_type    difference_type;
#endif

  protected:
    typedef value_alloc_type::pointer       pointer;
    typedef value_alloc_type::const_pointer const_pointer;

  public:

    //
    // forward declarations
    //
    class iterator;
    class const_iterator;

    //
    // bit reference
    //
    class reference
    {
        friend class iterator;
        friend class const_iterator;
      __DECPROTECTED:
        unsigned int* p;
        unsigned int mask;
        reference (unsigned int* x, unsigned int y) : p(x), mask(y) {}
      public:
        reference () : p(0), mask(0) {}
        operator bool () const { return !(!(*p & mask)); }
        reference& operator= (bool x)
        {
            if (x)      
                *p |= mask;
            else
                *p &= ~mask;
            return *this;
        }
        reference& operator= (const reference& x) { return *this = bool(x); }
        bool operator== (const reference& x) const
        {
            return bool(*this) == bool(x);
        }
        bool operator< (const reference& x) const
        {
            return bool(*this) < bool(x);
        }
        bool operator!= (const reference& x) const
        {
            return !(*this == x);
        }
        bool operator> (const reference& x) const
        {
            return  x < *this;
        }
         bool operator>= (const reference& x) const
        {
            return !(*this < x);
        }
        bool operator<= (const reference& x) const
        {
            return !(*this > x);
        }
        void flip () { *p ^= mask; }
    };
    
    typedef bool const_reference;
    //
    // Definition of our iterator.
    //
    class iterator : public random_access_iterator<bool, difference_type>
    {
        friend class vector<bool,allocator<bool> >;
        friend class const_iterator;

      __DECPROTECTED:

        unsigned int* p;
        unsigned int  offset;

        void bump_up ()
        {
            if (offset++ == __WORD_BIT - 1)
            {
                offset = 0; ++p;
            }
        }
        void bump_down ()
        {
            if (offset-- == 0)
            {
                offset = __WORD_BIT - 1; --p;
            }
        }

      public:
        iterator () : p(0), offset(0) {}
        iterator (unsigned int* x, unsigned int y) : p(x), offset(y) {}

        reference operator* () const { return reference(p, 1U << offset); }
        iterator& operator++ ()
        {
            bump_up(); return *this;
        }
        iterator operator++ (int)
        {
            iterator tmp = *this; bump_up(); return tmp;
        }
        iterator& operator-- ()
        {
            bump_down(); return *this;
        }
        iterator operator-- (int)
        {
            iterator tmp = *this; bump_down(); return tmp;
        }
        iterator& operator+= (difference_type i)
        {
            difference_type n = i + offset;
            p += n / __WORD_BIT;
            n = n % __WORD_BIT;
            if (n < 0)
            {
                offset = n + __WORD_BIT; --p;
            }
            else
                offset = n;
            return *this;
        }
        iterator& operator-= (difference_type i)
        {
            *this += -i; return *this;
        }
        iterator operator+ (difference_type i) const
        {
            iterator tmp = *this; return tmp += i;
        }
        iterator operator- (difference_type i) const
        {
            iterator tmp = *this; return tmp -= i;
        }
        difference_type operator- (iterator x) const
        {
            return __WORD_BIT * (p - x.p) + offset - x.offset;
        }
        reference operator[] (difference_type i)
        {
            return *(*this + i);
        }
        bool operator== (const iterator& x) const
        {
            return p == x.p && offset == x.offset;
        }
        bool operator< (const iterator& x) const
        {
            return p < x.p || (p == x.p && offset < x.offset);
        }
        bool operator!= (const iterator& x) const
        {
            return !(*this == x);
        }
        bool operator> (const iterator& x) const
        {
            return x < *this;
        }
         bool operator>= (const iterator& x) const
        {
            return !(*this < x);
        }
        bool operator<= (const iterator& x) const
        {
            return !(*this > x);
        }
    };
    //
    // Definition of our const_iterator.
    //
    class const_iterator
        : public random_access_iterator<bool, difference_type>
    {
        friend class vector<bool,allocator<bool> >;

      __DECPROTECTED:

        unsigned int* p;
        unsigned int offset;
        void bump_up ()
        {
            if (offset++ == __WORD_BIT - 1)
            {
                offset = 0; ++p;
            }
        }
        void bump_down()
        {
            if (offset-- == 0)
            {
                offset = __WORD_BIT - 1; --p;
            }
        }

      public:
        const_iterator () : p(0), offset(0) {}
        const_iterator (unsigned int* x, unsigned int y) : p(x), offset(y) {}
        const_iterator (const vector<bool,allocator<bool> >::iterator& x) : p(x.p), offset(x.offset) {}

        const_reference operator* () const
        {
            return reference(p, 1U << offset);
        }
        const_iterator& operator++ ()
        {
            bump_up(); return *this;
        }
        const_iterator operator++ (int)
        {
            const_iterator tmp = *this; bump_up(); return tmp;
        }
        const_iterator& operator-- ()
        {
            bump_down(); return *this;
        }
        const_iterator operator-- (int)
        {
            const_iterator tmp = *this; bump_down(); return tmp;
        }
        const_iterator& operator+= (difference_type i)
        {
            difference_type n = i + offset;
            p += n / __WORD_BIT;
            n = n % __WORD_BIT;
            if (n < 0)
            {
                offset = n + __WORD_BIT; --p;
            }
            else
                offset = n;
            return *this;
        }
        const_iterator& operator-= (difference_type i)
        {
            *this += -i; return *this;
        }
        const_iterator operator+ (difference_type i) const
        {
            const_iterator tmp = *this; return tmp += i;
        }
        const_iterator operator- (difference_type i) const
        {
            const_iterator tmp = *this; return tmp -= i;
        }
        difference_type operator- (const_iterator x) const
        {
            return __WORD_BIT * (p - x.p) + offset - x.offset;
        }
        const_reference operator[] (difference_type i)
        { 
            return *(*this + i); 
        }
        bool operator== (const const_iterator& x) const
        {
            return p == x.p && offset == x.offset;
        }
        bool operator< (const const_iterator& x) const
        {
            return p < x.p || (p == x.p && offset < x.offset);
        }
        bool operator!= (const const_iterator& x) const
        {
            return !(*this == x);
        }
        bool operator> (const const_iterator& x) const
        {
            return x < *this;
        }
         bool operator>= (const const_iterator& x) const
        {
            return !(*this < x);
        }
        bool operator<= (const const_iterator& x) const
        {
            return !(*this > x);
        }
    };
    //
    // types
    //
    typedef _STD::reverse_iterator<const_iterator,
                             value_type,
                             const_reference, const_pointer,
                             difference_type> const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator,
                             value_type,
                             reference, pointer,
                             difference_type> reverse_iterator;
  protected:

    allocator_type          the_allocator;
    iterator                start;
    iterator                finish;
    unsigned int*           end_of_storage;

    unsigned int* bit_alloc (size_type n)
    {
        return value_alloc_type(the_allocator).allocate((n + __WORD_BIT - 1)/__WORD_BIT,start.p);
    }
    void initialize (size_type n)
    {
        unsigned int* q = bit_alloc(n);
        end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
        start = iterator(q, 0);
        finish = start + n;
    }
    void insert_aux (iterator position, bool x);

  public:

    //
    // construct/copy/destroy
    //
    vector ()
        : start(iterator()), finish(iterator()), end_of_storage(0) {}
    _EXPLICIT vector (size_type n, bool value = bool())
    {
        initialize(n); 
#ifdef _RWSTD_FILL_NAME_CLASH
        std_fill(start.p, end_of_storage, value ? ~0 : 0);
#else
        fill(start.p, end_of_storage, value ? ~0 : 0);
#endif
    }
    vector (const vector<bool,allocator<bool> >& x)
    {
        initialize(x.size()); copy(x.begin(), x.end(), start);
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template<class InputIterator>
    vector (InputIterator first, InputIterator last)
    {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        initialize(n);
        copy(first, last, start);
    }
#else
    vector (const_iterator first, const_iterator last)
    {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        initialize(n);
        copy(first, last, start);
    }
    vector (const bool* first, const bool* last)
    {
        size_type n;
        __initialize(n, size_type(0));
        distance(first, last, n);
        initialize(n);
        copy(first, last, start);
    }
#endif
    ~vector () { value_alloc_type(the_allocator).deallocate(start.p); }
    vector& operator= (const vector<bool,allocator<bool> >& x)
    {
        if (&x == this) return *this;
        if (x.size() > capacity())
        {
            value_alloc_type(the_allocator).deallocate(start.p); 
            initialize(x.size());
        }
        copy(x.begin(), x.end(), begin());
        finish = begin() + x.size();
        return *this;
    }
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void assign (InputIterator first, InputIterator last)
#else
    void assign (const_iterator first, const_iterator last)
#endif
    {
        erase(begin(), end()); insert(begin(), first, last);
    }
 
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class Size, class T>
    void assign (Size n, const bool& t = bool())
#else
    void assign (size_type n, const bool& t = bool())
#endif
    {
        erase(begin(), end()); insert(begin(), n, t);
    }
    allocator_type get_allocator() const
    {
        return the_allocator;
    }

    //
    // iterators
    //
    iterator       begin ()       { return start; }
    const_iterator begin () const { return start; }
    iterator       end   ()       { return finish; }
    const_iterator end   () const { return finish; }

    reverse_iterator       rbegin () { return reverse_iterator(end()); }
    const_reverse_iterator rbegin () const
    { 
        return const_reverse_iterator(end()); 
    }
    reverse_iterator       rend () { return reverse_iterator(begin()); }
    const_reverse_iterator rend () const
    { 
        return const_reverse_iterator(begin()); 
    }

    //
    // capacity
    //
    size_type size     () const { return size_type(end() - begin());  }
    size_type max_size () const { return value_alloc_type(the_allocator).max_size(); }
    void resize (size_type new_size, bool c = false);
    size_type capacity () const
    {
        return size_type(const_iterator(end_of_storage, 0) - begin());
    }
    bool empty () const { return begin() == end(); }
    void reserve (size_type n)
    {
        if (capacity() < n)
        {
            unsigned int* q = bit_alloc(n);
            finish = copy(begin(), end(), iterator(q, 0));
            value_alloc_type(the_allocator).deallocate(start.p);
            start = iterator(q, 0);
            end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
        }
    }

    //
    // element access
    //
    reference       operator[] (size_type n)       { return *(begin() + n); }
    const_reference operator[] (size_type n) const { return *(begin() + n); }
    reference       at (size_type n)               
    { 
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n); 
    }
    const_reference at (size_type n)         const 
    {
      _RWSTD_THROW(n >= size(), out_of_range, __RWSTD::rwse_OutOfRange);
      return *(begin() + n); 
    }
    reference       front ()       { return *begin();     }
    const_reference front () const { return *begin();     }
    reference       back  ()       { return *(end() - 1); }
    const_reference back  () const { return *(end() - 1); }
    
    //
    // modifiers
    //
    void push_back (const bool& x)
    {
        if (finish.p != end_of_storage)
            *finish++ = x;
        else
            insert_aux(end(), x);
    }
    void pop_back () { --finish; }
    iterator insert (iterator position, const bool& x = bool())
    {
        size_type n = position - begin();
        if (finish.p != end_of_storage && position == end())
            *finish++ = x;
        else
            insert_aux(position, x);
        return begin() + n;
    }
    void insert (iterator position, size_type n, const bool& x);

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);
#else
    void insert (iterator position, const_iterator first, 
                 const_iterator last);
#endif

    iterator erase (iterator position)
    {
#ifndef _RWSTD_NO_NAMESPACE
        using namespace rel_ops;
#endif
        if (position + 1 != end())
            copy(position + 1, end(), position);
        --finish;
        return position;
    }
    iterator erase(iterator first, iterator last)
    {
        finish = copy(last, end(), first);
        return first;
    }
    void swap (vector<bool,allocator<bool> >& x)
    {
#ifndef _RWSTD_NO_NAMESPACE
        std::swap(start,          x.start);
        std::swap(finish,         x.finish);
        std::swap(the_allocator,  x.the_allocator);
        std::swap(end_of_storage, x.end_of_storage);
#else
        ::swap(start,          x.start); 
        ::swap(finish,         x.finish);
        ::swap(the_allocator,  x.the_allocator);
        ::swap(end_of_storage, x.end_of_storage);
#endif
    }
    static void swap(reference x, reference y);
    void flip ();
    void clear()
    {
        erase(begin(),end());
    }
};

inline bool operator== (const vector<bool,allocator<bool> >& x, 
                        const vector<bool,allocator<bool> >& y)
{
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

inline bool operator< (const vector<bool,allocator<bool> >& x, 
                       const vector<bool,allocator<bool> >& y)
{
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
inline bool operator!= (const vector<bool,allocator<bool> >& x, 
                        const vector<bool,allocator<bool> >& y)
{
    return !(x == y);
}

inline bool operator> (const vector<bool,allocator<bool> >& x, 
                       const vector<bool,allocator<bool> >& y)
{
    return y < x;
}

inline bool operator>= (const vector<bool,allocator<bool> >& x, 
                        const vector<bool,allocator<bool> >& y)
{
    return !(x < y);
}

inline bool operator<= (const vector<bool,allocator<bool> >& x, 
                        const vector<bool,allocator<bool> >& y)
{
    return !(y <  x);
}
#endif

inline void swap(vector<bool,allocator<bool> >& a, vector<bool,allocator<bool> >& b)
{
    a.swap(b);
}

#undef __WORD_BIT

#else

// vector<bool> is replaced by bit_vector at present because bool is not
// implemented.  

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

class bit_vector {
public:
    typedef allocator<unsigned int> allocator_type;
    typedef bool value_type;
    typedef allocator_type::size_type size_type;
    typedef allocator_type::difference_type difference_type; 
    typedef bool* pointer;
    typedef const bool* const_pointer;

    class iterator;
    class const_iterator;

private:
#ifdef _RWSTD_ALLOCATOR
    typedef allocator<unsigned int>::rebind<unsigned int>::other value_alloc_type;
#else
    typedef allocator_interface<allocator_type,unsigned int> value_alloc_type;
#endif

public:
    class reference {
    friend class iterator;
    friend class const_iterator;
    __DECPROTECTED:
	unsigned int* p;
	unsigned int mask;
	reference(unsigned int* x, unsigned int y) : p(x), mask(y) {}
    public:
	reference() : p(0), mask(0) {}
	operator bool() const { return !(!(*p & mask)); }
	reference& operator=(bool x) {
	    if (x)      
		*p |= mask;
	    else 
		*p &= ~mask;
	    return *this;
	}
	reference& operator=(const reference& x) { return *this = bool(x); }
	bool operator==(const reference& x) const {
	    return bool(*this) == bool(x);
	}
	bool operator<(const reference& x) const {
	    return bool(*this) < bool(x);
	}
	void flip() { *p ^= mask; }
    };
    typedef bool const_reference;
    class iterator : public random_access_iterator<bool, difference_type> {
    friend class bit_vector;
    friend class const_iterator;
    __DECPROTECTED:
	unsigned int* p;
	unsigned int offset;
	void bump_up() {
	    if (offset++ == __WORD_BIT - 1) {
		offset = 0;
		++p;
	    }
	}
    void bump_down() {
	if (offset-- == 0) {
	    offset = __WORD_BIT - 1;
	    --p;
	}
    }
    public:
	iterator() : p(0), offset(0) {}
	iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
	reference operator*() const { return reference(p, 1U << offset); }
	reference* operator->() const { reference r=reference(p, 1U << offset);
					return &r; } 
	iterator& operator++() {
	    bump_up();
	    return *this;
	}
	iterator operator++(int) {
	    iterator tmp = *this;
	    bump_up();
	    return tmp;
	}
	iterator& operator--() {
	    bump_down();
	    return *this;
	}
	iterator operator--(int) {
	    iterator tmp = *this;
	    bump_down();
	    return tmp;
	}
	iterator& operator+=(difference_type i) {
	    difference_type n = i + offset;
	    p += n / __WORD_BIT;
	    n = n % __WORD_BIT;
	    if (n < 0) {
		offset = n + __WORD_BIT;
		--p;
	    } else
		offset = n;
	    return *this;
	}
	iterator& operator-=(difference_type i) {
	    *this += -i;
	    return *this;
	}
	iterator operator+(difference_type i) const {
	    iterator tmp = *this;
	    return tmp += i;
	}
	iterator operator-(difference_type i) const {
	    iterator tmp = *this;
	    return tmp -= i;
	}
	difference_type operator-(iterator x) const {
	    return __WORD_BIT * (p - x.p) + offset - x.offset;
	}
	reference operator[](difference_type i) { return *(*this + i); }
	bool operator==(const iterator& x) const {
	    return p == x.p && offset == x.offset;
	}
	bool operator<(iterator x) const {
	    return p < x.p || (p == x.p && offset < x.offset);
	}
    };

    class const_iterator 
	: public random_access_iterator<bool, difference_type> {
    friend class bit_vector;
    __DECPROTECTED:
	unsigned int* p;
	unsigned int offset;
	void bump_up() {
	    if (offset++ == __WORD_BIT - 1) {
		offset = 0;
		++p;
	    }
	}
    void bump_down() {
	if (offset-- == 0) {
	    offset = __WORD_BIT - 1;
	    --p;
	}
    }
    public:
	const_iterator() : p(0), offset(0) {}
	const_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {}
	const_iterator(const iterator& x) : p(x.p), offset(x.offset) {}
	const_reference operator*() const {
	    return reference(p, 1U << offset);
	}
	const_iterator& operator++() {
	    bump_up();
	    return *this;
	}
	const_iterator operator++(int) {
	    const_iterator tmp = *this;
	    bump_up();
	    return tmp;
	}
	const_iterator& operator--() {
	    bump_down();
	    return *this;
	}
	const_iterator operator--(int) {
	    const_iterator tmp = *this;
	    bump_down();
	    return tmp;
	}
	const_iterator& operator+=(difference_type i) {
	    difference_type n = i + offset;
	    p += n / __WORD_BIT;
	    n = n % __WORD_BIT;
	    if (n < 0) {
		offset = n + __WORD_BIT;
		--p;
	    } else
		offset = n;
	    return *this;
	}
	const_iterator& operator-=(difference_type i) {
	    *this += -i;
	    return *this;
	}
	const_iterator operator+(difference_type i) const {
	    const_iterator tmp = *this;
	    return tmp += i;
	}
	const_iterator operator-(difference_type i) const {
	    const_iterator tmp = *this;
	    return tmp -= i;
	}
	difference_type operator-(const_iterator x) const {
	    return __WORD_BIT * (p - x.p) + offset - x.offset;
	}
	const_reference operator[](difference_type i) { 
	    return *(*this + i); 
	}
	bool operator==(const const_iterator& x) const {
	    return p == x.p && offset == x.offset;
	}
	bool operator<(const_iterator x) const {
	    return p < x.p || (p == x.p && offset < x.offset);
	}
    };

    typedef _STD::reverse_iterator<const_iterator, value_type, const_reference, 
                            const_pointer, difference_type> const_reverse_iterator;
    typedef _STD::reverse_iterator<iterator, value_type, reference, pointer, difference_type> reverse_iterator;
protected:
    allocator<unsigned int> bvector_allocator;
    iterator start;
    iterator finish;
    unsigned int* end_of_storage;
    unsigned int* bit_alloc(size_type n) {
	return value_alloc_type(bvector_allocator).allocate((n + __WORD_BIT - 1)/__WORD_BIT);
    }
    void initialize(size_type n) {
	unsigned int* q = bit_alloc(n);
	end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
	start = iterator(q, 0);
	finish = start + n;
    }
    void insert_aux(iterator position, bool x) {
	if (finish.p != end_of_storage) {
	    copy_backward(position, finish - 1, finish);
	    *position = x;
	    ++finish;
    	} else {
	    size_type len = size() ? 2 * size() : __WORD_BIT;
	    unsigned int* q = bit_alloc(len);
	    iterator i = copy(begin(), position, iterator(q, 0));
	    *i++ = x;
	    finish = copy(position, end(), i);
	    bvector_allocator.deallocate(start.p);
	    end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT;
	    start = iterator(q, 0);
	}
    }
    typedef bit_vector self;
public:
    iterator begin() { return start; }
    const_iterator begin() const { return start; }
    iterator end() { return finish; }
    const_iterator end() const { return finish; }

    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { 
        return const_reverse_iterator(end()); 
    }

    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { 
        return const_reverse_iterator(begin()); 
    }

    size_type size() const { return size_type(end() - begin()); }
    size_type max_size() const { return value_alloc_type(bvector_allocator).max_size(); }
    size_type capacity() const {
	return size_type(const_iterator(end_of_storage, 0) - begin());
    }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    const_reference operator[](size_type n) const { return *(begin() + n); }
    bit_vector() : start(iterator()), finish(iterator()), end_of_storage(0) {}
    _EXPLICIT bit_vector(size_type, bool = false); 
    bit_vector(const self& x) {
	initialize(x.size());
	copy(x.begin(), x.end(), start);
    }
    bit_vector(const_iterator first, const_iterator last) {
	size_type n = 0;
	distance(first, last, n);
	initialize(n);
	copy(first, last, start);
    }
    ~bit_vector() { bvector_allocator.deallocate(start.p); }
    self& operator=(const self& x) {
	if (&x == this) return *this;
	if (x.size() > capacity()) {
	    bvector_allocator.deallocate(start.p); 
	    initialize(x.size());
	}
	copy(x.begin(), x.end(), begin());
	finish = begin() + x.size();
	return *this;
    }
    void reserve(size_type n) {
	if (capacity() < n) {
	    unsigned int* q = bit_alloc(n);
	    finish = copy(begin(), end(), iterator(q, 0));
	    bvector_allocator.deallocate(start.p);
	    start = iterator(q, 0);
	    end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT;
	}
    }
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *(end() - 1); }
    const_reference back() const { return *(end() - 1); }
    void push_back(bool x) {
	if (finish.p != end_of_storage)
	    *finish++ = x;
	else
	    insert_aux(end(), x);
    }
    void swap(bit_vector& x) {
	::swap(start, x.start);
	::swap(finish, x.finish);
	::swap(end_of_storage, x.end_of_storage);
	::swap(bvector_allocator, x.bvector_allocator);
    }
    iterator insert(iterator position, bool x) {
	size_type n = position - begin();
	if (finish.p != end_of_storage && position == end())
	    *finish++ = x;
	else
	    insert_aux(position, x);
	return begin() + n;
    }
    void insert(iterator position, const_iterator first, 
		const_iterator last);
    void insert(iterator position, size_type n, bool x);
    void pop_back() { --finish; }
    iterator erase(iterator position) {
    	size_type n = 0;
    	distance(start, position, n);
	if (position + 1 != end())
	    copy(position + 1, end(), position);
	--finish;
	return start + n;
    }
    iterator erase(iterator first, iterator last) {
    	size_type n = 0;
    	distance(start, first, n);
	finish = copy(last, end(), first);
	return start + n;
    }
    void clear() { erase(begin(),end()); }
};

inline bool operator==(const bit_vector& x, const bit_vector& y) {
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

inline bool operator<(const bit_vector& x, const bit_vector& y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

#undef __WORD_BIT

#endif /*_RWSTD_NO_BOOL*/

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#undef vector

#endif /*__STD_VECTOR__*/