CoinUtils trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2000, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef CoinPackedVector_H 00007 #define CoinPackedVector_H 00008 00009 #include <map> 00010 00011 #include "CoinPragma.hpp" 00012 #include "CoinPackedVectorBase.hpp" 00013 #include "CoinSort.hpp" 00014 00015 #ifdef COIN_FAST_CODE 00016 #ifndef COIN_NOTEST_DUPLICATE 00017 #define COIN_NOTEST_DUPLICATE 00018 #endif 00019 #endif 00020 00021 #ifndef COIN_NOTEST_DUPLICATE 00022 #define COIN_DEFAULT_VALUE_FOR_DUPLICATE true 00023 #else 00024 #define COIN_DEFAULT_VALUE_FOR_DUPLICATE false 00025 #endif 00026 00123 class CoinPackedVector : public CoinPackedVectorBase { 00124 friend void CoinPackedVectorUnitTest(); 00125 00126 public: 00129 00130 virtual int getNumElements() const { return nElements_; } 00132 virtual const int * getIndices() const { return indices_; } 00134 virtual const double * getElements() const { return elements_; } 00136 int * getIndices() { return indices_; } 00138 double * getElements() { return elements_; } 00142 const int * getOriginalPosition() const { return origIndices_; } 00144 00145 //------------------------------------------------------------------- 00146 // Set indices and elements 00147 //------------------------------------------------------------------- 00150 00151 void clear(); 00156 CoinPackedVector & operator=(const CoinPackedVector &); 00161 CoinPackedVector & operator=(const CoinPackedVectorBase & rhs); 00162 00169 void assignVector(int size, int*& inds, double*& elems, 00170 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00171 00177 void setVector(int size, const int * inds, const double * elems, 00178 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00179 00181 void setConstant(int size, const int * inds, double elems, 00182 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00183 00185 void setFull(int size, const double * elems, 00186 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00187 00190 void setFullNonZero(int size, const double * elems, 00191 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00192 00196 void setElement(int index, double element); 00197 00199 void insert(int index, double element); 00201 void append(const CoinPackedVectorBase & caboose); 00202 00204 void swap(int i, int j); 00205 00208 void truncate(int newSize); 00210 00213 00214 void operator+=(double value); 00216 void operator-=(double value); 00218 void operator*=(double value); 00220 void operator/=(double value); 00222 00232 template <class CoinCompare3> 00233 void sort(const CoinCompare3 & tc) 00234 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00235 tc); } 00236 00237 void sortIncrIndex() 00238 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00239 CoinFirstLess_3<int, int, double>()); } 00240 00241 void sortDecrIndex() 00242 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00243 CoinFirstGreater_3<int, int, double>()); } 00244 00245 void sortIncrElement() 00246 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_, 00247 CoinFirstLess_3<double, int, int>()); } 00248 00249 void sortDecrElement() 00250 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_, 00251 CoinFirstGreater_3<double, int, int>()); } 00252 00253 00258 void sortOriginalOrder(); 00260 00267 void reserve(int n); 00271 int capacity() const { return capacity_; } 00273 00276 CoinPackedVector(bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00281 CoinPackedVector(int size, const int * inds, const double * elems, 00282 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00288 CoinPackedVector(int capacity, int size, int *&inds, double *&elems, 00289 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00291 CoinPackedVector(int size, const int * inds, double element, 00292 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00295 CoinPackedVector(int size, const double * elements, 00296 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00298 CoinPackedVector(const CoinPackedVector &); 00300 CoinPackedVector(const CoinPackedVectorBase & rhs); 00302 virtual ~CoinPackedVector (); 00304 00305 private: 00308 00309 void gutsOfSetVector(int size, 00310 const int * inds, const double * elems, 00311 bool testForDuplicateIndex, 00312 const char * method); 00314 void gutsOfSetConstant(int size, 00315 const int * inds, double value, 00316 bool testForDuplicateIndex, 00317 const char * method); 00319 00320 private: 00323 00324 int * indices_; 00326 double * elements_; 00328 int nElements_; 00330 int * origIndices_; 00332 int capacity_; 00334 }; 00335 00336 //############################################################################# 00337 00353 template <class BinaryFunction> void 00354 binaryOp(CoinPackedVector& retVal, 00355 const CoinPackedVectorBase& op1, double value, 00356 BinaryFunction bf) 00357 { 00358 retVal.clear(); 00359 const int s = op1.getNumElements(); 00360 if (s > 0) { 00361 retVal.reserve(s); 00362 const int * inds = op1.getIndices(); 00363 const double * elems = op1.getElements(); 00364 for (int i=0; i<s; ++i ) { 00365 retVal.insert(inds[i], bf(value, elems[i])); 00366 } 00367 } 00368 } 00369 00370 template <class BinaryFunction> inline void 00371 binaryOp(CoinPackedVector& retVal, 00372 double value, const CoinPackedVectorBase& op2, 00373 BinaryFunction bf) 00374 { 00375 binaryOp(retVal, op2, value, bf); 00376 } 00377 00378 template <class BinaryFunction> void 00379 binaryOp(CoinPackedVector& retVal, 00380 const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2, 00381 BinaryFunction bf) 00382 { 00383 retVal.clear(); 00384 const int s1 = op1.getNumElements(); 00385 const int s2 = op2.getNumElements(); 00386 /* 00387 Replaced || with &&, in response to complaint from Sven deVries, who 00388 rightly points out || is not appropriate for additive operations. && 00389 should be ok as long as binaryOp is understood not to create something 00390 from nothing. -- lh, 04.06.11 00391 */ 00392 if (s1 == 0 && s2 == 0) 00393 return; 00394 00395 retVal.reserve(s1+s2); 00396 00397 const int * inds1 = op1.getIndices(); 00398 const double * elems1 = op1.getElements(); 00399 const int * inds2 = op2.getIndices(); 00400 const double * elems2 = op2.getElements(); 00401 00402 int i; 00403 // loop once for each element in op1 00404 for ( i=0; i<s1; ++i ) { 00405 const int index = inds1[i]; 00406 const int pos2 = op2.findIndex(index); 00407 const double val = bf(elems1[i], pos2 == -1 ? 0.0 : elems2[pos2]); 00408 // if (val != 0.0) // *THINK* : should we put in only nonzeros? 00409 retVal.insert(index, val); 00410 } 00411 // loop once for each element in operand2 00412 for ( i=0; i<s2; ++i ) { 00413 const int index = inds2[i]; 00414 // if index exists in op1, then element was processed in prior loop 00415 if ( op1.isExistingIndex(index) ) 00416 continue; 00417 // Index does not exist in op1, so the element value must be zero 00418 const double val = bf(0.0, elems2[i]); 00419 // if (val != 0.0) // *THINK* : should we put in only nonzeros? 00420 retVal.insert(index, val); 00421 } 00422 } 00423 00424 //----------------------------------------------------------------------------- 00425 00426 template <class BinaryFunction> CoinPackedVector 00427 binaryOp(const CoinPackedVectorBase& op1, double value, 00428 BinaryFunction bf) 00429 { 00430 CoinPackedVector retVal; 00431 retVal.setTestForDuplicateIndex(true); 00432 binaryOp(retVal, op1, value, bf); 00433 return retVal; 00434 } 00435 00436 template <class BinaryFunction> CoinPackedVector 00437 binaryOp(double value, const CoinPackedVectorBase& op2, 00438 BinaryFunction bf) 00439 { 00440 CoinPackedVector retVal; 00441 retVal.setTestForDuplicateIndex(true); 00442 binaryOp(retVal, op2, value, bf); 00443 return retVal; 00444 } 00445 00446 template <class BinaryFunction> CoinPackedVector 00447 binaryOp(const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2, 00448 BinaryFunction bf) 00449 { 00450 CoinPackedVector retVal; 00451 retVal.setTestForDuplicateIndex(true); 00452 binaryOp(retVal, op1, op2, bf); 00453 return retVal; 00454 } 00455 00456 //----------------------------------------------------------------------------- 00458 inline CoinPackedVector operator+(const CoinPackedVectorBase& op1, 00459 const CoinPackedVectorBase& op2) 00460 { 00461 CoinPackedVector retVal; 00462 retVal.setTestForDuplicateIndex(true); 00463 binaryOp(retVal, op1, op2, std::plus<double>()); 00464 return retVal; 00465 } 00466 00468 inline CoinPackedVector operator-(const CoinPackedVectorBase& op1, 00469 const CoinPackedVectorBase& op2) 00470 { 00471 CoinPackedVector retVal; 00472 retVal.setTestForDuplicateIndex(true); 00473 binaryOp(retVal, op1, op2, std::minus<double>()); 00474 return retVal; 00475 } 00476 00478 inline CoinPackedVector operator*(const CoinPackedVectorBase& op1, 00479 const CoinPackedVectorBase& op2) 00480 { 00481 CoinPackedVector retVal; 00482 retVal.setTestForDuplicateIndex(true); 00483 binaryOp(retVal, op1, op2, std::multiplies<double>()); 00484 return retVal; 00485 } 00486 00488 inline CoinPackedVector operator/(const CoinPackedVectorBase& op1, 00489 const CoinPackedVectorBase& op2) 00490 { 00491 CoinPackedVector retVal; 00492 retVal.setTestForDuplicateIndex(true); 00493 binaryOp(retVal, op1, op2, std::divides<double>()); 00494 return retVal; 00495 } 00497 00500 inline double sparseDotProduct(const CoinPackedVectorBase& op1, 00501 const CoinPackedVectorBase& op2){ 00502 int len, i; 00503 double acc = 0.0; 00504 CoinPackedVector retVal; 00505 00506 CoinPackedVector retval = op1*op2; 00507 len = retval.getNumElements(); 00508 double * CParray = retval.getElements(); 00509 00510 for(i = 0; i < len; i++){ 00511 acc += CParray[i]; 00512 } 00513 return acc; 00514 } 00515 00516 00519 inline double sortedSparseDotProduct(const CoinPackedVectorBase& op1, 00520 const CoinPackedVectorBase& op2){ 00521 int i, j, len1, len2; 00522 double acc = 0.0; 00523 00524 const double* v1val = op1.getElements(); 00525 const double* v2val = op2.getElements(); 00526 const int* v1ind = op1.getIndices(); 00527 const int* v2ind = op2.getIndices(); 00528 00529 len1 = op1.getNumElements(); 00530 len2 = op2.getNumElements(); 00531 00532 i = 0; 00533 j = 0; 00534 00535 while(i < len1 && j < len2){ 00536 if(v1ind[i] == v2ind[j]){ 00537 acc += v1val[i] * v2val[j]; 00538 i++; 00539 j++; 00540 } 00541 else if(v2ind[j] < v1ind[i]){ 00542 j++; 00543 } 00544 else{ 00545 i++; 00546 } // end if-else-elseif 00547 } // end while 00548 return acc; 00549 } 00550 00551 00552 //----------------------------------------------------------------------------- 00553 00559 00560 inline CoinPackedVector 00561 operator+(const CoinPackedVectorBase& op1, double value) 00562 { 00563 CoinPackedVector retVal(op1); 00564 retVal += value; 00565 return retVal; 00566 } 00567 00569 inline CoinPackedVector 00570 operator-(const CoinPackedVectorBase& op1, double value) 00571 { 00572 CoinPackedVector retVal(op1); 00573 retVal -= value; 00574 return retVal; 00575 } 00576 00578 inline CoinPackedVector 00579 operator*(const CoinPackedVectorBase& op1, double value) 00580 { 00581 CoinPackedVector retVal(op1); 00582 retVal *= value; 00583 return retVal; 00584 } 00585 00587 inline CoinPackedVector 00588 operator/(const CoinPackedVectorBase& op1, double value) 00589 { 00590 CoinPackedVector retVal(op1); 00591 retVal /= value; 00592 return retVal; 00593 } 00594 00595 //----------------------------------------------------------------------------- 00596 00598 inline CoinPackedVector 00599 operator+(double value, const CoinPackedVectorBase& op1) 00600 { 00601 CoinPackedVector retVal(op1); 00602 retVal += value; 00603 return retVal; 00604 } 00605 00607 inline CoinPackedVector 00608 operator-(double value, const CoinPackedVectorBase& op1) 00609 { 00610 CoinPackedVector retVal(op1); 00611 const int size = retVal.getNumElements(); 00612 double* elems = retVal.getElements(); 00613 for (int i = 0; i < size; ++i) { 00614 elems[i] = value - elems[i]; 00615 } 00616 return retVal; 00617 } 00618 00620 inline CoinPackedVector 00621 operator*(double value, const CoinPackedVectorBase& op1) 00622 { 00623 CoinPackedVector retVal(op1); 00624 retVal *= value; 00625 return retVal; 00626 } 00627 00629 inline CoinPackedVector 00630 operator/(double value, const CoinPackedVectorBase& op1) 00631 { 00632 CoinPackedVector retVal(op1); 00633 const int size = retVal.getNumElements(); 00634 double* elems = retVal.getElements(); 00635 for (int i = 0; i < size; ++i) { 00636 elems[i] = value / elems[i]; 00637 } 00638 return retVal; 00639 } 00641 00642 //############################################################################# 00648 void 00649 CoinPackedVectorUnitTest(); 00650 00651 #endif