1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file idxset.h 26 * @brief Set of indices. 27 */ 28 #ifndef _IDXSET_H_ 29 #define _IDXSET_H_ 30 31 #include "soplex/spxdefines.h" 32 #include "soplex/spxalloc.h" 33 #include <assert.h> 34 35 namespace soplex 36 { 37 /**@brief Set of indices. 38 @ingroup Elementary 39 40 Class IdxSet provides a set of indices. At construction it must be given 41 an array of int where to store the indice and its length. The array will 42 from then on be managed by the IdxSet. 43 44 Indices are implicitely numbered from 0 thru size()-1. They can be 45 accessed (and altered) via method index() with the desired index number as 46 argument. Range checking is performed in the debug version. 47 48 Indices may be added or removed from the set, by calling add() or 49 remove() methods, respectively. However, no IdxSet can hold more then 50 max() indices, i.e. the number given at the constructor. 51 52 When removing indices, the remaining ones are renumbered. However, all 53 indices before the first removed index keep their number unchanged. 54 55 The internal structure of an IdxSet consists of an array #idx storing the 56 indices, its length len, and the actually used number of indices #num. 57 The class IdxSet doesn't allocate memory for the #idx array. Instead, the 58 user has to provide an adequate buffer to the constructor. 59 60 An IdxSet cannot be extended to fit more than max() elements. If 61 necessary, the user must explicitely provide the IdxSet with a 62 suitable memory. Alternatively, one can use \ref DIdxSet "DIdxSets" 63 which provide the required memory managemant. 64 */ 65 class IdxSet 66 { 67 protected: 68 69 //--------------------------------------- 70 /**@name Data */ 71 ///@{ 72 int num; ///< number of used indices 73 int len; ///< length of array \ref soplex::IdxSet::idx "idx" 74 int* idx; ///< array of indices 75 bool freeArray; ///< true iff \ref soplex::IdxSet::idx "idx" should be freed inside of this object 76 ///@} 77 78 public: 79 80 //--------------------------------------- 81 /**@name Construction / destruction */ 82 ///@{ 83 /// constructor. 84 /** The constructur receives the index memory \p imem to use for saving 85 its indices. This must be large enough to fit \p n indices. \p l can 86 be given to construct an #IdxSet initialized to the \p l first 87 indices in \p imem. 88 */ 89 IdxSet(int n, int imem[], int l = 0) 90 : num(l), len(n), idx(imem), freeArray(false) 91 { 92 assert(isConsistent()); 93 } 94 95 /// default constructor. 96 /** The default constructor creates an index set with an empty index 97 space. You cannot store any indices in an #IdxSet created with 98 the default constructor. 99 */ 100 IdxSet() 101 : num(0), len(0), idx(0), freeArray(false) 102 { 103 assert(isConsistent()); 104 } 105 106 /// destructor. 107 virtual ~IdxSet() 108 { 109 if(freeArray) 110 spx_free(idx); 111 } 112 113 /// assignment operator. 114 /** The assignment operator copies all nonzeros of the right handside 115 #IdxSet to the left one. This implies, that the latter must have 116 enough index memory. 117 */ 118 IdxSet& operator=(const IdxSet& set); 119 /// copy constructor. 120 IdxSet(const IdxSet&); 121 ///@} 122 123 //--------------------------------------- 124 /**@name Access */ 125 ///@{ 126 /// access \p n 'th index. 127 int index(int n) const 128 { 129 assert(n >= 0 && n < size() && idx != 0); 130 return idx[n]; 131 } 132 /// returns the number of used indices. 133 int size() const 134 { 135 return num; 136 } 137 /// returns the maximal number of indices which can be stored in IdxSet. 138 int max() const 139 { 140 return len; 141 } 142 143 /// returns the maximal index. 144 int dim() const; 145 146 /// returns the position of index \p i. 147 /** Finds the position of the first index \p i in the #IdxSet. If no index \p i is 148 available in the #IdxSet, -1 is returned. Otherwise, 149 index(pos(\p i)) == \p i holds. 150 */ 151 int pos(int i) const; 152 ///@} 153 154 //--------------------------------------- 155 /**@name Modification */ 156 ///@{ 157 /// appends \p n uninitialized indices. 158 void add(int n) 159 { 160 assert(n >= 0 && n + size() <= max()); 161 num += n; 162 } 163 164 /// appends all indices of \p set. 165 void add(const IdxSet& set) 166 { 167 add(set.size(), set.idx); 168 } 169 170 /// appends \p n indices in \p i. 171 void add(int n, const int i[]); 172 173 /// appends index \p i. 174 void addIdx(int i) 175 { 176 assert(size() < max()); 177 idx[num++] = i; 178 } 179 /// removes indices at position numbers \p n through \p m. 180 void remove(int n, int m); 181 182 /// removes \p n 'th index. 183 void remove(int n) 184 { 185 // /**@todo Shouldn't this be an assert instead of an if (see add()) */ 186 // if (n < size() && n >= 0) 187 // idx[n] = idx[--num]; 188 assert(n >= 0 && n < size()); 189 idx[n] = idx[--num]; 190 } 191 192 /// removes all indices. 193 void clear() 194 { 195 num = 0; 196 } 197 ///@} 198 199 //--------------------------------------- 200 /**@name Consistency check */ 201 ///@{ 202 /// consistency check. 203 bool isConsistent() const; 204 ///@} 205 }; 206 207 } // namespace soplex 208 #endif // _IDXSET_H_ 209