sortandlifeview.cpp

Conway s Game of life 算法程序

// SortAndLifeView.cpp : implementation of the CSortAndLifeView class
//
/*
 * SortAndLifeView.cpp  - Copyright (C) 2006 Jerry Jiang
 *
 **********************************************************************
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *Version 1.0
 *Modified March 2009 to add cells by left click
 
 **********************************************************************
 *
 */

#include "stdafx.h"
#include "SortAndLife.h"

#include "SortAndLifeDoc.h"
#include "SortAndLifeView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView

#define SWAP(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

IMPLEMENT_DYNCREATE(CSortAndLifeView, CView)

BEGIN_MESSAGE_MAP(CSortAndLifeView, CView)
	//{{AFX_MSG_MAP(CSortAndLifeView)
	ON_WM_LBUTTONDOWN()
	ON_WM_RBUTTONDOWN()
	ON_WM_DESTROY()
	ON_WM_CANCELMODE()
	ON_WM_TIMER()
	ON_WM_SIZE()
	ON_WM_ERASEBKGND()
	ON_WM_SETCURSOR()
	ON_WM_MOUSEMOVE()

	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
	ON_MESSAGE(WM_DISPLAYCHANGE, OnDisplayChange)
	ON_COMMAND(ID_BUTTON_CLEAR,OnClear)
	ON_COMMAND(ID_BUTTON_GRID,OnGrid)
	ON_COMMAND(ID_BUTTON_SEED, OnSeedInit)
	ON_COMMAND(ID_BUTTON_START, OnStart)
	ON_COMMAND(ID_BUTTON_STOP,OnStop)
	ON_COMMAND(ID_BUTTON_SPEEDUP, OnSpeedUp)
	ON_COMMAND(ID_BUTTON_SLOWDOWN, OnSlowDown)
	ON_COMMAND(ID_BUTTON_COLOR, OnSetColor)
	ON_UPDATE_COMMAND_UI(ID_BUTTON_START,OnUpdateCommand)
	ON_UPDATE_COMMAND_UI(ID_BUTTON_STOP,OnUpdateCommand)
	ON_UPDATE_COMMAND_UI(ID_BUTTON_GRID,OnUpdateCommand)

END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView construction/destruction

CSortAndLifeView::CSortAndLifeView()
{
	m_prePoint = (-1,-1);
	m_bDDrawActive = FALSE;
	m_nTimer = NULL;
	m_bInitial = FALSE;
	hThread = NULL;
	m_bTermination = FALSE;
	m_bStart = FALSE;
	// TODO: add construction code here
}

CSortAndLifeView::~CSortAndLifeView()
{
}

BOOL CSortAndLifeView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

BOOL CSortAndLifeView::OnSetCursor(CWnd *pWnd,UINT nHitTest,UINT message)
{
	::SetCursor( AfxGetApp()->LoadCursor(IDC_CURSOR_HAND));	
	return TRUE;
}

void CSortAndLifeView::OnDestroy()
{
	if(m_nTimer)
	{
		KillTimer(m_nTimer);
		m_nTimer = NULL;
	}
	m_bTermination = TRUE;
	if(hThread)
	{
		if(WaitForSingleObject(hThread, 200) != WAIT_OBJECT_0)
		{
			TerminateThread(hThread, 1);
		}
		CloseHandle(hThread);
		hThread = NULL;
	}
}
void CSortAndLifeView::OnInitialUpdate() 
{
	CView::OnInitialUpdate();
	
	// TODO: Add your specialized code here and/or call the base class
	// OK, here is where you initialize the DirectDraw interface.
	if (!m_directXObj.Init(GetSafeHwnd()))
	{
		AfxMessageBox("Failed to Create DirectDraw Interface.");
		m_bDDrawActive = FALSE;
	}
	else
	{
		m_bDDrawActive = TRUE;
	}
	m_bInitial = TRUE;
	CSortAndLifeDoc* pDoc = GetDocument();
	
	CString m_sTitle = pDoc->GetTitle();
	if(m_sTitle.Left(4) == "Sort")
		m_bDocumentType = 1;
	else
		m_bDocumentType = 0;
	m_nSleep = pDoc->m_nSleep;
}


void CSortAndLifeView::OnPaint() 
{
	CPaintDC dc(this);
	OnDraw(&dc);
}

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView drawing

void CSortAndLifeView::OnDraw(CDC* pDC)
{
	// TODO: add draw code for native data here
	CSortAndLifeDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	GetClientRect(&rectView);

	pDoc->LockData();
	if(m_bDocumentType == DOCTYPE_LIFE)
		m_directXObj.CellDraw((char *)pDoc->m_cCellArray,pDoc->m_cellColor,rectView,pDoc->m_bGrid);
	else
		m_directXObj.BarDraw((int *)pDoc->m_nNumberArray,pDoc->m_barColor,rectView);
	pDoc->UnLockData();
	m_directXObj.Display();
}

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView printing

BOOL CSortAndLifeView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CSortAndLifeView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CSortAndLifeView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView diagnostics

#ifdef _DEBUG
void CSortAndLifeView::AssertValid() const
{
	CView::AssertValid();
}

void CSortAndLifeView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CSortAndLifeDoc* CSortAndLifeView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSortAndLifeDoc)));
	return (CSortAndLifeDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CSortAndLifeView message handlers

void CSortAndLifeView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default

	CView::OnLButtonDown(nFlags, point);

	CSortAndLifeDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	GetClientRect(&rectView);

	int nCellWidth = rectView.Width()/CONST_INT_GRIDNUMBER;
	int nCellHeight = rectView.Height()/CONST_INT_GRIDNUMBER;



	point.x -= (rectView.Width()-nCellWidth*CONST_INT_GRIDNUMBER)/2;
	point.y -= (rectView.Height()-nCellHeight*CONST_INT_GRIDNUMBER)/2;

	pDoc->CreateCell(point.x/nCellWidth,point.y/nCellHeight);
	Invalidate();
}

void CSortAndLifeView::OnMouseMove(UINT nFlags, CPoint point) 
{
	CView::OnMouseMove(nFlags, point);

	if(nFlags & MK_LBUTTON)
	{
		CSortAndLifeDoc* pDoc = GetDocument();
		ASSERT_VALID(pDoc);
		GetClientRect(&rectView);

		int nCellWidth = rectView.Width()/CONST_INT_GRIDNUMBER;
		int nCellHeight = rectView.Height()/CONST_INT_GRIDNUMBER;

		point.x -= (rectView.Width()-nCellWidth*CONST_INT_GRIDNUMBER)/2;
		point.y -= (rectView.Height()-nCellHeight*CONST_INT_GRIDNUMBER)/2;
		point.x /= nCellWidth;
		point.y /= nCellHeight;
		if(m_prePoint != point)
		{
			pDoc->CreateCell(point.x,point.y);
			m_prePoint = point;
			Invalidate();
		}
	}
}

void CSortAndLifeView::OnRButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if((m_nTimer == NULL)&&(m_bDocumentType))
	{
		m_nTimer = SetTimer(2,20,0);   
		m_bDocumentType = 2;
		CreatSortThread();
	}
	CView::OnRButtonDown(nFlags, point);
}


void CSortAndLifeView::OnCancelMode() 
{
	CView::OnCancelMode();
	// TODO: Add your message handler code here
}

void CSortAndLifeView::OnTimer(UINT nIDEvent)
{
	if(nIDEvent == 2)
	{
		OnPaint() ;
	}
}

void CSortAndLifeView::CreatSortThread()
{
	unsigned threadID;

	if(hThread)
		CloseHandle(hThread);
	hThread = (HANDLE)_beginthreadex(NULL, 0, thread_proc, this, CREATE_SUSPENDED,  &threadID);
    ResumeThread(hThread);

}

unsigned int __stdcall CSortAndLifeView::thread_proc(void* pv)
{
	CSortAndLifeView *this_ = reinterpret_cast<CSortAndLifeView*>(pv);
	if(this_->m_bDocumentType == DOCTYPE_LIFE)
		this_->OnLifeGame();
	else if(this_->m_bDocumentType == DOCTYPE_BUBBLESORT)
		this_->OnBubbleSort();
	else if(this_->m_bDocumentType == DOCTYPE_QUICKSORT)
		this_->OnQuickSort();
	 _endthreadex( 0 );
	return 0;
}

void CSortAndLifeView::OnQuickSort() 
{
	CSortAndLifeDoc* pDoc = GetDocument();
	int *pnArray = (int *)pDoc->m_nNumberArray;
	QuickSort(pnArray,0,CONST_INT_BARNUMBER-1);
	Sleep(m_nSleep);  
	if(m_nTimer > 0)
		KillTimer(m_nTimer);
	m_nTimer = NULL;
}

void CSortAndLifeView::OnLifeGame() 
{
	while(!m_bTermination)
	{
		if(m_bStart)
			StepGeneration();
		Sleep(m_nSleep);
	}
	KillTimer(m_nTimer);
	m_nTimer = NULL;
}

void CSortAndLifeView::OnSize(UINT nType, int cx, int cy) 
{
	CView::OnSize(nType, cx, cy);
	if(m_bInitial)
		OnDisplayChange(NULL, NULL);
}

void CSortAndLifeView::OnSpeedUp() 
{
    if(m_nSleep > 30)
	    m_nSleep -=  10;
    else
		if(m_nSleep>2)
			m_nSleep--;

	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;
	pDoc->m_nSleep = m_nSleep;
}

void CSortAndLifeView::OnSlowDown() 
{
	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;
	m_nSleep += 10;
	pDoc->m_nSleep = m_nSleep;
}

void CSortAndLifeView::OnSetColor() 
{ 
	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;

	CColorDialog dlg (pDoc->m_barColor, CC_FULLOPEN);
	if (IDOK == dlg.DoModal())
	{	
		pDoc->m_barColor = dlg.GetColor ();
		pDoc->m_cellColor = dlg.GetColor ();
	}
	Invalidate();
}

void CSortAndLifeView::OnSeedInit() 
{
	CSortAndLifeDoc* pDoc = GetDocument();

	if(pDoc == NULL)
		return;

	pDoc->SetNewRandom();
	Invalidate();
}

void CSortAndLifeView::OnStop() 
{
	m_bStart = FALSE;
}

void CSortAndLifeView::OnStart() 
{
	m_bStart = TRUE;
	if(m_nTimer == NULL)
	{
		m_nTimer = SetTimer(2,20,0);   
		CreatSortThread();
	}
}

void CSortAndLifeView::OnClear() 
{
	m_bStart = FALSE;
	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;
	pDoc->Clear();
	Invalidate();
}

void CSortAndLifeView::OnGrid() 
{
	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;
	pDoc->m_bGrid = !pDoc->m_bGrid;
	Invalidate();
}

BOOL CSortAndLifeView::OnEraseBkgnd(CDC *pDC)
{
	return TRUE;
}

void CSortAndLifeView::OnUpdateCommand(CCmdUI* pCmdUI)
{
	if(pCmdUI->m_nID == ID_BUTTON_START)
	{
		pCmdUI->SetCheck(m_bStart);
	}
	else if(pCmdUI->m_nID == ID_BUTTON_STOP)
	{
		pCmdUI->SetCheck(!m_bStart);
	}
	else if(pCmdUI->m_nID == ID_BUTTON_GRID)
	{
		CSortAndLifeDoc* pDoc = GetDocument();
		if(pDoc == NULL)
			return;
		pCmdUI->SetCheck(pDoc->m_bGrid);
	}
}

LRESULT CSortAndLifeView::OnDisplayChange(WPARAM wParam, LPARAM lParam)
{
	LRESULT _lResult;
	
	_lResult = CWnd::OnDisplayChange(wParam, lParam);

	if(m_bDDrawActive)
		m_directXObj.Terminate();
	m_bDDrawActive = FALSE;

	if (!m_directXObj.Init(GetSafeHwnd()))
	{
		AfxMessageBox("Failed to Create DirectDraw Interface.");
		m_bDDrawActive = FALSE;
	}
	else
	{
		m_bDDrawActive = TRUE;
	}

	return _lResult;
}

//Algorithum for Conway's Game of Life begin
void CSortAndLifeView::StepGeneration()
{
	CSortAndLifeDoc* pDoc = GetDocument();
	if(pDoc == NULL)
		return;

	int		i, j, x;
	char	bCell;
	char	doubleArray[CONST_INT_GRIDNUMBER][CONST_INT_GRIDNUMBER];

	for(i=0;i<CONST_INT_GRIDNUMBER;i++)
	{
		for(j=0;j<CONST_INT_GRIDNUMBER;j++)
		{
			x = pDoc->Neighbors(i,j,bCell);
			if(bCell)
			{
				if((x == 2) || (x == 3))
					doubleArray[i][j] = 1;
				else
					doubleArray[i][j] = 0;
			}
			else
			{
				if(x == 3)
					doubleArray[i][j] = 1;
				else
					doubleArray[i][j] = 0;
			}
	    }
	}
	pDoc->CopyArray(&doubleArray[0][0]);	
}


//Bubble and Quick Sort algorithum begin
void CSortAndLifeView::OnBubbleSort() 
{
	// TODO: Add your message handler code here and/or call default
	CSortAndLifeDoc* pDoc = GetDocument();
	int *pnArray = (int *)pDoc->m_nNumberArray;

	for (int i=0; i<CONST_INT_BARNUMBER; i++) 
	{
		for (int j=0; j<CONST_INT_BARNUMBER-1-i; j++)
			if (pnArray[j+1] < pnArray[j])
			{  
				SWAP(pnArray[j],pnArray[j+1]);
   				Sleep(m_nSleep);
			}
	}
	Sleep(30);
	if(m_nTimer > 0)
		KillTimer(m_nTimer);
	m_nTimer = NULL;
}


void CSortAndLifeView::QuickSort(int *pnVec, int nLoBound, int nHiBound) 
{
    int nPivot,nLoSwap,nHiSwap;

    if (nLoBound >= nHiBound) // Zero or one item to sort
		return;
	if (nHiBound-nLoBound == 1) 
	{ // Just two items to sort
      if (pnVec[nLoBound] > pnVec[nHiBound])
		  SWAP(pnVec[nLoBound],pnVec[nHiBound]);
      return;
   }
   
	// 3 or more items to sort
   nPivot = pnVec[(nLoBound+nHiBound)/2]; 
   pnVec[(nLoBound+nHiBound)/2] = pnVec[nLoBound];
   pnVec[nLoBound] = nPivot;
   nLoSwap = nLoBound + 1;
   nHiSwap = nHiBound;

   do
   { 
      while (nLoSwap <= nHiSwap && pnVec[nLoSwap] <= nPivot)
         nLoSwap++;
      while (pnVec[nHiSwap] > nPivot)
         nHiSwap--;
      if (nLoSwap < nHiSwap)
		 SWAP(pnVec[nLoSwap],pnVec[nHiSwap]);
	 
   } while (nLoSwap < nHiSwap);

   Sleep(m_nSleep);  	

   pnVec[nLoBound] = pnVec[nHiSwap];
   pnVec[nHiSwap] = nPivot;

   QuickSort(pnVec, nLoBound, nHiSwap-1);
   QuickSort(pnVec, nHiSwap+1, nHiBound);
}

//Bubble and Quick Sort algorithum end