CoinSearchTree.hpp

Go to the documentation of this file.
00001 /* $Id: CoinSearchTree.hpp 1824 2015-04-04 16:27:28Z tkr $ */
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 || 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 // #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

Generated on 28 Aug 2016 for CoinUtils by  doxygen 1.6.1