DataStructures.hpp

   1 /*
   2  * Implementation of Data Structures for GenericStorageContainerTemplateImpl
   3  * Copyright (c) 2014 TJ <hacker@iam.tj>
   4  *
   5  *    This program is free software: you can redistribute it and/or modify
   6  *    it under the terms of the GNU General Public License as published by
   7  *    the Free Software Foundation, either version 3 of the License.
   8  *
   9  *    This program is distributed in the hope that it will be useful,
  10  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *    GNU General Public License for more details.
  13  *
  14  *   You should have received a copy of the GNU General Public License
  15  *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * see ./COPYRIGHT or http://www.gnu.org/licenses/gpl-3.0.html
  18  */
  19
  20 #ifndef _DATASTRUCTURE_HPP_
  21 #define _DATASTRUCTURE_HPP_
  22
  23 #include <memory>
  24 #include <new>      // for std::nothrow
  25
  26 namespace tj
  27 {
  28
  29   /* Abstract base class for the different data structures
  30    *
  31    * Defines the API they must implement. The API allows the Container and its
  32    * Iterator to call common methods to perform store, retrieve, and search operations
  33    */
  34
  35   template <typename D>
  36   class AbstractDataStructure
  37   {
  38     typedef AbstractDataStructure<D> self_type;
  39
  40     protected:
  41
  42     // shared pointer wraps actual data so that iterator instances can safely reference the same data
  43     std::shared_ptr<D> data_;
  44     size_t capacity_;  // storage allocated (in units of data type)
  45     size_t size_;      // storage used (in units of data type)
  46     size_t current_;   // index of active element (may not make sense for some data structures but is needed for API)
  47
  48     public:
  49
  50     /* use descriptive symbols rather than booleans for method parameters */
  51
  52     // alternatives to numeric 'index' values
  53     enum position {
  54       BEGIN = 0,
  55       END = -1, // newest
  56       TAIL = 0,
  57       HEAD = -1 // newest
  58     };
  59
  60     // element erasure choices that evaluate to boolean states
  61     enum erasure {
  62       NO_ERASE, // false
  63       ERASE     // true
  64     };
  65
  66     AbstractDataStructure(size_t capacity = 0) :
  67       // use a lambda as the shared_ptr array deleter since the default deleter does not handle array deletion
  68       data_(new D[capacity_], []( D* p) {delete[] p; } ),
  69       capacity_(capacity),
  70       size_(0),
  71       current_(0)
  72     {
  73       if (capacity_)
  74         data_.reset(new(std::nothrow) D[capacity_]);
  75     };
  76
  77     virtual ~AbstractDataStructure() {};
  78
  79
  80     /* API available to caller
  81      *
  82      * Some methods are pure virtual making this an Abstract (base) class
  83      * Sub-classes must implement these methods and over-ride others to
  84      * provide the specific storage class functionality
  85      */
  86
  87     virtual size_t get_capacity() // storage allocated (in units of data type)
  88     {
  89       return capacity_;
  90     };
  91
  92     virtual size_t get_size() // storage used (in units of data type)
  93     {
  94       return size_;
  95     };
  96
  97     /* the concepts of first, last, next and previous may not have a useful meaning in
  98      * some data structures e.g: 'previous' in a 1-way linked list (only has 'next').
  99      */
 100     virtual D* get_data()
 101     {
 102       return (data_.get() && size_ > 0) ? &data_.get()[current_] : nullptr;
 103     };
 104
 105     virtual self_type* get_begin() = 0;
 106     virtual self_type* get_end() = 0;
 107     virtual self_type* get_next() = 0;
 108     virtual self_type* get_previous() = 0;
 109
 110     /*
 111      * @param data the item (of type S) to be stored
 112      * @param index position to insert; 0 is 'beginning', -1 is 'end'
 113      *
 114      * Depending on the data structure, values of index other than 0 or -1 may have no meaning and be ignored
 115      */
 116     virtual bool insert_at(D& data, long index = HEAD) = 0;
 117
 118     virtual bool insert(D& data)
 119     {
 120       return this->insert_at(data, TAIL);
 121     };
 122     virtual bool append(D& data)
 123     {
 124       return this->insert_at(data);
 125     };
 126
 127     /* the remove operation can perform an optional erasure (delete) of the stored data.
 128      *
 129      * returns true if the operation succeeded
 130      */
 131
 132     // 'data' element at 'index' must satisfy equality
 133     virtual bool remove_at(D& data, long index = HEAD, bool erase = NO_ERASE) = 0; // element matching 'data' at 'index'
 134     virtual bool remove_at(long index = HEAD, bool erase = NO_ERASE) = 0; // any element at 'index'
 135     virtual bool remove_all(D& data, bool erase = NO_ERASE) = 0;        // all elements matching 'data'
 136
 137     /* the replace operation can perform an optional erasure (delete) of the current data element
 138      */
 139     virtual bool replace_at(D& data_in, D& data_out, long index = HEAD, bool erase = NO_ERASE) = 0; // element matching 'data_out' at 'index'
 140     virtual bool replace_at(D& data_in, long index = HEAD, bool erase = NO_ERASE) = 0; // any element at 'index'
 141     virtual bool replace_all(D& data_in, D& data_out, bool erase = NO_ERASE) = 0; // all elements matching 'data_out'
 142
 143
 144     /* Search for an element matching 'needle'. The stored type must have defined
 145      * operator<() and operator==() to allow the container to compare 'needle' with each stored element.
 146      *
 147      * If find() is called with last_found == nullptr it searches from the start of the container. If
 148      * last_found points to an element in the container the search continues from that element. The
 149      * implementation must guard against last_found not pointing to a valid object, or that object not
 150      * belonging to the container.
 151      *
 152      * returns a nullptr if there are no (more) matches
 153      */
 154     virtual D* find(D& needle, D* last_found = nullptr) = 0;
 155
 156     // comparison methods
 157     virtual bool operator==(const self_type& right_hand_side)
 158     {
 159       bool result = false;
 160       if (this->data_.get() && right_hand_side.data_.get())
 161         result = this->current_ == right_hand_side.current_;
 162
 163       return result;
 164     };
 165     virtual bool operator!=(const self_type& right_hand_side)
 166     {
 167       return !this->operator==(right_hand_side);
 168     };
 169     virtual bool operator< (const self_type& right_hand_side)
 170     {
 171       bool result = false;
 172       if (this->data_.get() && right_hand_side.data_.get())
 173         result = this->current_ < right_hand_side.current_;
 174
 175       return result;
 176     };
 177     virtual bool operator<=(const self_type& right_hand_side)
 178     {
 179       return this->operator==(right_hand_side) | this->operator<(right_hand_side);
 180     };
 181
 182   };
 183
 184
 185   /* Specialised data structure implementing a Dynamic Array
 186    */
 187   template <typename AD>
 188   class DataStructure_ArrayDynamic : public AbstractDataStructure<AD>
 189   {
 190     typedef DataStructure_ArrayDynamic<AD> self_type;
 191     typedef AbstractDataStructure<AD> BASE_CLASS; // alias for easier reading of enums
 192
 193     size_t growth_;
 194
 195     public:
 196     DataStructure_ArrayDynamic<AD>(size_t capacity = 512) : AbstractDataStructure<AD>(capacity), growth_(512) {};
 197
 198     /* Copy constructor that can do deep and shallow copies.
 199      * Shallow copies are efficient for use by iterators where the only unique variable is
 200      * the 'current_' index - the object can share a pointer to the data.
 201      */
 202     DataStructure_ArrayDynamic<AD>(const self_type& copy, bool shallow = false)
 203     {
 204       this->data_ = copy.data_;
 205       this->capacity_ = copy.capacity_;
 206       this->size_ = copy.size_;
 207       this->current_ = copy.current_;
 208       this->growth_ = copy.growth_;
 209       if (!shallow)
 210       {
 211         this->data_.reset(new AD [this->capacity_]);
 212         for (size_t i = 0; i < this->capacity_; ++i)
 213             this->data_.get()[i] = copy.data_.get()[i];
 214       }
 215     }
 216
 217     virtual self_type* get_begin()
 218     {
 219       self_type* result = nullptr;
 220
 221       if (this->size_ > 0) {
 222         // TODO: make a shallow copy (share the array to avoid an expensive copy)
 223         result = new self_type(*this, true);
 224         result->current_ = 0;
 225       }
 226       return result;
 227     };
 228
 229     virtual self_type* get_end()
 230     {
 231       self_type* result = nullptr;
 232
 233       if (this->size_ > 0)
 234       {
 235         result = new self_type(*this, true);
 236         // 1 beyond last element; used by iterator loops to detect when to break
 237         result->current_ = result->size_;
 238       }
 239       return result;
 240     };
 241
 242     virtual self_type* get_next()
 243     {
 244       self_type* result = nullptr;
 245
 246       if (this->size_ > 0)
 247       {
 248         /* if (this->current_ + 1 < this->size_)
 249         { */
 250           result = new self_type(*this, true);
 251           ++result->current_;
 252         // }
 253       }
 254
 255       return result;
 256     };
 257
 258     virtual self_type* get_previous()
 259     {
 260       self_type* result = nullptr;
 261
 262       if (this->size_ > 0)
 263       {
 264         if (this->current_ - 1 >= 0)
 265         {
 266           result = new self_type(*this, true);
 267           --result->current_;
 268         }
 269       }
 270
 271       return result;
 272     };
 273
 274     virtual bool insert_at(AD& data, long index = BASE_CLASS::HEAD)
 275     {
 276       bool result = false;
 277
 278       if (this->data_ != nullptr)
 279       {
 280         if (index == BASE_CLASS::TAIL)
 281           index = 0;
 282         else if (index == BASE_CLASS::HEAD)
 283           index = this->size_;
 284
 285         if (this->capacity_ <= index)
 286           this->grow();
 287
 288         if (this->capacity_ > index)
 289         {
 290           this->data_.get()[index] = data;
 291
 292           if (index >= this->size_)
 293             this->size_ = index + 1;
 294
 295           result = true;
 296         }
 297       }
 298
 299       return result;
 300     };
 301
 302     virtual bool remove_at(AD& data, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
 303     {
 304       bool result = false;
 305       // TODO: implement
 306       return result;
 307     };
 308
 309     virtual bool remove_at(long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
 310     {
 311       bool result = false;
 312       // TODO: implement
 313       return result;
 314     };
 315
 316     virtual bool remove_all(AD& data, bool eraser = BASE_CLASS::NO_ERASE)
 317     {
 318       bool result = false;
 319       // TODO: implement
 320       return result;
 321     };
 322
 323     virtual bool replace_at(AD& data_in, AD& data_out, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
 324     {
 325       bool result = false;
 326       // TODO: implement
 327       return result;
 328     };
 329
 330     virtual bool replace_at(AD& data_in, long index = BASE_CLASS::TAIL, bool erase = BASE_CLASS::NO_ERASE)
 331     {
 332       bool result = false;
 333       // TODO: implement
 334       return result;
 335     };
 336
 337     virtual bool replace_all(AD& data_in, AD& data_out, bool erase = BASE_CLASS::NO_ERASE)
 338     {
 339       bool result = false;
 340       // TODO: implement
 341       return result;
 342     };
 343
 344     virtual AD* find(AD& needle, AD* last_found = nullptr)
 345     {
 346       AD* result = nullptr;
 347       // TODO: implement
 348       return result;
 349     };
 350
 351     // comparisons require both sides to have the same array pointer
 352     virtual bool operator==(const self_type& right_hand_side)
 353     {
 354       bool result = false;
 355
 356       if (this->data_.get() == right_hand_side.data_.get())
 357         result = this->current_ == right_hand_side.current_;
 358
 359       return result;
 360     };
 361
 362     virtual bool operator<(const self_type& right_hand_side)
 363     {
 364       bool result = false;
 365
 366       if (this->data_.get() == right_hand_side.data_.get())
 367         result = this->current_ < right_hand_side.current_;
 368
 369       return result;
 370     };
 371
 372     bool grow()
 373     {
 374       bool result = false;
 375       AD* temp = new (std::nothrow) AD[this->capacity_ + this->growth_];
 376       if (temp != nullptr)
 377       {
 378         for (size_t index = 0; index < this->size_; ++index)
 379           temp[index] = this->data_.get()[index];
 380
 381         this->data_.reset(temp);
 382
 383         this->capacity_ += this->growth_;
 384         result = true;
 385       }
 386
 387       return result;
 388     };
 389
 390     // TODO: implement
 391   };
 392
 393   /* Specialised data structure implementing a 1-way Linked List
 394    */
 395   template <typename LLS>
 396   class DataStructure_LinkedListSingle : protected AbstractDataStructure<LLS>
 397   {
 398     // TODO: implement
 399   };
 400
 401   /* Specialised data structure implementing a 2-way Linked List
 402    */
 403   template <typename LLD>
 404   class DataStructure_LinkedListDouble : public DataStructure_LinkedListSingle<LLD>
 405   {
 406     // TODO: implement
 407   };
 408
 409   /* Specialised data structure implementing a Binary Search Tree
 410    */
 411   template <typename BST>
 412   class DataStructure_BinarySearchTree : protected AbstractDataStructure<BST>
 413   {
 414     // TODO: implement
 415   };
 416
 417 }; // end of namespace
 418
 419 #endif
 420