00001
00002
00003
00004
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
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
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 || candidateList_.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
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