/*
- * Implementation of a Generic Storage Type Container Template including STL Iterator
+ * Implementation of a Generic Data Structure Container Template including STL Iterator
* Copyright (c) 2014 TJ <hacker@iam.tj>
*
* This program is free software: you can redistribute it and/or modify
* 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_
+#ifndef _GENERICSTORAGECONTAINERTEMPLATEIMPL_HPP_
+#define _GENERICSTORAGECONTAINERTEMPLATEIMPL_HPP_
+#include "DataStructures.hpp"
#include <iterator>
+#include <memory>
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
+ /* A generic Container that can use different internal data structures
+ * (Array, Linked-List, Binary Search Tree) determined by
+ * application code at compile time using the power of Templating
* and Metaprogramming of C++11 and later.
*
+ * Default data structure is a Dynamic Array
+ *
* 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 parameters:
+ * T = type being stored
+ * DATA_STRUCTURE = class providing underlying storage of T elements, defaults to dynamic array
+ *
+ * For template template parameters see http://en.cppreference.com/w/cpp/language/template_parameters
*/
- template <typename T, int storage_class>
+ template <typename T, template<typename> class DATA_STRUCTURE = DataStructure_ArrayDynamic>
class GenericStorageContainerTemplateImpl
{
+ // easy to read aliases
+ typedef AbstractDataStructure<T> DS_BASE_CLASS; // for access to enums
+ // data structure type is templated and decided by application code at compilation time
+ DATA_STRUCTURE<T> data_structure_;
- /* 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
+ /* constant and non-constant custom Standard Template Library (STL) compatible 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
- */
-
+ class iterator : public std::iterator< std::bidirectional_iterator_tag, AbstractDataStructure<T> >
{
- /*
- * 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 typename std::conditional< is_const_iterator, const AbstractDataStructure<T>, AbstractDataStructure<T> >::type value_type;
+ typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>&, AbstractDataStructure<T>& >::type reference;
+ typedef typename std::conditional< is_const_iterator, const AbstractDataStructure<T>*, AbstractDataStructure<T>* >::type pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef int difference_type;
- StorageClass<T>& __node;
+ DATA_STRUCTURE<T>* element_;
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
+ iterator<is_const_iterator> () {};
+ iterator<is_const_iterator> (DATA_STRUCTURE<T>* element) : element_(element) {};
+ iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : element_(copy.element_) {}; // copy constructor
- // ForwardIterator methods
+ /* ForwardIterator methods */
// 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
+ self_type original(*this); // need to keep a copy of the current value so it can be returned
+
+ DATA_STRUCTURE<T>* temp = element_->get_next();
+ if (temp)
+ element_ = temp; // the increment changes the item being referenced
+
return original;
- }
+ };
// prefix increment operator
self_type operator++(int unused)
{
- __node = __node.get_next();
+ DATA_STRUCTURE<T>* result = nullptr;
+
+ if (element_) {
+ result = element_->get_next();
+ element_ = result;
+ }
return *this;
- }
+ };
- // BidirectionalIterator methods
+ /* BidirectionalIterator methods */
// postfix decrement
self_type operator--()
{
- self_type original = *this; // keep reference to value that is to be returned
- this->__node.get_previous();
+ self_type original(*this); // keep copy that is to be returned
+ this->element_->get_previous();
return original;
};
// prefix decrement
self_type operator--(int unused)
{
- __node = __node->get_previous();
+ if (element_)
+ element_ = element_->get_previous();
+
return *this;
};
- // Comparison methods
+
+ /* Comparison */
+
bool operator==(const self_type& right_hand_side)
{
- return __node == right_hand_side.__node;
- }
+ bool result = false;
+ if (element_ && right_hand_side.element_)
+ result = *this->element_ == *right_hand_side.element_;
+
+ return result;
+ };
+
+ // implemented using operator==()
bool operator!=(const self_type& right_hand_side)
{
- return __node != right_hand_side.__node;
- }
+ return !this->operator==(right_hand_side);
+ };
+
+ bool operator<(const self_type& right_hand_side)
+ {
+ bool result = false;
+
+ if (element_ && right_hand_side.element_)
+ result = *this->element_ < *right_hand_side.element_;
+
+ return result;
+ };
+
+ // implemented using operator==() and operator<()
+ bool operator<=(const self_type& right_hand_side)
+ {
+ return this->operator==(right_hand_side) | this->operator<(right_hand_side);
+ };
+
+ /*
+ * Data access */
+ // value-at
T operator* ()
{
- return __node->get_data();
- }
+ return element_ ? *element_->get_data() : 0;
+ };
+ // pointer-to
std::conditional<is_const_iterator, const T*, T*> operator->()
{
- return &__node->get_data();
- }
+ return &element_->get_data();
+ };
- // allow const and non-const iterator copy-contructors access to private members
+ // allow const and non-const iterator copy-contructors access to private members of each other
friend class iterator<!is_const_iterator>;
}; // end of Iterator
- /* use these handy short-cuts in application code
- */
+ // use these handy aliases in application code
typedef iterator<true> _const_iterator;
typedef iterator<false> _iterator;
+ /* methods directly supporting use of the iterator uses 'template' to avoid
+ * writing 4 method definitions (2 for constant and 2 for non-constant iterators)
+ *
+ * begin() and end() are used in code that instantiates the iterator:
+ *
+ * GSCTI<int> container;
+ * container.append(1);
+ * container.append(2);
+ *
+ * for (_const_iterator i = container.begin(); i != container.end(); ++i)
+ * {
+ * cout << *i << endl;
+ * }
+ *
+ * for (auto element : container ) // range-for operator
+ * {
+ * cout << element << endl;
+ * }
+ */
+ template<bool is_const_iterator = false>
+ iterator<is_const_iterator> begin()
+ {
+ return iterator<is_const_iterator>(data_structure_.get_begin());
+ };
+
+ template<bool is_const_iterator = false>
+ iterator<is_const_iterator> end()
+ {
+ return iterator<is_const_iterator>(data_structure_.get_end());
+ };
+
+
+ /* Object life-cycle */
+
+ GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> () {};
+ GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> (const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
+ {
+ // TODO: implement copy constructor
+ };
+
+ ~GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>()
+ {
+ };
+
+
+ /* Capacity */
+
+ // storage allocated (in units of stored type)
+ size_t get_capacity()
+ {
+ return data_structure_.get_capacity();
+ };
+
+ // storage used (in units of stored type)
+ size_t get_size()
+ {
+ return data_structure_.get_size();
+ };
+
+ /* Modifiers */
+
+ // append
+ bool append(T& data)
+ {
+ return data_structure_.append(data);
+ };
+
+ // remove
+ bool remove()
+ {
+ return data_structure_.remove_at(DS_BASE_CLASS::HEAD, DS_BASE_CLASS::NO_ERASE);
+ };
+
}; // end of GenericStorageContainerTemplateImpl
+ // GSCTI: handy alias for unweildy type name
+ template<typename T, template<class> class DS = DataStructure_ArrayDynamic> using GSCTI = GenericStorageContainerTemplateImpl< T, DS>;
+
}; // end of namespace
#endif
+
projects / GenericStorageContainerTemplate.git / blobdiff