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 inline int getVectorNumElements() const { return nElements_; } 00140 inline const int * getVectorIndices() const { return indices_; } 00142 inline const double * getVectorElements() const { return elements_; } 00144 double * getElements() { return elements_; } 00148 const int * getOriginalPosition() const { return origIndices_; } 00150 00151 //------------------------------------------------------------------- 00152 // Set indices and elements 00153 //------------------------------------------------------------------- 00156 00157 void clear(); 00162 CoinPackedVector & operator=(const CoinPackedVector &); 00167 CoinPackedVector & operator=(const CoinPackedVectorBase & rhs); 00168 00175 void assignVector(int size, int*& inds, double*& elems, 00176 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00177 00183 void setVector(int size, const int * inds, const double * elems, 00184 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00185 00187 void setConstant(int size, const int * inds, double elems, 00188 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00189 00191 void setFull(int size, const double * elems, 00192 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00193 00196 void setFullNonZero(int size, const double * elems, 00197 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00198 00202 void setElement(int index, double element); 00203 00205 void insert(int index, double element); 00207 void append(const CoinPackedVectorBase & caboose); 00208 00210 void swap(int i, int j); 00211 00214 void truncate(int newSize); 00216 00219 00220 void operator+=(double value); 00222 void operator-=(double value); 00224 void operator*=(double value); 00226 void operator/=(double value); 00228 00238 template <class CoinCompare3> 00239 void sort(const CoinCompare3 & tc) 00240 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00241 tc); } 00242 00243 void sortIncrIndex() 00244 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00245 CoinFirstLess_3<int, int, double>()); } 00246 00247 void sortDecrIndex() 00248 { CoinSort_3(indices_, indices_ + nElements_, origIndices_, elements_, 00249 CoinFirstGreater_3<int, int, double>()); } 00250 00251 void sortIncrElement() 00252 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_, 00253 CoinFirstLess_3<double, int, int>()); } 00254 00255 void sortDecrElement() 00256 { CoinSort_3(elements_, elements_ + nElements_, origIndices_, indices_, 00257 CoinFirstGreater_3<double, int, int>()); } 00258 00259 00264 void sortOriginalOrder(); 00266 00273 void reserve(int n); 00277 int capacity() const { return capacity_; } 00279 00282 CoinPackedVector(bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00287 CoinPackedVector(int size, const int * inds, const double * elems, 00288 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00294 CoinPackedVector(int capacity, int size, int *&inds, double *&elems, 00295 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00297 CoinPackedVector(int size, const int * inds, double element, 00298 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00301 CoinPackedVector(int size, const double * elements, 00302 bool testForDuplicateIndex = COIN_DEFAULT_VALUE_FOR_DUPLICATE); 00304 CoinPackedVector(const CoinPackedVector &); 00306 CoinPackedVector(const CoinPackedVectorBase & rhs); 00308 virtual ~CoinPackedVector (); 00310 00311 private: 00314 00315 void gutsOfSetVector(int size, 00316 const int * inds, const double * elems, 00317 bool testForDuplicateIndex, 00318 const char * method); 00320 void gutsOfSetConstant(int size, 00321 const int * inds, double value, 00322 bool testForDuplicateIndex, 00323 const char * method); 00325 00326 private: 00329 00330 int * indices_; 00332 double * elements_; 00334 int nElements_; 00336 int * origIndices_; 00338 int capacity_; 00340 }; 00341 00342 //############################################################################# 00343 00359 template <class BinaryFunction> void 00360 binaryOp(CoinPackedVector& retVal, 00361 const CoinPackedVectorBase& op1, double value, 00362 BinaryFunction bf) 00363 { 00364 retVal.clear(); 00365 const int s = op1.getNumElements(); 00366 if (s > 0) { 00367 retVal.reserve(s); 00368 const int * inds = op1.getIndices(); 00369 const double * elems = op1.getElements(); 00370 for (int i=0; i<s; ++i ) { 00371 retVal.insert(inds[i], bf(value, elems[i])); 00372 } 00373 } 00374 } 00375 00376 template <class BinaryFunction> inline void 00377 binaryOp(CoinPackedVector& retVal, 00378 double value, const CoinPackedVectorBase& op2, 00379 BinaryFunction bf) 00380 { 00381 binaryOp(retVal, op2, value, bf); 00382 } 00383 00384 template <class BinaryFunction> void 00385 binaryOp(CoinPackedVector& retVal, 00386 const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2, 00387 BinaryFunction bf) 00388 { 00389 retVal.clear(); 00390 const int s1 = op1.getNumElements(); 00391 const int s2 = op2.getNumElements(); 00392 /* 00393 Replaced || with &&, in response to complaint from Sven deVries, who 00394 rightly points out || is not appropriate for additive operations. && 00395 should be ok as long as binaryOp is understood not to create something 00396 from nothing. -- lh, 04.06.11 00397 */ 00398 if (s1 == 0 && s2 == 0) 00399 return; 00400 00401 retVal.reserve(s1+s2); 00402 00403 const int * inds1 = op1.getIndices(); 00404 const double * elems1 = op1.getElements(); 00405 const int * inds2 = op2.getIndices(); 00406 const double * elems2 = op2.getElements(); 00407 00408 int i; 00409 // loop once for each element in op1 00410 for ( i=0; i<s1; ++i ) { 00411 const int index = inds1[i]; 00412 const int pos2 = op2.findIndex(index); 00413 const double val = bf(elems1[i], pos2 == -1 ? 0.0 : elems2[pos2]); 00414 // if (val != 0.0) // *THINK* : should we put in only nonzeros? 00415 retVal.insert(index, val); 00416 } 00417 // loop once for each element in operand2 00418 for ( i=0; i<s2; ++i ) { 00419 const int index = inds2[i]; 00420 // if index exists in op1, then element was processed in prior loop 00421 if ( op1.isExistingIndex(index) ) 00422 continue; 00423 // Index does not exist in op1, so the element value must be zero 00424 const double val = bf(0.0, elems2[i]); 00425 // if (val != 0.0) // *THINK* : should we put in only nonzeros? 00426 retVal.insert(index, val); 00427 } 00428 } 00429 00430 //----------------------------------------------------------------------------- 00431 00432 template <class BinaryFunction> CoinPackedVector 00433 binaryOp(const CoinPackedVectorBase& op1, double value, 00434 BinaryFunction bf) 00435 { 00436 CoinPackedVector retVal; 00437 retVal.setTestForDuplicateIndex(true); 00438 binaryOp(retVal, op1, value, bf); 00439 return retVal; 00440 } 00441 00442 template <class BinaryFunction> CoinPackedVector 00443 binaryOp(double value, const CoinPackedVectorBase& op2, 00444 BinaryFunction bf) 00445 { 00446 CoinPackedVector retVal; 00447 retVal.setTestForDuplicateIndex(true); 00448 binaryOp(retVal, op2, value, bf); 00449 return retVal; 00450 } 00451 00452 template <class BinaryFunction> CoinPackedVector 00453 binaryOp(const CoinPackedVectorBase& op1, const CoinPackedVectorBase& op2, 00454 BinaryFunction bf) 00455 { 00456 CoinPackedVector retVal; 00457 retVal.setTestForDuplicateIndex(true); 00458 binaryOp(retVal, op1, op2, bf); 00459 return retVal; 00460 } 00461 00462 //----------------------------------------------------------------------------- 00464 inline CoinPackedVector operator+(const CoinPackedVectorBase& op1, 00465 const CoinPackedVectorBase& op2) 00466 { 00467 CoinPackedVector retVal; 00468 retVal.setTestForDuplicateIndex(true); 00469 binaryOp(retVal, op1, op2, std::plus<double>()); 00470 return retVal; 00471 } 00472 00474 inline CoinPackedVector operator-(const CoinPackedVectorBase& op1, 00475 const CoinPackedVectorBase& op2) 00476 { 00477 CoinPackedVector retVal; 00478 retVal.setTestForDuplicateIndex(true); 00479 binaryOp(retVal, op1, op2, std::minus<double>()); 00480 return retVal; 00481 } 00482 00484 inline CoinPackedVector operator*(const CoinPackedVectorBase& op1, 00485 const CoinPackedVectorBase& op2) 00486 { 00487 CoinPackedVector retVal; 00488 retVal.setTestForDuplicateIndex(true); 00489 binaryOp(retVal, op1, op2, std::multiplies<double>()); 00490 return retVal; 00491 } 00492 00494 inline CoinPackedVector operator/(const CoinPackedVectorBase& op1, 00495 const CoinPackedVectorBase& op2) 00496 { 00497 CoinPackedVector retVal; 00498 retVal.setTestForDuplicateIndex(true); 00499 binaryOp(retVal, op1, op2, std::divides<double>()); 00500 return retVal; 00501 } 00503 00506 inline double sparseDotProduct(const CoinPackedVectorBase& op1, 00507 const CoinPackedVectorBase& op2){ 00508 int len, i; 00509 double acc = 0.0; 00510 CoinPackedVector retVal; 00511 00512 CoinPackedVector retval = op1*op2; 00513 len = retval.getNumElements(); 00514 double * CParray = retval.getElements(); 00515 00516 for(i = 0; i < len; i++){ 00517 acc += CParray[i]; 00518 } 00519 return acc; 00520 } 00521 00522 00525 inline double sortedSparseDotProduct(const CoinPackedVectorBase& op1, 00526 const CoinPackedVectorBase& op2){ 00527 int i, j, len1, len2; 00528 double acc = 0.0; 00529 00530 const double* v1val = op1.getElements(); 00531 const double* v2val = op2.getElements(); 00532 const int* v1ind = op1.getIndices(); 00533 const int* v2ind = op2.getIndices(); 00534 00535 len1 = op1.getNumElements(); 00536 len2 = op2.getNumElements(); 00537 00538 i = 0; 00539 j = 0; 00540 00541 while(i < len1 && j < len2){ 00542 if(v1ind[i] == v2ind[j]){ 00543 acc += v1val[i] * v2val[j]; 00544 i++; 00545 j++; 00546 } 00547 else if(v2ind[j] < v1ind[i]){ 00548 j++; 00549 } 00550 else{ 00551 i++; 00552 } // end if-else-elseif 00553 } // end while 00554 return acc; 00555 } 00556 00557 00558 //----------------------------------------------------------------------------- 00559 00565 00566 inline CoinPackedVector 00567 operator+(const CoinPackedVectorBase& op1, double value) 00568 { 00569 CoinPackedVector retVal(op1); 00570 retVal += value; 00571 return retVal; 00572 } 00573 00575 inline CoinPackedVector 00576 operator-(const CoinPackedVectorBase& op1, double value) 00577 { 00578 CoinPackedVector retVal(op1); 00579 retVal -= value; 00580 return retVal; 00581 } 00582 00584 inline CoinPackedVector 00585 operator*(const CoinPackedVectorBase& op1, double value) 00586 { 00587 CoinPackedVector retVal(op1); 00588 retVal *= value; 00589 return retVal; 00590 } 00591 00593 inline CoinPackedVector 00594 operator/(const CoinPackedVectorBase& op1, double value) 00595 { 00596 CoinPackedVector retVal(op1); 00597 retVal /= value; 00598 return retVal; 00599 } 00600 00601 //----------------------------------------------------------------------------- 00602 00604 inline CoinPackedVector 00605 operator+(double value, const CoinPackedVectorBase& op1) 00606 { 00607 CoinPackedVector retVal(op1); 00608 retVal += value; 00609 return retVal; 00610 } 00611 00613 inline CoinPackedVector 00614 operator-(double value, const CoinPackedVectorBase& op1) 00615 { 00616 CoinPackedVector retVal(op1); 00617 const int size = retVal.getNumElements(); 00618 double* elems = retVal.getElements(); 00619 for (int i = 0; i < size; ++i) { 00620 elems[i] = value - elems[i]; 00621 } 00622 return retVal; 00623 } 00624 00626 inline CoinPackedVector 00627 operator*(double value, const CoinPackedVectorBase& op1) 00628 { 00629 CoinPackedVector retVal(op1); 00630 retVal *= value; 00631 return retVal; 00632 } 00633 00635 inline CoinPackedVector 00636 operator/(double value, const CoinPackedVectorBase& op1) 00637 { 00638 CoinPackedVector retVal(op1); 00639 const int size = retVal.getNumElements(); 00640 double* elems = retVal.getElements(); 00641 for (int i = 0; i < size; ++i) { 00642 elems[i] = value / elems[i]; 00643 } 00644 return retVal; 00645 } 00647 00648 //############################################################################# 00654 void 00655 CoinPackedVectorUnitTest(); 00656 00657 #endif