code:
// The template and inlines for the -*- C++ -*- internal _Meta class.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file valarray_before.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

// Written by Gabriel Dos Reis <Gabriel.Dos-Reis@cmla.ens-cachan.fr>

#ifndef _VALARRAY_BEFORE_H
#define _VALARRAY_BEFORE_H 1

#pragma GCC system_header

#include <bits/slice_array.h>

_GLIBCXX_BEGIN_NAMESPACE(std)

  //
  // Implementing a loosened valarray return value is tricky.
  // First we need to meet 26.3.1/3: we should not add more than
  // two levels of template nesting. Therefore we resort to template
  // template to "flatten" loosened return value types.
  // At some point we use partial specialization to remove one level
  // template nesting due to _Expr<>
  //

  // This class is NOT defined. It doesn't need to.
  template<typename _Tp1, typename _Tp2> class _Constant;

  // Implementations of unary functions applied to valarray<>s.
  // I use hard-coded object functions here instead of a generic
  // approach like pointers to function:
  //    1) correctness: some functions take references, others values.
  //       we can't deduce the correct type afterwards.
  //    2) efficiency -- object functions can be easily inlined
  //    3) be Koenig-lookup-friendly

  struct __abs
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return abs(__t); }
  };

  struct __cos
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return cos(__t); }
  };

  struct __acos
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return acos(__t); }
  };

  struct __cosh
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return cosh(__t); }
  };

  struct __sin
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return sin(__t); }
  };

  struct __asin
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return asin(__t); }
  };

  struct __sinh
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return sinh(__t); }
  };

  struct __tan
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return tan(__t); }
  };

  struct __atan
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return atan(__t); }
  };

  struct __tanh
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return tanh(__t); }
  };

  struct __exp
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return exp(__t); }
  };

  struct __log
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return log(__t); }
  };

  struct __log10
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return log10(__t); }
  };

  struct __sqrt
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return sqrt(__t); }
  };

  // In the past, we used to tailor operator applications semantics
  // to the specialization of standard function objects (i.e. plus<>, etc.)
  // That is incorrect.  Therefore we provide our own surrogates.

  struct __unary_plus
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return +__t; }
  };

  struct __negate
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return -__t; }
  };

  struct __bitwise_not
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __t) const
      { return ~__t; }
  };

  struct __plus
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x + __y; }
  };

  struct __minus
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x - __y; }
  };

  struct __multiplies
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x * __y; }
  };

  struct __divides
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x / __y; }
  };

  struct __modulus
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x % __y; }
  };

  struct __bitwise_xor
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x ^ __y; }
  };

  struct __bitwise_and
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x & __y; }
  };

  struct __bitwise_or
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x | __y; }
  };

  struct __shift_left
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x << __y; }
  };

  struct __shift_right
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return __x >> __y; }
  };

  struct __logical_and
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x && __y; }
  };

  struct __logical_or
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x || __y; }
  };

  struct __logical_not
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x) const { return !__x; }
  };

  struct __equal_to
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x == __y; }
  };

  struct __not_equal_to
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x != __y; }
  };

  struct __less
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
  };

  struct __greater
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
  };

  struct __less_equal
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x <= __y; }
  };

  struct __greater_equal
  {
    template<typename _Tp>
      bool operator()(const _Tp& __x, const _Tp& __y) const
      { return __x >= __y; }
  };

  // The few binary functions we miss.
  struct __atan2
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return atan2(__x, __y); }
  };

  struct __pow
  {
    template<typename _Tp>
      _Tp operator()(const _Tp& __x, const _Tp& __y) const
      { return pow(__x, __y); }
  };

  // We need these bits in order to recover the return type of
  // some functions/operators now that we're no longer using
  // function templates.
  template<typename, typename _Tp>
    struct __fun
    {
      typedef _Tp result_type;
    };

  // several specializations for relational operators.
  template<typename _Tp>
    struct __fun<__logical_not, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__logical_and, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__logical_or, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__less, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__greater, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__less_equal, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__greater_equal, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__equal_to, _Tp>
    {
      typedef bool result_type;
    };

  template<typename _Tp>
    struct __fun<__not_equal_to, _Tp>
    {
      typedef bool result_type;
    };

  //
  // Apply function taking a value/const reference closure
  //

  template<typename _Dom, typename _Arg>
    class _FunBase
    {
    public:
      typedef typename _Dom::value_type value_type;

      _FunBase(const _Dom& __e, value_type __f(_Arg))
      : _M_expr(__e), _M_func(__f) {}

      value_type operator[](size_t __i) const
      { return _M_func (_M_expr[__i]); }

      size_t size() const { return _M_expr.size ();}

    private:
      const _Dom& _M_expr;
      value_type (*_M_func)(_Arg);
    };

  template<class _Dom>
    struct _ValFunClos<_Expr,_Dom> : _FunBase<_Dom, typename _Dom::value_type>
    {
      typedef _FunBase<_Dom, typename _Dom::value_type> _Base;
      typedef typename _Base::value_type value_type;
      typedef value_type _Tp;

      _ValFunClos(const _Dom& __e, _Tp __f(_Tp)) : _Base(__e, __f) {}
    };

  template<typename _Tp>
    struct _ValFunClos<_ValArray,_Tp> : _FunBase<valarray<_Tp>, _Tp>
    {
      typedef _FunBase<valarray<_Tp>, _Tp> _Base;
      typedef _Tp value_type;

      _ValFunClos(const valarray<_Tp>& __v, _Tp __f(_Tp)) : _Base(__v, __f) {}
    };

  template<class _Dom>
    struct _RefFunClos<_Expr, _Dom>
    : _FunBase<_Dom, const typename _Dom::value_type&>
    {
      typedef _FunBase<_Dom, const typename _Dom::value_type&> _Base;
      typedef typename _Base::value_type value_type;
      typedef value_type _Tp;

      _RefFunClos(const _Dom& __e, _Tp __f(const _Tp&))
      : _Base(__e, __f) {}
    };

  template<typename _Tp>
    struct _RefFunClos<_ValArray, _Tp>
    : _FunBase<valarray<_Tp>, const _Tp&>
    {
      typedef _FunBase<valarray<_Tp>, const _Tp&> _Base;
      typedef _Tp value_type;

      _RefFunClos(const valarray<_Tp>& __v, _Tp __f(const _Tp&))
      : _Base(__v, __f) {}
    };

  //
  // Unary expression closure.
  //

  template<class _Oper, class _Arg>
    class _UnBase
    {
    public:
      typedef typename _Arg::value_type _Vt;
      typedef typename __fun<_Oper, _Vt>::result_type value_type;

      _UnBase(const _Arg& __e) : _M_expr(__e) {}

      value_type operator[](size_t __i) const
      { return _Oper()(_M_expr[__i]); }

      size_t size() const { return _M_expr.size(); }

    private:
      const _Arg& _M_expr;
    };

  template<class _Oper, class _Dom>
    struct _UnClos<_Oper, _Expr, _Dom>
    : _UnBase<_Oper, _Dom>
    {
      typedef _Dom _Arg;
      typedef _UnBase<_Oper, _Dom> _Base;
      typedef typename _Base::value_type value_type;

      _UnClos(const _Arg& __e) : _Base(__e) {}
    };

  template<class _Oper, typename _Tp>
    struct _UnClos<_Oper, _ValArray, _Tp>
    : _UnBase<_Oper, valarray<_Tp> >
    {
      typedef valarray<_Tp> _Arg;
      typedef _UnBase<_Oper, valarray<_Tp> > _Base;
      typedef typename _Base::value_type value_type;

      _UnClos(const _Arg& __e) : _Base(__e) {}
    };

  //
  // Binary expression closure.
  //

  template<class _Oper, class _FirstArg, class _SecondArg>
    class _BinBase
    {
    public:
      typedef typename _FirstArg::value_type _Vt;
      typedef typename __fun<_Oper, _Vt>::result_type value_type;

      _BinBase(const _FirstArg& __e1, const _SecondArg& __e2)
      : _M_expr1(__e1), _M_expr2(__e2) {}

      value_type operator[](size_t __i) const
      { return _Oper()(_M_expr1[__i], _M_expr2[__i]); }

      size_t size() const { return _M_expr1.size(); }

    private:
      const _FirstArg& _M_expr1;
      const _SecondArg& _M_expr2;
    };

  template<class _Oper, class _Clos>
    class _BinBase2
    {
    public:
      typedef typename _Clos::value_type _Vt;
      typedef typename __fun<_Oper, _Vt>::result_type value_type;

      _BinBase2(const _Clos& __e, const _Vt& __t)
      : _M_expr1(__e), _M_expr2(__t) {}

      value_type operator[](size_t __i) const
      { return _Oper()(_M_expr1[__i], _M_expr2); }

      size_t size() const { return _M_expr1.size(); }

    private:
      const _Clos& _M_expr1;
      const _Vt& _M_expr2;
    };

  template<class _Oper, class _Clos>
    class _BinBase1
    {
    public:
      typedef typename _Clos::value_type _Vt;
      typedef typename __fun<_Oper, _Vt>::result_type value_type;

      _BinBase1(const _Vt& __t, const _Clos& __e)
      : _M_expr1(__t), _M_expr2(__e) {}

      value_type operator[](size_t __i) const
      { return _Oper()(_M_expr1, _M_expr2[__i]); }

      size_t size() const { return _M_expr2.size(); }

    private:
      const _Vt& _M_expr1;
      const _Clos& _M_expr2;
    };

  template<class _Oper, class _Dom1, class _Dom2>
    struct _BinClos<_Oper, _Expr, _Expr, _Dom1, _Dom2>
    : _BinBase<_Oper, _Dom1, _Dom2>
    {
      typedef _BinBase<_Oper, _Dom1, _Dom2> _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const _Dom1& __e1, const _Dom2& __e2) : _Base(__e1, __e2) {}
    };

  template<class _Oper, typename _Tp>
    struct _BinClos<_Oper,_ValArray, _ValArray, _Tp, _Tp>
    : _BinBase<_Oper, valarray<_Tp>, valarray<_Tp> >
    {
      typedef _BinBase<_Oper, valarray<_Tp>, valarray<_Tp> > _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const valarray<_Tp>& __v, const valarray<_Tp>& __w)
      : _Base(__v, __w) {}
    };

  template<class _Oper, class _Dom>
    struct _BinClos<_Oper, _Expr, _ValArray, _Dom, typename _Dom::value_type>
    : _BinBase<_Oper, _Dom, valarray<typename _Dom::value_type> >
    {
      typedef typename _Dom::value_type _Tp;
      typedef _BinBase<_Oper,_Dom,valarray<_Tp> > _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const _Dom& __e1, const valarray<_Tp>& __e2)
      : _Base(__e1, __e2) {}
    };

  template<class _Oper, class _Dom>
    struct _BinClos<_Oper, _ValArray, _Expr, typename _Dom::value_type, _Dom>
    : _BinBase<_Oper, valarray<typename _Dom::value_type>,_Dom>
    {
      typedef typename _Dom::value_type _Tp;
      typedef _BinBase<_Oper, valarray<_Tp>, _Dom> _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const valarray<_Tp>& __e1, const _Dom& __e2)
      : _Base(__e1, __e2) {}
    };

  template<class _Oper, class _Dom>
    struct _BinClos<_Oper, _Expr, _Constant, _Dom, typename _Dom::value_type>
    : _BinBase2<_Oper, _Dom>
    {
      typedef typename _Dom::value_type _Tp;
      typedef _BinBase2<_Oper,_Dom> _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const _Dom& __e1, const _Tp& __e2) : _Base(__e1, __e2) {}
    };

  template<class _Oper, class _Dom>
    struct _BinClos<_Oper, _Constant, _Expr, typename _Dom::value_type, _Dom>
    : _BinBase1<_Oper, _Dom>
    {
      typedef typename _Dom::value_type _Tp;
      typedef _BinBase1<_Oper, _Dom> _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const _Tp& __e1, const _Dom& __e2) : _Base(__e1, __e2) {}
    };

  template<class _Oper, typename _Tp>
    struct _BinClos<_Oper, _ValArray, _Constant, _Tp, _Tp>
    : _BinBase2<_Oper, valarray<_Tp> >
    {
      typedef _BinBase2<_Oper,valarray<_Tp> > _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const valarray<_Tp>& __v, const _Tp& __t) : _Base(__v, __t) {}
    };

  template<class _Oper, typename _Tp>
    struct _BinClos<_Oper, _Constant, _ValArray, _Tp, _Tp>
    : _BinBase1<_Oper, valarray<_Tp> >
    {
      typedef _BinBase1<_Oper, valarray<_Tp> > _Base;
      typedef typename _Base::value_type value_type;

      _BinClos(const _Tp& __t, const valarray<_Tp>& __v) : _Base(__t, __v) {}
    };

    //
    // slice_array closure.
    //
  template<typename _Dom>
    class _SBase
    {
    public:
      typedef typename _Dom::value_type value_type;

      _SBase (const _Dom& __e, const slice& __s)
      : _M_expr (__e), _M_slice (__s) {}

      value_type
      operator[] (size_t __i) const
      { return _M_expr[_M_slice.start () + __i * _M_slice.stride ()]; }

      size_t
      size() const
      { return _M_slice.size (); }

    private:
      const _Dom& _M_expr;
      const slice& _M_slice;
    };

  template<typename _Tp>
    class _SBase<_Array<_Tp> >
    {
    public:
      typedef _Tp value_type;

      _SBase (_Array<_Tp> __a, const slice& __s)
      : _M_array (__a._M_data+__s.start()), _M_size (__s.size()),
	_M_stride (__s.stride()) {}

      value_type
      operator[] (size_t __i) const
      { return _M_array._M_data[__i * _M_stride]; }

      size_t
      size() const
      { return _M_size; }

    private:
      const _Array<_Tp> _M_array;
      const size_t _M_size;
      const size_t _M_stride;
    };

  template<class _Dom>
    struct _SClos<_Expr, _Dom>
    : _SBase<_Dom>
    {
      typedef _SBase<_Dom> _Base;
      typedef typename _Base::value_type value_type;

      _SClos (const _Dom& __e, const slice& __s) : _Base (__e, __s) {}
    };

  template<typename _Tp>
    struct _SClos<_ValArray, _Tp>
    : _SBase<_Array<_Tp> >
    {
      typedef  _SBase<_Array<_Tp> > _Base;
      typedef _Tp value_type;

      _SClos (_Array<_Tp> __a, const slice& __s) : _Base (__a, __s) {}
    };

_GLIBCXX_END_NAMESPACE

#endif /* _CPP_VALARRAY_BEFORE_H */


code:
// Vector implementation (out of line) -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * 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.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * 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.  Silicon Graphics makes no
 * representations about the suitability of this  software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file vector.tcc
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _VECTOR_TCC
#define _VECTOR_TCC 1

_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    reserve(size_type __n)
    {
      if (__n > this->max_size())
	__throw_length_error(__N("vector::reserve"));
      if (this->capacity() < __n)
	{
	  const size_type __old_size = size();
	  pointer __tmp = _M_allocate_and_copy(__n, this->_M_impl._M_start,
					       this->_M_impl._M_finish);
	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			_M_get_Tp_allocator());
	  _M_deallocate(this->_M_impl._M_start,
			this->_M_impl._M_end_of_storage
			- this->_M_impl._M_start);
	  this->_M_impl._M_start = __tmp;
	  this->_M_impl._M_finish = __tmp + __old_size;
	  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
	}
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    insert(iterator __position, const value_type& __x)
    {
      const size_type __n = __position - begin();
      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
	  && __position == end())
	{
	  this->_M_impl.construct(this->_M_impl._M_finish, __x);
	  ++this->_M_impl._M_finish;
	}
      else
        _M_insert_aux(__position, __x);
      return iterator(this->_M_impl._M_start + __n);
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    erase(iterator __position)
    {
      if (__position + 1 != end())
        std::copy(__position + 1, end(), __position);
      --this->_M_impl._M_finish;
      this->_M_impl.destroy(this->_M_impl._M_finish);
      return __position;
    }

  template<typename _Tp, typename _Alloc>
    typename vector<_Tp, _Alloc>::iterator
    vector<_Tp, _Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__last != end())
	std::copy(__last, end(), __first);
      _M_erase_at_end(__first.base() + (end() - __last));
      return __first;
    }

  template<typename _Tp, typename _Alloc>
    vector<_Tp, _Alloc>&
    vector<_Tp, _Alloc>::
    operator=(const vector<_Tp, _Alloc>& __x)
    {
      if (&__x != this)
	{
	  const size_type __xlen = __x.size();
	  if (__xlen > capacity())
	    {
	      pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
						   __x.end());
	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			    _M_get_Tp_allocator());
	      _M_deallocate(this->_M_impl._M_start,
			    this->_M_impl._M_end_of_storage
			    - this->_M_impl._M_start);
	      this->_M_impl._M_start = __tmp;
	      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
	    }
	  else if (size() >= __xlen)
	    {
	      std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
			    end(), _M_get_Tp_allocator());
	    }
	  else
	    {
	      std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
			this->_M_impl._M_start);
	      std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
					  __x._M_impl._M_finish,
					  this->_M_impl._M_finish,
					  _M_get_Tp_allocator());
	    }
	  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
	}
      return *this;
    }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_fill_assign(size_t __n, const value_type& __val)
    {
      if (__n > capacity())
	{
	  vector __tmp(__n, __val, _M_get_Tp_allocator());
	  __tmp.swap(*this);
	}
      else if (__n > size())
	{
	  std::fill(begin(), end(), __val);
	  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
					__n - size(), __val,
					_M_get_Tp_allocator());
	  this->_M_impl._M_finish += __n - size();
	}
      else
        _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      void
      vector<_Tp, _Alloc>::
      _M_assign_aux(_InputIterator __first, _InputIterator __last,
		    std::input_iterator_tag)
      {
	pointer __cur(this->_M_impl._M_start);
	for (; __first != __last && __cur != this->_M_impl._M_finish;
	     ++__cur, ++__first)
	  *__cur = *__first;
	if (__first == __last)
	  _M_erase_at_end(__cur);
	else
	  insert(end(), __first, __last);
      }

  template<typename _Tp, typename _Alloc>
    template<typename _ForwardIterator>
      void
      vector<_Tp, _Alloc>::
      _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
		    std::forward_iterator_tag)
      {
	const size_type __len = std::distance(__first, __last);

	if (__len > capacity())
	  {
	    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			  _M_get_Tp_allocator());
	    _M_deallocate(this->_M_impl._M_start,
			  this->_M_impl._M_end_of_storage
			  - this->_M_impl._M_start);
	    this->_M_impl._M_start = __tmp;
	    this->_M_impl._M_finish = this->_M_impl._M_start + __len;
	    this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
	  }
	else if (size() >= __len)
	  _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
	else
	  {
	    _ForwardIterator __mid = __first;
	    std::advance(__mid, size());
	    std::copy(__first, __mid, this->_M_impl._M_start);
	    this->_M_impl._M_finish =
	      std::__uninitialized_copy_a(__mid, __last,
					  this->_M_impl._M_finish,
					  _M_get_Tp_allocator());
	  }
      }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_insert_aux(iterator __position, const _Tp& __x)
    {
      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	{
	  this->_M_impl.construct(this->_M_impl._M_finish,
				  *(this->_M_impl._M_finish - 1));
	  ++this->_M_impl._M_finish;
	  _Tp __x_copy = __x;
	  std::copy_backward(__position.base(),
			     this->_M_impl._M_finish - 2,
			     this->_M_impl._M_finish - 1);
	  *__position = __x_copy;
	}
      else
	{
	  const size_type __old_size = size();
	  if (__old_size == this->max_size())
	    __throw_length_error(__N("vector::_M_insert_aux"));

	  // When sizeof(value_type) == 1 and __old_size > size_type(-1)/2
	  // __len overflows: if we don't notice and _M_allocate doesn't
	  // throw we crash badly later.
	  size_type __len = __old_size != 0 ? 2 * __old_size : 1;
	  if (__len < __old_size)
	    __len = this->max_size();

	  pointer __new_start(this->_M_allocate(__len));
	  pointer __new_finish(__new_start);
	  try
	    {
	      __new_finish =
		std::__uninitialized_copy_a(this->_M_impl._M_start,
					    __position.base(), __new_start,
					    _M_get_Tp_allocator());
	      this->_M_impl.construct(__new_finish, __x);
	      ++__new_finish;
	      __new_finish =
		std::__uninitialized_copy_a(__position.base(),
					    this->_M_impl._M_finish,
					    __new_finish,
					    _M_get_Tp_allocator());
	    }
	  catch(...)
	    {
	      std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
	      _M_deallocate(__new_start, __len);
	      __throw_exception_again;
	    }
	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			_M_get_Tp_allocator());
	  _M_deallocate(this->_M_impl._M_start,
			this->_M_impl._M_end_of_storage
			- this->_M_impl._M_start);
	  this->_M_impl._M_start = __new_start;
	  this->_M_impl._M_finish = __new_finish;
	  this->_M_impl._M_end_of_storage = __new_start + __len;
	}
    }

  template<typename _Tp, typename _Alloc>
    void
    vector<_Tp, _Alloc>::
    _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
    {
      if (__n != 0)
	{
	  if (size_type(this->_M_impl._M_end_of_storage
			- this->_M_impl._M_finish) >= __n)
	    {
	      value_type __x_copy = __x;
	      const size_type __elems_after = end() - __position;
	      pointer __old_finish(this->_M_impl._M_finish);
	      if (__elems_after > __n)
		{
		  std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
					      this->_M_impl._M_finish,
					      this->_M_impl._M_finish,
					      _M_get_Tp_allocator());
		  this->_M_impl._M_finish += __n;
		  std::copy_backward(__position.base(), __old_finish - __n,
				     __old_finish);
		  std::fill(__position.base(), __position.base() + __n,
			    __x_copy);
		}
	      else
		{
		  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
						__n - __elems_after,
						__x_copy,
						_M_get_Tp_allocator());
		  this->_M_impl._M_finish += __n - __elems_after;
		  std::__uninitialized_copy_a(__position.base(), __old_finish,
					      this->_M_impl._M_finish,
					      _M_get_Tp_allocator());
		  this->_M_impl._M_finish += __elems_after;
		  std::fill(__position.base(), __old_finish, __x_copy);
		}
	    }
	  else
	    {
	      const size_type __old_size = size();
	      if (this->max_size() - __old_size < __n)
		__throw_length_error(__N("vector::_M_fill_insert"));

	      // See _M_insert_aux above.
	      size_type __len = __old_size + std::max(__old_size, __n);
	      if (__len < __old_size)
		__len = this->max_size();

	      pointer __new_start(this->_M_allocate(__len));
	      pointer __new_finish(__new_start);
	      try
		{
		  __new_finish =
		    std::__uninitialized_copy_a(this->_M_impl._M_start,
						__position.base(),
						__new_start,
						_M_get_Tp_allocator());
		  std::__uninitialized_fill_n_a(__new_finish, __n, __x,
						_M_get_Tp_allocator());
		  __new_finish += __n;
		  __new_finish =
		    std::__uninitialized_copy_a(__position.base(),
						this->_M_impl._M_finish,
						__new_finish,
						_M_get_Tp_allocator());
		}
	      catch(...)
		{
		  std::_Destroy(__new_start, __new_finish,
				_M_get_Tp_allocator());
		  _M_deallocate(__new_start, __len);
		  __throw_exception_again;
		}
	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			    _M_get_Tp_allocator());
	      _M_deallocate(this->_M_impl._M_start,
			    this->_M_impl._M_end_of_storage
			    - this->_M_impl._M_start);
	      this->_M_impl._M_start = __new_start;
	      this->_M_impl._M_finish = __new_finish;
	      this->_M_impl._M_end_of_storage = __new_start + __len;
	    }
	}
    }

  template<typename _Tp, typename _Alloc> template<typename _InputIterator>
    void
    vector<_Tp, _Alloc>::
    _M_range_insert(iterator __pos, _InputIterator __first,
		    _InputIterator __last, std::input_iterator_tag)
    {
      for (; __first != __last; ++__first)
	{
	  __pos = insert(__pos, *__first);
	  ++__pos;
	}
    }

  template<typename _Tp, typename _Alloc>
    template<typename _ForwardIterator>
      void
      vector<_Tp, _Alloc>::
      _M_range_insert(iterator __position, _ForwardIterator __first,
		      _ForwardIterator __last, std::forward_iterator_tag)
      {
	if (__first != __last)
	  {
	    const size_type __n = std::distance(__first, __last);
	    if (size_type(this->_M_impl._M_end_of_storage
			  - this->_M_impl._M_finish) >= __n)
	      {
		const size_type __elems_after = end() - __position;
		pointer __old_finish(this->_M_impl._M_finish);
		if (__elems_after > __n)
		  {
		    std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
						this->_M_impl._M_finish,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __n;
		    std::copy_backward(__position.base(), __old_finish - __n,
				       __old_finish);
		    std::copy(__first, __last, __position);
		  }
		else
		  {
		    _ForwardIterator __mid = __first;
		    std::advance(__mid, __elems_after);
		    std::__uninitialized_copy_a(__mid, __last,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __n - __elems_after;
		    std::__uninitialized_copy_a(__position.base(),
						__old_finish,
						this->_M_impl._M_finish,
						_M_get_Tp_allocator());
		    this->_M_impl._M_finish += __elems_after;
		    std::copy(__first, __mid, __position);
		  }
	      }
	    else
	      {
		const size_type __old_size = size();
		if (this->max_size() - __old_size < __n)
		  __throw_length_error(__N("vector::_M_range_insert"));

		// See _M_insert_aux above.
		size_type __len = __old_size + std::max(__old_size, __n);
		if (__len < __old_size)
		  __len = this->max_size();

		pointer __new_start(this->_M_allocate(__len));
		pointer __new_finish(__new_start);
		try
		  {
		    __new_finish =
		      std::__uninitialized_copy_a(this->_M_impl._M_start,
						  __position.base(),
						  __new_start,
						  _M_get_Tp_allocator());
		    __new_finish =
		      std::__uninitialized_copy_a(__first, __last, __new_finish,
						  _M_get_Tp_allocator());
		    __new_finish =
		      std::__uninitialized_copy_a(__position.base(),
						  this->_M_impl._M_finish,
						  __new_finish,
						  _M_get_Tp_allocator());
		  }
		catch(...)
		  {
		    std::_Destroy(__new_start, __new_finish,
				  _M_get_Tp_allocator());
		    _M_deallocate(__new_start, __len);
		    __throw_exception_again;
		  }
		std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
			      _M_get_Tp_allocator());
		_M_deallocate(this->_M_impl._M_start,
			      this->_M_impl._M_end_of_storage
			      - this->_M_impl._M_start);
		this->_M_impl._M_start = __new_start;
		this->_M_impl._M_finish = __new_finish;
		this->_M_impl._M_end_of_storage = __new_start + __len;
	      }
	  }
      }

_GLIBCXX_END_NESTED_NAMESPACE

#endif /* _VECTOR_TCC */

repo_name: veiledmerc/mira

license: mit


code:
// <bitset> -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 * Copyright (c) 1998
 * Silicon Graphics Computer Systems, Inc.
 *
 * 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.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file include/bitset
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_BITSET
#define _GLIBCXX_BITSET 1

#pragma GCC system_header

#include <cstddef>     // For size_t
#include <cstring>     // For memset
#include <limits>      // For numeric_limits
#include <string>
#include <bits/functexcept.h>   // For invalid_argument, out_of_range,
                                // overflow_error
#include <ostream>     // For ostream (operator<<)
#include <istream>     // For istream (operator>>)

#define _GLIBCXX_BITSET_BITS_PER_WORD  numeric_limits<unsigned long>::digits
#define _GLIBCXX_BITSET_WORDS(__n) \
 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
                  / _GLIBCXX_BITSET_BITS_PER_WORD)

_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)

  /**
   *  @if maint
   *  Base class, general case.  It is a class inveriant that _Nw will be
   *  nonnegative.
   *
   *  See documentation for bitset.
   *  @endif
  */
  template<size_t _Nw>
    struct _Base_bitset
    {
      typedef unsigned long _WordT;

      /// 0 is the least significant word.
      _WordT 		_M_w[_Nw];

      _Base_bitset()
      { _M_do_reset(); }

      _Base_bitset(unsigned long __val)
      {
	_M_do_reset();
	_M_w[0] = __val;
      }

      static size_t
      _S_whichword(size_t __pos )
      { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }

      static size_t
      _S_whichbyte(size_t __pos )
      { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }

      static size_t
      _S_whichbit(size_t __pos )
      { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _WordT
      _S_maskbit(size_t __pos )
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      _WordT&
      _M_getword(size_t __pos)
      { return _M_w[_S_whichword(__pos)]; }

      _WordT
      _M_getword(size_t __pos) const
      { return _M_w[_S_whichword(__pos)]; }

      _WordT&
      _M_hiword()
      { return _M_w[_Nw - 1]; }

      _WordT
      _M_hiword() const
      { return _M_w[_Nw - 1]; }

      void
      _M_do_and(const _Base_bitset<_Nw>& __x)
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] &= __x._M_w[__i];
      }

      void
      _M_do_or(const _Base_bitset<_Nw>& __x)
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] |= __x._M_w[__i];
      }

      void
      _M_do_xor(const _Base_bitset<_Nw>& __x)
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] ^= __x._M_w[__i];
      }

      void
      _M_do_left_shift(size_t __shift);

      void
      _M_do_right_shift(size_t __shift);

      void
      _M_do_flip()
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] = ~_M_w[__i];
      }

      void
      _M_do_set()
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] = ~static_cast<_WordT>(0);
      }

      void
      _M_do_reset()
      { std::memset(_M_w, 0, _Nw * sizeof(_WordT)); }

      bool
      _M_is_equal(const _Base_bitset<_Nw>& __x) const
      {
	for (size_t __i = 0; __i < _Nw; ++__i)
	  {
	    if (_M_w[__i] != __x._M_w[__i])
	      return false;
	  }
	return true;
      }

      bool
      _M_is_any() const
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  {
	    if (_M_w[__i] != static_cast<_WordT>(0))
	      return true;
	  }
	return false;
      }

      size_t
      _M_do_count() const
      {
	size_t __result = 0;
	for (size_t __i = 0; __i < _Nw; __i++)
	  __result += __builtin_popcountl(_M_w[__i]);
	return __result;
      }

      unsigned long
      _M_do_to_ulong() const;

      // find first "on" bit
      size_t
      _M_do_find_first(size_t __not_found) const;

      // find the next "on" bit that follows "prev"
      size_t
      _M_do_find_next(size_t __prev, size_t __not_found) const;
    };

  // Definitions of non-inline functions from _Base_bitset.
  template<size_t _Nw>
    void
    _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
    {
      if (__builtin_expect(__shift != 0, 1))
	{
	  const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
	  const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;

	  if (__offset == 0)
	    for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
	      _M_w[__n] = _M_w[__n - __wshift];
	  else
	    {
	      const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
					   - __offset);
	      for (size_t __n = _Nw - 1; __n > __wshift; --__n)
		_M_w[__n] = ((_M_w[__n - __wshift] << __offset)
			     | (_M_w[__n - __wshift - 1] >> __sub_offset));
	      _M_w[__wshift] = _M_w[0] << __offset;
	    }

	  std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
	}
    }

  template<size_t _Nw>
    void
    _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
    {
      if (__builtin_expect(__shift != 0, 1))
	{
	  const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
	  const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
	  const size_t __limit = _Nw - __wshift - 1;

	  if (__offset == 0)
	    for (size_t __n = 0; __n <= __limit; ++__n)
	      _M_w[__n] = _M_w[__n + __wshift];
	  else
	    {
	      const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
					   - __offset);
	      for (size_t __n = 0; __n < __limit; ++__n)
		_M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
			     | (_M_w[__n + __wshift + 1] << __sub_offset));
	      _M_w[__limit] = _M_w[_Nw-1] >> __offset;
	    }

	  std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
	}
    }

  template<size_t _Nw>
    unsigned long
    _Base_bitset<_Nw>::_M_do_to_ulong() const
    {
      for (size_t __i = 1; __i < _Nw; ++__i)
	if (_M_w[__i])
	  __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
      return _M_w[0];
    }

  template<size_t _Nw>
    size_t
    _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
    {
      for (size_t __i = 0; __i < _Nw; __i++)
	{
	  _WordT __thisword = _M_w[__i];
	  if (__thisword != static_cast<_WordT>(0))
	    return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
		    + __builtin_ctzl(__thisword));
	}
      // not found, so return an indication of failure.
      return __not_found;
    }

  template<size_t _Nw>
    size_t
    _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
    {
      // make bound inclusive
      ++__prev;

      // check out of bounds
      if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
	return __not_found;

      // search first word
      size_t __i = _S_whichword(__prev);
      _WordT __thisword = _M_w[__i];

      // mask off bits below bound
      __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);

      if (__thisword != static_cast<_WordT>(0))
	return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
		+ __builtin_ctzl(__thisword));

      // check subsequent words
      __i++;
      for (; __i < _Nw; __i++)
	{
	  __thisword = _M_w[__i];
	  if (__thisword != static_cast<_WordT>(0))
	    return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
		    + __builtin_ctzl(__thisword));
	}
      // not found, so return an indication of failure.
      return __not_found;
    } // end _M_do_find_next

  /**
   *  @if maint
   *  Base class, specialization for a single word.
   *
   *  See documentation for bitset.
   *  @endif
  */
  template<>
    struct _Base_bitset<1>
    {
      typedef unsigned long _WordT;
      _WordT _M_w;

      _Base_bitset(void)
      : _M_w(0)
      { }

      _Base_bitset(unsigned long __val)
      : _M_w(__val)
      { }

      static size_t
      _S_whichword(size_t __pos )
      { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }

      static size_t
      _S_whichbyte(size_t __pos )
      { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }

      static size_t
      _S_whichbit(size_t __pos )
      {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _WordT
      _S_maskbit(size_t __pos )
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      _WordT&
      _M_getword(size_t)
      { return _M_w; }

      _WordT
      _M_getword(size_t) const
      { return _M_w; }

      _WordT&
      _M_hiword()
      { return _M_w; }

      _WordT
      _M_hiword() const
      { return _M_w; }

      void
      _M_do_and(const _Base_bitset<1>& __x)
      { _M_w &= __x._M_w; }

      void
      _M_do_or(const _Base_bitset<1>& __x)
      { _M_w |= __x._M_w; }

      void
      _M_do_xor(const _Base_bitset<1>& __x)
      { _M_w ^= __x._M_w; }

      void
      _M_do_left_shift(size_t __shift)
      { _M_w <<= __shift; }

      void
      _M_do_right_shift(size_t __shift)
      { _M_w >>= __shift; }

      void
      _M_do_flip()
      { _M_w = ~_M_w; }

      void
      _M_do_set()
      { _M_w = ~static_cast<_WordT>(0); }

      void
      _M_do_reset()
      { _M_w = 0; }

      bool
      _M_is_equal(const _Base_bitset<1>& __x) const
      { return _M_w == __x._M_w; }

      bool
      _M_is_any() const
      { return _M_w != 0; }

      size_t
      _M_do_count() const
      { return __builtin_popcountl(_M_w); }

      unsigned long
      _M_do_to_ulong() const
      { return _M_w; }

      size_t
      _M_do_find_first(size_t __not_found) const
      {
        if (_M_w != 0)
          return __builtin_ctzl(_M_w);
        else
          return __not_found;
      }

      // find the next "on" bit that follows "prev"
      size_t
      _M_do_find_next(size_t __prev, size_t __not_found) const
      {
	++__prev;
	if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
	  return __not_found;

	_WordT __x = _M_w >> __prev;
	if (__x != 0)
	  return __builtin_ctzl(__x) + __prev;
	else
	  return __not_found;
      }
    };

  /**
   *  @if maint
   *  Base class, specialization for no storage (zero-length %bitset).
   *
   *  See documentation for bitset.
   *  @endif
  */
  template<>
    struct _Base_bitset<0>
    {
      typedef unsigned long _WordT;

      _Base_bitset()
      { }

      _Base_bitset(unsigned long)
      { }

      static size_t
      _S_whichword(size_t __pos )
      { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }

      static size_t
      _S_whichbyte(size_t __pos )
      { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }

      static size_t
      _S_whichbit(size_t __pos )
      {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _WordT
      _S_maskbit(size_t __pos )
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      // This would normally give access to the data.  The bounds-checking
      // in the bitset class will prevent the user from getting this far,
      // but (1) it must still return an lvalue to compile, and (2) the
      // user might call _Unchecked_set directly, in which case this /needs/
      // to fail.  Let's not penalize zero-length users unless they actually
      // make an unchecked call; all the memory ugliness is therefore
      // localized to this single should-never-get-this-far function.
      _WordT&
      _M_getword(size_t) const
      {
	__throw_out_of_range(__N("_Base_bitset::_M_getword"));
	return *new _WordT;
      }

      _WordT
      _M_hiword() const
      { return 0; }

      void
      _M_do_and(const _Base_bitset<0>&)
      { }

      void
      _M_do_or(const _Base_bitset<0>&)
      { }

      void
      _M_do_xor(const _Base_bitset<0>&)
      { }

      void
      _M_do_left_shift(size_t)
      { }

      void
      _M_do_right_shift(size_t)
      { }

      void
      _M_do_flip()
      { }

      void
      _M_do_set()
      { }

      void
      _M_do_reset()
      { }

      // Are all empty bitsets equal to each other?  Are they equal to
      // themselves?  How to compare a thing which has no state?  What is
      // the sound of one zero-length bitset clapping?
      bool
      _M_is_equal(const _Base_bitset<0>&) const
      { return true; }

      bool
      _M_is_any() const
      { return false; }

      size_t
      _M_do_count() const
      { return 0; }

      unsigned long
      _M_do_to_ulong() const
      { return 0; }

      // Normally "not found" is the size, but that could also be
      // misinterpreted as an index in this corner case.  Oh well.
      size_t
      _M_do_find_first(size_t) const
      { return 0; }

      size_t
      _M_do_find_next(size_t, size_t) const
      { return 0; }
    };

  // Helper class to zero out the unused high-order bits in the highest word.
  template<size_t _Extrabits>
    struct _Sanitize
    {
      static void _S_do_sanitize(unsigned long& __val)
      { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
    };

  template<>
    struct _Sanitize<0>
    { static void _S_do_sanitize(unsigned long) {} };

  /**
   *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
   *
   *  @ingroup Containers
   *
   *  (Note that %bitset does @e not meet the formal requirements of a
   *  container.  Mainly, it lacks iterators.)
   *
   *  The template argument, @a Nb, may be any non-negative number,
   *  specifying the number of bits (e.g., "0", "12", "1024*1024").
   *
   *  In the general unoptimized case, storage is allocated in word-sized
   *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
   *  words will be used for storage.  B - Nb%B bits are unused.  (They are
   *  the high-order bits in the highest word.)  It is a class invariant
   *  that those unused bits are always zero.
   *
   *  If you think of %bitset as "a simple array of bits," be aware that
   *  your mental picture is reversed:  a %bitset behaves the same way as
   *  bits in integers do, with the bit at index 0 in the "least significant
   *  / right-hand" position, and the bit at index Nb-1 in the "most
   *  significant / left-hand" position.  Thus, unlike other containers, a
   *  %bitset's index "counts from right to left," to put it very loosely.
   *
   *  This behavior is preserved when translating to and from strings.  For
   *  example, the first line of the following program probably prints
   *  "b('a') is 0001100001" on a modern ASCII system.
   *
   *  @code
   *     #include <bitset>
   *     #include <iostream>
   *     #include <sstream>
   *
   *     using namespace std;
   *
   *     int main()
   *     {
   *         long         a = 'a';
   *         bitset<10>   b(a);
   *
   *         cout << "b('a') is " << b << endl;
   *
   *         ostringstream s;
   *         s << b;
   *         string  str = s.str();
   *         cout << "index 3 in the string is " << str[3] << " but\n"
   *              << "index 3 in the bitset is " << b[3] << endl;
   *     }
   *  @endcode
   *
   *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
   *  for a description of extensions.
   *
   *  @if maint
   *  Most of the actual code isn't contained in %bitset<> itself, but in the
   *  base class _Base_bitset.  The base class works with whole words, not with
   *  individual bits.  This allows us to specialize _Base_bitset for the
   *  important special case where the %bitset is only a single word.
   *
   *  Extra confusion can result due to the fact that the storage for
   *  _Base_bitset @e is a regular array, and is indexed as such.  This is
   *  carefully encapsulated.
   *  @endif
  */
  template<size_t _Nb>
    class bitset
    : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
    {
    private:
      typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
      typedef unsigned long _WordT;

      void
	_M_do_sanitize()
	{
	  _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
	    _S_do_sanitize(this->_M_hiword());
	}

    public:
      /**
       *  This encapsulates the concept of a single bit.  An instance of this
       *  class is a proxy for an actual bit; this way the individual bit
       *  operations are done as faster word-size bitwise instructions.
       *
       *  Most users will never need to use this class directly; conversions
       *  to and from bool are automatic and should be transparent.  Overloaded
       *  operators help to preserve the illusion.
       *
       *  (On a typical system, this "bit %reference" is 64 times the size of
       *  an actual bit.  Ha.)
       */
      class reference
      {
	friend class bitset;

	_WordT *_M_wp;
	size_t _M_bpos;

	// left undefined
	reference();

      public:
	reference(bitset& __b, size_t __pos)
	{
	  _M_wp = &__b._M_getword(__pos);
	  _M_bpos = _Base::_S_whichbit(__pos);
	}

	~reference()
	{ }

	// For b[i] = __x;
	reference&
	operator=(bool __x)
	{
	  if (__x)
	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
	  else
	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	  return *this;
	}

	// For b[i] = b[__j];
	reference&
	operator=(const reference& __j)
	{
	  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
	  else
	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	  return *this;
	}

	// Flips the bit
	bool
	operator~() const
	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }

	// For __x = b[i];
	operator bool() const
	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }

	// For b[i].flip();
	reference&
	flip()
	{
	  *_M_wp ^= _Base::_S_maskbit(_M_bpos);
	  return *this;
	}
      };
      friend class reference;

      // 23.3.5.1 constructors:
      /// All bits set to zero.
      bitset()
      { }

      /// Initial bits bitwise-copied from a single word (others set to zero).
      bitset(unsigned long __val)
      : _Base(__val)
      { _M_do_sanitize(); }

      /**
       *  @brief  Use a subset of a string.
       *  @param  s  A string of '0' and '1' characters.
       *  @param  position  Index of the first character in @a s to use;
       *                    defaults to zero.
       *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      template<class _CharT, class _Traits, class _Alloc>
	explicit
	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
	       size_t __position = 0)
	: _Base()
	{
	  if (__position > __s.size())
	    __throw_out_of_range(__N("bitset::bitset initial position "
				     "not valid"));
	  _M_copy_from_string(__s, __position,
			      std::basic_string<_CharT, _Traits, _Alloc>::npos);
	}

      /**
       *  @brief  Use a subset of a string.
       *  @param  s  A string of '0' and '1' characters.
       *  @param  position  Index of the first character in @a s to use.
       *  @param  n    The number of characters to copy.
       *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      template<class _CharT, class _Traits, class _Alloc>
	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
	       size_t __position, size_t __n)
	: _Base()
	{
	  if (__position > __s.size())
	    __throw_out_of_range(__N("bitset::bitset initial position "
				     "not valid"));
	  _M_copy_from_string(__s, __position, __n);
	}

      // 23.3.5.2 bitset operations:
      //@{
      /**
       *  @brief  Operations on bitsets.
       *  @param  rhs  A same-sized bitset.
       *
       *  These should be self-explanatory.
       */
      bitset<_Nb>&
      operator&=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_and(__rhs);
	return *this;
      }

      bitset<_Nb>&
      operator|=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_or(__rhs);
	return *this;
      }

      bitset<_Nb>&
      operator^=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_xor(__rhs);
	return *this;
      }
      //@}

      //@{
      /**
       *  @brief  Operations on bitsets.
       *  @param  position  The number of places to shift.
       *
       *  These should be self-explanatory.
       */
      bitset<_Nb>&
      operator<<=(size_t __position)
      {
	if (__builtin_expect(__position < _Nb, 1))
	  {
	    this->_M_do_left_shift(__position);
	    this->_M_do_sanitize();
	  }
	else
	  this->_M_do_reset();
	return *this;
      }

      bitset<_Nb>&
      operator>>=(size_t __position)
      {
	if (__builtin_expect(__position < _Nb, 1))
	  {
	    this->_M_do_right_shift(__position);
	    this->_M_do_sanitize();
	  }
	else
	  this->_M_do_reset();
	return *this;
      }
      //@}

      //@{
      /**
       *  These versions of single-bit set, reset, flip, and test are
       *  extensions from the SGI version.  They do no range checking.
       *  @ingroup SGIextensions
       */
      bitset<_Nb>&
      _Unchecked_set(size_t __pos)
      {
	this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	return *this;
      }

      bitset<_Nb>&
      _Unchecked_set(size_t __pos, int __val)
      {
	if (__val)
	  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	else
	  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
	return *this;
      }

      bitset<_Nb>&
      _Unchecked_reset(size_t __pos)
      {
	this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
	return *this;
      }

      bitset<_Nb>&
      _Unchecked_flip(size_t __pos)
      {
	this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
	return *this;
      }

      bool
      _Unchecked_test(size_t __pos) const
      { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
		!= static_cast<_WordT>(0)); }
      //@}

      // Set, reset, and flip.
      /**
       *  @brief Sets every bit to true.
       */
      bitset<_Nb>&
      set()
      {
	this->_M_do_set();
	this->_M_do_sanitize();
	return *this;
      }

      /**
       *  @brief Sets a given bit to a particular value.
       *  @param  position  The index of the bit.
       *  @param  val  Either true or false, defaults to true.
       *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
       */
      bitset<_Nb>&
      set(size_t __position, bool __val = true)
      {
	if (__position >= _Nb)
	  __throw_out_of_range(__N("bitset::set"));
	return _Unchecked_set(__position, __val);
      }

      /**
       *  @brief Sets every bit to false.
       */
      bitset<_Nb>&
      reset()
      {
	this->_M_do_reset();
	return *this;
      }

      /**
       *  @brief Sets a given bit to false.
       *  @param  position  The index of the bit.
       *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
       *
       *  Same as writing @c set(pos,false).
       */
      bitset<_Nb>&
      reset(size_t __position)
      {
	if (__position >= _Nb)
	  __throw_out_of_range(__N("bitset::reset"));
	return _Unchecked_reset(__position);
      }

      /**
       *  @brief Toggles every bit to its opposite value.
       */
      bitset<_Nb>&
      flip()
      {
	this->_M_do_flip();
	this->_M_do_sanitize();
	return *this;
      }

      /**
       *  @brief Toggles a given bit to its opposite value.
       *  @param  position  The index of the bit.
       *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
       */
      bitset<_Nb>&
      flip(size_t __position)
      {
	if (__position >= _Nb)
	  __throw_out_of_range(__N("bitset::flip"));
	return _Unchecked_flip(__position);
      }

      /// See the no-argument flip().
      bitset<_Nb>
      operator~() const
      { return bitset<_Nb>(*this).flip(); }

      //@{
      /**
       *  @brief  Array-indexing support.
       *  @param  position  Index into the %bitset.
       *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
       *           instance of the reference proxy class.
       *  @note  These operators do no range checking and throw no exceptions,
       *         as required by DR 11 to the standard.
       *
       *  @if maint
       *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
       *  resolves DR 11 (items 1 and 2), but does not do the range-checking
       *  required by that DR's resolution.  -pme
       *  The DR has since been changed:  range-checking is a precondition
       *  (users' responsibility), and these functions must not throw.  -pme
       *  @endif
       */
      reference
      operator[](size_t __position)
      { return reference(*this,__position); }

      bool
      operator[](size_t __position) const
      { return _Unchecked_test(__position); }
      //@}

      /**
       *  @brief Retuns a numerical interpretation of the %bitset.
       *  @return  The integral equivalent of the bits.
       *  @throw  std::overflow_error  If there are too many bits to be
       *                               represented in an @c unsigned @c long.
       */
      unsigned long
      to_ulong() const
      { return this->_M_do_to_ulong(); }

      /**
       *  @brief Retuns a character interpretation of the %bitset.
       *  @return  The string equivalent of the bits.
       *
       *  Note the ordering of the bits:  decreasing character positions
       *  correspond to increasing bit positions (see the main class notes for
       *  an example).
       */
      template<class _CharT, class _Traits, class _Alloc>
	std::basic_string<_CharT, _Traits, _Alloc>
	to_string() const
	{
	  std::basic_string<_CharT, _Traits, _Alloc> __result;
	  _M_copy_to_string(__result);
	  return __result;
	}

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 434. bitset::to_string() hard to use.
      template<class _CharT, class _Traits>
	std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
	to_string() const
	{ return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }

      template<class _CharT>
	std::basic_string<_CharT, std::char_traits<_CharT>,
	                  std::allocator<_CharT> >
	to_string() const
	{
	  return to_string<_CharT, std::char_traits<_CharT>,
	                   std::allocator<_CharT> >();
	}

      std::basic_string<char, std::char_traits<char>, std::allocator<char> >
      to_string() const
      {
	return to_string<char, std::char_traits<char>,
	                 std::allocator<char> >();
      }

      // Helper functions for string operations.
      template<class _CharT, class _Traits, class _Alloc>
	void
	_M_copy_from_string(const std::basic_string<_CharT,
			    _Traits, _Alloc>& __s,
			    size_t, size_t);

      template<class _CharT, class _Traits, class _Alloc>
	void
	_M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&) const;

      /// Returns the number of bits which are set.
      size_t
      count() const
      { return this->_M_do_count(); }

      /// Returns the total number of bits.
      size_t
      size() const
      { return _Nb; }

      //@{
      /// These comparisons for equality/inequality are, well, @e bitwise.
      bool
      operator==(const bitset<_Nb>& __rhs) const
      { return this->_M_is_equal(__rhs); }

      bool
      operator!=(const bitset<_Nb>& __rhs) const
      { return !this->_M_is_equal(__rhs); }
      //@}

      /**
       *  @brief Tests the value of a bit.
       *  @param  position  The index of a bit.
       *  @return  The value at @a pos.
       *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
       */
      bool
      test(size_t __position) const
      {
	if (__position >= _Nb)
	  __throw_out_of_range(__N("bitset::test"));
	return _Unchecked_test(__position);
      }

      /**
       *  @brief Tests whether any of the bits are on.
       *  @return  True if at least one bit is set.
       */
      bool
      any() const
      { return this->_M_is_any(); }

      /**
       *  @brief Tests whether any of the bits are on.
       *  @return  True if none of the bits are set.
       */
      bool
      none() const
      { return !this->_M_is_any(); }

      //@{
      /// Self-explanatory.
      bitset<_Nb>
      operator<<(size_t __position) const
      { return bitset<_Nb>(*this) <<= __position; }

      bitset<_Nb>
      operator>>(size_t __position) const
      { return bitset<_Nb>(*this) >>= __position; }
      //@}

      /**
       *  @brief  Finds the index of the first "on" bit.
       *  @return  The index of the first bit set, or size() if not found.
       *  @ingroup SGIextensions
       *  @sa  _Find_next
       */
      size_t
      _Find_first() const
      { return this->_M_do_find_first(_Nb); }

      /**
       *  @brief  Finds the index of the next "on" bit after prev.
       *  @return  The index of the next bit set, or size() if not found.
       *  @param  prev  Where to start searching.
       *  @ingroup SGIextensions
       *  @sa  _Find_first
       */
      size_t
      _Find_next(size_t __prev ) const
      { return this->_M_do_find_next(__prev, _Nb); }
    };

  // Definitions of non-inline member functions.
  template<size_t _Nb>
    template<class _CharT, class _Traits, class _Alloc>
      void
      bitset<_Nb>::
      _M_copy_from_string(const std::basic_string<_CharT, _Traits,
			  _Alloc>& __s, size_t __pos, size_t __n)
      {
	reset();
	const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos));
	for (size_t __i = __nbits; __i > 0; --__i)
	  {
	    switch(__s[__pos + __nbits - __i])
	      {
	      case '0':
		break;
	      case '1':
		_Unchecked_set(__i - 1);
		break;
	      default:
		__throw_invalid_argument(__N("bitset::_M_copy_from_string"));
	      }
	  }
      }

  template<size_t _Nb>
    template<class _CharT, class _Traits, class _Alloc>
      void
      bitset<_Nb>::
      _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s) const
      {
	__s.assign(_Nb, '0');
	for (size_t __i = _Nb; __i > 0; --__i)
	  if (_Unchecked_test(__i - 1))
	    __s[_Nb - __i] = '1';
      }

  // 23.3.5.3 bitset operations:
  //@{
  /**
   *  @brief  Global bitwise operations on bitsets.
   *  @param  x  A bitset.
   *  @param  y  A bitset of the same size as @a x.
   *  @return  A new bitset.
   *
   *  These should be self-explanatory.
  */
  template<size_t _Nb>
    inline bitset<_Nb>
    operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    {
      bitset<_Nb> __result(__x);
      __result &= __y;
      return __result;
    }

  template<size_t _Nb>
    inline bitset<_Nb>
    operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    {
      bitset<_Nb> __result(__x);
      __result |= __y;
      return __result;
    }

  template <size_t _Nb>
    inline bitset<_Nb>
    operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    {
      bitset<_Nb> __result(__x);
      __result ^= __y;
      return __result;
    }
  //@}

  //@{
  /**
   *  @brief Global I/O operators for bitsets.
   *
   *  Direct I/O between streams and bitsets is supported.  Output is
   *  straightforward.  Input will skip whitespace, only accept '0' and '1'
   *  characters, and will only extract as many digits as the %bitset will
   *  hold.
  */
  template<class _CharT, class _Traits, size_t _Nb>
    std::basic_istream<_CharT, _Traits>&
    operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
    {
      typedef typename _Traits::char_type char_type;
      std::basic_string<_CharT, _Traits> __tmp;
      __tmp.reserve(_Nb);

      std::ios_base::iostate __state = std::ios_base::goodbit;
      typename std::basic_istream<_CharT, _Traits>::sentry __sentry(__is);
      if (__sentry)
	{
	  try
	    {
	      basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
	      // 303. Bitset input operator underspecified
	      const char_type __zero = __is.widen('0');
	      const char_type __one = __is.widen('1');
	      for (size_t __i = _Nb; __i > 0; --__i)
		{
		  static typename _Traits::int_type __eof = _Traits::eof();

		  typename _Traits::int_type __c1 = __buf->sbumpc();
		  if (_Traits::eq_int_type(__c1, __eof))
		    {
		      __state |= std::ios_base::eofbit;
		      break;
		    }
		  else
		    {
		      const char_type __c2 = _Traits::to_char_type(__c1);
		      if (__c2 == __zero)
			__tmp.push_back('0');
		      else if (__c2 == __one)
			__tmp.push_back('1');
		      else if (_Traits::eq_int_type(__buf->sputbackc(__c2),
						    __eof))
			{
			  __state |= std::ios_base::failbit;
			  break;
			}
		    }
		}
	    }
	  catch(...)
	    { __is._M_setstate(std::ios_base::badbit); }
	}

      if (__tmp.empty() && _Nb)
	__state |= std::ios_base::failbit;
      else
	__x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
      if (__state)
	__is.setstate(__state);
      return __is;
    }

  template <class _CharT, class _Traits, size_t _Nb>
    std::basic_ostream<_CharT, _Traits>&
    operator<<(std::basic_ostream<_CharT, _Traits>& __os,
	       const bitset<_Nb>& __x)
    {
      std::basic_string<_CharT, _Traits> __tmp;
      __x._M_copy_to_string(__tmp);
      return __os << __tmp;
    }

  // Specializations for zero-sized bitsets, to avoid "unsigned comparison
  // with zero" warnings.
  template<>
    inline bitset<0>&
    bitset<0>::
    set(size_t, bool)
    {
      __throw_out_of_range(__N("bitset::set"));
      return *this;
    }

  template<>
    inline bitset<0>&
    bitset<0>::
    reset(size_t)
    {
      __throw_out_of_range(__N("bitset::reset"));
      return *this;
    }

  template<>
    inline bitset<0>&
    bitset<0>::
    flip(size_t)
    {
      __throw_out_of_range(__N("bitset::flip"));
      return *this;
    }

  template<>
    inline bool
    bitset<0>::
    test(size_t) const
    {
      __throw_out_of_range(__N("bitset::test"));
      return false;
    }
  //@}

_GLIBCXX_END_NESTED_NAMESPACE

#undef _GLIBCXX_BITSET_WORDS
#undef _GLIBCXX_BITSET_BITS_PER_WORD

#ifdef _GLIBCXX_DEBUG
# include <debug/bitset>
#endif

#endif /* _GLIBCXX_BITSET */


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file cassert
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c assert.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 19.2  Assertions
//

// No include guards on this header...

#pragma GCC system_header

#include <assert.h>


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file include/cctype
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c ctype.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: <ccytpe>
//

#ifndef _GLIBCXX_CCTYPE
#define _GLIBCXX_CCTYPE 1

#pragma GCC system_header

#include <bits/c++config.h>
#include <ctype.h>

// Get rid of those macros defined in <ctype.h> in lieu of real functions.
#undef isalnum
#undef isalpha
#undef iscntrl
#undef isdigit
#undef isgraph
#undef islower
#undef isprint
#undef ispunct
#undef isspace
#undef isupper
#undef isxdigit
#undef tolower
#undef toupper

_GLIBCXX_BEGIN_NAMESPACE(std)

  using ::isalnum;
  using ::isalpha;
  using ::iscntrl;
  using ::isdigit;
  using ::isgraph;
  using ::islower;
  using ::isprint;
  using ::ispunct;
  using ::isspace;
  using ::isupper;
  using ::isxdigit;
  using ::tolower;
  using ::toupper;

_GLIBCXX_END_NAMESPACE

#endif


code:
// The -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file cerrno
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c errno.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 19.3  Error numbers
//

#ifndef _GLIBCXX_CERRNO
#define _GLIBCXX_CERRNO 1

#pragma GCC system_header

#include <errno.h>

// Adhere to section 17.4.1.2 clause 5 of ISO 14882:1998
#ifndef errno
#define errno errno
#endif

#endif


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file include/cfloat
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c float.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 18.2.2  Implementation properties: C library
//

#ifndef _GLIBCXX_CFLOAT
#define _GLIBCXX_CFLOAT 1

#pragma GCC system_header

#include <float.h>

#endif


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file ciso646
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c iso646.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file include/climits
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c limits.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 18.2.2  Implementation properties: C library
//

#ifndef _GLIBCXX_CLIMITS
#define _GLIBCXX_CLIMITS 1

#pragma GCC system_header

#include <limits.h>

#endif


code:
// -*- C++ -*- forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file clocale
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c locale.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 18.2.2  Implementation properties: C library
//

#ifndef _GLIBCXX_CLOCALE
#define _GLIBCXX_CLOCALE 1

#pragma GCC system_header

#include <bits/c++config.h>
#include <locale.h>

// Get rid of those macros defined in <locale.h> in lieu of real functions.
#undef setlocale
#undef localeconv

_GLIBCXX_BEGIN_NAMESPACE(std)

  using ::lconv;
  using ::setlocale;
  using ::localeconv;

_GLIBCXX_END_NAMESPACE

#endif


code:
// -*- C++ -*- C forwarding header.

// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file include/cmath
 *  This is a Standard C++ Library file.  You should @c #include this file
 *  in your programs, rather than any of the "*.h" implementation files.
 *
 *  This is the C++ version of the Standard C Library header @c math.h,
 *  and its contents are (mostly) the same as that header, but are all
 *  contained in the namespace @c std (except for names which are defined
 *  as macros in C).
 */

//
// ISO C++ 14882: 26.5  C library
//

#ifndef _GLIBCXX_CMATH
#define _GLIBCXX_CMATH 1

#pragma GCC system_header

#include <bits/c++config.h>
#include <bits/cpp_type_traits.h>
#include <ext/type_traits.h>

#include <math.h>

// Get rid of those macros defined in <math.h> in lieu of real functions.
#undef abs
#undef div
#undef acos
#undef asin
#undef atan
#undef atan2
#undef ceil
#undef cos
#undef cosh
#undef exp
#undef fabs
#undef floor
#undef fmod
#undef frexp
#undef ldexp
#undef log
#undef log10
#undef modf
#undef pow
#undef sin
#undef sinh
#undef sqrt
#undef tan
#undef tanh

_GLIBCXX_BEGIN_NAMESPACE(std)

  // Forward declaration of a helper function.  This really should be
  // an `exported' forward declaration.
  template<typename _Tp> _Tp __cmath_power(_Tp, unsigned int);

  inline double
  abs(double __x)
  { return __builtin_fabs(__x); }

  inline float
  abs(float __x)
  { return __builtin_fabsf(__x); }

  inline long double
  abs(long double __x)
  { return __builtin_fabsl(__x); }

  using ::acos;

  inline float
  acos(float __x)
  { return __builtin_acosf(__x); }

  inline long double
  acos(long double __x)
  { return __builtin_acosl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    acos(_Tp __x)
    { return __builtin_acos(__x); }

  using ::asin;

  inline float
  asin(float __x)
  { return __builtin_asinf(__x); }

  inline long double
  asin(long double __x)
  { return __builtin_asinl(__x); }

  template<typename _Tp>
  inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					 double>::__type
    asin(_Tp __x)
    { return __builtin_asin(__x); }

  using ::atan;

  inline float
  atan(float __x)
  { return __builtin_atanf(__x); }

  inline long double
  atan(long double __x)
  { return __builtin_atanl(__x); }

  template<typename _Tp>
  inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					 double>::__type
    atan(_Tp __x)
    { return __builtin_atan(__x); }

  using ::atan2;

  inline float
  atan2(float __y, float __x)
  { return __builtin_atan2f(__y, __x); }

  inline long double
  atan2(long double __y, long double __x)
  { return __builtin_atan2l(__y, __x); }

  template<typename _Tp, typename _Up>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value
    					   && __is_integer<_Up>::__value,
					   double>::__type
    atan2(_Tp __y, _Up __x)
    { return __builtin_atan2(__y, __x); }

  using ::ceil;

  inline float
  ceil(float __x)
  { return __builtin_ceilf(__x); }

  inline long double
  ceil(long double __x)
  { return __builtin_ceill(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    ceil(_Tp __x)
    { return __builtin_ceil(__x); }

  using ::cos;

  inline float
  cos(float __x)
  { return __builtin_cosf(__x); }

  inline long double
  cos(long double __x)
  { return __builtin_cosl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    cos(_Tp __x)
    { return __builtin_cos(__x); }

  using ::cosh;

  inline float
  cosh(float __x)
  { return __builtin_coshf(__x); }

  inline long double
  cosh(long double __x)
  { return __builtin_coshl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    cosh(_Tp __x)
    { return __builtin_cosh(__x); }

  using ::exp;

  inline float
  exp(float __x)
  { return __builtin_expf(__x); }

  inline long double
  exp(long double __x)
  { return __builtin_expl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    exp(_Tp __x)
    { return __builtin_exp(__x); }

  using ::fabs;

  inline float
  fabs(float __x)
  { return __builtin_fabsf(__x); }

  inline long double
  fabs(long double __x)
  { return __builtin_fabsl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    fabs(_Tp __x)
    { return __builtin_fabs(__x); }

  using ::floor;

  inline float
  floor(float __x)
  { return __builtin_floorf(__x); }

  inline long double
  floor(long double __x)
  { return __builtin_floorl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    floor(_Tp __x)
    { return __builtin_floor(__x); }

  using ::fmod;

  inline float
  fmod(float __x, float __y)
  { return __builtin_fmodf(__x, __y); }

  inline long double
  fmod(long double __x, long double __y)
  { return __builtin_fmodl(__x, __y); }

  using ::frexp;

  inline float
  frexp(float __x, int* __exp)
  { return __builtin_frexpf(__x, __exp); }

  inline long double
  frexp(long double __x, int* __exp)
  { return __builtin_frexpl(__x, __exp); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    frexp(_Tp __x, int* __exp)
    { return __builtin_frexp(__x, __exp); }

  using ::ldexp;

  inline float
  ldexp(float __x, int __exp)
  { return __builtin_ldexpf(__x, __exp); }

  inline long double
  ldexp(long double __x, int __exp)
  { return __builtin_ldexpl(__x, __exp); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
  ldexp(_Tp __x, int __exp)
  { return __builtin_ldexp(__x, __exp); }

  using ::log;

  inline float
  log(float __x)
  { return __builtin_logf(__x); }

  inline long double
  log(long double __x)
  { return __builtin_logl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    log(_Tp __x)
    { return __builtin_log(__x); }

  using ::log10;

  inline float
  log10(float __x)
  { return __builtin_log10f(__x); }

  inline long double
  log10(long double __x)
  { return __builtin_log10l(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    log10(_Tp __x)
    { return __builtin_log10(__x); }

  using ::modf;

  inline float
  modf(float __x, float* __iptr)
  { return __builtin_modff(__x, __iptr); }

  inline long double
  modf(long double __x, long double* __iptr)
  { return __builtin_modfl(__x, __iptr); }

  template<typename _Tp>
    inline _Tp
    __pow_helper(_Tp __x, int __n)
    {
      return __n < 0
        ? _Tp(1)/__cmath_power(__x, -__n)
        : __cmath_power(__x, __n);
    }

  using ::pow;

  inline float
  pow(float __x, float __y)
  { return __builtin_powf(__x, __y); }

  inline long double
  pow(long double __x, long double __y)
  { return __builtin_powl(__x, __y); }

  inline double
  pow(double __x, int __i)
  { return __builtin_powi(__x, __i); }

  inline float
  pow(float __x, int __n)
  { return __builtin_powif(__x, __n); }

  inline long double
  pow(long double __x, int __n)
  { return __builtin_powil(__x, __n); }

  using ::sin;

  inline float
  sin(float __x)
  { return __builtin_sinf(__x); }

  inline long double
  sin(long double __x)
  { return __builtin_sinl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    sin(_Tp __x)
    { return __builtin_sin(__x); }

  using ::sinh;

  inline float
  sinh(float __x)
  { return __builtin_sinhf(__x); }

  inline long double
  sinh(long double __x)
  { return __builtin_sinhl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    sinh(_Tp __x)
    { return __builtin_sinh(__x); }

  using ::sqrt;

  inline float
  sqrt(float __x)
  { return __builtin_sqrtf(__x); }

  inline long double
  sqrt(long double __x)
  { return __builtin_sqrtl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    sqrt(_Tp __x)
    { return __builtin_sqrt(__x); }

  using ::tan;

  inline float
  tan(float __x)
  { return __builtin_tanf(__x); }

  inline long double
  tan(long double __x)
  { return __builtin_tanl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    tan(_Tp __x)
    { return __builtin_tan(__x); }

  using ::tanh;

  inline float
  tanh(float __x)
  { return __builtin_tanhf(__x); }

  inline long double
  tanh(long double __x)
  { return __builtin_tanhl(__x); }

  template<typename _Tp>
    inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
					   double>::__type
    tanh(_Tp __x)
    { return __builtin_tanh(__x); }

_GLIBCXX_END_NAMESPACE

#if _GLIBCXX_USE_C99_MATH
#if !_GLIBCXX_USE_C99_FP_MACROS_DYNAMIC
// These are possible macros imported from C99-land. For strict
// conformance, remove possible C99-injected names from the global
// namespace, and sequester them in the __gnu_cxx extension namespace.

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  template<typename _Tp>
    inline int
    __capture_fpclassify(_Tp __f) { return fpclassify(__f); }

  template<typename _Tp>
    inline int
    __capture_isfinite(_Tp __f) { return isfinite(__f); }

  template<typename _Tp>
    inline int
    __capture_isinf(_Tp __f) { return isinf(__f); }

  template<typename _Tp>
    inline int
    __capture_isnan(_Tp __f) { return isnan(__f); }

  template<typename _Tp>
    inline int
    __capture_isnormal(_Tp __f) { return isnormal(__f); }

  template<typename _Tp>
    inline int
    __capture_signbit(_Tp __f) { return signbit(__f); }

  template<typename _Tp>
    inline int
    __capture_isgreater(_Tp __f1, _Tp __f2)
    { return isgreater(__f1, __f2); }

  template<typename _Tp>
    inline int
    __capture_isgreaterequal(_Tp __f1, _Tp __f2)
    { return isgreaterequal(__f1, __f2); }

  template<typename _Tp>
    inline int
    __capture_isless(_Tp __f1, _Tp __f2) { return isless(__f1, __f2); }

  template<typename _Tp>
    inline int
    __capture_islessequal(_Tp __f1, _Tp __f2)
    { return islessequal(__f1, __f2); }

  template<typename _Tp>
    inline int
    __capture_islessgreater(_Tp __f1, _Tp __f2)
    { return islessgreater(__f1, __f2); }

  template<typename _Tp>
    inline int
    __capture_isunordered(_Tp __f1, _Tp __f2)
    { return isunordered(__f1, __f2); }

_GLIBCXX_END_NAMESPACE

// Only undefine the C99 FP macros, if actually captured for namespace movement
#undef fpclassify
#undef isfinite
#undef isinf
#undef isnan
#undef isnormal
#undef signbit
#undef isgreater
#undef isgreaterequal
#undef isless
#undef islessequal
#undef islessgreater
#undef isunordered

_GLIBCXX_BEGIN_NAMESPACE(std)

  template<typename _Tp>
    inline int
    fpclassify(_Tp __f) { return ::__gnu_cxx::__capture_fpclassify(__f); }

  template<typename _Tp>
    inline int
    isfinite(_Tp __f) { return ::__gnu_cxx::__capture_isfinite(__f); }

  template<typename _Tp>
    inline int
    isinf(_Tp __f) { return ::__gnu_cxx::__capture_isinf(__f); }

  template<typename _Tp>
    inline int
    isnan(_Tp __f) { return ::__gnu_cxx::__capture_isnan(__f); }

  template<typename _Tp>
    inline int
    isnormal(_Tp __f) { return ::__gnu_cxx::__capture_isnormal(__f); }

  template<typename _Tp>
    inline int
    signbit(_Tp __f) { return ::__gnu_cxx::__capture_signbit(__f); }

  template<typename _Tp>
    inline int
    isgreater(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_isgreater(__f1, __f2); }

  template<typename _Tp>
    inline int
    isgreaterequal(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_isgreaterequal(__f1, __f2); }

  template<typename _Tp>
    inline int
    isless(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_isless(__f1, __f2); }

  template<typename _Tp>
    inline int
    islessequal(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_islessequal(__f1, __f2); }

  template<typename _Tp>
    inline int
    islessgreater(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_islessgreater(__f1, __f2); }

  template<typename _Tp>
    inline int
    isunordered(_Tp __f1, _Tp __f2)
    { return ::__gnu_cxx::__capture_isunordered(__f1, __f2); }

_GLIBCXX_END_NAMESPACE

#endif /* _GLIBCXX_USE_C99_FP_MACROS_DYNAMIC */
#endif

#ifndef _GLIBCXX_EXPORT_TEMPLATE
# include <bits/cmath.tcc>
#endif

#endif