2. Domácí úkol - hashovací tabulka

Čtěte prosím tuto stránku celou a pozorně.

Zadání

Naprogramujte pomocí hashování "pole" řetězců, u kterého jsou jednotlivé prvky pole identifikovány řetězci. Vhodnou hashovací funkci zvolte podle vlastního uvážení.

Pole je možné používat tímto způsobem:

Uses hash.pas;
Var A : TStringArray;
Begin
  A := TStringArray.Create(15);
  A.Data['ahoj'] := 'nazdar';
  A.Data['ahoj'] := 'cau';
  Writeln(A.Data['ahoj']); { vypíše cau }
  A.Destroy;
End.


Váš úkol bude implementovat objekt TStringArray, který je definovaný v souboru hash.pas následujícím způsobem:

TStringArray = Class

  Private

    Function GetData(Const key : String) : String;
    Procedure SetData(Const key : String; s : String);

  Public

    Constructor Create(table_size : Integer);
    Destructor Destroy; Override;

    Function IsKey(key : String) : Boolean;
    Procedure RemoveKey(key : String);

    Property Data[Const key : String] : String Read GetData Write SetData;
End;


Soubor hash.pas včetně testovacího prostředí je v archivu zadani.tar.

Metody třídy TStringArray

Konstruktor objektu třídy TStringArray má jediný parametr - velikost hashovací tabulky. Je garantováno, že počet prvků uložených v poli v žádném testu nepřekročí hodnotu tohoto parametru.

Destruktor objektu by měl uvolnit večkerou paměť, kterou si objekt alokoval během svého života.

Metoda IsKey má vracet True v případě, že daný pro klíč existuje v poli nějaká hodnota, tj. v minulosti byl proveden příkaz A.Data[<klíč>] := 'cosi'. V opačném případě má metoda vracet False.

Metoda RemoveKey odstraní daný klíč i jeho hodnotu z pole.

Vlastnost Data představuje jen jiný způsob volání metod GetData a SetData. Příkaz A.Data[X] := Y způsobí volání metody A.SetData(X, Y), příkaz Z := A.Data[W] je ekvivalentní příkazu Z := A.GetData(W). Metody GetData a SetData však není možné používat přímo, protože jsou deklarovány v sekci Private. Jediný způsob, jak je zavolat z vnějšku objektu, je pomocí vlastnosti Data.

Pro implementaci je nutné připsat do deklarace třídy TStringArray datové položky ve kterých bude uložena hashovací tabulka a může být vhodné přidat některé vlastní (privátní) metody.

Ošetření chyb

V případě, že uživatel objektu (tj. programátor, který váš objekt používá - typicky cvičící) zavolá metodu GetData, nebo RemoveKey na klíč, který v poli neexistuje, musí váš kód vygenerovat výjimku. Tuto výjimku lze vyvolat příkazem Raise EInvalidKey.Create(key). Tento příkaz vyskočí z aktuální procedury a ze všech předchozích procedur, které ještě nebyly dokončeny. Program bude pokračovat v nejbližším bloku Try Except End.

Následující příklad demonstruje chování programu v případě vyvolání výjimky:

Procedure A;
Begin
  Raise EInvalidKey.Create('ahoj');
  Writeln('A');
End;

Procedure B;
Begin
  A;
  Writeln('B');
End;

Begin
  Try
    B;
    Writeln('OK');
  Except
    Writeln('Vyjimka')
  End;
  Writeln('Hotovo');
End.


Předchozí program vypíše pouze dvě slova: Vyjimka a Hotovo. Volání Raise způsobí skok na první příkaz za klíčovým slovem Except.

Výjimky se v programech obvykle používají pro ošetření chyb. V případě, že spustíte program z integrovaného prostředí Delphi a nastane volání Raise, zastaví debugger program na místě volání Raise. Program můžete opět spustit klávesou F9. Program v Delphi může navíc volitelně podat uživateli hlášení o výjimce pomocí dialogového okna (kód pro zobrazení okna je automaticky generován překladačem). Toto chování lze vypnout v nastavení překladače. Dialogové okno se objevuje i v případě, že program nebyl spuštěn z integrovaného prostředí. V projektu, který je umístěn v archivu zadani.tar je již toto chování vypnuto.

Formát testovacích dat

Testovací data jsou umístěna v souboru vstup.txt. Každému řádku odpovídá jedno volání metody objektu třídy TStringArray. Každý řádek začíná slovem, které identifikuje metodu. Za prvním slovem obvykle následují parametry metody a očekávaný (správný) výsledek volání.

Zde jsou možné případy, které se mohou ve vstupním souboru vyskytnout:

• Create 5 - vytvoř pole s velikostí 5
• Get 'limonada' exception - zeptej se na klíč 'limonada', očekávej výjimku
• Set 'rum' 'alkohol' - nastav klíč 'rum' na hodnotu 'alkohol'
• Get 'rum' 'alkohol' - zjisti hodnotu klíče 'rum', očekávej hodnotu 'alkohol'
• IsKey 'limonada' False - zeptej se, zda existuje klíč 'limonada', očekávej hodnotu False
• IsKey 'rum' True - zeptej se, zda existuje klíč 'rum', očekávej hodnotu True
• RemoveKey 'limonada' exception - odstraň klíč 'limonada', očekávej výjimku
• RemoveKey 'rum' ok - odstraň klíč 'limonada', neočekávej výjimku
• Destroy - zruš objekt

Uživatelské rozhraní

Verze Delphi

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program by kromě vstupního textového souboru nesmí požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - hash a s přiloženým souborem hash.pas.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 3.5.2007.
Termín odevzdání: 20.5.2007.
Termín oprav: 27.5.2007.