/*
  這個文件是本程序的算法最核心的東西,
  定義了一個修正單純型表類TxzDcx(修正單純型拼音的首字母)
  和一個單純型表算法通道TxzDcxChannel
*/
//---------------------------------------------------------------------------
#ifndef xzDcxH
#define xzDcxH

#include "Matrix.h"
#include "Vector.h"
#include "TList.h"
#include "global.h"
#include "TDcxQ.h"
//---------------------------------------------------------------------------
#define TxzDE_OUTOFMEMMORY      0
#define TxzDE_INVALIDOPERATION  1
#define TxzDE_INVALIDPARAM      2
#define TxzDE_OUTOFBOUND        3

//修正單純型表異常類
class TxzDException
{
public:
    unsigned int mErrorCode;
public:
    TxzDException(){
    }
    TxzDException(unsigned int aE){
        mErrorCode=aE;
    }
    operator unsigned int(void){    //重載(int)強制轉換:如 if(e) dosomething;
        return mErrorCode;
    }
};



//修正單純型表節點數據
class TxzDcx
{
private:
   TCVector *mCVetBx;   //當前基解的正分量
   TMatrix *mMatU;      //當前矩陣的逆陣
   TCVector *mCVety;    //平衡方程的解
   TMVALUE mValz0;      //當前最優值~cx

   KTList<unsigned int> *mLB;    //當前基
public:
   //拷貝構造一個節點數據
   TxzDcx(TxzDcx &axzDcx)
   {
      int i,j;
      //當前基
      mLB = NULL;
      mLB = new KTList<unsigned int>;
      if (!mLB)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      for (axzDcx.mLB->First();!axzDcx.mLB->IsEof();axzDcx.mLB->Next()){
         mLB->Append(axzDcx.mLB->GetData());
      }

      //當前基矩陣的逆陣
      mMatU = NULL;
      mMatU = new TMatrix(axzDcx.mMatU);
      if (!mMatU)
         throw TxzDException(TxzDE_OUTOFMEMMORY);

      //當前基解的正分量
      mCVetBx = NULL;
      mCVetBx = new TCVector(axzDcx.mCVetBx);
      if (!mCVetBx)
         throw TxzDException(TxzDE_OUTOFMEMMORY);

      //平衡方程的解(~y = ~Bc * U)
      mCVety = NULL;
      mCVety = new TCVector(axzDcx.mCVety);
      if (!mCVety)
         throw TxzDException(TxzDE_OUTOFMEMMORY);

      //當前最優值 (z(0) = Bx * ~Bc)
      mValz0 = axzDcx.mValz0;
   }

   //由原線性規劃問題構造修正單純型表
   TxzDcx(TDcxQuestion *aDcxQ)
   {
      unsigned int i,j;

      unsigned int lRowCount = aDcxQ->mMatA->GetRowCount();
      unsigned int lColCount = aDcxQ->mMatA->GetColCount();

      //當前基
      mLB = NULL;
      mLB = new KTList<unsigned int>;
      if (!mLB)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      for (i=1;i<=lColCount;i++){
         if ((*aDcxQ->mCVetx)(i) > 0)
             mLB->Append(i);
      }

      //構造基矩陣
      TMatrix lMatM(lRowCount,lRowCount);
      unsigned int k;
      for (k=1,mLB->First();!mLB->IsEof();mLB->Next(),k++) {
         j=mLB->GetData();
         for (i=1;i<=lRowCount;i++)
            lMatM(i,k) = (*aDcxQ->mMatA)(i,j);
      }

      //當前基矩陣的逆陣
      mMatU = NULL;
      mMatU = new TMatrix(lRowCount,lRowCount);
      if (!mMatU)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      *mMatU = lMatM^-1;

      //當前基解的正分量
      mCVetBx = NULL;
      mCVetBx = new TCVector(lRowCount);
      if (!mCVetBx)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      for (i=1,mLB->First();!mLB->IsEof();mLB->Next(),i++) {
         (*mCVetBx)(i) = (*aDcxQ->mCVetx)(mLB->GetData());
      }

      //當前基費用向量
      TCVector *lCVetBc;   //當前基費用向量
      lCVetBc = NULL;
      lCVetBc = new TCVector(lRowCount);
      if (!lCVetBc)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      for (i=1,mLB->First();!mLB->IsEof();mLB->Next(),i++) {
         (*lCVetBc)(i) = (*aDcxQ->mCVetc)(mLB->GetData());
      }

      //平衡方程的解(~y = ~Bc * U)
      mCVety = NULL;
      mCVety = new TCVector(lRowCount);
      if (!mCVety)
         throw TxzDException(TxzDE_OUTOFMEMMORY);
      *mCVety = (~*mMatU) * (*(TMatrix*)lCVetBc);

      //當前最優值 (z(0) = ~Bx * Bc)
      mValz0 = (~*mCVetBx * (*((TMatrix*)lCVetBc)))(1,1);
   }


   ~TxzDcx()
   {
      delete mCVetBx;   //當前基解的正分量
      delete mMatU;     //當前矩陣的逆陣
      delete mCVety;    //平衡方程的解

      delete mLB;      //當前基
   }

   //傳進當前問題,計算取得該節點的非基判別行矩陣MatJudge及樞列坐標as、樞列向量VetPivot及樞行坐標位置,
   //返回:
   // 1  - 所有判別行z(j)-c(j)都<=0(即當前已是最優解)
   // -1 - 所有樞列VetPivot(j)都<=0(即無最優解，目標函數值趨向于正無窮)
   // 0  - 正常
   int GetPivot(TDcxQuestion* aDcxQ,TMatrix* aMatJudge,unsigned int* as,TCVector* aCVetPivot,unsigned int *ar)
   {
      unsigned int s,i;
      unsigned int lRowCount,lColCount;
      lRowCount = aDcxQ->mMatA->GetRowCount();
      lColCount = aDcxQ->mMatA->GetColCount();

      //計算非基變量的判別行:z(s)-c(s) = ~y*a(s) - c(s)
     // delete aMatJudge;
     // aMatJudge = new TMatrix(lColCount - lRowCount,2);
      TCVector lCVet(lRowCount);
      for (s=1,i=1;s<=lColCount;s++) {
         if (!mLB->Locate(s)) {
            (*aMatJudge)(i,1) = s;   //下標
            lCVet = aDcxQ->mMatA->CVector(s);
            (*aMatJudge)(i,2) = ((~*mCVety)*(*(TMatrix*)&lCVet))(1,1) - (*aDcxQ->mCVetc)(s); //值
       //?  (*aMatJudge)(i,2) = ((~*mCVety)*(aDcxQ->mMatA->CVector(s)))(1,1) - (*aDcxQ->mCVetc)(s); //值
            i++;
         }
      }

      //找非基變量的判別行的z(j)-c(j)的最大元素lMaxJudge及其位置s即樞列
      TMVALUE lMaxJudge = (*aMatJudge)(1,2);
      *as = 1;//StrToInt((AnsiString)((*aMatJudge)(1,1)));
      for (i=2;i<=lColCount-lRowCount;i++)
         if (lMaxJudge < (*aMatJudge)(i,2)) {
            lMaxJudge = (*aMatJudge)(i,2);
            *as = i;//StrToInt((AnsiString)((*aMatJudge)(i,1)));
         }

      //所有判別行z(j)-c(j)都<=0(即當前已是最優解)
      if (lMaxJudge <= 0)
         return 1;

      //計算樞列各元素(t(i,s) = ~U(i) * A(s))   <= A(s) = M * t(s)
      lCVet = aDcxQ->mMatA->CVector(StrToInt((AnsiString)((*aMatJudge)(*as,1))));
      for (i=1;i<=lRowCount;i++) {
         (*aCVetPivot)(i) = (mMatU->RVector(i) * *(TMatrix*)&lCVet)(1,1);
      }

      //確定樞行r
      TMVALUE lMinPivot;
      TMVALUE lTemp;
      bool lIsFirst=true;
      *ar = 0;
      for (i=1;i<=lRowCount;i++) {
         lTemp = (*aCVetPivot)(i);
         if (lTemp > 0) {
            lTemp = (*mCVetBx)(i) / lTemp;
            if (lIsFirst) {
               lMinPivot = lTemp;
               lIsFirst = false;
               *ar = i;
            }
            else if (lTemp < lMinPivot) {
               lMinPivot = lTemp;
               *ar = i;
            }
         }
      }

      //如果所有樞列VetPivot(j)都<=0(即無最優解，目標函數值趨向于正無窮)
      if (*ar == 0)
         return -1;

      //還無法確定能否達到最優
      return 0;
   }

   //根據樞列向量VetPivot和最大的z(s)-c(s)變換基
   void ChangeBase(TCVector* aCVetPivot,unsigned int ar,TMVALUE aMaxJudge,unsigned int as)
   {
      unsigned int i,j;
      unsigned int lRowCount;
      lRowCount = aCVetPivot->GetDimCount();

      //新i行 = (舊i行) -  (t(i)/t(r)) * (舊r行)
      for (i=1;i<=lRowCount;i++) {
         if (i!=ar) {
            //矩陣U
            mMatU->RAddition(i,ar,-(*aCVetPivot)(i)/(*aCVetPivot)(ar));
            //基解的正分量
            (*mCVetBx)(i) = (*mCVetBx)(i) - ((*aCVetPivot)(i)/(*aCVetPivot)(ar)) * (*mCVetBx)(ar);
         }
      }
      //平衡方程的解y (只有1行)
      for (j=1;j<=lRowCount;j++){
        (*mCVety)(j) = (*mCVety)(j) - (aMaxJudge/(*aCVetPivot)(ar)) * (*mMatU)(ar,j);
      }
      //當前最優值z(0)(只有1行,1列)
      mValz0 = mValz0 - (aMaxJudge/(*aCVetPivot)(ar)) * (*mCVetBx)(ar);

      //新r行 = (舊r行) / t(r)
      //矩陣U
      mMatU->RScale(ar,1/(*aCVetPivot)(ar));
      //基解的正分量
      (*mCVetBx)(ar) = (*mCVetBx)(ar) / (*aCVetPivot)(ar);

      //換基
      //B的第r個元素離基, s入基
      for (i=1,mLB->First();!mLB->IsEof() && i<=lRowCount;mLB->Next(),i++) {
         if (i == ar) {
            mLB->SetData(as);
            break;
         }
      }
   }

   //以整一個單存型表返回
   TMatrix GetMatxzDcx()
   {
      unsigned int lDimCount = mMatU->GetRowCount()+1;
      TMatrix lMatR(lDimCount,lDimCount);

      unsigned int i,j;
      //U
      for (i=1;i<=lDimCount-1;i++)
         for (j=2;j<=lDimCount;j++)
            lMatR(i,j) = (*mMatU)(i,j-1);

      //y-最后一行
      for (j=2;j<=lDimCount;j++)
         lMatR(lDimCount,j) = (*mCVety)(j-1);

      //Bx-第一列
      for (i=1;i<=lDimCount-1;i++)
         lMatR(i,1) = (*mCVetBx)(i);

      //z0-左下角
      lMatR(lDimCount,1) = mValz0;

      return lMatR;
   }


   TMatrix* GetMatU() { return mMatU; }
   TCVector* GetCVety() { return mCVety; }
   TCVector* GetCVetBx() { return mCVetBx; }
   TMVALUE GetValz0() { return mValz0; }
   KTList<unsigned int>* GetLB() { return mLB; }
};
//---------------------------------------------------------------------------

//單純型表算法通道
class TxzDcxChannel
{
private:
   KTList<TxzDcx*> *mLxzDcx;  //解路徑
   TxzDcx *mxzDcx;            //當前數據狀態

   TDcxQuestion *mDcxQ;       //原單純型問題

   //當前節點可得到的狀態,中間變量
   TMatrix *mMatJudge;     //非基判別行矩陣MatJudge
   TCVector *mCVetPivot;   //樞列向量
   unsigned int *ms,*mr;   //樞列坐標s,樞行坐標r
   int mResult;            //計算結果 1: 當前已是最優解, -1:當前可判斷無最優解，0: 正常

private:
   bool mIsValid;            //當前通道是否有效
   bool mIsRecord;         //是否記錄中間狀態

public:

   TxzDcxChannel()
   {
      mIsValid = false;
      mIsRecord = true;  //默認記錄中間狀態
   }

   ~TxzDcxChannel()
   {
      if (mIsValid) {  //如果通道有效(即有數據),先刪除數據
         for (mLxzDcx->First();!mLxzDcx->IsEof();mLxzDcx->Next())
            delete mLxzDcx->GetData();    //節點數據

         delete mLxzDcx;    //解路徑
         delete mDcxQ;      //原單純型問題
         delete mMatJudge;  //非基判別行矩陣MatJudge
         delete mCVetPivot; //樞列向量
         delete ms;         //樞列坐標s
         delete mr;         //樞行坐標r
      }
   }

   //設置工作狀態
   void SetStates(bool aIsRecord)
   {
      mIsRecord = aIsRecord;
      if (mIsValid) {  //如果通道有效(即有數據),先刪除數據
         for (mLxzDcx->First();!mLxzDcx->IsEof();mLxzDcx->Next())
            delete mLxzDcx->GetData();    //節點數據

         delete mLxzDcx;    //解路徑
         delete mDcxQ;      //原單純型問題
         delete mMatJudge;  //非基判別行矩陣MatJudge
         delete mCVetPivot; //樞列向量
         delete ms;         //樞列坐標s
         delete mr;         //樞行坐標r
      }
      mIsValid = false;
   }

   //提交數據,立即執行
   void operator<<(TDcxQuestion* aDcxQ)
   {
      if (mIsValid) {  //如果通道有效(即有數據),先刪除數據
         for (mLxzDcx->First();!mLxzDcx->IsEof();mLxzDcx->Next())
            delete mLxzDcx->GetData();    //節點數據

         delete mLxzDcx;    //解路徑
         delete mDcxQ;      //原單純型問題
         delete mMatJudge;  //非基判別行矩陣MatJudge
         delete mCVetPivot; //樞列向量
         delete ms;         //樞列坐標s
         delete mr;         //樞行坐標r
      }

      //拷貝原單純型問題
      mDcxQ = new TDcxQuestion(*aDcxQ);

      //由原單純型問題構造一個修正單純型表節點數據
      mxzDcx = new TxzDcx(mDcxQ);

      mMatJudge = new TMatrix(mDcxQ->mMatA->GetColCount()-mDcxQ->mMatA->GetRowCount(),2);   //非基判別行矩陣MatJudge
      mCVetPivot = new TCVector(mDcxQ->mMatA->GetRowCount());     //樞列向量
      ms = new unsigned int;            //樞列坐標s
      mr = new unsigned int;            //樞行坐標r

      //傳進原問題,計算取得非基判別行矩陣MatJudge及樞列坐標as、樞列向量VetPivot及樞行坐標位置,
      mResult = mxzDcx->GetPivot(mDcxQ,mMatJudge,ms,mCVetPivot,mr);

      mLxzDcx = new KTList<TxzDcx*>;  //解路徑
      mLxzDcx->Append(mxzDcx);

      if (mIsRecord) {  //要記錄中間結果
         while (mResult==0) {
            mxzDcx = new TxzDcx(*mxzDcx);   //拷貝一個新節點
            mxzDcx->ChangeBase(mCVetPivot,*mr,(*mMatJudge)(*ms,2),StrToInt((AnsiString)((*mMatJudge)(*ms,1))));  //換基
            mResult = mxzDcx->GetPivot(mDcxQ,mMatJudge,ms,mCVetPivot,mr);//計算樞行樞列
            mLxzDcx->Append(mxzDcx);
         }
      }
      else {     //不要記錄中間結果
         while (mResult==0) {
            mxzDcx->ChangeBase(mCVetPivot,*mr,(*mMatJudge)(*ms,2),StrToInt((AnsiString)((*mMatJudge)(*ms,1))));  //換基
            mResult = mxzDcx->GetPivot(mDcxQ,mMatJudge,ms,mCVetPivot,mr);//計算樞行樞列
         }
      }

      mIsValid = true;
   }

   //用鏈表取得所有節點數據
   void operator>>(KTList<TxzDcx*>* aLxzDcx)
   {
      TxzDcx *lxzDcx;

      //清空原來的數據
      for (aLxzDcx->First();!aLxzDcx->IsEof();aLxzDcx->Next())
         delete aLxzDcx->GetData();
      aLxzDcx->Empty();
         
      for (mLxzDcx->First();!mLxzDcx->IsEof();mLxzDcx->Next()) {
         lxzDcx = new TxzDcx(*mLxzDcx->GetData());
         aLxzDcx->Append(lxzDcx);
      }
   }


};
//---------------------------------------------------------------------------
#endif