heapsortview.cpp

演示了堆排序的算法逻辑

// HeapSortView.cpp : implementation of the CHeapSortView class
//

#include "stdafx.h"
#include "HeapSort.h"

#include "HeapSortDoc.h"
#include "HeapSortView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CHeapSortView

IMPLEMENT_DYNCREATE(CHeapSortView, CView)

BEGIN_MESSAGE_MAP(CHeapSortView, CView)
	//{{AFX_MSG_MAP(CHeapSortView)
	ON_WM_LBUTTONDOWN()
	ON_COMMAND(ID_CREATE, OnCreate)
	ON_COMMAND(ID_CARTOON, OnCartoon)
	ON_UPDATE_COMMAND_UI(ID_CARTOON, OnUpdateCartoon)
	ON_COMMAND(ID_MAX, OnMax)
	ON_UPDATE_COMMAND_UI(ID_MAX, OnUpdateMax)
	ON_COMMAND(ID_MIN, OnMin)
	ON_UPDATE_COMMAND_UI(ID_MIN, OnUpdateMin)
	ON_COMMAND(ID_NEW, OnNew)
	ON_UPDATE_COMMAND_UI(ID_CREATE, OnUpdateCreate)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHeapSortView construction/destruction

CHeapSortView::CHeapSortView()
{
	//checked = false;
	blicked = false;
	started = false;
	n = N - 1;
	m = n;
	Createif = false;
	min_max = 1;//升序　-1　为降序
	linewide = 1;
	becol = RGB(0,116,167);
	afcol = RGB(230,117,219);

}

CHeapSortView::~CHeapSortView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CHeapSortView drawing

void CHeapSortView::OnDraw(CDC* pDC)
{
	CHeapSortDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	/*My own codes*/
	if(started == true)
	{
		GetClientRect(&rect);
		heap.SetNode(rect);
		drawmap(pDC);
	}
	/*Definition finished*/

}

/////////////////////////////////////////////////////////////////////////////
// CHeapSortView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CHeapSortView message handlers

#ifndef MY_CODE
#define MY_CODE

void CHeapSortView::drawmap(CDC* hDC)
{
	CRect rect;
	CPoint pText;
	CPoint from,end;
	int i = 1;
	//CString s = "";
	/*for(;i < N;i++)
	{
		s += heap.Heapnode[i].key;
		s += " ";
	}*/
	hDC->SetBkMode(TRANSPARENT);
	//hDC->SetBkColor(RGB(215,222,232));
	//hDC->TextOut(10,10,s);
	for(; i < N; i++)
	{
		if(heap.Heapnode[i].style == 1)
			hDC->SetTextColor(RGB(255,0,0));
		else
			hDC->SetTextColor(RGB(215,222,232));
		hDC->TextOut(i * Text,10,heap.Heapnode[i].key);
	}
	CBrush *hOldBrush,sBrush;
	CPen *hOldPen,sPen;

	sPen.CreateStockObject(PS_NULL);
	hOldPen = hDC->SelectObject(&sPen);

	sBrush.CreateSolidBrush(becol);
	hOldBrush = hDC->SelectObject(&sBrush);

	hDC->SetTextColor(RGB(215,222,232));
	for(i = 1;i < N;i++)
	{
		rect.left = X + heap.Heapnode[i].Locate.x - R;
		rect.right = X + heap.Heapnode[i].Locate.x + R;
		rect.top = Y + heap.Heapnode[i].Locate.y - R;
		rect.bottom = Y + heap.Heapnode[i].Locate.y + R;
		hDC->Ellipse(rect);
		pText.x = X + heap.Heapnode[i].Locate.x - TextR;
		pText.y = Y + heap.Heapnode[i].Locate.y - TextR;
		hDC->SetBkMode(TRANSPARENT);
		hDC->TextOut(pText.x,pText.y,heap.Heapnode[i].key);
	}

	sPen.DeleteObject();
	sPen.CreatePen(PS_DOT,linewide,afcol);
	hDC->SelectObject(&sPen);
	for(i = 2; i < N ; i++)
	{
		from = heap.Heapnode[i].Locate;
		end = heap.Heapnode[i].Parent;
		from.x += X;
		from.y += Y;
		end.x += X;
		end.y += Y;
		hDC->MoveTo(from);
		hDC->LineTo(end);
	}
	hDC->SelectObject(hOldPen);
	sPen.DeleteObject();
	sPen.CreatePen(PS_SOLID,linewide,becol);
	hOldPen = hDC->SelectObject(&sPen);
	for( i = 2 ;i < N ; i++)
	{
		if(heap.Heapnode[i].style == 0)
		{
			from = heap.Heapnode[i].Locate;
			end = heap.Heapnode[i].Parent;
			from.x += X;
			from.y += Y;
			end.x += X;
			end.y += Y;
			hDC->MoveTo(from);
			hDC->LineTo(end);
		}
	}
	hDC->SelectObject(hOldPen);
	sPen.DeleteObject();
	sPen.CreateStockObject(PS_NULL);
	hOldPen = hDC->SelectObject(&sPen);
	for(i = 1;i < N;i++)
	{
		rect.left = X + heap.Heapnode[i].Locate.x - R;
		rect.right = X + heap.Heapnode[i].Locate.x + R;
		rect.top = Y + heap.Heapnode[i].Locate.y - R;
		rect.bottom = Y + heap.Heapnode[i].Locate.y + R;
		hDC->Ellipse(rect);
		pText.x = X + heap.Heapnode[i].Locate.x - TextR;
		pText.y = Y + heap.Heapnode[i].Locate.y - TextR;
		hDC->SetBkMode(TRANSPARENT);
		hDC->TextOut(pText.x,pText.y,heap.Heapnode[i].key);
	}
	hDC->SelectObject(hOldPen);
	sPen.DeleteObject();

}


void CHeapSortView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	CString temp;
	if(blicked == false)
		blicked = true;
	if(Createif == true)
	{
		if(m >= 2)
		{
			temp = heap.Heapnode[1].key;
			heap.Heapnode[1].key = heap.Heapnode[m].key;
			heap.Heapnode[m].key = temp;
			heap.Heapnode[m].style = 1;
			if(min_max == 1)
			{
				siftmax(1,m-1);
					
			}
			else if(min_max == -1)
			{
				siftmin(1,m-1);
			}	
			m--;
		}
		else if(m == 1)
			heap.Heapnode[m].style = 1;
	}
	Invalidate();
	
	CView::OnLButtonDown(nFlags, point);
}

void CHeapSortView::OnCreate() 
{
	Createif = true;
	if(min_max == 1)
	{
		for(int i = n/2;i >= 1;i--)
			siftmax(i,n);
			
	}
	else if(min_max == -1)
	{
		for(int i = n/2;i >= 1;i--)
			siftmin(i,n);
	}
	Invalidate();
}



void CHeapSortView::OnCartoon() 
{
	CString temp;
	if(blicked == false)
		blicked = true;
	for(;m >= 2;m--)	//16
	{
		temp = heap.Heapnode[1].key;
		heap.Heapnode[1].key = heap.Heapnode[m].key;
		heap.Heapnode[m].key = temp;
		heap.Heapnode[m].style = 1;
		if(min_max == 1)
		{
			siftmax(1,m-1);
				
		}
		else if(min_max == -1)
		{
			siftmin(1,m-1);
		}
		Invalidate(true);		
	}
		
}

void CHeapSortView::OnUpdateCartoon(CCmdUI* pCmdUI) 
{
	pCmdUI->Enable((Createif == true && started == true)?true:false);
	
}

void CHeapSortView::OnMax() 
{
	min_max = 1;
	
}

void CHeapSortView::OnUpdateMax(CCmdUI* pCmdUI) 
{
	pCmdUI->Enable((Createif == false && started == true && started == true)?true:false);
	pCmdUI->SetCheck((min_max == 1)?1:0);
	
}

void CHeapSortView::OnMin() 
{
	min_max = -1;
	
}

void CHeapSortView::OnUpdateMin(CCmdUI* pCmdUI) 
{
	pCmdUI->Enable((Createif == false && started == true)?true:false);
	pCmdUI->SetCheck((min_max == -1)?1:0);
	
}

void CHeapSortView::OnNew() 
{
	started = true;
	n = N - 1;
	m = n;
	Createif = false;
	min_max = 1;//升序　-1　为降序
	linewide = 1;
	becol = RGB(0,116,167);
	afcol = RGB(230,117,219);
	heap.reset(rect);
	Invalidate();
	
}

void CHeapSortView::siftmax(int k,int nn)
{
	CString temp;
	int i,j;
	i = k;
	j = 2 * i;
	temp = heap.Heapnode[i].key;
	while(j <= nn)
	{
		if(j < nn && heap.Heapnode[j].key < heap.Heapnode[j+1].key)
			j++;
		if(temp < heap.Heapnode[j].key)
		{
			heap.Heapnode[i].key = heap.Heapnode[j].key;
			i = j;
			j = 2 * i;
		}
		else break;
	}
	heap.Heapnode[i].key = temp;
}

void CHeapSortView::siftmin(int k,int n)
{
	CString temp;
	int i,j;
	i = k;
	j = 2 * i;
	temp = heap.Heapnode[i].key;
	while(j <= n)
	{
		if(j < n && heap.Heapnode[j].key > heap.Heapnode[j+1].key)
			j++;
		if(temp > heap.Heapnode[j].key)
		{
			heap.Heapnode[i].key = heap.Heapnode[j].key;
			i = j;
			j = 2 * i;
		}
		else break;
	}
	heap.Heapnode[i].key = temp;
}
#endif

void CHeapSortView::OnUpdateCreate(CCmdUI* pCmdUI) 
{
	pCmdUI->Enable((started == true && blicked == false)?true:false);
	
}