* see ./COPYRIGHT or http://www.gnu.org/licenses/gpl-3.0.html
*/
-#ifndef _STORAGE_CLASS_HPP_
-#define _STORAGE_CLASS_HPP_
+#ifndef _DATASTRUCTURE_HPP_
+#define _DATASTRUCTURE_HPP_
#include <iterator>
#include <memory>
namespace tj
{
- /* Abstract base class for the different storage classes
+ /* Abstract base class for the different data structures
*
* 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>
+ template <typename D>
class AbstractDataStructure
{
size_t capacity_;
* Sub-classes must implement these methods and over-ride others to
* provide the specific storage class functionality
*/
+
virtual size_t get_capacity() // available storage (in units of storage type)
{
return capacity_;
/* the concepts of first, last, next and previous may not have a useful meaning in
* some storage classes e.g: 'previous' in a 1-way linked list (only has 'next').
*/
- virtual S& get_first() = 0;
- virtual S& get_last() = 0;
- virtual S& get_next() = 0;
- virtual S& get_previous() = 0;
+ virtual D* get_data() = 0;
+ virtual D& get_first() = 0;
+ virtual D& get_last() = 0;
+ virtual D& get_next() = 0;
+ virtual D& get_previous() = 0;
/*
* @param data the item (of type S) to be stored
*
* Depending on the data structure, 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_at(D& data, long index = -1) = 0;
- virtual bool insert(S& data)
+ virtual bool insert(D& data)
{
return insert_at(data, 0);
};
- virtual bool append(S& data)
+ virtual bool append(D& data)
{
return insert_at(data, -1);
};
*/
// 'data' element at 'index' must satisfy equality
- virtual bool remove_at(S& data, long index = -1, bool erase = false) = 0; // element matching 'data' at 'index'
+ virtual bool remove_at(D& data, long index = -1, bool erase = false) = 0; // element matching 'data' at 'index'
virtual bool remove_at(long index = -1, bool erase = false) = 0; // any element at 'index'
- virtual bool remove_all(S& data, bool erase = false) = 0; // all elements matching 'data'
+ virtual bool remove_all(D& data, bool erase = false) = 0; // all elements matching 'data'
/* the replace operation can perform an optional erasure (delete) of the current data element
*/
- virtual bool replace_at(S& data_in, S& data_out, long index = -1, bool erase = false) = 0; // element matching 'data_out' at 'index'
- virtual bool replace_at(S& data_in, long index = -1, bool erase = false) = 0; // any element at 'index'
- virtual bool replace_all(S& data_in, S& data_out, bool erase = false) = 0; // all elements matching 'data_out'
+ virtual bool replace_at(D& data_in, D& data_out, long index = -1, bool erase = false) = 0; // element matching 'data_out' at 'index'
+ virtual bool replace_at(D& data_in, long index = -1, bool erase = false) = 0; // any element at 'index'
+ virtual bool replace_all(D& data_in, D& data_out, bool erase = false) = 0; // all elements matching 'data_out'
/* Search for an element matching 'needle'. The stored type must have defined
*
* returns a nullptr if there are no (more) matches
*/
- virtual S* find(S& needle, S* last_found = nullptr) = 0;
+ virtual D* find(D& needle, D* last_found = nullptr) = 0;
// mnemonic alternatives to plain 'index' values
enum position {
BEGIN = 0,
- END = -1
+ END = -1,
+ HEAD = 0,
+ TAIL = -1
};
};
/* Specialised data structure implementing a Binary Search Tree
*/
template <typename BST>
- class DataStructure_BinarySearchTree : DataStructure<BST>
+ class DataStructure_BinarySearchTree : AbstractDataStructure<BST>
{
// TODO: implement
};
#ifndef _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
#define _GENERIC_STORAGE_CONTAINER_TEMPLATE_IMPL_HPP_
+#include "DataStructures.hpp"
#include <iterator>
#include <memory>
namespace tj
{
- /* 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 <typename T, template<typename> class STORAGE_CLASS = StorageClass_DynamicArray>
+ template <typename T, template<typename> class DATA_STRUCTURE = DataStructure_ArrayDynamic>
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>
- * ^
- */
-
// attributes
- // storage class type is templated
- STORAGE_CLASS<T> storage_;
+ // data structure type is templated
+ DATA_STRUCTURE<T> data_structure_;
public:
GenericStorageContainerTemplateImpl() {};
- GenericStorageContainerTemplateImpl(const GenericStorageContainerTemplateImpl<T, STORAGE_CLASS>& copy)
+ GenericStorageContainerTemplateImpl(const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
{
};
~GenericStorageContainerTemplateImpl()
{
- delete storage_;
+ delete data_structure_;
};
- /* 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> >
+ class iterator : public std::iterator< std::bidirectional_iterator_tag, AbstractDataStructure<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 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;
+ AbstractDataStructure<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> (AbstractDataStructure<T>& element) : element_(element) {};
+ iterator<is_const_iterator> (const iterator<is_const_iterator>& copy) : element_(copy.element_) {}; // copy constructor
// 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
+ this->element_ = this->element_.get_next(); // after the increment changes the item being referenced
return original;
}
// prefix increment operator
self_type operator++(int unused)
{
- __node = __node.get_next();
+ element_ = element_.get_next();
return *this;
}
self_type operator--()
{
self_type original = *this; // keep reference to value that is to be returned
- this->__node.get_previous();
+ this->element_.get_previous();
return original;
};
// prefix decrement
self_type operator--(int unused)
{
- __node = __node->get_previous();
+ element_ = element_.get_previous();
return *this;
};
// Comparison methods
bool operator==(const self_type& right_hand_side)
{
- return __node == right_hand_side.__node;
+ return element_ == right_hand_side.element_;
}
bool operator!=(const self_type& right_hand_side)
{
- return __node != right_hand_side.__node;
+ return element_ != right_hand_side.element_;
}
T operator* ()
{
- return __node->get_data();
+ return element_.get_data();
}
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
}; // end of GenericStorageContainerTemplateImpl
// handy short-cuts for unweildy names
- template<typename T, template<class> class SC = StorageClass_DynamicArray> using GSCTI = GenericStorageContainerTemplateImpl< T, SC>;
+ template<typename T, template<class> class DS = DataStructure_ArrayDynamic> using GSCTI = GenericStorageContainerTemplateImpl< T, DS>;
}; // end of namespace
projects / GenericStorageContainerTemplate.git / commitdiff