- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# CoinSearchTree.hpp

Go to the documentation of this file.

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