From: TJ Date: Mon, 13 Apr 2015 23:30:24 +0000 (+0100) Subject: ArrayDynamic: Partial implementation X-Git-Url: https://iam.tj/gitweb/gitweb.cgi?p=GenericStorageContainerTemplate.git;a=commitdiff_plain;h=f0fb0e2a3b1deedf30ceb5d4c6694f2a7dcba11d ArrayDynamic: Partial implementation --- diff --git a/DataStructures.hpp b/DataStructures.hpp index d8283a5..83cc2ed 100644 --- a/DataStructures.hpp +++ b/DataStructures.hpp @@ -20,8 +20,9 @@ #ifndef _DATASTRUCTURE_HPP_ #define _DATASTRUCTURE_HPP_ -#include +// #include #include +#include // for std::nothrow namespace tj { @@ -32,15 +33,38 @@ 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 class AbstractDataStructure { + protected: + typedef AbstractDataStructure 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 * @@ -62,11 +86,15 @@ namespace tj /* 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 @@ -78,11 +106,11 @@ namespace tj 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. @@ -114,12 +142,11 @@ namespace tj */ 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; }; }; @@ -127,15 +154,180 @@ namespace tj /* Specialised data structure implementing a Dynamic Array */ template - class DataStructure_ArrayDynamic : AbstractDataStructure + class DataStructure_ArrayDynamic : public AbstractDataStructure { + typedef DataStructure_ArrayDynamic self_type; + + size_t growth_; + + public: + DataStructure_ArrayDynamic(size_t capacity = 512) : AbstractDataStructure(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 - class DataStructure_LinkedListSingle : AbstractDataStructure + class DataStructure_LinkedListSingle : protected AbstractDataStructure { // TODO: implement }; @@ -143,7 +335,7 @@ namespace tj /* Specialised data structure implementing a 2-way Linked List */ template - class DataStructure_LinkedListDouble : DataStructure_LinkedListSingle + class DataStructure_LinkedListDouble : public DataStructure_LinkedListSingle { // TODO: implement }; @@ -151,7 +343,7 @@ namespace tj /* Specialised data structure implementing a Binary Search Tree */ template - class DataStructure_BinarySearchTree : AbstractDataStructure + class DataStructure_BinarySearchTree : protected AbstractDataStructure { // TODO: implement }; diff --git a/GenericStorageContainerTemplateImpl.hpp b/GenericStorageContainerTemplateImpl.hpp index e75fc00..e84b99a 100644 --- a/GenericStorageContainerTemplateImpl.hpp +++ b/GenericStorageContainerTemplateImpl.hpp @@ -1,5 +1,5 @@ /* - * 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 * * This program is free software: you can redistribute it and/or modify @@ -17,8 +17,8 @@ * 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 @@ -50,16 +50,6 @@ namespace tj public: - GenericStorageContainerTemplateImpl() {}; - GenericStorageContainerTemplateImpl(const GenericStorageContainerTemplateImpl& 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 @@ -77,12 +67,12 @@ namespace tj typedef std::bidirectional_iterator_tag iterator_category; typedef int difference_type; - AbstractDataStructure& element_; + DATA_STRUCTURE* element_; public: iterator () {}; - iterator (AbstractDataStructure& element) : element_(element) {}; + iterator (DATA_STRUCTURE* element) : element_(element) {}; iterator (const iterator& copy) : element_(copy.element_) {}; // copy constructor // ForwardIterator methods @@ -90,64 +80,148 @@ namespace tj // 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* 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* 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 operator->() { - return &element_.get_data(); - } + return &element_->get_data(); + }; // allow const and non-const iterator copy-contructors access to private members friend class iterator; }; // end of Iterator - // use these handy short-cuts in application code - typedef iterator _const_iterator; - typedef iterator _iterator; + // use these handy short-cuts in application code + typedef iterator _const_iterator; + typedef iterator _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 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 + iterator begin() + { + return iterator(data_structure_.get_begin()); + }; + + template + iterator end() + { + return iterator(data_structure_.get_end()); + }; + + // object life-cycle + GenericStorageContainerTemplateImpl () {}; + GenericStorageContainerTemplateImpl (const GenericStorageContainerTemplateImpl& copy) + { + // TODO: implement copy constructor + }; + + ~GenericStorageContainerTemplateImpl() + { + 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 diff --git a/GenericStorageContainerTest.cpp b/GenericStorageContainerTest.cpp index b697408..65f220c 100644 --- a/GenericStorageContainerTest.cpp +++ b/GenericStorageContainerTest.cpp @@ -35,13 +35,16 @@ main (int argc, char **argv, char **env) 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; }