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

- File List
- File Members

# /home/coin/SVN-release/Clp-1.5.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
    00008 #include "CoinFinite.hpp"
    00009 #include "CoinHelperFunctions.hpp"
    00010
    00011 //#############################################################################
    00012
    00016 class CoinTreeNode {
    00017 protected:
    00018     CoinTreeNode() :
    00019         depth_(-1),
    00020         quality_(-COIN_DBL_MAX),
    00021         true_lower_bound_(-COIN_DBL_MAX) {}
    00022     CoinTreeNode(int d,
    00023                  double q = -COIN_DBL_MAX,
    00024                  double tlb = -COIN_DBL_MAX /*, double f*/) :
    00025         depth_(d),
    00026         quality_(q),
    00027         true_lower_bound_(tlb)/*, fractionality_(f)*/ {}
    00028     CoinTreeNode(const CoinTreeNode& x) :
    00029         depth_(x.depth_),
    00030         quality_(x.quality_),
    00031         true_lower_bound_(x.true_lower_bound_) {}
    00032     CoinTreeNode& operator=(const CoinTreeNode& x) {
    00033         // Not worth to test (this != &x)
    00034         depth_ = x.depth_;
    00035         quality_ = x.quality_;
    00036         true_lower_bound_ = x.true_lower_bound_;
    00037         return *this;
    00038     }
    00039 private:
    00041     int depth_;
    00045     double quality_;
    00049     double true_lower_bound_;
    00052     /*double fractionality_;*/
    00053 public:
    00054     virtual ~CoinTreeNode() {}
    00055
    00056     inline int    getDepth()   const { return depth_; }
    00057     inline double getQuality() const { return quality_; }
    00058     inline double getTrueLB()  const { return true_lower_bound_; }
    00059
    00060     inline void setDepth(int d)       { depth_ = d; }
    00061     inline void setQuality(double q)  { quality_ = q; }
    00062     inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
    00063 };
    00064
    00065 class CoinTreeSiblings {
    00066 private:
    00067     CoinTreeSiblings();
    00068     CoinTreeSiblings& operator=(const CoinTreeSiblings&);
    00069 private:
    00070     int current_;
    00071     int numSiblings_;
    00072     CoinTreeNode** siblings_;
    00073 public:
    00074     CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
    00075         current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n])
    00076     {
    00077         CoinDisjointCopyN(nodes, n, siblings_);
    00078     }
    00079     CoinTreeSiblings(const CoinTreeSiblings& s) :
    00080         current_(s.current_),
    00081         numSiblings_(s.numSiblings_),
    00082         siblings_(new CoinTreeNode*[s.numSiblings_])
    00083     {
    00084         CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_);
    00085     }
    00086     ~CoinTreeSiblings() { delete[] siblings_; }
    00087     inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
    00089     inline bool advanceNode() { return ++current_ != numSiblings_; }
    00090     inline int toProcess() const { return numSiblings_ - current_; }
    00091     inline int size() const { return numSiblings_; }
    00092 };
    00093
    00094 //#############################################################################
    00095
    00101 struct CoinSearchTreeCompareDepth {
    00102     inline bool operator()(const CoinTreeSiblings* x,
    00103                            const CoinTreeSiblings* y) const {
    00104         return x->currentNode()->getDepth() > y->currentNode()->getDepth();
    00105     }
    00106 };
    00107
    00108 //-----------------------------------------------------------------------------
    00109 /* Breadth First Search */
    00110 struct CoinSearchTreeCompareBreadth {
    00111     inline bool operator()(const CoinTreeSiblings* x,
    00112                            const CoinTreeSiblings* y) const {
    00113         return x->currentNode()->getDepth() < y->currentNode()->getDepth();
    00114     }
    00115 };
    00116
    00117 //-----------------------------------------------------------------------------
    00119 struct CoinSearchTreeCompareBest {
    00120     inline bool operator()(const CoinTreeSiblings* x,
    00121                            const CoinTreeSiblings* y) const {
    00122         return x->currentNode()->getQuality() < y->currentNode()->getQuality();
    00123     }
    00124 };
    00125
    00126 //#############################################################################
    00127
    00128 class CoinSearchTreeBase
    00129 {
    00130 private:
    00131     CoinSearchTreeBase(const CoinSearchTreeBase&);
    00132     CoinSearchTreeBase& operator=(const CoinSearchTreeBase&);
    00133
    00134 protected:
    00135     std::vector<CoinTreeSiblings*> candidateList_;
    00136     int numInserted_;
    00137     int size_;
    00138
    00139 protected:
    00140     CoinSearchTreeBase() : candidateList_(), numInserted_(0), size_(0) {}
    00141
    00142     virtual void realpop() = 0;
    00143     virtual void realpush(CoinTreeSiblings* s) = 0;
    00144     virtual void fixTop() = 0;
    00145
    00146 public:
    00147     virtual ~CoinSearchTreeBase() {}
    00148
    00149     inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
    00150         return candidateList_;
    00151     }
    00152     inline bool empty() const { return candidateList_.empty(); }
    00153     inline int size() const { return size_; }
    00154     inline int numInserted() const { return numInserted_; }
    00155     inline CoinTreeNode* top() const {
    00156         return (size_ == 0) ? NULL : candidateList_.front()->currentNode();
    00157     }
    00161     inline void pop() {
    00162         CoinTreeSiblings* s = candidateList_.front();
    00163         if (!s->advanceNode()) {
    00164             realpop();
    00165             delete s;
    00166         } else {
    00167             fixTop();
    00168         }
    00169         --size_;
    00170     }
    00171     inline void push(int numNodes, CoinTreeNode** nodes,
    00172                      const bool incrInserted = true) {
    00173         CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
    00174         realpush(s);
    00175         if (incrInserted) {
    00176             numInserted_ += numNodes;
    00177         }
    00178         size_ += numNodes;
    00179     }
    00180     inline void push(const CoinTreeSiblings& sib,
    00181                      const bool incrInserted = true) {
    00182         CoinTreeSiblings* s = new CoinTreeSiblings(sib);
    00183         realpush(s);
    00184         if (incrInserted) {
    00185             numInserted_ += sib.toProcess();
    00186         }
    00187         size_ += sib.size();
    00188     }
    00189 };
    00190
    00191 //#############################################################################
    00192
    00193 #ifdef CAN_TRUST_STL_HEAP
    00194
    00195 template <class Comp>
    00196 class CoinSearchTree : public CoinSearchTreeBase
    00197 {
    00198 private:
    00199     Comp comp_;
    00200 protected:
    00201     virtual void realpop() {
    00202         candidateList_.pop();
    00203     }
    00204     virtual void fixTop() {
    00205         CoinTreeSiblings* s = top();
    00206         realpop();
    00207         push(s, false);
    00208     }
    00209     virtual void realpush(CoinTreeSiblings* s) {
    00210         nodes_.push_back(s);
    00211         std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
    00212     }
    00213 public:
    00214     CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
    00215     CoinSearchTree(const CoinSearchTreeBase& t) :
    00216         CoinSearchTreeBase(), comp_() {
    00217         candidateList_ = t.getCandidates();
    00218         std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
    00219         numInserted_ = t.numInserted_;
    00220         size_ = t.size_;
    00221     }
    00222     ~CoinSearchTree() {}
    00223 };
    00224
    00225 #else
    00226
    00227 template <class Comp>
    00228 class CoinSearchTree : public CoinSearchTreeBase
    00229 {
    00230 private:
    00231     Comp comp_;
    00232
    00233 protected:
    00234     virtual void realpop() {
    00235         candidateList_[0] = candidateList_.back();
    00236         candidateList_.pop_back();
    00237         fixTop();
    00238     }
    00240     virtual void fixTop() {
    00241         const int size = candidateList_.size();
    00242         if (size > 1) {
    00243             CoinTreeSiblings** candidates = &candidateList_[0];
    00244             CoinTreeSiblings* s = candidates[0];
    00245             --candidates;
    00246             int pos = 1;
    00247             int ch;
    00248             for (ch = 2; ch < size; pos = ch, ch *= 2) {
    00249                 if (comp_(candidates[ch+1], candidates[ch]))
    00250                     ++ch;
    00251                 if (comp_(s, candidates[ch]))
    00252                     break;
    00253                 candidates[pos] = candidates[ch];
    00254             }
    00255             if (ch == size) {
    00256                 if (comp_(candidates[ch], s)) {
    00257                     candidates[pos] = candidates[ch];
    00258                     pos = ch;
    00259                 }
    00260             }
    00261             candidates[pos] = s;
    00262         }
    00263     }
    00264     virtual void realpush(CoinTreeSiblings* s) {
    00265         candidateList_.push_back(s);
    00266         CoinTreeSiblings** candidates = &candidateList_[0];
    00267         --candidates;
    00268         int pos = candidateList_.size();
    00269         int ch;
    00270         for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
    00271             if (comp_(candidates[ch], s))
    00272                 break;
    00273             candidates[pos] = candidates[ch];
    00274         }
    00275         candidates[pos] = s;
    00276     }
    00277
    00278 public:
    00279     CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
    00280     CoinSearchTree(const CoinSearchTreeBase& t) :
    00281         CoinSearchTreeBase(), comp_() {
    00282         candidateList_ = t.getCandidates();
    00283         std::sort(candidateList_.begin(), candidateList_.end(), comp_);
    00284         numInserted_ = t.numInserted();
    00285         size_ = t.size();
    00286     }
    00287     ~CoinSearchTree() {}
    00288 };
    00289
    00290 #endif
    00291
    00292 //#############################################################################
    00293
    00294 enum CoinNodeAction {
    00295     CoinAddNodeToCandidates,
    00296     CoinTestNodeForDiving,
    00297     CoinDiveIntoNode
    00298 };
    00299
    00300 class CoinSearchTreeManager
    00301 {
    00302 private:
    00303     CoinSearchTreeManager(const CoinSearchTreeManager&);
    00304     CoinSearchTreeManager& operator=(const CoinSearchTreeManager&);
    00305 private:
    00306     CoinSearchTreeBase* candidates_;
    00307     int numSolution;
    00310     bool hasUB_;
    00311
    00313     bool recentlyReevaluatedSearchStrategy_;
    00314
    00315 public:
    00316     CoinSearchTreeManager() :
    00317         candidates_(NULL),
    00318         numSolution(0),
    00319         recentlyReevaluatedSearchStrategy_(true)
    00320     {}
    00321     virtual ~CoinSearchTreeManager() {
    00322         delete candidates_;
    00323     }
    00324
    00325     inline void setTree(CoinSearchTreeBase* t) {
    00326         delete candidates_;
    00327         candidates_ = t;
    00328     }
    00329     inline CoinSearchTreeBase* getTree() const {
    00330         return candidates_;
    00331     }
    00332
    00333     inline bool empty() const { return candidates_->empty(); }
    00334     inline size_t size() const { return candidates_->size(); }
    00335     inline size_t numInserted() const { return candidates_->numInserted(); }
    00336     inline CoinTreeNode* top() const { return candidates_->top(); }
    00337     inline void pop() { candidates_->pop(); }
    00338     inline void push(CoinTreeNode* node, const bool incrInserted = true) {
    00339         candidates_->push(1, &node, incrInserted);
    00340     }
    00341     inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
    00342         candidates_->push(s, incrInserted);
    00343     }
    00344     inline void push(const int n, CoinTreeNode** nodes,
    00345                      const bool incrInserted = true) {
    00346         candidates_->push(n, nodes, incrInserted);
    00347     }
    00348
    00349     inline CoinTreeNode* bestQualityCandidate() const {
    00350         return candidates_->top();
    00351     }
    00352     inline double bestQuality() const {
    00353         return candidates_->top()->getQuality();
    00354     }
    00355     void newSolution(double solValue);
    00356     void reevaluateSearchStrategy();
    00357 };
    00358
    00359 //#############################################################################
    00360
    00361 #endif