priority_queue.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2015 jwellbelove, rlindeman
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_PRIORITY_QUEUE__
00032 #define __ETL_PRIORITY_QUEUE__
00033 
00034 #include <stddef.h>
00035 #include <functional>
00036 #include <algorithm>
00037 
00038 #include "platform.h "
00039 #include "container.h "
00040 #include "vector.h "
00041 #include "type_traits.h "
00042 #include "parameter_type.h "
00043 #include "error_handler.h "
00044 #include "exception.h "
00045 
00046 #undef ETL_FILE
00047 #define ETL_FILE "12"
00048 
00049 //*****************************************************************************
00050 ///\defgroup queue queue
00051 /// A priority queue with the capacity defined at compile time,
00052 /// written in the STL style.
00053 ///\ingroup containers
00054 //*****************************************************************************
00055 
00056 namespace etl
00057 {
00058   //***************************************************************************
00059   /// The base class for priority_queue exceptions.
00060   ///\ingroup queue
00061   //***************************************************************************
00062   class priority_queue_exception : public exception
00063   {
00064   public:
00065 
00066     priority_queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00067       : exception(reason_, file_name_, line_number_)
00068     {
00069     }
00070   };
00071 
00072   //***************************************************************************
00073   /// The exception thrown when the queue is full.
00074   ///\ingroup queue
00075   //***************************************************************************
00076   class priority_queue_full : public etl::priority_queue_exception
00077   {
00078   public:
00079 
00080     priority_queue_full(string_type file_name_, numeric_type line_number_)
00081       : priority_queue_exception(ETL_ERROR_TEXT("priority_queue:full", ETL_FILE"A"), file_name_, line_number_)
00082     {
00083     }
00084   };
00085 
00086   //***************************************************************************
00087   /// The priority queue iterator exception on reversed iterators
00088   ///\ingroup queue
00089   //***************************************************************************
00090   class priority_queue_iterator : public etl::priority_queue_exception
00091   {
00092   public:
00093 
00094     priority_queue_iterator(string_type file_name_, numeric_type line_number_)
00095       : priority_queue_exception(ETL_ERROR_TEXT("priority_queue:iterator", ETL_FILE"B"), file_name_, line_number_)
00096     {
00097     }
00098   };
00099 
00100   //***************************************************************************
00101   ///\ingroup queue
00102   ///\brief This is the base for all priority queues that contain a particular type.
00103   ///\details Normally a reference to this type will be taken from a derived queue.
00104   /// The TContainer specified must provide the front, push_back, pop_back, and
00105   /// assign methods to work correctly with priority_queue.
00106   ///\code
00107   /// etl::priority_queue<int, 10> myPriorityQueue;
00108   /// etl::ipriority_queue<int>& iQueue = myPriorityQueue;
00109   ///\endcode
00110   /// \warning This priority queue cannot be used for concurrent access from
00111   /// multiple threads.
00112   /// \tparam T The type of value that the queue holds.
00113   /// \tparam TContainer to hold the T queue values
00114   /// \tparam TCompare to use in comparing T values
00115   //***************************************************************************
00116   template <typename T, typename TContainer, typename TCompare>
00117   class ipriority_queue
00118   {
00119   public:
00120 
00121     typedef T                     value_type;         ///< The type stored in the queue.
00122     typedef TContainer            container_type;     ///< The container type used for priority queue.
00123     typedef TCompare              compare_type;       ///< The comparison type.
00124     typedef T&                    reference;          ///< A reference to the type used in the queue.
00125     typedef const T&              const_reference;    ///< A const reference to the type used in the queue.
00126     typedef typename TContainer::size_type size_type; ///< The type used for determining the size of the queue.
00127     typedef typename std::iterator_traits<typename TContainer::iterator>::difference_type difference_type;
00128 
00129   private:
00130 
00131     typedef typename etl::parameter_type<T>::type parameter_t;
00132 
00133   public:
00134 
00135     //*************************************************************************
00136     /// Gets a reference to the highest priority value in the priority queue.<br>
00137     /// \return A reference to the highest priority value in the priority queue.
00138     //*************************************************************************
00139     reference top()
00140     {
00141       return container.front();
00142     }
00143 
00144     //*************************************************************************
00145     /// Gets a const reference to the highest priority value in the priority queue.<br>
00146     /// \return A const reference to the highest priority value in the priority queue.
00147     //*************************************************************************
00148     const_reference top() const
00149     {
00150       return container.front();
00151     }
00152 
00153     //*************************************************************************
00154     /// Adds a value to the queue.
00155     /// If asserts or exceptions are enabled, throws an etl::priority_queue_full
00156     /// is the priority queue is already full.
00157     ///\param value The value to push to the queue.
00158     //*************************************************************************
00159     void push(parameter_t value)
00160     {
00161       ETL_ASSERT(!full(), ETL_ERROR(etl::priority_queue_full));
00162 
00163       // Put element at end
00164       container.push_back(value);
00165       // Make elements in container into heap
00166       std::push_heap(container.begin(), container.end(), TCompare());
00167     }
00168 
00169     //*************************************************************************
00170     /// Emplaces a value to the queue.
00171     /// If asserts or exceptions are enabled, throws an etl::priority_queue_full
00172     /// is the priority queue is already full.
00173     ///\param value The value to push to the queue.
00174     //*************************************************************************
00175     template <typename T1>
00176     void emplace(const T1& value1)
00177     {
00178       ETL_ASSERT(!full(), ETL_ERROR(etl::priority_queue_full));
00179 
00180       // Put element at end
00181       container.emplace_back(value1);
00182       // Make elements in container into heap
00183       std::push_heap(container.begin(), container.end(), TCompare());
00184     }
00185 
00186     //*************************************************************************
00187     /// Emplaces a value to the queue.
00188     /// If asserts or exceptions are enabled, throws an etl::priority_queue_full
00189     /// is the priority queue is already full.
00190     ///\param value The value to push to the queue.
00191     //*************************************************************************
00192     template <typename T1, typename T2>
00193     void emplace(const T1& value1, const T2& value2)
00194     {
00195       ETL_ASSERT(!full(), ETL_ERROR(etl::priority_queue_full));
00196 
00197       // Put element at end
00198       container.emplace_back(value1, value2);
00199       // Make elements in container into heap
00200       std::push_heap(container.begin(), container.end(), TCompare());
00201     }
00202 
00203     //*************************************************************************
00204     /// Emplaces a value to the queue.
00205     /// If asserts or exceptions are enabled, throws an etl::priority_queue_full
00206     /// is the priority queue is already full.
00207     ///\param value The value to push to the queue.
00208     //*************************************************************************
00209     template <typename T1, typename T2, typename T3>
00210     void emplace(const T1& value1, const T2& value2, const T3& value3)
00211     {
00212       ETL_ASSERT(!full(), ETL_ERROR(etl::priority_queue_full));
00213 
00214       // Put element at end
00215       container.emplace_back(value1, value2, value3);
00216       // Make elements in container into heap
00217       std::push_heap(container.begin(), container.end(), TCompare());
00218     }
00219 
00220     //*************************************************************************
00221     /// Emplaces a value to the queue.
00222     /// If asserts or exceptions are enabled, throws an etl::priority_queue_full
00223     /// is the priority queue is already full.
00224     ///\param value The value to push to the queue.
00225     //*************************************************************************
00226     template <typename T1, typename T2, typename T3, typename T4>
00227     void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
00228     {
00229       ETL_ASSERT(!full(), ETL_ERROR(etl::priority_queue_full));
00230 
00231       // Put element at end
00232       container.emplace_back(value1, value2, value3, value4);
00233       // Make elements in container into heap
00234       std::push_heap(container.begin(), container.end(), TCompare());
00235     }
00236 
00237     //*************************************************************************
00238     /// Assigns values to the priority queue.
00239     /// If asserts or exceptions are enabled, emits priority_queue_full if
00240     /// priority queue does not have enough free space.
00241     /// If asserts or exceptions are enabled, emits priority_iterator if the
00242     /// iterators are reversed.
00243     ///\param first The iterator to the first element.
00244     ///\param last  The iterator to the last element + 1.
00245     //*************************************************************************
00246     template <typename TIterator>
00247     void assign(TIterator first, TIterator last)
00248     {
00249 #if defined(ETL_DEBUG)
00250       difference_type d = std::distance(first, last);
00251       ETL_ASSERT(d >= 0, ETL_ERROR(etl::priority_queue_iterator));
00252       ETL_ASSERT(static_cast<size_t>(d) <= max_size(), ETL_ERROR(etl::priority_queue_full));
00253 #endif
00254 
00255       clear();
00256       container.assign(first, last);
00257       std::make_heap(container.begin(), container.end(), TCompare());
00258     }
00259 
00260     //*************************************************************************
00261     /// Removes the oldest value from the back of the priority queue.
00262     /// Does nothing if the priority queue is already empty.
00263     //*************************************************************************
00264     void pop()
00265     {
00266       // Move largest element to end
00267       std::pop_heap(container.begin(), container.end(), TCompare());
00268       // Actually remove largest element at end
00269       container.pop_back();
00270     }
00271 
00272     //*************************************************************************
00273     /// Gets the highest priority value in the priority queue
00274     /// and assigns it to destination and removes it from the queue.
00275     //*************************************************************************
00276     void pop_into(reference destination)
00277     {
00278       destination = top();
00279       pop();
00280     }
00281 
00282     //*************************************************************************
00283     /// Returns the current number of items in the priority queue.
00284     //*************************************************************************
00285     size_type size() const
00286     {
00287       return container.size();
00288     }
00289 
00290     //*************************************************************************
00291     /// Returns the maximum number of items that can be queued.
00292     //*************************************************************************
00293     size_type max_size() const
00294     {
00295       return container.max_size();
00296     }
00297 
00298     //*************************************************************************
00299     /// Checks to see if the priority queue is empty.
00300     /// \return <b>true</b> if the queue is empty, otherwise <b>false</b>
00301     //*************************************************************************
00302     bool empty() const
00303     {
00304       return container.empty();
00305     }
00306 
00307     //*************************************************************************
00308     /// Checks to see if the priority queue is full.
00309     /// \return <b>true</b> if the priority queue is full, otherwise <b>false</b>
00310     //*************************************************************************
00311     bool full() const
00312     {
00313       return container.size() == container.max_size();
00314     }
00315 
00316     //*************************************************************************
00317     /// Returns the remaining capacity.
00318     ///\return The remaining capacity.
00319     //*************************************************************************
00320     size_t available() const
00321     {
00322       return container.max_size() - container.size();
00323     }
00324 
00325     //*************************************************************************
00326     /// Clears the queue to the empty state.
00327     //*************************************************************************
00328     void clear()
00329     {
00330       container.clear();
00331     }
00332 
00333   protected:
00334 
00335     //*************************************************************************
00336     /// Make this a clone of the supplied priority queue
00337     //*************************************************************************
00338     void clone(const ipriority_queue& other)
00339     {
00340       assign(other.container.cbegin(), other.container.cend());
00341     }
00342 
00343     //*************************************************************************
00344     /// The constructor that is called from derived classes.
00345     //*************************************************************************
00346     ipriority_queue()
00347     {
00348     }
00349 
00350   private:
00351 
00352     // Disable copy construction.
00353     ipriority_queue(const ipriority_queue&);
00354 
00355     /// The container specified at instantiation of the priority_queue
00356     TContainer container;
00357   };
00358 
00359   //***************************************************************************
00360   ///\ingroup priority_queue
00361   /// A fixed capacity priority queue.
00362   /// This queue does not support concurrent access by different threads.
00363   /// \tparam T    The type this queue should support.
00364   /// \tparam SIZE The maximum capacity of the queue.
00365   //***************************************************************************
00366   template <typename T, const size_t SIZE, typename TContainer = etl::vector<T, SIZE>, typename TCompare = std::less<typename TContainer::value_type> >
00367   class priority_queue : public etl::ipriority_queue<T, TContainer, TCompare>
00368   {
00369   public:
00370 
00371     static const size_t MAX_SIZE = SIZE;
00372 
00373     //*************************************************************************
00374     /// Default constructor.
00375     //*************************************************************************
00376     priority_queue()
00377       : etl::ipriority_queue<T, TContainer, TCompare>()
00378     {
00379     }
00380 
00381     //*************************************************************************
00382     /// Copy constructor
00383     //*************************************************************************
00384     priority_queue(const priority_queue& rhs)
00385       : etl::ipriority_queue<T, TContainer, TCompare>()
00386     {
00387       etl::ipriority_queue<T, TContainer, TCompare>::clone(rhs);
00388     }
00389 
00390     //*************************************************************************
00391     /// Constructor, from an iterator range.
00392     ///\tparam TIterator The iterator type.
00393     ///\param first The iterator to the first element.
00394     ///\param last  The iterator to the last element + 1.
00395     //*************************************************************************
00396     template <typename TIterator>
00397     priority_queue(TIterator first, TIterator last)
00398       : etl::ipriority_queue<T, TContainer, TCompare>()
00399     {
00400       etl::ipriority_queue<T, TContainer, TCompare>::assign(first, last);
00401     }
00402 
00403     //*************************************************************************
00404     /// Destructor.
00405     //*************************************************************************
00406     ~priority_queue()
00407     {
00408       etl::ipriority_queue<T, TContainer, TCompare>::clear();
00409     }
00410 
00411     //*************************************************************************
00412     /// Assignment operator.
00413     //*************************************************************************
00414     priority_queue& operator = (const priority_queue& rhs)
00415     {
00416       if (&rhs != this)
00417       {
00418         etl::ipriority_queue<T, TContainer, TCompare>::clone(rhs);
00419       }
00420 
00421       return *this;
00422     }
00423   };
00424 }
00425 
00426 #undef ETL_FILE
00427 
00428 #endif
00429