williamr@2: /* williamr@2: * williamr@2: * Copyright (c) 1994 williamr@2: * Hewlett-Packard Company williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1997 williamr@2: * Moscow Center for SPARC Technology williamr@2: * williamr@2: * Copyright (c) 1999 williamr@2: * Boris Fomitchev williamr@2: * williamr@2: * This material is provided "as is", with absolutely no warranty expressed williamr@2: * or implied. Any use is at your own risk. williamr@2: * williamr@2: * Permission to use or copy this software for any purpose is hereby granted williamr@2: * without fee, provided the above notices are retained on all copies. williamr@2: * Permission to modify the code and to distribute modified code is granted, williamr@2: * provided the above notices are retained, and a notice that the code was williamr@2: * modified is included with the above copyright notice. williamr@2: * williamr@2: */ williamr@2: williamr@2: /* NOTE: This is an internal header file, included by other STL headers. williamr@2: * You should not attempt to use it directly. williamr@2: */ williamr@2: williamr@2: #ifndef _STLP_INTERNAL_QUEUE_H williamr@2: #define _STLP_INTERNAL_QUEUE_H williamr@2: williamr@2: #ifndef _STLP_INTERNAL_DEQUE_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: #ifndef _STLP_INTERNAL_VECTOR_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: #ifndef _STLP_INTERNAL_HEAP_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: #ifndef _STLP_INTERNAL_FUNCTION_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: #if defined(__SC__) && !defined(__DMC__) //*ty 12/07/2001 - since "comp" is a built-in type and reserved under SCpp williamr@2: #define comp _Comp williamr@2: #endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@2: # if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) williamr@2: template > williamr@2: # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) williamr@2: # define _STLP_QUEUE_ARGS _Tp williamr@2: template williamr@2: # else williamr@2: template williamr@2: # endif williamr@2: williamr@2: class queue { williamr@2: # if defined ( _STLP_QUEUE_ARGS ) williamr@2: typedef deque<_Tp> _Sequence; williamr@2: # endif williamr@2: public: williamr@2: typedef typename _Sequence::value_type value_type; williamr@2: typedef typename _Sequence::size_type size_type; williamr@2: typedef _Sequence container_type; williamr@2: williamr@2: typedef typename _Sequence::reference reference; williamr@2: typedef typename _Sequence::const_reference const_reference; williamr@2: williamr@2: protected: williamr@2: _Sequence c; williamr@2: public: williamr@2: queue() : c() {} williamr@2: explicit queue(const _Sequence& __c) : c(__c) {} williamr@2: williamr@2: bool empty() const { return c.empty(); } williamr@2: size_type size() const { return c.size(); } williamr@2: reference front() { return c.front(); } williamr@2: const_reference front() const { return c.front(); } williamr@2: reference back() { return c.back(); } williamr@2: const_reference back() const { return c.back(); } williamr@2: void push(const value_type& __x) { c.push_back(__x); } williamr@2: void pop() { c.pop_front(); } williamr@2: const _Sequence& _Get_c() const { return c; } williamr@2: }; williamr@2: williamr@2: # ifndef _STLP_QUEUE_ARGS williamr@2: # define _STLP_QUEUE_ARGS _Tp, _Sequence williamr@2: # define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence williamr@2: # else williamr@2: # define _STLP_QUEUE_HEADER_ARGS class _Tp williamr@2: # endif williamr@2: williamr@2: template < _STLP_QUEUE_HEADER_ARGS > williamr@2: inline bool _STLP_CALL williamr@2: operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) williamr@2: { williamr@2: return __x._Get_c() == __y._Get_c(); williamr@2: } williamr@2: williamr@2: template < _STLP_QUEUE_HEADER_ARGS > williamr@2: inline bool _STLP_CALL williamr@2: operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) williamr@2: { williamr@2: return __x._Get_c() < __y._Get_c(); williamr@2: } williamr@2: williamr@2: _STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > ) williamr@2: williamr@2: # if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG )) williamr@2: template , williamr@2: class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> > williamr@2: # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) williamr@2: template williamr@2: # else williamr@2: template williamr@2: # endif williamr@2: class priority_queue { williamr@2: # ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS williamr@2: typedef vector<_Tp> _Sequence; williamr@2: typedef less< typename vector<_Tp>::value_type> _Compare; williamr@2: # endif williamr@2: public: williamr@2: typedef typename _Sequence::value_type value_type; williamr@2: typedef typename _Sequence::size_type size_type; williamr@2: typedef _Sequence container_type; williamr@2: williamr@2: typedef typename _Sequence::reference reference; williamr@2: typedef typename _Sequence::const_reference const_reference; williamr@2: protected: williamr@2: _Sequence c; williamr@2: _Compare comp; williamr@2: public: williamr@2: priority_queue() : c() {} williamr@2: explicit priority_queue(const _Compare& __x) : c(), comp(__x) {} williamr@2: explicit priority_queue(const _Compare& __x, const _Sequence& __s) williamr@2: : c(__s), comp(__x) williamr@2: { make_heap(c.begin(), c.end(), comp); } williamr@2: williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template williamr@2: priority_queue(_InputIterator __first, _InputIterator __last) williamr@2: : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } williamr@2: williamr@2: template williamr@2: priority_queue(_InputIterator __first, williamr@2: _InputIterator __last, const _Compare& __x) williamr@2: : c(__first, __last), comp(__x) williamr@2: { make_heap(c.begin(), c.end(), comp); } williamr@2: williamr@2: template williamr@2: priority_queue(_InputIterator __first, _InputIterator __last, williamr@2: const _Compare& __x, const _Sequence& __s) williamr@2: : c(__s), comp(__x) williamr@2: { williamr@2: c.insert(c.end(), __first, __last); williamr@2: make_heap(c.begin(), c.end(), comp); williamr@2: } williamr@2: williamr@2: #else /* _STLP_MEMBER_TEMPLATES */ williamr@2: priority_queue(const value_type* __first, const value_type* __last) williamr@2: : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } williamr@2: williamr@2: priority_queue(const value_type* __first, const value_type* __last, williamr@2: const _Compare& __x) williamr@2: : c(__first, __last), comp(__x) williamr@2: { make_heap(c.begin(), c.end(), comp); } williamr@2: williamr@2: priority_queue(const value_type* __first, const value_type* __last, williamr@2: const _Compare& __x, const _Sequence& __c) williamr@2: : c(__c), comp(__x) williamr@2: { williamr@2: c.insert(c.end(), __first, __last); williamr@2: make_heap(c.begin(), c.end(), comp); williamr@2: } williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: bool empty() const { return c.empty(); } williamr@2: size_type size() const { return c.size(); } williamr@2: const_reference top() const { return c.front(); } williamr@2: void push(const value_type& __x) { williamr@2: _STLP_TRY { williamr@2: c.push_back(__x); williamr@2: push_heap(c.begin(), c.end(), comp); williamr@2: } williamr@2: _STLP_UNWIND(c.clear()); williamr@2: } williamr@2: void pop() { williamr@2: _STLP_TRY { williamr@2: pop_heap(c.begin(), c.end(), comp); williamr@2: c.pop_back(); williamr@2: } williamr@2: _STLP_UNWIND(c.clear()); williamr@2: } williamr@2: }; williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: # undef _STLP_QUEUE_ARGS williamr@2: # undef _STLP_QUEUE_HEADER_ARGS williamr@2: williamr@2: #endif /* _STLP_INTERNAL_QUEUE_H */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: