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