CoinUtils trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2006, 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 CoinSearchTree_H 00007 #define CoinSearchTree_H 00008 00009 #include <vector> 00010 #include <algorithm> 00011 #include <cmath> 00012 #include <string> 00013 00014 #include "CoinFinite.hpp" 00015 #include "CoinHelperFunctions.hpp" 00016 00017 // #define DEBUG_PRINT 00018 00019 //############################################################################# 00020 00021 class BitVector128 { 00022 friend bool operator<(const BitVector128& b0, const BitVector128& b1); 00023 private: 00024 unsigned int bits_[4]; 00025 public: 00026 BitVector128(); 00027 ~BitVector128() {} 00028 void setBit(int i); 00029 void clearBit(int i); 00030 std::string str() const; 00031 }; 00032 00033 bool operator<(const BitVector128& b0, const BitVector128& b1); 00034 00035 //############################################################################# 00036 00040 class CoinTreeNode { 00041 protected: 00042 CoinTreeNode() : 00043 depth_(-1), 00044 fractionality_(-1), 00045 quality_(-COIN_DBL_MAX), 00046 true_lower_bound_(-COIN_DBL_MAX), 00047 preferred_() {} 00048 CoinTreeNode(int d, 00049 int f = -1, 00050 double q = -COIN_DBL_MAX, 00051 double tlb = -COIN_DBL_MAX, 00052 BitVector128 p = BitVector128()) : 00053 depth_(d), 00054 fractionality_(f), 00055 quality_(q), 00056 true_lower_bound_(tlb), 00057 preferred_(p) {} 00058 CoinTreeNode(const CoinTreeNode& x) : 00059 depth_(x.depth_), 00060 fractionality_(x.fractionality_), 00061 quality_(x.quality_), 00062 true_lower_bound_(x.true_lower_bound_), 00063 preferred_(x.preferred_) {} 00064 CoinTreeNode& operator=(const CoinTreeNode& x) { 00065 if (this != &x) { 00066 depth_ = x.depth_; 00067 fractionality_ = x.fractionality_; 00068 quality_ = x.quality_; 00069 true_lower_bound_ = x.true_lower_bound_; 00070 preferred_ = x.preferred_; 00071 } 00072 return *this; 00073 } 00074 private: 00076 int depth_; 00079 int fractionality_; 00083 double quality_; 00087 double true_lower_bound_; 00089 BitVector128 preferred_; 00090 public: 00091 virtual ~CoinTreeNode() {} 00092 00093 inline int getDepth() const { return depth_; } 00094 inline int getFractionality() const { return fractionality_; } 00095 inline double getQuality() const { return quality_; } 00096 inline double getTrueLB() const { return true_lower_bound_; } 00097 inline BitVector128 getPreferred() const { return preferred_; } 00098 00099 inline void setDepth(int d) { depth_ = d; } 00100 inline void setFractionality(int f) { fractionality_ = f; } 00101 inline void setQuality(double q) { quality_ = q; } 00102 inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; } 00103 inline void setPreferred(BitVector128 p) { preferred_ = p; } 00104 }; 00105 00106 //============================================================================== 00107 00108 class CoinTreeSiblings { 00109 private: 00110 CoinTreeSiblings(); 00111 CoinTreeSiblings& operator=(const CoinTreeSiblings&); 00112 private: 00113 int current_; 00114 int numSiblings_; 00115 CoinTreeNode** siblings_; 00116 public: 00117 CoinTreeSiblings(const int n, CoinTreeNode** nodes) : 00118 current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n]) 00119 { 00120 CoinDisjointCopyN(nodes, n, siblings_); 00121 } 00122 CoinTreeSiblings(const CoinTreeSiblings& s) : 00123 current_(s.current_), 00124 numSiblings_(s.numSiblings_), 00125 siblings_(new CoinTreeNode*[s.numSiblings_]) 00126 { 00127 CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_); 00128 } 00129 ~CoinTreeSiblings() { delete[] siblings_; } 00130 inline CoinTreeNode* currentNode() const { return siblings_[current_]; } 00132 inline bool advanceNode() { return ++current_ != numSiblings_; } 00133 inline int toProcess() const { return numSiblings_ - current_; } 00134 inline int size() const { return numSiblings_; } 00135 inline void printPref() const { 00136 for (int i = 0; i < numSiblings_; ++i) { 00137 std::string pref = siblings_[i]->getPreferred().str(); 00138 printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str()); 00139 } 00140 } 00141 }; 00142 00143 //############################################################################# 00144 00150 struct CoinSearchTreeComparePreferred { 00151 static inline const char* name() { return "CoinSearchTreeComparePreferred"; } 00152 inline bool operator()(const CoinTreeSiblings* x, 00153 const CoinTreeSiblings* y) const { 00154 register const CoinTreeNode* xNode = x->currentNode(); 00155 register const CoinTreeNode* yNode = y->currentNode(); 00156 const BitVector128 xPref = xNode->getPreferred(); 00157 const BitVector128 yPref = yNode->getPreferred(); 00158 bool retval = true; 00159 if (xPref < yPref) { 00160 retval = true; 00161 } else if (yPref < xPref) { 00162 retval = false; 00163 } else { 00164 retval = xNode->getQuality() < yNode->getQuality(); 00165 } 00166 #ifdef DEBUG_PRINT 00167 printf("Comparing xpref (%s) and ypref (%s) : %s\n", 00168 xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F"); 00169 #endif 00170 return retval; 00171 } 00172 }; 00173 00174 //----------------------------------------------------------------------------- 00176 struct CoinSearchTreeCompareDepth { 00177 static inline const char* name() { return "CoinSearchTreeCompareDepth"; } 00178 inline bool operator()(const CoinTreeSiblings* x, 00179 const CoinTreeSiblings* y) const { 00180 #if 1 00181 return x->currentNode()->getDepth() >= y->currentNode()->getDepth(); 00182 #else 00183 if(x->currentNode()->getDepth() > y->currentNode()->getDepth()) 00184 return 1; 00185 if(x->currentNode()->getDepth() == y->currentNode()->getDepth() && 00186 x->currentNode()->getQuality() <= y->currentNode()->getQuality()) 00187 return 1; 00188 return 0; 00189 #endif 00190 } 00191 }; 00192 00193 //----------------------------------------------------------------------------- 00194 /* Breadth First Search */ 00195 struct CoinSearchTreeCompareBreadth { 00196 static inline const char* name() { return "CoinSearchTreeCompareBreadth"; } 00197 inline bool operator()(const CoinTreeSiblings* x, 00198 const CoinTreeSiblings* y) const { 00199 return x->currentNode()->getDepth() < y->currentNode()->getDepth(); 00200 } 00201 }; 00202 00203 //----------------------------------------------------------------------------- 00205 struct CoinSearchTreeCompareBest { 00206 static inline const char* name() { return "CoinSearchTreeCompareBest"; } 00207 inline bool operator()(const CoinTreeSiblings* x, 00208 const CoinTreeSiblings* y) const { 00209 return x->currentNode()->getQuality() < y->currentNode()->getQuality(); 00210 } 00211 }; 00212 00213 //############################################################################# 00214 00215 class CoinSearchTreeBase 00216 { 00217 private: 00218 CoinSearchTreeBase(const CoinSearchTreeBase&); 00219 CoinSearchTreeBase& operator=(const CoinSearchTreeBase&); 00220 00221 protected: 00222 std::vector<CoinTreeSiblings*> candidateList_; 00223 int numInserted_; 00224 int size_; 00225 00226 protected: 00227 CoinSearchTreeBase() : candidateList_(), numInserted_(0), size_(0) {} 00228 00229 virtual void realpop() = 0; 00230 virtual void realpush(CoinTreeSiblings* s) = 0; 00231 virtual void fixTop() = 0; 00232 00233 public: 00234 virtual ~CoinSearchTreeBase() {} 00235 virtual const char* compName() const = 0; 00236 00237 inline const std::vector<CoinTreeSiblings*>& getCandidates() const { 00238 return candidateList_; 00239 } 00240 inline bool empty() const { return candidateList_.empty(); } 00241 inline int size() const { return size_; } 00242 inline int numInserted() const { return numInserted_; } 00243 inline CoinTreeNode* top() const { 00244 if (size_ == 0) 00245 return NULL; 00246 #ifdef DEBUG_PRINT 00247 char output[44]; 00248 output[43] = 0; 00249 candidateList_.front()->currentNode()->getPreferred().print(output); 00250 printf("top's pref: %s\n", output); 00251 #endif 00252 return candidateList_.front()->currentNode(); 00253 } 00257 inline void pop() { 00258 CoinTreeSiblings* s = candidateList_.front(); 00259 if (!s->advanceNode()) { 00260 realpop(); 00261 delete s; 00262 } else { 00263 fixTop(); 00264 } 00265 --size_; 00266 } 00267 inline void push(int numNodes, CoinTreeNode** nodes, 00268 const bool incrInserted = true) { 00269 CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes); 00270 realpush(s); 00271 if (incrInserted) { 00272 numInserted_ += numNodes; 00273 } 00274 size_ += numNodes; 00275 } 00276 inline void push(const CoinTreeSiblings& sib, 00277 const bool incrInserted = true) { 00278 CoinTreeSiblings* s = new CoinTreeSiblings(sib); 00279 #ifdef DEBUG_PRINT 00280 s->printPref(); 00281 #endif 00282 realpush(s); 00283 if (incrInserted) { 00284 numInserted_ += sib.toProcess(); 00285 } 00286 size_ += sib.size(); 00287 } 00288 }; 00289 00290 //############################################################################# 00291 00292 // #define CAN_TRUST_STL_HEAP 00293 #ifdef CAN_TRUST_STL_HEAP 00294 00295 template <class Comp> 00296 class CoinSearchTree : public CoinSearchTreeBase 00297 { 00298 private: 00299 Comp comp_; 00300 protected: 00301 virtual void realpop() { 00302 candidateList_.pop_back(); 00303 } 00304 virtual void fixTop() { 00305 CoinTreeSiblings* s = top(); 00306 realpop(); 00307 push(s, false); 00308 } 00309 virtual void realpush(CoinTreeSiblings* s) { 00310 nodes_.push_back(s); 00311 std::push_heap(candidateList_.begin(), candidateList_.end(), comp_); 00312 } 00313 public: 00314 CoinSearchTree() : CoinSearchTreeBase(), comp_() {} 00315 CoinSearchTree(const CoinSearchTreeBase& t) : 00316 CoinSearchTreeBase(), comp_() { 00317 candidateList_ = t.getCandidates(); 00318 std::make_heap(candidateList_.begin(), candidateList_.end(), comp_); 00319 numInserted_ = t.numInserted_; 00320 size_ = t.size_; 00321 } 00322 ~CoinSearchTree() {} 00323 const char* compName() const { return Comp::name(); } 00324 }; 00325 00326 #else 00327 00328 template <class Comp> 00329 class CoinSearchTree : public CoinSearchTreeBase 00330 { 00331 private: 00332 Comp comp_; 00333 00334 protected: 00335 virtual void realpop() { 00336 candidateList_[0] = candidateList_.back(); 00337 candidateList_.pop_back(); 00338 fixTop(); 00339 } 00341 virtual void fixTop() { 00342 const size_t size = candidateList_.size(); 00343 if (size > 1) { 00344 CoinTreeSiblings** candidates = &candidateList_[0]; 00345 CoinTreeSiblings* s = candidates[0]; 00346 --candidates; 00347 size_t pos = 1; 00348 size_t ch; 00349 for (ch = 2; ch < size; pos = ch, ch *= 2) { 00350 if (comp_(candidates[ch+1], candidates[ch])) 00351 ++ch; 00352 if (comp_(s, candidates[ch])) 00353 break; 00354 candidates[pos] = candidates[ch]; 00355 } 00356 if (ch == size) { 00357 if (comp_(candidates[ch], s)) { 00358 candidates[pos] = candidates[ch]; 00359 pos = ch; 00360 } 00361 } 00362 candidates[pos] = s; 00363 } 00364 } 00365 virtual void realpush(CoinTreeSiblings* s) { 00366 candidateList_.push_back(s); 00367 CoinTreeSiblings** candidates = &candidateList_[0]; 00368 --candidates; 00369 size_t pos = candidateList_.size(); 00370 size_t ch; 00371 for (ch = pos/2; ch != 0; pos = ch, ch /= 2) { 00372 if (comp_(candidates[ch], s)) 00373 break; 00374 candidates[pos] = candidates[ch]; 00375 } 00376 candidates[pos] = s; 00377 } 00378 00379 public: 00380 CoinSearchTree() : CoinSearchTreeBase(), comp_() {} 00381 CoinSearchTree(const CoinSearchTreeBase& t) : 00382 CoinSearchTreeBase(), comp_() { 00383 candidateList_ = t.getCandidates(); 00384 std::sort(candidateList_.begin(), candidateList_.end(), comp_); 00385 numInserted_ = t.numInserted(); 00386 size_ = t.size(); 00387 } 00388 ~CoinSearchTree() {} 00389 const char* compName() const { return Comp::name(); } 00390 }; 00391 00392 #endif 00393 00394 //############################################################################# 00395 00396 enum CoinNodeAction { 00397 CoinAddNodeToCandidates, 00398 CoinTestNodeForDiving, 00399 CoinDiveIntoNode 00400 }; 00401 00402 class CoinSearchTreeManager 00403 { 00404 private: 00405 CoinSearchTreeManager(const CoinSearchTreeManager&); 00406 CoinSearchTreeManager& operator=(const CoinSearchTreeManager&); 00407 private: 00408 CoinSearchTreeBase* candidates_; 00409 int numSolution; 00412 bool hasUB_; 00413 00415 bool recentlyReevaluatedSearchStrategy_; 00416 00417 public: 00418 CoinSearchTreeManager() : 00419 candidates_(NULL), 00420 numSolution(0), 00421 recentlyReevaluatedSearchStrategy_(true) 00422 {} 00423 virtual ~CoinSearchTreeManager() { 00424 delete candidates_; 00425 } 00426 00427 inline void setTree(CoinSearchTreeBase* t) { 00428 delete candidates_; 00429 candidates_ = t; 00430 } 00431 inline CoinSearchTreeBase* getTree() const { 00432 return candidates_; 00433 } 00434 00435 inline bool empty() const { return candidates_->empty(); } 00436 inline size_t size() const { return candidates_->size(); } 00437 inline size_t numInserted() const { return candidates_->numInserted(); } 00438 inline CoinTreeNode* top() const { return candidates_->top(); } 00439 inline void pop() { candidates_->pop(); } 00440 inline void push(CoinTreeNode* node, const bool incrInserted = true) { 00441 candidates_->push(1, &node, incrInserted); 00442 } 00443 inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) { 00444 candidates_->push(s, incrInserted); 00445 } 00446 inline void push(const int n, CoinTreeNode** nodes, 00447 const bool incrInserted = true) { 00448 candidates_->push(n, nodes, incrInserted); 00449 } 00450 00451 inline CoinTreeNode* bestQualityCandidate() const { 00452 return candidates_->top(); 00453 } 00454 inline double bestQuality() const { 00455 return candidates_->top()->getQuality(); 00456 } 00457 void newSolution(double solValue); 00458 void reevaluateSearchStrategy(); 00459 }; 00460 00461 //############################################################################# 00462 00463 #endif