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 <iterator>
  24 #include <memory>
  25 #include <new>      // for std::nothrow
  26
  27 namespace tj
  28 {
  29
  30   /* Abstract base class for the different data structures
  31    *
  32    * Defines the API they must implement. The API allows the Container and its
  33    * Iterator to call common methods to perform store, retrieve, and search operations
  34    */
  35
  36   // mnemonic alternatives to plain 'index' values
  37   enum position {
  38     BEGIN = 0,
  39     END = -1,
  40     TAIL = 0,
  41     HEAD = -1
  42   };
  43
  44   template <typename D>
  45   class AbstractDataStructure
  46   {
  47     protected:
  48     typedef AbstractDataStructure<D> self_type;
  49
  50     D* data_;
  51     size_t capacity_;
  52     size_t size_;
  53     size_t current_;
  54
  55     public:
  56
  57     AbstractDataStructure(size_t capacity = 0) : data_(nullptr), capacity_(capacity), size_(0), current_(0)
  58     {
  59       if (capacity_)
  60         data_ = new(std::nothrow) D[capacity_];
  61     };
  62
  63     virtual ~AbstractDataStructure()
  64     {
  65       if (data_ != nullptr)
  66         delete[] data_;
  67     };
  68
  69     /* API available to application
  70      *
  71      * Some methods are pure virtual making this an Abstract (base) class
  72      * Sub-classes must implement these methods and over-ride others to
  73      * provide the specific storage class functionality
  74      */
  75
  76     virtual size_t get_capacity() // available storage (in units of storage type)
  77     {
  78       return capacity_;
  79     };
  80
  81     virtual size_t get_size() // used storage (in units of storage type)
  82     {
  83       return size_;
  84     };
  85
  86     /* the concepts of first, last, next and previous may not have a useful meaning in
  87      * some storage classes e.g: 'previous' in a 1-way linked list (only has 'next').
  88      */
  89     virtual D* get_data()
  90     {
  91       return (data_ && size_ > 0) ? &data_[current_] : nullptr;
  92     };
  93
  94     virtual self_type* get_begin() = 0;
  95     virtual self_type* get_end() = 0;
  96     virtual self_type* get_next() = 0;
  97     virtual self_type* get_previous() = 0;
  98
  99     /*
 100      * @param data the item (of type S) to be stored
 101      * @param index position to insert; 0 is 'beginning', -1 is 'end'
 102      *
 103      * Depending on the data structure, values of index other than 0 or -1 may have no meaning and be ignored
 104      */
 105     virtual bool insert_at(D& data, long index = -1) = 0;
 106
 107     virtual bool insert(D& data)
 108     {
 109       return insert_at(data, TAIL);
 110     };
 111     virtual bool append(D& data)
 112     {
 113       return insert_at(data, HEAD);
 114     };
 115
 116     /* the remove operation can perform an optional erasure (delete) of the stored data.
 117      *
 118      * returns true if the operation succeeded
 119      */
 120
 121     // 'data' element at 'index' must satisfy equality
 122     virtual bool remove_at(D& data, long index = -1, bool erase = false) = 0; // element matching 'data' at 'index'
 123     virtual bool remove_at(long index = -1, bool erase = false) = 0; // any element at 'index'
 124     virtual bool remove_all(D& data, bool erase = false) = 0;        // all elements matching 'data'
 125
 126     /* the replace operation can perform an optional erasure (delete) of the current data element
 127      */
 128     virtual bool replace_at(D& data_in, D& data_out, long index = -1, bool erase = false) = 0; // element matching 'data_out' at 'index'
 129     virtual bool replace_at(D& data_in, long index = -1, bool erase = false) = 0; // any element at 'index'
 130     virtual bool replace_all(D& data_in, D& data_out, bool erase = false) = 0; // all elements matching 'data_out'
 131
 132
 133     /* Search for an element matching 'needle'. The stored type must have defined
 134      * operator<() and operator==() to allow the container to compare 'needle' with each stored element.
 135      *
 136      * If find() is called with last_found == nullptr it searches from the start of the container. If
 137      * last_found points to an element in the container the search continues from that element. The
 138      * implementation must guard against last_found not pointing to a valid object, or that object not
 139      * belonging to the container.
 140      *
 141      * returns a nullptr if there are no (more) matches
 142      */
 143     virtual D* find(D& needle, D* last_found = nullptr) = 0;
 144
 145     virtual bool operator==(const D& right_hand_side)
 146     {
 147       bool result = false;
 148       // TODO: implement
 149       return result;
 150     };
 151   };
 152
 153
 154   /* Specialised data structure implementing a Dynamic Array
 155    */
 156   template <typename AD>
 157   class DataStructure_ArrayDynamic : public AbstractDataStructure<AD>
 158   {
 159     typedef DataStructure_ArrayDynamic<AD> self_type;
 160
 161     size_t growth_;
 162
 163     public:
 164     DataStructure_ArrayDynamic<AD>(size_t capacity = 512) : AbstractDataStructure<AD>(capacity), growth_(512) {};
 165
 166     virtual self_type* get_begin()
 167     {
 168       self_type* result = nullptr;
 169
 170       if (this->size_ > 0) {
 171         this->current_ = 0;
 172         result = this;
 173       }
 174       return result;
 175     };
 176
 177     virtual self_type* get_end()
 178     {
 179       self_type* result = nullptr;
 180
 181       if (this->size_ > 0)
 182       {
 183         this->current_ = this->size_ - 1;
 184         result = this;
 185       }
 186       return result;
 187     };
 188
 189     virtual self_type* get_next()
 190     {
 191       self_type* result = nullptr;
 192
 193       if (this->size_ > 0)
 194       {
 195         if (this->current_ + 1 < this->size_)
 196         {
 197           ++this->current_;
 198           result = this;
 199         }
 200       }
 201
 202       return result;
 203     };
 204
 205     virtual self_type* get_previous()
 206     {
 207       self_type* result = nullptr;
 208
 209       if (this->size_ > 0)
 210       {
 211         if (this->current_ - 1 >= 0)
 212         {
 213           --this->current_;
 214           result = this;
 215         }
 216       }
 217
 218       return result;
 219     };
 220
 221     virtual bool insert_at(AD& data, long index = TAIL)
 222     {
 223       bool result = false;
 224
 225       if (this->data_ != nullptr)
 226       {
 227         if (index == TAIL)
 228           index = 0;
 229         else if (index == HEAD)
 230           index = this->size_;
 231
 232         if (this->capacity_ <= index)
 233           this->grow();
 234
 235         if (this->capacity_ > index)
 236         {
 237           this->data_[index] = data;
 238
 239           if (index >= this->size_)
 240             this->size_ = index + 1;
 241
 242           result = true;
 243         }
 244       }
 245
 246       return result;
 247     };
 248
 249     virtual bool remove_at(AD& data, long index = TAIL, bool erase = false)
 250     {
 251       bool result = false;
 252       // TODO: implement
 253       return result;
 254     };
 255
 256     virtual bool remove_at(long index = TAIL, bool erase = false)
 257     {
 258       bool result = false;
 259       // TODO: implement
 260       return result;
 261     };
 262
 263     virtual bool remove_all(AD& data, bool eraser = false)
 264     {
 265       bool result = false;
 266       // TODO: implement
 267       return result;
 268     };
 269
 270     virtual bool replace_at(AD& data_in, AD& data_out, long index = TAIL, bool erase = false)
 271     {
 272       bool result = false;
 273       // TODO: implement
 274       return result;
 275     };
 276
 277     virtual bool replace_at(AD& data_in, long index = TAIL, bool erase = false)
 278     {
 279       bool result = false;
 280       // TODO: implement
 281       return result;
 282     };
 283
 284     virtual bool replace_all(AD& data_in, AD& data_out, bool erase = false)
 285     {
 286       bool result = false;
 287       // TODO: implement
 288       return result;
 289     };
 290
 291     virtual AD* find(AD& needle, AD* last_found = nullptr)
 292     {
 293       AD* result = nullptr;
 294       // TODO: implement
 295       return result;
 296     };
 297
 298     virtual bool operator==(const self_type& right_hand_side)
 299     {
 300       bool result = false;
 301       // TODO: implement
 302       return result;
 303     };
 304
 305     bool grow()
 306     {
 307       bool result = false;
 308       AD* temp = new (std::nothrow) AD[this->capacity_ + this->growth_];
 309       if (temp != nullptr)
 310       {
 311         for (size_t index = 0; index < this->size_; ++index)
 312           temp[index] = this->data_[index];
 313
 314         delete[] this->data_;
 315         this->data_ = temp;
 316
 317         this->capacity_ += this->growth_;
 318         result = true;
 319       }
 320
 321       return result;
 322     };
 323
 324     // TODO: implement
 325   };
 326
 327   /* Specialised data structure implementing a 1-way Linked List
 328    */
 329   template <typename LLS>
 330   class DataStructure_LinkedListSingle : protected AbstractDataStructure<LLS>
 331   {
 332     // TODO: implement
 333   };
 334
 335   /* Specialised data structure implementing a 2-way Linked List
 336    */
 337   template <typename LLD>
 338   class DataStructure_LinkedListDouble : public DataStructure_LinkedListSingle<LLD>
 339   {
 340     // TODO: implement
 341   };
 342
 343   /* Specialised data structure implementing a Binary Search Tree
 344    */
 345   template <typename BST>
 346   class DataStructure_BinarySearchTree : protected AbstractDataStructure<BST>
 347   {
 348     // TODO: implement
 349   };
 350
 351 }; // end of namespace
 352
 353 #endif
 354