#ifndef _DATASTRUCTURE_HPP_
#define _DATASTRUCTURE_HPP_
-// #include <iterator>
#include <memory>
#include <new> // for std::nothrow
protected:
typedef AbstractDataStructure<D> self_type;
- D* data_;
+ std::shared_ptr<D> data_;
size_t capacity_;
size_t size_;
size_t current_;
public:
- AbstractDataStructure(size_t capacity = 0) : data_(nullptr), capacity_(capacity), size_(0), current_(0)
+ 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_ = new(std::nothrow) D[capacity_];
+ data_.reset(new(std::nothrow) D[capacity_]);
};
- virtual ~AbstractDataStructure()
- {
- if (data_ != nullptr)
- delete[] data_;
- };
+ virtual ~AbstractDataStructure() {};
/* API available to application
*
*/
virtual D* get_data()
{
- return (data_ && size_ > 0) ? &data_[current_] : nullptr;
+ return (data_.get() && size_ > 0) ? &data_.get()[current_] : nullptr;
};
virtual self_type* get_begin() = 0;
*/
virtual D* find(D& needle, D* last_found = nullptr) = 0;
- virtual bool operator==(const D& right_hand_side)
+ // comparison methods
+ virtual bool operator==(const self_type& right_hand_side)
{
bool result = false;
- // TODO: implement
+ 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);
+ };
+
};
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) {
- this->current_ = 0;
- result = this;
+ // TODO: make a shallow copy (share the array to avoid an expensive copy)
+ result = new self_type(*this, true);
+ result->current_ = 0;
}
return result;
};
if (this->size_ > 0)
{
- this->current_ = this->size_ - 1;
- result = this;
+ 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;
};
if (this->size_ > 0)
{
- if (this->current_ + 1 < this->size_)
- {
- ++this->current_;
- result = this;
- }
+ /* if (this->current_ + 1 < this->size_)
+ { */
+ result = new self_type(*this, true);
+ ++result->current_;
+ // }
}
return result;
{
if (this->current_ - 1 >= 0)
{
- --this->current_;
- result = this;
+ result = new self_type(*this, true);
+ --result->current_;
}
}
if (this->capacity_ > index)
{
- this->data_[index] = data;
+ this->data_.get()[index] = data;
if (index >= this->size_)
this->size_ = index + 1;
return result;
};
+ // comparisons require both sides to have the same array pointer
virtual bool operator==(const self_type& right_hand_side)
{
bool result = false;
- // TODO: implement
+
+ 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;
};
if (temp != nullptr)
{
for (size_t index = 0; index < this->size_; ++index)
- temp[index] = this->data_[index];
+ temp[index] = this->data_.get()[index];
- delete[] this->data_;
- this->data_ = temp;
+ this->data_.reset(temp);
this->capacity_ += this->growth_;
result = true;
// prefix increment operator
self_type operator++(int unused)
{
+ DATA_STRUCTURE<T>* result = nullptr;
+
if (element_) {
- DATA_STRUCTURE<T>* temp = element_->get_next();
- if (temp)
- element_ = temp;
+ result = element_->get_next();
+ element_ = result;
}
return *this;
};
return *this;
};
- // Comparison methods
+ // comparison methods
bool operator==(const self_type& right_hand_side)
{
bool result = false;
if (element_ && right_hand_side.element_)
- result = *element_ == *right_hand_side.element_;
+ result = *this->element_ == *right_hand_side.element_;
return result;
};
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;
+ };
+
+ bool operator<=(const self_type& right_hand_side)
+ {
+ return this->operator==(right_hand_side) | this->operator<(right_hand_side);
+ };
+
+ // data access
T operator* ()
{
~GenericStorageContainerTemplateImpl<T, DATA_STRUCTURE>()
{
- delete &data_structure_;
};
// capacity