{Програма порівнює методи пошуку: лінійний, бінарний, хешування}
{$F+}
{$M 65520, 0, 655360}

Program SearchTest;

uses WinDos;

const
maxn=4096; {максимальна кількість елементів масиву}
step=500; {крок аналізу середньої кількості операційЇ
TestNum = maxn div step; {кількість тестів}
ProcNum = 3; {кількість методів пошуку}
strlen=10; {довжина рядка}
empty=''; {порожній рядок}

type str=string[strlen];
t = array [1..maxn] of str;
InsertProc = procedure (var a: t; x: str; var n: word); {тип процедури вставки елемента}
SearchProc = function (var a: t; x: str; n:word): word; {тип функції пошуку}

DiffRec = record {тип запису для збереження результатів тесту}
ins,srcrnd,srcex: real
end;
InfoRec = record {тип запису характеристик тестів одного методу пошуку}
SPr: SearchProc;
IPr: InsertProc;
Name: string;
Inf: array [1..TestNum] of DiffRec
end;
var c: t;
ia: array [1..ProcNum] of InfoRec; {масив результатів всіх тестів всіх методів}
inscount, searchcount: longint; {лічильники кількості операцій вставки та пошуку}


procedure Prt (var a: t; i: integer); {службова процедура друку масиву}
var j: word;
begin
{ write('i=',i,' ');
for j:=1 to n do write(' ',a[j]);
writeln }
end;

function h(x: str): word; {функція хешування}
var i, s: word;
begin
s:=0;
for i:=1 to length(x) do
s:=s+i*ord(x[i]);
h:= s mod maxn + 1
end;

function genrnd: str; {функція генерації випадкового рядка з 10 символів}
var x: str;
i: word;
begin
x:='';
for i:=1 to strlen do
x:=x+chr(random(256));
genrnd:=x
end;

function selectrnd(r: word; var a:t): str; {функція вибору випадкового за номером рядка з масиву}
var i,j: word;
begin
i:=0; j:=0; selectrnd:='';
while (j < r) and (i=maxn*2) do begin
if a[i mod maxn+1]>'' then begin
inc(j);
if j = r then selectrnd:=a[i mod maxn+1]
end;
i:=i+1
end
end;

procedure LinIns (var a: t; x: str; var n: word); {вставка елемента для лінійного пошуку}
var i, j: word; b: boolean;
begin
inc(n); a[n]:=x; inc(inscount)
{ Prt(a,i)}
end;

procedure BinIns (var a: t; x: str; var n: word); {вставка елемента для бінарного пошуку}
var i, j, l, r, m: word;
begin
l:=1; inc(n); r:=n; inc(inscount);
while l < r do begin
m:=(l+r) div 2;
if a[m] < =x then l:=m+1
else r:=m;
inc(inscount)
end;
for j:=n downto r+1 do begin
a[j]:=a[j-1];
inc(inscount);
end;
a[r]:=x;
{ Prt(a,i)}
end;

procedure HashIns (var a: t; x: str; var n: word); {вставка елемента для хешування пошуку}
var i, j: word;
begin
i:=h(x); j:=0; inc(inscount); inc(n);
while (a[i] <> empty) and (j < maxn) do begin
inc(j);
i:=i mod maxn + 1;
inc(inscount)
end;
if a[i] = empty then a[i]:=x
else begin
writeln('table is full'); halt
end;
{ Prt(a,i)}
end;

function LinSearch (var a: t; x: str; n:word): word; {лінійний пошук}
var i: word; b: boolean;
begin
i:=0; b:=false; inc(searchcount);
while (in) and not b do begin
inc(i);
b:=a[i]=x;
inc(searchcount)
end;
if b then LinSearch:=i
else LinSearch:=0;
{ Prt(a,i)}
end;

function BinSearch (var a: t; x: str; n:word): word; {бінарний пошук}
var l,r,m: word; b: boolean;
begin
l:=1; r:=n; inc(searchcount);
while l < r do begin
m:=(l+r) div 2;
if a[m] < x then l:=m+1
else r:=m;
inc(searchcount)
end;
if a[l]=x then BinSearch:=l
else BinSearch:=0;
{ Prt(a,i)}
end;

function HashSearch (var a: t; x: str; n:word): word; {пошук хешуванням}
var i, j: word;
begin
i:=h(x); j:=0; inc(searchcount);
while (a[i] <> empty) and (a[i] <> x) and (j < maxn) do begin
inc(j);
i:=i mod maxn + 1;
inc(searchcount)
end;
if a[i]=x then HashSearch:=i
else HashSearch:=0;
{ Prt(a,i)}
end;

procedure TestOne(i: word); {процедура виконання тестів для 1 методу}
var
x: str;
j, k, l,ii: word;
a: t;
begin
for ii:=1 to maxn do a[ii]:=empty;
inscount:=0; searchcount:=0; k:=0; j:=0;
for ii:=1 to maxn do begin
x:=genrnd;
ia[i].IPr(a,x,k);
x:=genrnd;
l:=ia[i].SPr(a,x,k);
if ii mod step = 0 then begin
inc(j);
ia[i].Inf[j].ins:=inscount/step;
ia[i].Inf[j].srcrnd:=searchcount/step;
inscount:=0; searchcount:=0;
end
end;
for ii:=1 to maxn do a[ii]:=empty;
searchcount:=0; k:=0; j:=0;
for ii:=1 to maxn do begin
x:=genrnd;
ia[i].IPr(a,x,k);
x:=selectrnd(random(k)+1,a);
l:=ia[i].SPr(a,x,k);
if ii mod step = 0 then begin
inc(j);
ia[i].Inf[j].srcex:=searchcount/step;
searchcount:=0;
end
end;
end;

var i,k: word;

begin
randomize;

ia[1].IPr:=LinIns;
ia[2].IPr:=BinIns;
ia[3].IPr:=HashIns;
ia[1].SPr:=LinSearch;
ia[2].SPr:=BinSearch;
ia[3].SPr:=HashSearch;
ia[1].Name:='LinSearch';
ia[2].Name:='BinSearch';
ia[3].Name:='HashSearch';

writeln;
write(' ':4);

for k:=1 to ProcNum do begin {виведення результатів}
write(ia[k].Name:24);
TestOne(k)
end;
writeln;
for i:=1 to TestNum do begin
write(step*i:8);
for k:=1 to ProcNum do begin
write(ia[k].Inf[i].ins:8:2);
write(ia[k].Inf[i].srcrnd:8:2);
write(ia[k].Inf[i].srcex:8:2);
end;
writeln
end;
writeln;

end.