Move-to-front algorithm: Difference between revisions

=={{header|FreeBASIC}}==

<lang freebasic>#define FAIL -1

sub mtf( s() as string, i as uinteger )

'moves the symbol at index i to the front and shifts preceding ones back

dim as string*1 t = s(i)

for j as uinteger = i to 1 step -1

s(j) = s(j-1)

next j

s(0)=t

end sub

sub make_symbols( s() as string )

'populates an array of strings with the lowercase alphabet

for i as uinteger = 97 to 122

s(i-97) = chr(i)

next i

end sub

function find( s() as string, l as string ) as integer

'returns the index of the first occurrence of the symbol l in s()

for i as uinteger = 0 to ubound(s)

if s(i) = l then return i

next i

return FAIL

end function

sub encode( s() as string, ind() as uinteger )

dim as integer n = ubound(s), i

redim as uinteger ind(0 to n)

dim as string a(0 to 25)

make_symbols(a())

for z as uinteger = 0 to n

i = find( a(), s(z) )

if i = FAIL then

print "Uh oh! Couldn't find ";s(z);" in alphabet."

end

end if

mtf( a(), i )

ind(z) = i

next z

end sub

sub decode( s() as string, ind() as uinteger )

dim as integer n = ubound(ind), i

redim as string s(0 to n)

dim as string a(0 to 25)

make_symbols(a())

for z as uinteger = 0 to n

s(z) = a(ind(z))

mtf(a(), ind(z))

next z

end sub

sub printarr( s() as string )

for i as uinteger = 0 to ubound(s)

print s(i);

next i

print

end sub

sub printind( ind() as integer )

for i as uinteger = 0 to ubound(ind)

print ind(i);" ";

next i

print

end sub

sub compose( s() as string, b as string )

'turns a string into a zero-indexed array of single letters

'The reason we use such arrays is to get them zero-indexed

'and to make the point that we could work with multi-char

'symbol tables if we wanted to

dim as integer n = len(b), i

redim as string s(0 to n-1)

for i = 0 to n-1

s(i) = mid(b, 1+i, 1)

next i

end sub

'-----------now the tests-------------

redim as string s(0)

redim as integer ind(0)

compose( s(), "broood" )

encode( s(), ind() )

printind( ind() )

decode( s(), ind() )

printarr( s() ) : print

compose( s(), "bananaaa" )

encode( s(), ind() )

printind( ind() )

decode( s(), ind() )

printarr( s() ) : print

compose( s(), "hiphophiphop" )

encode( s(), ind() )

printind( ind() )

decode( s(), ind() )

printarr( s() )</lang>

{{out}}<pre>

1 17 15 0 0 5

broood

1 1 13 1 1 1 0 0

bananaaa

7 8 15 2 15 2 2 3 2 2 3 2

hiphophiphop

</pre>