home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _queue.h < prev    next >
C/C++ Source or Header  |  2002-01-18  |  6KB  |  213 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Copyright (c) 1996,1997
  7.  * Silicon Graphics Computer Systems, Inc.
  8.  *
  9.  * Copyright (c) 1997
  10.  * Moscow Center for SPARC Technology
  11.  *
  12.  * Copyright (c) 1999 
  13.  * Boris Fomitchev
  14.  *
  15.  * This material is provided "as is", with absolutely no warranty expressed
  16.  * or implied. Any use is at your own risk.
  17.  *
  18.  * Permission to use or copy this software for any purpose is hereby granted 
  19.  * without fee, provided the above notices are retained on all copies.
  20.  * Permission to modify the code and to distribute modified code is granted,
  21.  * provided the above notices are retained, and a notice that the code was
  22.  * modified is included with the above copyright notice.
  23.  *
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef _STLP_INTERNAL_QUEUE_H
  31. #define _STLP_INTERNAL_QUEUE_H
  32.  
  33. #ifndef _STLP_INTERNAL_DEQUE_H
  34. # include <stl/_deque.h>
  35. #endif
  36.  
  37. #ifndef _STLP_INTERNAL_VECTOR_H
  38. # include <stl/_vector.h>
  39. #endif
  40.  
  41. #ifndef _STLP_INTERNAL_HEAP_H
  42. # include <stl/_heap.h>
  43. #endif
  44.  
  45. #ifndef _STLP_INTERNAL_FUNCTION_H
  46. # include <stl/_function.h>
  47. #endif
  48.  
  49. #if defined(__SC__)        //*ty 12/07/2001 - since "comp" is a built-in type and reserved under SCpp
  50. #define comp _Comp
  51. #endif
  52.  
  53. _STLP_BEGIN_NAMESPACE
  54.  
  55. # if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES )
  56. template <class _Tp, class _Sequence = deque<_Tp> >
  57. # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
  58. #  define _STLP_QUEUE_ARGS _Tp
  59. template <class _Tp>
  60. # else
  61. template <class _Tp, class _Sequence>
  62. # endif
  63.  
  64. class queue {
  65. # if defined ( _STLP_QUEUE_ARGS )
  66.   typedef deque<_Tp> _Sequence;
  67. # endif
  68. public:
  69.   typedef typename _Sequence::value_type      value_type;
  70.   typedef typename _Sequence::size_type       size_type;
  71.   typedef          _Sequence                  container_type;
  72.  
  73.   typedef typename _Sequence::reference       reference;
  74.   typedef typename _Sequence::const_reference const_reference;
  75.  
  76. protected:
  77.   _Sequence c;
  78. public:
  79.   queue() : c() {}
  80.   explicit queue(const _Sequence& __c) : c(__c) {}
  81.  
  82.   bool empty() const { return c.empty(); }
  83.   size_type size() const { return c.size(); }
  84.   reference front() { return c.front(); }
  85.   const_reference front() const { return c.front(); }
  86.   reference back() { return c.back(); }
  87.   const_reference back() const { return c.back(); }
  88.   void push(const value_type& __x) { c.push_back(__x); }
  89.   void pop() { c.pop_front(); }
  90.   const _Sequence& _Get_c() const { return c; }
  91. };
  92.  
  93. # ifndef _STLP_QUEUE_ARGS
  94. #  define _STLP_QUEUE_ARGS _Tp, _Sequence
  95. #  define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence
  96. # else
  97. #  define _STLP_QUEUE_HEADER_ARGS class _Tp
  98. # endif
  99.  
  100. template < _STLP_QUEUE_HEADER_ARGS >
  101. inline bool _STLP_CALL 
  102. operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y)
  103. {
  104.   return __x._Get_c() == __y._Get_c();
  105. }
  106.  
  107. template < _STLP_QUEUE_HEADER_ARGS >
  108. inline bool _STLP_CALL
  109. operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y)
  110. {
  111.   return __x._Get_c() < __y._Get_c();
  112. }
  113.  
  114. _STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > )
  115.  
  116. # if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG ))
  117. template <class _Tp, class _Sequence = vector<_Tp>, 
  118.           class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> >
  119. # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
  120. template <class _Tp>
  121. # else
  122. template <class _Tp, class _Sequence, class _Compare>
  123. # endif
  124. class  priority_queue {
  125. # ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS
  126.   typedef vector<_Tp> _Sequence;
  127.   typedef less< typename vector<_Tp>::value_type> _Compare; 
  128. # endif
  129. public:
  130.   typedef typename _Sequence::value_type      value_type;
  131.   typedef typename _Sequence::size_type       size_type;
  132.   typedef          _Sequence                  container_type;
  133.  
  134.   typedef typename _Sequence::reference       reference;
  135.   typedef typename _Sequence::const_reference const_reference;
  136. protected:
  137.   _Sequence c;
  138.   _Compare comp;
  139. public:
  140.   priority_queue() : c() {}
  141.   explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
  142.   priority_queue(const _Compare& __x, const _Sequence& __s) 
  143.     : c(__s), comp(__x)
  144.     { make_heap(c.begin(), c.end(), comp); }
  145.  
  146. #ifdef _STLP_MEMBER_TEMPLATES
  147.   template <class _InputIterator>
  148.   priority_queue(_InputIterator __first, _InputIterator __last) 
  149.     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  150.  
  151.   template <class _InputIterator>
  152.   priority_queue(_InputIterator __first, 
  153.                  _InputIterator __last, const _Compare& __x)
  154.     : c(__first, __last), comp(__x)
  155.     { make_heap(c.begin(), c.end(), comp); }
  156.  
  157.   template <class _InputIterator>
  158.   priority_queue(_InputIterator __first, _InputIterator __last,
  159.                  const _Compare& __x, const _Sequence& __s)
  160.   : c(__s), comp(__x)
  161.   { 
  162.     c.insert(c.end(), __first, __last);
  163.     make_heap(c.begin(), c.end(), comp);
  164.   }
  165.  
  166. #else /* _STLP_MEMBER_TEMPLATES */
  167.   priority_queue(const value_type* __first, const value_type* __last) 
  168.     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  169.  
  170.   priority_queue(const value_type* __first, const value_type* __last, 
  171.                  const _Compare& __x) 
  172.     : c(__first, __last), comp(__x)
  173.     { make_heap(c.begin(), c.end(), comp); }
  174.  
  175.   priority_queue(const value_type* __first, const value_type* __last, 
  176.                  const _Compare& __x, const _Sequence& __c)
  177.     : c(__c), comp(__x)
  178.   { 
  179.     c.insert(c.end(), __first, __last);
  180.     make_heap(c.begin(), c.end(), comp);
  181.   }
  182. #endif /* _STLP_MEMBER_TEMPLATES */
  183.  
  184.   bool empty() const { return c.empty(); }
  185.   size_type size() const { return c.size(); }
  186.   const_reference top() const { return c.front(); }
  187.   void push(const value_type& __x) {
  188.     _STLP_TRY {
  189.       c.push_back(__x); 
  190.       push_heap(c.begin(), c.end(), comp);
  191.     }
  192.     _STLP_UNWIND(c.clear());
  193.   }
  194.   void pop() {
  195.     _STLP_TRY {
  196.       pop_heap(c.begin(), c.end(), comp);
  197.       c.pop_back();
  198.     }
  199.     _STLP_UNWIND(c.clear());
  200.   }
  201. };
  202.  
  203. _STLP_END_NAMESPACE
  204.  
  205. #  undef _STLP_QUEUE_ARGS
  206. #  undef _STLP_QUEUE_HEADER_ARGS
  207.  
  208. #endif /* _STLP_INTERNAL_QUEUE_H */
  209.  
  210. // Local Variables:
  211. // mode:C++
  212. // End:
  213.