GenericStorageContainerTemplateImpl.hpp

   1 /*
   2  * Implementation of a Generic Data Structure Container 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 _GENERICSTORAGECONTAINERTEMPLATEIMPL_HPP_
  21 #define _GENERICSTORAGECONTAINERTEMPLATEIMPL_HPP_
  22
  23 #include "DataStructures.hpp"
  24 #include <iterator>
  25 #include <memory>
  26
  27 namespace tj
  28 {
  29
  30  /* A generic Container that can use different internal data structures
  31    * (Array, Linked-List, Binary Search Tree) determined by
  32    * application code at compile time using the power of Templating
  33    * and Metaprogramming of C++11 and later.
  34    *
  35    * Default data structure is a Dynamic Array
  36    *
  37    * Uses Metaprogramming conditionals to create constant and non-constant iterators
  38    * from a single iterator definition. Provides typedefs to make instantiating the
  39    * correct type of iterator easier to read and write in application code.
  40    *
  41    * template parameters:
  42    * T = type being stored
  43    * DATA_STRUCTURE = class providing underlying storage of T elements, defaults to dynamic array
  44    *
  45    * For template template parameters see http://en.cppreference.com/w/cpp/language/template_parameters
  46    */
  47   template <typename T, template<typename> class DATA_STRUCTURE = DataStructure_ArrayDynamic>
  48   class GenericStorageContainerTemplateImpl
  49   {
  50     // easy to read aliases
  51     typedef AbstractDataStructure<T> DS_BASE_CLASS; // for access to enums
  52
  53     // data structure type is templated and decided by application code at compilation time
  54     DATA_STRUCTURE<T> data_structure_;
  55
  56
  57     public:
  58
  59     /* constant and non-constant custom Standard Template Library (STL) compatible iterators
  60      * avoiding writing 2 separate class definitions that only differ on their
  61      * constant vs non-constant type specifiers. This makes extensive use of
  62      * template metaprogramming
  63      *
  64      * defaults to a non-const iterator
  65      */
  66     template <bool is_const_iterator = false>
  67     class iterator : public std::iterator< std::bidirectional_iterator_tag, AbstractDataStructure<T> >
  68     {
  69       typedef iterator self_type;
  70       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>, AbstractDataStructure<T> >::type value_type;
  71       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>&, AbstractDataStructure<T>& >::type reference;
  72       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>*, AbstractDataStructure<T>* >::type pointer;
  73       typedef std::bidirectional_iterator_tag iterator_category;
  74       typedef int difference_type;
  75
  76       DATA_STRUCTURE<T>* element_;
  77
  78       public:
  79
  80       iterator<is_const_iterator> () {};
  81       iterator<is_const_iterator> (DATA_STRUCTURE<T>* element) : element_(element) {};
  82       iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : element_(copy.element_) {}; // copy constructor
  83
  84       /* ForwardIterator methods */
  85
  86       // postfix increment operator
  87       self_type operator++()
  88       {
  89         self_type original(*this); // need to keep a copy of the current value so it can be returned
  90
  91         DATA_STRUCTURE<T>* temp = element_->get_next();
  92         if (temp)
  93           element_ = temp; // the increment changes the item being referenced
  94
  95         return original;
  96       };
  97
  98       // prefix increment operator
  99       self_type operator++(int unused)
 100       {
 101         DATA_STRUCTURE<T>* result = nullptr;
 102
 103         if (element_) {
 104           result = element_->get_next();
 105           element_ = result;
 106         }
 107         return *this;
 108       };
 109
 110       /* BidirectionalIterator methods */
 111
 112       // postfix decrement
 113       self_type operator--()
 114       {
 115         self_type original(*this); // keep copy that is to be returned
 116         this->element_->get_previous();
 117         return original;
 118       };
 119
 120       // prefix decrement
 121       self_type operator--(int unused)
 122       {
 123         if (element_)
 124           element_ = element_->get_previous();
 125
 126         return *this;
 127       };
 128
 129
 130       /* Comparison */
 131
 132       bool operator==(const self_type& right_hand_side)
 133       {
 134         bool result = false;
 135
 136         if (element_ && right_hand_side.element_)
 137           result = *this->element_ == *right_hand_side.element_;
 138
 139         return result;
 140       };
 141
 142       // implemented using operator==()
 143       bool operator!=(const self_type& right_hand_side)
 144       {
 145         return !this->operator==(right_hand_side);
 146       };
 147
 148       bool operator<(const self_type& right_hand_side)
 149       {
 150         bool result = false;
 151
 152         if (element_ && right_hand_side.element_)
 153           result = *this->element_ < *right_hand_side.element_;
 154
 155         return result;
 156       };
 157
 158       // implemented using operator==() and operator<()
 159       bool operator<=(const self_type& right_hand_side)
 160       {
 161         return this->operator==(right_hand_side) | this->operator<(right_hand_side);
 162       };
 163
 164       /*
 165        * Data access */
 166
 167       // value-at
 168       T operator* ()
 169       {
 170         return element_ ? *element_->get_data() : 0;
 171       };
 172
 173       // pointer-to
 174       std::conditional<is_const_iterator, const T*, T*>  operator->()
 175       {
 176         return &element_->get_data();
 177       };
 178
 179       // allow const and non-const iterator copy-contructors access to private members of each other
 180       friend class iterator<!is_const_iterator>;
 181
 182     }; // end of Iterator
 183
 184     // use these handy aliases in application code
 185     typedef iterator<true> _const_iterator;
 186     typedef iterator<false> _iterator;
 187
 188     /* methods directly supporting use of the iterator uses 'template' to avoid
 189      * writing 4 method definitions (2 for constant and 2 for non-constant iterators)
 190      *
 191      * begin() and end() are used in code that instantiates the iterator:
 192      *
 193      * GSCTI<int> container;
 194      * container.append(1);
 195      * container.append(2);
 196      *
 197      * for (_const_iterator i = container.begin(); i != container.end(); ++i)
 198      * {
 199      *   cout << *i << endl;
 200      * }
 201      *
 202      * for (auto element : container ) // range-for operator
 203      * {
 204      *   cout << element << endl;
 205      * }
 206      */
 207     template<bool is_const_iterator = false>
 208     iterator<is_const_iterator> begin()
 209     {
 210       return iterator<is_const_iterator>(data_structure_.get_begin());
 211     };
 212
 213     template<bool is_const_iterator = false>
 214     iterator<is_const_iterator> end()
 215     {
 216       return iterator<is_const_iterator>(data_structure_.get_end());
 217     };
 218
 219
 220     /* Object life-cycle */
 221
 222     GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> () {};
 223     GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> (const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
 224     {
 225        // TODO: implement copy constructor
 226     };
 227
 228     ~GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>()
 229     {
 230     };
 231
 232
 233     /* Capacity */
 234
 235     // storage allocated (in units of stored type)
 236     size_t get_capacity()
 237     {
 238       return data_structure_.get_capacity();
 239     };
 240
 241     // storage used (in units of stored type)
 242     size_t get_size()
 243     {
 244       return data_structure_.get_size();
 245     };
 246
 247     /* Modifiers */
 248
 249     // append
 250     bool append(T& data)
 251     {
 252       return data_structure_.append(data);
 253     };
 254
 255     // remove
 256     bool remove()
 257     {
 258       return data_structure_.remove_at(DS_BASE_CLASS::HEAD, DS_BASE_CLASS::NO_ERASE);
 259     };
 260
 261   }; // end of GenericStorageContainerTemplateImpl
 262
 263   // GSCTI: handy alias for unweildy type name
 264   template<typename T, template<class> class DS = DataStructure_ArrayDynamic> using GSCTI = GenericStorageContainerTemplateImpl< T, DS>;
 265
 266 }; // end of namespace
 267
 268 #endif
 269