Documentation Overview Building ASL Documentation Library Wiki Docs Indices Browse Perforce More Info Release Notes Wiki Site Search License Success Stories Contributors Media Download Perforce Depots Support ASL SourceForge Home Mailing Lists Discussion Forums Report Bugs Suggest Features Contribute to ASL RSS Short-text news Full-text news File releases Other Adobe Projects Adobe Air Adobe GIL C++ Benchmarks Adobe Labs Adobe Media Gallery Adobe XMP Tamarin project (Mozilla Foundation) Other Resources Boost RIAForge SGI STL

circular_queue.hpp Go to the documentation of this file. /* Copyright 2005-2007 Adobe Systems Incorporated Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt or a copy at http://stlab.adobe.com/licenses.html) */ /*************************************************************************************************/ #ifndef ADOBE_CIRCULAR_QUEUE_HPP #define ADOBE_CIRCULAR_QUEUE_HPP /*************************************************************************************************/ #include <adobe/config.hpp> #include <adobe/algorithm/equal.hpp> #include <adobe/iterator.hpp> #include <adobe/move.hpp> #include <boost/operators.hpp> #include <cassert> #include <vector> /*************************************************************************************************/ namespace adobe { /*************************************************************************************************/ #if 1 // REVISIT (fbrereto) : Possible compiler optimization? #define ADOBE_NOTHROW throw() #else #define ADOBE_NOTHROW #endif /*************************************************************************************************/ template <typename T> class circular_queue; template <typename T> bool operator == (const circular_queue<T>& x, const circular_queue<T>& y); template <typename T> void swap(circular_queue<T>&, circular_queue<T>&); /*************************************************************************************************/ template <typename T> class circular_queue : boost::equality_comparable<circular_queue<T> > { public: typedef T value_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef std::size_t size_type; circular_queue(std::size_t capacity = 0); #if !defined(ADOBE_NO_DOCUMENTATION) circular_queue(const circular_queue& rhs); circular_queue& operator = (circular_queue rhs); #endif // !defined(ADOBE_NO_DOCUMENTATION) size_type size() const ADOBE_NOTHROW; size_type max_size() const ADOBE_NOTHROW { return container_m.size(); } size_type capacity() const ADOBE_NOTHROW { return container_m.size(); } bool empty() const ADOBE_NOTHROW { return is_empty_m; } bool full() const ADOBE_NOTHROW { return !is_empty_m && begin_m == end_m; } void clear() ADOBE_NOTHROW { begin_m = end_m; is_empty_m = true; } reference front() ADOBE_NOTHROW; const_reference front() const ADOBE_NOTHROW; template <typename U> void push_back(const U& x, typename copy_sink<U, T>::type = 0); template <typename U> void push_back(U x, typename move_sink<U, T>::type = 0); void pop_front() ADOBE_NOTHROW; void putback() ADOBE_NOTHROW; #if !defined(ADOBE_NO_DOCUMENTATION) private: friend inline void swap(circular_queue& x, circular_queue& y) { swap(x.container_m, y.container_m); std::swap(x.begin_m, y.begin_m); std::swap(x.end_m, y.end_m); swap(x.is_empty_m, y.is_empty_m); } friend bool operator == <> (const circular_queue& x, const circular_queue& y); typedef typename std::vector<value_type> container_t; typedef typename container_t::iterator iterator; typedef typename container_t::const_iterator const_iterator; /* WARNING (sparent) : Order of members is important to initialization */ container_t container_m; iterator begin_m; iterator end_m; bool is_empty_m; /* WARNING (sparent) : Order of members is important to initialization */ // Note that these ranges assume non-empty. typedef std::pair<const_iterator, const_iterator> const_range; const_range first_range() const { return const_range(begin_m, begin_m < end_m ? const_iterator(end_m) : boost::end(container_m)); } const_range second_range() const { return const_range(begin_m < end_m ? const_iterator(end_m) : boost::begin(container_m), end_m); } #endif // !defined(ADOBE_NO_DOCUMENTATION) }; /*************************************************************************************************/ template <typename T> circular_queue<T>::circular_queue(std::size_t capacity) : container_m(capacity), begin_m(boost::begin(container_m)), end_m(boost::begin(container_m)), is_empty_m(true) { } #if !defined(ADOBE_NO_DOCUMENTATION) /*************************************************************************************************/ template <typename T> circular_queue<T>::circular_queue(const circular_queue& rhs) : container_m (rhs.capacity()), begin_m (boost::begin(container_m)), end_m (boost::begin(container_m)), is_empty_m (rhs.is_empty_m) { if (is_empty_m) return; end_m = copy(rhs.first_range(), end_m); end_m = copy(rhs.second_range(), end_m); } /*************************************************************************************************/ template <typename T> inline circular_queue<T>& circular_queue<T>::operator = (circular_queue rhs) { swap(*this, rhs); return *this; } #endif // !defined(ADOBE_NO_DOCUMENTATION) /*************************************************************************************************/ template <typename T> typename circular_queue<T>::reference circular_queue<T>::front() ADOBE_NOTHROW { assert(!empty()); return *begin_m; } /*************************************************************************************************/ template <typename T> typename circular_queue<T>::const_reference circular_queue<T>::front() const ADOBE_NOTHROW { assert(!empty()); return *begin_m; } /*************************************************************************************************/ template <typename T> template <typename U> void circular_queue<T>::push_back(const U& x, typename copy_sink<U, T>::type) { *end_m = x; bool was_full (full()); if (++end_m == boost::end(container_m)) end_m = boost::begin(container_m); if (was_full) begin_m = end_m; is_empty_m = false; } /*************************************************************************************************/ template <typename T> template <typename U> void circular_queue<T>::push_back(U x, typename move_sink<U, T>::type) { *end_m = move(x); bool was_full (full()); if (++end_m == boost::end(container_m)) end_m = boost::begin(container_m); if (was_full) begin_m = end_m; is_empty_m = false; } /*************************************************************************************************/ template <typename T> void circular_queue<T>::pop_front() ADOBE_NOTHROW { assert(!empty()); if (++begin_m == boost::end(container_m)) begin_m = boost::begin(container_m); is_empty_m = begin_m == end_m; } /*************************************************************************************************/ template <typename T> void circular_queue<T>::putback() ADOBE_NOTHROW { assert(!full()); if (begin_m == boost::begin(container_m)) begin_m = boost::end(container_m); --begin_m; is_empty_m = false; } /*************************************************************************************************/ template <typename T> typename circular_queue<T>::size_type circular_queue<T>::size() const ADOBE_NOTHROW { if (begin_m < end_m) return std::distance(begin_m, end_m); return is_empty_m ? 0 : capacity() - std::distance(end_m, begin_m); } /*************************************************************************************************/ template <typename T> bool operator == ( const circular_queue<T>& x, const circular_queue<T>& y) { /* REVISIT (sparent) : I'm trying to move the code towards equality of containers to mean "the size is the same and all the parts are the same." By making the segmented iterators part of a public begin, end interface this would simply be a generic. "equal_containers()" function. */ typedef typename circular_queue<T>::const_range const_range; if (x.size() != y.size()) return false; const_range sequence1[] = { x.first_range(), x.second_range() }; const_range sequence2[] = { y.first_range(), y.second_range() }; return equal(make_segmented_range(sequence1), make_segmented_iterator(sequence2)); } /*************************************************************************************************/ #undef ADOBE_NOTHROW /*************************************************************************************************/ } // namespace adobe /*************************************************************************************************/ #endif // ADOBE_CIRCULAR_QUEUE_HPP /*************************************************************************************************/

• Company | 
• Online Privacy Policy | 
• Terms of Use | 
• Contact Us | 
• Accessibility | 
• Report Piracy | 
• Permissions & Trademarks | 
• Product License Agreements | 
• Send Feedback

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