/home/coin/SVN-release/Clp-1.7.0/CoinUtils/src/CoinSearchTree.hpp

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

Generated on Mon Apr 28 23:50:11 2008 by  doxygen 1.4.7