- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

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