CoinSearchTree.hpp

Go to the documentation of this file.

/* $Id$ */
// 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
  {
    const CoinTreeNode *xNode = x->currentNode();
    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
 
/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/