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    */
  42   template <typename T, template<typename> class DATA_STRUCTURE = DataStructure_ArrayDynamic>
  43   class GenericStorageContainerTemplateImpl
  44   {
  45     // attributes
  46
  47     // data structure type is templated
  48     DATA_STRUCTURE<T> data_structure_;
  49
  50
  51     public:
  52
  53     /* constant and non-constant custom Standard Template Library (STL) compatible iterators
  54      * avoiding writing 2 separate class definitions that only differ on their
  55      * constant vs non-constant type specifiers. This makes extensive use of
  56      * template metaprogramming
  57      *
  58      * defaults to a non-const iterator
  59      */
  60     template <bool is_const_iterator = false>
  61     class iterator : public std::iterator< std::bidirectional_iterator_tag, AbstractDataStructure<T> >
  62     {
  63       typedef iterator self_type;
  64       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>, AbstractDataStructure<T> >::type value_type;
  65       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>&, AbstractDataStructure<T>& >::type reference;
  66       typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>*, AbstractDataStructure<T>* >::type pointer;
  67       typedef std::bidirectional_iterator_tag iterator_category;
  68       typedef int difference_type;
  69
  70       DATA_STRUCTURE<T>* element_;
  71
  72       public:
  73
  74       iterator<is_const_iterator> () {};
  75       iterator<is_const_iterator> (DATA_STRUCTURE<T>* element) : element_(element) {};
  76       iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : element_(copy.element_) {}; // copy constructor
  77
  78       // ForwardIterator methods
  79
  80       // postfix increment operator
  81       self_type operator++()
  82       {
  83         self_type original(*this); // need to keep a copy of the current value so it can be returned
  84
  85         DATA_STRUCTURE<T>* temp = element_->get_next();
  86         if (temp)
  87           element_ = temp; // the increment changes the item being referenced
  88
  89         return original;
  90       };
  91
  92       // prefix increment operator
  93       self_type operator++(int unused)
  94       {
  95         DATA_STRUCTURE<T>* result = nullptr;
  96
  97         if (element_) {
  98           result = element_->get_next();
  99           element_ = result;
 100         }
 101         return *this;
 102       };
 103
 104       // BidirectionalIterator methods
 105
 106       // postfix decrement
 107       self_type operator--()
 108       {
 109         self_type original(*this); // keep copy that is to be returned
 110         this->element_->get_previous();
 111         return original;
 112       };
 113
 114       // prefix decrement
 115       self_type operator--(int unused)
 116       {
 117         if (element_)
 118           element_ = element_->get_previous();
 119
 120         return *this;
 121       };
 122
 123       // comparison methods
 124       bool operator==(const self_type& right_hand_side)
 125       {
 126         bool result = false;
 127
 128         if (element_ && right_hand_side.element_)
 129           result = *this->element_ == *right_hand_side.element_;
 130
 131         return result;
 132       };
 133
 134       bool operator!=(const self_type& right_hand_side)
 135       {
 136         return !this->operator==(right_hand_side);
 137       };
 138
 139       bool operator<(const self_type& right_hand_side)
 140       {
 141         bool result = false;
 142
 143         if (element_ && right_hand_side.element_)
 144           result = *this->element_ < *right_hand_side.element_;
 145
 146         return result;
 147       };
 148
 149       bool operator<=(const self_type& right_hand_side)
 150       {
 151         return this->operator==(right_hand_side) | this->operator<(right_hand_side);
 152       };
 153
 154       // data access
 155       T operator* ()
 156       {
 157
 158         return element_ ? *element_->get_data() : 0;
 159       };
 160
 161       std::conditional<is_const_iterator, const T*, T*>  operator->()
 162       {
 163         return &element_->get_data();
 164       };
 165
 166       // allow const and non-const iterator copy-contructors access to private members
 167       friend class iterator<!is_const_iterator>;
 168
 169     }; // end of Iterator
 170
 171     // use these handy short-cuts in application code
 172     typedef iterator<true> _const_iterator;
 173     typedef iterator<false> _iterator;
 174
 175     /* methods directly supporting use of the iterator uses 'template' to avoid
 176      * writing 4 method definitions (2 for constant and 2 for non-constant iterators)
 177      *
 178      * begin() and end() are used in code that instantiates the iterator:
 179      *
 180      * GSCTI<int> container;
 181      * container.insert(1);
 182      * container.insert(2);
 183      *
 184      * for (_const_iterator i = container.begin(); i != container.end(); ++i)
 185      * {
 186      *   cout << *i << endl;
 187      * }
 188      *
 189      * for (auto element : container ) // range-for operator
 190      * {
 191      *   cout << element << endl;
 192      * }
 193      */
 194     template<bool is_const_iterator = false>
 195     iterator<is_const_iterator> begin()
 196     {
 197       return iterator<is_const_iterator>(data_structure_.get_begin());
 198     };
 199
 200     template<bool is_const_iterator = false>
 201     iterator<is_const_iterator> end()
 202     {
 203       return iterator<is_const_iterator>(data_structure_.get_end());
 204     };
 205
 206     // object life-cycle
 207     GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> () {};
 208     GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> (const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
 209     {
 210        // TODO: implement copy constructor
 211     };
 212
 213     ~GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>()
 214     {
 215     };
 216
 217     // capacity
 218     size_t get_capacity()
 219     {
 220       return data_structure_.get_capacity();
 221     };
 222
 223     size_t get_size()
 224     {
 225       return data_structure_.get_size();
 226     };
 227
 228     // modifiers
 229
 230     // append at tail
 231     bool append(T& data)
 232     {
 233       return data_structure_.append(data);
 234     };
 235
 236     // remove from tail
 237     bool remove()
 238     {
 239       return false;
 240     };
 241
 242   }; // end of GenericStorageContainerTemplateImpl
 243
 244   // handy short-cuts for unweildy names
 245   template<typename T, template<class> class DS = DataStructure_ArrayDynamic> using GSCTI = GenericStorageContainerTemplateImpl< T, DS>;
 246
 247 }; // end of namespace
 248
 249 #endif