stack.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) 2014 jwellbelove, Mark Kitson
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_STACK__
00032 #define __ETL_STACK__
00033 
00034 #include <stddef.h>
00035 #include <stdint.h>
00036 #include <algorithm>
00037 
00038 #include "platform.h "
00039 #include "container.h "
00040 #include "alignment.h "
00041 #include "array.h "
00042 #include "exception.h "
00043 #include "error_handler.h "
00044 #include "debug_count.h "
00045 #include "type_traits.h "
00046 #include "parameter_type.h "
00047 
00048 #define ETL_FILE "15"
00049 
00050 //*****************************************************************************
00051 ///\defgroup stack stack
00052 /// A Last-in / first-out stack with the capacity defined at compile time,
00053 /// written in the STL style.
00054 ///\ingroup containers
00055 //*****************************************************************************
00056 
00057 namespace etl
00058 {
00059   //***************************************************************************
00060   ///\ingroup stack
00061   /// The base class for stack exceptions.
00062   //***************************************************************************
00063   class stack_exception : public exception
00064   {
00065   public:
00066 
00067     stack_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00068       : exception(reason_, file_name_, line_number_)
00069     {
00070     }
00071   };
00072 
00073   //***************************************************************************
00074   ///\ingroup stack
00075   /// The exception thrown when the stack is full.
00076   //***************************************************************************
00077   class stack_full : public stack_exception
00078   {
00079   public:
00080 
00081     stack_full(string_type file_name_, numeric_type line_number_)
00082       : stack_exception(ETL_ERROR_TEXT("stack:full", ETL_FILE"A"), file_name_, line_number_)
00083     {
00084     }
00085   };
00086 
00087   //***************************************************************************
00088   ///\ingroup stack
00089   /// The exception thrown when the stack is empty.
00090   //***************************************************************************
00091   class stack_empty : public stack_exception
00092   {
00093   public:
00094 
00095     stack_empty(string_type file_name_, numeric_type line_number_)
00096       : stack_exception(ETL_ERROR_TEXT("stack:empty", ETL_FILE"B"), file_name_, line_number_)
00097     {
00098     }
00099   };
00100 
00101   //***************************************************************************
00102   ///\ingroup stack
00103   /// A fixed capacity stack written in the STL style.
00104   /// \warntopg This stack cannot be used for concurrent access from multiple threads.
00105   //***************************************************************************
00106   class stack_base
00107   {
00108   public:
00109 
00110     typedef size_t size_type; ///< The type used for determining the size of stack.
00111 
00112     //*************************************************************************
00113     /// Checks to see if the stack is empty.
00114     /// \return <b>true</b> if the stack is empty, otherwise <b>false</b>
00115     //*************************************************************************
00116     bool empty() const
00117     {
00118       return current_size == 0;
00119     }
00120 
00121     //*************************************************************************
00122     /// Checks to see if the stack is full.
00123     /// \return <b>true</b> if the stack is full, otherwise <b>false</b>
00124     //*************************************************************************
00125     bool full() const
00126     {
00127       return current_size == CAPACITY;
00128     }
00129 
00130     //*************************************************************************
00131     /// Returns the current number of items top the stack.
00132     //*************************************************************************
00133     size_type size() const
00134     {
00135       return current_size;
00136     }
00137 
00138     //*************************************************************************
00139     /// Returns the maximum number of items that can be stacked.
00140     //*************************************************************************
00141     size_type max_size() const
00142     {
00143       return CAPACITY;
00144     }
00145 
00146     //*************************************************************************
00147     /// Returns the remaining capacity.
00148     ///\return The remaining capacity.
00149     //*************************************************************************
00150     size_t available() const
00151     {
00152       return max_size() - size();
00153     }
00154 
00155   protected:
00156 
00157     //*************************************************************************
00158     /// The constructor that is called from derived classes.
00159     //*************************************************************************
00160     stack_base(size_type max_size_)
00161       : top_index(0),
00162         current_size(0),
00163         CAPACITY(max_size_)
00164     {
00165     }
00166 
00167     //*************************************************************************
00168     /// Increments the indexes value to record a stack addition.
00169     //*************************************************************************
00170     void add_in()
00171     {
00172       top_index = current_size++;
00173       ++construct_count;
00174     }
00175 
00176     //*************************************************************************
00177     /// Decrements the indexes value to record a queue deletion.
00178     //*************************************************************************
00179     void del_out()
00180     {
00181       --top_index;
00182       --current_size;
00183       --construct_count;
00184     }
00185 
00186     size_type top_index;              ///< The index of the top of the stack.
00187     size_type current_size;           ///< The number of items in the stack.
00188     const size_type CAPACITY;         ///< The maximum number of items in the stack.
00189     etl::debug_count construct_count; ///< For internal debugging purposes.
00190   };
00191 
00192   //***************************************************************************
00193   ///\ingroup stack
00194   ///\brief This is the base for all stacks that contain a particular type.
00195   ///\details Normally a reference to this type will be taken from a derived stack.
00196   ///\code
00197   /// etl::stack<int, 10> myStack;
00198   /// etl::istack<int>& iStack = myStack;
00199   ///\endcode
00200   /// \warning This stack cannot be used for concurrent access from multiple threads.
00201   /// \tparam T The type of value that the stack holds.
00202   //***************************************************************************
00203   template <typename T>
00204   class istack : public etl::stack_base
00205   {
00206   public:
00207 
00208     typedef T                     value_type;      ///< The type stored in the stack.
00209     typedef T&                    reference;       ///< A reference to the type used in the stack.
00210     typedef const T&              const_reference; ///< A const reference to the type used in the stack.
00211     typedef T*                    pointer;         ///< A pointer to the type used in the stack.
00212     typedef const T*              const_pointer;   ///< A const pointer to the type used in the stack.
00213     typedef stack_base::size_type size_type;       ///< The type used for determining the size of the stack.
00214 
00215   private:
00216 
00217     typedef typename etl::parameter_type<T>::type parameter_t;
00218     typedef typename etl::stack_base              base_t;
00219 
00220   public:
00221 
00222     //*************************************************************************
00223     /// Gets a reference to the value at the top of the stack.<br>
00224     /// \return A reference to the value at the top of the stack.
00225     //*************************************************************************
00226     reference top()
00227     {
00228       return p_buffer[top_index];
00229     }
00230 
00231     //*************************************************************************
00232     /// Adds a value to the stack.
00233     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00234     ///\param value The value to push to the stack.
00235     //*************************************************************************
00236     void push(parameter_t value)
00237     {
00238 #if defined(ETL_CHECK_PUSH_POP)
00239       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00240 #endif
00241       base_t::add_in();
00242       ::new (&p_buffer[top_index]) T(value);
00243     }
00244 
00245     //*************************************************************************
00246     /// Constructs a value in the stack place'.
00247     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00248     ///\param value The value to push to the stack.
00249     //*************************************************************************
00250     template <typename T1>
00251     void emplace(const T1& value1)
00252     {
00253 #if defined(ETL_CHECK_PUSH_POP)
00254       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00255 #endif
00256       base_t::add_in();
00257       ::new (&p_buffer[top_index]) T(value1);
00258     }
00259 
00260     //*************************************************************************
00261     /// Constructs a value in the stack place'.
00262     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00263     ///\param value The value to push to the stack.
00264     //*************************************************************************
00265     template <typename T1, typename T2>
00266     void emplace(const T1& value1, const T2& value2)
00267     {
00268 #if defined(ETL_CHECK_PUSH_POP)
00269       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00270 #endif
00271       base_t::add_in();
00272       ::new (&p_buffer[top_index]) T(value1, value2);
00273     }
00274 
00275     //*************************************************************************
00276     /// Constructs a value in the stack place'.
00277     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00278     ///\param value The value to push to the stack.
00279     //*************************************************************************
00280     template <typename T1, typename T2, typename T3>
00281     void emplace(const T1& value1, const T2& value2, const T3& value3)
00282     {
00283 #if defined(ETL_CHECK_PUSH_POP)
00284       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00285 #endif
00286       base_t::add_in();
00287       ::new (&p_buffer[top_index]) T(value1, value2, value3);
00288     }
00289 
00290     //*************************************************************************
00291     /// Constructs a value in the stack place'.
00292     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00293     ///\param value The value to push to the stack.
00294     //*************************************************************************
00295     template <typename T1, typename T2, typename T3, typename T4>
00296     void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
00297     {
00298 #if defined(ETL_CHECK_PUSH_POP)
00299       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00300 #endif
00301       base_t::add_in();
00302       ::new (&p_buffer[top_index]) T(value1, value2, value3, value4);
00303     }
00304 
00305     //*************************************************************************
00306     /// Allows a possibly more efficient 'push' by moving to the next input value
00307     /// and returning a reference to it.
00308     /// This may eliminate a copy by allowing direct construction in-place.<br>
00309     /// If asserts or exceptions are enabled, throws an etl::stack_full if the stack is already full.
00310     /// \return A reference to the position to 'push' to.
00311     //*************************************************************************
00312     reference push()
00313     {
00314 #if defined(ETL_CHECK_PUSH_POP)
00315       ETL_ASSERT(!full(), ETL_ERROR(stack_full));
00316 #endif
00317       base_t::add_in();
00318 
00319       return p_buffer[top_index];
00320     }
00321 
00322     //*************************************************************************
00323     /// Gets a const reference to the value at the top of the stack.<br>
00324     /// \return A const reference to the value at the top of the stack.
00325     //*************************************************************************
00326     const_reference top() const
00327     {
00328       return p_buffer[top_index];
00329     }
00330 
00331     //*************************************************************************
00332     /// Clears the stack to the empty state.
00333     //*************************************************************************
00334     void clear()
00335     {
00336       while (current_size > 0)
00337       {
00338         p_buffer[top_index].~T();
00339         base_t::del_out();
00340       }
00341     }
00342 
00343     //*************************************************************************
00344     /// Removes the oldest item from the top of the stack.
00345     //*************************************************************************
00346     void pop()
00347     {
00348 #if defined(ETL_CHECK_PUSH_POP)
00349       ETL_ASSERT(!empty(), ETL_ERROR(stack_empty));
00350 #endif
00351       p_buffer[top_index].~T();
00352       base_t::del_out();
00353     }
00354 
00355     //*************************************************************************
00356     /// Removes the oldest item from the top of the stack and puts it in the destination.
00357     //*************************************************************************
00358     void pop_into(reference destination)
00359     {
00360       destination = top();
00361       pop();
00362     }
00363 
00364     //*************************************************************************
00365     /// Removes the oldest item from the top of the stack and pushes it to the
00366     /// destination container.
00367     /// NOTE: The destination must support a push(T) member function.
00368     //*************************************************************************
00369     template <typename TContainer>
00370     void pop_into(TContainer& destination)
00371     {
00372       destination.push(top());
00373       pop();
00374     }
00375 
00376     //*************************************************************************
00377     /// Reverses the stack.
00378     //*************************************************************************
00379     void reverse()
00380     {
00381       std::reverse(p_buffer, p_buffer + current_size);
00382     }
00383 
00384     //*************************************************************************
00385     /// Assignment operator.
00386     //*************************************************************************
00387     istack& operator = (const istack& rhs)
00388     {
00389       if (&rhs != this)
00390       {
00391         clear();
00392         clone(rhs);
00393       }
00394 
00395       return *this;
00396     }
00397 
00398   protected:
00399 
00400     //*************************************************************************
00401     /// Make this a clone of the supplied stack
00402     //*************************************************************************
00403     void clone(const istack& other)
00404     {
00405       size_t index = 0;
00406 
00407       for (size_t i = 0; i < other.size(); ++i)
00408       {
00409         push(other.p_buffer[index++]);
00410       }
00411     }
00412 
00413     //*************************************************************************
00414     /// The constructor that is called from derived classes.
00415     //*************************************************************************
00416     istack(T* p_buffer_, size_type max_size_)
00417       : stack_base(max_size_),
00418         p_buffer(p_buffer_)
00419     {
00420     }
00421 
00422   private:
00423 
00424     // Disable copy construction.
00425     istack(const istack&);
00426 
00427     T* p_buffer; ///< The internal buffer.
00428   };
00429 
00430   //***************************************************************************
00431   ///\ingroup stack
00432   /// A fixed capacity stack.
00433   /// This stack does not suppo7rt concurrent access by different threads.
00434   /// \tparam T        The type this stack should support.
00435   /// \tparam MAX_SIZE The maximum capacity of the stack.
00436   //***************************************************************************
00437   template <typename T, const size_t SIZE>
00438   class stack : public etl::istack<T>
00439   {
00440   public:
00441 
00442     static const size_t MAX_SIZE = SIZE;
00443 
00444     //*************************************************************************
00445     /// Default constructor.
00446     //*************************************************************************
00447     stack()
00448       : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
00449     {
00450     }
00451 
00452     //*************************************************************************
00453     /// Copy constructor
00454     //*************************************************************************
00455     stack(const stack& rhs)
00456       : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
00457     {
00458       etl::istack<T>::clone(rhs);
00459     }
00460 
00461     //*************************************************************************
00462     /// Destructor.
00463     //*************************************************************************
00464     ~stack()
00465     {
00466       etl::istack<T>::clear();
00467     }
00468 
00469     //*************************************************************************
00470     /// Assignment operator.
00471     //*************************************************************************
00472     stack& operator = (const stack& rhs)
00473     {
00474       if (&rhs != this)
00475       {
00476         etl::istack<T>::clone(rhs);
00477       }
00478 
00479       return *this;
00480     }
00481 
00482   private:
00483 
00484     /// The unintitialised buffer of T used in the stack.
00485     typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type buffer[SIZE];
00486   };
00487 }
00488 
00489 #undef ETL_FILE
00490 
00491 #endif
00492