MestInt - Jegyzet osztályokról

AbsztraktÁllapot osztály (absztrakt):
Annak az osztálynak a váza, amely tulajdonképpen a probléma megoldására hozunk létre, dolgozunk ki.
(Érdemes tudni: Immutable = nem változtatható.
Ebben az esetben nem változhat meg a belső állapot. Minden állapotváltoztatás esetén új objektumot hozunk létre.
Szentírás, fogadjátok el, hogy ez jó valamire, hozzám nem ért el ez az információ. :D
Immutable esetén nem kívülről klónozunk hanem belülről (nem kell örökölni az IClonable-t). Azelőtt klónozunk, mielőtt változtatnánk bármin is, így gyakorlatilag elérjük azt, hogy minden példány immutable lesz, tehát a belső állapot nem fog változni, mert minden változtatás előtt készítünk egy klónt, és az új objektumon megy tovább a kísérletezés.)
######## ZH-ban valószínű, hogy az immutable fog kelleni. ########

Állapotokra vonatkozó függvények (abstract):
1) bool ÁllapotE():
	Publikus.
	Ez a függvény kidolgozva megmondja, hogy az operátor nem végez-e rossz műveletet. Kicsit nehéz körülírni; a 3 kancsós problémánál szimplán return true van, mert elég nehéz rosszul önteni a kancsóba, viszont az éhes huszár problémánál itt vizsgáljuk hogy a ló pl a margón van-e.

2) bool CélÁllapotE():
	Publikus.
	Ennek a függvénynek kidolgozott formája mondja meg, hogy elértük-e azt amit szeretnénk, megoldottuk-e a problémát, vagyis hogy terminális csúcson vagyunk-e. A három kancsó probléma terminális csúcsának állapota az, amikor az egyik kancsóban 4 liter víz van. Ekkor a függvény true értékkel tér vissza.

Operátorokra vonatkozó függvények (abstract):
3) int OperátorokSzáma():
	Publikus.
	Visszatér az operátorok számával (ezt sajátkezűleg kell beállítanod, hogy mennyi).

4) bool/AbszraktÁllapot SzuperOperátor(int i):
	Publikus.
	A visszatérési érték mutable esetén bool, immutable esetén AbsztraktÁllapot.
	Itt vannak felsorolva a lehetséges műveletek, az összes lehetséges operátor; az összes lehetséges kancsóöntés, lólépés, kannibál-szerzetes szállítás.
	Az ehhez szükséges függvényt (Töltés, lólépés, stb) nekünk kell kidolgoznunk. A függvény visszatérési értéke a SzuperOperátor függvény visszatérési értékével kell megegyezzen.

Egyéb függvények:
5) virtual object Clone()
	Immutable esetén protected, egyébként publikus.
	Kidolgozva ez tér vissza a klónozandó elem másolatával (copy-konstruktor).

6) override bool Equals(object o)
	Publikus.
	Egyenlő a két objektum, ha a belső állapotuk egyenlő.

7) override GetHashCode()
	Publikus.
	Ha az Equast kidolgozzuk, ki szoktuk ezt is dolgozni. Ez is szentírás (tehát nincs ötletem miért létszükség (nem az, egyébként)), és a VS is warningolni fog miatta.

-------------------------------

Csúcs osztály:
A gráfkereső által bejárható gráf egy-egy csúcsát reprezentálja.
Mezők:
1) Csúcs szülő;
	Az adott csúcs szülőjét tárolja.
2) int mélység;
	A startcsúcs mélysége 0, az ő közvetlen gyerekének 1, és így tovább...
3) AbszratkÁllapot állapot;
	Az aktuális csúcs belső állapotát tárolja.

Konstruktorok:
1) Kezdőállapot:
	public Csúcs(AbsztraktÁllapot kezdőÁllapot)
	{
		állapot = kezdőÁllapot;
		mélység = 0;
		szülő = null;
	}
2) Továbbiakban:
	2/a) Mutable:
		public Csúcs(Csúcs szülő)
		{
			állapot = (AbsztraktÁllapot)szülő.állapot.Clone();
			mélység = szülő.mélység + 1;
			this.szülő = szülő;
		}
	2/b) Immutable:
	Az új csúcs gyártása előtt klónozunk!
	    public Csúcs(AbsztraktÁllapot állapot, int mélység, Csúcs szülő)
		{
			this.állapot = állapot;
			this.mélység = mélység;
			this.szülő = szülő;
		}

Függvények (mind publikus):
1) Csúcs GetSzülő() / int GetMélység()
	C#-osabb megoldás lenne a property itt. Csak a mező értékével tér vissza.
	return szülő; / return mélység;

2) bool TerminálisCsúcsE()
	Egyszerűen meghívja a jelenlegi állapotának a CélÁllapotE() függvényét. Ha ez true, akkor van egy megoldása a keresésnek.
	Ez a báziskritériuma a rekurzív keresésnek.

3) int OperátorokSzáma()
	Meghívja ugyanezt a függvényt az állapotra.
	return  állapot.OperátorokSzáma();

4) bool/AbsztraktÁllapot SzuperOperátor(int i);
	4/a) Mutable:
		Meghívja ugyanezt a függvényt az állapotra.
		return állapot.SzuperOperátor(i);
	4/b) Immutable:
		Gyártunk egy új állapotot (belső klónozás) a függvény hívásával.
			AbsztraktÁllapot új = állapot.SzuperOperátor(i); // ez lesz az új állapot, amit visszaadott a szuperoperátor
			if (új != null) { return new Csúcs(új, mélység + 1, this); } // az immutable konstruktornak megfelelően így térünk vissza az új csúccsal
			else return null; // null, ha egyik szuperoperátor sem volt jó

5) bool Equals(object o)
	Két csúcs akkor egyenlő, ha az állapotuk egyenlő. Tehát: meghívjuk az állapot.Equals-t ugyanígy!

6) int GetHashCode()
	Az előzőhöz hasonlóan az állapot hash kódjával térünk vissza.

7) string ToString()
	Itt is: az állapot ToString függvényét hívjuk meg.

-------------------------------

Gráfkereső osztály (absztrakt):
Egy gráfkereső (pl. backtrack) algoritmus váza.

Mezők:
1) Csúcs startCsúcs;
	A gráf gyökere, a start.

Konstruktor:
	Csak a startCsúcsot kell beállítani, ahonnan a kereső keresni fog.

Függvények:
1) Csúcs GetStartCsúcs()
	Protected.
	Megint csak propertyvel lenne szebb, dehát a java átka.... a startcsúccsal tér vissza.
2) Keresés() (absztrakt)
	Publikus.
	Override-olandó, itt hajtódik végre minden lényeges művelet.

3) void MegoldásKiírása(Csúcs csúcs)
	Publikus.
	Két eset lehetséges: vagy van megoldás, vagy nincs. Ha van megoldás, a függvénynek átadott Csúcs objektum nem lesz null. Ha nincs megoldás, akkor a csúcs null, ekkor ezt kiíratjuk és kilépünk (return).
	Ha van megoldás, akkor meg kell fordítani a csúcsok sorrendjét, amit megjegyzett a kereső, hogy a kiíratás ne fordított sorrendben történjen. Ez egy veremmel könnyen megvalósítható: belepakolod sorban, és fordított sorrendben kiolvasod. Addig kéred le a csúcs szülőjét, amíg el nem éred a start csúcsot (a startcsúcs szülője null).
		Stack<Csúcs> megoldás = new Stack<Csúcs>();
        Csúcs aktCsúcs = csúcs;
        while (aktCsúcs != null)
        {
            megoldás.Push(aktCsúcs);
            aktCsúcs = aktCsúcs.GetSzülő();
        }
	...és ezután szépen kiíratjuk őket sorban.
        foreach (Csúcs akt in megoldás)
			Console.WriteLine(akt);

-------------------------------

BackTrack osztály (örökli a GráfKereső osztályt):
A visszalépéses keresést megvalósító gráfkereső osztály.

Mezők:
	1) Csúcs startCsúcs;
		Örökölt.
	2) bool emlékezetes;
		Hogy emlékezetes backtracket szeretnénk-e avagy sem.. (emlékezetes: megjegyzi a szülőket, tudva ezzel az útvonalat, ahogyan eljutott a csúcsig. Enélkül nem tudnánk kiíratni a megoldáshoz vezető utat.)
	3) int korlát;
		Hogy korlátos backtracket szeretnénk-e avagy sem.. (korlát: egy bizonyos mélységi határ, aminél messzebb már nem keres tovább a gráfkereső)

Konstruktorok:
	1) A háromparaméteres konstruktor a "fő", az hívja meg az ősosztály konstruktorát, ahol beállítjuk a startcsúcsot. A többi mező úgyis csak a backtrack osztályban létezik. A többi konstruktor meghívja ezt a konstruktort, a hiányzó paramétert pótolva egy 0-val a korlát esetén, false-al az emlékezetes esetén.
		public BackTrack(Csúcs startCsúcs, int korlát, bool emlékezetes)
			: base(startCsúcs)
		{
			this.korlát = korlát;
			this.emlékezetes = emlékezetes;
		}
	Továbbiak:
	2) Emlékezetes, nem korlátolt
	3) Nem emlékezetes, korlátos

Függvények:
	1) Egy függvény van, a keresés.
		1/a) A paraméter nélküli publikus, ez a gyökérelemtől elkezdi a keresést.
		Ez kapásból meghívja a paraméterezett keresés függvényt, csak a startcsúcsot adja át neki. (return Keresés(GetStartCsúcs());).
		1/b) A paraméterezett privát, ez egy adott csúcsból kezd el keresni.
			Folyamata:
				1) Lekérdezi az aktuális mélységet.
				2) Megvizsgálja, hogy korlátos backtrackről van-e szó (korlát > 0 [korlát = 0, ha nem korlátos]), és ha igen, akkor kívül esett-e már a keresés a mélységen (mélység >= korlát). Ha igen, nullal tér vissza.
				3) Megvizsgálja, hogy emlékezetes backtrack-e, s ha igen, eltárolja a szülőt (aktSzülő = aktCsúcs.GetSzülő();),
				4) Végigfut egy while ciklus ami a körfigyeléshez kell. Megnézi, hogy az aktuális úton szerepelt-e már az aktuális csúcs. Ha igen akkor visszalép, hiszen körbe került (volt min. 2x ugyan az a csúcs).
				5) Báziskritérium!! Megnézi hogy az aktuális csúcs terminális csúcs-e, vagyis hogy a csúcs állapota célállapotban van-e. (Ez esetben visszatér az aktuális csúccsal.)
				6) Indul egy forciklus, ami gyakorlatilag végignézi az aktuális csúcs gyerekelemeit. A ciklus az operátorok számáig megy.
					Mutable:
						1) Gyárt egy új csúcsot (copy konstruktor)
						2) Megnézi hogy alkalmazható-e az i. operátor
						3) Ha nem, pörög egyet a ciklus, növeljük az i-t egyel
						4) Ha igen, akkor indul egy új rekurzió, onnan folytatva tovább a keresést.
						5) Ha egy keresés befejeződött, megnézzük, hogy a csúcs amivel visszatért a keresés, terminális-e (nem egyenlő nullal).
						6) Ha igen, akkor visszaadjuk a csúcsot, mint terminális csúcsot.
						7) Ha nem, akkor folytatjuk a keresést tovább.
						8) Ha elfogytak az operátorok, a keresés nullal tér vissza. Ha a legfelső keresés is nullal tér vissza, nincs megoldás.
					Immutable:
						A folyamat hasonló az előzőhöz, néhány különbséggel.
						1) Gyárt egy új csúcsot, ami a szuperoperátor visszatérési értéke. (Csúcs újCsúcs = aktCsúcs.SzuperOperátor(i);)
						2) Megnézi hogy az új csúcs null-e (alkalmazható volt-e az operátor)
						3) Ha nem, megy tovább a ciklus
						4) Ha igen, indul egy újabb rekurzió az új csúcsból.
						....de innen minden ugyanaz, mint a mutable esetén.

-------------------------------

Főprogram:
1) Startcsúcs példányosítása (Csúcs konstruktorába ugye egy absztraktállapot-kompatibilis példány kell, pölö: Csúcs startcsúcs = new Csúcs(new HáromKancsóÁllapot()));
2) Gráfkereső példányosítása (péééééldául BackTrack, aminek át kell adni a startcsúcsot, opcionálisan a korlátot és azt, hogy emlékezetes legyen-e)
3) kereső.MegoldásKiírása(kereső.Keresés());

És.... ennyi!