6 #ifndef CoinSearchTree_H
7 #define CoinSearchTree_H
29 void set(
unsigned int bits[4]);
32 std::string
str()
const;
104 inline void setTrueLB(
double tlb) { true_lower_bound_ = tlb; }
120 current_(0), numSiblings_(n), siblings_(new
CoinTreeNode*[n])
125 current_(s.current_),
126 numSiblings_(s.numSiblings_),
140 printf(
"prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
153 static inline const char*
name() {
return "CoinSearchTreeComparePreferred"; }
163 }
else if (yPref < xPref) {
169 printf(
"Comparing xpref (%s) and ypref (%s) : %s\n",
170 xpref.str().c_str(), ypref.str().c_str(), retval ?
"T" :
"F");
179 static inline const char*
name() {
return "CoinSearchTreeCompareDepth"; }
198 static inline const char*
name() {
return "CoinSearchTreeCompareBreadth"; }
208 static inline const char*
name() {
return "CoinSearchTreeCompareBest"; }
233 virtual void fixTop() = 0;
237 virtual const char*
compName()
const = 0;
242 inline bool empty()
const {
return candidateList_.empty(); }
251 candidateList_.front()->currentNode()->getPreferred().print(output);
252 printf(
"top's pref: %s\n", output);
254 return candidateList_.front()->currentNode();
270 const bool incrInserted =
true) {
274 numInserted_ += numNodes;
279 const bool incrInserted =
true) {
295 #ifdef CAN_TRUST_STL_HEAP
297 template <
class Comp>
325 const char*
compName()
const {
return Comp::name(); }
330 template <
class Comp>
351 for (ch = 2; ch <
size; pos = ch, ch *= 2) {
352 if (
comp_(candidates[ch+1], candidates[ch]))
354 if (
comp_(s, candidates[ch]))
356 candidates[pos] = candidates[ch];
359 if (
comp_(candidates[ch], s)) {
360 candidates[pos] = candidates[ch];
373 for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
374 if (
comp_(candidates[ch], s))
376 candidates[pos] = candidates[ch];
391 const char*
compName()
const {
return Comp::name(); }
423 recentlyReevaluatedSearchStrategy_(true)
438 inline size_t size()
const {
return candidates_->
size(); }
441 inline void pop() { candidates_->
pop(); }
443 candidates_->
push(1, &node, incrInserted);
446 candidates_->
push(s, incrInserted);
449 const bool incrInserted =
true) {
450 candidates_->
push(n, nodes, incrInserted);
454 return candidates_->
top();
const char * compName() const
CoinSearchTreeBase * candidates_
bool recentlyReevaluatedSearchStrategy_
variable used to test whether we need to reevaluate search strategy
bool operator<(const BitVector128 &b0, const BitVector128 &b1)
bool hasUB_
Whether there is an upper bound or not.
int depth_
The depth of the node in the tree.
void CoinDisjointCopyN(register const T *from, const int size, register T *to)
This helper function copies an array to another location.
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
void set(unsigned int bits[4])
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
virtual void fixTop()
After changing data in the top node, fix the heap.
void push(CoinTreeNode *node, const bool incrInserted=true)
double quality_
Some quality for the node.
void setQuality(double q)
CoinSearchTreeManager & operator=(const CoinSearchTreeManager &)
CoinTreeNode * top() const
CoinSearchTree(const CoinSearchTreeBase &t)
Function objects to compare search tree nodes.
bool advanceNode()
returns false if cannot be advanced
CoinTreeNode * currentNode() const
double true_lower_bound_
A true lower bound on the node.
static const char * name()
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
virtual const char * compName() const =0
std::vector< CoinTreeSiblings * > candidateList_
virtual ~CoinSearchTreeManager()
CoinTreeNode & operator=(const CoinTreeNode &x)
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
static const char * name()
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
int getFractionality() const
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
const std::vector< CoinTreeSiblings * > & getCandidates() const
void newSolution(double solValue)
CoinSearchTreeBase & operator=(const CoinSearchTreeBase &)
CoinTreeNode ** siblings_
CoinTreeSiblings(const CoinTreeSiblings &s)
static const char * name()
CoinTreeNode(int d, int f=-1, double q=-COIN_DBL_MAX, double tlb=-COIN_DBL_MAX, BitVector128 p=BitVector128())
int fractionality_
A measure of fractionality, e.g., the number of unsatisfied integrality requirements.
virtual ~CoinSearchTree()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
CoinSearchTreeBase * getTree() const
static const char * name()
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
CoinTreeSiblings & operator=(const CoinTreeSiblings &)
void setTree(CoinSearchTreeBase *t)
CoinTreeNode(const CoinTreeNode &x)
A class from which the real tree nodes should be derived from.
void reevaluateSearchStrategy()
virtual void realpush(CoinTreeSiblings *s)
void setPreferred(BitVector128 p)
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...
BitVector128 getPreferred() const
double bestQuality() const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
const double COIN_DBL_MAX
CoinTreeNode * bestQualityCandidate() const
double getQuality() const
CoinTreeNode * top() const
void setTrueLB(double tlb)
size_t numInserted() const
virtual void realpush(CoinTreeSiblings *s)=0
virtual ~CoinSearchTreeBase()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const