Založte si na GitLabu nový repozitář. Bude se jmenovat ViSort. V repozitáři budou čtyři oddělené projekty (čtyři oddělená VS solutions), abychom vyzkoušeli koncepci loosely coupled komponent aplikace. Cílem bude vizualizovat efektivitu třídicích algoritmů.
Druhý a třetí projekt budou "propojené" pouze tím, že oba budou používat knihovnu tříd, která vznikne sestavením (buildem) prvního projektu. V knihovně tříd z prvního projektu bude rozhraní (interface) ISortAlgorithm s několika metodami pro synchronizaci obou aplikací.
Můžete si vybrat, zda budete pracovat v .NET Frameworku (4.7.2 nebo 4.8), nebo v .NET Core (5.0). Já ale doporučuji raději všechny projekty založit jako .NET Framework. Budete s tím mít méně problémů. Nicméně, kdo potřebuje nějaké fíčury z .NET 5, tak holt použijete .NET Core 5.0.
Kdo si nebude vědět rady s tím, jak začít, může se podívat na náznak řešení tady.
V ZIP archivu jsou všechny 4 projekty, některé z nich ve velmi zjednodušené podobě, aby byla zřejmá spolupráce mezi nimi, a zároveň zbylo místo pro vaši práci. Knihovna tříd (class library) obsahuje pouze rozhraní ISortAlgorithm a dá se rovnou použít. Orchestrátor (ten čtvrtý projekt) je taktéž téměř hotov, jen do něj potřebujete "nasázet" vaše implementace třídění a vaši appku s vizualizačním formulářem.
Těžiště vaší práce bude spočívat ve druhém a třetím projektu. V ukázce jsou místo skutečných třídicích algoritmů
pouze tzv. "fake", či spíše "mock" objekty, které sice implementují předepsaný interface ISortAlgorithm,
ale ve skutečnosti nic netřídí, pouze vracejí nějaké "rozumné" hodnoty, které interface předepisuje.
Vizualizace zase nepoužívá GDI grafiku (kterou použijete vy), pouze zobrazuje pole hodnot, které se má setřídit,
v různých stavech tak, jak mock-ované třídění po jednotlivých krocích probíhá.
Náznak vzorového řešení nicméně ukazuje, jak se vypořádat se synchronizací mezi vlákny vaší aplikace.
Scénář, ve kterém pracujete s Windows Forms a tzv. Single Thread Apartment
(viz atribut STAThread, který dekoruje metodu Main),
totiž vyžaduje, aby kód vaší aplikace interagoval s grafickými komponentami operačního systému (okna, text boxy, tlačítka apod.)
pouze v hlavním (výchozím) vláknu, nikoliv v tzv. background threads, ve kterých běží výpočet (v našem případě třídění).
S tímto omezením vám pomůže třída BackgroundWorker,
kterou pro vás ve jmenném prostoru System.ComponentModel již připravili vývojaři .NET-u.
První projekt (Class Library) se bude jmenovat ViSortCommon (VS solution ViSortCommonSol, VS project ViSortCommonLib). Bude obsahovat již zmíněný interface ISortAlgorithm. Interface ISortAlgorithm bude mít dvě sady metod:
Pro vizualizaci se samozřejmě mohou použít i některé metody ze základní sady (např. pro zadání vstupu a pro získání výstupu).
public interface ISortAlgorithm
{
// Basic methods.
void SetInputData(List<int> unsorted);
void Sort();
List<int> GetOutputData();
int GetTotalNumberOfComparisons();
int GetTotalNumberOfMoves();
// Advanced methods.
void StartSorting();
bool HasSortingCompleted();
void ProceedOneStep();
int GetLastStepComplexityInComparisons();
int GetLastStepComplexityInMoves();
List<int> GetInterimData();
}
Pokud jde o základní metody, tak pro setřídění seznamu celých čísel provedeme následující postup:
Při vizualizaci budeme potřebovat i některé pokročilé metody:
Druhý projekt (Console App) se bude jmenovat ViSortLogic (VS solution ViSortLogicSol, VS project ViSortLogicCon). Bude obsahovat alespoň dvě třídy, které implementují interface ISortAlgorithm. Dále v něm bude nějaký jednoduchý test, který ověří, že každý z algoritmů funguje (správně třídí).
Projekt bude mít podadresář lib a v něm bude DLL knihovna vzniklá kompilací prvního projektu s interfacem. Projekt bude mít nastavenu závislost na této assembly.
Při implementaci pokročilých metod se snažte algoritmus "rozsekat" na menší kousky tak, aby každý kus představoval jeden logický krok postupu. Např. jedno porovnání a jedno prohození. Nebo např. několik porovnání a prohození, kterými projdeme jednu celou iteraci v Bubble sortu. Apod.
Hint:
Jelikož bude jednotlivé kroky volat někdo zvenčí (vaše vizualizační část s GDI grafikou),
musíte si stav třídění mezi jednotlivými kroky (včetně nějakých pomocných indexů apod.) uchovávat v proměnných instance objektu,
který reprezentuje váš algoritmus, tedy v proměnných instance té třídy, která implementuje ISortAlgorithm.
Třetí projekt (WinForms App) se bude jmenovat ViSortGDI (VS solution ViSortGDISol, VS project ViSortGDIWin). Projekt bude obsahovat formulář s panelem, který se použije na vizualizaci průběhu třídění pomocí GDI grafiky. Do formuláře bude možné "injektovat" seznam alespoň dvou tříd, které implementují rozhraní ISortAlgorithm. Na formuláři bude dále tlačítko, kterým se spustí vizualizace.
Projekt bude mít podadresář lib a v něm bude DLL knihovna vzniklá kompilací prvního projektu s interfacem. Projekt bude mít nastavenu závislost na této assembly.
Když se podíváte, jak funguje BackgroundWorker, zjistíte, že informaci
o progresu výpočtu a data výpočtu si mezi sebou hlavní vlákno (které obsluhuje okna a ovládací prvky na nich)
a vlákna běžící na pozadí (ve kterých se provádějí výpočty) vyměňují pomocí hadlerů dvou událostí objektu
BackgroundWorker:
worker_DoWork.
worker_DoWork
se bude provádět v kontextu každého z nich, čili se vlastně bude provádět paralelně několikrát
(podle počtu tříd implementujících nějaké třídění).
Objekt BackgroundWorker má metodu ReportProgress, přes kterou může vlákno běžící na pozadí
předat informaci o progresu výpočtu a aktuální stav pole s daty, které třídíme, do hlavního vlákna aplikace.
worker_ProgressChanged.
Hint:
Protože třídění v reálném čase na datech o velikosti např. n = 20 (počet prvků pole pro třídění je 20)
bude trvat pouze pár desítek milisekund, je dobré v obsluze události DoWork po provedení každého kroku
třídění "zpomalit" průběh třídění tak, že např. cenu jednoho kroku (počet operací porovnání prvků a/nebo prohození prvků)
vynásobíme nějakou časovou konstantou (třeba 500 ms) a necháme vlákno běžící na pozadí chvíli spát (Thread.Sleep),
aby člověk, který vaši aplikaci spustí, byl schopen postup třídění sledovat v sekundách, a ne v milisekundách.
Čtvrtý projekt (WinForms App) se bude jmenovat ViSortUI (VS solution ViSortUISol, VS project ViSortUIWin). Bude mít přístupné všechny 3 předešlé projekty. Projekt bude orchestrovat celou aplikaci:
Projekt bude mít podadresář lib a v něm bude DLL knihovna vzniklá kompilací prvního projektu s interfacem. Projekt bude mít nastavenu závislost na této assembly.
V podadresáři lib bude i DLL/EXE appka vzniklá kompilací druhého projektu s tříděním. Projekt bude mít nastavenu závislost na této assembly.
V podadresáři lib bude i DLL/EXE appka vzniklá kompilací třetího projektu s GDI vizualizací. Projekt bude mít nastavenu závislost na této assembly.
Vizuálním výsledkem vaší práce by mělo být něco podobného, jako ukazuje následující video: