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