1/* $Id: CoinPackedVectorBase.hpp 1448 2011-06-19 15:34:41Z stefan $ */
2// Copyright (C) 2000, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CoinPackedVectorBase_H
7#define CoinPackedVectorBase_H
8
9#include <set>
10#include <map>
11#include "CoinPragma.hpp"
12#include "CoinError.hpp"
13
14class CoinPackedVector;
15
16/** Abstract base class for various sparse vectors.
17
18 Since this class is abstract, no object of this type can be created. The
19 sole purpose of this class is to provide access to a <em>constant</em>
20 packed vector. All members of this class are const methods, they can't
21 change the object. */
22
23class CoinPackedVectorBase {
24
25public:
26 /**@name Virtual methods that the derived classes must provide */
27 //@{
28 /// Get length of indices and elements vectors
29 virtual int getNumElements() const = 0;
30 /// Get indices of elements
31 virtual const int * getIndices() const = 0;
32 /// Get element values
33 virtual const double * getElements() const = 0;
34 //@}
35
36 /**@name Methods related to whether duplicate-index checking is performed.
37
38 If the checking for duplicate indices is turned off, then
39 some CoinPackedVector methods may not work correctly if there
40 are duplicate indices.
41 Turning off the checking for duplicate indices may result in
42 better run time performance.
43 */
44 //@{
45 /** \brief Set to the argument value whether to test for duplicate indices
46 in the vector whenever they can occur.
47
48 Calling this method with \p test set to true will trigger an immediate
49 check for duplicate indices.
50 */
51 void setTestForDuplicateIndex(bool test) const;
52 /** \brief Set to the argument value whether to test for duplicate indices
53 in the vector whenever they can occur BUT we know that right
54 now the vector has no duplicate indices.
55
56 Calling this method with \p test set to true will <em>not</em> trigger
57 an immediate check for duplicate indices; instead, it's assumed that
58 the result of the test will be true.
59 */
60 void setTestForDuplicateIndexWhenTrue(bool test) const;
61 /** Returns true if the vector should be tested for duplicate indices when
62 they can occur. */
63 bool testForDuplicateIndex() const { return testForDuplicateIndex_; }
64 /// Just sets test stuff false without a try etc
65 inline void setTestsOff() const
66 { testForDuplicateIndex_=false; testedDuplicateIndex_=false;}
67 //@}
68
69 /**@name Methods for getting info on the packed vector as a full vector */
70 //@{
71 /** Get the vector as a dense vector. The argument specifies how long this
72 dense vector is. <br>
73 <strong>NOTE</strong>: The user needs to <code>delete[]</code> this
74 pointer after it's not needed anymore.
75 */
76 double * denseVector(int denseSize) const;
77 /** Access the i'th element of the full storage vector.
78 If the i'th is not stored, then zero is returned. The initial use of
79 this method has some computational and storage overhead associated with
80 it.<br>
81 <strong>NOTE</strong>: This is <em>very</em> expensive. It is probably
82 much better to use <code>denseVector()</code>.
83 */
84 double operator[](int i) const;
85 //@}
86
87 /**@name Index methods */
88 //@{
89 /// Get value of maximum index
90 int getMaxIndex() const;
91 /// Get value of minimum index
92 int getMinIndex() const;
93
94 /// Throw an exception if there are duplicate indices
95 void duplicateIndex(const char* methodName = nullptr,
96 const char * className = nullptr) const;
97
98 /** Return true if the i'th element of the full storage vector exists in
99 the packed storage vector.*/
100 bool isExistingIndex(int i) const;
101
102 /** Return the position of the i'th element of the full storage vector.
103 If index does not exist then -1 is returned */
104 int findIndex(int i) const;
105
106 //@}
107
108 /**@name Comparison operators on two packed vectors */
109 //@{
110 /** Equal. Returns true if vectors have same length and corresponding
111 element of each vector is equal. */
112 bool operator==(const CoinPackedVectorBase & rhs) const;
113 /// Not equal
114 bool operator!=(const CoinPackedVectorBase & rhs) const;
115
116#if 0
117 // LL: This should be implemented eventually. It is useful to have.
118 /** Lexicographic comparisons of two packed vectors. Returns
119 negative/0/positive depending on whether \c this is
120 smaller/equal.greater than \c rhs */
121 int lexCompare(const CoinPackedVectorBase& rhs);
122#endif
123
124 /** This method establishes an ordering on packed vectors. It is complete
125 ordering, but not the same as lexicographic ordering. However, it is
126 quick and dirty to compute and thus it is useful to keep packed vectors
127 in a heap when all we care is to quickly check whether a particular
128 vector is already in the heap or not. Returns negative/0/positive
129 depending on whether \c this is smaller/equal.greater than \c rhs. */
130 int compare(const CoinPackedVectorBase& rhs) const;
131
132 /** equivalent - If shallow packed vector A & B are equivalent, then they
133 are still equivalent no matter how they are sorted.
134 In this method the FloatEqual function operator can be specified. The
135 default equivalence test is that the entries are relatively equal.<br>
136 <strong>NOTE</strong>: This is a relatively expensive method as it
137 sorts the two shallow packed vectors.
138 */
139 template <class FloatEqual> bool
140 isEquivalent(const CoinPackedVectorBase& rhs, const FloatEqual& eq) const
141 {
142 if (getNumElements() != rhs.getNumElements())
143 return false;
144
145 duplicateIndex("equivalent", "CoinPackedVector");
146 rhs.duplicateIndex("equivalent", "CoinPackedVector");
147
148 std::map<int,double> mv;
149 const int * inds = getIndices();
150 const double * elems = getElements();
151 int i;
152 for ( i = getNumElements() - 1; i >= 0; --i) {
153 mv.insert(std::make_pair(inds[i], elems[i]));
154 }
155
156 std::map<int,double> mvRhs;
157 inds = rhs.getIndices();
158 elems = rhs.getElements();
159 for ( i = getNumElements() - 1; i >= 0; --i) {
160 mvRhs.insert(std::make_pair(inds[i], elems[i]));
161 }
162
163 std::map<int,double>::const_iterator mvI = mv.begin();
164 std::map<int,double>::const_iterator mvIlast = mv.end();
165 std::map<int,double>::const_iterator mvIrhs = mvRhs.begin();
166 while (mvI != mvIlast) {
167 if (mvI->first != mvIrhs->first || ! eq(mvI->second, mvIrhs->second))
168 return false;
169 ++mvI;
170 ++mvIrhs;
171 }
172 return true;
173 }
174
175 bool isEquivalent(const CoinPackedVectorBase& rhs) const;
176 //@}
177
178
179 /**@name Arithmetic operators. */
180 //@{
181 /// Create the dot product with a full vector
182 double dotProduct(const double* dense) const;
183
184 /// Return the 1-norm of the vector
185 double oneNorm() const;
186
187 /// Return the square of the 2-norm of the vector
188 double normSquare() const;
189
190 /// Return the 2-norm of the vector
191 double twoNorm() const;
192
193 /// Return the infinity-norm of the vector
194 double infNorm() const;
195
196 /// Sum elements of vector.
197 double sum() const;
198 //@}
199
200protected:
201
202 /**@name Constructors, destructor
203 <strong>NOTE</strong>: All constructors are protected. There's no need
204 to expose them, after all, this is an abstract class. */
205 //@{
206 /** Default constructor. */
207 CoinPackedVectorBase();
208
209public:
210 /** Destructor */
211 virtual ~CoinPackedVectorBase();
212 //@}
213
214private:
215 /**@name Disabled methods */
216 //@{
217 /** The copy constructor. <br>
218 This must be at least protected, but we make it private. The reason is
219 that when, say, a shallow packed vector is created, first the
220 underlying class, it this one is constructed. However, at that point we
221 don't know how much of the data members of this class we need to copy
222 over. Therefore the copy constructor is not used. */
223 CoinPackedVectorBase(const CoinPackedVectorBase&);
224 /** This class provides <em>const</em> access to packed vectors, so there's
225 no need to provide an assignment operator. */
226 CoinPackedVectorBase& operator=(const CoinPackedVectorBase&);
227 //@}
228
229protected:
230
231 /**@name Protected methods */
232 //@{
233 /// Find Maximum and Minimum Indices
234 void findMaxMinIndices() const;
235
236 /// Return indexSetPtr_ (create it if necessary).
237 std::set<int> * indexSet(const char* methodName = nullptr,
238 const char * className = nullptr) const;
239
240 /// Delete the indexSet
241 void clearIndexSet() const;
242 void clearBase() const;
243 void copyMaxMinIndex(const CoinPackedVectorBase & x) const {
244 maxIndex_ = x.maxIndex_;
245 minIndex_ = x.minIndex_;
246 }
247 //@}
248
249private:
250 /**@name Protected member data */
251 //@{
252 /// Contains max index value or -infinity
253 mutable int maxIndex_;
254 /// Contains minimum index value or infinity
255 mutable int minIndex_;
256 /** Store the indices in a set. This set is only created if it is needed.
257 Its primary use is testing for duplicate indices.
258 */
259 mutable std::set<int> * indexSetPtr_;
260 /** True if the vector should be tested for duplicate indices when they can
261 occur. */
262 mutable bool testForDuplicateIndex_;
263 /** True if the vector has already been tested for duplicate indices. Most
264 of the operations in CoinPackedVector preserves this flag. */
265 mutable bool testedDuplicateIndex_;
266 //@}
267};
268
269#endif
270