1 // queue standard header
2 #pragma once
3 #ifndef _QUEUE_
4 #define _QUEUE_
5 #ifndef RC_INVOKED
6 #include <algorithm>
7 #include <deque>
8 #include <functional>
9 #include <vector>
10
11 #ifdef _MSC_VER
12  #pragma pack(push,_CRT_PACKING)
13  #pragma warning(push,3)
14 #endif  /* _MSC_VER */
15 _STD_BEGIN
16
17         // TEMPLATE CLASS queue
18 template<class _Ty,
19     class _Container = deque<_Ty> >
20     class queue
21     {    // FIFO queue implemented with a container
22 public:
23     typedef _Container container_type;
24     typedef typename _Container::value_type value_type;
25     typedef typename _Container::size_type size_type;
26     typedef typename _Container::reference reference;
27     typedef typename _Container::const_reference const_reference;
28
29     queue()
30         : c()
31         {    // construct with empty container
32         }
33
34     explicit queue(const _Container& _Cont)
35         : c(_Cont)
36         {    // construct by copying specified container
37         }
38
39     bool empty() const
40         {    // test if queue is empty
41         return (c.empty());
42         }
43
44     size_type size() const
45         {    // return length of queue
46         return (c.size());
47         }
48
49     reference front()
50         {    // return first element of mutable queue
51         return (c.front());
52         }
53
54     const_reference front() const
55         {    // return first element of nonmutable queue
56         return (c.front());
57         }
58
59     reference back()
60         {    // return last element of mutable queue
61         return (c.back());
62         }
63
64     const_reference back() const
65         {    // return last element of nonmutable queue
66         return (c.back());
67         }
68
69     void push(const value_type& _Val)
70         {    // insert element at beginning
71         c.push_back(_Val);
72         }
73
74     void pop()
75         {    // erase element at end
76         c.pop_front();
77         }
78
79     const _Container& _Get_container() const
80         {    // get reference to container
81         return (c);
82         }
83
84 protected:
85     _Container c;    // the underlying container
86     };
87
88         // queue TEMPLATE FUNCTIONS
89 template<class _Ty,
90     class _Container> inline
91     bool operator==(const queue<_Ty, _Container>& _Left,
92         const queue<_Ty, _Container>& _Right)
93     {    // test for queue equality
94     return (_Left._Get_container() == _Right._Get_container());
95     }
96
97 template<class _Ty,
98     class _Container> inline
99     bool operator!=(const queue<_Ty, _Container>& _Left,
100         const queue<_Ty, _Container>& _Right)
101     {    // test for queue inequality
102     return (!(_Left == _Right));
103     }
104
105 template<class _Ty,
106     class _Container> inline
107     bool operator<(const queue<_Ty, _Container>& _Left,
108         const queue<_Ty, _Container>& _Right)
109     {    // test if _Left < _Right for queues
110     return (_Left._Get_container() < _Right._Get_container());
111     }
112
113 template<class _Ty,
Lines 114 ... 123 are skipped.
124         const queue<_Ty, _Container>& _Right)
125     {    // test if _Left <= _Right for queues
126     return (!(_Right < _Left));
127     }
128
129 template<class _Ty,
130     class _Container> inline
131     bool operator>=(const queue<_Ty, _Container>& _Left,
132         const queue<_Ty, _Container>& _Right)
133     {    // test if _Left >= _Right for queues
134     return (!(_Left < _Right));
135     }
136
137         // TEMPLATE CLASS priority_queue
138 template<class _Ty,
139     class _Container = vector<_Ty>,
140     class _Pr = less<typename _Container::value_type> >
141     class priority_queue
142     {    // priority queue implemented with a _Container
143 public:
144     typedef _Container container_type;
145     typedef typename _Container::value_type value_type;
146     typedef typename _Container::size_type size_type;
147     typedef typename _Container::reference reference;
148     typedef typename _Container::const_reference const_reference;
149
150     priority_queue()
151         : c(), comp()
152         {    // construct with empty container, default comparator
153         }
154
155     explicit priority_queue(const _Pr& _Pred)
156         : c(), comp(_Pred)
157         {    // construct with empty container, specified comparator
158         }
159
160     priority_queue(const _Pr& _Pred, const _Container& _Cont)
161         : c(_Cont), comp(_Pred)
162         {    // construct by copying specified container, comparator
163         make_heap(c.begin(), c.end(), comp);
164         }
165
166     template<class _Iter>
167         priority_queue(_Iter _First, _Iter _Last)
168         : c(_First, _Last), comp()
169         {    // construct by copying [_First, _Last), default comparator
170         make_heap(c.begin(), c.end(), comp);
171         }
172
173     template<class _Iter>
174         priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred)
175         : c(_First, _Last), comp(_Pred)
176         {    // construct by copying [_First, _Last), specified comparator
177         make_heap(c.begin(), c.end(), comp);
178         }
179
180     template<class _Iter>
181         priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred,
182             const _Container& _Cont)
183         : c(_Cont), comp(_Pred)
184         {    // construct by copying [_First, _Last), container, and comparator
185         c.insert(c.end(), _First, _Last);
186         make_heap(c.begin(), c.end(), comp);
187         }
188
189     bool empty() const
190         {    // test if queue is empty
191         return (c.empty());
192         }
193
194     size_type size() const
195         {    // return length of queue
196         return (c.size());
197         }
198
199     const_reference top() const
200         {    // return highest-priority element
201         return (c.front());
202         }
203
204     reference top()
205         {    // return mutable highest-priority element (retained)
206         return (c.front());
207         }
208
209     void push(const value_type& _Pred)
210         {    // insert value in priority order
211         c.push_back(_Pred);
212         push_heap(c.begin(), c.end(), comp);
213         }
214
215     void pop()
216         {    // erase highest-priority element
217         pop_heap(c.begin(), c.end(), comp);
218         c.pop_back();
219         }
220
221 protected:
222     _Container c;    // the underlying container
223     _Pr comp;    // the comparator functor
224     };
225 _STD_END
226 #ifdef _MSC_VER
227  #pragma warning(pop)
228  #pragma pack(pop)
229 #endif  /* _MSC_VER */
230
231 #endif /* RC_INVOKED */
232 #endif /* _QUEUE_ */
233
234 /*
235  * Copyright (c) 1992-2007 by P.J. Plauger.  ALL RIGHTS RESERVED.
236  * Consult your license regarding permissions and restrictions.
237  */
238
239 /*
240  * This file is derived from software bearing the following
241  * restrictions:
242  *
243  * Copyright (c) 1994
244  * Hewlett-Packard Company
245  *
246  * Permission to use, copy, modify, distribute and sell this
247  * software and its documentation for any purpose is hereby
248  * granted without fee, provided that the above copyright notice
249  * appear in all copies and that both that copyright notice and
250  * this permission notice appear in supporting documentation.
251  * Hewlett-Packard Company makes no representations about the
252  * suitability of this software for any purpose. It is provided
253  * "as is" without express or implied warranty.
254  V5.03:0009 */
255