• Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

/build/buildd/coinutils-2.6.4/CoinUtils/src/CoinSearchTree.hpp

Go to the documentation of this file.
00001 /* $Id: CoinSearchTree.hpp 1191 2009-07-25 08:38:12Z forrest $ */
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 int size = candidateList_.size();
00339         if (size > 1) {
00340             CoinTreeSiblings** candidates = &candidateList_[0];
00341             CoinTreeSiblings* s = candidates[0];
00342             --candidates;
00343             int pos = 1;
00344             int 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         int pos = candidateList_.size();
00366         int 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

Generated on Fri Oct 15 2010 18:21:02 by  doxygen 1.7.1