2 * Implementation of a Generic Storage Type Container Template including STL Iterator
3 * Copyright (c) 2014 TJ <hacker@iam.tj>
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.
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.
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/>.
17 * see ./COPYRIGHT or http://www.gnu.org/licenses/gpl-3.0.html
20 #ifndef _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
21 #define _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
28 /* possible options for the storage class the application may request
39 LENGTH // allows application to determine how many storage classes are available
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.
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.
52 template <typename T, int storage_class>
53 class GenericStorageContainerTemplateImpl
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:
62 * GenericStorageContainerTemplateImpl.hpp:40:15: error: declaration of ‘class T’
63 * template <typename T>
65 * GenericStorageContainerTemplateImpl.hpp:31:13: error: shadows template parm ‘class T’
66 * template <typename T, int storage_class>
70 /* Abstract base class for the different storage classes
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
83 StorageClass(S& data) : __data(data) {};
85 /* API available to application
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
97 S& get_previous() = 0;
102 * @param data the item (of type S) to be stored
103 * @param index position to insert; 0 is 'beginning', -1 is 'end'
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
108 virtual bool insert_at(S& data, long index = -1) = 0;
109 virtual bool insert(S& data)
111 return insert_at(data, 0);
113 virtual bool append(S& data)
115 return insert_at(data, -1);
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;
125 /* Specialised storage class implementing a Dynamic Array
127 template <typename SAD>
128 class StorageClass_DynamicArray : StorageClass<SAD>
133 /* Specialised storage class implementing a 2-way Linked List
135 template <typename SLLD>
136 class StorageClass_DoubleLinkedList : StorageClass<SLLD>
141 /* Specialised storage class implementing a Binary Search Tree
143 template <typename SBST>
144 class StorageClass_BinarySearchTree : StorageClass<SBST>
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
156 StorageClass<T> storage;
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
166 * defaults to a non-const iterator
168 template <bool is_const_iterator = false>
169 class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
170 /* XXX: Ensure the <iterator> header is included to avoid cryptic errors:
172 * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected template-name before ‘<’ token
173 * class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
175 * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected ‘{’ before ‘<’ token
176 * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected unqualified-id before ‘<’ token
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)
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;
193 StorageClass<T>& __node;
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
201 // ForwardIterator methods
203 // postfix increment operator
204 self_type operator++()
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
211 // prefix increment operator
212 self_type operator++(int unused)
214 __node = __node.get_next();
218 // BidirectionalIterator methods
221 self_type operator--()
223 self_type original = *this; // keep reference to value that is to be returned
224 this->__node.get_previous();
229 self_type operator--(int unused)
231 __node = __node->get_previous();
235 // Comparison methods
236 bool operator==(const self_type& right_hand_side)
238 return __node == right_hand_side.__node;
241 bool operator!=(const self_type& right_hand_side)
243 return __node != right_hand_side.__node;
248 return __node->get_data();
251 std::conditional<is_const_iterator, const T*, T*> operator->()
253 return &__node->get_data();
256 // allow const and non-const iterator copy-contructors access to private members
257 friend class iterator<!is_const_iterator>;
259 }; // end of Iterator
261 /* use these handy short-cuts in application code
263 typedef iterator<true> _const_iterator;
264 typedef iterator<false> _iterator;
266 }; // end of GenericStorageContainerTemplateImpl
268 }; // end of namespace