// FindPath.cpp: implementation of the CFindPath class.
//
//////////////////////////////////////////////////////////////////////


#include "stdafx.h"
#include "FindAllPath.h"
#include "FindPath.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
ClayData::ClayData()
{
 m_num_data = 0 ;
}
ClayData::~ClayData()
{
if ( m_data != NULL)
delete []m_data ;

if( m_pre != NULL)
delete []m_pre;

}

CFindPath::CFindPath()
{
	m_list = NULL;

}

CFindPath::~CFindPath()
{ 

  //delete []m_list;
  

}

ClayData::ClayData(int lengthpre, int numdata)
{
	m_num_data = numdata ;
   m_data = new int[numdata + 1];
   m_pre = new int [lengthpre + 1];}

BOOL CFindPath::FindPath()
{
  BOOL breturn = FALSE;
  CPathList m_pathList;
  m_list = new CLayList[NUM];
 if (!DealFisrtLay())
	 return FALSE;
  for ( int i = 2 ; i < NUM ; i++)
  {
	  DealLayData(i);
  }

 for ( int j = 1 ; j < NUM ; j++)
 {
	 int k = 0 ;
     k = m_list[j].GetSize();
	 for ( int f = 0 ; f <  k ; f++)
	 {
         ClayData * laydata = m_list[j].GetAt(f);
		 TRACE("%d",laydata->m_num_data);
		 for ( int g = 1 ; g <= laydata->m_num_data ; g++)
		 {
			 if ( laydata->m_data[g] == to)
			 {
				 CPathData * _pathdata = new CPathData(j+1);

				 for ( int l = 1 ; l <= j ; l++)
				 {   
					 _pathdata->data[l-1] = laydata->m_pre[l];
				 }
				 _pathdata->data[j] = to;
                 m_pathList.Add(_pathdata);
			 }
		 }
	 }

 }

  printf("從頂點%d到頂點%d的所有路徑如下:\n",from,to);
 for ( int f = 0 ; f < m_pathList.GetSize(); f++)
 {
    CPathData * _pathData = m_pathList.GetAt(f);
	for ( int l = 0 ; l <  _pathData->PathLength  ; l++)
	{
		printf("%d\t",_pathData->data[l]);
	}
	printf("\n");
	
 }

   ClearList();
 
  return breturn;

}


BOOL CFindPath::DealFisrtLay()
{
	BOOL breturn = FALSE;
    int num = NUM;

	if (num <= 1 )
		breturn = FALSE;
	int length = 0  ;
	int *_data = new int[num+1];

	for ( int j = 1 ; j <= num ; j++)
	{
		if(m_adj(from,j) == 1 )
		{
			length++;
			_data[length] = j ;
		}
	}

	ClayData * _laydata = new ClayData(1,length);
	_laydata->m_pre[1] = from ;

	while(length)
	{
		_laydata->m_data[length] = _data[length];
		length--;
		breturn = TRUE;

	}
	m_list[1].Add(_laydata);

	delete _data; // maybe some error in this line;


  return breturn;

}

BOOL CFindPath::DealLayData(int laynum)
{

 BOOL breturn = FALSE;

 int lastlay = laynum - 1;
 int * _datatemp = new int[NUM];
 int length  = 0;
 for ( int i = 0 ; i < m_list[lastlay].GetSize() ; i++)
 {
	 ClayData * lastlaydata = m_list[lastlay].GetAt(i);
     for ( int j = 1 ; j <= lastlaydata->m_num_data ; j++)
	 {
		 int laythisdata = lastlaydata->m_data[j];
		 length = 0 ;

		 if ( laythisdata != to) //if equ to , don't dealwith
		 {
			 for ( int k = 1 ; k <= NUM ; k++)
			 {
				 if(m_adj(laythisdata,k) == 1 && NotInPreData(k,lastlaydata->m_pre,lastlay)) // if not in data , should add a new laydata
				 {
                       length++;
					   _datatemp[length] = k;
                     
				 }
			 }

			 ClayData * newlaydata = new ClayData ( laynum,length); //should add a new laydata
             int f ; 
             for (  f = 1 ; f <= lastlay ; f++)
			 {
				 newlaydata->m_pre[f] = lastlaydata->m_pre[f];

			 }

			 newlaydata->m_pre[f] = laythisdata ;  // add a new laydata , because of a new lay;

			 for ( f = 1 ;  f <= length ; f++)
			 {
				 newlaydata->m_data[f] = _datatemp[f];
			 }
                 
			 breturn = TRUE;

			 m_list[laynum].Add(newlaydata);
		 }
	 }

 }
delete []_datatemp;

  return breturn;
}

BOOL CFindPath::NotInPreData(int k, int *data, int length)
{
 
	BOOL breturn = TRUE;
 
	for ( int i = 1 ; i <= length ; i++)
	{
		if ( k == data[i] )
		{
			breturn = FALSE;
			break;
		}
	}

  return breturn;
}

void CFindPath::ClearList()
{
 for ( int j = 1 ; j < NUM ; j++)
 {
	 int k = 0 ;
     k = m_list[j].GetSize();
	 for ( int f = 0 ; f <  k ; f++)
	 {
         delete m_list[j].GetAt(f);
		 
	 }
	 m_list[j].RemoveAll();

 }
 delete []m_list;



}

CPathData::CPathData(int length)
{
 PathLength = length;
 data = new int[length];

}

CPathData::~CPathData()
{
 delete [] data;

}

CPathData::CPathData()
{

}

CFindPath::CFindPath(int num)
{
  NUM = num ;
  m_adj.ReSetRowCol(NUM,NUM);
}