00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef UTIL_MACROS_INCLUDED
00017 #define UTIL_MACROS_INCLUDED
00018
00019
00020 #include <cstdio>
00021 #include <cassert>
00022 #include <vector>
00023 #include <list>
00024 #include <iostream>
00025 #include <fstream>
00026 #include <iomanip>
00027 #include <numeric>
00028 #include <sstream>
00029 #include <algorithm>
00030 #include <functional>
00031 #include <string>
00032 #include <map>
00033 #include <climits>
00034 #include <cmath>
00035 #include <cstring>
00036 #include <ctime>
00037 #include <memory>
00038
00039
00040 const std::string UtilSpaces = " \t\r\n";
00041 const double UtilEpsilon = 1.0e-6;
00042 const double UtilTooBig = 1.0e20;
00043 const double UtilSmallerThanTooBig = 1.0e19;
00044 #ifndef INT_MAX
00045 #define INT_MAX (static_cast<int>((~(static_cast<unsigned int>(0))) >> 1))
00046 #endif
00047
00048 #ifndef round
00049 #define round(x) floor(x+0.5)
00050 #endif
00051
00052
00053
00054
00055
00056
00057 enum UtilStatus {
00058 UtilStatusOk = 0,
00059 UtilStatusFileIO
00060 };
00061
00062
00063
00064
00065 #define UTIL_DELPTR(x) if(x) {delete x; x = 0;}
00066 #define UTIL_DELARR(x) if(x) {delete [] x; x = 0;}
00067
00068
00069
00070
00071 #ifdef NDEBUG
00072
00073 #define UTIL_DEBUG(param, level, x)
00074
00075 #else
00076 #define UTIL_DEBUG(param, level, x) if(param >= level) {x fflush(stdout);}
00077 #endif
00078
00079
00080 #define UTIL_MSG(param, level, x) if(param >= level) {x fflush(stdout);}
00081
00082
00083
00084 #ifndef NDEBUG
00085 #define UtilAssert(expression,errorMsg,os) assert(expresssion)
00086 #else
00087 inline void UtilAssert(bool expression,
00088 std::string errorMsg,
00089 std::ostream* os)
00090 {
00091
00092
00093
00094 if (!expression) {
00095 (*os) << "ERROR:" << errorMsg << std::endl;
00096 abort();
00097 }
00098 }
00099 #endif
00100
00101
00102 inline void UtilPrintParameter(std::ostream* os,
00103 const std::string& section,
00104 const std::string& name,
00105 const int value)
00106 {
00107 (*os) << std::left << std::setw(15) << section
00108 << std::left << std::setw(25) << name
00109 << std::setw(10) << value << std::endl;
00110 }
00111
00112
00113 inline void UtilPrintParameter(std::ostream* os,
00114 const std::string& section,
00115 const std::string& name,
00116 const double value)
00117 {
00118 (*os) << std::left << std::setw(15) << section
00119 << std::left << std::setw(25) << name
00120 << std::setw(10) << value << std::endl;
00121 }
00122
00123
00124 inline void UtilPrintParameter(std::ostream* os,
00125 const std::string& section,
00126 const std::string& name,
00127 const std::string& value)
00128 {
00129 (*os) << std::left << std::setw(15) << section
00130 << std::left << std::setw(25) << name
00131 << std::setw(10) << value << std::endl;
00132 }
00133
00134
00135
00136 template <class T> inline void
00137 UtilPrintVector(const std::vector<T>& v,
00138 std::ostream* os = &std::cout)
00139 {
00140 typename std::vector<T>::const_iterator it;
00141
00142 for (it = v.begin(); it != v.end(); it++) {
00143 (*os) << *it << " ";
00144 }
00145
00146 (*os) << "\n";
00147 }
00148
00149
00150 template <class T> inline void
00151 UtilPrintVector(const std::vector<T>& v,
00152 const std::vector<std::string>& label,
00153 std::ostream* os = &std::cout)
00154 {
00155 typename std::vector<T>::const_iterator it;
00156
00157 for (it = v.begin(); it != v.end(); it++) {
00158 (*os) << std::setw(5) << *it << " -> "
00159 << std::setw(25) << label[*it] << std::endl;
00160 }
00161 }
00162
00163
00164 template <class T> inline void
00165 UtilPrintList(const std::list<T>& v,
00166 std::ostream* os = &std::cout)
00167 {
00168 typename std::list<T>::const_iterator it;
00169 (*os) << "\n";
00170
00171 for (it = v.begin(); it != v.end(); it++) {
00172 (*os) << *it << " ";
00173 }
00174 }
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223 inline int UtilNumEdgesU(const int n)
00224 {
00225 return ((n * n) - n) / 2;
00226 }
00227
00228
00229 inline int UtilIndexU(const int i, const int j)
00230 {
00231 return i > j ? (i * (i - 1) / 2) + j : (j * (j - 1) / 2) + i;
00232 }
00233
00234
00235 std::pair<int, int> UtilBothEndsU(const int index);
00236
00237
00238 inline void UtilPrintEdge(const int index,
00239 std::ostream* os = &std::cout)
00240 {
00241 std::pair<int, int> uv = UtilBothEndsU(index);
00242 (*os) << "(" << std::setw(2) << uv.first << "," << std::setw(
00243 2) << uv.second << ") ";
00244 }
00245
00246
00247 inline std::string UtilEdgeToStr(const int index)
00248 {
00249 std::stringstream ss;
00250 std::pair<int, int> uv = UtilBothEndsU(index);
00251 ss << "(" << std::setw(2) << uv.first << "," << std::setw(
00252 2) << uv.second << ") ";
00253 return ss.str();
00254 }
00255
00256
00257
00258
00259
00260
00261 template <class T> inline void
00262 UtilFillN(T* to, const int size, const T value)
00263 {
00264 int i;
00265
00266 for (i = 0; i < size; i++) {
00267 to[i] = value;
00268 }
00269 }
00270
00271
00272 template <class T> inline void
00273 UtilFillN(std::vector<T>& v, const int size, const T value)
00274 {
00275 std::fill_n(back_inserter(v), size, value);
00276 }
00277
00278
00279 inline void UtilIotaN(int* first,
00280 const int size,
00281 const int init)
00282 {
00283 int val = init + size;
00284 int ii;
00285
00286 for (ii = size; ii-- != 0; ) {
00287 first[ii] = --val;
00288 }
00289 }
00290
00291
00292 inline void UtilIotaN(std::vector<int>& first,
00293 const int size,
00294 const int init)
00295 {
00296 first.reserve(size);
00297 int i, val = init + size;
00298
00299 for (i = init; i < val; i++) {
00300 first.push_back(i);
00301 }
00302 }
00303
00304
00305
00306
00307
00308
00309 inline double UtilURand(const double a, const double b)
00310 {
00311 double rand01 = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
00312 return a + (rand01 * (b - a));
00313 }
00314
00315
00316 inline int UtilURand(const int a, const int b)
00317 {
00318 double rand01 = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
00319 return a + static_cast<int>(rand01 * (b - a));
00320 }
00321
00322
00323 inline double UtilNormRand(const double mean,
00324 const double sigma)
00325 {
00326
00327 double rand01a = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
00328 double rand01b = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
00329 const double pi = 3.14159265358979323846;
00330 double z1 = sqrt(-2.0 * log(rand01a)) * cos(2.0 * pi * rand01b);
00331 return z1 * sigma + mean;
00332 }
00333
00334
00335
00336
00337
00338
00339 inline double UtilAve(const std::vector<double>& x)
00340 {
00341 return std::accumulate(x.begin(), x.end(), 0.0) /
00342 static_cast<double>(x.size());
00343 }
00344
00345
00346 inline double UtilAve(const std::vector<int>& x)
00347 {
00348 return std::accumulate(x.begin(), x.end(), 0.0) /
00349 static_cast<double>(x.size());
00350 }
00351
00352
00353 inline double UtilAve(const double* x,
00354 const int len)
00355 {
00356 return std::accumulate(x, x + len, 0.0) / static_cast<double>(len);
00357 }
00358
00359
00360
00361
00362
00363
00364 inline void UtilStringTokenize(std::string const& input,
00365 std::string const& delimiters,
00366 std::vector<std::string>& tokens)
00367 {
00368 std::string::size_type last_pos = 0;
00369 std::string::size_type pos = 0;
00370
00371 while (true) {
00372 pos = input.find_first_of(delimiters, last_pos);
00373
00374 if ( pos == std::string::npos ) {
00375 tokens.push_back(input.substr(last_pos));
00376 break;
00377 } else {
00378 tokens.push_back(input.substr(last_pos, pos - last_pos));
00379 last_pos = pos + 1;
00380 }
00381 }
00382 }
00383
00384
00385 inline std::string UtilStringRandom(int iLength)
00386 {
00387 std::string strReturn;
00388 srand( (unsigned int)time(NULL) );
00389
00390 for ( int i = 0 ; i < iLength ; ++i ) {
00391 int iNumber;
00392 iNumber = rand() % 122;
00393
00394 if ( 48 > iNumber ) {
00395 iNumber += 48;
00396 }
00397
00398 if ( ( 57 < iNumber ) && ( 65 > iNumber ) ) {
00399 iNumber += 7;
00400 }
00401
00402 if ( ( 90 < iNumber ) && ( 97 > iNumber ) ) {
00403 iNumber += 6;
00404 }
00405
00406 strReturn += (char)iNumber;
00407 }
00408
00409 srand(1);
00410 return strReturn;
00411 }
00412
00413
00414
00415 inline std::string& UtilStrTrim(std::string& s,
00416 const std::string& t = UtilSpaces)
00417 {
00418 if (s.size() == 0) {
00419 return s;
00420 }
00421
00422 std::string::size_type pos = s.find_last_not_of(t);
00423
00424 if (pos != std::string::npos) {
00425 s.erase(pos + 1);
00426 pos = s.find_first_not_of(t);
00427
00428 if (pos != std::string::npos) {
00429 s.erase(0, pos);
00430 }
00431 } else {
00432 s.erase(s.begin(), s.end());
00433 }
00434
00435 return s;
00436 }
00437
00438
00439
00440 inline std::string& UtilStrToLower(std::string& s)
00441 {
00442
00443
00444 if (s.size() == 0) {
00445 return s;
00446 }
00447
00448
00449 std::transform(s.begin(), s.end(), s.begin(), std::ptr_fun<int, int>(tolower));
00450
00451
00452
00453 return s;
00454 }
00455
00456
00457
00458
00459 inline std::string& UtilStrToUpper(std::string& s)
00460 {
00461
00462
00463 int i;
00464
00465 if (s.size() == 0) {
00466 return s;
00467 }
00468
00469 for (i = 0; s[i] != '\0'; i++) {
00470 s[i] = static_cast<char>(toupper(s[i]));
00471 }
00472
00473 return s;
00474 }
00475
00476
00477
00478
00479
00480
00481 template <class T> inline int UtilGetSize(const std::vector<T>& vec)
00482 {
00483 return static_cast<int>(vec.size());
00484 }
00485
00486
00487 inline bool UtilIsInSet(const int value,
00488 const int* set,
00489 const int setSize)
00490 {
00491 int i;
00492 bool inSet = false;
00493
00494 for (i = 0; i < setSize; i++) {
00495 if (set[i] == value) {
00496 inSet = true;
00497 break;
00498 }
00499 }
00500
00501 return inSet;
00502 }
00503
00504
00505 inline int UtilNumNonzeros(const double* x,
00506 const int len,
00507 const double etol = 1.0e-8)
00508 {
00509 int i;
00510 int nzs = 0;
00511
00512 for (i = 0; i < len; i++) {
00513 if (fabs(x[i]) > etol) {
00514 nzs++;
00515 }
00516 }
00517
00518 return nzs;
00519 }
00520
00521
00522 inline double UtilFracPart(const double x)
00523 {
00524 double floor_x = floor(x);
00525 double floor_xplus = floor(x + 0.5);
00526
00527 if (fabs(floor_xplus - x) < (UtilEpsilon * (fabs(floor_xplus) + 1.0))) {
00528 return 0.0;
00529 }
00530
00531 return x - floor_x;
00532 }
00533
00534
00535 int UtilScaleDblToIntArr(const int arrLen,
00536 const double* arrDbl,
00537 int* arrInt,
00538 const double oneDbl,
00539 int* oneInt,
00540 const double epstol = UtilEpsilon);
00541
00542
00543 int UtilScaleDblToIntArr(const int arrLen,
00544 const double* arrDbl,
00545 int* arrInt,
00546 const double epstol = UtilEpsilon);
00547
00548
00549 inline bool UtilIsZero(const double x,
00550 const double etol = 1.0e-8)
00551 {
00552 return fabs(x) < etol;
00553 }
00554
00555
00556 inline std::string UtilIntToStr(const int i)
00557 {
00558 std::stringstream ss;
00559 ss << i;
00560 return ss.str();
00561 }
00562
00563
00564 inline std::string UtilDblToStr(const double x,
00565 const int precision = -1,
00566 const double tooBig = UtilSmallerThanTooBig)
00567 {
00568 std::stringstream ss;
00569
00570 if (fabs(x) > tooBig) {
00571 if (x < 0) {
00572 ss << "-INF";
00573 } else {
00574 ss << " INF";
00575 }
00576 } else {
00577 if (precision >= 0) {
00578 ss << std::setiosflags(std::ios::fixed | std::ios::showpoint);
00579 ss << std::setprecision(precision);
00580 }
00581
00582 ss << x;
00583 }
00584
00585 return ss.str();
00586 }
00587
00588
00589 inline void UtilPrintMemUsage(std::ostream* os = &std::cout,
00590 int logLevel = 0,
00591 int logLimit = 2)
00592 {
00593
00594 #if 0
00595 #if not defined(_MSC_VER)
00596
00597 if (logLevel >= logLimit) {
00598 struct mallinfo memInfo = mallinfo();
00599 double memUsage = static_cast<double>(memInfo.uordblks +
00600 memInfo.hblkhd) / 1024.0;
00601 memUsage /= 1024.0;
00602 (*os) << "memUsage = " << UtilDblToStr(memUsage, 2) << " MB\n";
00603 }
00604
00605 #endif
00606 #endif
00607 }
00608
00609
00610 template <class T>
00611 void UtilDeleteVectorPtr(std::vector<T*>& vectorPtr,
00612 typename std::vector<T*>::iterator first,
00613 typename std::vector<T*>::iterator last)
00614 {
00615 typename std::vector<T*>::iterator it;
00616
00617 for (it = first; it != last; it++) {
00618 delete *it;
00619 }
00620
00621 vectorPtr.erase(first, last);
00622 }
00623
00624
00625 template <class T> void UtilDeleteVectorPtr(std::vector<T*>& vectorPtr)
00626 {
00627 UtilDeleteVectorPtr(vectorPtr, vectorPtr.begin(), vectorPtr.end());
00628 }
00629
00630
00631 template <class T> void UtilDeleteListPtr(std::list<T*>& listPtr,
00632 typename std::list<T*>::iterator first,
00633 typename std::list<T*>::iterator last)
00634 {
00635 typename std::list<T*>::iterator it;
00636
00637 for (it = first; it != last; it++) {
00638 delete *it;
00639 }
00640
00641 listPtr.erase(first, last);
00642 }
00643
00644
00645 template <class T> void UtilDeleteListPtr(std::list<T*>& listPtr)
00646 {
00647 UtilDeleteListPtr(listPtr, listPtr.begin(), listPtr.end());
00648 }
00649
00650
00651 template <class S, class T>
00652 void UtilDeleteMapPtr(std::map<S, T*>& mapPtr,
00653 typename std::map<S, T*>::iterator first,
00654 typename std::map<S, T*>::iterator last)
00655 {
00656 typename std::map<S, T*>::iterator it;
00657
00658 for (it = first; it != last; it++) {
00659 delete (*it).second;
00660 }
00661
00662 mapPtr.erase(first, last);
00663 }
00664
00665
00666 template <class S, class T> void UtilDeleteMapPtr(std::map<S, T*>& mapPtr)
00667 {
00668 UtilDeleteMapPtr(mapPtr, mapPtr.begin(), mapPtr.end());
00669 }
00670
00671
00672 template <class S, class T>
00673 void UtilDeleteMapVecPtr(std::map<S, std::vector<T*> >& mapPtr,
00674 typename std::map<S, std::vector<T*> >::iterator first,
00675 typename std::map<S, std::vector<T*> >::iterator last)
00676 {
00677 typename std::map<S, std::vector<T*> >::iterator it;
00678
00679 for (it = first; it != last; it++) {
00680 UtilDeleteVectorPtr((*it).second);
00681 }
00682
00683 mapPtr.erase(first, last);
00684 }
00685
00686
00687 template <class S, class T>
00688 void UtilDeleteMapVecPtr(std::map<S, std::vector<T*> >& mapPtr)
00689 {
00690 UtilDeleteMapVecPtr(mapPtr, mapPtr.begin(), mapPtr.end());
00691 }
00692
00693
00694 inline bool UtilIsIntegral(const double x,
00695 const double etol = 1.0e-10)
00696 {
00697 return UtilIsZero(x - floor(x), etol) || UtilIsZero(ceil(x) - x, etol);
00698 }
00699
00700
00701 inline bool UtilIsIntegral(const double* x,
00702 const int len,
00703 const double etol = 1.0e-10)
00704 {
00705 int i;
00706
00707 for (i = 0; i < len; i++) {
00708 if (!UtilIsIntegral(x[i], etol)) {
00709 return false;
00710 }
00711 }
00712
00713 return true;
00714 }
00715
00716
00717 template <class T> inline void UtilNegateArr(const int arrLen,
00718 T* arr)
00719 {
00720 transform(arr, arr + arrLen, arr, std::negate<T>());
00721 }
00722
00723
00724 template <class T>
00725 struct AddOffset : public std::unary_function<T, T> {
00726 T m_n;
00727 T operator() (const T& k) {
00728 return k + m_n;
00729 }
00730 AddOffset(T n) : m_n (n) {};
00731 };
00732
00733
00734 template <class T> inline void UtilAddOffsetArr(const int arrLen,
00735 T offset,
00736 T* arr)
00737 {
00738 transform(arr, arr + arrLen, arr, AddOffset<T>(offset));
00739 }
00740
00741
00742 struct Perturb {
00743 double m_randLB;
00744 double m_randUB;
00745 double operator() (const double& k) {
00746 return k + UtilURand(m_randLB, m_randUB);
00747 }
00748 Perturb(double randLB, double randUB) :
00749 m_randLB(randLB), m_randUB(randUB) {};
00750 };
00751
00752
00753 inline void UtilPerturbCost(const int seed,
00754 const int arrLen,
00755 const double randLB,
00756 const double randUB,
00757 double* arr)
00758 {
00759 srand(seed);
00760 std::transform(arr, arr + arrLen, arr, Perturb(randLB, randUB));
00761 }
00762
00763
00764 inline void UtilFlipRowLtoG(const int len,
00765 double* els,
00766 char& sense,
00767 double& rhs)
00768 {
00769 if (sense == 'L') {
00770 return;
00771 }
00772
00773 if (sense == 'G') {
00774 for (int i = 0; i < len; i++) {
00775 els[i] = -els[i];
00776 }
00777
00778 sense = 'L';
00779 rhs = -rhs;
00780 }
00781
00782 assert(0);
00783 }
00784
00785
00786 inline void UtilBoundToSense(const double lb,
00787 const double ub,
00788 const double inf,
00789 char& sense,
00790 double& rhs,
00791 double& range)
00792 {
00793 range = 0.0;
00794
00795 if (lb > -inf) {
00796 if (ub < inf) {
00797 rhs = ub;
00798
00799 if (UtilIsZero(ub - lb)) {
00800 sense = 'E';
00801 } else {
00802 sense = 'R';
00803 range = ub - lb;
00804 }
00805 } else {
00806 sense = 'G';
00807 rhs = lb;
00808 }
00809 } else {
00810 if (ub < inf) {
00811 sense = 'L';
00812 rhs = ub;
00813 } else {
00814 sense = 'N';
00815 rhs = 0.0;
00816 }
00817 }
00818 }
00819
00820
00821 inline void UtilSenseToBound(const char sense,
00822 const double rhs,
00823 const double range,
00824 const double inf,
00825 double& lb,
00826 double& ub)
00827 {
00828 switch (sense) {
00829 case 'E':
00830 lb = rhs;
00831 ub = rhs;
00832 break;
00833 case 'L':
00834 lb = -inf;
00835 ub = rhs;
00836 break;
00837 case 'G':
00838 lb = rhs;
00839 ub = inf;
00840 break;
00841 case 'R':
00842 lb = rhs - range;
00843 ub = rhs;
00844 break;
00845 case 'N':
00846 lb = -inf;
00847 ub = inf;
00848 break;
00849 }
00850 }
00851
00852
00853 template<class S, class T> class UtilIsGreaterThan {
00854 public:
00855 bool operator()( const std::pair<S, T>& x,
00856 const std::pair<S, T>& y) {
00857 return x.second > y.second;
00858 }
00859 };
00860
00861
00862 template<class S, class T> class UtilIsLessThan {
00863 public:
00864 bool operator()( const std::pair<S, T>& x,
00865 const std::pair<S, T>& y) {
00866 return x.second < y.second;
00867 }
00868 };
00869
00870
00871 inline std::string UtilDirSlash()
00872 {
00873 std::string slash;
00874 #if defined(_MSC_VER)
00875 slash = "\\";
00876 #else
00877 slash = "/";
00878 #endif
00879 return slash;
00880 }
00881
00882
00883 inline int UtilOpenFile(std::ofstream& os,
00884 const char* fileName)
00885 {
00886 int status = UtilStatusOk;
00887 os.open(fileName);
00888
00889 if (!os) {
00890 std::string errMessage = "Error: Filename = ";
00891 errMessage += fileName;
00892 errMessage += " failed to open.";
00893 std::cerr << errMessage.c_str() << std::endl;
00894 fflush(stdout);
00895 status = UtilStatusFileIO;
00896 assert(os);
00897 }
00898
00899 return status;
00900 }
00901
00902
00903 inline int UtilOpenFile(std::ifstream& is,
00904 const char* fileName)
00905 {
00906 int status = UtilStatusOk;
00907 is.open(fileName);
00908
00909 if (!is) {
00910 std::string errMessage = "Error: Filename = ";
00911 errMessage += fileName;
00912 errMessage += " failed to open.";
00913 std::cerr << errMessage.c_str() << std::endl;
00914 fflush(stdout);
00915 status = UtilStatusFileIO;
00916 assert(is);
00917 }
00918
00919 return status;
00920 }
00921
00922
00923 inline int UtilOpenFile(std::ofstream& os,
00924 const std::string& fileName)
00925 {
00926 return UtilOpenFile(os, fileName.c_str());
00927 }
00928
00929
00930 inline int UtilOpenFile(std::ifstream& is,
00931 const std::string& fileName)
00932 {
00933 return UtilOpenFile(is, fileName.c_str());
00934 }
00935
00936
00937
00938 #endif