rekurzió: (főnév) lásd: rekurzió
És megvan a hiba. Miután az előző bejegyzésben említett debugprinteket használva lokalizáltam a végtelen ciklus forrását, hatalmas megvilágosodásban volt részem: a terminálatlan rekurzió bizony terminálatlan marad saját maga meghívása után is. Persze, hozzá kell tegyem, hogy nem egészen vagyok tisztában még a típusosztályokkal, de nagy nehezen sikerült rájönnöm a probléma okára.
Adott egy kölcsönösen rekurzív definíció: legyen egy Node (csomópont) osztályunk, amiből útszegmensek indulnak ki, és hát legyen egy Edge (él, útszegmens) osztályunk is. A Node tartalmaz egy pozíciót, meg a belőle kiinduló éleket. Az Edge pedig tartalmazza a két végpontját, amik ugye Node-ok. Tehát a Node Edge-eket tartalmaz, az Edge meg Node-okat. Ezzel eddig nem lenne nagy probléma.
Na de próbáljunk meg összehasonlítani - mondjuk - két Node-ot. Alapértelmezett módon az összehasonlítás úgy zajlik, hogy az osztály minden elemét (jelen esetben a pozíciót és a kiinduló éleket) külön-külön összehasonlítjuk. Tehát, ugyanaz-e a pozíciója a két Node-nak, és ugyanazok-e a kiinduló élek. Ehhez képesnek kell lennünk két él összehasonlítására. Ami, ha alkalmazzuk az előzőekben lemondottakat, úgy történik, hogy összehasonlítjuk az élek elemeit külön-külön. Vagyis összehasonlítjuk a kezdőpontokat, ami ugye Node típusú, meg aztán a végpontokat. És itt jön a gubanc: épp ugyanazokat a Node-okat kellene megvizsgálni, amiknek a vizsgálatában tartunk épp. Tehát nem tudunk összehasonlítani két Node-ot, ha még nincsenek összehasonlítva, mert két Node akkor egyenlő, ha minden Edge-ük is egyenlő, ami viszont akkor egyenlő, ha a Node-jaik egyenlők.
Példa.
Legyen négy Node-unk: node_A_start, node_A_end, node_B_start, node_B_end. Aztán legyen két Edge-ünk: edge_A, edge_B. Az edge_A él kezdő- és végpontja node_A_start és node_A_end. Az edge_B élé pedig - értelemszerűen - node_B_start és node_B_end. Ugyanakkor a node_A_start-ból kiinduló él ugye az edge_A, valamint az node_A_end-ből kiinduló él is az edge_A. A "b"-s pontokra hasonló logika vonatkozik.
Kérdés: egyenlő-e a node_A_start és a node_B_start?
Hát, nézzük: két Node akkor egyenlő, ha a pozíciójuk és a belőlük kiinduló él ugyanaz. Tegyük fel, hogy most véletlenül ugyanaz a pozíciójuk, tehát az éleket kell már csak ellenőrizni. A node_A_start-ból kiinduló él az edge_A, a node_B_start-ból kiinduló él pedig az edge_B. Össze kell hasonlítani őket. Két Edge akkor egyenlő, ha a kezdő-, és vég-node egyenlő. Tehát össze kell hasonlítani az edge_A kezdőpontját, ami node_A_start, és az edge_B kezdőpontját, ami node_B_start. Vagyis azt kell ellenőrizni, hogy egyenlő-e a node_A_start és a node_B_start. És most akkor ugorjunk vissza a kérdésre, mert pont ezt kezdtük el vizsgálni. (Ki az, aki emlékezik még a Win95-ös időkre? Amikor még először a 3.1-et kellett telepíteni, és utána jöhetett a 95? Na, innen terjedt el "A Windows 3.1 telepítéséhez először telepítenie kell a Windows 3.1-et" mondás is :D Körülbelül ugyanaz a probléma :))
Ez azért eltart egy darabig (egészen pontosan végtelen ideig a jelenlegi PC-ken), így jelentős lassulásra lehetne számítani, ha ezt így hagynám :D De, miután felfedeztem a problémát, már nagy örömmel kezdtem neki a megoldásnak, ami egész egyszerűen annyit jelentett, hogy - és ezt nyugodtan besorolhatjátok hack-nek - a Node-ból kiinduló éleket nem vizsgáljuk. Akkor lesz egyenlő két Node, ha a pozíciójuk azonos. Ami teljesen értelmes esetünkben, mivel, ha két útkereszteződés ugyanott van, akkor az gyakorlatilag egy útkereszteződés :D (Persze, most lehetne hőbörögni, hogy há'de a mutatózás, meg indexelés sokkal jobb megoldás... oké, oké, csak épp az rengeteg munka - főleg agymunka - lenne, és nincs is rá most szükség. Persze, vannak olyan esetek, amikor kb. csak ez segít, de a jelenlegi probléma nem ilyennek tűnik.)
Szóval nagy hatalom a rekurzió, de azért itt is figyelni kell.
