/* HANOI.C: Towers of Hanoi
A sample code from the textbook "Windows Wisdom for C and C++ Programmers"
by Leendert Ammeraal. */
#include <windows.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "hanoi.h"
#define NMAX 20
enum {WAITING, STARTING, BUSY} status;
int N;
COLORREF WoodColor;
const char* /*const*/ pCaption="Towers of Hanoi (use New to start)";
HWND hWindow;
HMENU hMenu;
HGLOBAL hgbl;
HANDLE hInstGlobal;
typedef
struct node_tag{int jSrc, jDest; int n; struct node_tag *pNext;}
NODE;
NODE *pStart=NULL;
LPWORD lpwAlign ( LPWORD lpIn)
{
ULONG ul;
ul = (ULONG) lpIn;
ul +=3;
ul >>=2;
ul <<=2;
return (LPWORD) ul;
}
void Push(int jSrc, int jDest, int n)
{ NODE *p=pStart;
pStart = (NODE *) malloc(sizeof(NODE));
if (pStart == NULL)
{ MessageBox(hWindow, "Not enough memory",
"Fatal error", MB_ICONSTOP);
PostQuitMessage(0);
}
pStart->jSrc = jSrc; pStart->jDest = jDest;
pStart->n = n; pStart->pNext = p;
}
int Pop(int *pSrc, int *pDest, int *pn)
{ NODE *p;
if (pStart == NULL) return 0;
*pSrc = pStart->jSrc; *pDest = pStart->jDest; *pn = pStart->n;
p = pStart;
pStart = pStart->pNext;
free(p);
return 1;
}
void CleanUp(void)
{ NODE *p;
while (pStart != NULL)
{ p = pStart;
pStart = pStart->pNext;
free(p);
}
}
int Hanoi(int *pSrc, int *pDest)
{ // Find source and destination pegs for next move:
int n;
for (;;)
{ if (!Pop(pSrc, pDest, &n)) return 0;
if (n < 0) break;
if (n > 0)
{ int jAux = 3 - *pSrc - *pDest; // 0 + 1 + 2 = 3
Push(jAux, *pDest, n-1);
// Third action (first to linked stack):
// tower of n-1 disks from jAux to jDest
Push(*pSrc, *pDest, -n);
// Second action:
// only disk n from jSrc to jDest
// (negative means one disk)
Push(*pSrc, jAux, n-1);
// First action (last to linked stack):
// tower of n-1 disks from jSrc to jAux.
}
}
return 1;
}
COLORREF GenColor(int i)
{ int red=0, green=0, blue=0;
switch (i % 6)
{ case 1: red = 255; break;
case 2: green = 255; break;
case 3: blue = 255; break;
case 4: red = green = 255; break;
case 5: green = blue = 255; break;
case 0: blue = red = 255; break;
}
return RGB(red, green, blue);
}
int PASCAL WinMain(HANDLE hInstance, HANDLE hPrevInstance,
LPSTR lpCmdLine, int nCmdShow)
{ char szAppName[]="hanoi";
WNDCLASSEX wndclass;
HWND hWnd;
MSG msg;
int xScreen = GetSystemMetrics(SM_CXSCREEN),
yScreen = GetSystemMetrics(SM_CYSCREEN);
WoodColor = RGB(120, 120, 0);
hInstGlobal = hInstance;
pStart = 0;
status = WAITING;
//HGLOBAL hgbl;
LPDLGTEMPLATE lpdt;
LPDLGITEMTEMPLATE lpdit;
LPWORD lpw;
LPWSTR lpwsz;
LRESULT ret;
int nchar;
hgbl = GlobalAlloc(GMEM_ZEROINIT, 1024);
if (!hgbl)
return -1;
lpdt = (LPDLGTEMPLATE)GlobalLock(hgbl);
// Define a dialog box.
lpdt->style = WS_POPUP | WS_BORDER | WS_SYSMENU
| DS_MODALFRAME | WS_CAPTION;
lpdt->cdit = 2; // number of controls
lpdt->x = 20; lpdt->y = 20;
lpdt->cx = 200; lpdt->cy = 60;
lpw = (LPWORD) (lpdt + 1);
*lpw++ = 0; // no menu
*lpw++ = 0; // predefined dialog box class (by default)
lpwsz = (LPWSTR) lpw;
nchar = 1+ MultiByteToWideChar (CP_ACP, 0, "Number of disks? (e.g. 5)", -1,
lpwsz, 50);
lpw += nchar;
//-----------------------
// Define an OK button.
//-----------------------
lpw = lpwAlign (lpw);
lpdit = (LPDLGITEMTEMPLATE) lpw;
lpdit->x = 95; lpdit->y = 30;
lpdit->cx = 30; lpdit->cy = 15;
lpdit->id = ID_OK; // OK button identifier
lpdit->style = WS_CHILD | WS_VISIBLE | BS_DEFPUSHBUTTON;
lpw = (LPWORD) (lpdit + 1);
*lpw++ = 0xFFFF;
*lpw++ = 0x0080; // button class
lpwsz = (LPWSTR) lpw;
nchar = 1+MultiByteToWideChar (CP_ACP, 0, "Ok", -1, lpwsz, 50);
lpw += nchar;
*lpw++ = 0; // no creation data
//-----------------------
// Define a EDIT.
//-----------------------
lpw = lpwAlign (lpw);
lpdit = (LPDLGITEMTEMPLATE) lpw;
lpdit->x = 5; lpdit->y = 10;
lpdit->cx = 50; lpdit->cy = 12;
lpdit->id = ID_INPUT; // Help button identifier
lpdit->style = ES_LEFT | WS_BORDER | WS_TABSTOP | WS_CHILD | WS_VISIBLE;
lpw = (LPWORD) (lpdit + 1);
*lpw++ = 0xFFFF;
*lpw++ = 0x0081; // edit class atom
/*lpwsz = (LPWSTR) lpw;
lstrcpyW(lpwsz, L"Edit"); // button label (Unicode)
lpw = (LPWORD) (lpwsz + lstrlenW(lpwsz) + 1);*/
*lpw++ = 0; // no creation data
GlobalUnlock(hgbl);
if (!hPrevInstance)
{ wndclass.cbSize = sizeof (wndclass);
wndclass.style = CS_HREDRAW | CS_VREDRAW;
wndclass.lpfnWndProc = WndProc;
wndclass.cbClsExtra = 0;
wndclass.cbWndExtra = 0;
wndclass.hInstance = hInstance;
wndclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
wndclass.hCursor = LoadCursor(NULL, IDC_ARROW);
wndclass.hbrBackground = GetStockObject(WHITE_BRUSH);
wndclass.lpszMenuName = "MainMenu";
// Reference to menu name in file HANOI.RC
wndclass.lpszClassName = szAppName;
// Name used in call to CreateWindow.
if (!RegisterClassEx(&wndclass)) return FALSE;
}
hMenu = CreateMenu ();
AppendMenu (hMenu, MF_STRING, IDM_NEW, "&New");
AppendMenu (hMenu, MF_STRING, IDM_STOP, "&Stop");
AppendMenu (hMenu, MF_STRING, IDM_EXIT, "&Exit");
hWindow = hWnd = CreateWindow(
szAppName,
"", // Text for window title bar.
WS_OVERLAPPEDWINDOW, // Window style.
0, // Initial x position
0, // Initial y position.
xScreen, // Width.
yScreen, // Height.
NULL, // Parent window handle.
hMenu, //NULL, // Window menu handle.
hInstance, // Program instance handle.
NULL // Create parameters.
);
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
SetTimer(hWnd, 1, 1500, NULL);
while (GetMessage(&msg, NULL, 0, 0))
{ TranslateMessage(&msg); // Translates virtual key codes
DispatchMessage(&msg); // Dispatches message to window
}
GlobalFree(hgbl);
return msg.wParam; // Returns the value from PostQuitMessage
}
const char * /*const*/ pLine1 =
"One by one, all disks move from A to C,";
const char * /*const*/ pLine2 =
"using B temporarily. A larger disk must";
const char * /*const*/ pLine3 =
"not be placed on top of a smaller one.";
long FAR PASCAL WndProc(HWND hWnd, UINT message,
WPARAM wParam, LPARAM lParam)
{ static int Stack[3][NMAX], StPtr[3], xA, xB, xC, rMaxDisk,
h, rPeg, yBase, yH, xScreen, yScreen;
int xLeft, xRight, d;
static long nCount, nTotalCount;
FARPROC lpProcInput;
char buf[25];
HDC hDC;
PAINTSTRUCT ps;
HPEN hPen, hWoodPen, hOldPen, hDiskPen, hWhitePen;
HBRUSH hBrush, hWoodBrush, hOldBrush, hDiskBrush, hWhiteBrush;
HFONT hFont, hOldFont;
int i, j, k, xText, xMargin;
COLORREF DiskColor;
SIZE sizeRect;
switch (message)
{
case WM_SIZE:
xScreen = LOWORD(lParam); yScreen = HIWORD(lParam);
break;
case WM_PAINT:
hDC = BeginPaint(hWnd, &ps);
SetMapMode(hDC, MM_ANISOTROPIC);
SetViewportOrgEx(hDC, 0, yScreen, NULL);
SetWindowExtEx(hDC, 10000, 10000, NULL);
SetViewportExtEx(hDC, xScreen, -yScreen, NULL);
yBase = 5000; yH = 9500;
d = 300; xA = 2000; xB = 5000; xC = 8000;
rMaxDisk = 1300; xLeft = 200; xRight = 9800; rPeg = 60;
hWoodPen = CreatePen(PS_SOLID, 0, WoodColor);
hWoodBrush = CreateSolidBrush(WoodColor);
hOldPen = SelectObject(hDC, hWoodPen);
hOldBrush = SelectObject(hDC, hWoodBrush);
Rectangle(hDC, xLeft, yBase, xRight, yBase-d);
Rectangle(hDC, xA-rPeg, yH, xA+rPeg, yBase);
Rectangle(hDC, xB-rPeg, yH, xB+rPeg, yBase);
Rectangle(hDC, xC-rPeg, yH, xC+rPeg, yBase);
SelectObject(hDC, hOldPen);
SelectObject(hDC, hOldBrush);
DeleteObject(hWoodPen);
DeleteObject(hWoodBrush);
hFont = CreateFont(900, 200, 0, 0, 500, 0, 0, 0,
ANSI_CHARSET, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS,
DEFAULT_QUALITY, FF_SWISS, NULL);
hOldFont = SelectObject(hDC, hFont);
SetTextAlign(hDC, TA_CENTER);
TextOut(hDC, xA, 4600, "A", 1);
TextOut(hDC, xB, 4600, "B", 1);
TextOut(hDC, xC, 4600, "C", 1);
SetTextAlign(hDC, TA_LEFT);
//xText = LOWORD(GetTextExtentPoint(hDC, pLine1, strlen(pLine1), &sizeRect));
GetTextExtentPoint(hDC, pLine1, strlen(pLine1), &sizeRect);
xMargin = (10000 - sizeRect.cx)/2;
TextOut(hDC, xMargin, 3500, pLine1, strlen(pLine1));
TextOut(hDC, xMargin, 2300, pLine2, strlen(pLine2));
TextOut(hDC, xMargin, 1100, pLine3, strlen(pLine3));
SelectObject(hDC, hOldFont);
DeleteObject(hFont);
for (j=0; j<3; j++)
{ // Restore tower j:
int xj = xA + j * (xB - xA);
for (k=0; k0; i--) Stack[0][N-i] = i;
StPtr[0] = N; StPtr[1] = StPtr[2] = 0;
status = BUSY;
nCount = 0;
nTotalCount = (1L << N) - 1;
InvalidateRect(hWnd, NULL, TRUE);
} else
if (status == BUSY)
{ int jSrc, jDest, dx=xB-xA, xScr, xDest, kSrc, kDest, ri;
// Find source and destination pegs and move one disk:
if (Hanoi(&jSrc, &jDest) == 0) status = WAITING; else
{ hDC = GetDC(hWnd);
SetMapMode(hDC, MM_ANISOTROPIC);
SetViewportOrgEx(hDC, 0, yScreen, NULL);
SetWindowExtEx(hDC, 10000, 10000, NULL);
SetViewportExtEx(hDC, xScreen, -yScreen, NULL);
kSrc = --StPtr[jSrc]; // j = horizontal position
kDest = StPtr[jDest]++; // k = vertical position
Stack[jDest][kDest] = i = Stack[jSrc][kSrc];
// i = disk number
ri = (int)((long)i * rMaxDisk/N); // radius of disk i
DiskColor = GenColor(i);
hPen = CreatePen(PS_SOLID, 0, DiskColor);
hBrush = CreateSolidBrush(DiskColor);
hOldPen = SelectObject(hDC, hPen);
hOldBrush = SelectObject(hDC, hBrush);
xScr = xA + jSrc * dx;
xDest = xA + jDest * dx;
// Disk to destination:
RoundRect(hDC, xDest-ri, yBase+(kDest+1)*h,
xDest+ri, yBase+kDest*h, h/2, h/2);
hWhitePen = GetStockObject(WHITE_PEN);
hWhiteBrush = GetStockObject(WHITE_BRUSH);
SelectObject(hDC, hWhitePen);
SelectObject(hDC, hWhiteBrush);
DeleteObject(hPen);
DeleteObject(hBrush);
// White rectangle to source:
Rectangle(hDC, xScr-ri, yBase+(kSrc+1)*h,
xScr+ri, yBase+kSrc*h);
hWoodPen = CreatePen(PS_SOLID, 0, WoodColor);
hWoodBrush = CreateSolidBrush(WoodColor);
SelectObject(hDC, hWoodPen);
SelectObject(hDC, hWoodBrush);
// Restore portion of the source peg:
Rectangle(hDC, xScr-rPeg, yBase+(kSrc+1)*h,
xScr+rPeg, yBase+kSrc*h);
SelectObject(hDC, hOldPen);
SelectObject(hDC, hOldBrush);
DeleteObject(hWoodPen);
DeleteObject(hWoodBrush);
sprintf(buf, "%5ld (%ld)", ++nCount, nTotalCount);
TextOut(hDC, 50, 9900, buf, strlen(buf));
ReleaseDC(hWnd, hDC);
}
} else SetWindowText(hWnd, pCaption); // Status = WAITING
break;
case WM_COMMAND:
if (wParam == IDM_NEW)
{ if (status != WAITING) break;
/*lpProcInput =
MakeProcInstance((FARPROC)InputProc, hInstGlobal);
DialogBox(hInstGlobal, "N_INPUT", hWnd, lpProcInput);
FreeProcInstance(lpProcInput);*/
DialogBoxIndirect(NULL, (LPDLGTEMPLATE) hgbl,
NULL, (DLGPROC) InputProc);
} else
if (wParam == IDM_STOP)
{ CleanUp();
status = WAITING;
} else
if (wParam == IDM_EXIT)
{ CleanUp();
SendMessage(hWnd, WM_CLOSE, wParam, lParam);
}
break;
case WM_DESTROY:
KillTimer(hWnd, 1);
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0L;
}
BOOL FAR PASCAL InputProc(HWND hDlg, UINT message,
WPARAM wParam, LPARAM lParam)
{ char buffer[25];
int n;
switch(message)
{
case WM_INITDIALOG:
SetFocus(GetDlgItem(hDlg, ID_INPUT));
return TRUE;
case WM_COMMAND:
if (wParam == ID_OK)
{ GetDlgItemText(hDlg, ID_INPUT, buffer, 25);
EndDialog(hDlg, TRUE);
if (sscanf(buffer, "%d", &n) == 1 && n >= 1 && n <= NMAX)
{ N = n;
Push(0, 2, N); // A = 0, B = 1, C = 2
status = STARTING;
SetWindowText(hWindow,
"Towers of Hanoi");
} else
{ char buf[80];
sprintf(buf, "N must be positive and not greater than %d",
NMAX);
MessageBox(hWindow, buf, "Error", MB_ICONSTOP);
}
return TRUE;
}
break;
}
return FALSE;
}