UNIT uWortListe;
(* ******************************************************************** *)
(*                                                                      *)
(* K L A S S E   : TWortListe                                           *)
(* -------------------------------------------------------------------- *)
(* Version       : 1.3                                                  *)
(* Autor         : S. Spolwig, OSZ-Handel I, 10997 Berlin               *)
(*                                                                      *)
(* Aufgabe       : Statische Liste zur Verwaltung beliebiger Strings    *)
(* ******************************************************************** *)

INTERFACE
const
   MAXLAENGE = 10000;

type
  TElement = string;
  
  TWortListe  = class (TStrListe)

   {
   private
    Kollektion  : array [0..MAXLAENGE + 1] of TElement;
    ListenLaenge,     // Anzahl der belegten Elemente
    AktuellePos : Word;
    ...
    }
  end;

(*  ----------------- B e s c h r e i b u n g -------------------------

Oberklasse     : TStrListe
Bezugsklassen  : -

Methoden
--------

SearchPos (key: string) : integer
  Anfrage: ob key in der Liste enthalten ist
  vorher : -
  nachher: liefert die Position in der Liste; wenn nicht vorhanden, 0


SearchPosBin (key: string) : integer
  Anfrage: ob key in der Liste enthalten ist
  vorher : -
  nachher: liefert die Position in der Liste; wenn nicht vorhanden, 0


RekursivDurchsuchen (key : string; unten,oben : integer; var Pos: integer )
----------------------------------------------------------------------- *)


IMPLEMENTATION
(* ==================================================================== *)

function  TWortListe.SearchPos (key : string) : integer;
(* -------------------------------------------------------------------- *)
begin
  Result := 0;   // nicht gefunden!
  First;
  while (Result = 0) AND (NOT EoList) do
  begin
     if Kollektion[AktuellePos] = key
     then Result := AktuellePos
     else inc(AktuellePos);   //Next;
  end;
end;


function  TWortListe.SearchPos (key : string) : integer;
(* -------------------------------------------------------------------- *)
(* Auftrag: lineares Suchen nach Wirth                                  *)
(* -------------------------------------------------------------------- *)
begin
  Result := 0;  // nicht drin
  AktuellePos := Listenlaenge + 1;
  SetElement(key);

  First;
  while Kollektion[AktuellePos] <> key do
  begin
    inc(AktuellePos); // next;
  end;

  if AktuellePos <= ListenLaenge
  then Result := AktuellePos;
end;


function  TWortListe.SearchPosBin (key : string) : integer;
(* -------------------------------------------------------------------- *)
var
  unten,
  oben,
  mitte   : integer;

begin
  Result := 0;   // nicht gefunden
  unten  := 1;
  oben   := ListenLaenge;

  while (oben >= unten) and (Result = 0) do
  begin
     mitte := (unten + oben) div 2;
     if (Kollektion[mitte] = key)      (* Treffer *)
     then Result := mitte
     else
       begin
         if (key < Kollektion[mitte])
         then oben  := mitte - 1
         else unten := mitte + 1;
       end;
  end; (* while *)
end;


procedure TWortListe.RekursivDurchsuchen (key : string; unten,oben : integer;
                                      var Pos: integer );
(* -------------------------------------------------------------------- *)
var mitte : integer;

begin
   if unten > oben
   then Pos := 0    (* abbruch - nicht gefunden *)
   else
     begin
       mitte := (unten + oben) div 2;

       if Kollektion[mitte] = key
       then Pos := mitte  (* Treffer ! *)
       else
         if (key < Kollektion[mitte])
         then RekursivDurchsuchen(key, unten, mitte -1, Pos)
         else RekursivDurchsuchen(key, mitte + 1, oben, Pos)
     end;  (* else AktuellePos *)
end;

END.