CoinUtils trunk
CoinSearchTree.hpp
Go to the documentation of this file.
00001 /* $Id$ */
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines