#ifndef _DATASTRUCTURE_HPP_
#define _DATASTRUCTURE_HPP_
-#include <iterator>
+// #include <iterator>
#include <memory>
+#include <new> // for std::nothrow
namespace tj
{
* 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;
+
+ D* data_;
size_t capacity_;
size_t size_;
+ size_t current_;
public:
- AbstractDataStructure() {};
- virtual ~AbstractDataStructure() {};
+
+ AbstractDataStructure(size_t capacity = 0) : data_(nullptr), capacity_(capacity), size_(0), current_(0)
+ {
+ if (capacity_)
+ data_ = new(std::nothrow) D[capacity_];
+ };
+
+ virtual ~AbstractDataStructure()
+ {
+ if (data_ != nullptr)
+ delete[] data_;
+ };
/* API available to application
*
/* 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 D* get_data() = 0;
- virtual D& get_first() = 0;
- virtual D& get_last() = 0;
- virtual D& get_next() = 0;
- virtual D& get_previous() = 0;
+ virtual D* get_data()
+ {
+ return (data_ && size_ > 0) ? &data_[current_] : nullptr;
+ };
+
+ virtual self_type* get_begin() = 0;
+ virtual self_type* get_end() = 0;
+ virtual self_type* get_next() = 0;
+ virtual self_type* get_previous() = 0;
/*
* @param data the item (of type S) to be stored
virtual bool insert(D& data)
{
- return insert_at(data, 0);
+ return insert_at(data, TAIL);
};
virtual bool append(D& data)
{
- return insert_at(data, -1);
+ return insert_at(data, HEAD);
};
/* the remove operation can perform an optional erasure (delete) of the stored data.
*/
virtual D* find(D& needle, D* last_found = nullptr) = 0;
- // mnemonic alternatives to plain 'index' values
- enum position {
- BEGIN = 0,
- END = -1,
- HEAD = 0,
- TAIL = -1
+ virtual bool operator==(const D& right_hand_side)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
};
};
/* Specialised data structure implementing a Dynamic Array
*/
template <typename AD>
- class DataStructure_ArrayDynamic : AbstractDataStructure<AD>
+ class DataStructure_ArrayDynamic :
public AbstractDataStructure<AD>
{
+ typedef DataStructure_ArrayDynamic<AD> self_type;
+
+ size_t growth_;
+
+ public:
+ DataStructure_ArrayDynamic<AD>(size_t capacity = 512) : AbstractDataStructure<AD>(capacity), growth_(512) {};
+
+ virtual self_type* get_begin()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0) {
+ this->current_ = 0;
+ result = this;
+ }
+ return result;
+ };
+
+ virtual self_type* get_end()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ this->current_ = this->size_ - 1;
+ result = this;
+ }
+ return result;
+ };
+
+ virtual self_type* get_next()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ if (this->current_ + 1 < this->size_)
+ {
+ ++this->current_;
+ result = this;
+ }
+ }
+
+ return result;
+ };
+
+ virtual self_type* get_previous()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ if (this->current_ - 1 >= 0)
+ {
+ --this->current_;
+ result = this;
+ }
+ }
+
+ return result;
+ };
+
+ virtual bool insert_at(AD& data, long index = TAIL)
+ {
+ bool result = false;
+
+ if (this->data_ != nullptr)
+ {
+ if (index == TAIL)
+ index = 0;
+ else if (index == HEAD)
+ index = this->size_;
+
+ if (this->capacity_ <= index)
+ this->grow();
+
+ if (this->capacity_ > index)
+ {
+ this->data_[index] = data;
+
+ if (index >= this->size_)
+ this->size_ = index + 1;
+
+ result = true;
+ }
+ }
+
+ return result;
+ };
+
+ virtual bool remove_at(AD& data, long index = TAIL, bool erase = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool remove_at(long index = TAIL, bool erase = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool remove_all(AD& data, bool eraser = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool replace_at(AD& data_in, AD& data_out, long index = TAIL, bool erase = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool replace_at(AD& data_in, long index = TAIL, bool erase = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool replace_all(AD& data_in, AD& data_out, bool erase = false)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual AD* find(AD& needle, AD* last_found = nullptr)
+ {
+ AD* result = nullptr;
+ // TODO: implement
+ return result;
+ };
+
+ virtual bool operator==(const self_type& right_hand_side)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ bool grow()
+ {
+ bool result = false;
+ AD* temp = new (std::nothrow) AD[this->capacity_ + this->growth_];
+ if (temp != nullptr)
+ {
+ for (size_t index = 0; index < this->size_; ++index)
+ temp[index] = this->data_[index];
+
+ delete[] this->data_;
+ this->data_ = temp;
+
+ this->capacity_ += this->growth_;
+ result = true;
+ }
+
+ return result;
+ };
+
// TODO: implement
};
/* Specialised data structure implementing a 1-way Linked List
*/
template <typename LLS>
- class DataStructure_LinkedListSingle : AbstractDataStructure<LLS>
+ class DataStructure_LinkedListSingle : protected AbstractDataStructure<LLS>
{
// TODO: implement
};
/* Specialised data structure implementing a 2-way Linked List
*/
template <typename LLD>
- class DataStructure_LinkedListDouble : DataStructure_LinkedListSingle<LLD>
+ class DataStructure_LinkedListDouble : public DataStructure_LinkedListSingle<LLD>
{
// TODO: implement
};
/* Specialised data structure implementing a Binary Search Tree
*/
template <typename BST>
- class DataStructure_BinarySearchTree : AbstractDataStructure<BST>
+ class DataStructure_BinarySearchTree : protected AbstractDataStructure<BST>
{
// TODO: implement
};
/*
- * 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>
public:
- GenericStorageContainerTemplateImpl() {};
- GenericStorageContainerTemplateImpl(const GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>& copy)
- {
-
- };
- ~GenericStorageContainerTemplateImpl()
- {
- delete data_structure_;
- };
-
/* 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
typedef std::bidirectional_iterator_tag iterator_category;
typedef int difference_type;
- AbstractDataStructure<T>& element_;
+ DATA_STRUCTURE<T>* element_;
public:
iterator<is_const_iterator> () {};
- iterator<is_const_iterator> (AbstractDataStructure<T>& element) : element_(element) {};
+ 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
// postfix increment operator
self_type operator++()
{
- 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
+ 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)
{
- element_ = element_.get_next();
+ if (element_) {
+ DATA_STRUCTURE<T>* temp = element_->get_next();
+ if (temp)
+ element_ = temp;
+ }
return *this;
- }
+ };
// BidirectionalIterator methods
// postfix decrement
self_type operator--()
{
- self_type original = *this; // keep reference to value that is to be returned
- this->element_.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)
{
- element_ = element_.get_previous();
+ if (element_)
+ element_ = element_->get_previous();
+
return *this;
};
// Comparison methods
bool operator==(const self_type& right_hand_side)
{
- return element_ == right_hand_side.element_;
- }
+ bool result = false;
+
+ if (element_ && right_hand_side.element_)
+ result = *element_ == *right_hand_side.element_;
+
+ return result;
+ };
bool operator!=(const self_type& right_hand_side)
{
- return element_ != right_hand_side.element_;
- }
+ return !this->operator==(right_hand_side);
+ };
T operator* ()
{
- return element_.get_data();
- }
+
+ return element_ ? *element_->get_data() : 0;
+ };
std::conditional<is_const_iterator, const T*, T*> operator->()
{
- return &element_.get_data();
- }
+ return &element_->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;
+ // use these handy short-cuts 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.insert(1);
+ * container.insert(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>()
+ {
+ delete &data_structure_;
+ };
+
+ // capacity
+ size_t get_capacity()
+ {
+ return data_structure_.get_capacity();
+ };
+
+ size_t get_size()
+ {
+ return data_structure_.get_size();
+ };
+
+ // modifiers
+
+ // append at tail
+ bool append(T& data)
+ {
+ return data_structure_.append(data);
+ };
+
+ // remove from tail
+ bool remove()
+ {
+ return false;
+ };
}; // end of GenericStorageContainerTemplateImpl
break;
case 1: // Add node
test = new int(76543);
- my_collection_of_ints.add_node(test);
+ if (!my_collection_of_ints.append(*test))
+ cerr << "Error: insert failed" << endl;
break;
case 2: // Remove node
+ if (!my_collection_of_ints.remove())
+ cerr << "Error: remove failed" << endl;
break;
case 3: // List using forward Iterator
- cout << "size = " << my_collection_of_ints.get_size();
- for (int i : my_collection_of_ints) // XXX: C++11 'range for' automagically uses the iterator
+ cout << "size = " << my_collection_of_ints.get_size() << endl;
+ for (auto i : my_collection_of_ints) // XXX: C++11 'range for' automagically uses the iterator
{
cout << "Node = " << i << endl;
}
projects / GenericStorageContainerTemplate.git / commitdiff