LISTVIEW PATHFINDING (WIN32)

#include <windows.h>
#include <stdlib.h>
#include <math.h>
#include <commctrl.h>
#include <shlobj.h>
#include "resource.h"
#include "liste.h"
#include "pile.h"

#pragma comment(lib, "comctl32.lib")
#define M 10
#define dist(xD, yD, xA, yA) (sqrt((xA - xD) * (xA - xD) + (yA - yD) * (yA - yD)))

RECT rcItem;
LPPOINT lpptDepPosItems, lpptFinPosItems;
HWND hMain, hOther, hList;
HINSTANCE hInst;
HANDLE hHeap;
DWORD dwItemCount, dwMapWidth, dwMapHeight;
int *iSortItem;
char szPath[256], **szName, *szMap;

typedef struct data {
	char szClass[16];
	HWND *hwnd;
} DATA;

struct coord {
	int X; 
	int Y; 
} Direction[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void DisplayError()
{
  LPVOID lpbuf = 0;
  DWORD dwerror = GetLastError();
  FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
                NULL, dwerror, MAKELANGID(LANG_NEUTRAL, SUBLANG_NEUTRAL),
                (LPTSTR) &lpbuf, 0, NULL);
  if(lpbuf) {
    MessageBox(GetFocus(), (LPCTSTR)lpbuf, 0, 0x30);
    LocalFree(lpbuf);
  }
}

int ObtDirectory() 
{
	BROWSEINFO bi;
  ITEMIDLIST *il;
  char buff[300];

  bi.hwndOwner = hMain;
  bi.pidlRoot  = NULL;
  bi.pszDisplayName = buff;
  bi.lpszTitle = "Choisissez un répertoire :";
  bi.ulFlags   = 0;
  bi.lpfn      = NULL;
	if (NULL == (il = SHBrowseForFolder(&bi))) { DisplayError(); return 0; }
    
	return SHGetPathFromIDList(il, szPath);
}

//Ne trie pas directement les elements, mais place l'ordre correct des chaines dans un tableau
//Tri quicksort (optimisations possibles : suppression de la recursion, meilleur choix de la mediane)
void TriQuick(int g, int d)
{
	int i, j, v, u;

	if (d - g > M) { //ne trie pas les partitions de taille inferieure a M (10)
		v = iSortItem[d]; i = g; j = d;
		for ( ; ; ) {
			while (stricmp(szName[iSortItem[i]], szName[iSortItem[v]]) < 0 && i < d) i++;
			while (stricmp(szName[iSortItem[j]], szName[iSortItem[v]]) > 0 && j > g) --j;
			if (j <= i) break;
			u = iSortItem[i]; iSortItem[i] = iSortItem[j]; iSortItem[j] = u;
		}
		u = iSortItem[i]; iSortItem[i] = iSortItem[d]; iSortItem[d] = u;
		TriQuick(g, i - 1);
		TriQuick(i + 1, d);
	}
}

//Tri par insertion
void TriFinal(int dwNumber)
{
	int i, j, v;

	for (i = 1; i < dwNumber; ++i) {
		v = iSortItem[i];
		j = i;
		while (j > 0 && stricmp(szName[iSortItem[j - 1]], szName[v]) > 0) {
			iSortItem[j] = iSortItem[j - 1];
			j--;
		}
		iSortItem[j] = v;
	}
}

BOOL CALLBACK EnumProc(HWND hwnd, LPARAM lparam)
{
	char szBuf[16];

	GetClassName(hwnd, szBuf, 16);
	if (!strcmp(szBuf, ((DATA *)lparam)->szClass)) {
		*((DATA *)lparam)->hwnd = hwnd;
		return 0;
	}
	return 1;
}

void  PathFinding(DWORD dwCount)
{
	DWORD dwCost;
	BOOL bExit = 0;
	struct noeud *p, *d, *n;
	int i, j;

	for (i = 0; i < dwCount; ++i) {
		SendMessage(hList, LVM_ENSUREVISIBLE, iSortItem[i], 0);
		InitialiserListe();
		n = malloc(sizeof *n);
		n->item.ptPos.x = lpptDepPosItems[iSortItem[i]].x; 
		n->item.ptPos.y = lpptDepPosItems[iSortItem[i]].y; 
		n->item.CoutFromDep = 0;
		n->item.CoutToEnd = dist(n->item.ptPos.x, n->item.ptPos.y, lpptFinPosItems[iSortItem[i]].x, lpptFinPosItems[iSortItem[i]].y);
		n->item.Poids = n->item.CoutFromDep + n->item.CoutToEnd;
		n->item.Parent = 0;
		InsererFirst(OPEN, n);
		while (!ListeVide(OPEN)) {
			p = GetBetterNode(OPEN);
			if (p->item.ptPos.x == lpptFinPosItems[iSortItem[i]].x && p->item.ptPos.y == lpptFinPosItems[iSortItem[i]].y) {
				break;
			} else {
				for (j = 0; j < 4 && !bExit; ++j) {
					int x = p->item.ptPos.x + Direction[j].X;
					int y = p->item.ptPos.y + Direction[j].Y;
					if (x >= 0 && y >= 0 && x <= dwMapWidth && y <= dwMapHeight) {
						d = malloc(sizeof *d);
						d->item.ptPos.x = x; d->item.ptPos.y = y;
						dwCost = dist(d->item.ptPos.x, d->item.ptPos.y, lpptFinPosItems[iSortItem[i]].x, lpptFinPosItems[iSortItem[i]].y);
						if (n = SearchNode(OPEN, d)) {
							//Si le poids n'est pas meilleur, on quitte
							if (dwCost > n->item.Poids)	goto FREE;
							//Sinon, on le supprime de OPEN, pour le modifier et ensuite le reinserer
							Supprimer(OPEN, n); goto MODIFY;
						}
						if (SearchNode(CLOSED, d)) goto FREE;
						//Ca bugge si l'arrivée est occupée par un item donc on fait une verification la aussi (pas beau mais obligatoire :()
						if (x == lpptFinPosItems[iSortItem[i]].x && y == lpptFinPosItems[iSortItem[i]].y) bExit = 1;
						if (szMap[y * dwMapWidth + x] == '1' && !bExit) goto FREE;
		MODIFY:
						d->item.CoutFromDep = p->item.CoutFromDep;
						d->item.CoutToEnd = dwCost;
						d->item.Poids = d->item.CoutFromDep + d->item.CoutToEnd;
						d->item.Parent = p;
						InsererFirst(OPEN, d);
		FREE:		free(d);
					}
				}
			}
			InsererFirst(CLOSED, p);
			Supprimer(OPEN, p);
			bExit = 0;
		} 
		InitialiserPile();
		while (p->item.Parent) {
			Empiler(p);
			p = p->item.Parent;
		}
		while (!PileVide()) {
			p = (struct noeud *)Depiler();
			SendMessage(hList, LVM_SETITEMPOSITION, iSortItem[i], MAKELPARAM(p->item.ptPos.x * rcItem.right, p->item.ptPos.y * rcItem.bottom));
			SendMessage(hList, LVM_ENSUREVISIBLE, iSortItem[i], 0);
			Sleep(5);		
		}
		szMap[lpptDepPosItems[iSortItem[i]].y * dwMapWidth + lpptDepPosItems[iSortItem[i]].x] = 0;
		szMap[lpptFinPosItems[iSortItem[i]].y * dwMapWidth + lpptFinPosItems[iSortItem[i]].x] = '1';
		DetruirePile();
		DetruireListe();
	}
}

//Principe du code :
//-	Desorganise les icones des listviews explorer et desktop permettant ainsi l'apparition d'obstacles et d'une certaine distance entre point de depart
//	et d'arrivée (imaginez si les icones etaient placées comme lors d'une reorganisation automatique, on pourrait pas les faire 
//	bouger :()
//- Tri par ordre alphabetique : on se sert d'un tableau d'entiers a coté qui va retenir l'ordre des elements, ca 
//	evite le deplacement de chaines de caracteres longues (donc on y gagne) : c'est une technique de tri par faux pointeurs
//Code largement inspiré de la source de ymca2003 (http://www.cppfrance.com/code.aspx?id=22940)
//Ne supporte que Win2k/XP
void LaunchPathFinding()
{
	STARTUPINFO si = { sizeof(si) };
	RECT rcList;
	PROCESS_INFORMATION pi;
	POINT ptListApprox;
	LVITEM lvItem;
	LPVOID lpData, lpChar, lplvItem, lpPos, lpRect;
	HANDLE hProcess;
	DWORD dwProcessId = 0, dwRet, dwStyle, dwDim, dwTemp;
	DATA dt;
	BOOL bExplorer = 0;
	int i, j, k;
	char *c = szPath, szCmd[512] = "c:\\WINDOWS\\explorer.exe ";

	//Choix du dossier a rearranger
	if (!ObtDirectory()) return;
	while (*c) c++;
	while (*c != '\\') c--;
	//L'user a choisi le bureau
	if (!strcmp("\\Bureau", c)) {
		hOther = FindWindow("ProgMan", 0);
		hList = GetTopWindow(GetTopWindow(hOther));
	} else {
		si.dwFlags = STARTF_USESHOWWINDOW;
		si.wShowWindow = SW_SHOWMAXIMIZED;
		strcpy(szCmd + 24, szPath);
		if (!CreateProcess(0, szCmd, 0, 0, 0, 0, 0, 0, &si, &pi)) { DisplayError(); return; }
		//WaitForInputIdle(pi.hProcess, INFINITE); //NE FONCTIONNE PAS (?!)
		Sleep(4000);
		dt.hwnd = &hOther;	strcpy(dt.szClass, "CabinetWClass");
		EnumWindows(EnumProc, (LPARAM)&dt);
		CloseHandle(pi.hProcess); CloseHandle(pi.hThread);
		dt.hwnd = &hList; strcpy(dt.szClass, "SysListView32");
		EnumChildWindows(hOther, EnumProc, (LPARAM)&dt);
		bExplorer = 1;
	}
	GetWindowThreadProcessId(hList, &dwProcessId);
	dwStyle = GetWindowLong(hList, GWL_STYLE);
	if (dwStyle & LVS_AUTOARRANGE) SetWindowLong(hList, GWL_STYLE, dwStyle & (~LVS_AUTOARRANGE));
	hProcess = OpenProcess(PROCESS_VM_OPERATION | PROCESS_VM_READ | PROCESS_VM_WRITE, 0, dwProcessId);
	if (!hProcess) return;
	dwItemCount = SendMessage(hList, LVM_GETITEMCOUNT, 0, 0);
	if (!dwItemCount) { MessageBox(0, "Aucun élément dans la listview.", 0, 0); goto Close; }
	GetClientRect(hList, &rcList);
	dwDim = SendMessage(hList, LVM_APPROXIMATEVIEWRECT, dwItemCount, -1); //si les items ne sont pas tous visibles
	ptListApprox.x = dwDim & 0xFFFF;
	ptListApprox.y = dwDim >> 16;
	if (bExplorer) { 
		if (rcList.bottom < 5 * ptListApprox.y && rcList.right < 5 * ptListApprox.x) {
			rcList.bottom *= 5; rcList.right *= 5;
		} else {
			rcList.bottom = rcList.bottom < ptListApprox.y ? ptListApprox.y : rcList.bottom;
			rcList.right = rcList.right < ptListApprox.x ? ptListApprox.x : rcList.right;
		}
	}
	lpData = VirtualAllocEx(hProcess, 0, sizeof(LVITEM) + sizeof(POINT) + sizeof(RECT) + 256, MEM_COMMIT, PAGE_READWRITE);
	if (!lpData) goto Close;
	lpChar		= (LPBYTE)lpData + sizeof(LVITEM) + sizeof(POINT) + sizeof(RECT);
	lpRect		= (LPBYTE)lpData + sizeof(LVITEM) + sizeof(POINT);
	lplvItem	= (LPBYTE)lpData + sizeof(POINT);
	lpPos			= (LPBYTE)lpData;
	lpptDepPosItems = (LPPOINT)HeapAlloc(hHeap, 0, dwItemCount * sizeof(POINT));
	if (!lpptDepPosItems) goto VFree;
	szName = (char **)HeapAlloc(hHeap, 0, dwItemCount * sizeof(char *));
	if (!szName) goto PosFree;
	SendMessage(hList, LVM_GETITEMRECT, 0, (LPARAM)lpRect);
	ReadProcessMemory(hProcess, lpRect, &rcItem, sizeof(RECT), &dwRet);
	rcItem.bottom -= (rcItem.top - 10); rcItem.right -= (rcItem.left - 5); //RECT des items
	dwMapWidth = (rcList.right / rcItem.right); dwMapHeight = (rcList.bottom  / rcItem.bottom);
	szMap = (char *)HeapAlloc(hHeap, HEAP_ZERO_MEMORY, dwMapHeight * dwMapWidth + 1);
	if (!szMap) goto SZFree;
	for (i = 0; i < dwItemCount; ++i) {
		ZeroMemory(&lvItem, sizeof(LVITEM));
		lvItem.iItem = i;
		lvItem.mask = LVIF_TEXT;
		lvItem.cchTextMax = 256;
		lvItem.pszText = (char *)lpChar;
		WriteProcessMemory(hProcess, lplvItem, &lvItem, sizeof(LVITEM), &dwRet);
		szName[i] = (char *)HeapAlloc(hHeap, 0, 256);
		SendMessage(hList, LVM_GETITEMTEXT, i, (LPARAM)lplvItem);
		ReadProcessMemory(hProcess, lpChar, szName[i], 256, &dwRet);
		dwTemp = ((bExplorer) ? ptListApprox.y: ptListApprox.x);
		lpptDepPosItems[i].y = dwTemp + (rand() % (rcList.bottom - dwTemp)) / rcItem.bottom * rcItem.bottom;
		lpptDepPosItems[i].x = (rand() % rcList.right + 1) / rcItem.right * rcItem.right;
		SendMessage(hList, LVM_SETITEMPOSITION, i, MAKELPARAM(lpptDepPosItems[i].x, lpptDepPosItems[i].y));
		lpptDepPosItems[i].x /= rcItem.right; lpptDepPosItems[i].y /= rcItem.bottom;
		szMap[lpptDepPosItems[i].y * dwMapWidth + lpptDepPosItems[i].x] = '1';
	}
	//Replace correctement les icones sur la 'grille' de la listview
	SendMessage(hList, LVM_ARRANGE, LVA_SNAPTOGRID, 0);
	iSortItem = (int *)HeapAlloc(hHeap, 0, dwItemCount * sizeof(int));
	if (!iSortItem) goto MFree;
	for (i = 0; i < dwItemCount; ++i) iSortItem[i] = i; 
	TriQuick(0, dwItemCount - 1);	//Tri QuickSort
	TriFinal(dwItemCount);				//Tri par insertion pour finir le boulot
	//On determine maintenant les coordonnées que vont devoir atteindre les items
	lpptFinPosItems = (LPPOINT)HeapAlloc(hHeap, 0, dwItemCount * sizeof(POINT));
	if (!lpptFinPosItems) goto SFree;
	lpptFinPosItems[iSortItem[0]].x = 0;
	lpptFinPosItems[iSortItem[0]].y = 0;
	for (i = 1; i < dwItemCount; ++i) {
		k = iSortItem[i]; j = iSortItem[i - 1];
		lpptFinPosItems[k].y = lpptFinPosItems[j].y;
		if (lpptFinPosItems[j].x >= rcList.right - 2 * rcItem.right) {
			lpptFinPosItems[k].x = 2; 
			lpptFinPosItems[k].y += rcItem.bottom;
		} else lpptFinPosItems[k].x = lpptFinPosItems[j].x + rcItem.right;
	}
	for (i = 1; i < dwItemCount; ++i) {
		lpptFinPosItems[iSortItem[i]].x /= rcItem.right; lpptFinPosItems[iSortItem[i]].y /= rcItem.bottom;
	}
	//On a les coordonnées de debut et de fin, les dimensions des cases (rcItem),
	//on lance alors le pathfinding 
	PathFinding(dwItemCount);

	HeapFree(hHeap, 0, lpptFinPosItems);
SFree:
	HeapFree(hHeap, 0, iSortItem);
MFree:
	HeapFree(hHeap, 0, szMap);
	for (i = 0; i < dwItemCount; i++) 
		HeapFree(hHeap, 0, szName[i]);
SZFree:
	HeapFree(hHeap, 0, szName);
PosFree:
	HeapFree(hHeap, 0, lpptDepPosItems);
VFree:
	VirtualFreeEx(hProcess, lpData, 0, MEM_RELEASE);
Close:
	CloseHandle(hProcess);
}

BOOL CALLBACK DlgProc(HWND hwnd, UINT message, WPARAM wparam, LPARAM lparam)
{
	switch (message) {
		case WM_INITDIALOG:
			hMain = hwnd;
			hHeap = GetProcessHeap();
			srand(GetTickCount());
			SetClassLong(hwnd, GCL_HICON, (long)LoadIcon(0, IDI_APPLICATION));
      return 1;
		case WM_COMMAND:
			switch (wparam) {
				case IDOK:
          ShowWindow(hwnd, SW_HIDE);
					LaunchPathFinding();
					ShowWindow(hwnd, SW_SHOW);
					break;
				case IDCANCEL:
					EndDialog(hwnd, 0);
					break;
			}
			return 0;
	}

	return 0;
}

int __stdcall WinMain(HINSTANCE hInstance, HINSTANCE p, LPSTR q, int r)
{
	hInst = hInstance;
	DialogBoxParam(hInst, (LPCTSTR)IDD_PATH, 0, DlgProc, 0);
	return 0;
}