cale(_Impl*) throw(); static void _S_initialize(); static void _S_initialize_once(); static category _S_normalize_category(category); void _M_coalesce(const locale& __base, const locale& __add, category __cat); }; // 22.1.1.1.2 Class locale::facet /** * @brief Localization functionality base class. * * The facet class is the base class for a localization feature, such as * money, time, and number printing. It provides common support for facets * and reference management. * * Facets may not be copied or assigned. */ class locale::facet { private: friend class locale; friend class locale::_Impl; mutable _Atomic_word _M_refcount; // Contains data from the underlying "C" library for the classic locale. static __c_locale _S_c_locale; // String literal for the name of the classic locale. static const char _S_c_name[2]; #ifdef __GTHREADS static __gthread_once_t _S_once; #endif static void _S_initialize_once(); protected: /** * @brief Facet constructor. * * This is the constructor provided by the standard. If refs is 0, the * facet is destroyed when the last referencing locale is destroyed. * Otherwise the facet will never be destroyed. * * @param refs The initial value for reference count. */ explicit facet(size_t __refs = 0) throw() : _M_refcount(__refs ? 1 : 0) { } /// Facet destructor. virtual ~facet(); static void _S_create_c_locale(__c_locale& __cloc, const char* __s, __c_locale __old = 0); static __c_locale _S_clone_c_locale(__c_locale& __cloc); static void _S_destroy_c_locale(__c_locale& __cloc); // Returns data from the underlying "C" library data for the // classic locale. static __c_locale _S_get_c_locale(); static const char* _S_get_c_name(); private: void _M_add_reference() const throw() { __gnu_cxx::__atomic_************add_dispatch(&_M_refcount, 1); } void _M_remove_reference() const throw() { if (__gnu_cxx::__exchange_and_add_dispatch(&_M_refcount, -1) == 1) { try { delete this; } catch(...) { } } } facet(const facet&); // Not defined. facet& operator=(const facet&); // Not defined. }; // 22.1.1.1.3 Class locale::id /** * @brief Facet ID class. * * The ID class provides facets with an index used to identify them. * Every facet class must define a public static member locale::id, or be * derived from a facet that provides this member, otherwise the facet * cannot be used in a locale. The locale::id ensures that each class * type gets a unique identifier. */ class locale::id { private: friend class locale; friend class locale::_Impl; template friend const _Facet& use_facet(const locale&); template friend bool has_facet(const locale&) throw (); // NB: There is no accessor for _M_index because it may be used // before the constructor is run; the effect of calling a member // function (even an inline) would be undefined. mutable size_t _M_index; // Last id number assigned. static _Atomic_word _S_refcount; void operator=(const id&); // Not defined. id(const id&); // Not defined. public: // NB: This class is always a static data member, and thus can be // counted on to be zero-initialized. /// Constructor. id() { } size_t _M_id() const; }; // Implementation object for locale. class locale::_Impl { public: // Friends. friend class locale; friend class locale::facet; template friend bool has_facet(const locale&) throw(); template friend const _Facet& use_facet(const locale&); template friend struct __use_cache; private: // Data Members. _Atomic_word _M_refcount; const facet** _M_facets; size_t _M_facets_size; const facet** _M_caches; char** _M_names; static const locale::id* const _S_id_ctype[]; static const locale::id* const _S_id_numeric[]; static const locale::id* const _S_id_collate[]; static const locale::id* const _S_id_time[]; static const locale::id* const _S_id_monetary[]; static const locale::id* const _S_id_messages[]; static const locale::id* const* const _S_facet_categories[]; void _M_add_reference() throw() { __gnu_cxx::__atomic_add_dispatch(&_M_refcount, 1); } void _M_remove_reference() throw() { if (__gnu_cxx::__exchange_and_add_dispatch(&_M_refcount, -1) == 1) { try { delete this; } catch(...) { } } } _Impl(const _Impl&, size_t); _Impl(const char*, size_t); _Impl(size_t) throw(); ~_Impl() throw(); _Impl(const _Impl&); // Not defined. void operator=(const _Impl&); // Not defined. bool _M_check_same_name() { bool __ret = true; if (_M_names[1]) // We must actually compare all the _M_names: can be all equal! for (size_t __i = 0; __ret && __i < _S_categories_size - 1; ++__i) __ret = __builtin_strcmp(_M_names[__i], _M_names[__i + 1]) == 0; return __ret; } void _M_replace_categories(const _Impl*, category); void _M_replace_category(const _Impl*, const locale::id* const*); void _M_replace_facet(const _Impl*, const locale::id*); void _M_install_facet(const locale::id*, const facet*); template void _M_init_facet(_Facet* __facet) { _M_install_facet(&_Facet::id, __facet); } void _M_install_cache(const facet*, size_t); }; /** * @brief Test for the presence of a facet. * * has_facet tests the locale argument for the presence of the facet type * provided as the template parameter. Facets derived from the facet * parameter will also return true. * * @param Facet The facet type to test the presence of. * @param locale The locale to test. * @return true if locale contains a facet of type Facet, else false. */ template bool has_facet(const locale& __loc) throw(); /** * @brief Return a facet. * * use_facet looks for and returns a reference to a facet of type Facet * where Facet is the template parameter. If has_facet(locale) is true, * there is a suitable facet to return. It throws std::bad_cast if the * locale doesn't contain a facet of type Facet. * * @param Facet The facet type to access. * @param locale The locale to use. * @return Reference to facet of type Facet. * @throw std::bad_cast if locale doesn't contain a facet of type Facet. */ template const _Facet& use_facet(const locale& __loc); /** * @brief Facet for localized string comparison. * * This facet encapsulates the code to compare strings in a localized * manner. * * The collate template uses protected virtual functions to provide * the actual results. The public accessors forward the call to * the virtual functions. These virtual functions are hooks for * developers to implement the behavior they require from the * collate facet. */ template class collate : public locale::facet { public: // Types: //@{ /// Public typedefs typedef _CharT char_type; typedef basic_string<_CharT> string_type; //@} protected: // Underlying "C" library locale information saved from // initialization, needed by collate_byname as well. __c_locale _M_c_locale_collate; public: /// Numpunct facet id. static locale::id id; /** * @brief Constructor performs initialization. * * This is the constructor provided by the standard. * * @param refs Passed to the base facet class. */ explicit collate(size_t __refs = 0) : facet(__refs), _M_c_locale_collate(_S_get_c_locale()) { } /** * @brief Internal constructor. Not for general use. * * This is a constructor for use by the library itself to set up new * locales. * * @param cloc The "C" locale. * @param refs Passed to the base facet class. */ explicit collate(__c_locale __cloc, size_t __refs = 0) : facet(__refs), _M_c_locale_collate(_S_clone_c_locale(__cloc)) { } /** * @brief Compare two strings. * * This function compares two strings and returns the result by calling * collate::do_compare(). * * @param lo1 Start of string 1. * @param hi1 End of string 1. * @param lo2 Start of string 2. * @param hi2 End of string 2. * @return 1 if string1 > string2, -1 if string1 < string2, else 0. */ int compare(const _CharT* __lo1, const _CharT* __hi1, const _CharT* __lo2, const _CharT* __hi2) const { return this->do_compare(__lo1, __hi1, __lo2, __hi2); } /** * @brief Transform string to comparable form. * * This function is a wrapper for strxfrm functionality. It takes the * input string and returns a modified string that can be directly * compared to other transformed strings. In the "C" locale, this * function just returns a copy of the input string. In some other * locales, it may replace two chars with one, change a char for * another, etc. It does so by returning collate::do_transform(). * * @param lo Start of string. * @param hi End of string. * @return Transformed string_type. */ string_type transform(const _CharT* __lo, const _CharT* __hi) const { return this->do_transform(__lo, __hi); } /** * @brief Return hash of a string. * * This function computes and returns a hash on the input string. It * does so by returning collate::do_hash(). * * @param lo Start of string. * @param hi End of string. * @return Hash value. */ long hash(const _CharT* __lo, const _CharT* __hi) const { return this->do_hash(__lo, __hi); } // Used to abstract out _CharT bits in virtual member functions, below. int _M_compare(const _CharT*, const _CharT*) const; size_t _M_transform(_CharT*, const _CharT*, size_t) const; protected: /// Destructor. virtual ~collate() { _S_destroy_c_locale(_M_c_locale_collate); } /** * @brief Compare two strings. * * This function is a hook for derived classes to change the value * returned. @see compare(). * * @param lo1 Start of string 1. * @param hi1 End of string 1. * @param lo2 Start of string 2. * @param hi2 End of string 2. * @return 1 if string1 > string2, -1 if string1 < string2, else 0. */ virtual int do_compare(const _CharT* __lo1, const _CharT* __hi1, const _CharT* __lo2, const _CharT* __hi2) const; /** * @brief Transform string to comparable form. * * This function is a hook for derived classes to change the value * returned. * * @param lo1 Start of string 1. * @param hi1 End of string 1. * @param lo2 Start of string 2. * @param hi2 End of string 2. * @return 1 if string1 > string2, -1 if string1 < string2, else 0. */ virtual string_type do_transform(const _CharT* __lo, const _CharT* __hi) const; /** * @brief Return hash of a string. * * This function computes and returns a hash on the input string. This * function is a hook for derived classes to change the value returned. * * @param lo Start of string. * @param hi End of string. * @return Hash value. */ virtual long do_hash(const _CharT* __lo, const _CharT* __hi) const; }; template locale::id collate<_CharT>::id; // Specializations. template<> int collate::_M_compare(const char*, const char*) const; template<> size_t collate::_M_transform(char*, const char*, size_t) const; #ifdef _GLIBCXX_USE_WCHAR_T template<> int collate::_M_compare(const wchar_t*, const wchar_t*) const; template<> size_t collate::_M_transform(wchar_t*, const wchar_t*, size_t) const; #endif /// class collate_byname [22.2.4.2]. template class collate_byname : public collate<_CharT> { public: //@{ /// Public typedefs typedef _CharT char_type; typedef basic_string<_CharT> string_type; //@} explicit collate_byname(const char* __s, size_t __refs = 0) : collate<_CharT>(__refs) { if (__builtin_strcmp(__s, "C") != 0 && __builtin_strcmp(__s, "POSIX") != 0) { this->_S_destroy_c_locale(this->_M_c_locale_collate); this->_S_create_c_locale(this->_M_c_locale_collate, __s); } } protected: virtual ~collate_byname() { } }; _GLIBCXX_END_NAMESPACE #ifndef _GLIBCXX_EXPORT_TEMPLATE # include #endif #endif // Locale support -*- C++ -*- // Copyright (C) 2007, 2008 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 locale_classes.tcc * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ // // ISO C++ 14882: 22.1 Locales // #ifndef _LOCALE_CLASSES_TCC #define _LOCALE_CLASSES_TCC 1 #pragma GCC system_header _GLIBCXX_BEGIN_NAMESPACE(std) template locale:: locale(const locale& __other, _Facet* __f) { _M_impl = new _Impl(*__other._M_impl, 1); try { _M_impl->_M_install_facet(&_Facet::id, __f); } catch(...) { _M_impl->_M_remove_reference(); __throw_exception_again; } delete [] _M_impl->_M_names[0]; _M_impl->_M_names[0] = 0; // Unnamed. } template locale locale:: combine(const locale& __other) const { _Impl* __tmp = new _Impl(*_M_impl, 1); try { __tmp->_M_replace_facet(__other._M_impl, &_Facet::id); } catch(...) { __tmp->_M_remove_reference(); __throw_exception_again; } return locale(__tmp); } template bool locale:: operator()(const basic_string<_CharT, _Traits, _Alloc>& __s1, const basic_string<_CharT, _Traits, _Alloc>& __s2) const { typedef std::collate<_CharT> __collate_type; const __collate_type& __collate = use_facet<__collate_type>(*this); return (__collate.compare(__s1.data(), __s1.data() + __s1.length(), __s2.data(), __s2.data() + __s2.length()) < 0); } template bool has_facet(const locale& __loc) throw() { const size_t __i = _Facet::id._M_id(); const locale::facet** __facets = __loc._M_impl->_M_facets; return (__i < __loc._M_impl->_M_facets_size #ifdef __GXX_RTTI && dynamic_cast(__facets[__i])); #else && static_cast(__facets[__i])); #endif } template const _Facet& use_facet(const locale& __loc) { const size_t __i = _Facet::id._M_id(); const locale::facet** __facets = __loc._M_impl->_M_facets; if (__i >= __loc._M_impl->_M_facets_size || !__facets[__i]) __throw_bad_cast(); #ifdef __GXX_RTTI return dynamic_cast(*__facets[__i]); #else return static_cast(*__facets[__i]); #endif } // Generic version does nothing. template int collate<_CharT>::_M_compare(const _CharT*, const _CharT*) const { return 0; } // Generic version does nothing. template size_t collate<_CharT>::_M_transform(_CharT*, const _CharT*, size_t) const { return 0; } template int collate<_CharT>:: do_compare(const _CharT* __lo1, const _CharT* __hi1, const _CharT* __lo2, const _CharT* __hi2) const { // strcoll assumes zero-terminated strings so we make a copy // and then put a zero at the end. const string_type __one(__lo1, __hi1); const string_type __two(__lo2, __hi2); const _CharT* __p = __one.c_str(); const _CharT* __pend = __one.data() + __one.length(); const _CharT* __q = __two.c_str(); const _CharT* __qend = __two.data() + __two.length(); // strcoll stops when it sees a nul character so we break // the strings into zero-terminated substrings and pass those // to strcoll. for (;;) { const int __res = _M_compare(__p, __q); if (__res) return __res; __p += char_traits<_CharT>::length(__p); __q += char_traits<_CharT>::length(__q); if (__p == __pend && __q == __qend) return 0; else if (__p == __pend) return -1; else if (__q == __qend) return 1; __p++; __q++; } } template typename collate<_CharT>::string_type collate<_CharT>:: do_transform(const _CharT* __lo, const _CharT* __hi) const { string_type __ret; // strxfrm assumes zero-terminated strings so we make a copy const string_type __str(__lo, __hi); const _CharT* __p = __str.c_str(); const _CharT* __pend = __str.data() + __str.length(); size_t __len = (__hi - __lo) * 2; _CharT* __c = new _CharT[__len]; try { // strxfrm stops when it sees a nul character so we break // the string into zero-terminated substrings and pass those // to strxfrm. for (;;) { // First try a buffer perhaps big enough. size_t __res = _M_transform(__c, __p, __len); // If the buffer was not large enough, try again with the // correct size. if (__res >= __len) { __len = __res + 1; delete [] __c, __c = 0; __c = new _CharT[__len]; __res = _M_transform(__c, __p, __len); } __ret.append(__c, __res); __p += char_traits<_CharT>::length(__p); if (__p == __pend) break; __p++; __ret.push_back(_CharT()); } } catch(...) { delete [] __c; __throw_exception_again; } delete [] __c; return __ret; } template long collate<_CharT>:: do_hash(const _CharT* __lo, const _CharT* __hi) const { unsigned long __val = 0; for (; __lo < __hi; ++__lo) __val = *__lo + ((__val << 7) | (__val >> (__gnu_cxx::__numeric_traits:: __digits - 7))); return static_cast(__val); } // Inhibit implicit instantiations for required instantiations, // which are defined via explicit instantiations elsewhere. // NB: This syntax is a GNU extension. #if _GLIBCXX_EXTERN_TEMPLATE extern template class collate; extern template class collate_byname; extern template const collate& use_facet >(const locale&); extern template bool has_facet >(const locale&); #ifdef _GLIBCXX_USE_WCHAR_T extern template class collate; extern template class collate_byname; extern template const collate& use_facet >(const locale&); extern template bool has_facet >(const locale&); #endif #endif _GLIBCXX_END_NAMESPACE #endif // Functions used by iterators -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // 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-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 stl_iterator_base_funcs.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. * * This file contains all of the general iterator-related utility * functions, such as distance() and advance(). */ #ifndef _STL_ITERATOR_BASE_FUNCS_H #define _STL_ITERATOR_BASE_FUNCS_H 1 #pragma GCC system_header #include _GLIBCXX_BEGIN_NAMESPACE(std) template inline typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag) { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) typename iterator_traits<_InputIterator>::difference_type __n = 0; while (__first != __last) { ++__first; ++__n; } return __n; } template inline typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) return __last - __first; } /** * @brief A generalization of pointer arithmetic. * @param first An input iterator. * @param last An input iterator. * @return The distance between them. * * Returns @c n such that first + n == last. This requires that @p last * must be reachable from @p first. Note that @c n may be negative. * * For random access iterators, this uses their @c + and @c - operations * and are constant time. For other %iterator classes they are linear time. */ template inline typename iterator_traits<_InputIterator>::difference_type distance(_InputIterator __first, _InputIterator __last) { // concept requirements -- taken care of in __distance return std::__distance(__first, __last, std::__iterator_category(__first)); } template inline void __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) while (__n--) ++__i; } template inline void __advance(_BidirectionalIterator& __i, _Distance __n, bidirectional_iterator_tag) { // concept requirements __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator>) if (__n > 0) while (__n--) ++__i; else while (__n++) --__i; } template inline void __advance(_RandomAccessIterator& __i, _Distance __n, random_access_iterator_tag) { // concept requirements __glibcxx_function_requires(_RandomAccessIteratorConcept< _RandomAccessIterator>) __i += __n; } /** * @brief A generalization of pointer arithmetic. * @param i An input iterator. * @param n The "delta" by which to change @p i. * @return Nothing. * * This increments @p i by @p n. For bidirectional and random access * iterators, @p n may be negative, in which case @p i is decremented. * * For random access iterators, this uses their @c + and @c - operations * and are constant time. For other %iterator classes they are linear time. */ template inline void advance(_InputIterator& __i, _Distance __n) { // concept requirements -- taken care of in __advance typename iterator_traits<_InputIterator>::difference_type __d = __n; std::__advance(__i, __d, std::__iterator_category(__i)); } _GLIBCXX_END_NAMESPACE #endif /* _STL_ITERATOR_BASE_FUNCS_H */ // The template and inlines for the -*- C++ -*- internal _Array helper class. // Copyright (C) 1997, 1998, 1999, 2003, 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 valarray_array.tcc * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ // Written by Gabriel Dos Reis #ifndef _VALARRAY_ARRAY_TCC #define _VALARRAY_ARRAY_TCC 1 _GLIBCXX_BEGIN_NAMESPACE(std) template void __valarray_fill(_Array<_Tp> __a, size_t __n, _Array __m, const _Tp& __t) { _Tp* __p = __a._M_data; bool* __ok (__m._M_data); for (size_t __i=0; __i < __n; ++__i, ++__ok, ++__p) { while (!*__ok) { ++__ok; ++__p; } *__p = __t; } } // Copy n elements of a into consecutive elements of b. When m is // false, the corresponding element of a is skipped. m must contain // at least n true elements. a must contain at least n elements and // enough elements to match up with m through the nth true element // of m. I.e. if n is 10, m has 15 elements with 5 false followed // by 10 true, a must have 15 elements. template void __valarray_copy(_Array<_Tp> __a, _Array __m, _Array<_Tp> __b, size_t __n) { _Tp* __p (__a._M_data); bool* __ok (__m._M_data); for (_Tp* __q = __b._M_data; __q < __b._M_data + __n; ++__q, ++__ok, ++__p) { while (! *__ok) { ++__ok; ++__p; } *__q = *__p; } } // Copy n consecutive elements from a into elements of b. Elements // of b are skipped if the corresponding element of m is false. m // must contain at least n true elements. b must have at least as // many elements as the index of the nth true element of m. I.e. if // m has 15 elements with 5 false followed by 10 true, b must have // at least 15 elements. template void __valarray_copy(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b, _Array __m) { _Tp* __q (__b._M_data); bool* __ok (__m._M_data); for (_Tp* __p = __a._M_data; __p < __a._M_data+__n; ++__p, ++__ok, ++__q) { while (! *__ok) { ++__ok; ++__q; } *__q = *__p; } } // Copy n elements from a into elements of b. Elements of a are // skipped if the corresponding element of m is false. Elements of // b are skipped if the corresponding element of k is false. m and // k must contain at least n true elements. a and b must have at // least as many elements as the index of the nth true element of m. template void __valarray_copy(_Array<_Tp> __a, _Array __m, size_t __n, _Array<_Tp> __b, _Array __k) { _Tp* __p (__a._M_data); _Tp* __q (__b._M_data); bool* __srcok (__m._M_data); bool* __dstok (__k._M_data); for (size_t __i = 0; __i < __n; ++__srcok, ++__p, ++__dstok, ++__q, ++__i) { while (! *__srcok) { ++__srcok; ++__p; } while (! *__dstok) { ++__dstok; ++__q; } *__q = *__p; } } // Copy n consecutive elements of e into consecutive elements of a. // I.e. a[i] = e[i]. template void __valarray_copy(const _Expr<_Dom, _Tp>& __e, size_t __n, _Array<_Tp> __a) { _Tp* __p (__a._M_data); for (size_t __i = 0; __i < __n; ++__i, ++__p) *__p = __e[__i]; } // Copy n consecutive elements of e into elements of a using stride // s. I.e., a[0] = e[0], a[s] = e[1], a[2*s] = e[2]. template void __valarray_copy(const _Expr<_Dom, _Tp>& __e, size_t __n, _Array<_Tp> __a, size_t __s) { _Tp* __p (__a._M_data); for (size_t __i = 0; __i < __n; ++__i, __p += __s) *__p = __e[__i]; } // Copy n consecutive elements of e into elements of a indexed by // contents of i. I.e., a[i[0]] = e[0]. template void __valarray_copy(const _Expr<_Dom, _Tp>& __e, size_t __n, _Array<_Tp> __a, _Array __i) { size_t* __j (__i._M_data); for (size_t __k = 0; __k < __n; ++__k, ++__j) __a._M_data[*__j] = __e[__k]; } // Copy n elements of e indexed by contents of f into elements of a // indexed by contents of i. I.e., a[i[0]] = e[f[0]]. template void __valarray_copy(_Array<_Tp> __e, _Array __f, size_t __n, _Array<_Tp> __a, _Array __i) { size_t* __g (__f._M_data); size_t* __j (__i._M_data); for (size_t __k = 0; __k < __n; ++__k, ++__j, ++__g) __a._M_data[*__j] = __e._M_data[*__g]; } // Copy n consecutive elements of e into elements of a. Elements of // a are skipped if the corresponding element of m is false. m must // have at least n true elements and a must have at least as many // elements as the index of the nth true element of m. I.e. if m // has 5 false followed by 10 true elements and n == 10, a must have // at least 15 elements. template void __valarray_copy(const _Expr<_Dom, _Tp>& __e, size_t __n, _Array<_Tp> __a, _Array __m) { bool* __ok (__m._M_data); _Tp* __p (__a._M_data); for (size_t __i = 0; __i < __n; ++__i, ++__ok, ++__p) { while (! *__ok) { ++__ok; ++__p; } *__p = __e[__i]; } } template void __valarray_copy_construct(const _Expr<_Dom, _Tp>& __e, size_t __n, _Array<_Tp> __a) { _Tp* __p (__a._M_data); for (size_t __i = 0; __i < __n; ++__i, ++__p) new (__p) _Tp(__e[__i]); } template void __valarray_copy_construct(_Array<_Tp> __a, _Array __m, _Array<_Tp> __b, size_t __n) { _Tp* __p (__a._M_data); bool* __ok (__m._M_data); for (_Tp* __q = __b._M_data; __q < __b._M_data+__n; ++__q, ++__ok, ++__p) { while (! *__ok) { ++__ok; ++__p; } new (__q) _Tp(*__p); } } _GLIBCXX_END_NAMESPACE #endif /* _VALARRAY_ARRAY_TCC */ // Algorithm implementation -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 // 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 stl_algo.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ #ifndef _STL_ALGO_H #define _STL_ALGO_H 1 #include // for rand #include #include #include // for _Temporary_buffer #include // See concept_check.h for the __glibcxx_*_requires macros. _GLIBCXX_BEGIN_NAMESPACE(std) /** * @brief Find the median of three values. * @param a A value. * @param b A value. * @param c A value. * @return One of @p a, @p b or @p c. * * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n * then the value returned will be @c m. * This is an SGI extension. * @ingroup SGIextensions */ template inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { // concept requirements __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) if (__a < __b) if (__b < __c) return __b; else if (__a < __c) return __c; else return __a; else if (__a < __c) return __a; else if (__b < __c) return __c; else return __b; } /** * @brief Find the median of three values using a predicate for comparison. * @param a A value. * @param b A value. * @param c A value. * @param comp A binary predicate. * @return One of @p a, @p b or @p c. * * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) * and @p comp(m,n) are both true then the value returned will be @c m. * This is an SGI extension. * @ingroup SGIextensions */ template inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { // concept requirements __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, _Tp, _Tp>) if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; else if (__comp(__a, __c)) return __c; else return __a; else if (__comp(__a, __c)) return __a; else if (__comp(__b, __c)) return __c; else return __b; } // for_each /// This is an overload used by find() for the Input Iterator case. template inline _InputIterator __find(_InputIterator __first, _InputIterator __last, const _Tp& __val, input_iterator_tag) { while (__first != __last && !(*__first == __val)) ++__first; return __first; } /// This is an overload used by find_if() for the Input Iterator case. template inline _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag) { while (__first != __last && !bool(__pred(*__first))) ++__first; return __first; } /// This is an overload used by find() for the RAI case. template _RandomAccessIterator __find(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __val, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIterator>::difference_type __trip_count = (__last - __first) >> 2; for (; __trip_count > 0; --__trip_count) { if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; } switch (__last - __first) { case 3: if (*__first == __val) return __first; ++__first; case 2: if (*__first == __val) return __first; ++__first; case 1: if (*__first == __val) return __first; ++__first; case 0: default: return __last; } } /// This is an overload used by find_if() for the RAI case. template _RandomAccessIterator __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIterator>::difference_type __trip_count = (__last - __first) >> 2; for (; __trip_count > 0; --__trip_count) { if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; } switch (__last - __first) { case 3: if (__pred(*__first)) return __first; ++__first; case 2: if (__pred(*__first)) return __first; ++__first; case 1: if (__pred(*__first)) return __first; ++__first; case 0: default: return __last; } } // set_difference // set_intersection // set_symmetric_difference // set_union // for_each // find // find_if // find_first_of // adjacent_find // count // count_if // search /** * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) * overloaded for forward iterators. */ template _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp& __val, std::forward_iterator_tag) { __first = _GLIBCXX_STD_P::find(__first, __last, __val); while (__first != __last) { typename iterator_traits<_ForwardIterator>::difference_type __n = __count; _ForwardIterator __i = __first; ++__i; while (__i != __last && __n != 1 && *__i == __val) { ++__i; --__n; } if (__n == 1) return __first; if (__i == __last) return __last; __first = _GLIBCXX_STD_P::find(++__i, __last, __val); } return __last; } /** * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) * overloaded for random access iterators. */ template _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp& __val, std::random_access_iterator_tag) { typedef typename std::iterator_traits<_RandomAccessIter>::difference_type _DistanceType; _DistanceType __tailSize = __last - __first; const _DistanceType __pattSize = __count; if (__tailSize < __pattSize) return __last; const _DistanceType __skipOffset = __pattSize - 1; _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize -= __pattSize; while (1) // the main loop... { // __lookAhead here is always pointing to the last element of next // possible match. while (!(*__lookAhead == __val)) // the skip loop... { if (__tailSize < __pattSize) return __last; // Failure __lookAhead += __pattSize; __tailSize -= __pattSize; } _DistanceType __remainder = __skipOffset; for (_RandomAccessIter __backTrack = __lookAhead - 1; *__backTrack == __val; --__backTrack) { if (--__remainder == 0) return (__lookAhead - __skipOffset); // Success } if (__remainder > __tailSize) return __last; // Failure __lookAhead += __remainder; __tailSize -= __remainder; } } // search_n /** * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, * _BinaryPredicate) * overloaded for forward iterators. */ template _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp& __val, _BinaryPredicate __binary_pred, std::forward_iterator_tag) { while (__first != __last && !bool(__binary_pred(*__first, __val))) ++__first; while (__first != __last) { typename iterator_traits<_ForwardIterator>::difference_type __n = __count; _ForwardIterator __i = __first; ++__i; while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val))) { ++__i; --__n; } if (__n == 1) return __first; if (__i == __last) return __last; __first = ++__i; while (__first != __last && !bool(__binary_pred(*__first, __val))) ++__first; } return __last; } /** * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, * _BinaryPredicate) * overloaded for random access iterators. */ template _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp& __val, _BinaryPredicate __binary_pred, std::random_access_iterator_tag) { typedef typename std::iterator_traits<_RandomAccessIter>::difference_type _DistanceType; _DistanceType __tailSize = __last - __first; const _DistanceType __pattSize = __count; if (__tailSize < __pattSize) return __last; const _DistanceType __skipOffset = __pattSize - 1; _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize -= __pattSize; while (1) // the main loop... { // __lookAhead here is always pointing to the last element of next /*************+++++++++ + + + + +++++++++++++++++++ +!+"+#+$+%+&+'+(+)+*+++,+-+.+/+0+1+2+3+4+5+6+7+8+9+:+;+<+=+>+?+@+A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T+U+V+W+X+Y+Z+[+\+]+^+_+`+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z+{+|+}+~++++++++++++++++++++++++++++++++++++++/ possible match. while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop... { if (__tailSize < __pattSize) return __last; // Failure __lookAhead += __pattSize; __tailSize -= __pattSize; } _DistanceType __remainder = __skipOffset; for (_RandomAccessIter __backTrack = __lookAhead - 1; __binary_pred(*__backTrack, __val); --__backTrack) { if (--__remainder == 0) return (__lookAhead - __skipOffset); // Success } if (__remainder > __tailSize) return __last; // Failure __lookAhead += __remainder; __tailSize -= __remainder; } } // find_end for forward iterators. template _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, forward_iterator_tag, forward_iterator_tag) { if (__first2 == __last2) return __last1; else { _ForwardIterator1 __result = __last1; while (1) { _ForwardIterator1 __new_result = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2); if (__new_result == __last1) return __result; else { __result = __new_result; __first1 = __new_result; ++__first1; } } } } template _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, forward_iterator_tag, forward_iterator_tag, _BinaryPredicate __comp) { if (__first2 == __last2) return __last1; else { _ForwardIterator1 __result = __last1; while (1) { _ForwardIterator1 __new_result = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2, __comp); if (__new_result == __last1) return __result; else { __result = __new_result; __first1 = __new_result; ++__first1; } } } } // find_end for bidirectional iterators (much faster). template _BidirectionalIterator1 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { // concept requirements __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator1>) __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator2>) typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; _RevIterator1 __rlast1(__first1); _RevIterator2 __rlast2(__first2); _RevIterator1 __rresult = _GLIBCXX_STD_P::search(_RevIterator1(__last1), __rlast1, _RevIterator2(__last2), __rlast2); if (__rresult == __rlast1) return __last1; else { _BidirectionalIterator1 __result = __rresult.base(); std::advance(__result, -std::distance(__first2, __last2)); return __result; } } template _BidirectionalIterator1 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag, _BinaryPredicate __comp) { // concept requirements __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator1>) __glibcxx_function_requires(_BidirectionalIteratorConcept< _BidirectionalIterator2>) typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; _RevIterator1 __rlast1(__first1); _RevIterator2 __rlast2(__first2); _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, _RevIterator2(__last2), __rlast2, __comp); if (__rresult == __rlast1) return __last1; else { _BidirectionalIterator1 __result = __rresult.base(); std::advance(__result, -std::distance(__first2, __last2)); return __result; } } /** * @brief Find last matching subsequence in a sequence. * @param first1 Start of range to search. * @param last1 End of range to search. * @param first2 Start of sequence to match. * @param last2 End of sequence to match. * @return The last iterator @c i in the range * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) * for each @c N in the range @p [0,last2-first2), or @p last1 if no * such iterator exists. * * Searches the range @p [first1,last1) for a sub-sequence that compares * equal value-by-value with the sequence given by @p [first2,last2) and * returns an iterator to the first element of the sub-sequence, or * @p last1 if the sub-sequence is not found. The sub-sequence will be the * last such subsequence contained in [first,last1). * * Because the sub-sequence must lie completely within the range * @p [first1,last1) it must start at a position less than * @p last1-(last2-first2) where @p last2-first2 is the length of the * sub-sequence. * This means that the returned iterator @c i will be in the range * @p [first1,last1-(last2-first2)) */ template inline _ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) __glibcxx_function_requires(_EqualOpConcept< typename iterator_traits<_ForwardIterator1>::value_type, typename iterator_traits<_ForwardIterator2>::value_type>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); return std::__find_end(__first1, __last1, __first2, __last2, std::__iterator_category(__first1), std::__iterator_category(__first2)); } /** * @brief Find last matching subsequence in a sequence using a predicate. * @param first1 Start of range to search. * @param last1 End of range to search. * @param first2 Start of sequence to match. * @param last2 End of sequence to match. * @param comp The predicate to use. * @return The last iterator @c i in the range * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or * @p last1 if no such iterator exists. * * Searches the range @p [first1,last1) for a sub-sequence that compares * equal value-by-value with the sequence given by @p [first2,last2) using * comp as a predicate and returns an iterator to the first element of the * sub-sequence, or @p last1 if the sub-sequence is not found. The * sub-sequence will be the last such subsequence contained in * [first,last1). * * Because the sub-sequence must lie completely within the range * @p [first1,last1) it must start at a position less than * @p last1-(last2-first2) where @p last2-first2 is the length of the * sub-sequence. * This means that the returned iterator @c i will be in the range * @p [first1,last1-(last2-first2)) */ template inline _ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __comp) { // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, typename iterator_traits<_ForwardIterator1>::value_type, typename iterator_traits<_ForwardIterator2>::value_type>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); return std::__find_end(__first1, __last1, __first2, __last2, std::__iterator_category(__first1), std::__iterator_category(__first2), __comp); } /** * @brief Copy a sequence, removing elements of a given value. * @param first An input iterator. * @param last An input iterator. * @param result An output iterator. * @param value The value to be removed. * @return An iterator designating the end of the resulting sequence. * * Copies each element in the range @p [first,last) not equal to @p value * to the range beginning at @p result. * remove_copy() is stable, so the relative order of elements that are * copied is unchanged. */ template _OutputIterator remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value) { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, typename iterator_traits<_InputIterator>::value_type>) __glibcxx_function_requires(_EqualOpConcept< typename iterator_traits<_InputIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); for (; __first != __last; ++__first) if (!(*__first == __value)) { *__result = *__first; ++__result; } return __result; } /** * @brief Copy a sequence, removing elements for which a predicate is true. * @param first An input iterator. * @param last An input iterator. * @param result An output iterator. * @param pred A predicate. * @return An iterator designating the end of the resulting sequence. * * Copies each element in the range @p [first,last) for which * @p pred returns false to the range beginning at @p result. * * remove_copy_if() is stable, so the relative order of elements that are * copied is unchanged. */ template _OutputIterator remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred) { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, typename iterator_traits<_InputIterator>::value_type>) __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); for (; __first != __last; ++__first) if (!bool(__pred(*__first))) { *__result = *__first; ++__result; } return __result; } /** * @brief Remove elements from a sequence. * @param first An input iterator. * @param last An input iterator. * @param value The value to be removed. * @return An iterator designating the end of the resulting sequence. * * All elements equal to @p value are removed from the range * @p [first,last). * * remove() is stable, so the relative order of elements that are * not removed is unchanged. * * Elements between the end of the resulting sequence and @p last * are still present, but their value is unspecified. */ template _ForwardIterator remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { // concept requirements __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< _ForwardIterator>) __glibcxx_function_requires(_EqualOpConcept< typename iterator_traits<_ForwardIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); __first = _GLIBCXX_STD_P::find(__first, __last, __value); if(__first == __last) return __first; _ForwardIterator __result = __first; ++__first; for(; __first != __last; ++__first) if(!(*__first == __value)) { *__result = _GLIBCXX_MOVE(*__first); ++__result; } return __result; } /** * @brief Remove elements from a sequence using a predicate. * @param first A forward iterator. * @param last A forward iterator. * @param pred A predicate. * @return An iterator designating the end of the resulting sequence. * * All elements for which @p pred ret