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
  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     size_t capacity_;
  39     size_t size_;
  40
  41     public:
  42     AbstractDataStructure() {};
  43     virtual ~AbstractDataStructure() {};
  44
  45     /* API available to application
  46      *
  47      * Some methods are pure virtual making this an Abstract (base) class
  48      * Sub-classes must implement these methods and over-ride others to
  49      * provide the specific storage class functionality
  50      */
  51
  52     virtual size_t get_capacity() // available storage (in units of storage type)
  53     {
  54       return capacity_;
  55     };
  56
  57     virtual size_t get_size() // used storage (in units of storage type)
  58     {
  59       return size_;
  60     };
  61
  62     /* the concepts of first, last, next and previous may not have a useful meaning in
  63      * some storage classes e.g: 'previous' in a 1-way linked list (only has 'next').
  64      */
  65     virtual D* get_data() = 0;
  66     virtual D& get_first() = 0;
  67     virtual D& get_last() = 0;
  68     virtual D& get_next() = 0;
  69     virtual D& get_previous() = 0;
  70
  71     /*
  72      * @param data the item (of type S) to be stored
  73      * @param index position to insert; 0 is 'beginning', -1 is 'end'
  74      *
  75      * Depending on the data structure, values of index other than 0 or -1 may have no meaning and be ignored
  76      */
  77     virtual bool insert_at(D& data, long index = -1) = 0;
  78
  79     virtual bool insert(D& data)
  80     {
  81       return insert_at(data, 0);
  82     };
  83     virtual bool append(D& data)
  84     {
  85       return insert_at(data, -1);
  86     };
  87
  88     /* the remove operation can perform an optional erasure (delete) of the stored data.
  89      *
  90      * returns true if the operation succeeded
  91      */
  92
  93     // 'data' element at 'index' must satisfy equality
  94     virtual bool remove_at(D& data, long index = -1, bool erase = false) = 0; // element matching 'data' at 'index'
  95     virtual bool remove_at(long index = -1, bool erase = false) = 0; // any element at 'index'
  96     virtual bool remove_all(D& data, bool erase = false) = 0;        // all elements matching 'data'
  97
  98     /* the replace operation can perform an optional erasure (delete) of the current data element
  99      */
 100     virtual bool replace_at(D& data_in, D& data_out, long index = -1, bool erase = false) = 0; // element matching 'data_out' at 'index'
 101     virtual bool replace_at(D& data_in, long index = -1, bool erase = false) = 0; // any element at 'index'
 102     virtual bool replace_all(D& data_in, D& data_out, bool erase = false) = 0; // all elements matching 'data_out'
 103
 104
 105     /* Search for an element matching 'needle'. The stored type must have defined
 106      * operator<() and operator==() to allow the container to compare 'needle' with each stored element.
 107      *
 108      * If find() is called with last_found == nullptr it searches from the start of the container. If
 109      * last_found points to an element in the container the search continues from that element. The
 110      * implementation must guard against last_found not pointing to a valid object, or that object not
 111      * belonging to the container.
 112      *
 113      * returns a nullptr if there are no (more) matches
 114      */
 115     virtual D* find(D& needle, D* last_found = nullptr) = 0;
 116
 117     // mnemonic alternatives to plain 'index' values
 118     enum position {
 119       BEGIN = 0,
 120       END = -1,
 121       HEAD = 0,
 122       TAIL = -1
 123     };
 124   };
 125
 126
 127   /* Specialised data structure implementing a Dynamic Array
 128    */
 129   template <typename AD>
 130   class DataStructure_ArrayDynamic : AbstractDataStructure<AD>
 131   {
 132     // TODO: implement
 133   };
 134
 135   /* Specialised data structure implementing a 1-way Linked List
 136    */
 137   template <typename LLS>
 138   class DataStructure_LinkedListSingle : AbstractDataStructure<LLS>
 139   {
 140     // TODO: implement
 141   };
 142
 143   /* Specialised data structure implementing a 2-way Linked List
 144    */
 145   template <typename LLD>
 146   class DataStructure_LinkedListDouble : DataStructure_LinkedListSingle<LLD>
 147   {
 148     // TODO: implement
 149   };
 150
 151   /* Specialised data structure implementing a Binary Search Tree
 152    */
 153   template <typename BST>
 154   class DataStructure_BinarySearchTree : AbstractDataStructure<BST>
 155   {
 156     // TODO: implement
 157   };
 158
 159 }; // end of namespace
 160
 161 #endif
 162