1/* $Id: CoinPackedVector.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 CoinPackedVector_H
7#define CoinPackedVector_H
8
9#include <map>
10
11#include "CoinPragma.hpp"
12#include "CoinPackedVectorBase.hpp"
13#include "CoinSort.hpp"
14
15#ifdef COIN_FAST_CODE
16#ifndef COIN_NOTEST_DUPLICATE
17#define COIN_NOTEST_DUPLICATE
18#endif
19#endif
20
21#ifndef COIN_NOTEST_DUPLICATE
22#define COIN_DEFAULT_VALUE_FOR_DUPLICATE true
23#else
24#define COIN_DEFAULT_VALUE_FOR_DUPLICATE false
25#endif
26/** Sparse Vector
27
28Stores vector of indices and associated element values.
29Supports sorting of vector while maintaining the original indices.
30
31Here is a sample usage:
32@verbatim
33 const int ne = 4;
34 int inx[ne] = { 1, 4, 0, 2 }
35 double el[ne] = { 10., 40., 1., 50. }
36
37 // Create vector and set its value
38 CoinPackedVector r(ne,inx,el);
39
40 // access each index and element
41 assert( r.indices ()[0]== 1 );
42 assert( r.elements()[0]==10. );
43 assert( r.indices ()[1]== 4 );
44 assert( r.elements()[1]==40. );
45 assert( r.indices ()[2]== 0 );
46 assert( r.elements()[2]== 1. );
47 assert( r.indices ()[3]== 2 );
48 assert( r.elements()[3]==50. );
49
50 // access original position of index
51 assert( r.originalPosition()[0]==0 );
52 assert( r.originalPosition()[1]==1 );
53 assert( r.originalPosition()[2]==2 );
54 assert( r.originalPosition()[3]==3 );
55
56 // access as a full storage vector
57 assert( r[ 0]==1. );
58 assert( r[ 1]==10.);
59 assert( r[ 2]==50.);
60 assert( r[ 3]==0. );
61 assert( r[ 4]==40.);
62
63 // sort Elements in increasing order
64 r.sortIncrElement();
65
66 // access each index and element
67 assert( r.indices ()[0]== 0 );
68 assert( r.elements()[0]== 1. );
69 assert( r.indices ()[1]== 1 );
70 assert( r.elements()[1]==10. );
71 assert( r.indices ()[2]== 4 );
72 assert( r.elements()[2]==40. );
73 assert( r.indices ()[3]== 2 );
74 assert( r.elements()[3]==50. );
75
76 // access original position of index
77 assert( r.originalPosition()[0]==2 );
78 assert( r.originalPosition()[1]==0 );
79 assert( r.originalPosition()[2]==1 );
80 assert( r.originalPosition()[3]==3 );
81
82 // access as a full storage vector
83 assert( r[ 0]==1. );
84 assert( r[ 1]==10.);
85 assert( r[ 2]==50.);
86 assert( r[ 3]==0. );
87 assert( r[ 4]==40.);
88
89 // Restore orignal sort order
90 r.sortOriginalOrder();
91
92 assert( r.indices ()[0]== 1 );
93 assert( r.elements()[0]==10. );
94 assert( r.indices ()[1]== 4 );
95 assert( r.elements()[1]==40. );
96 assert( r.indices ()[2]== 0 );
97 assert( r.elements()[2]== 1. );
98 assert( r.indices ()[3]== 2 );
99 assert( r.elements()[3]==50. );
100
101 // Tests for equality and equivalence
102 CoinPackedVector r1;
103 r1=r;
104 assert( r==r1 );
105 assert( r.equivalent(r1) );
106 r.sortIncrElement();
107 assert( r!=r1 );
108 assert( r.equivalent(r1) );
109
110 // Add packed vectors.
111 // Similarly for subtraction, multiplication,
112 // and division.
113 CoinPackedVector add = r + r1;
114 assert( add[0] == 1.+ 1. );
115 assert( add[1] == 10.+10. );
116 assert( add[2] == 50.+50. );
117 assert( add[3] == 0.+ 0. );
118 assert( add[4] == 40.+40. );
119
120 assert( r.sum() == 10.+40.+1.+50. );
121@endverbatim
122*/
123class CoinPackedVector : public CoinPackedVectorBase {
124 friend void CoinPackedVectorUnitTest();
125
126public:
127 /**@name Get methods. */
128 //@{
129 /// Get the size
130 virtual int getNumElements() const override { return nElements_; }
131 /// Get indices of elements
132 virtual const int * getIndices() const override { return indices_; }
133 /// Get element values
134 virtual const double * getElements() const override { return elements_; }
135 /// Get indices of elements
136 int * getIndices() { return indices_; }
137 /// Get element values
138 double * getElements() { return elements_; }
139 /** Get pointer to int * vector of original postions.
140 If the packed vector has not been sorted then this
141 function returns the vector: 0, 1, 2, ..., size()-1. */
142 const int * getOriginalPosition() const { return origIndices_; }
143 //@}
144
145 //-------------------------------------------------------------------
146 // Set indices and elements
147 //-------------------------------------------------------------------
148 /**@name Set methods */
149 //@{
150 /// Reset the vector (as if were just created an empty vector)
151 void clear();
152 /** Assignment operator. <br>
153 <strong>NOTE</strong>: This operator keeps the current
154 <code>testForDuplicateIndex</code> setting, and affter copying the data
155 it acts accordingly. */
156 CoinPackedVector & operator=(const CoinPackedVector &);
157 /** Assignment operator from a CoinPackedVectorBase. <br>
158 <strong>NOTE</strong>: This operator keeps the current
159 <code>testForDuplicateIndex</code> setting, and affter copying the data
160 it acts accordingly. */
161 CoinPackedVector & operator=(const CoinPackedVectorBase & rhs);
162
163 /** Assign the ownership of the arguments to this vector.
164 Size is the length of both the indices and elements vectors.
165 The indices and elements vectors are copied into this class instance's
166 member data. The last argument indicates whether this vector will have
167 to be tested for duplicate indices.
168 */
169 void assignVector(int size, int*& inds, double*& elems,
170 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
171
172 /** Set vector size, indices, and elements.
173 Size is the length of both the indices and elements vectors.
174 The indices and elements vectors are copied into this class instance's
175 member data. The last argument specifies whether this vector will have
176 to be checked for duplicate indices whenever that can happen. */
177 void setVector(int size, const int * inds, const double * elems,
178 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
179
180 /** Elements set to have the same scalar value */
181 void setConstant(int size, const int * inds, double elems,
182 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
183
184 /** Indices are not specified and are taken to be 0,1,...,size-1 */
185 void setFull(int size, const double * elems,
186 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
187
188 /** Indices are not specified and are taken to be 0,1,...,size-1,
189 but only where non zero*/
190 void setFullNonZero(int size, const double * elems,
191 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
192
193 /** Set an existing element in the packed vector
194 The first argument is the "index" into the elements() array
195 */
196 void setElement(int index, double element);
197
198 /// Insert an element into the vector
199 void insert(int index, double element);
200 /// Append a CoinPackedVector to the end
201 void append(const CoinPackedVectorBase & caboose);
202
203 /// Swap values in positions i and j of indices and elements
204 void swap(int i, int j);
205
206 /** Resize the packed vector to be the first newSize elements.
207 Problem with truncate: what happens with origIndices_ ??? */
208 void truncate(int newSize);
209 //@}
210
211 /**@name Arithmetic operators. */
212 //@{
213 /// add <code>value</code> to every entry
214 void operator+=(double value);
215 /// subtract <code>value</code> from every entry
216 void operator-=(double value);
217 /// multiply every entry by <code>value</code>
218 void operator*=(double value);
219 /// divide every entry by <code>value</code>
220 void operator/=(double value);
221 //@}
222
223 /**@name Sorting */
224 //@{
225 /** Sort the packed storage vector.
226 Typcical usages:
227 <pre>
228 packedVector.sort(CoinIncrIndexOrdered()); //increasing indices
229 packedVector.sort(CoinIncrElementOrdered()); // increasing elements
230 </pre>
231 */
232 template <class CoinCompare3>
233 void sort(const CoinCompare3 & tc)
234 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_,
235 tc); }
236
237 void sortIncrIndex()
238 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_,
239 CoinFirstLess_3<int, int, double>()); }
240
241 void sortDecrIndex()
242 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_,
243 CoinFirstGreater_3<int, int, double>()); }
244
245 void sortIncrElement()
246 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_,
247 CoinFirstLess_3<double, int, int>()); }
248
249 void sortDecrElement()
250 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_,
251 CoinFirstGreater_3<double, int, int>()); }
252
253
254 /** Sort in original order.
255 If the vector has been sorted, then this method restores
256 to its orignal sort order.
257 */
258 void sortOriginalOrder();
259 //@}
260
261 /**@name Memory usage */
262 //@{
263 /** Reserve space.
264 If one knows the eventual size of the packed vector,
265 then it may be more efficient to reserve the space.
266 */
267 void reserve(int n);
268 /** capacity returns the size which could be accomodated without
269 having to reallocate storage.
270 */
271 int capacity() const { return capacity_; }
272 //@}
273 /**@name Constructors and destructors */
274 //@{
275 /** Default constructor */
276 CoinPackedVector(bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
277 /** \brief Alternate Constructors - set elements to vector of doubles
278
279 This constructor copies the vectors provided as parameters.
280 */
281 CoinPackedVector(int size, const int * inds, const double * elems,
282 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
283 /** \brief Alternate Constructors - set elements to vector of doubles
284
285 This constructor takes ownership of the vectors passed as parameters.
286 \p inds and \p elems will be NULL on return.
287 */
288 CoinPackedVector(int capacity, int size, int *&inds, double *&elems,
289 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
290 /** Alternate Constructors - set elements to same scalar value */
291 CoinPackedVector(int size, const int * inds, double element,
292 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
293 /** Alternate Constructors - construct full storage with indices 0 through
294 size-1. */
295 CoinPackedVector(int size, const double * elements,
296 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE);
297 /** Copy constructor. */
298 CoinPackedVector(const CoinPackedVector &);
299 /** Copy constructor <em>from a PackedVectorBase</em>. */
300 CoinPackedVector(const CoinPackedVectorBase & rhs);
301 /** Destructor */
302 virtual ~CoinPackedVector ();
303 //@}
304
305private:
306 /**@name Private methods */
307 //@{
308 /// Copy internal date
309 void gutsOfSetVector(int size,
310 const int * inds, const double * elems,
311 bool testForDuplicateIndex,
312 const char * method);
313 ///
314 void gutsOfSetConstant(int size,
315 const int * inds, double value,
316 bool testForDuplicateIndex,
317 const char * method);
318 //@}
319
320private:
321 /**@name Private member data */
322 //@{
323 /// Vector indices
324 int * indices_;
325 ///Vector elements
326 double * elements_;
327 /// Size of indices and elements vectors
328 int nElements_;
329 /// original unsorted indices
330 int * origIndices_;
331 /// Amount of memory allocated for indices_, origIndices_, and elements_.
332 int capacity_;
333 //@}
334};
335
336//#############################################################################
337
338/**@name Arithmetic operators on packed vectors.
339
340 <strong>NOTE</strong>: These methods operate on those positions where at
341 least one of the arguments has a value listed. At those positions the
342 appropriate operation is executed, Otherwise the result of the operation is
343 considered 0.<br>
344 <strong>NOTE 2</strong>: There are two kind of operators here. One is used
345 like "c = binaryOp(a, b)", the other is used like "binaryOp(c, a, b)", but
346 they are really the same. The first is much more natural to use, but it
347 involves the creation of a temporary object (the function *must* return an
348 object), while the second form puts the result directly into the argument
349 "c". Therefore, depending on the circumstances, the second form can be
350 significantly faster.
351 */
352//@{
353template <class BinaryFunction> void
354binaryOp(CoinPackedVector& retVal,
355 const CoinPackedVectorBase& op1, double value,
356 BinaryFunction bf)
357{
358 retVal.clear();
359 const int s = op1.getNumElements();
360 if (s > 0) {
361 retVal.reserve(s);
362 const int * inds = op1.getIndices();
363 const double * elems = op1.getElements();
364 for (int i=0; i<s; ++i ) {
365 retVal.insert(inds[i], bf(value, elems[i]));
366 }
367 }
368}
369
370template <class BinaryFunction> inline void
371binaryOp(CoinPackedVector& retVal,
372 double value, const CoinPackedVectorBase& op2,
373 BinaryFunction bf)
374{
375 binaryOp(retVal, op2, value, bf);
376}
377
378template <class BinaryFunction> void
379binaryOp(CoinPackedVector& retVal,
380 const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2,
381 BinaryFunction bf)
382{
383 retVal.clear();
384 const int s1 = op1.getNumElements();
385 const int s2 = op2.getNumElements();
386/*
387 Replaced || with &&, in response to complaint from Sven deVries, who
388 rightly points out || is not appropriate for additive operations. &&
389 should be ok as long as binaryOp is understood not to create something
390 from nothing. -- lh, 04.06.11
391*/
392 if (s1 == 0 && s2 == 0)
393 return;
394
395 retVal.reserve(s1+s2);
396
397 const int * inds1 = op1.getIndices();
398 const double * elems1 = op1.getElements();
399 const int * inds2 = op2.getIndices();
400 const double * elems2 = op2.getElements();
401
402 int i;
403 // loop once for each element in op1
404 for ( i=0; i<s1; ++i ) {
405 const int index = inds1[i];
406 const int pos2 = op2.findIndex(index);
407 const double val = bf(elems1[i], pos2 == -1 ? 0.0 : elems2[pos2]);
408 // if (val != 0.0) // *THINK* : should we put in only nonzeros?
409 retVal.insert(index, val);
410 }
411 // loop once for each element in operand2
412 for ( i=0; i<s2; ++i ) {
413 const int index = inds2[i];
414 // if index exists in op1, then element was processed in prior loop
415 if ( op1.isExistingIndex(index) )
416 continue;
417 // Index does not exist in op1, so the element value must be zero
418 const double val = bf(0.0, elems2[i]);
419 // if (val != 0.0) // *THINK* : should we put in only nonzeros?
420 retVal.insert(index, val);
421 }
422}
423
424//-----------------------------------------------------------------------------
425
426template <class BinaryFunction> CoinPackedVector
427binaryOp(const CoinPackedVectorBase& op1, double value,
428 BinaryFunction bf)
429{
430 CoinPackedVector retVal;
431 retVal.setTestForDuplicateIndex(true);
432 binaryOp(retVal, op1, value, bf);
433 return retVal;
434}
435
436template <class BinaryFunction> CoinPackedVector
437binaryOp(double value, const CoinPackedVectorBase& op2,
438 BinaryFunction bf)
439{
440 CoinPackedVector retVal;
441 retVal.setTestForDuplicateIndex(true);
442 binaryOp(retVal, op2, value, bf);
443 return retVal;
444}
445
446template <class BinaryFunction> CoinPackedVector
447binaryOp(const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2,
448 BinaryFunction bf)
449{
450 CoinPackedVector retVal;
451 retVal.setTestForDuplicateIndex(true);
452 binaryOp(retVal, op1, op2, bf);
453 return retVal;
454}
455
456//-----------------------------------------------------------------------------
457/// Return the sum of two packed vectors
458inline CoinPackedVector operator+(const CoinPackedVectorBase& op1,
459 const CoinPackedVectorBase& op2)
460{
461 CoinPackedVector retVal;
462 retVal.setTestForDuplicateIndex(true);
463 binaryOp(retVal, op1, op2, std::plus<double>());
464 return retVal;
465}
466
467/// Return the difference of two packed vectors
468inline CoinPackedVector operator-(const CoinPackedVectorBase& op1,
469 const CoinPackedVectorBase& op2)
470{
471 CoinPackedVector retVal;
472 retVal.setTestForDuplicateIndex(true);
473 binaryOp(retVal, op1, op2, std::minus<double>());
474 return retVal;
475}
476
477/// Return the element-wise product of two packed vectors
478inline CoinPackedVector operator*(const CoinPackedVectorBase& op1,
479 const CoinPackedVectorBase& op2)
480{
481 CoinPackedVector retVal;
482 retVal.setTestForDuplicateIndex(true);
483 binaryOp(retVal, op1, op2, std::multiplies<double>());
484 return retVal;
485}
486
487/// Return the element-wise ratio of two packed vectors
488inline CoinPackedVector operator/(const CoinPackedVectorBase& op1,
489 const CoinPackedVectorBase& op2)
490{
491 CoinPackedVector retVal;
492 retVal.setTestForDuplicateIndex(true);
493 binaryOp(retVal, op1, op2, std::divides<double>());
494 return retVal;
495}
496//@}
497
498/// Returns the dot product of two CoinPackedVector objects whose elements are
499/// doubles. Use this version if the vectors are *not* guaranteed to be sorted.
500inline double sparseDotProduct(const CoinPackedVectorBase& op1,
501 const CoinPackedVectorBase& op2){
502 int len, i;
503 double acc = 0.0;
504 CoinPackedVector retVal;
505
506 CoinPackedVector retval = op1*op2;
507 len = retval.getNumElements();
508 double * CParray = retval.getElements();
509
510 for(i = 0; i < len; i++){
511 acc += CParray[i];
512 }
513return acc;
514}
515
516
517/// Returns the dot product of two sorted CoinPackedVector objects.
518/// The vectors should be sorted in ascending order of indices.
519inline double sortedSparseDotProduct(const CoinPackedVectorBase& op1,
520 const CoinPackedVectorBase& op2){
521 int i, j, len1, len2;
522 double acc = 0.0;
523
524 const double* v1val = op1.getElements();
525 const double* v2val = op2.getElements();
526 const int* v1ind = op1.getIndices();
527 const int* v2ind = op2.getIndices();
528
529 len1 = op1.getNumElements();
530 len2 = op2.getNumElements();
531
532 i = 0;
533 j = 0;
534
535 while(i < len1 && j < len2){
536 if(v1ind[i] == v2ind[j]){
537 acc += v1val[i] * v2val[j];
538 i++;
539 j++;
540 }
541 else if(v2ind[j] < v1ind[i]){
542 j++;
543 }
544 else{
545 i++;
546 } // end if-else-elseif
547 } // end while
548 return acc;
549 }
550
551
552//-----------------------------------------------------------------------------
553
554/**@name Arithmetic operators on packed vector and a constant. <br>
555 These functions create a packed vector as a result. That packed vector will
556 have the same indices as <code>op1</code> and the specified operation is
557 done entry-wise with the given value. */
558//@{
559/// Return the sum of a packed vector and a constant
560inline CoinPackedVector
561operator+(const CoinPackedVectorBase& op1, double value)
562{
563 CoinPackedVector retVal(op1);
564 retVal += value;
565 return retVal;
566}
567
568/// Return the difference of a packed vector and a constant
569inline CoinPackedVector
570operator-(const CoinPackedVectorBase& op1, double value)
571{
572 CoinPackedVector retVal(op1);
573 retVal -= value;
574 return retVal;
575}
576
577/// Return the element-wise product of a packed vector and a constant
578inline CoinPackedVector
579operator*(const CoinPackedVectorBase& op1, double value)
580{
581 CoinPackedVector retVal(op1);
582 retVal *= value;
583 return retVal;
584}
585
586/// Return the element-wise ratio of a packed vector and a constant
587inline CoinPackedVector
588operator/(const CoinPackedVectorBase& op1, double value)
589{
590 CoinPackedVector retVal(op1);
591 retVal /= value;
592 return retVal;
593}
594
595//-----------------------------------------------------------------------------
596
597/// Return the sum of a constant and a packed vector
598inline CoinPackedVector
599operator+(double value, const CoinPackedVectorBase& op1)
600{
601 CoinPackedVector retVal(op1);
602 retVal += value;
603 return retVal;
604}
605
606/// Return the difference of a constant and a packed vector
607inline CoinPackedVector
608operator-(double value, const CoinPackedVectorBase& op1)
609{
610 CoinPackedVector retVal(op1);
611 const int size = retVal.getNumElements();
612 double* elems = retVal.getElements();
613 for (int i = 0; i < size; ++i) {
614 elems[i] = value - elems[i];
615 }
616 return retVal;
617}
618
619/// Return the element-wise product of a constant and a packed vector
620inline CoinPackedVector
621operator*(double value, const CoinPackedVectorBase& op1)
622{
623 CoinPackedVector retVal(op1);
624 retVal *= value;
625 return retVal;
626}
627
628/// Return the element-wise ratio of a a constant and packed vector
629inline CoinPackedVector
630operator/(double value, const CoinPackedVectorBase& op1)
631{
632 CoinPackedVector retVal(op1);
633 const int size = retVal.getNumElements();
634 double* elems = retVal.getElements();
635 for (int i = 0; i < size; ++i) {
636 elems[i] = value / elems[i];
637 }
638 return retVal;
639}
640//@}
641
642//#############################################################################
643/** A function that tests the methods in the CoinPackedVector class. The
644 only reason for it not to be a member method is that this way it doesn't
645 have to be compiled into the library. And that's a gain, because the
646 library should be compiled with optimization on, but this method should be
647 compiled with debugging. */
648void
649CoinPackedVectorUnitTest();
650
651#endif
652