CoinSearchTree.hpp

Go to the documentation of this file.

/* $Id: CoinSearchTree.hpp 1824 2015-04-04 16:27:28Z tkr $ */
// Copyright (C) 2006, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#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(unsigned int bits[4]);
  ~BitVector128() {}
  void set(unsigned int bits[4]);
  void setBit(int i);
  void clearBit(int i);
  std::string str() const;
};

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

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

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:
    int depth_;
    int fractionality_;
    double quality_;
    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_]; }
    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());
      }
    }
};

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

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;
  }
};

//-----------------------------------------------------------------------------
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();
  }
};

//-----------------------------------------------------------------------------
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 || candidateList_.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();
    }
    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.toProcess();
    }
};

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

// #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();
    }
    virtual void fixTop() {
        const size_t size = candidateList_.size();
        if (size > 1) {
            CoinTreeSiblings** candidates = &candidateList_[0];
            CoinTreeSiblings* s = candidates[0];
            --candidates;
            size_t pos = 1;
            size_t 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;
        size_t pos = candidateList_.size();
        size_t 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();
    }
    virtual ~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;
    bool hasUB_;

    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