Scippy

SoPlex

Sequential object-oriented simPlex

idxset.h
Go to the documentation of this file.
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  */
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_
void add(int n)
appends n uninitialized indices.
Definition: idxset.h:158
int * idx
array of indices
Definition: idxset.h:74
Memory allocation routines.
int max() const
returns the maximal number of indices which can be stored in IdxSet.
Definition: idxset.h:138
IdxSet(int n, int imem[], int l=0)
constructor.
Definition: idxset.h:89
void clear()
removes all indices.
Definition: idxset.h:193
void add(const IdxSet &set)
appends all indices of set.
Definition: idxset.h:165
IdxSet()
default constructor.
Definition: idxset.h:100
void addIdx(int i)
appends index i.
Definition: idxset.h:174
bool isConsistent() const
consistency check.
Definition: idxset.cpp:126
bool freeArray
true iff idx should be freed inside of this object
Definition: idxset.h:75
int pos(int i) const
returns the position of index i.
Definition: idxset.cpp:41
virtual ~IdxSet()
destructor.
Definition: idxset.h:107
int size() const
returns the number of used indices.
Definition: idxset.h:133
int len
length of array idx
Definition: idxset.h:73
IdxSet & operator=(const IdxSet &set)
assignment operator.
Definition: idxset.cpp:80
Debugging, floating point type and parameter definitions.
Everything should be within this namespace.
int dim() const
returns the maximal index.
Definition: idxset.cpp:30
int index(int n) const
access n &#39;th index.
Definition: idxset.h:127
int num
number of used indices
Definition: idxset.h:72
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
Definition: idxset.h:65
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:121