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

- File List
- File Members

# /home/coin/SVN-release/Alps-1.2.1/CoinUtils/src/CoinSearchTree.hpp

Go to the documentation of this file.

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