array.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
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_ARRAY__
00032 #define __ETL_ARRAY__
00033 
00034 #include <iterator>
00035 #include <functional>
00036 #include <algorithm>
00037 #include <stddef.h>
00038 
00039 #include "platform.h "
00040 #include "exception.h "
00041 #include "type_traits.h "
00042 #include "parameter_type.h "
00043 #include "static_assert.h"
00044 #include "error_handler.h "
00045 #include "algorithm.h "
00046 
00047 ///\defgroup array array
00048 /// A replacement for std::array if you haven't got C++0x11.
00049 ///\ingroup containers
00050 
00051 namespace etl
00052 {
00053   //***************************************************************************
00054   ///\ingroup array
00055   /// The base class for array exceptions.
00056   //***************************************************************************
00057   class array_exception : public exception
00058   {
00059   public:
00060 
00061     array_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00062       : exception(reason_, file_name_, line_number_)
00063     {
00064     }
00065   };
00066 
00067   //***************************************************************************
00068   ///\ingroup array
00069   /// The out of range exceptions.
00070   //***************************************************************************
00071   class array_out_of_range : public array_exception
00072   {
00073   public:
00074 
00075     array_out_of_range(string_type file_name_, numeric_type line_number_)
00076       : array_exception("array:range", file_name_, line_number_)
00077     {
00078     }
00079   };
00080 
00081   //***************************************************************************
00082   ///\ingroup array
00083   /// A replacement for std::array if you haven't got C++0x11.
00084   //***************************************************************************
00085   template <typename T, const size_t SIZE_>
00086   class array
00087   {
00088   private:
00089 
00090     typedef typename etl::parameter_type<T>::type parameter_t;
00091 
00092   public:
00093 
00094     enum
00095     {
00096       SIZE = SIZE_
00097     };
00098 
00099     typedef T                                     value_type;
00100     typedef std::size_t                           size_type;
00101     typedef std::ptrdiff_t                        difference_type;
00102     typedef T&                                    reference;
00103     typedef const T&                              const_reference;
00104     typedef T*                                    pointer;
00105     typedef const T*                              const_pointer;
00106     typedef T*                                    iterator;
00107     typedef const T*                              const_iterator;
00108     typedef std::reverse_iterator<iterator>       reverse_iterator;
00109     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00110 
00111     //*************************************************************************
00112     // Element access
00113     //*************************************************************************
00114 
00115     //*************************************************************************
00116     /// Returns a reference to the value at index 'i'.
00117     ///\param i The index of the element to access.
00118     //*************************************************************************
00119     reference at(size_t i)
00120     {
00121       ETL_ASSERT(i < SIZE, ETL_ERROR(array_out_of_range));
00122 
00123       return _buffer[i];
00124     }
00125 
00126     //*************************************************************************
00127     /// Returns a const reference to the value at index 'i'.
00128     ///\param i The index of the element to access.
00129     //*************************************************************************
00130     const_reference at(size_t i) const
00131     {
00132       ETL_ASSERT(i < SIZE, ETL_ERROR(array_out_of_range));
00133 
00134       return _buffer[i];
00135     }
00136 
00137     //*************************************************************************
00138     /// [] operator.
00139     /// Returns a reference to the value at index 'i'.
00140     ///\param i The index of the element to access.
00141     //*************************************************************************
00142     reference operator[](size_t i)
00143     {
00144       return _buffer[i];
00145     }
00146 
00147     //*************************************************************************
00148     /// [] operator.
00149     /// Returns a const reference to the value at index 'i'.
00150     ///\param i The index of the element to access.
00151     //*************************************************************************
00152     const_reference operator[](size_t i) const
00153     {
00154       return _buffer[i];
00155     }
00156 
00157     //*************************************************************************
00158     /// Returns a reference to the first element.
00159     //*************************************************************************
00160     reference front()
00161     {
00162       return _buffer[0];
00163     }
00164 
00165     //*************************************************************************
00166     /// Returns a const reference to the first element.
00167     //*************************************************************************
00168     const_reference front() const
00169     {
00170       return _buffer[0];
00171     }
00172 
00173     //*************************************************************************
00174     /// Returns a reference to the last element.
00175     //*************************************************************************
00176     reference back()
00177     {
00178       return _buffer[SIZE - 1];
00179     }
00180 
00181     //*************************************************************************
00182     /// Returns a const reference to the last element.
00183     //*************************************************************************
00184     const_reference back() const
00185     {
00186       return _buffer[SIZE - 1];
00187     }
00188 
00189     //*************************************************************************
00190     /// Returns a pointer to the first element of the internal buffer.
00191     //*************************************************************************
00192     pointer data()
00193     {
00194       return &_buffer[0];
00195     }
00196 
00197     //*************************************************************************
00198     /// Returns a const pointer to the first element of the internal buffer.
00199     //*************************************************************************
00200     const_pointer data() const
00201     {
00202       return &_buffer[0];
00203     }
00204 
00205     //*************************************************************************
00206     // Iterators
00207     //*************************************************************************
00208 
00209     //*************************************************************************
00210     /// Returns an iterator to the beginning of the array.
00211     //*************************************************************************
00212     iterator begin()
00213     {
00214       return &_buffer[0];
00215     }
00216 
00217     //*************************************************************************
00218     /// Returns a const iterator to the beginning of the array.
00219     //*************************************************************************
00220     const_iterator begin() const
00221     {
00222       return &_buffer[0];
00223     }
00224 
00225     //*************************************************************************
00226     /// Returns a const iterator to the beginning of the array.
00227     //*************************************************************************
00228     const_iterator cbegin() const
00229     {
00230       return begin();
00231     }
00232 
00233     //*************************************************************************
00234     /// Returns an iterator to the end of the array.
00235     //*************************************************************************
00236     iterator end()
00237     {
00238       return &_buffer[SIZE];
00239     }
00240 
00241     //*************************************************************************
00242     /// Returns a const iterator to the end of the array.
00243     //*************************************************************************
00244     const_iterator end() const
00245     {
00246       return &_buffer[SIZE];
00247     }
00248 
00249     //*************************************************************************
00250     // Returns a const iterator to the end of the array.
00251     //*************************************************************************
00252     const_iterator cend() const
00253     {
00254       return &_buffer[SIZE];
00255     }
00256 
00257     //*************************************************************************
00258     // Returns an reverse iterator to the reverse beginning of the array.
00259     //*************************************************************************
00260     reverse_iterator rbegin()
00261     {
00262       return reverse_iterator(end());
00263     }
00264 
00265     //*************************************************************************
00266     /// Returns a const reverse iterator to the reverse beginning of the array.
00267     //*************************************************************************
00268     const_reverse_iterator rbegin() const
00269     {
00270       return const_reverse_iterator(end());
00271     }
00272 
00273     //*************************************************************************
00274     /// Returns a const reverse iterator to the reverse beginning of the array.
00275     //*************************************************************************
00276     const_reverse_iterator crbegin() const
00277     {
00278       return const_reverse_iterator(end());
00279     }
00280 
00281     //*************************************************************************
00282     /// Returns a reverse iterator to the end of the array.
00283     //*************************************************************************
00284     reverse_iterator rend()
00285     {
00286       return reverse_iterator(begin());
00287     }
00288 
00289     //*************************************************************************
00290     /// Returns a const reverse iterator to the end of the array.
00291     //*************************************************************************
00292     const_reverse_iterator rend() const
00293     {
00294       return const_reverse_iterator(begin());
00295     }
00296 
00297     //*************************************************************************
00298     /// Returns a const reverse iterator to the end of the array.
00299     //*************************************************************************
00300     const_reverse_iterator crend() const
00301     {
00302       return const_reverse_iterator(begin());
00303     }
00304 
00305     //*************************************************************************
00306     // Capacity
00307     //*************************************************************************
00308 
00309     //*************************************************************************
00310     /// Returns <b>true</b> if the array size is zero.
00311     //*************************************************************************
00312     bool empty() const
00313     {
00314       return (SIZE == 0);
00315     }
00316 
00317     //*************************************************************************
00318     /// Returns the size of the array.
00319     //*************************************************************************
00320     size_t size() const
00321     {
00322       return SIZE;
00323     }
00324 
00325     //*************************************************************************
00326     /// Returns the maximum possible size of the array.
00327     //*************************************************************************
00328     size_t max_size() const
00329     {
00330       return SIZE;
00331     }
00332 
00333     //*************************************************************************
00334     // Operations
00335     //*************************************************************************
00336 
00337     //*************************************************************************
00338     /// Fills the array with the specified value.
00339     ///\param value The value to fill the array with.
00340     //*************************************************************************
00341     void fill(parameter_t value)
00342     {
00343       std::fill(begin(), end(), value);
00344     }
00345 
00346     //*************************************************************************
00347     /// Swaps the contents of this array and another.
00348     ///\param other A reference to the other array.
00349     //*************************************************************************
00350     void swap(array& other)
00351     {
00352       for (size_t i = 0; i < SIZE; ++i)
00353       {
00354         std::swap(_buffer[i], other._buffer[i]);
00355       }
00356     }
00357 
00358     //*************************************************************************
00359     /// Fills the array from the range.
00360     /// If the range is larger than the array then the extra data is ignored.
00361     /// If the range is smaller than the array then the unused array elements are left unmodified.
00362     ///\param first The iterator to the first item in the ramge.
00363     ///\param last  The iterator to one past the final item in the range.
00364     //*************************************************************************
00365     template <typename TIterator>
00366     void assign(TIterator first, const TIterator last)
00367     {
00368       etl::copy(first, last, begin(), end());
00369     }
00370 
00371     //*************************************************************************
00372     /// Fills the array from the range.
00373     /// If the range is larger than the array then the extra data is ignored.
00374     /// If the range is smaller than the array then the unused array elements are initialised with the supplied value.
00375     ///\param first The iterator to the first item in the ramge.
00376     ///\param last  The iterator to one past the final item in the range.
00377     //*************************************************************************
00378     template <typename TIterator>
00379     void assign(TIterator first, const TIterator last, parameter_t value)
00380     {
00381       // Copy from the range.
00382       iterator p = etl::copy(first, last, begin(), end());
00383 
00384       // Default initialise any that are left.
00385       std::fill(p, end(), value);
00386     }
00387 
00388     //*************************************************************************
00389     /// Inserts a value into the array.
00390     ///\param position The index of the position to insert at.
00391     ///\param value    The value to insert.
00392     //*************************************************************************
00393     inline iterator insert_at(size_t position, parameter_t value)
00394     {
00395       return insert(begin() + position, value);
00396     }
00397 
00398     //*************************************************************************
00399     /// Inserts a value into the array.
00400     ///\param position The iterator to the position to insert at.
00401     ///\param value    The value to insert.
00402     //*************************************************************************
00403     iterator insert(const_iterator position, parameter_t value)
00404     {
00405       iterator p = const_cast<iterator>(position);
00406 
00407       std::copy_backward(p, end() - 1, end());
00408       *p = value;
00409 
00410       return p;
00411     }
00412 
00413     //*************************************************************************
00414     /// Insert into the array from the range.
00415     ///\param position The position to insert at.
00416     ///\param first    The iterator to the first item in the range.
00417     ///\param last     The iterator to one past the final item in the range.
00418     //*************************************************************************
00419     template <typename TIterator>
00420     inline iterator insert_at(size_t position, TIterator first, const TIterator last)
00421     {
00422       return insert(begin() + position, first, last);
00423     }
00424 
00425     //*************************************************************************
00426     /// Insert into the array from the range.
00427     ///\param position The position to insert at.
00428     ///\param first    The iterator to the first item in the range.
00429     ///\param last     The iterator to one past the final item in the range.
00430     //*************************************************************************
00431     template <typename TIterator>
00432     iterator insert(const_iterator position, TIterator first, const TIterator last)
00433     {
00434       iterator p = const_cast<iterator>(position);
00435       iterator result(p);
00436 
00437       size_t source_size       = std::distance(first, last);
00438       size_t destination_space = std::distance(position, cend());
00439 
00440       // Do we need to move anything?
00441       if (source_size < destination_space)
00442       {
00443         size_t length = SIZE - (std::distance(begin(), p) + source_size);
00444         std::copy_backward(p, p + length, end());
00445       }
00446 
00447       // Copy from the range.
00448       etl::copy(first, last, p, end());
00449 
00450       return result;
00451     }
00452 
00453     //*************************************************************************
00454     /// Erases a value from the array.
00455     /// After erase, the last value in the array will be unmodified.
00456     ///\param position The index of the position to erase at.
00457     //*************************************************************************
00458     inline iterator erase_at(size_t position)
00459     {
00460       return erase(begin() + position);
00461     }
00462 
00463     //*************************************************************************
00464     /// Erases a value from the array.
00465     /// After erase, the last value in the array will be unmodified.
00466     ///\param position The iterator to the position to erase at.
00467     //*************************************************************************
00468     iterator erase(const_iterator position)
00469     {
00470       iterator p = const_cast<iterator>(position);
00471       std::copy(p + 1, end(), p);
00472 
00473       return p;
00474     }
00475 
00476     //*************************************************************************
00477     /// Erases a range of values from the array.
00478     /// After erase, the last values in the array will be unmodified.
00479     ///\param first The first item to erase.
00480     ///\param last  The one past the last item to erase.
00481     //*************************************************************************
00482     iterator erase_range(size_t first, size_t last)
00483     {
00484       return erase(begin() + first, begin() + last);
00485     }
00486 
00487     //*************************************************************************
00488     /// Erases a range of values from the array.
00489     /// After erase, the last values in the array will be unmodified.
00490     ///\param first The first item to erase.
00491     ///\param last  The one past the last item to erase.
00492     //*************************************************************************
00493     iterator erase(const_iterator first, const_iterator last)
00494     {
00495       iterator p = const_cast<iterator>(first);
00496       std::copy(last, cend(), p);
00497       return p;
00498     }
00499 
00500     //*************************************************************************
00501     /// Erases a value from the array.
00502     ///\param position The index of the position to erase at.
00503     ///\param value    The value to use to overwrite the last element in the array.
00504     //*************************************************************************
00505     inline iterator erase_at(size_t position, parameter_t value)
00506     {
00507       return erase(begin() + position, value);
00508     }
00509 
00510     //*************************************************************************
00511     /// Erases a value from the array.
00512     ///\param position The iterator to the position to erase at.
00513     ///\param value    The value to use to overwrite the last element in the array.
00514     //*************************************************************************
00515     iterator erase(const_iterator position, parameter_t value)
00516     {
00517       iterator p = const_cast<iterator>(position);
00518 
00519       std::copy(p + 1, end(), p);
00520       back() = value;
00521 
00522       return p;
00523     }
00524 
00525     //*************************************************************************
00526     /// Erases a range of values from the array.
00527     ///\param first The first item to erase.
00528     ///\param last  The one past the last item to erase.
00529     ///\param value The value to use to overwrite the last elements in the array.
00530     //*************************************************************************
00531     iterator erase_range(size_t first, size_t last, parameter_t value)
00532     {
00533       return erase(begin() + first, begin() + last, value);
00534     }
00535 
00536     //*************************************************************************
00537     /// Erases a range of values from the array.
00538     ///\param position The iterator to the position to erase at.
00539     ///\param value    The value to use to overwrite the last elements in the array.
00540     //*************************************************************************
00541     iterator erase(const_iterator first, const_iterator last, parameter_t value)
00542     {
00543       iterator p = const_cast<iterator>(first);
00544 
00545       p = std::copy(last, cend(), p);
00546       std::fill(p, end(), value);
00547 
00548       return const_cast<iterator>(first);
00549     }
00550 
00551     /// The array data.
00552     T _buffer[SIZE];
00553   };
00554 
00555   //*************************************************************************
00556   /// Overloaded swap for etl::array<T, SIZE>
00557   ///\param lhs The first array.
00558   ///\param rhs The second array.
00559   //*************************************************************************
00560   template <typename T, const size_t SIZE>
00561   void swap(etl::array<T, SIZE> &lhs, etl::array<T, SIZE> &rhs)
00562   {
00563     lhs.swap(rhs);
00564   }
00565 
00566   //*************************************************************************
00567   /// Equal operator.
00568   ///\param lhs The first array.
00569   ///\param rhs The second array.
00570   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
00571   //*************************************************************************
00572   template <typename T, std::size_t SIZE>
00573   bool operator ==(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00574   {
00575     return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin());
00576   }
00577 
00578   //*************************************************************************
00579   /// Not equal operator.
00580   ///\param lhs The first array.
00581   ///\param rhs The second array.
00582   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
00583   //*************************************************************************
00584   template <typename T, std::size_t SIZE>
00585   bool operator !=(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00586   {
00587     return !(lhs == rhs);
00588   }
00589 
00590   //*************************************************************************
00591   /// Less than operator.
00592   ///\param lhs The first array.
00593   ///\param rhs The second array.
00594   ///\return <b>true</b> if the first array is lexicographically less than the second, otherwise <b>false</b>
00595   //*************************************************************************
00596   template <typename T, std::size_t SIZE>
00597   bool operator <(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00598   {
00599     return std::lexicographical_compare(lhs.cbegin(),
00600                                         lhs.cend(),
00601                                         rhs.cbegin(),
00602                                         rhs.cend());
00603   }
00604 
00605   //*************************************************************************
00606   /// Less than or equal operator.
00607   ///\param lhs The first array.
00608   ///\param rhs The second array.
00609   ///\return <b>true</b> if the first array is lexicographically less than or equal to the second, otherwise <b>false</b>
00610   //*************************************************************************
00611   template <typename T, std::size_t SIZE>
00612   bool operator <=(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00613   {
00614     return !(lhs > rhs);
00615   }
00616 
00617   //*************************************************************************
00618   /// Greater than operator.
00619   ///\param lhs The first array.
00620   ///\param rhs The second array.
00621   ///\return <b>true</b> if the first array is lexicographically greater than the second, otherwise <b>false</b>
00622   template <typename T, std::size_t SIZE>
00623   //*************************************************************************
00624   bool operator >(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00625   {
00626     return (rhs < lhs);
00627   }
00628 
00629   //*************************************************************************
00630   /// Greater than or equal operator.
00631   ///\param lhs The first array.
00632   ///\param rhs The second array.
00633   ///\return <b>true</b> if the first array is lexicographically greater than or equal to the second, otherwise <b>false</b>
00634   //*************************************************************************
00635   template <typename T, std::size_t SIZE>
00636   bool operator >=(const etl::array<T, SIZE>& lhs, const etl::array<T, SIZE>& rhs)
00637   {
00638     return !(lhs < rhs);
00639   }
00640 
00641   //*************************************************************************
00642   /// Gets a reference to an element in the array.
00643   ///\tparam I The index.
00644   ///\tparam T The type.
00645   ///\tparam MAXN The array size.
00646   ///\param a The array.
00647   ///\return A reference to the element
00648   //*************************************************************************
00649   template <std::size_t I, typename T, std::size_t MAXN>
00650   inline T& get(array<T, MAXN>& a)
00651   {
00652     STATIC_ASSERT(I < MAXN, "Index out of bounds");
00653     return a[I];
00654   }
00655 
00656   //*************************************************************************
00657   /// Gets a const reference to an element in the array.
00658   ///\tparam I The index.
00659   ///\tparam T The type.
00660   ///\tparam MAXN The array size.
00661   ///\param a The array.
00662   ///\return A const reference to the element
00663   //*************************************************************************
00664   template <std::size_t I, typename T, std::size_t MAXN>
00665   inline const T& get(const array<T, MAXN>& a)
00666   {
00667     STATIC_ASSERT(I < MAXN, "Index out of bounds");
00668     return a[I];
00669   }
00670 }
00671 
00672 #endif
00673 
00674