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