CoinUtils  2.10.13
CoinSearchTree.hpp
Go to the documentation of this file.
1 /* $Id: CoinSearchTree.hpp 1824 2015-04-04 16:27:28Z tkr $ */
2 // Copyright (C) 2006, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef CoinSearchTree_H
7 #define CoinSearchTree_H
8 
9 #include <vector>
10 #include <algorithm>
11 #include <cmath>
12 #include <string>
13 
14 #include "CoinFinite.hpp"
15 #include "CoinHelperFunctions.hpp"
16 
17 // #define DEBUG_PRINT
18 
19 //#############################################################################
20 
21 class BitVector128 {
22  friend bool operator<(const BitVector128& b0, const BitVector128& b1);
23 private:
24  unsigned int bits_[4];
25 public:
26  BitVector128();
27  BitVector128(unsigned int bits[4]);
29  void set(unsigned int bits[4]);
30  void setBit(int i);
31  void clearBit(int i);
32  std::string str() const;
33 };
34 
35 bool operator<(const BitVector128& b0, const BitVector128& b1);
36 
37 //#############################################################################
38 
42 class CoinTreeNode {
43 protected:
45  depth_(-1),
46  fractionality_(-1),
47  quality_(-COIN_DBL_MAX),
48  true_lower_bound_(-COIN_DBL_MAX),
49  preferred_() {}
50  CoinTreeNode(int d,
51  int f = -1,
52  double q = -COIN_DBL_MAX,
53  double tlb = -COIN_DBL_MAX,
54  BitVector128 p = BitVector128()) :
55  depth_(d),
56  fractionality_(f),
57  quality_(q),
58  true_lower_bound_(tlb),
59  preferred_(p) {}
61  depth_(x.depth_),
62  fractionality_(x.fractionality_),
63  quality_(x.quality_),
64  true_lower_bound_(x.true_lower_bound_),
65  preferred_(x.preferred_) {}
67  if (this != &x) {
68  depth_ = x.depth_;
69  fractionality_ = x.fractionality_;
70  quality_ = x.quality_;
71  true_lower_bound_ = x.true_lower_bound_;
72  preferred_ = x.preferred_;
73  }
74  return *this;
75  }
76 private:
78  int depth_;
81  int fractionality_;
85  double quality_;
89  double true_lower_bound_;
91  BitVector128 preferred_;
92 public:
93  virtual ~CoinTreeNode() {}
94 
95  inline int getDepth() const { return depth_; }
96  inline int getFractionality() const { return fractionality_; }
97  inline double getQuality() const { return quality_; }
98  inline double getTrueLB() const { return true_lower_bound_; }
99  inline BitVector128 getPreferred() const { return preferred_; }
100 
101  inline void setDepth(int d) { depth_ = d; }
102  inline void setFractionality(int f) { fractionality_ = f; }
103  inline void setQuality(double q) { quality_ = q; }
104  inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
105  inline void setPreferred(BitVector128 p) { preferred_ = p; }
106 };
107 
108 //==============================================================================
109 
111 private:
113  CoinTreeSiblings& operator=(const CoinTreeSiblings&);
114 private:
115  int current_;
116  int numSiblings_;
117  CoinTreeNode** siblings_;
118 public:
119  CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
120  current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n])
121  {
122  CoinDisjointCopyN(nodes, n, siblings_);
123  }
125  current_(s.current_),
126  numSiblings_(s.numSiblings_),
127  siblings_(new CoinTreeNode*[s.numSiblings_])
128  {
129  CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_);
130  }
131  ~CoinTreeSiblings() { delete[] siblings_; }
132  inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
134  inline bool advanceNode() { return ++current_ != numSiblings_; }
135  inline int toProcess() const { return numSiblings_ - current_; }
136  inline int size() const { return numSiblings_; }
137  inline void printPref() const {
138  for (int i = 0; i < numSiblings_; ++i) {
139  std::string pref = siblings_[i]->getPreferred().str();
140  printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
141  }
142  }
143 };
144 
145 //#############################################################################
146 
153  static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
154  inline bool operator()(const CoinTreeSiblings* x,
155  const CoinTreeSiblings* y) const {
156  register const CoinTreeNode* xNode = x->currentNode();
157  register const CoinTreeNode* yNode = y->currentNode();
158  const BitVector128 xPref = xNode->getPreferred();
159  const BitVector128 yPref = yNode->getPreferred();
160  bool retval = true;
161  if (xPref < yPref) {
162  retval = true;
163  } else if (yPref < xPref) {
164  retval = false;
165  } else {
166  retval = xNode->getQuality() < yNode->getQuality();
167  }
168 #ifdef DEBUG_PRINT
169  printf("Comparing xpref (%s) and ypref (%s) : %s\n",
170  xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
171 #endif
172  return retval;
173  }
174 };
175 
176 //-----------------------------------------------------------------------------
179  static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
180  inline bool operator()(const CoinTreeSiblings* x,
181  const CoinTreeSiblings* y) const {
182 #if 1
183  return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
184 #else
185  if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
186  return 1;
187  if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
188  x->currentNode()->getQuality() <= y->currentNode()->getQuality())
189  return 1;
190  return 0;
191 #endif
192  }
193 };
194 
195 //-----------------------------------------------------------------------------
196 /* Breadth First Search */
198  static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
199  inline bool operator()(const CoinTreeSiblings* x,
200  const CoinTreeSiblings* y) const {
201  return x->currentNode()->getDepth() < y->currentNode()->getDepth();
202  }
203 };
204 
205 //-----------------------------------------------------------------------------
208  static inline const char* name() { return "CoinSearchTreeCompareBest"; }
209  inline bool operator()(const CoinTreeSiblings* x,
210  const CoinTreeSiblings* y) const {
211  return x->currentNode()->getQuality() < y->currentNode()->getQuality();
212  }
213 };
214 
215 //#############################################################################
216 
218 {
219 private:
221  CoinSearchTreeBase& operator=(const CoinSearchTreeBase&);
222 
223 protected:
224  std::vector<CoinTreeSiblings*> candidateList_;
226  int size_;
227 
228 protected:
230 
231  virtual void realpop() = 0;
232  virtual void realpush(CoinTreeSiblings* s) = 0;
233  virtual void fixTop() = 0;
234 
235 public:
236  virtual ~CoinSearchTreeBase() {}
237  virtual const char* compName() const = 0;
238 
239  inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
240  return candidateList_;
241  }
242  inline bool empty() const { return candidateList_.empty(); }
243  inline int size() const { return size_; }
244  inline int numInserted() const { return numInserted_; }
245  inline CoinTreeNode* top() const {
246  if (size_ == 0 || candidateList_.size() == 0)
247  return NULL;
248 #ifdef DEBUG_PRINT
249  char output[44];
250  output[43] = 0;
251  candidateList_.front()->currentNode()->getPreferred().print(output);
252  printf("top's pref: %s\n", output);
253 #endif
254  return candidateList_.front()->currentNode();
255  }
259  inline void pop() {
260  CoinTreeSiblings* s = candidateList_.front();
261  if (!s->advanceNode()) {
262  realpop();
263  delete s;
264  } else {
265  fixTop();
266  }
267  --size_;
268  }
269  inline void push(int numNodes, CoinTreeNode** nodes,
270  const bool incrInserted = true) {
271  CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
272  realpush(s);
273  if (incrInserted) {
274  numInserted_ += numNodes;
275  }
276  size_ += numNodes;
277  }
278  inline void push(const CoinTreeSiblings& sib,
279  const bool incrInserted = true) {
280  CoinTreeSiblings* s = new CoinTreeSiblings(sib);
281 #ifdef DEBUG_PRINT
282  s->printPref();
283 #endif
284  realpush(s);
285  if (incrInserted) {
286  numInserted_ += sib.toProcess();
287  }
288  size_ += sib.toProcess();
289  }
290 };
291 
292 //#############################################################################
293 
294 // #define CAN_TRUST_STL_HEAP
295 #ifdef CAN_TRUST_STL_HEAP
296 
297 template <class Comp>
298 class CoinSearchTree : public CoinSearchTreeBase
299 {
300 private:
301  Comp comp_;
302 protected:
303  virtual void realpop() {
304  candidateList_.pop_back();
305  }
306  virtual void fixTop() {
307  CoinTreeSiblings* s = top();
308  realpop();
309  push(s, false);
310  }
311  virtual void realpush(CoinTreeSiblings* s) {
312  nodes_.push_back(s);
313  std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
314  }
315 public:
316  CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
318  CoinSearchTreeBase(), comp_() {
320  std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
322  size_ = t.size_;
323  }
324  ~CoinSearchTree() {}
325  const char* compName() const { return Comp::name(); }
326 };
327 
328 #else
329 
330 template <class Comp>
332 {
333 private:
334  Comp comp_;
335 
336 protected:
337  virtual void realpop() {
338  candidateList_[0] = candidateList_.back();
339  candidateList_.pop_back();
340  fixTop();
341  }
343  virtual void fixTop() {
344  const size_t size = candidateList_.size();
345  if (size > 1) {
346  CoinTreeSiblings** candidates = &candidateList_[0];
347  CoinTreeSiblings* s = candidates[0];
348  --candidates;
349  size_t pos = 1;
350  size_t ch;
351  for (ch = 2; ch < size; pos = ch, ch *= 2) {
352  if (comp_(candidates[ch+1], candidates[ch]))
353  ++ch;
354  if (comp_(s, candidates[ch]))
355  break;
356  candidates[pos] = candidates[ch];
357  }
358  if (ch == size) {
359  if (comp_(candidates[ch], s)) {
360  candidates[pos] = candidates[ch];
361  pos = ch;
362  }
363  }
364  candidates[pos] = s;
365  }
366  }
367  virtual void realpush(CoinTreeSiblings* s) {
368  candidateList_.push_back(s);
369  CoinTreeSiblings** candidates = &candidateList_[0];
370  --candidates;
371  size_t pos = candidateList_.size();
372  size_t ch;
373  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
374  if (comp_(candidates[ch], s))
375  break;
376  candidates[pos] = candidates[ch];
377  }
378  candidates[pos] = s;
379  }
380 
381 public:
384  CoinSearchTreeBase(), comp_() {
386  std::sort(candidateList_.begin(), candidateList_.end(), comp_);
388  size_ = t.size();
389  }
390  virtual ~CoinSearchTree() {}
391  const char* compName() const { return Comp::name(); }
392 };
393 
394 #endif
395 
396 //#############################################################################
397 
402 };
403 
405 {
406 private:
408  CoinSearchTreeManager& operator=(const CoinSearchTreeManager&);
409 private:
410  CoinSearchTreeBase* candidates_;
411  int numSolution;
414  bool hasUB_;
415 
417  bool recentlyReevaluatedSearchStrategy_;
418 
419 public:
421  candidates_(NULL),
422  numSolution(0),
423  recentlyReevaluatedSearchStrategy_(true)
424  {}
426  delete candidates_;
427  }
428 
429  inline void setTree(CoinSearchTreeBase* t) {
430  delete candidates_;
431  candidates_ = t;
432  }
433  inline CoinSearchTreeBase* getTree() const {
434  return candidates_;
435  }
436 
437  inline bool empty() const { return candidates_->empty(); }
438  inline size_t size() const { return candidates_->size(); }
439  inline size_t numInserted() const { return candidates_->numInserted(); }
440  inline CoinTreeNode* top() const { return candidates_->top(); }
441  inline void pop() { candidates_->pop(); }
442  inline void push(CoinTreeNode* node, const bool incrInserted = true) {
443  candidates_->push(1, &node, incrInserted);
444  }
445  inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
446  candidates_->push(s, incrInserted);
447  }
448  inline void push(const int n, CoinTreeNode** nodes,
449  const bool incrInserted = true) {
450  candidates_->push(n, nodes, incrInserted);
451  }
452 
454  return candidates_->top();
455  }
456  inline double bestQuality() const {
457  return candidates_->top()->getQuality();
458  }
459  void newSolution(double solValue);
461 };
462 
463 //#############################################################################
464 
465 #endif
const char * compName() const
virtual void realpop()=0
bool operator<(const BitVector128 &b0, const BitVector128 &b1)
void CoinDisjointCopyN(register const T *from, const int size, register T *to)
This helper function copies an array to another location.
std::string str() const
int getFractionality() const
CoinTreeNode * top() const
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
double getQuality() const
virtual void realpop()
virtual void fixTop()
After changing data in the top node, fix the heap.
void push(CoinTreeNode *node, const bool incrInserted=true)
void setBit(int i)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
CoinNodeAction
void setQuality(double q)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
BitVector128 getPreferred() const
CoinSearchTreeBase * getTree() const
CoinTreeNode * top() const
CoinSearchTree(const CoinSearchTreeBase &t)
Function objects to compare search tree nodes.
int toProcess() const
bool advanceNode()
returns false if cannot be advanced
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
virtual const char * compName() const =0
std::vector< CoinTreeSiblings * > candidateList_
CoinTreeNode & operator=(const CoinTreeNode &x)
int getDepth() const
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
static const char * name()
void setDepth(int d)
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
const std::vector< CoinTreeSiblings * > & getCandidates() const
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
void newSolution(double solValue)
CoinTreeSiblings(const CoinTreeSiblings &s)
Depth First Search.
static const char * name()
CoinTreeNode(int d, int f=-1, double q=-COIN_DBL_MAX, double tlb=-COIN_DBL_MAX, BitVector128 p=BitVector128())
double bestQuality() const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
size_t numInserted() const
virtual ~CoinSearchTree()
static const char * name()
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
double getTrueLB() const
void setTree(CoinSearchTreeBase *t)
CoinTreeNode(const CoinTreeNode &x)
A class from which the real tree nodes should be derived from.
virtual void realpush(CoinTreeSiblings *s)
void setPreferred(BitVector128 p)
void clearBit(int i)
virtual void fixTop()=0
CoinTreeNode * bestQualityCandidate() const
void setFractionality(int f)
void pop()
pop will advance the next pointer among the siblings on the top and then moves the top to its correct...
CoinTreeNode * currentNode() const
const double COIN_DBL_MAX
Definition: CoinFinite.hpp:18
virtual ~CoinTreeNode()
void setTrueLB(double tlb)
void printPref() const
virtual void realpush(CoinTreeSiblings *s)=0
virtual ~CoinSearchTreeBase()