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