さいてきにじゅんさく

3674 ワード

 #include <iostream>
#include <type_traits>
#include <vector>
#include <initializer_list>
#include <typeinfo>
enum:int { MAXVALUE=999 };
template<typename T=double, typename Ty=double, typename Type=double>
class BestTree{
 private:
  T** root;// . 
  Ty** e;// . 
  Type** w;// .
  std::vector<Ty> p;
  std::vector<Type> q;
  int pLength;
  
  public:
   
   template<typename X=double, typename Y=double>
   BestTree(const std::initializer_list<X>& _p, const std::initializer_list<Y>& _q);// _p , _q . 
   
   ~BestTree();
   void OptimalBST();
   void Subtree();
   
};
template<typename T, typename Ty, typename Type>
template<typename X, typename Y>
BestTree<T, Ty, Type>::BestTree(const std::initializer_list<X>& _p, const std::initializer_list<Y>& _q)
                      :p(_p),
                       q(_q)
{
 std::cout<<"test"<<std::endl;
 if(typeid(T)!=typeid(X) || typeid(Ty)!=typeid(Y) || typeid(Type) != typeid(Y)){ // . 
  throw std::bad_cast();
 }
 
 std::cout<<"test"<<std::endl;
 
 this->pLength=_q.size();
 
 root=new X*[pLength];// [pLenght][pLenght]; 
 for(int i=0; i<pLength; ++i){
  root[i]=new X[pLength];
 }
 
 for(int i=0; i<pLength; ++i){
  for(int j=0; j<pLength; ++j){
   this->root[i][j]=T(0);
  }
 }
 
 e=new Y*[pLength+1];// 。
 w=new Y*[pLength+1];// T,Ty Y . 
 for(int i=0; i<pLength+1; ++i){
  e[i]=new Y[pLength];
  w[i]=new Y[pLength];
 }
 
 
  typename std::initializer_list<Y>::iterator iterB=_p.begin();
  //typename std::initializer_list<Y>::iterator iterE=_p.end();
  
  for(int i=0; i<pLength+1; ++i){
   for(int j=0; j<pLength; ++j){
    w[i][j]=T(0);
    e[i][j]=T(0);
   }
  }
    
  for(int m=1; m<pLength+1; ++m){
   e[m][m-1]= *(iterB+m-1);
   w[m][m-1]= *(iterB+m-1);
  }
  
  std::cout<<"success"<<std::endl;
}
template<typename T, typename Ty, typename Type>
void BestTree<T, Ty, Type>::OptimalBST()
{
 std::cout<<"enter"<<std::endl;
 
 for(int l=1; l<this->pLength+1; ++l){ // 1 <= i <= j <= n . 
  for(int i=1; i<this->pLength-l+1; ++i){
   
   int j=i+l-1; //j 1, 2, 3, 4....
   
   this->e[i][j]=MAXVALUE; // . e[i][i]=MAXVALUE;
   this->w[i][j]=w[i][j-1]+p[j]+q[j]; // w[i][i-1].
   
    for(int k=i; k<j+1; ++k){ // i=2 . 
     T t=e[i][k-1]+e[k+1][j]+w[i][j]; // i-j k .( .)
     
     if(t < e[i][j]){
      e[i][j]=t;
      root[i][j]=k;
     } 
    }
  }
 }
}
template<typename T, typename Ty, typename Type>
void BestTree<T, Ty, Type>::Subtree()
{
 for(int i=0; i<pLength; ++i){
  
  for(int j=0; j<pLength; ++j){
   std::cout<<this->root[i][j]<<"  ";
  }
  
  std::cout<<std::endl;
 }
}
template<typename T, typename Ty, typename Type>
BestTree<T, Ty, Type>::~BestTree()
{
 if(root != nullptr && w != nullptr && e != nullptr){
  for(int i=0; i<pLength; ++i){
   delete[] root[i];
  }
  delete[] root;
  
  for(int i=0; i<pLength+1; ++i){
   delete[] w[i];
   delete[] e[i];
  }
  
  delete[] w;
  delete[] e;
 }
 
 p.clear();
 q.clear();
}
int main()
{
 BestTree<> myTree( {double(-1), 0.15, 0.1, 0.05, 0.1, 0.2}, {0.05, 0.1, 0.05, 0.05, 0.05, 0.1});
 // double(-1), .  vector<int> != vector<double>; 
  
 myTree.OptimalBST();
 myTree.Subtree();
 
 return 0;
}