GenericStorageContainerTemplateImpl.hpp

   1 /*
   2  * Implementation of a Generic Storage Type 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 _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
  21 #define _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
  22
  23 #include <iterator>
  24 #include <memory>
  25
  26 namespace tj
  27 {
  28
  29   /* possible options for the storage class the application may request
  30    */
  31   enum Storage
  32   {
  33     unknown,
  34     static_array,
  35     dynamic_array,
  36     linked_list_single,
  37     linked_list_double,
  38     bst,
  39     bst_reversible,
  40     LENGTH                // allows application to determine how many storage classes are available
  41   };
  42
  43   /* A generic Container that can use different internal storage
  44    * representations (Array, Linked-List, Binary Search Tree) based on an
  45    * enum passed by application code at compile time using the power of Templating
  46    * and Metaprogramming of C++11 and later.
  47    *
  48    * Uses Metaprogramming conditionals to create constant and non-constant iterators
  49    * from a single iterator definition. Provides typedefs to make instantiating the
  50    * correct type of iterator easier to read and write in application code.
  51    *
  52    */
  53   template <typename T, class STORAGE_CLASS>
  54   class GenericStorageContainerTemplateImpl
  55   {
  56     /* XXX: Have to use different template typename value (T, S, etc.) although the types are
  57      * the same else the compiler cannot determine the correct value to use.
  58      * Metaprogramming does not have the concept of scope or namespace:
  59      *
  60      *
  61      *   GenericStorageContainerTemplateImpl.hpp:40:15: error: declaration of ‘class T’
  62      *   template <typename T>
  63      *             ^
  64      *   GenericStorageContainerTemplateImpl.hpp:31:13: error:  shadows template parm ‘class T’
  65      *   template <typename T, int storage_class>
  66      *             ^
  67      */
  68
  69     /* Abstract base class for the different storage classes
  70      *
  71      * Defines the API they must implement. The API allows the Container and its
  72      * Iterator to call common methods to perform store, retrieve, and search operations
  73      */
  74
  75     public:
  76     template <typename S>
  77     class StorageClass
  78     {
  79       S& __data;
  80
  81       public:
  82       StorageClass() {};
  83       StorageClass(S& data) : __data(data) {};
  84       virtual ~StorageClass() {};
  85
  86       /* API available to application
  87        *
  88        * Some methods are pure virtual making this an Abstract (base) class
  89        * Sub-classes must implement these methods and over-ride others to
  90        * provide the specific storage class functionality
  91        */
  92       S& get_data()
  93       {
  94         return __data;
  95       };
  96
  97       virtual S& get_first() = 0;
  98       virtual S& get_previous() = 0;
  99       virtual S& get_next() = 0;
 100       virtual S& get_last() = 0;
 101
 102       /*
 103        * @param data the item (of type S) to be stored
 104        * @param index position to insert; 0 is 'beginning', -1 is 'end'
 105        *
 106        * Depending on the concrete implemenation of this method, values of index other
 107        * than 0 or -1 may have no meaning and be ignored
 108        */
 109       virtual bool insert_at(S& data, long index = -1) = 0;
 110       virtual bool insert(S& data)
 111       {
 112         return insert_at(data, 0);
 113       };
 114       virtual bool append(S& data)
 115       {
 116         return insert_at(data, -1);
 117       };
 118
 119       virtual bool remove_at(S& data, long index = -1) = 0;
 120       virtual bool remove() = 0;
 121       virtual bool remove(S& data) = 0;
 122       virtual bool erase(S& data) = 0;
 123     };
 124
 125
 126     /* Specialised storage class implementing a Dynamic Array
 127      */
 128     template <typename SAD>
 129     class StorageClass_DynamicArray : StorageClass<SAD>
 130     {
 131       // TODO: implement
 132     };
 133
 134     /* Specialised storage class implementing a 2-way Linked List
 135      */
 136     template <typename SLLD>
 137     class StorageClass_LinkedListDouble : StorageClass<SLLD>
 138     {
 139       // TODO: implement
 140     };
 141
 142     /* Specialised storage class implementing a Binary Search Tree
 143      */
 144     template <typename SBST>
 145     class StorageClass_BinarySearchTree : StorageClass<SBST>
 146     {
 147       // TODO: implement
 148     };
 149
 150
 151     // attributes
 152
 153     /* storage class type is decided when collection is compiled
 154      * so use the (abstract) base class to keep the Collection's private
 155      * reference to the internal storage class
 156      */
 157     STORAGE_CLASS __storage;
 158
 159
 160     public:
 161
 162     GenericStorageContainerTemplateImpl() : __storage(nullptr) {};
 163     GenericStorageContainerTemplateImpl(T& data)
 164     {
 165
 166       __storage = new STORAGE_CLASS(data);
 167     };
 168
 169     /* constant and non-constant custom Standard Template Library (STL) iterators
 170      * avoiding writing 2 separate class definitions that only differ on their
 171      * constant vs non-constant type specifiers. This makes extensive use of
 172      * template metaprogramming
 173      *
 174      * defaults to a non-const iterator
 175      */
 176     template <bool is_const_iterator = false>
 177     class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
 178     {
 179       /* XXX: Ensure the <iterator> header is included to avoid cryptic errors:
 180        *
 181        *     GenericStorageContainerTemplateImpl.hpp:168:42: error: expected template-name before ‘<’ token
 182        *        class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
 183        *                                             ^
 184        *     GenericStorageContainerTemplateImpl.hpp:168:42: error: expected ‘{’ before ‘<’ token
 185        *     GenericStorageContainerTemplateImpl.hpp:168:42: error: expected unqualified-id before ‘<’ token
 186        */
 187
 188       /*
 189        * 1. typedef the container's type to the naming convention used by the STL iterators (makes readable code)
 190        * 2. Use Metaprogramming's std::conditional to decide whether to declare const or non-const iterator
 191        *    which avoids writing 2 iterator classes, keeping the code cleaner and easier to use
 192        * 3. declare and implement methods to support forward and reverse iteration (bidirectional)
 193        */
 194       typedef iterator self_type;
 195       typedef typename std::conditional< is_const_iterator, const StorageClass<T>, StorageClass<T> >::type value_type;
 196       typedef typename std::conditional< is_const_iterator, const StorageClass<T>&, StorageClass<T>& >::type reference;
 197       typedef typename std::conditional< is_const_iterator, const StorageClass<T>*, StorageClass<T>* >::type pointer;
 198       typedef std::bidirectional_iterator_tag iterator_category;
 199       typedef int difference_type;
 200
 201       StorageClass<T>& __node;
 202
 203       public:
 204
 205       iterator<is_const_iterator> () {}; // default constructor
 206       iterator<is_const_iterator> ( StorageClass<T>& node) : __node(node) {};
 207       iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : __node(copy.__node) {}; // copy constructor
 208
 209       // ForwardIterator methods
 210
 211       // postfix increment operator
 212       self_type operator++()
 213       {
 214         self_type original = *this; // need to keep a reference to the current value so it can be returned
 215         this->__node = this->__node->get_next(); // after the increment changes the item being referenced
 216         return original;
 217       }
 218
 219       // prefix increment operator
 220       self_type operator++(int unused)
 221       {
 222         __node = __node.get_next();
 223         return *this;
 224       }
 225
 226       // BidirectionalIterator methods
 227
 228       // postfix decrement
 229       self_type operator--()
 230       {
 231         self_type original = *this; // keep reference to value that is to be returned
 232         this->__node.get_previous();
 233         return original;
 234       };
 235
 236       // prefix decrement
 237       self_type operator--(int unused)
 238       {
 239         __node = __node->get_previous();
 240         return *this;
 241       };
 242
 243       // Comparison methods
 244       bool operator==(const self_type& right_hand_side)
 245       {
 246         return __node == right_hand_side.__node;
 247       }
 248
 249       bool operator!=(const self_type& right_hand_side)
 250       {
 251         return __node != right_hand_side.__node;
 252       }
 253
 254       T operator* ()
 255       {
 256         return __node->get_data();
 257       }
 258
 259       std::conditional<is_const_iterator, const T*, T*>  operator->()
 260       {
 261         return &__node->get_data();
 262       }
 263
 264       // allow const and non-const iterator copy-contructors access to private members
 265       friend class iterator<!is_const_iterator>;
 266
 267     }; // end of Iterator
 268
 269   // use these handy short-cuts in application code
 270   typedef iterator<true> _const_iterator;
 271   typedef iterator<false> _iterator;
 272
 273   }; // end of GenericStorageContainerTemplateImpl
 274
 275   // handy short-cuts for unweildy names
 276   template<typename T, class SC> using GSCTI = GenericStorageContainerTemplateImpl< T, SC>;
 277   template<typename T> using SC_DA = tj::GenericStorageContainerTemplateImpl::StorageClass_DynamicArray<T>;
 278
 279 }; // end of namespace
 280
 281 #endif