95 lines
2.2 KiB
Plaintext
95 lines
2.2 KiB
Plaintext
|
unit MTFBaseUnit;
|
||
|
{-------------------------------------------------------------------------------
|
||
|
Move To Front Base Class
|
||
|
------------------------
|
||
|
reSource v2.6
|
||
|
Copyright (C) 1998-2001 Victor Kasenda / gruv
|
||
|
http://go.to/gruv
|
||
|
email: vickas@singnet.com.sg
|
||
|
|
||
|
The MTF is derived from Peter Fenwick's implementation.
|
||
|
|
||
|
Desc:
|
||
|
We work with two arrays --
|
||
|
image contains an image of the MTF list, most recent in posn 0
|
||
|
map contains the position of the chars in image.
|
||
|
|
||
|
MTFDest has been removed.
|
||
|
|
||
|
This is done so that searching for the character is faster.
|
||
|
e.g. search for 'c', look up index 2 in map to get its position.
|
||
|
Then move it to the front by shifting all chars before it in the image
|
||
|
one step up. Update the map accordingly.
|
||
|
-------------------------------------------------------------------------------}
|
||
|
|
||
|
(**) interface (**)
|
||
|
uses StructsUnit;
|
||
|
|
||
|
const
|
||
|
NumSym = 256;
|
||
|
|
||
|
type
|
||
|
TMTFBase = class
|
||
|
protected
|
||
|
map: array[0..NumSym-1] of byte; // index of a character
|
||
|
image: array[0..NumSym-1] of byte; // chars in MTF order
|
||
|
procedure MoveToFront(const s:byte);
|
||
|
|
||
|
public
|
||
|
constructor Create;
|
||
|
procedure Init;
|
||
|
end;
|
||
|
|
||
|
(**) implementation (**)
|
||
|
|
||
|
(*******************************************************************************
|
||
|
TMTFBase
|
||
|
*******************************************************************************)
|
||
|
|
||
|
constructor TMTFBase.Create;
|
||
|
begin
|
||
|
inherited Create;
|
||
|
end;
|
||
|
|
||
|
procedure TMTFBase.Init;
|
||
|
var
|
||
|
i: byte;
|
||
|
begin
|
||
|
for i := 0 to NumSym-1 do
|
||
|
begin
|
||
|
image[i] := i;
|
||
|
map[i] := i;
|
||
|
end;
|
||
|
end;
|
||
|
|
||
|
{-------------------------------------------------------------------------------
|
||
|
MoveToFront
|
||
|
-----------
|
||
|
Move symbol s to the front
|
||
|
-------------------------------------------------------------------------------}
|
||
|
|
||
|
procedure TMTFBase.MoveToFront(const s:byte);
|
||
|
var
|
||
|
i: byte;
|
||
|
begin
|
||
|
if (map[s] <> 0) then
|
||
|
begin
|
||
|
|
||
|
{Move everything before s in image up one step.
|
||
|
update the maps accordingly}
|
||
|
for i := map[s] downto 1 do
|
||
|
begin
|
||
|
image[i] := image[i-1];
|
||
|
map[image[i]] := i;
|
||
|
end;
|
||
|
|
||
|
{s is moved to the front}
|
||
|
image[0] := s;
|
||
|
map[s] := 0;
|
||
|
end;
|
||
|
end;
|
||
|
|
||
|
|
||
|
|
||
|
end.
|