1/* $Id: CoinSearchTree.cpp 1373 2011-01-03 23:57:44Z lou $ */
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#include <cstdio>
7#include "CoinSearchTree.hpp"
8
9BitVector128::BitVector128()
10{
11 bits_[0] = 0;
12 bits_[1] = 0;
13 bits_[2] = 0;
14 bits_[3] = 0;
15}
16
17void
18BitVector128::setBit(int i)
19{
20 int byte = i >> 5;
21 int bit = i & 31;
22 bits_[byte] |= (1 << bit);
23}
24
25void
26BitVector128::clearBit(int i)
27{
28 int byte = i >> 5;
29 int bit = i & 31;
30 bits_[byte] &= ~(1 << bit);
31}
32
33std::string
34BitVector128::str() const
35{
36 char output[33];
37 output[32] = 0;
38 sprintf(output, "%08X%08X%08X%08X",
39 bits_[3], bits_[2], bits_[1], bits_[0]);
40 return output;
41}
42
43bool
44operator<(const BitVector128& b0, const BitVector128& b1)
45{
46 if (b0.bits_[3] < b1.bits_[3])
47 return true;
48 if (b0.bits_[3] > b1.bits_[3])
49 return false;
50 if (b0.bits_[2] < b1.bits_[2])
51 return true;
52 if (b0.bits_[2] > b1.bits_[2])
53 return false;
54 if (b0.bits_[1] < b1.bits_[1])
55 return true;
56 if (b0.bits_[1] > b1.bits_[1])
57 return false;
58 return (b0.bits_[0] < b1.bits_[0]);
59}
60
61void
62CoinSearchTreeManager::newSolution(double solValue)
63{
64 ++numSolution;
65 hasUB_ = true;
66 CoinTreeNode* top = candidates_->top();
67 const double q = top ? top->getQuality() : solValue;
68 const bool switchToDFS = fabs(q) < 1e-3 ?
69 (fabs(solValue) < 0.005) : ((solValue-q)/fabs(q) < 0.005);
70 if (switchToDFS &&
71 dynamic_cast<CoinSearchTree<CoinSearchTreeCompareDepth>*>(candidates_) == NULL) {
72 CoinSearchTree<CoinSearchTreeCompareDepth>* cands =
73 new CoinSearchTree<CoinSearchTreeCompareDepth>(*candidates_);
74 delete candidates_;
75 candidates_ = cands;
76 }
77}
78
79void
80CoinSearchTreeManager::reevaluateSearchStrategy()
81{
82 const int n = candidates_->numInserted() % 1000;
83 /* the tests below ensure that even if this method is not invoked after
84 every push(), the search strategy will be reevaluated when n is ~500 */
85 if (recentlyReevaluatedSearchStrategy_) {
86 if (n > 250 && n <= 500) {
87 recentlyReevaluatedSearchStrategy_ = false;
88 }
89 } else {
90 if (n > 500) {
91 recentlyReevaluatedSearchStrategy_ = true;
92 /* we can reevaluate things... */
93 }
94 }
95}
96