| // -*- C++ -*- |
| /*************************************************************************** |
| * |
| * queue - declarations of the C++ Standard Library queue |
| * and priority_queue class templates |
| * |
| * $Id: //stdlib/dev/include/queue#20 $ |
| * |
| *************************************************************************** |
| * |
| * 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) 1994-2005 Quovadx, Inc., acting through its Rogue Wave |
| * Software division. Licensed under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance with the |
| * License. You may obtain a copy of the License at |
| * http://www.apache.org/licenses/LICENSE-2.0. Unless required by |
| * applicable law or agreed to in writing, software distributed under |
| * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR |
| * CONDITIONS OF ANY KIND, either express or implied. See the License |
| * for the specific language governing permissions and limitations under |
| * the License. |
| * |
| **************************************************************************/ |
| |
| #ifndef _RWSTD_QUEUE_INCLUDED |
| #define _RWSTD_QUEUE_INCLUDED |
| |
| #include <deque> |
| #include <functional> |
| #include <vector> |
| |
| #include <rw/_heap.h> |
| #include <rw/_defs.h> |
| |
| |
| _RWSTD_NAMESPACE (std) { |
| |
| template <class _TypeT, |
| class _Container _RWSTD_COMPLEX_DEFAULT (deque<_TypeT>) > |
| class queue; |
| |
| template <class _TypeT, class _Container> |
| inline bool operator== (const queue<_TypeT, _Container>&, |
| const queue<_TypeT, _Container>&); |
| |
| template <class _TypeT, class _Container> |
| inline bool operator< (const queue<_TypeT, _Container>&, |
| const queue<_TypeT, _Container>&); |
| |
| template <class _TypeT, class _Container> |
| class queue |
| { |
| friend bool _RWSTD_SPECIALIZED_FRIEND (operator==) |
| (const queue&, const queue&); |
| |
| friend bool _RWSTD_SPECIALIZED_FRIEND (operator<) |
| (const queue&, const queue&); |
| |
| public: |
| |
| typedef _Container container_type; |
| typedef _TYPENAME container_type::value_type value_type; |
| typedef _TYPENAME container_type::size_type size_type; |
| // lwg issue 307: additional typedefs |
| typedef _TYPENAME container_type::reference reference; |
| typedef _TYPENAME container_type::const_reference const_reference; |
| |
| protected: |
| |
| container_type c; |
| |
| public: |
| |
| _EXPLICIT |
| queue (const container_type &__c = container_type ()) |
| : c (__c) { } |
| |
| bool empty () const { |
| return c.empty (); |
| } |
| |
| size_type size () const { |
| return c.size (); |
| } |
| |
| // lwg issue 307: return reference instead of value_type& |
| reference front () { |
| return c.front (); |
| } |
| |
| // lwg issue 307: return const_reference instead of const value_type& |
| const_reference front () const { |
| return c.front (); |
| } |
| |
| // lwg issue 307: return reference instead of value_type& |
| reference back () { |
| return c.back (); |
| } |
| |
| // lwg issue 307: return const_reference instead of const value_type& |
| const_reference back () const { |
| return c.back (); |
| } |
| |
| void push (const value_type &__x) { |
| c.push_back (__x); |
| } |
| |
| void pop () { |
| c.pop_front (); |
| } |
| }; |
| |
| template <class _TypeT, class _Container> |
| inline bool operator== (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return __x.c == __y.c; |
| } |
| |
| template <class _TypeT, class _Container> |
| inline bool operator< (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return __x.c < __y.c; |
| } |
| |
| template <class _TypeT, class _Container> |
| inline bool operator!= (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _TypeT, class _Container> |
| inline bool operator> (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return __y < __x; |
| } |
| |
| template <class _TypeT, class _Container> |
| inline bool operator>= (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return !(__x < __y); |
| } |
| |
| template <class _TypeT, class _Container> |
| inline bool operator<= (const queue<_TypeT, _Container> &__x, |
| const queue<_TypeT, _Container> &__y) |
| { |
| return !(__y < __x); |
| } |
| |
| |
| #ifndef _RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES |
| |
| template<class _TypeT, |
| class _Container = vector<_TypeT>, |
| class _Compare = less<_TYPENAME _Container::value_type> > |
| #else // if defined (_RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES) |
| template <class _TypeT, class _Container, class _Compare> |
| #endif // _RWSTD_NO_COMPLEX_DEFAULT_TEMPLATES |
| class priority_queue |
| { |
| public: |
| |
| typedef _Container container_type; |
| typedef _TYPENAME container_type::value_type value_type; |
| typedef _TYPENAME container_type::size_type size_type; |
| // lwg issue 307: additional typedefs |
| typedef _TYPENAME container_type::reference reference; |
| typedef _TYPENAME container_type::const_reference const_reference; |
| |
| protected: |
| |
| container_type c; |
| _Compare comp; |
| |
| public: |
| |
| _EXPLICIT |
| priority_queue (const _Compare &__cmp = _Compare (), |
| const container_type &__c = container_type ()) |
| : c (__c), comp (__cmp) { |
| _STD::make_heap (c.begin (), c.end (), comp); |
| } |
| |
| #ifndef _RWSTD_NO_INLINE_MEMBER_TEMPLATES |
| |
| template <class _InputIter> |
| priority_queue (_InputIter __first, _InputIter __last, |
| const _Compare &__cmp = _Compare (), |
| const _Container &__c = container_type ()) |
| : c (__c), comp (__cmp) { |
| c.insert (c.end (), __first, __last); |
| _STD::make_heap (c.begin (), c.end (), comp); |
| } |
| |
| #else // if defined (_RWSTD_NO_INLINE_MEMBER_TEMPLATES) |
| |
| priority_queue (_TYPENAME _Container::const_iterator __first, |
| _TYPENAME _Container::const_iterator __last, |
| const _Compare &__cmp = _Compare (), |
| const _Container &__c = container_type ()) |
| : c (__c), comp (__cmp) { |
| c.insert (c.end (), __first, __last); |
| _STD::make_heap (c.begin (), c.end (), comp); |
| } |
| |
| #endif // _RWSTD_NO_INLINE_MEMBER_TEMPLATES |
| |
| bool empty () const { |
| return c.empty (); |
| } |
| |
| size_type size () const { |
| return c.size (); |
| } |
| |
| const_reference top () const { |
| return c.front (); |
| } |
| |
| void push (const value_type &__x) { |
| c.push_back (__x); |
| _STD::push_heap (c.begin (), c.end (), comp); |
| } |
| |
| void pop () { |
| _STD::pop_heap (c.begin (), c.end (), comp); |
| c.pop_back (); |
| } |
| }; |
| |
| |
| } // namespace std |
| |
| |
| #endif // _RWSTD_QUEUE_INCLUDED |