Úkolem je realizovat třídu CBusLine, která bude implementovat seznam zastávek jedné autobusové linky.

Předpokládáme, že autobusy v modelovaném městě jezdí zásadně dvousměrně. Vyjíždějí z jedné konečné, projíždějí definovaným seznamem zastávek a končí ve druhé konečné. Tam jízdu přeruší a po nezbytné přestávce autobus jede po stejné trase zpět na první konečnou (pochopitelně projíždí zastávky v opačném pořadí). Seznam zastávek se tedy vyplatí reprezentovat jako dvousměrně zřetězený spojový seznam, ve třídě CBusLine máme odkaz na obě konečné.

Vaším úkolem je realizovat třídu CBusLine a další podpůrné třídy. Jejich rozhraní je následující: CBusLine

konstruktor bez parametrů

  vytvoří prázdnou instanci třídy, tedy nastaví obě členské proměnné na NULL,

destruktor

  uvolní prostředky alokované instancí,

kopírující konstruktor

  vytvoří hlubokou kopii instance,

Add

  metoda přidá další zastávky do existujícího seznamu (prodloužení trasy). Vkládané zastávky jsou přidávané na konec seznamu, tedy za původní m_Terminal2). Po přidání zastávek musí opět vzniknout platný dvousměrně zřetězený spojový seznam. Parametrem volání je vstupní stream, v tomto vstupním streamu jsou uvedená jména zastávek, vždy jedna zastávka na jedné řádce. Ve vstupním streamu mohou vyskytovat prázdné řádky (budou ignorovány) a duplicity (v seznamu zastávek se to samé jméno může objevit vícekrát, v počtu podle vstupu).

Trip

  metoda nalezne cestu mezi dvojicí zastávek. Parametrem volání jsou dva řetězce - nástupní a výstupní zastávka. Použití metody je zřejmé z ukázek níže:

      výpis nalezené cesty zobrazí se seznam zastávek počínaje nástupní a konče výstupní. Ve výpisu je každá zastávka na jedné řádce, za každou (i za poslední) řádkou výstupu je odřádkování (viz ukázka níže).
      Metoda Stops spočte počet zastávek v nalezené cestě, návratová hodnota zahrnuje počáteční a koncovou zastávku.

  Pokud se zadané zastávky v seznamu nevyskytují, bude vyhozena výjimka CNameException. Můžete předpokládat, že zadaná nástupní/výstupní zastávka je v seznamu uvedena nejvýše jednou, tedy cesta je unikátní,

m_Terminal1

  členská proměnná ukazuje vždy na první konečnou (nastavena na NULL pro prázdný seznam),

m_Terminal2

  členská proměnná ukazuje vždy na druhou konečnou (nastavena na NULL pro prázdný seznam),

CTester

  tato třída je implementována v testovacím prostředí. Je používaná pro kontrolu struktury Vašeho spojového seznamu. Ponechte deklaraci friend, pokud ji odstraníte, odevzdaný program nepůjde zkompilovat.

TStop

Tato struktura je používaná pro reprezentaci seznamu zastávek. Má následující rozhraní:

m_Next

  obsahuje ukazatel na další prvek ve spojovém seznamu, poslední prvek obsahuje hodnotu NULL. Pokud začneme procházet spojový seznam z m_Terminal1, pak při použití odkazů m_Next projdeme celou trasu,

m_Prev

  obsahuje ukazatel na předchozí prvek ve spojovém seznamu, první prvek obsahuje hodnotu NULL. Pokud začneme procházet spojový seznam z m_Terminal2, pak při použití odkazů m_Prev projdeme celou trasu,

m_Name

  obsahuje jméno zastávky (řetězec).

CNameException

Třída reprezentuje výjimku, která bude vygenerovaná pokud není nalezena požadovaná zastávka. Rozhraní musí umožňovat zobrazení ve výstupním streamu pomocí operátoru «, ve výpisu je na konci odřádkování.

Odevzdávejte soubor, který obsahuje pouze implementovanou třídu CBusLine a další podpůrné třídy. Třída musí splňovat veřejné rozhraní podle ukázky - pokud Vámi odevzdané řešení nebude obsahovat popsané rozhraní, dojde k chybě při kompilaci. Do třídy si ale můžete doplnit další metody (veřejné nebo i privátní) a členské proměnné. Odevzdávaný soubor musí obsahovat jak deklaraci třídy (popis rozhraní) tak i definice metod, konstruktoru a destruktoru. Je jedno, zda jsou metody implementované inline nebo odděleně. Pro usnadnění odevzdávání můžete využít toho, že ProgTest definuje proměnnou preprocesoru PROGTEST. Použijte přiložený archiv jako základ Vašeho řešení.

Implementovaná třída nesmí používat datové struktury z STL (vector, list, …, není pro to ani důvod). Jejich použití povede k chybě při kompilaci. Třída je testovaná v omezeném prostředí, konkrétní omezení je zřejmé z hodnocení referenčního řešení.

V realizované třídě se nemusíte zabývat implementací operátoru =. Progtest v této úloze netestuje tuto funkcionalitu. Pozor - testovací prostředí kontroluje strukturu Vašeho spojového seznamu, dejte zejména pozor na odkaz m_Terminal2. Požadované veřejné rozhraní třídy:

#ifndef __PROGTEST__
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <string>
using namespace std;
#endif /* __PROGTEST__ */

class CNameException
 {
   public:
    // op <<
 };

struct TStop
 {
                   TStop  ( const string & name )
                    : m_Next ( NULL ), m_Prev ( NULL ), m_Name ( name ) { }
   TStop         * m_Next;
   TStop         * m_Prev;
   string          m_Name;
 };

class CBusLine
 {
   public:
    // default constructor
    // copy constructor
    // destructor
    // Add   ( istream & is )
    // Trip  ( const string & from, const string & to ) const
   private:
    // todo
    TStop        * m_Terminal1, * m_Terminal2;
    friend class CTester;
 };

Ukázka použití třídy:

istringstream is;
int           l;
CBusLine a;
is . clear ();
is . str ( "Newton\nBlack Hill\nWood Side\nGreen Hill\nLakeside\n" );
a . Add ( is );
l = a . Trip ( "Black Hill", "Green Hill" ) . Stops (); // l = 3
cout << a . Trip ( "Black Hill", "Green Hill" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Black Hill
 -> Wood Side
 -> Green Hill
--8<----8<----8<----8<----8<----8<----8<--
*/

l = a . Trip ( "Wood Side", "Newton" ) . Stops (); // l = 3
cout << a . Trip ( "Wood Side", "Newton" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Wood Side
 -> Black Hill
 -> Newton
--8<----8<----8<----8<----8<----8<----8<--
*/

l = a . Trip ( "Black Hill", "Black Hill" ) . Stops (); // l = 1
cout << a . Trip ( "Black Hill", "Black Hill" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Black Hill
--8<----8<----8<----8<----8<----8<----8<--
*/

is . clear ();
is . str ( "Great Newton\nLittle Burnside\n" );
a . Add ( is );
l = a . Trip ( "Great Newton", "Newton" ) . Stops (); // l = 6
cout << a . Trip ( "Great Newton", "Newton" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Great Newton
 -> Lakeside
 -> Green Hill
 -> Wood Side
 -> Black Hill
 -> Newton
--8<----8<----8<----8<----8<----8<----8<--
*/

try { cout << a . Trip ( "Blue Hill", "Newton" ); }
catch ( const CNameException & e ) { cout << e; }
/*
--8<----8<----8<----8<----8<----8<----8<--
Unknown stop 'Blue Hill'
--8<----8<----8<----8<----8<----8<----8<--
*/

CBusLine b;
is . clear ();
is . str ( "Newton Valley\nNewton Heights\n\n\nNewton Crossroad\nBlack Hill\n" );
b . Add ( is );
l = b . Trip ( "Newton Heights", "Black Hill" ) . Stops (); // l = 3
cout << b . Trip ( "Newton Heights", "Black Hill" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Newton Heights
 -> Newton Crossroad
 -> Black Hill
--8<----8<----8<----8<----8<----8<----8<--
*/

is . clear ();
is . str ( "Little Beacon Hill\nBeacon Hill\nBeacon Hill\nGreen Hill" );
b . Add ( is );
l = b . Trip ( "Newton Crossroad", "Green Hill" ) . Stops (); // l = 6
cout << b . Trip ( "Newton Crossroad", "Green Hill" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Newton Crossroad
 -> Black Hill
 -> Little Beacon Hill
 -> Beacon Hill
 -> Beacon Hill
 -> Green Hill
--8<----8<----8<----8<----8<----8<----8<--
*/

l = b . Trip ( "Green Hill", "Newton Heights" ) . Stops (); // l = 7
cout << b . Trip ( "Green Hill", "Newton Heights" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Green Hill
 -> Beacon Hill
 -> Beacon Hill
 -> Little Beacon Hill
 -> Black Hill
 -> Newton Crossroad
 -> Newton Heights
--8<----8<----8<----8<----8<----8<----8<--
*/

CBusLine c;
is . clear ();
is . str ( "Newton Valley\nNewton Heights\n\n\nNewton Crossroad\nBlack Hill\n" );
c . Add ( is );
CBusLine d = c;
is . clear ();
is . str ( "Wildcat Valley\nBurnside East\nBurnside Woods\nWood Side East\nWood Side Central" );
c . Add ( is );
is . clear ();
is . str ( "Castle Hill\nLittle Bradford\nWood Side Mountains\nWood Side Central" );
d . Add ( is );
l = c . Trip ( "Black Hill", "Wood Side Central" ) . Stops (); // l = 6
cout << c . Trip ( "Black Hill", "Wood Side Central" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Black Hill
 -> Wildcat Valley
 -> Burnside East
 -> Burnside Woods
 -> Wood Side East
 -> Wood Side Central
--8<----8<----8<----8<----8<----8<----8<--
*/

l = d . Trip ( "Black Hill", "Wood Side Central" ) . Stops (); // l = 5
cout << d . Trip ( "Black Hill", "Wood Side Central" );
/*
--8<----8<----8<----8<----8<----8<----8<--
Black Hill
 -> Castle Hill
 -> Little Bradford
 -> Wood Side Mountains
 -> Wood Side Central
--8<----8<----8<----8<----8<----8<----8<--
*/