# CoinSearchTree.hpp

Go to the documentation of this file.

    00001 /* $Id: CoinSearchTree.hpp 1590 2013-04-10 16:48:33Z stefan $ */
    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.size();
    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

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines