#ifndef _DATASTRUCTURE_HPP_
#define _DATASTRUCTURE_HPP_
-#include <iterator>
#include <memory>
+#include <new> // for std::nothrow
namespace tj
{
template <typename D>
class AbstractDataStructure
{
- size_t capacity_;
- size_t size_;
+ 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_; // 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:
- AbstractDataStructure() {};
+
+ /* 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; } ),
+ capacity_(capacity),
+ size_(0),
+ current_(0)
+ {
+ if (capacity_)
+ data_.reset(new(std::nothrow) D[capacity_]);
+ };
+
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() = 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_.get() && size_ > 0) ? &data_.get()[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
*
* 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, 0);
+ return this->insert_at(data, TAIL);
};
virtual bool append(D& data)
{
- return insert_at(data, -1);
+ 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
*/
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
+ // comparison methods
+ virtual bool operator==(const self_type& right_hand_side)
+ {
+ bool result = false;
+ if (this->data_.get() && right_hand_side.data_.get())
+ result = this->current_ == right_hand_side.current_;
+
+ return result;
+ };
+ virtual bool operator!=(const self_type& right_hand_side)
+ {
+ return !this->operator==(right_hand_side);
+ };
+ virtual bool operator< (const self_type& right_hand_side)
+ {
+ bool result = false;
+ if (this->data_.get() && right_hand_side.data_.get())
+ result = this->current_ < right_hand_side.current_;
+
+ return result;
};
+ virtual bool operator<=(const self_type& right_hand_side)
+ {
+ return this->operator==(right_hand_side) | this->operator<(right_hand_side);
+ };
+
};
/* 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;
+ typedef AbstractDataStructure<AD> BASE_CLASS; // alias for easier reading of enums
+
+ size_t growth_;
+
+ public:
+ DataStructure_ArrayDynamic<AD>(size_t capacity = 512) : AbstractDataStructure<AD>(capacity), growth_(512) {};
+
+ /* Copy constructor that can do deep and shallow copies.
+ * Shallow copies are efficient for use by iterators where the only unique variable is
+ * the 'current_' index - the object can share a pointer to the data.
+ */
+ DataStructure_ArrayDynamic<AD>(const self_type& copy, bool shallow = false)
+ {
+ this->data_ = copy.data_;
+ this->capacity_ = copy.capacity_;
+ this->size_ = copy.size_;
+ this->current_ = copy.current_;
+ this->growth_ = copy.growth_;
+ if (!shallow)
+ {
+ this->data_.reset(new AD [this->capacity_]);
+ for (size_t i = 0; i < this->capacity_; ++i)
+ this->data_.get()[i] = copy.data_.get()[i];
+ }
+ }
+
+ virtual self_type* get_begin()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0) {
+ // TODO: make a shallow copy (share the array to avoid an expensive copy)
+ result = new self_type(*this, true);
+ result->current_ = 0;
+ }
+ return result;
+ };
+
+ virtual self_type* get_end()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ result = new self_type(*this, true);
+ // 1 beyond last element; used by iterator loops to detect when to break
+ result->current_ = result->size_;
+ }
+ return result;
+ };
+
+ virtual self_type* get_next()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ /* if (this->current_ + 1 < this->size_)
+ { */
+ result = new self_type(*this, true);
+ ++result->current_;
+ // }
+ }
+
+ return result;
+ };
+
+ virtual self_type* get_previous()
+ {
+ self_type* result = nullptr;
+
+ if (this->size_ > 0)
+ {
+ if (this->current_ - 1 >= 0)
+ {
+ result = new self_type(*this, true);
+ --result->current_;
+ }
+ }
+
+ return result;
+ };
+
+ virtual bool insert_at(AD& data, long index = BASE_CLASS::HEAD)
+ {
+ bool result = false;
+
+ if (this->data_ != nullptr)
+ {
+ if (index == BASE_CLASS::TAIL)
+ index = 0;
+ else if (index == BASE_CLASS::HEAD)
+ index = this->size_;
+
+ if (this->capacity_ <= index)
+ this->grow();
+
+ if (this->capacity_ > index)
+ {
+ this->data_.get()[index] = data;
+
+ if (index >= this->size_)
+ this->size_ = index + 1;
+
+ result = true;
+ }
+ }
+
+ return result;
+ };
+
+ 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 = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ 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 = 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 = 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 = BASE_CLASS::NO_ERASE)
+ {
+ bool result = false;
+ // TODO: implement
+ return result;
+ };
+
+ virtual AD* find(AD& needle, AD* last_found = nullptr)
+ {
+ AD* result = nullptr;
+ // TODO: implement
+ return result;
+ };
+
+ // comparisons require both sides to have the same array pointer
+ virtual bool operator==(const self_type& right_hand_side)
+ {
+ bool result = false;
+
+ if (this->data_.get() == right_hand_side.data_.get())
+ result = this->current_ == right_hand_side.current_;
+
+ return result;
+ };
+
+ virtual bool operator<(const self_type& right_hand_side)
+ {
+ bool result = false;
+
+ if (this->data_.get() == right_hand_side.data_.get())
+ result = this->current_ < right_hand_side.current_;
+
+ 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_.get()[index];
+
+ this->data_.reset(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
};
projects / GenericStorageContainerTemplate.git / blobdiff