DynamicArrayTemplateImpl.hpp

   1 /*
   2  * Implementation of a dynamically sizing Array Template including STL Iterator
   3  * Copyright (c) 2014 TJ <hacker@iam.tj>
   4  *
   5  *    This program is free software: you can redistribute it and/or modify
   6  *    it under the terms of the GNU General Public License as published by
   7  *    the Free Software Foundation, either version 3 of the License.
   8  *
   9  *    This program is distributed in the hope that it will be useful,
  10  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *    GNU General Public License for more details.
  13  *
  14  *   You should have received a copy of the GNU General Public License
  15  *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * see ./COPYRIGHT or http://www.gnu.org/licenses/gpl-3.0.html
  18  */
  19
  20 #ifndef ARRAY_TEMPLATE_IMPL
  21 #define ARRAY_TEMPLATE_IMPL
  22
  23 #include <cassert>
  24
  25 /*
  26  * Template declarations *and* definitions do not generate any code until an
  27  * object of a concrete type is instantiated. Therefore declaration
  28  * and definition should be #include-d by source files (.cpp) that instantiate
  29  * the concrete type object; the template should *not* compiled as a separate unit.
  30  */
  31
  32 namespace tj
  33 {
  34   /* allow index type to be easily changed (allows optimum choice of type based on maximum
  35    * expected number of elements to be stored)
  36    *
  37    * using unsigned (int) since the index can never be less than zero
  38    */
  39   typedef unsigned size_type;
  40
  41   template <typename T>
  42   class ArrayTemplateImpl
  43   {
  44     /* default access specifier for 'class' is "private" so no need to explicitly use it
  45      * (for 'struct' the default is "public" since 'struct' originally extended the C language 'struct')
  46      */
  47     T* elements_ptr;    // pointer to a block of contiguous memory containing some number of T objects
  48     size_type size;      // number of elements in the array
  49     size_type next_free; // index of first unallocated element (in other words, the number of allocated elements)
  50
  51     protected:
  52
  53     // these methods aren't available publicly but can be accessed by sub-classes
  54
  55     size_type get_next_free() { return next_free; }
  56
  57     // use a default parameter value (can be over-ridden by caller's own value)
  58     size_type grow(size_type new_elements = 10)
  59     {
  60       if (new_elements > 0)
  61       {
  62         size += new_elements;
  63         T* enlarged[size];
  64         for (size_type i = 0; i < size; ++i)
  65           if (i < next_free)
  66             enlarged[i] = elements_ptr[i];
  67           else
  68             break;
  69
  70         delete[] elements_ptr;
  71         elements_ptr = enlarged;
  72       }
  73       return size;
  74     }
  75
  76     // reduces the size of the array so all elements are in use
  77     size_type shrink()
  78     {
  79       if (next_free > 0 && next_free < size - 1)
  80       {
  81         T* shrunk[next_free];
  82         for (size_type i = 0; i < next_free; ++i)
  83           shrunk[i] = elements_ptr[i];
  84         delete[] elements_ptr;
  85         elements_ptr = shrunk;
  86         size = next_free;
  87       }
  88       return size;
  89     }
  90
  91     public:
  92
  93     // use initialiser lists to save on temporary variables needing to be initialised in the constructor body
  94     ArrayTemplateImpl() : elements_ptr(nullptr), size(0), next_free(0) {}
  95     ArrayTemplateImpl(size_type elements) : size(elements), next_free(0) { elements_ptr = new T[size]; }
  96
  97     ArrayTemplateImpl(const ArrayTemplateImpl& object) : size(object.get_size()), next_free(object.get_next_free())
  98     {
  99       if (size > 0 ) {
 100         elements_ptr = new T[size];
 101         for (size_type i = 0; i < size; ++i)
 102           elements_ptr[i] = object.element_at(i);
 103       }
 104     }
 105
 106     ~ArrayTemplateImpl()
 107     {
 108       delete[] elements_ptr;
 109       elements_ptr = nullptr;
 110       size = next_free = 0;
 111     }
 112
 113     size_type get_size() { return size; }
 114
 115     void add_element(T& new_element)
 116     {
 117       if (next_free == size)
 118         grow();
 119
 120       /* using post-increment; equivalent to:
 121        * elements_ptr[next_free] = new_element;
 122        * ++next_free;
 123        */
 124       elements_ptr[next_free++] = new_element;
 125     }
 126
 127     // when removing an element return it to the caller in case it is needed elsewhere
 128     T* remove_element()
 129     {
 130       // using ternary operator since 1 of 2 values is always returned (with integrated post-decrement)
 131       return next_free > 0 ? &elements_ptr[--next_free] : nullptr;
 132
 133       /* since 'next_free' is the sole indicator of how many elements of the array are
 134        * allocated it isn't necessary to reset the vacated T* e.g:
 135        *  T* temp_ptr = elements_ptr[next_free];
 136        *  elements_ptr[next_free--] = nullptr;
 137        *  return temp_ptr;
 138        */
 139     }
 140
 141     T& operator[](size_type index) { assert(index < size); return elements_ptr[index]; }
 142
 143     // using ternary operator since 1 of 2 values is always returned
 144     T* element_at(size_type index) { return index < size ? &elements_ptr[index] : nullptr; }
 145
 146
 147     /* inner class declaring const and non-const custom Standard Template Library (STL) iterators
 148      * without duplicate class declarations */
 149
 150
 151     template<bool is_const_iterator = true>
 152     class iterator : public std::iterator<std::forward_iterator_tag, T> {
 153       /*
 154        * 1. typedef our container's type to the naming convention used by the STL iterators
 155        * 2. Use std::conditional to decide whether to declare const or non-const iterator
 156        * 3. declare and implement methods to support a forward iterator
 157        */
 158       typedef iterator self_type;
 159       typedef typename std::conditional<is_const_iterator, const T, T>::type value_type;
 160       typedef typename std::conditional<is_const_iterator, const T&, T&>::type reference;
 161       typedef typename std::conditional<is_const_iterator, const T*, T*>::type pointer;
 162       typedef std::forward_iterator_tag iterator_category;
 163       typedef int difference_type;
 164
 165       pointer element_ptr;
 166
 167       public:
 168
 169       iterator(pointer element) : element_ptr(element) {}
 170       iterator(const iterator<false>& copy) : element_ptr(copy.element_ptr) { }
 171       self_type operator++() { self_type e = *this; ++element_ptr; return e; }
 172       self_type operator++(int unused) { ++element_ptr; return *this; }
 173       reference operator*() { return *element_ptr; }
 174       pointer   operator->() { return element_ptr; }
 175       bool operator==(const self_type& right_hand_side) { return element_ptr == right_hand_side.element_ptr; }
 176       bool operator!=(const self_type& right_hand_side) { return element_ptr != right_hand_side.element_ptr; }
 177
 178       friend class iterator<true>; // allow const and non-const iterator copy-contructors access to private members
 179
 180     }; // end of inner class
 181
 182
 183     // methods directly supporting use of the iterator
 184     template<bool is_const_iterator = true>
 185     iterator<is_const_iterator> begin() { return iterator<is_const_iterator>(elements_ptr); }
 186     template<bool is_const_iterator = true>
 187     iterator<is_const_iterator> end()   { return iterator<is_const_iterator>( next_free > 0 ? &elements_ptr[next_free - 1] : nullptr); }
 188
 189     // helper types for code that instantiates iterators
 190     typedef iterator<true> _const_iterator;
 191     typedef iterator<false> _iterator;
 192   };
 193
 194 }
 195 #endif
 196