--- /dev/null
+/*
+ * Implementation of a Generic Storage Type Container Template including STL Iterator
+ * Copyright (c) 2014 TJ <hacker@iam.tj>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * see ./COPYRIGHT or http://www.gnu.org/licenses/gpl-3.0.html
+ */
+
+#ifndef _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
+#define _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
+
+#include <iterator>
+
+namespace tj
+{
+
+ /* possible options for the storage class the application may request
+ */
+ enum Storage
+ {
+ unknown,
+ static_array,
+ dynamic_array,
+ linked_list_single,
+ linked_list_double,
+ bst,
+ bst_reversible,
+ LENGTH // allows application to determine how many storage classes are available
+ };
+
+ /* A generic Container that can use different internal storage
+ * representations (Array, Linked-List, Binary Search Tree) based on an
+ * enum passed by application code at compile time using the power of Templating
+ * and Metaprogramming of C++11 and later.
+ *
+ * Uses Metaprogramming conditionals to create constant and non-constant iterators
+ * from a single iterator definition. Provides typedefs to make instantiating the
+ * correct type of iterator easier to read and write in application code.
+ *
+ */
+ template <typename T, int storage_class>
+ class GenericStorageContainerTemplateImpl
+ {
+
+
+ /* XXX: Have to use different template typename value (T, S, etc.) although the types are
+ * the same else the compiler cannot determine the correct value to use.
+ * Metaprogramming does not have the concept of scope or namespace:
+ *
+ *
+ * GenericStorageContainerTemplateImpl.hpp:40:15: error: declaration of ‘class T’
+ * template <typename T>
+ * ^
+ * GenericStorageContainerTemplateImpl.hpp:31:13: error: shadows template parm ‘class T’
+ * template <typename T, int storage_class>
+ * ^
+ */
+
+ /* Abstract base class for the different storage classes
+ *
+ * Defines the API they must implement. The API allows the Container and its
+ * Iterator to call common methods to perform store, retrieve, and search operations
+ */
+
+ template <typename S>
+ class StorageClass
+ {
+ S& __data;
+
+ public:
+ StorageClass() {};
+ StorageClass(S& data) : __data(data) {};
+
+ /* API available to application
+ *
+ * Some methods are pure virtual making this an Abstract (base) class
+ * Sub-classes must implement these methods and over-ride others to
+ * provide the specific storage class functionality
+ */
+ S& get_data()
+ {
+ return __data;
+ };
+
+ S& get_first() = 0;
+ S& get_previous() = 0;
+ S& get_next() = 0;
+ S& get_last() = 0;
+
+ /*
+ * @param data the item (of type S) to be stored
+ * @param index position to insert; 0 is 'beginning', -1 is 'end'
+ *
+ * Depending on the concrete implemenation of this method, values of index other
+ * than 0 or -1 may have no meaning and be ignored
+ */
+ virtual bool insert_at(S& data, long index = -1) = 0;
+ virtual bool insert(S& data)
+ {
+ return insert_at(data, 0);
+ };
+ virtual bool append(S& data)
+ {
+ return insert_at(data, -1);
+ };
+
+ virtual bool remove_at(S& data, long index = -1) = 0;
+ virtual bool remove() = 0;
+ virtual bool remove(S& data) = 0;
+ virtual bool erase(S& data) = 0;
+ };
+
+
+ /* Specialised storage class implementing a Dynamic Array
+ */
+ template <typename SAD>
+ class StorageClass_DynamicArray : StorageClass<SAD>
+ {
+ // TODO: implement
+ };
+
+ /* Specialised storage class implementing a 2-way Linked List
+ */
+ template <typename SLLD>
+ class StorageClass_DoubleLinkedList : StorageClass<SLLD>
+ {
+ // TODO: implement
+ };
+
+ /* Specialised storage class implementing a Binary Search Tree
+ */
+ template <typename SBST>
+ class StorageClass_BinarySearchTree : StorageClass<SBST>
+ {
+ // TODO: implement
+ };
+
+
+ // attributes
+
+ /* storage class type is decided when collection is compiled
+ * so use the (abstract) base class to keep the Collection's private
+ * reference to the internal storage class
+ */
+ StorageClass<T> storage;
+
+
+ public:
+
+ /* constant and non-constant custom Standard Template Library (STL) iterators
+ * avoiding writing 2 separate class definitions that only differ on their
+ * constant vs non-constant type specifiers. This makes extensive use of
+ * template metaprogramming
+ *
+ * defaults to a non-const iterator
+ */
+ template <bool is_const_iterator = false>
+ class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
+ /* XXX: Ensure the <iterator> header is included to avoid cryptic errors:
+ *
+ * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected template-name before ‘<’ token
+ * class iterator : public std::iterator< std::bidirectional_iterator_tag, StorageClass<T> >
+ * ^
+ * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected ‘{’ before ‘<’ token
+ * GenericStorageContainerTemplateImpl.hpp:168:42: error: expected unqualified-id before ‘<’ token
+ */
+
+ {
+ /*
+ * 1. typedef the container's type to the naming convention used by the STL iterators (makes readable code)
+ * 2. Use Metaprogramming's std::conditional to decide whether to declare const or non-const iterator
+ * which avoids writing 2 iterator classes, keeping the code cleaner and easier to use
+ * 3. declare and implement methods to support forward and reverse iteration (bidirectional)
+ */
+ typedef iterator self_type;
+ typedef typename std::conditional< is_const_iterator, const StorageClass<T>, StorageClass<T> >::type value_type;
+ typedef typename std::conditional< is_const_iterator, const StorageClass<T>&, StorageClass<T>& >::type reference;
+ typedef typename std::conditional< is_const_iterator, const StorageClass<T>*, StorageClass<T>* >::type pointer;
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef int difference_type;
+
+ StorageClass<T>& __node;
+
+ public:
+
+ iterator<is_const_iterator> () {}; // default constructor
+ iterator<is_const_iterator> ( StorageClass<T>& node) : __node(node) {};
+ iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : __node(copy.__node) {}; // copy constructor
+
+ // postfix increment operator
+ self_type operator++()
+ {
+ self_type original = *this; // need to keep a reference to the current value so it can be returned
+ this->__node = this->__node->get_next(); // after the increment changes the item being referenced
+ return original;
+ }
+
+ // prefix increment operator
+ self_type operator++(int unused)
+ {
+ __node = __node->get_next();
+ return *this;
+ }
+
+ bool operator==(const self_type& right_hand_side)
+ {
+ return __node == right_hand_side.__node;
+ }
+
+ bool operator!=(const self_type& right_hand_side)
+ {
+ return __node != right_hand_side.__node;
+ }
+
+ T operator* ()
+ {
+ return __node->get_data();
+ }
+
+ std::conditional<is_const_iterator, const T*, T*> operator->()
+ {
+ return &__node->get_data();
+ }
+
+ // allow const and non-const iterator copy-contructors access to private members
+ friend class iterator<!is_const_iterator>;
+
+ }; // end of Iterator
+
+ /* use these handy short-cuts in application code
+ */
+ typedef iterator<true> _const_iterator;
+ typedef iterator<false> _iterator;
+
+ }; // end of GenericStorageContainerTemplateImpl
+
+}; // end of namespace
+
+#endif
projects / GenericStorageContainerTemplate.git / commitdiff