* Iterator to call common methods to perform store, retrieve, and search operations
*/
- // mnemonic alternatives to plain 'index' values
- enum position {
- BEGIN = 0,
- END = -1,
- TAIL = 0,
- HEAD = -1
- };
-
template <typename D>
class AbstractDataStructure
{
- protected:
typedef AbstractDataStructure<D> self_type;
+ protected:
+
+ // shared pointer wraps actual data so that iterator instances can safely reference the same data
std::shared_ptr<D> data_;
- size_t capacity_;
- size_t size_;
- size_t current_;
+ size_t capacity_; // storage allocated (in units of data type)
+ size_t size_; // storage used (in units of data type)
+ size_t current_; // index of active element (may not make sense for some data structures but is needed for API)
public:
+ /* use descriptive symbols rather than booleans for method parameters */
+
+ // alternatives to numeric 'index' values
+ enum position {
+ BEGIN = 0,
+ END = -1, // newest
+ TAIL = 0,
+ HEAD = -1 // newest
+ };
+
+ // element erasure choices that evaluate to boolean states
+ enum erasure {
+ NO_ERASE, // false
+ ERASE // true
+ };
+
AbstractDataStructure(size_t capacity = 0) :
// use a lambda as the shared_ptr array deleter since the default deleter does not handle array deletion
data_(new D[capacity_], []( D* p) {delete[] p; } ),
virtual ~AbstractDataStructure() {};
- /* API available to application
+
+ /* API available to caller
*
* 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
*/
- virtual size_t get_capacity() // available storage (in units of storage type)
+ virtual size_t get_capacity() // storage allocated (in units of data type)
{
return capacity_;
};
- virtual size_t get_size() // used storage (in units of storage type)
+ virtual size_t get_size() // storage used (in units of data type)
{
return size_;
};
/* 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').
+ * some data structures e.g: 'previous' in a 1-way linked list (only has 'next').
*/
virtual D* get_data()
{
*
* Depending on the data structure, values of index other than 0 or -1 may have no meaning and be ignored
*/
- virtual bool insert_at(D& data, long index = -1) = 0;
+ virtual bool insert_at(D& data, long index = HEAD) = 0;
virtual bool insert(D& data)
{
- return insert_at(data, TAIL);
+ return this->insert_at(data, TAIL);
};
virtual bool append(D& data)
{
- return insert_at(data, HEAD);
+ return this->insert_at(data);
};
/* the remove operation can perform an optional erasure (delete) of the stored data.
*/
// 'data' element at 'index' must satisfy equality
- 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(D& data, bool erase = false) = 0; // all elements matching 'data'
+ virtual bool remove_at(D& data, long index = HEAD, bool erase = NO_ERASE) = 0; // element matching 'data' at 'index'
+ virtual bool remove_at(long index = HEAD, bool erase = NO_ERASE) = 0; // any element at 'index'
+ virtual bool remove_all(D& data, bool erase = NO_ERASE) = 0; // all elements matching 'data'
/* the replace operation can perform an optional erasure (delete) of the current data element
*/
- 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'
+ virtual bool replace_at(D& data_in, D& data_out, long index = HEAD, bool erase = NO_ERASE) = 0; // element matching 'data_out' at 'index'
+ virtual bool replace_at(D& data_in, long index = HEAD, bool erase = NO_ERASE) = 0; // any element at 'index'
+ virtual bool replace_all(D& data_in, D& data_out, bool erase = NO_ERASE) = 0; // all elements matching 'data_out'
/* Search for an element matching 'needle'. The stored type must have defined
class DataStructure_ArrayDynamic : public AbstractDataStructure<AD>
{
typedef DataStructure_ArrayDynamic<AD> self_type;
+ typedef AbstractDataStructure<AD> BASE_CLASS; // alias for easier reading of enums
size_t growth_;
return result;
};
- virtual bool insert_at(AD& data, long index = TAIL)
+ virtual bool insert_at(AD& data, long index = BASE_CLASS::HEAD)
{
bool result = false;
if (this->data_ != nullptr)
{
- if (index == TAIL)
+ if (index == BASE_CLASS::TAIL)
index = 0;
- else if (index == HEAD)
+ else if (index == BASE_CLASS::HEAD)
index = this->size_;
if (this->capacity_ <= index)
return result;
};
- virtual bool remove_at(AD& data, long index = TAIL, bool erase = false)
+ virtual bool remove_at(AD& data, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
return result;
};
- virtual bool remove_at(long index = TAIL, bool erase = false)
+ virtual bool remove_at(long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
return result;
};
- virtual bool remove_all(AD& data, bool eraser = false)
+ virtual bool remove_all(AD& data, bool eraser = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
return result;
};
- virtual bool replace_at(AD& data_in, AD& data_out, long index = TAIL, bool erase = false)
+ virtual bool replace_at(AD& data_in, AD& data_out, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
return result;
};
- virtual bool replace_at(AD& data_in, long index = TAIL, bool erase = false)
+ virtual bool replace_at(AD& data_in, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
return result;
};
- virtual bool replace_all(AD& data_in, AD& data_out, bool erase = false)
+ virtual bool replace_all(AD& data_in, AD& data_out, bool erase = BASE_CLASS::NO_ERASE)
{
bool result = false;
// TODO: implement
* 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, template<typename> class DATA_STRUCTURE = DataStructure_ArrayDynamic>
class GenericStorageContainerTemplateImpl
{
- // attributes
-
- // data structure type is templated
+ // 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_;
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++()
return *this;
};
- // BidirectionalIterator methods
+ /* BidirectionalIterator methods */
// postfix decrement
self_type operator--()
return *this;
};
- // comparison methods
+
+ /* Comparison */
+
bool operator==(const self_type& right_hand_side)
{
bool result = false;
return result;
};
+ // implemented using operator==()
bool operator!=(const self_type& right_hand_side)
{
return !this->operator==(right_hand_side);
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
+ /*
+ * Data access */
+
+ // value-at
T operator* ()
{
-
return element_ ? *element_->get_data() : 0;
};
+ // pointer-to
std::conditional<is_const_iterator, const T*, T*> operator->()
{
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;
* begin() and end() are used in code that instantiates the iterator:
*
* GSCTI<int> container;
- * container.insert(1);
- * container.insert(2);
+ * container.append(1);
+ * container.append(2);
*
* for (_const_iterator i = container.begin(); i != container.end(); ++i)
* {
{
return iterator<is_const_iterator>(data_structure_.get_end());
};
-
- // object life-cycle
+
+
+ /* Object life-cycle */
+
GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> () {};
GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE> (const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
{
{
};
- // capacity
+
+ /* 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
+ /* Modifiers */
- // append at tail
+ // append
bool append(T& data)
{
return data_structure_.append(data);
};
- // remove from tail
+ // remove
bool remove()
{
- return false;
+ return data_structure_.remove_at(DS_BASE_CLASS::HEAD, DS_BASE_CLASS::NO_ERASE);
};
}; // end of GenericStorageContainerTemplateImpl
- // handy short-cuts for unweildy names
+ // 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
+