Zadání finálové úlohy

Vyhledávání v jízdním řádu

Soutěž dětí a mládeže v programování – finále 19. ročníku

24.–26. června 2005

Vaším úkolem je napsat klient/server aplikaci umožňující vyhledání spojení v jízdním řádu. Aplikace se skládá ze dvou zcela samostatných programů – klienta a serveru – které spolu komunikují pomocí protokolu HTTP. Můžete si vybrat, zda budete psát klienta, server nebo oba dva programy.

Server

Server bude schopen vyhledat spojení v jízdním řádu, který se bude načítat ze souboru, jehož jméno bude zadáno jako parametr při spouštění serveru. Jako parametr při startu půjde zadat i číslo portu, na kterém server očekává požadavky. Nebudou-li parametry zadány, program bude jízdní řády načítat ze souboru data.xml v aktuálním adresáři a poběží na portu 80.

Jízdní řád bude mít podobu dokumentu XML s následující strukturou:

<Linky>
  <Linka cislo="EC134">
    <Stanice odjezd="15:38">Bratislava hl.st.</Stanice>
    <Stanice prijezd="16:14" odjezd="16:16">Kuty</Stanice>
    <Stanice prijezd="16:33" odjezd="16:36">Breclav</Stanice>
    <Stanice prijezd="17:07" odjezd="17:09">Brno hl.n.</Stanice>
    <Stanice prijezd="18:10" odjezd="18:11">Ceska Trebova</Stanice>
    <Stanice prijezd="18:47" odjezd="18:49">Pardubice hl.n.</Stanice>
    <Stanice prijezd="19:12" odjezd="19:13">Kolin</Stanice>
    <Stanice prijezd="19:55">Praha hl.n.</Stanice>
    <Poznamka>pohranicni prechodovy bod [SK/CZ]: Kuty(Gr)</Poznamka>
    <Poznamka>do vsech vozu k sezeni mozno zakoupit mistenku</Poznamka>
    <Poznamka>restauracni vuz (servis: JLV)</Poznamka>
  </Linka>
  <Linka>
    ...
  </Linka>
  ...
</Linky>

V elementu Linky je seznam jednotlivých linek. Informace o každé lince jsou uloženy v elementu Linka. Atribut cislo obsahuje číslo linky, které ji zároveň jednoznačně identifikuje. Každá linka obsahuje alespoň dvě stanice. Pořadí průjezdu stanicemi odpovídá pořadí elementů Stanice uvnitř elementu Linka. Název stanice je uložen jako obsah elementu a neobsahuje české znaky s diakritikou. Čas odjezdu spoje je uložen v atributu odjezd. Tento atribut je uveden u všech stanic, kromě konečné. U všech stanic kromě počáteční může být uveden ještě čas příjezdu spoje (atribut prijezd).

Za seznamem stanic může být u každé linky uveden libovolný počet elementů Poznamka, které obsahují doplňující informace o spoji.

Datový soubor v XML je připraven tak, že na jedné řádce je vždy uveden právě jeden element.

Server bude nabízet dvě služby – vrácení seznamu stanic a vyhledání spojení. Obě služby budou dostupné pomocí podmnožiny protokolu HTTP, která je popsána dále.

Zjištění všech stanic

Při zaslání požadavku GET na adresu /SeznamStanic (např. http://localhost/SeznamStanic) vrátí server jako odpověď seznam stanic v podobě dokumentu XML s následující strukturou:

<SeznamStanic>
  <Stanice>Horni Blatna</Stanice>
  <Stanice>Karlovy Vary</Stanice>
  <Stanice>...</Stanice>
  ...
</SeznamStanic>

Stanice budou vráceny v abecedním pořadí, každá stanice bude vrácena pouze jednou, nesmí se opakovat.

Vyhledání spojení

Druhou službou, kterou server bude nabízet, je vyhledání spojení v jízdním řádu. Tato služba bude vyvolána zasláním požadavku na adresu /NajdiSpojeni. Parametry požadavku přitom budou určovat parametry hledaného spojení. Server bude podporovat následující parametry:

odkud

Název počáteční stanice, kde začíná cesta.

kam

Název cílové stanice, kde cesta končí.

pres

Název stanice, přes kterou musí nalezené spoje vést. Parametr je nepovinný.

odjezd

Čas odjezdu. Nalezená spojení musí začínat v tomto čase nebo později (nezapomeňte, že například jedna hodina ráno je později než jedenáct hodin večer). Parametr má tvar hhmm, a pokud není zadán předpokládá se aktuální čas.

prestupy

Maximální počet přestupů. Nalezená spojení nesmí vyžadovat více než zadaný počet přestupů. Parametr je nepovinný a není-li zadán, hledají se jen přímá spojení. Je-li parametr zadán, má tvar kladného celého čísla.

spojeni

Maximální počet spojení vrácených serverem. Server na základě parametrů nalezne spojení, která mají nejdřívější čas příjezdu do cílové stanice a přitom každé z nich začíná jinou linkou. Nalezená spojení se vrací v pořadí času odjezdu. Je-li takovýchto spojení více, než udává parametr spojeni, je vráceno jen prvních spojeni spojení. Tento parametr je opět kladné celé číslo a není-li zadán, předpokládá se jeho hodnota 5.

Například dotaz na vyhledání dvou spojení s maximálně třemi přestupy z Košic do Vrútek odjíždějících po 12:20 bude mít následující tvar:

http://localhost/NajdiSpojeni?odkud=Kosice&kam=Vrutky&spojeni=2&odjezd=1220&prestupy=3

Jednotlivé parametry přitom mohou být zadány v libovolném pořadí. Při vkládání jednotlivých parametrů do adresy požadavku je potřeba nahradit mezeru znakem +.

Informace o nalezených spojeních vrátí server opět v podobě dokumentu XML.

<Spojeni>
  <Spoj>
    <Linka cislo="R608">
      <Stanice odjezd="12:20">Kosice</Stanice>
      <Stanice prijezd="12:32" odjezd="12:34">Kysak</Stanice>
      <Stanice prijezd="12:48" odjezd="12:50">Margecany</Stanice>
      <Stanice prijezd="13:16" odjezd="13:18">Spisska Nova Ves</Stanice>
      <Stanice prijezd="13:37" odjezd="13:40">Poprad-Tatry</Stanice>
      <Stanice prijezd="13:55" odjezd="13:57">Strba</Stanice>
      <Stanice prijezd="14:24" odjezd="14:26">Liptovsky Mikulas</Stanice>
      <Stanice prijezd="14:44" odjezd="14:46">Ruzomberok</Stanice>
      <Stanice prijezd="15:01" odjezd="15:03">Kralovany</Stanice>
      <Stanice prijezd="15:16" odjezd="15:18">Vrutky</Stanice>
      <Poznamka>do oznacenych vozu mozno zakoupit mistenku</Poznamka>
      <Poznamka>pojizdna uschovna</Poznamka>
    </Linka>
  </Spoj>
  <Spoj>
    <Linka cislo="IC404">
      <Stanice odjezd="12:46">Kosice</Stanice>
      <Stanice prijezd="12:57" odjezd="12:58">Kysak</Stanice>
      <Stanice prijezd="13:50" odjezd="13:52">Poprad-Tatry</Stanice>
      <Stanice prijezd="14:31" odjezd="14:32">Liptovsky Mikulas</Stanice>
      <Stanice prijezd="15:28" odjezd="15:33">Zilina</Stanice>
      <Poznamka>povinne mistenkovy vlak (Kosice-&gt;Bratislava)</Poznamka>
      <Poznamka>pojizdna uschovna</Poznamka>
    </Linka>    
    <Linka cislo="IC141">
      <Stanice prijezd="15:34" odjezd="15:40">Zilina</Stanice>
      <Stanice prijezd="15:56" odjezd="16:06">Vrutky</Stanice>
      <Poznamka>do vsech vozu k sezeni mozno zakoupit mistenku</Poznamka>
      <Poznamka>druh vlaku:expres (Cadca Gr.-&gt;Zvolen os.st.)</Poznamka>
      <Poznamka>restauracni vuz (servis: JLV)</Poznamka>
      <Poznamka>pohranicni prechodovy bod [CZ/SK]: Cadca(Gr)</Poznamka>
    </Linka>
  </Spoj>
</Spojeni>

Každé nalezené spojení je uloženo do elementu Spoj. Uvnitř tohoto elementu se pak nachází seznam linek (element Linka), které spoj využívá (je-li přímý, je linka jen jedna). U linky se přitom nevrací údaje o všech jejích stanicích od počátku do konce, ale jen o těch stanicích, kterými nalezený spoj projíždí.

Není-li možné najít žádné spojení vyhovující zadaným parametrům, vrátí server pouze prázdný element Spojeni.

Chybný požadavek

Obdrží-li server chybný požadavek, odpoví na něj zasláním chybového hlášení v podobě dokumentu XML s jedním elementem Chyba. Například:

<Chyba>Neznamy pozadavek. Nebude zpracovan.</Chyba>

Obsluha požadavků

Server nemusí zvládat obsluhu více požadavků současně. Po ukončení obsluhy jednoho požadavku musí být server schopen zpracovávat další požadavky.

Klient

Klient bude nabízet pohodlné uživatelské rozhraní pro vyhledávání v jízdních řádech. Pro samotné nalezení spojení však bude klient používat služby serveru.

Klient umožní uživateli změnit adresu a port serveru, na které se zasílají požadavky pro vrácení seznamu stanic a pro vyhledání spojení. Výchozí nastavení je přitom takové, že se požadavky zasílají na počítač localhost a port 80.

Klient umožní uživateli jednoduše zadat všechny parametry potřebné pro vyhledání spojení (počáteční a cílovou stanici, čas odjezdu, maximální počet přestupů, počet vrácených spojení a stanici, přes kterou má spojení vést). Po zadání parametrů odešle serveru požadavek na vyhledání spojení a zobrazí je uživateli. U nalezených spojení bude zobrazena jejich trasa, časy průjezdu stanicemi, poznámky a celková doba jízdy.

Komunikační protokol

Klient pro komunikaci se serverem používá podmnožinu protokolu HTTP. Jedná se o aplikační protokol využívající TCP spojení na portu 80, případně na jiném portu zvoleném uživatelem.

Protokol funguje na jednoduchém modelu požadavek–odpověď. Pro každý nový požadavek musí klient navázat nové TCP spojení. Toto spojení je serverem ukončeno okamžitě po vyřízení odpovědi.

Požadavek má tvar:

GET /cesta_z_url?parametry HTTP/verze
libovolný počet řádek, které se ignorují
prázdná řádka

Odpověď serveru má tvar:

HTTP/verze 200 cokoliv
libovolný počet řádek
prázdná řádka
data v XML

Pokud odpověď na první řádce neobsahuje text 200, chápe se to jako chybná odpověď serveru.

Jako verze používejte řetězec 1.0, ale zpracujte i požadavky a odpovědi, které vrátí hodnotu 1.1.

Ukázka komunikace mezi klientem a serverem:

Klient
GET /NajdiSpojeni?odkud=Kosice&kam=Bratislava+hl.st.&spojeni=3 HTTP/1.0
Host: localhost
User-Agent: Vyhledavac Jizdnich Radu (v0.1)
Server
HTTP/1.0 200 OK
Content-type: text/xml
Date: Mon, 30 Mar 1998 12:00:00 GMT

<Spojeni>
  <Spoj>
    <Linka cislo="R610">
      <Stanice odjezd="14:20">Kosice</Stanice>
      <Stanice prijezd="15:37" odjezd="15:40">Poprad Tatry</Stanice>
      <Stanice odjezd="18:05">Povazska Bystrica</Stanice>
  ...

Protokol HTTP je citlivý na velikost písmen, stejně tak URL adresa požadavku. Pro ukončení řádky se používá dvojice znaků CR (kód 13) LF (kód 10).

Pokyny a hodnocení

Na řešení úlohy máte 4 hodiny čistého času. Vaše řešení uložte do adresáře c:\XX, kde XX je vaše startovní číslo. Soubory patřící serveru a klientovi uložte do samostatných adresářů (c:\XX\server a c:\XX\klient).

Při hodnocení úloh budou body rozděleny následujícím způsobem: 30 % bodů je vyhrazeno na hodnocení funkčnosti klienta, 30 % bodů na základní síťovou funkčnost serveru a 40 % bodů na funkci vyhledání spojení. Hodnotí se i dokumentace a přehlednost zdrojového kódu. Hodnocení je navrženo tak, že server, který dokáže nalézt a vrátit alespoň nějaké správné spojení, je hodnocen lépe než sebelepší klient.

Ukázkové řešení a data

V adresáři r:\soutez naleznete ukázkové řešení klienta i serveru a vzorový datový soubor. Zkopírujte si tyto soubory na váš lokální disk.

r:\soutez\klient\jrcl.exe

Ukázkový klient. Při startu je možné zvolit adresu a port, na kterém běží server.

r:\soutez\server\jzserver.exe

Ukázkový server. Při startu je možné zvolit port, na kterém server naslouchá, a datový soubor s jízdními řády.

r:\soutez\server\data.xml

Ukázkový dokument s daty jízdních řádů.