This file is indexed.

/usr/include/coin/CoinSearchTree.hpp is in coinor-libcoinutils-dev 2.6.4-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
/* $Id: CoinSearchTree.hpp 1191 2009-07-25 08:38:12Z forrest $ */
#ifndef CoinSearchTree_H
#define CoinSearchTree_H

#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

#include "CoinFinite.hpp"
#include "CoinHelperFunctions.hpp"

// #define DEBUG_PRINT

//#############################################################################

class BitVector128 {
  friend bool operator<(const BitVector128& b0, const BitVector128& b1);
private:
  unsigned int bits_[4];
public:
  BitVector128();
  ~BitVector128() {}
  void setBit(int i);
  void clearBit(int i);
  std::string str() const;
};

bool operator<(const BitVector128& b0, const BitVector128& b1);

//#############################################################################

/** A class from which the real tree nodes should be derived from. Some of the
    data that undoubtedly exist in the real tree node is replicated here for
    fast access. This class is used in the various comparison functions. */
class CoinTreeNode {
protected:
    CoinTreeNode() :
	depth_(-1),
	fractionality_(-1),
	quality_(-COIN_DBL_MAX),
	true_lower_bound_(-COIN_DBL_MAX),
	preferred_() {}
    CoinTreeNode(int d,
		 int f = -1,
		 double q = -COIN_DBL_MAX,
		 double tlb = -COIN_DBL_MAX,
		 BitVector128 p = BitVector128()) :
	depth_(d),
	fractionality_(f),
	quality_(q),
	true_lower_bound_(tlb),
	preferred_(p) {}
    CoinTreeNode(const CoinTreeNode& x) :
	depth_(x.depth_),
	fractionality_(x.fractionality_),
	quality_(x.quality_),
	true_lower_bound_(x.true_lower_bound_),
	preferred_(x.preferred_) {}
    CoinTreeNode& operator=(const CoinTreeNode& x) {
        if (this != &x) {
	  depth_ = x.depth_;
	  fractionality_ = x.fractionality_;
	  quality_ = x.quality_;
	  true_lower_bound_ = x.true_lower_bound_;
	  preferred_ = x.preferred_;
	}
	return *this;
    }
private:
    /// The depth of the node in the tree
    int depth_;
    /** A measure of fractionality, e.g., the number of unsatisfied
	integrality requirements */
    int fractionality_;
    /** Some quality for the node. For normal branch-and-cut problems the LP
	relaxation value will do just fine. It is probably an OK approximation
	even if column generation is done. */
    double quality_;
    /** A true lower bound on the node. May be -infinity. For normal
	branch-and-cut problems the LP relaxation value is OK. It is different
	when column generation is done. */
    double true_lower_bound_;
    /** */
    BitVector128 preferred_;
public:
    virtual ~CoinTreeNode() {}

    inline int          getDepth()         const { return depth_; }
    inline int          getFractionality() const { return fractionality_; }
    inline double       getQuality()       const { return quality_; }
    inline double       getTrueLB()        const { return true_lower_bound_; }
    inline BitVector128 getPreferred()     const { return preferred_; }
    
    inline void setDepth(int d)              { depth_ = d; }
    inline void setFractionality(int f)      { fractionality_ = f; }
    inline void setQuality(double q)         { quality_ = q; }
    inline void setTrueLB(double tlb)        { true_lower_bound_ = tlb; }
    inline void setPreferred(BitVector128 p) { preferred_ = p; }
};

//==============================================================================

class CoinTreeSiblings {
private:
    CoinTreeSiblings();
    CoinTreeSiblings& operator=(const CoinTreeSiblings&);
private:
    int current_;
    int numSiblings_;
    CoinTreeNode** siblings_;
public:
    CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
	current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n])
    {
	CoinDisjointCopyN(nodes, n, siblings_);
    }
    CoinTreeSiblings(const CoinTreeSiblings& s) :
	current_(s.current_),
	numSiblings_(s.numSiblings_),
	siblings_(new CoinTreeNode*[s.numSiblings_])
    {
	CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_);
    }
    ~CoinTreeSiblings() { delete[] siblings_; }
    inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
    /** returns false if cannot be advanced */
    inline bool advanceNode() { return ++current_ != numSiblings_; }
    inline int toProcess() const { return numSiblings_ - current_; }
    inline int size() const { return numSiblings_; }
    inline void printPref() const {
      for (int i = 0; i < numSiblings_; ++i) {
	std::string pref = siblings_[i]->getPreferred().str();
	printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
      }
    }
};

//#############################################################################

/** Function objects to compare search tree nodes. The comparison function
    must return true if the first argument is "better" than the second one,
    i.e., it should be processed first. */
/*@{*/
/** Depth First Search. */
struct CoinSearchTreeComparePreferred {
  static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
  inline bool operator()(const CoinTreeSiblings* x,
			 const CoinTreeSiblings* y) const {
    register const CoinTreeNode* xNode = x->currentNode();
    register const CoinTreeNode* yNode = y->currentNode();
    const BitVector128 xPref = xNode->getPreferred();
    const BitVector128 yPref = yNode->getPreferred();
    bool retval = true;
    if (xPref < yPref) {
      retval = true;
    } else if (yPref < xPref) {
      retval = false;
    } else {
      retval = xNode->getQuality() < yNode->getQuality();
    }
#ifdef DEBUG_PRINT
    printf("Comparing xpref (%s) and ypref (%s) : %s\n",
	   xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
#endif
    return retval;
  }
};

//-----------------------------------------------------------------------------
/** Depth First Search. */
struct CoinSearchTreeCompareDepth {
  static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
  inline bool operator()(const CoinTreeSiblings* x,
			 const CoinTreeSiblings* y) const {
#if 1
    return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
#else
    if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
      return 1;
    if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
       x->currentNode()->getQuality() <= y->currentNode()->getQuality())
      return 1;
    return 0;
#endif
  }
};

//-----------------------------------------------------------------------------
/* Breadth First Search */
struct CoinSearchTreeCompareBreadth {
  static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
  inline bool operator()(const CoinTreeSiblings* x,
			 const CoinTreeSiblings* y) const {
    return x->currentNode()->getDepth() < y->currentNode()->getDepth();
  }
};

//-----------------------------------------------------------------------------
/** Best first search */
struct CoinSearchTreeCompareBest {
  static inline const char* name() { return "CoinSearchTreeCompareBest"; }
  inline bool operator()(const CoinTreeSiblings* x,
			 const CoinTreeSiblings* y) const {
    return x->currentNode()->getQuality() < y->currentNode()->getQuality();
  }
};

//#############################################################################

class CoinSearchTreeBase
{
private:
    CoinSearchTreeBase(const CoinSearchTreeBase&);
    CoinSearchTreeBase& operator=(const CoinSearchTreeBase&);

protected:
    std::vector<CoinTreeSiblings*> candidateList_;
    int numInserted_;
    int size_;

protected:
    CoinSearchTreeBase() : candidateList_(), numInserted_(0), size_(0) {}

    virtual void realpop() = 0;
    virtual void realpush(CoinTreeSiblings* s) = 0;
    virtual void fixTop() = 0;

public:
    virtual ~CoinSearchTreeBase() {}
    virtual const char* compName() const = 0;

    inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
	return candidateList_;
    }
    inline bool empty() const { return candidateList_.empty(); }
    inline int size() const { return size_; }
    inline int numInserted() const { return numInserted_; }
    inline CoinTreeNode* top() const {
      if (size_ == 0)
	return NULL;
#ifdef DEBUG_PRINT
      char output[44];
      output[43] = 0;
      candidateList_.front()->currentNode()->getPreferred().print(output);
      printf("top's pref: %s\n", output);
#endif
      return candidateList_.front()->currentNode();
    }
    /** pop will advance the \c next pointer among the siblings on the top and
	then moves the top to its correct position. #realpop is the method
	that actually removes the element from the heap */
    inline void pop() {
	CoinTreeSiblings* s = candidateList_.front();
	if (!s->advanceNode()) {
	    realpop();
	    delete s;
	} else {
	    fixTop();
	}
	--size_;
    }
    inline void push(int numNodes, CoinTreeNode** nodes,
		     const bool incrInserted = true) {
	CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
	realpush(s);
	if (incrInserted) {
	    numInserted_ += numNodes;
	}
	size_ += numNodes;
    }
    inline void push(const CoinTreeSiblings& sib,
		     const bool incrInserted = true) {
	CoinTreeSiblings* s = new CoinTreeSiblings(sib);
#ifdef DEBUG_PRINT
	s->printPref();
#endif
	realpush(s);
	if (incrInserted) {
	    numInserted_ += sib.toProcess();
	}
	size_ += sib.size();
    }
};

//#############################################################################

// #define CAN_TRUST_STL_HEAP
#ifdef CAN_TRUST_STL_HEAP

template <class Comp>
class CoinSearchTree : public CoinSearchTreeBase
{
private:
    Comp comp_;
protected:
    virtual void realpop() {
	candidateList_.pop_back();
    }
    virtual void fixTop() {
	CoinTreeSiblings* s = top();
	realpop();
	push(s, false);
    }
    virtual void realpush(CoinTreeSiblings* s) {
	nodes_.push_back(s);
	std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
    }
public:
    CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
    CoinSearchTree(const CoinSearchTreeBase& t) :
	CoinSearchTreeBase(), comp_() {
	candidateList_ = t.getCandidates();
	std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
	numInserted_ = t.numInserted_;
	size_ = t.size_;
    }
    ~CoinSearchTree() {}
    const char* compName() const { return Comp::name(); }
};

#else

template <class Comp>
class CoinSearchTree : public CoinSearchTreeBase
{
private:
    Comp comp_;

protected:
    virtual void realpop() {
	candidateList_[0] = candidateList_.back();
	candidateList_.pop_back();
	fixTop();
    }
    /** After changing data in the top node, fix the heap */
    virtual void fixTop() {
	const int size = candidateList_.size();
	if (size > 1) {
	    CoinTreeSiblings** candidates = &candidateList_[0];
	    CoinTreeSiblings* s = candidates[0];
	    --candidates;
	    int pos = 1;
	    int ch;
	    for (ch = 2; ch < size; pos = ch, ch *= 2) {
		if (comp_(candidates[ch+1], candidates[ch]))
		    ++ch;
		if (comp_(s, candidates[ch]))
		    break;
		candidates[pos] = candidates[ch];
	    }
	    if (ch == size) {
		if (comp_(candidates[ch], s)) {
		    candidates[pos] = candidates[ch];
		    pos = ch;
		}
	    }
	    candidates[pos] = s;
	}
    }
    virtual void realpush(CoinTreeSiblings* s) {
	candidateList_.push_back(s);
	CoinTreeSiblings** candidates = &candidateList_[0];
	--candidates;
	int pos = candidateList_.size();
	int ch;
	for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
	    if (comp_(candidates[ch], s))
		break;
	    candidates[pos] = candidates[ch];
	}
	candidates[pos] = s;
    }
  
public:
    CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
    CoinSearchTree(const CoinSearchTreeBase& t) :
	CoinSearchTreeBase(), comp_() {
	candidateList_ = t.getCandidates();
	std::sort(candidateList_.begin(), candidateList_.end(), comp_);
	numInserted_ = t.numInserted();
	size_ = t.size();
    }
    ~CoinSearchTree() {}
    const char* compName() const { return Comp::name(); }
};

#endif

//#############################################################################

enum CoinNodeAction {
    CoinAddNodeToCandidates,
    CoinTestNodeForDiving,
    CoinDiveIntoNode
};

class CoinSearchTreeManager
{
private:
    CoinSearchTreeManager(const CoinSearchTreeManager&);
    CoinSearchTreeManager& operator=(const CoinSearchTreeManager&);
private:
    CoinSearchTreeBase* candidates_;
    int numSolution;
    /** Whether there is an upper bound or not. The upper bound may have come
	as input, not necessarily from a solution */
    bool hasUB_;

    /** variable used to test whether we need to reevaluate search strategy */
    bool recentlyReevaluatedSearchStrategy_;
    
public:
    CoinSearchTreeManager() :
	candidates_(NULL),
	numSolution(0),
	recentlyReevaluatedSearchStrategy_(true)
    {}
    virtual ~CoinSearchTreeManager() {
	delete candidates_;
    }
    
    inline void setTree(CoinSearchTreeBase* t) {
	delete candidates_;
	candidates_ = t;
    }
    inline CoinSearchTreeBase* getTree() const {
	return candidates_;
    }

    inline bool empty() const { return candidates_->empty(); }
    inline size_t size() const { return candidates_->size(); }
    inline size_t numInserted() const { return candidates_->numInserted(); }
    inline CoinTreeNode* top() const { return candidates_->top(); }
    inline void pop() { candidates_->pop(); }
    inline void push(CoinTreeNode* node, const bool incrInserted = true) {
	candidates_->push(1, &node, incrInserted);
    }
    inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
	candidates_->push(s, incrInserted);
    }
    inline void push(const int n, CoinTreeNode** nodes,
		     const bool incrInserted = true) {
	candidates_->push(n, nodes, incrInserted);
    }

    inline CoinTreeNode* bestQualityCandidate() const {
	return candidates_->top();
    }
    inline double bestQuality() const {
	return candidates_->top()->getQuality();
    }
    void newSolution(double solValue);
    void reevaluateSearchStrategy();
};

//#############################################################################

#endif