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