stlab.adobe.com Adobe Systems Incorporated
circular_queue.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_CIRCULAR_QUEUE_HPP
10 #define ADOBE_CIRCULAR_QUEUE_HPP
11 
12 /*************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
17 #include <adobe/iterator.hpp>
18 #include <adobe/move.hpp>
19 
20 #include <boost/operators.hpp>
21 
22 #include <cassert>
23 #include <vector>
24 
25 /*************************************************************************************************/
26 
27 namespace adobe {
207 /*************************************************************************************************/
208 
209 #if 1 // REVISIT (fbrereto) : Possible compiler optimization?
210  #define ADOBE_NOTHROW throw()
211 #else
212  #define ADOBE_NOTHROW
213 #endif
214 
215 /*************************************************************************************************/
216 
217 template <typename T> class circular_queue;
218 
219 template <typename T>
220 bool operator == (const circular_queue<T>& x, const circular_queue<T>& y);
221 
222 template <typename T>
224 
225 /*************************************************************************************************/
226 
243 template <typename T>
244 class circular_queue : boost::equality_comparable<circular_queue<T> >
245 {
246 public:
247  typedef T value_type;
248  typedef T* pointer;
249  typedef const T* const_pointer;
250  typedef T& reference;
251  typedef const T& const_reference;
252  typedef std::size_t size_type;
253 
254  circular_queue(std::size_t capacity = 0);
255 
256 #if !defined(ADOBE_NO_DOCUMENTATION)
257  circular_queue(const circular_queue& rhs);
258 
259  circular_queue& operator = (circular_queue rhs);
260 #endif // !defined(ADOBE_NO_DOCUMENTATION)
261 
262  size_type size() const ADOBE_NOTHROW;
263  size_type max_size() const ADOBE_NOTHROW { return container_m.size(); }
264  size_type capacity() const ADOBE_NOTHROW { return container_m.size(); }
265 
266  bool empty() const ADOBE_NOTHROW { return is_empty_m; }
267  bool full() const ADOBE_NOTHROW { return !is_empty_m && begin_m == end_m; }
268 
269  void clear() ADOBE_NOTHROW { begin_m = end_m; is_empty_m = true; }
270 
273 
274  void push_back(T x);
275 
276  void pop_front() ADOBE_NOTHROW;
277 
278  void putback() ADOBE_NOTHROW;
279 
280 #if !defined(ADOBE_NO_DOCUMENTATION)
281 private:
282  friend inline void swap(circular_queue& x, circular_queue& y)
283  {
284  swap(x.container_m, y.container_m);
285  std::swap(x.begin_m, y.begin_m);
286  std::swap(x.end_m, y.end_m);
287  swap(x.is_empty_m, y.is_empty_m);
288  }
289 
290  friend bool operator == <> (const circular_queue& x,
291  const circular_queue& y);
292 
293  typedef typename std::vector<value_type> container_t;
294  typedef typename container_t::iterator iterator;
295  typedef typename container_t::const_iterator const_iterator;
296 
297  /* WARNING (sparent) : Order of members is important to initialization */
298  container_t container_m;
299  iterator begin_m;
300  iterator end_m;
301  bool is_empty_m;
302  /* WARNING (sparent) : Order of members is important to initialization */
303 
304  // Note that these ranges assume non-empty.
305 
306  typedef std::pair<const_iterator, const_iterator> const_range;
307 
308  const_range first_range() const
309  { return const_range(begin_m, begin_m < end_m ? const_iterator(end_m) : boost::end(container_m)); }
310 
311  const_range second_range() const
312  { return const_range(begin_m < end_m ? const_iterator(end_m) : boost::begin(container_m), end_m); }
313 
314 #endif // !defined(ADOBE_NO_DOCUMENTATION)
315 };
316 
317 /*************************************************************************************************/
318 
319 template <typename T>
320 circular_queue<T>::circular_queue(std::size_t capacity) :
321  container_m(capacity),
322  begin_m(boost::begin(container_m)),
323  end_m(boost::begin(container_m)),
324  is_empty_m(true)
325 { }
326 
327 #if !defined(ADOBE_NO_DOCUMENTATION)
328 
329 /*************************************************************************************************/
330 
331 template <typename T>
333  container_m (rhs.capacity()),
334  begin_m (boost::begin(container_m)),
335  end_m (boost::begin(container_m)),
336  is_empty_m (rhs.is_empty_m)
337 {
338  if (is_empty_m) return;
339 
340  end_m = copy(rhs.first_range(), end_m);
341  end_m = copy(rhs.second_range(), end_m);
342 }
343 
344 /*************************************************************************************************/
345 
346 template <typename T>
347 inline circular_queue<T>& circular_queue<T>::operator = (circular_queue rhs)
348 { swap(*this, rhs); return *this; }
349 
350 #endif // !defined(ADOBE_NO_DOCUMENTATION)
351 /*************************************************************************************************/
352 
353 template <typename T>
355 {
356  assert(!empty());
357  return *begin_m;
358 }
359 
360 /*************************************************************************************************/
361 
362 template <typename T>
365 {
366  assert(!empty());
367  return *begin_m;
368 }
369 
370 /*************************************************************************************************/
371 
372 template <typename T>
374 {
375  *end_m = adobe::move(x);
376 
377  bool was_full (full());
378 
379  if (++end_m == boost::end(container_m)) end_m = boost::begin(container_m);
380  if (was_full) begin_m = end_m;
381 
382  is_empty_m = false;
383 }
384 
385 /*************************************************************************************************/
386 
387 template <typename T>
389 {
390  assert(!empty());
391  if (++begin_m == boost::end(container_m))
392  begin_m = boost::begin(container_m);
393  is_empty_m = begin_m == end_m;
394 }
395 
396 /*************************************************************************************************/
397 
398 template <typename T>
400 {
401  assert(!full());
402  if (begin_m == boost::begin(container_m))
403  begin_m = boost::end(container_m);
404  --begin_m;
405  is_empty_m = false;
406 }
407 
408 /*************************************************************************************************/
409 
410 template <typename T>
412 {
413  if (begin_m < end_m) return std::distance(begin_m, end_m);
414 
415  return is_empty_m ? 0 : capacity() - std::distance(end_m, begin_m);
416 }
417 
418 /*************************************************************************************************/
419 
420 template <typename T>
422  const circular_queue<T>& y)
423 {
424 /*
425  REVISIT (sparent) : I'm trying to move the code towards equality of containers to mean "the
426  size is the same and all the parts are the same." By making the segmented iterators part of
427  a public begin, end interface this would simply be a generic. "equal_containers()" function.
428 */
429  typedef typename circular_queue<T>::const_range const_range;
430 
431  if (x.size() != y.size()) return false;
432 
433  const_range sequence1[] = { x.first_range(), x.second_range() };
434  const_range sequence2[] = { y.first_range(), y.second_range() };
435 
436  return equal(make_segmented_range(sequence1),
437  make_segmented_iterator(sequence2));
438 }
439 
440 /*************************************************************************************************/
441 
442 #undef ADOBE_NOTHROW
443 
444 /*************************************************************************************************/
445 
446 } // namespace adobe
447 
448 /*************************************************************************************************/
449 
450 #endif // ADOBE_CIRCULAR_QUEUE_HPP
451 
452 /*************************************************************************************************/
bool swap(circular_queue &x, circular_queue &y)
void putback() ADOBE_NOTHROW
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
Definition: equal.hpp:38
void clear() ADOBE_NOTHROW
circular_queue(std::size_t capacity=0)
void swap(adobe::lex_stream_t &, adobe::lex_stream_t &)
Definition: lex_stream.hpp:68
A queue with a fixed capacity which supports putting back elements. Pushing more elements than there ...
bool operator==(const circular_queue< T > &x, const circular_queue< T > &y)
boost::difference_type< I >::type distance(I &range)
Definition: distance.hpp:29
OutputIterator copy(const InputRange &range, OutputIterator result)
copy implementation
Definition: copy.hpp:43
size_type max_size() const ADOBE_NOTHROW
segmented_iterator< typename boost::range_iterator< R >::type > make_segmented_iterator(R &r)
Definition: iterator.hpp:229
bool empty() const ADOBE_NOTHROW
bool full() const ADOBE_NOTHROW
void swap(circular_queue< T > &, circular_queue< T > &)
#define ADOBE_NOTHROW
size_type size() const ADOBE_NOTHROW
size_type capacity() const ADOBE_NOTHROW
reference front() ADOBE_NOTHROW
void pop_front() ADOBE_NOTHROW
boost::iterator_range< segmented_iterator< typename boost::range_iterator< R >::type > > make_segmented_range(R &r)
Definition: iterator.hpp:219

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google