00001 // Copyright (C) 2004, International Business Machines 00002 // Corporation and others. All Rights Reserved. 00003 #ifndef CbcTree_H 00004 #define CbcTree_H 00005 00006 #include <vector> 00007 #include <algorithm> 00008 #include <cmath> 00009 00010 #include "CoinFinite.hpp" 00011 #include "CoinHelperFunctions.hpp" 00012 00018 //#define CBC_DUBIOUS_HEAP 00019 #if defined(_MSC_VER) || defined(__MNO_CYGWIN) 00020 //#define CBC_DUBIOUS_HEAP 00021 #endif 00022 #ifndef CBC_DUBIOUS_HEAP 00023 class CbcTree { 00024 00025 public: 00026 00027 // Default Constructor 00028 CbcTree (); 00029 00030 // Copy constructor 00031 CbcTree ( const CbcTree & rhs); 00032 // = operator 00033 CbcTree & operator=(const CbcTree & rhs); 00034 00035 virtual ~CbcTree(); 00036 00038 virtual CbcTree * clone() const; 00040 virtual void generateCpp( FILE * fp) {} 00041 00044 00046 void setComparison(CbcCompareBase &compare); 00047 00049 virtual CbcNode * top() const; 00050 00052 virtual void push(CbcNode * x); 00053 00055 virtual void pop() ; 00057 virtual CbcNode * bestNode(double cutoff); 00058 00060 00062 00064 virtual bool empty() ; 00065 00067 virtual int size() const 00068 {return nodes_.size();} 00069 00071 00074 00083 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00084 00086 CbcNode * bestAlternate(); 00087 00089 virtual void endSearch() {} 00090 00092 virtual double getBestPossibleObjective(); 00094 inline void resetNodeNumbers() 00095 { maximumNodeNumber_=0;} 00097 protected: 00098 std::vector <CbcNode *> nodes_; 00099 CbcCompare comparison_; 00100 00101 int maximumNodeNumber_; 00102 }; 00103 00105 #include "CoinSearchTree.hpp" 00112 class CbcNewTree : public CbcTree, public CoinSearchTreeManager { 00113 00114 public: 00115 00116 // Default Constructor 00117 CbcNewTree (); 00118 00119 // Copy constructor 00120 CbcNewTree ( const CbcNewTree & rhs); 00121 // = operator 00122 CbcNewTree & operator=(const CbcNewTree & rhs); 00123 00124 virtual ~CbcNewTree(); 00125 00127 virtual CbcNewTree * clone() const; 00129 virtual void generateCpp( FILE * fp) {} 00130 00133 00135 void setComparison(CbcCompareBase &compare); 00136 00138 virtual CbcNode * top() const; 00139 00141 virtual void push(CbcNode * x); 00142 00144 virtual void pop() ; 00146 virtual CbcNode * bestNode(double cutoff); 00147 00149 00151 00153 virtual bool empty() ; 00154 00156 inline int size() const 00157 { return nodes_.size();} 00158 00160 inline CbcNode * operator [] (int i) const 00161 { return nodes_[i];} 00162 00164 inline CbcNode * nodePointer (int i) const 00165 { return nodes_[i];} 00166 00168 00171 00180 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00181 00183 CbcNode * bestAlternate(); 00184 00186 virtual void endSearch() {} 00188 protected: 00189 00190 00191 }; 00192 #else 00193 class CbcTree { 00194 00195 public: 00196 00197 // Default Constructor 00198 CbcTree (); 00199 00200 // Copy constructor 00201 CbcTree ( const CbcTree & rhs); 00202 // = operator 00203 CbcTree & operator=(const CbcTree & rhs); 00204 00205 virtual ~CbcTree(); 00206 00208 virtual CbcTree * clone() const; 00210 virtual void generateCpp( FILE * fp) {} 00211 00214 00216 void setComparison(CbcCompareBase &compare); 00217 00219 virtual CbcNode * top() const; 00220 00222 virtual void push(CbcNode * x); 00223 00225 virtual void pop() ; 00227 virtual CbcNode * bestNode(double cutoff); 00228 00230 00232 00234 //virtual bool empty() ; 00235 00237 inline int size() const 00238 { return nodes_.size();} 00239 00241 inline CbcNode * operator [] (int i) const 00242 { return nodes_[i];} 00243 00245 inline CbcNode * nodePointer (int i) const 00246 { return nodes_[i];} 00247 00248 virtual bool empty(); 00249 //inline int size() const { return size_; } 00250 void realpop(); 00252 void fixTop(); 00253 void realpush(CbcNode * node); 00255 00258 00267 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00268 00270 CbcNode * bestAlternate(); 00271 00273 virtual void endSearch() {} 00275 inline void resetNodeNumbers() 00276 { maximumNodeNumber_=0;} 00278 protected: 00279 std::vector <CbcNode *> nodes_; 00280 CbcCompare comparison_; 00281 00282 int maximumNodeNumber_; 00283 00284 00285 }; 00286 #endif 00287 #endif 00288