1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation.  Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose.  It is provided "as is" without express or implied warranty.
13 *
14 *
15 * Copyright (c) 1996,1997
16 * Silicon Graphics Computer Systems, Inc.
17 *
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation.  Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose.  It is provided "as is" without express or implied warranty.
25 */
26
27/* NOTE: This is an internal header file, included by other STL headers.
28 *   You should not attempt to use it directly.
29 */
30
31#ifndef __SGI_STL_INTERNAL_QUEUE_H
32#define __SGI_STL_INTERNAL_QUEUE_H
33
34__STL_BEGIN_NAMESPACE
35
36#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
37template <class _Tp, class _Sequence = deque<_Tp> >
38#else
39template <class _Tp, class _Sequence>
40#endif
41class queue {
42  friend bool operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);
43  friend bool operator< __STL_NULL_TMPL_ARGS (const queue&, const queue&);
44public:
45  typedef typename _Sequence::value_type      value_type;
46  typedef typename _Sequence::size_type       size_type;
47  typedef          _Sequence                  container_type;
48
49  typedef typename _Sequence::reference       reference;
50  typedef typename _Sequence::const_reference const_reference;
51protected:
52  _Sequence c;
53public:
54  queue() : c() {}
55  explicit queue(const _Sequence& __c) : c(__c) {}
56
57  bool empty() const { return c.empty(); }
58  size_type size() const { return c.size(); }
59  reference front() { return c.front(); }
60  const_reference front() const { return c.front(); }
61  reference back() { return c.back(); }
62  const_reference back() const { return c.back(); }
63  void push(const value_type& __x) { c.push_back(__x); }
64  void pop() { c.pop_front(); }
65};
66
67template <class _Tp, class _Sequence>
68bool
69operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
70{
71  return __x.c == __y.c;
72}
73
74template <class _Tp, class _Sequence>
75bool
76operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
77{
78  return __x.c < __y.c;
79}
80
81#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
82
83template <class _Tp, class _Sequence>
84bool
85operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
86{
87  return !(__x == __y);
88}
89
90template <class _Tp, class _Sequence>
91bool
92operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
93{
94  return __y < __x;
95}
96
97template <class _Tp, class _Sequence>
98bool
99operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
100{
101  return !(__y < __x);
102}
103
104template <class _Tp, class _Sequence>
105bool
106operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
107{
108  return !(__x < __y);
109}
110
111#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
112
113#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
114template <class _Tp, class _Sequence = vector<_Tp>,
115          class _Compare = less<typename _Sequence::value_type> >
116#else
117template <class _Tp, class _Sequence, class _Compare>
118#endif
119class  priority_queue {
120public:
121  typedef typename _Sequence::value_type      value_type;
122  typedef typename _Sequence::size_type       size_type;
123  typedef          _Sequence                  container_type;
124
125  typedef typename _Sequence::reference       reference;
126  typedef typename _Sequence::const_reference const_reference;
127protected:
128  _Sequence c;
129  _Compare comp;
130public:
131  priority_queue() : c() {}
132  explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
133  priority_queue(const _Compare& __x, const _Sequence& __s)
134    : c(__s), comp(__x)
135    { make_heap(c.begin(), c.end(), comp); }
136
137#ifdef __STL_MEMBER_TEMPLATES
138  template <class _InputIterator>
139  priority_queue(_InputIterator __first, _InputIterator __last)
140    : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
141
142  template <class _InputIterator>
143  priority_queue(_InputIterator __first,
144                 _InputIterator __last, const _Compare& __x)
145    : c(__first, __last), comp(__x)
146    { make_heap(c.begin(), c.end(), comp); }
147
148  template <class _InputIterator>
149  priority_queue(_InputIterator __first, _InputIterator __last,
150                 const _Compare& __x, const _Sequence& __s)
151  : c(__s), comp(__x)
152  {
153    c.insert(c.end(), __first, __last);
154    make_heap(c.begin(), c.end(), comp);
155  }
156
157#else /* __STL_MEMBER_TEMPLATES */
158  priority_queue(const value_type* __first, const value_type* __last)
159    : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
160
161  priority_queue(const value_type* __first, const value_type* __last,
162                 const _Compare& __x)
163    : c(__first, __last), comp(__x)
164    { make_heap(c.begin(), c.end(), comp); }
165
166  priority_queue(const value_type* __first, const value_type* __last,
167                 const _Compare& __x, const _Sequence& __c)
168    : c(__c), comp(__x)
169  {
170    c.insert(c.end(), __first, __last);
171    make_heap(c.begin(), c.end(), comp);
172  }
173#endif /* __STL_MEMBER_TEMPLATES */
174
175  bool empty() const { return c.empty(); }
176  size_type size() const { return c.size(); }
177  const_reference top() const { return c.front(); }
178  void push(const value_type& __x) {
179    __STL_TRY {
180      c.push_back(__x);
181      push_heap(c.begin(), c.end(), comp);
182    }
183    __STL_UNWIND(c.clear());
184  }
185  void pop() {
186    __STL_TRY {
187      pop_heap(c.begin(), c.end(), comp);
188      c.pop_back();
189    }
190    __STL_UNWIND(c.clear());
191  }
192};
193
194// no equality is provided
195
196__STL_END_NAMESPACE
197
198#endif /* __SGI_STL_INTERNAL_QUEUE_H */
199
200// Local Variables:
201// mode:C++
202// End:
203