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