program f;
{       Disk defragmentation
        29 Mar 1988     3:00
        30 Mar 1988     3:30
}

const GROUPMAX = 389;
      FILEMAX = 128;

type DiskGroup = 1..GROUPMAX;

var table: array[DiskGroup] of Integer;
var i,nFiles: Integer;
var key: array [0..FILEMAX] of Integer;
    sort: array [1..FILEMAX] of Integer;
    totalSwaps,totalGroups: Integer;

procedure init;
var s: DiskGroup;
var i: Integer;
begin
for s:=1 to GROUPMAX do
    table[s]:=0;
key[0]:=FILEMAX+1;
for i:=1 to FILEMAX do
    begin key[i]:=0; sort[i]:=0; end;
end;

procedure load(n:Integer);
var i,fileNr,length: Integer;
    s,t,sec: DiskGroup;
begin
fileNr:=0;
sec:=1;
while sec<GROUPMAX do
    begin
    i:=Random(n+1);
    if key[i]=0 then
        begin
        fileNr:=fileNr+1;
        key[i]:=fileNr;
        sort[fileNr]:=i;
        end;
    length := Random(GROUPMAX div 100); {estimate for maximum file length}
    t:=sec+length;
    if t>GROUPMAX then t:=GROUPMAX;
    for s:=sec to t do
        table[s]:=i;
    sec:=t;
    end;
end;

procedure show(swaps:Integer);
var s: DiskGroup;
    i: Integer;
begin
{for s:=1 to GROUPMAX do
    write(table[s]);}
write(' ',swaps);
end;

procedure defrag;
type DiskSegment = record
                   first,last: DiskGroup;
                   end;
var segment1, segment2: DiskSegment;
var swaps: Integer;
label break;

procedure getSegment(var segment: DiskSegment);
begin
segment.last:=segment.first;
while (segment.last<GROUPMAX) and (table[segment.last+1]=table[segment.first]) do
      segment.last:=segment.last + 1;
end;

procedure invert(seg: DiskSegment);
var s: DiskGroup;
    i,len: Integer;
    temp: Integer;
begin
len := (seg.last-seg.first+1) div 2 - 1;
for i:=0 to len do
    begin
    temp:=table[seg.first+i];
    table[seg.first+i]:=table[seg.last-i];
    table[seg.last-i]:=temp;
    totalGroups:=totalGroups+1;
    end;
end;

procedure swapSegments(var seg1,seg2: DiskSegment);
var seg: DiskSegment;
    len1,len2: Integer;
begin
seg.first:=seg1.first; seg.last:=seg2.last;
len1:=seg1.last-seg1.first;
len2:=seg2.last-seg2.first;
invert(seg1);
invert(seg2);
invert(seg);
seg1.last:=seg1.first+len2;
seg2.first:=seg2.last-len1;
end;

begin {defrag}
totalSwaps:=0; totalGroups:=0;
repeat
    swaps:=0;
    segment1.first:=1;
    repeat
        getSegment(segment1);
        if segment1.last>=GROUPMAX then goto break;
        segment2.first:=segment1.last+1;
        getSegment(segment2);
        if key[table[segment1.first]]>key[table[segment2.first]] then
            begin
            swapSegments(segment1,segment2);
            swaps:=swaps+1;
            end;
        segment1:=segment2;
    until segment1.last>=GROUPMAX;
break:
    show(swaps);
    totalSwaps:=totalSwaps+swaps;
until swaps=0;
end;

begin {Main program}
write('How many files: '); Readln(nFiles);
init;
load(nFiles);
write('Keys: ');
for i:=1 to nFiles do
    write(key[i]:3);
writeln;
write('Sort: ');
for i:=1 to nFiles do
    write(sort[i]:3);
writeln;
show(0);
defrag;
writeln;
writeln(totalSwaps,' swaps involving ',totalGroups,' groups');
end.

