CoinSearchTree.hpp
Go to the documentation of this file.
1 /* $Id: CoinSearchTree.hpp 1191 2009-07-25 08:38:12Z forrest $ */
2 #ifndef CoinSearchTree_H
3 #define CoinSearchTree_H
4 
5 #include <vector>
6 #include <algorithm>
7 #include <cmath>
8 #include <string>
9 
10 #include "CoinFinite.hpp"
11 #include "CoinHelperFunctions.hpp"
12 
13 // #define DEBUG_PRINT
14 
15 //#############################################################################
16 
17 class BitVector128 {
18  friend bool operator<(const BitVector128& b0, const BitVector128& b1);
19 private:
20  unsigned int bits_[4];
21 public:
22  BitVector128();
24  void setBit(int i);
25  void clearBit(int i);
26  std::string str() const;
27 };
28 
29 bool operator<(const BitVector128& b0, const BitVector128& b1);
30 
31 //#############################################################################
32 
36 class CoinTreeNode {
37 protected:
39  depth_(-1),
40  fractionality_(-1),
43  preferred_() {}
44  CoinTreeNode(int d,
45  int f = -1,
46  double q = -COIN_DBL_MAX,
47  double tlb = -COIN_DBL_MAX,
48  BitVector128 p = BitVector128()) :
49  depth_(d),
50  fractionality_(f),
51  quality_(q),
52  true_lower_bound_(tlb),
53  preferred_(p) {}
55  depth_(x.depth_),
57  quality_(x.quality_),
61  if (this != &x) {
62  depth_ = x.depth_;
64  quality_ = x.quality_;
67  }
68  return *this;
69  }
70 private:
72  int depth_;
79  double quality_;
86 public:
87  virtual ~CoinTreeNode() {}
88 
89  inline int getDepth() const { return depth_; }
90  inline int getFractionality() const { return fractionality_; }
91  inline double getQuality() const { return quality_; }
92  inline double getTrueLB() const { return true_lower_bound_; }
93  inline BitVector128 getPreferred() const { return preferred_; }
94 
95  inline void setDepth(int d) { depth_ = d; }
96  inline void setFractionality(int f) { fractionality_ = f; }
97  inline void setQuality(double q) { quality_ = q; }
98  inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
99  inline void setPreferred(BitVector128 p) { preferred_ = p; }
100 };
101 
102 //==============================================================================
103 
105 private:
108 private:
109  int current_;
112 public:
113  CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
115  {
116  CoinDisjointCopyN(nodes, n, siblings_);
117  }
119  current_(s.current_),
122  {
124  }
125  ~CoinTreeSiblings() { delete[] siblings_; }
126  inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
128  inline bool advanceNode() { return ++current_ != numSiblings_; }
129  inline int toProcess() const { return numSiblings_ - current_; }
130  inline int size() const { return numSiblings_; }
131  inline void printPref() const {
132  for (int i = 0; i < numSiblings_; ++i) {
133  std::string pref = siblings_[i]->getPreferred().str();
134  printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
135  }
136  }
137 };
138 
139 //#############################################################################
140 
147  static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
148  inline bool operator()(const CoinTreeSiblings* x,
149  const CoinTreeSiblings* y) const {
150  register const CoinTreeNode* xNode = x->currentNode();
151  register const CoinTreeNode* yNode = y->currentNode();
152  const BitVector128 xPref = xNode->getPreferred();
153  const BitVector128 yPref = yNode->getPreferred();
154  bool retval = true;
155  if (xPref < yPref) {
156  retval = true;
157  } else if (yPref < xPref) {
158  retval = false;
159  } else {
160  retval = xNode->getQuality() < yNode->getQuality();
161  }
162 #ifdef DEBUG_PRINT
163  printf("Comparing xpref (%s) and ypref (%s) : %s\n",
164  xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
165 #endif
166  return retval;
167  }
168 };
169 
170 //-----------------------------------------------------------------------------
173  static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
174  inline bool operator()(const CoinTreeSiblings* x,
175  const CoinTreeSiblings* y) const {
176 #if 1
177  return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
178 #else
179  if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
180  return 1;
181  if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
182  x->currentNode()->getQuality() <= y->currentNode()->getQuality())
183  return 1;
184  return 0;
185 #endif
186  }
187 };
188 
189 //-----------------------------------------------------------------------------
190 /* Breadth First Search */
192  static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
193  inline bool operator()(const CoinTreeSiblings* x,
194  const CoinTreeSiblings* y) const {
195  return x->currentNode()->getDepth() < y->currentNode()->getDepth();
196  }
197 };
198 
199 //-----------------------------------------------------------------------------
202  static inline const char* name() { return "CoinSearchTreeCompareBest"; }
203  inline bool operator()(const CoinTreeSiblings* x,
204  const CoinTreeSiblings* y) const {
205  return x->currentNode()->getQuality() < y->currentNode()->getQuality();
206  }
207 };
208 
209 //#############################################################################
210 
212 {
213 private:
216 
217 protected:
218  std::vector<CoinTreeSiblings*> candidateList_;
220  int size_;
221 
222 protected:
224 
225  virtual void realpop() = 0;
226  virtual void realpush(CoinTreeSiblings* s) = 0;
227  virtual void fixTop() = 0;
228 
229 public:
230  virtual ~CoinSearchTreeBase() {}
231  virtual const char* compName() const = 0;
232 
233  inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
234  return candidateList_;
235  }
236  inline bool empty() const { return candidateList_.empty(); }
237  inline int size() const { return size_; }
238  inline int numInserted() const { return numInserted_; }
239  inline CoinTreeNode* top() const {
240  if (size_ == 0)
241  return NULL;
242 #ifdef DEBUG_PRINT
243  char output[44];
244  output[43] = 0;
245  candidateList_.front()->currentNode()->getPreferred().print(output);
246  printf("top's pref: %s\n", output);
247 #endif
248  return candidateList_.front()->currentNode();
249  }
253  inline void pop() {
254  CoinTreeSiblings* s = candidateList_.front();
255  if (!s->advanceNode()) {
256  realpop();
257  delete s;
258  } else {
259  fixTop();
260  }
261  --size_;
262  }
263  inline void push(int numNodes, CoinTreeNode** nodes,
264  const bool incrInserted = true) {
265  CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
266  realpush(s);
267  if (incrInserted) {
268  numInserted_ += numNodes;
269  }
270  size_ += numNodes;
271  }
272  inline void push(const CoinTreeSiblings& sib,
273  const bool incrInserted = true) {
274  CoinTreeSiblings* s = new CoinTreeSiblings(sib);
275 #ifdef DEBUG_PRINT
276  s->printPref();
277 #endif
278  realpush(s);
279  if (incrInserted) {
280  numInserted_ += sib.toProcess();
281  }
282  size_ += sib.size();
283  }
284 };
285 
286 //#############################################################################
287 
288 // #define CAN_TRUST_STL_HEAP
289 #ifdef CAN_TRUST_STL_HEAP
290 
291 template <class Comp>
292 class CoinSearchTree : public CoinSearchTreeBase
293 {
294 private:
295  Comp comp_;
296 protected:
297  virtual void realpop() {
298  candidateList_.pop_back();
299  }
300  virtual void fixTop() {
301  CoinTreeSiblings* s = top();
302  realpop();
303  push(s, false);
304  }
305  virtual void realpush(CoinTreeSiblings* s) {
306  nodes_.push_back(s);
307  std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
308  }
309 public:
314  std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
316  size_ = t.size_;
317  }
318  ~CoinSearchTree() {}
319  const char* compName() const { return Comp::name(); }
320 };
321 
322 #else
323 
324 template <class Comp>
326 {
327 private:
328  Comp comp_;
329 
330 protected:
331  virtual void realpop() {
332  candidateList_[0] = candidateList_.back();
333  candidateList_.pop_back();
334  fixTop();
335  }
337  virtual void fixTop() {
338  const int size = candidateList_.size();
339  if (size > 1) {
340  CoinTreeSiblings** candidates = &candidateList_[0];
341  CoinTreeSiblings* s = candidates[0];
342  --candidates;
343  int pos = 1;
344  int ch;
345  for (ch = 2; ch < size; pos = ch, ch *= 2) {
346  if (comp_(candidates[ch+1], candidates[ch]))
347  ++ch;
348  if (comp_(s, candidates[ch]))
349  break;
350  candidates[pos] = candidates[ch];
351  }
352  if (ch == size) {
353  if (comp_(candidates[ch], s)) {
354  candidates[pos] = candidates[ch];
355  pos = ch;
356  }
357  }
358  candidates[pos] = s;
359  }
360  }
361  virtual void realpush(CoinTreeSiblings* s) {
362  candidateList_.push_back(s);
363  CoinTreeSiblings** candidates = &candidateList_[0];
364  --candidates;
365  int pos = candidateList_.size();
366  int ch;
367  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
368  if (comp_(candidates[ch], s))
369  break;
370  candidates[pos] = candidates[ch];
371  }
372  candidates[pos] = s;
373  }
374 
375 public:
380  std::sort(candidateList_.begin(), candidateList_.end(), comp_);
382  size_ = t.size();
383  }
385  const char* compName() const { return Comp::name(); }
386 };
387 
388 #endif
389 
390 //#############################################################################
391 
396 };
397 
399 {
400 private:
403 private:
408  bool hasUB_;
409 
412 
413 public:
415  candidates_(NULL),
416  numSolution(0),
418  {}
420  delete candidates_;
421  }
422 
423  inline void setTree(CoinSearchTreeBase* t) {
424  delete candidates_;
425  candidates_ = t;
426  }
427  inline CoinSearchTreeBase* getTree() const {
428  return candidates_;
429  }
430 
431  inline bool empty() const { return candidates_->empty(); }
432  inline size_t size() const { return candidates_->size(); }
433  inline size_t numInserted() const { return candidates_->numInserted(); }
434  inline CoinTreeNode* top() const { return candidates_->top(); }
435  inline void pop() { candidates_->pop(); }
436  inline void push(CoinTreeNode* node, const bool incrInserted = true) {
437  candidates_->push(1, &node, incrInserted);
438  }
439  inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
440  candidates_->push(s, incrInserted);
441  }
442  inline void push(const int n, CoinTreeNode** nodes,
443  const bool incrInserted = true) {
444  candidates_->push(n, nodes, incrInserted);
445  }
446 
448  return candidates_->top();
449  }
450  inline double bestQuality() const {
451  return candidates_->top()->getQuality();
452  }
453  void newSolution(double solValue);
455 };
456 
457 //#############################################################################
458 
459 #endif