Move-to-front algorithm: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(39 intermediate revisions by 21 users not shown) | |||
Line 2:
Given a symbol table of a ''zero-indexed'' array of all possible input symbols
[[wp:Move-to-front transform|this algorithm]] reversibly transforms a sequence
of input symbols into an array of output numbers (indices).
The transform in many cases acts to give frequently repeated input symbols
lower indices which is [[wp:Move-to-front_transform#Use_in_practical_data_compression_algorithms| useful in some compression algorithms]].
;Encoding algorithm:
Line 12 ⟶ 14:
move that symbol to the front of the symbol table
</pre>
;Decoding algorithm:
Line 20 ⟶ 23:
move that symbol to the front of the symbol table
</pre>
;Example:
Encoding the string of character symbols 'broood' using a symbol table of the lowercase characters '''a'''-to-'''z'''
:::::{| class="wikitable" border="1"
|-
! Input
Line 55 ⟶ 58:
| 'orbacdefghijklmnpqstuvwxyz'
|}
Decoding the indices back to the original symbol order:
:::::{| class="wikitable" border="1"
|-
! Input
Line 87 ⟶ 91:
| 'orbacdefghijklmnpqstuvwxyz'
|}
;Task:
:* Encode and decode the following three strings of characters using the symbol table of the lowercase characters '''a'''-to-'''z''' as above.
:* Show the strings and their encoding here.
:* Add a check to ensure that the decoded string is the same as the original.
<br>
Line 100 ⟶ 105:
<big> hiphophiphop </big>
<small>(Note the misspellings in the above strings.)</small>
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V symboltable = Array(‘a’..‘z’)
F move2front_encode(strng)
[Int] sequence
V pad = copy(:symboltable)
L(char) strng
V indx = pad.index(char)
sequence.append(indx)
pad = [pad.pop(indx)] [+] pad
R sequence
F move2front_decode(sequence)
[Char] chars
V pad = copy(:symboltable)
L(indx) sequence
V char = pad[indx]
chars.append(char)
pad = [pad.pop(indx)] [+] pad
R chars.join(‘’)
L(s) [‘broood’, ‘bananaaa’, ‘hiphophiphop’]
V encode = move2front_encode(s)
print(‘#14 encodes to #.’.format(s, encode), end' ‘, ’)
V decode = move2front_decode(encode)
print(‘which decodes back to #.’.format(decode))
assert(s == decode, ‘Whoops!’)</syntaxhighlight>
{{out}}
<pre>
broood encodes to [1, 17, 15, 0, 0, 5], which decodes back to broood
bananaaa encodes to [1, 1, 13, 1, 1, 1, 0, 0], which decodes back to bananaaa
hiphophiphop encodes to [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2], which decodes back to hiphophiphop
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">DEFINE SYMBOL_TABLE_SIZE="26"
PROC InitSymbolTable(BYTE ARRAY table BYTE len)
BYTE i
FOR i=0 TO len-1
DO
table(i)=i+'a
OD
RETURN
BYTE FUNC Find(BYTE ARRAY table BYTE len,c)
BYTE i
FOR i=0 TO len-1
DO
IF table(i)=c THEN
RETURN (i)
FI
OD
Break()
RETURN (0)
PROC MoveToFront(BYTE ARRAY table BYTE len,pos)
BYTE sym
sym=table(pos)
WHILE pos>0
DO
table(pos)=table(pos-1)
pos==-1
OD
table(pos)=sym
RETURN
PROC Encode(CHAR ARRAY in BYTE ARRAY out BYTE POINTER outLen)
BYTE ARRAY table(SYMBOL_TABLE_SIZE)
BYTE i,pos
outLen^=0
InitSymbolTable(table,SYMBOL_TABLE_SIZE)
FOR i=1 TO in(0)
DO
pos=Find(table,SYMBOL_TABLE_SIZE,in(i))
out(outLen^)=pos
outLen^==+1
MoveToFront(table,SYMBOL_TABLE_SIZE,pos)
OD
RETURN
PROC Decode(BYTE ARRAY in BYTE inLen CHAR ARRAY out)
BYTE ARRAY table(SYMBOL_TABLE_SIZE)
BYTE i,pos,len
len=0
InitSymbolTable(table,SYMBOL_TABLE_SIZE)
FOR i=0 TO inLen-1
DO
pos=in(i)
len==+1
out(len)=table(pos)
MoveToFront(table,SYMBOL_TABLE_SIZE,pos)
OD
out(0)=len
RETURN
PROC Test(CHAR ARRAY s)
BYTE ARRAY encoded(255)
CHAR ARRAY decoded(256)
BYTE encodedLength,i
Print("Source: ")
PrintE(s)
Encode(s,encoded,@encodedLength)
Print("Encoded: ")
FOR i=0 TO encodedLength-1
DO
PrintB(encoded(i)) Put(32)
OD
PutE()
Decode(encoded,encodedLength,decoded)
Print("Decoded: ")
PrintE(decoded)
IF SCompare(s,decoded)=0 THEN
PrintE("Decoded is equal to the source.")
ELSE
PrintE("Decoded is different from the source!")
FI
PutE()
RETURN
PROC Main()
Test("broood")
Test("bananaaa")
Test("hiphophiphop")
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Move-to-front_algorithm.png Screenshot from Atari 8-bit computer]
<pre>
Source: broood
Encoded: 1 17 15 0 0 5
Decoded: broood
Decoded is equal to the source.
Source: bananaaa
Encoded: 1 1 13 1 1 1 0 0
Decoded: bananaaa
Decoded is equal to the source.
Source: hiphophiphop
Encoded: 7 8 15 2 15 2 2 3 2 2 3 2
Decoded: hiphophiphop
Decoded is equal to the source.
</pre>
=={{header|Ada}}==
<
procedure Move_To_Front is
Line 186 ⟶ 347:
Encode_Write_Check("bananaaa");
Encode_Write_Check("hiphophiphop");
end Move_To_Front;</
{{out}}
Line 193 ⟶ 354:
'bananaaa' encodes to 1 1 13 1 1 1 0 0. This decodes to 'bananaaa'. Correct!
'hiphophiphop' encodes to 7 8 15 2 15 2 2 3 2 2 3 2. This decodes to 'hiphophiphop'. Correct!</pre>
=={{header|Aime}}==
<syntaxhighlight lang="aime">decode(list l)
{
integer c, e;
data al, s;
al = "abcdefghijklmnopqrstuvwxyz";
for (, e in l) {
s.append(c = al[e]);
al.delete(e).insert(0, c);
}
s;
}
encode(data s)
{
integer c, e;
data al;
list l;
al = "abcdefghijklmnopqrstuvwxyz";
for (, c in s) {
l.append(e = al.place(c));
al.delete(e).insert(0, c);
}
l;
}
main(void)
{
for (, text s in list("broood", "bananaaa", "hiphophiphop")) {
list l;
l = encode(s);
l.ucall(o_, 1, " ");
o_(": ", decode(l), "\n");
}
0;
}</syntaxhighlight>
{{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>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# note text pos is based from 0 #
PROC move to front = ( STRING text, INT text pos )STRING:
Line 332 ⟶ 540:
# ; test encode and decode( "zyxwvutsrqponmlkjihgfedcba" ) #
)</
{{out}}
<pre>
Line 339 ⟶ 547:
hiphophiphop encodes to [ 7 8 15 2 15 2 2 3 2 2 3 2 ] which correctly decodes to "hiphophiphop"
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">
symbolTable: @`a`..`z`
encodeWord: function [s][
symt: new symbolTable
result: []
loop s 'c [
idx: index symt c
'result ++ idx
symt: (rotate symt\[0..idx] 1) ++ symt\[(idx+1)..dec size symt]
]
return result
]
decodeWord: function [s][
symt: new symbolTable
result: []
loop s 'idx [
'result ++ symt\[idx]
symt: (rotate symt\[0..idx] 1) ++ symt\[(idx+1)..dec size symt]
]
return join result
]
loop ["broood", "babanaaa", "hiphophiphop"] 'word [
encoded: encodeWord word
decoded: decodeWord encoded
print ["'"++word++"'" "encodes to" encoded "which correctly decodes to" "'"++decoded++"'"]
]</syntaxhighlight>
{{out}}
<pre>'broood' encodes to [1 17 15 0 0 5] which correctly decodes to 'broood'
'babanaaa' encodes to [1 1 1 1 13 1 0 0] which correctly decodes to 'babanaaa'
'hiphophiphop' encodes to [7 8 15 2 15 2 2 3 2 2 3 2] which correctly decodes to 'hiphophiphop'</pre>
=={{header|AutoHotkey}}==
<
str := "abcdefghijklmnopqrstuvwxyz"
loop, parse, string
Line 354 ⟶ 599:
return string
}
</syntaxhighlight>
Examples:<
loop, parse, testStrings, `,
Output .= A_LoopField "`t" MTF_Encode(A_LoopField) "`t" MTF_Decode(MTF_Encode(A_LoopField)) "`n"
MsgBox % Output
return</
Outputs:<pre>broood 1,17,15,0,0,5 broood
bananaaa 1,1,13,1,1,1,0,0 bananaaa
hiphophiphop 7,8,15,2,15,2,2,3,2,2,3,2 hiphophiphop</pre>
=={{header|Bracmat}}==
<syntaxhighlight lang="bracmat"> ( encode
= string symboltable
. !arg:(?string.?symboltable)
& vap
$ ( (
= A Z i
. !symboltable:?A [?i !arg ?Z
& !arg !A !Z:?symboltable
& !i
)
. !string
)
)
& ( decode
= indices symboltable
. !arg:(?indices.?symboltable)
& str
$ ( map
$ ( (
= A Z symbol
. !symboltable:?A [!arg %?symbol ?Z
& !symbol !A !Z:?symboltable
& !symbol
)
. !indices
)
)
)
& ( test
= string symboltable encoded decoded
. !arg:(?string.?symboltable)
& put$str$("input:" !string ", ")
& encode$(!string.!symboltable):?encoded
& put$("encoded:" !encoded ", ")
& decode$(!encoded.!symboltable):?decoded
& put$str$("decoded:" !decoded ", ")
& ( !string:!decoded
& out$OK
| out$WRONG
)
)
& a b c d e f g h i j k l m n o p q r s t y v w x y z
: ?symboltable
& test$(broood.!symboltable)
& test$(bananaaa.!symboltable)
& test$(hiphophiphop.!symboltable)</syntaxhighlight>
=={{header|C}}==
<
#include<stdlib.h>
#include<string.h>
Line 452 ⟶ 745:
}
return 0;
}</
{{Out}}
<pre>broood : [1 17 15 0 0 5 ]
Line 460 ⟶ 753:
hiphophiphop : [7 8 15 2 15 2 2 3 2 2 3 2 ]
Correct :)</pre>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">
using System;
using System.Collections.Generic;
using System.Text;
namespace MoveToFront
{
class Program
{
private static char[] symbolTable;
private static void setSymbolTable()
{
symbolTable = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
}
private static void moveToFront(int charIndex)
{
char toFront = symbolTable[charIndex];
for (int j = charIndex; j > 0; j--)
{
symbolTable[j] = symbolTable[j - 1];
}
symbolTable[0] = toFront;
}
public static int[] Encode(string input)
{
setSymbolTable();
var output = new List<int>();
foreach (char c in input)
{
for (int i = 0; i < 26; i++)
{
if (symbolTable[i] == c)
{
output.Add(i);
moveToFront(i);
break;
}
}
}
return output.ToArray();
}
public static string Decode(int[] input)
{
setSymbolTable();
var output = new StringBuilder(input.Length);
foreach (int n in input)
{
output.Append(symbolTable[n]);
moveToFront(n);
}
return output.ToString();
}
static void Main(string[] args)
{
string[] testInputs = new string[] { "broood", "bananaaa", "hiphophiphop" };
int[] encoding;
foreach (string s in testInputs)
{
Console.WriteLine($"Encoding for '{s}':");
encoding = Encode(s);
foreach (int i in encoding)
{
Console.Write($"{i} ");
}
Console.WriteLine($"\nDecoding for '{s}':");
Console.WriteLine($"{Decode(encoding)}\n");
}
}
}
}
</syntaxhighlight>
=={{header|C++}}==
<syntaxhighlight lang="cpp">
#include <iostream>
#include <iterator>
Line 545 ⟶ 915:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 552 ⟶ 922:
hiphophiphop -> encoded = 7 8 15 2 15 2 2 3 2 2 3 2 ; decoded = hiphophiphop
</pre>
=={{header|Clojure}}==
<
(defn move-to-front [x xs]
Line 651 ⟶ 944:
decoded (decode encoded lowercase)]
(println (format "%s encodes to %s which decodes back to %s."
word encoded decoded))))</
{{Out}}
Line 661 ⟶ 954:
=={{header|Common Lisp}}==
<
(defun move-to-front (x xs)
Line 687 ⟶ 980:
(assert (string= word decoded))
(format T "~s encodes to ~a which decodes back to ~s.~%"
word encoded decoded)))</
{{Out}}
Line 695 ⟶ 988:
=={{header|D}}==
<
ptrdiff_t[] mtfEncoder(in string data) pure nothrow @safe
Line 743 ⟶ 1,036:
assert(word == decoded);
}
}</
{{out}}
<pre>'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'
Line 750 ⟶ 1,043:
=={{header|Elixir}}==
<
@table Enum.to_list(?a..?z)
Line 775 ⟶ 1,068:
IO.inspect enc = MoveToFront.encode(word)
IO.puts "#{word == MoveToFront.decode(enc)}\n"
end)</
{{out}}
Line 790 ⟶ 1,083:
[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2]
true
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// Move-to-front algorithm . Nigel Galloway: March 1st., 2021
let fN g=List.permute(fun n->match compare n g with 0->0 |1->n |_->n+1)
let decode n=let rec fG n g=[|match n with n::t->yield List.item n g; yield! fG t (fN n g)|_->()|] in fG n ['a'..'z']|>System.String
let encode n=let rec fG n g=[match n with n::t->let n=g|>List.findIndex((=)n) in yield n; yield! fG t (fN n g)|_->()]
fG ((string n).ToCharArray()|>List.ofArray) ['a'..'z']
["broood";"bananaaa";"hiphophiphop"]|>List.iter(fun n->let i=encode n in let g=decode i in printfn "%s->%A->%s check=%A" n i g (n=g))
</syntaxhighlight>
{{out}}
<pre>
broood->[1; 17; 15; 0; 0; 5]->broood check=true
bananaaa->[1; 1; 13; 1; 1; 1; 0; 0]->bananaaa check=true
hiphophiphop->[7; 8; 15; 2; 15; 2; 2; 3; 2; 2; 3; 2]->hiphophiphop check=true
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: formatting kernel locals make sequences ;
: to-front ( elt seq -- seq' ) over [ remove ] dip prefix ;
: encode ( symbols msg -- indices )
[ [ swap 2dup index , to-front ] each ] { } make nip ;
: decode ( symbols indices -- msg )
[ [ swap [ nth ] keep over , to-front ] each ] "" make nip ;
:: round-trip ( msg symbols -- )
symbols msg encode :> encoded
symbols encoded decode :> decoded
msg decoded assert=
msg encoded decoded "%s -> %u -> %s\n" printf ;
"broood" "bananaaa" "hiphophiphop"
[ "abcdefghijklmnopqrstuvwxyz" round-trip ] tri@</syntaxhighlight>
{{out}}
<pre>
broood -> { 1 17 15 0 0 5 } -> broood
bananaaa -> { 1 1 13 1 1 1 0 0 } -> bananaaa
hiphophiphop -> { 7 8 15 2 15 2 2 3 2 2 3 2 } -> hiphophiphop
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight 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() )</syntaxhighlight>
{{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>
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=4268c779c36def03ea10764630cdc401 Click this link to run this code]'''
<
Dim sToCode As String[] = ["broood", "bananaaa", "hiphophiphop"] 'Samples to process
Dim sHold As New String[] 'To store results
Line 826 ⟶ 1,272:
Next
End</
Output:
<pre>
Line 840 ⟶ 1,286:
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 852 ⟶ 1,298:
seq := make([]byte, len(s))
pad := []byte(symbols)
x := bytes.IndexByte(pad, c)
copy(pad[1:], pad[:x])
pad[0] = c
Line 886 ⟶ 1,329:
}
}
}</
{{out}}
<pre>
Line 895 ⟶ 1,338:
=={{header|Haskell}}==
<
import Data.Maybe (fromJust)
Line 919 ⟶ 1,362:
(,) <*> uncurry ((==) . fst) <$> -- Test that ((fst . fst) x) == snd x)
((,) <*> (decode . snd) <$>
((,) <*> encode <$> ["broood", "bananaaa", "hiphophiphop"]))</
{{out}}
<pre>((("broood",[1,17,15,0,0,5]),"broood"),True)
Line 928 ⟶ 1,371:
Works in both languages:
<
every writes(s := !A, " -> [") do {
every writes(!(enc := encode(&lcase,s))," ")
Line 956 ⟶ 1,399:
procedure reorder(s1,s2,s3)
return s2||s1||s3
end</
Sample run:
Line 969 ⟶ 1,412:
=={{header|J}}==
<
'seq table'=. y
ndx=.$0
Line 989 ⟶ 1,432:
end.
seq
)</
Required examples:
<
1 17 15 0 0 5
spindizzy 'bananaaa';'abcdefghijklmnopqrstuvwxyz'
1 1 13 1 1 1 0 0
spindizzy 'hiphophiphop';'abcdefghijklmnopqrstuvwxyz'
7 8 15 2 15 2 2 3 2 2 3 2</
It's not clear, though, why anyone would think that this is any better than lookups against an unmodified symbol table.
=={{header|Java}}==
{{works with|Java|1.5+}}
<
import java.util.List;
Line 1,042 ⟶ 1,486:
test("hiphophiphop", symTable);
}
}</
{{out}}
<pre>broood: [1, 17, 15, 0, 0, 5]
Line 1,052 ⟶ 1,496:
=={{header|JavaScript}}==
<
var init = {wordAsNumbers: [], charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};
Line 1,082 ⟶ 1,526:
console.log(encoded);
console.log("from decoded:");
console.log(decoded);</
{{out}}
<pre>from encoded:
Line 1,095 ⟶ 1,539:
=={{header|jq}}==
{{works with|jq|q.4}}
<
# Output: the encoded string (an array)
def m2f_encode(st):
Line 1,113 ⟶ 1,557:
| [ (.[0] + [ $st[$ix] ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )
| .[0]
| implode;</
'''Example''':
<
| ("broood", "bananaaa", "hiphophiphop")
| . as $string
Line 1,123 ⟶ 1,567:
| if $string == $decoded then "\($string) => \($encoded) => \($decoded)"
else "INTERNAL ERROR: encoding of \($string) => \($encoded) => \($decoded)"
end</
{{Out}}
<
broood => [1,17,15,0,0,5] => broood
bananaaa => [1,1,13,1,1,1,0,0] => bananaaa
hiphophiphop => [7,8,15,2,15,2,2,3,2,2,3,2] => hiphophiphop</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
function encode(ch::Char)
r = findfirst(symtable, ch)
Line 1,164 ⟶ 1,608:
@test str == dec
end
end</
{{out}}
Line 1,180 ⟶ 1,624:
=={{header|Kotlin}}==
<
fun encode(s: String): IntArray {
Line 1,227 ⟶ 1,671:
println(" -> ${if (decoded[i] == strings[i]) "correct" else "incorrect"}")
}
}</
{{out}}
Line 1,241 ⟶ 1,685:
=={{header|Lua}}==
<
function getAlphabet ()
local letters = {}
Line 1,286 ⟶ 1,730:
print("Decoded: " .. decode(output))
print()
end</
{{out}}
<pre>Original string: broood
Line 1,300 ⟶ 1,744:
Decoded: hiphophiphop</pre>
edit
=={{header|M2000 Interpreter}}==
In Encode$() we use a string of parameters (function Quote$() make this)
Function Param() get the string with parameters and place it in code (inline).
In Decode$ we use current stack (first we flush to ensure that isn't some other arguments on it, M2000 has no signature control over the call of user functions, we can place anything)
For deleting and inserting characters in a string we use Insert. Insert of "" in a place of 1 char means delete it. So Insert k, 1 SymbolTable$="" means that in k position, for one char we place empty string.
To extract information to clipboard we use global variables, is handy;
Number pop a number from stack of values, if no number found then raise error.
<syntaxhighlight lang="m2000 interpreter">
Module CheckIt {
Global All$, nl$
\\ upgrade to document
Document All$
Nl$<={
}
Function Encode$(Inp$) {
Def SymbolTable$="abcdefghijklmnopqrstuvwxyz", Out$=""
For i=1 to Len(Inp$)
c$=Mid$(Inp$, i, 1)
k=Instr(SymbolTable$, c$)
Insert k, 1 SymbolTable$=""
Out$=If$(Out$="" -> Quote$(k-1),Quote$(Param(Out$), k-1))
Insert 1 SymbolTable$=c$
\\ we use <= for globals
All$<=Format$(" {0} {1:30} {2}", c$, Out$, SymbolTable$)+nl$
Next i
=Out$
}
Function Decode$(Inp$) {
Def SymbolTable$="abcdefghijklmnopqrstuvwxyz", Out$=""
flush
Data Param(Inp$)
While not empty {
k=Number+1
c$=Mid$(SymbolTable$, k, 1)
Out$+=c$
Insert k, 1 SymbolTable$="" ' erase at position k
Insert 1 SymbolTable$=c$
All$<=Format$("{0::-2} {1} {2:30} {3}", k-1, c$, Out$, SymbolTable$)+nl$
}
=Out$
}
TryThis("broood")
TryThis("bananaaa")
TryThis("hiphophiphop")
ClipBoard All$
Sub TryThis(a$)
Local Out$=Encode$(a$)
Local final$=Decode$(Out$)
Print final$, final$=a$
End Sub
}
CheckIt
</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
broood True
bananaaa True
hiphophiphop True
</pre>
From clipboard
<pre style="height:30ex;overflow:scroll">
b 1 bacdefghijklmnopqrstuvwxyz
r 1,17 rbacdefghijklmnopqstuvwxyz
o 1,17,15 orbacdefghijklmnpqstuvwxyz
o 1,17,15,0 orbacdefghijklmnpqstuvwxyz
o 1,17,15,0,0 orbacdefghijklmnpqstuvwxyz
d 1,17,15,0,0,5 dorbacefghijklmnpqstuvwxyz
1 b b bacdefghijklmnopqrstuvwxyz
17 r br rbacdefghijklmnopqstuvwxyz
15 o bro orbacdefghijklmnpqstuvwxyz
0 o broo orbacdefghijklmnpqstuvwxyz
0 o brooo orbacdefghijklmnpqstuvwxyz
5 d broood dorbacefghijklmnpqstuvwxyz
b 1 bacdefghijklmnopqrstuvwxyz
a 1,1 abcdefghijklmnopqrstuvwxyz
n 1,1,13 nabcdefghijklmopqrstuvwxyz
a 1,1,13,1 anbcdefghijklmopqrstuvwxyz
n 1,1,13,1,1 nabcdefghijklmopqrstuvwxyz
a 1,1,13,1,1,1 anbcdefghijklmopqrstuvwxyz
a 1,1,13,1,1,1,0 anbcdefghijklmopqrstuvwxyz
a 1,1,13,1,1,1,0,0 anbcdefghijklmopqrstuvwxyz
1 b b bacdefghijklmnopqrstuvwxyz
1 a ba abcdefghijklmnopqrstuvwxyz
13 n ban nabcdefghijklmopqrstuvwxyz
1 a bana anbcdefghijklmopqrstuvwxyz
1 n banan nabcdefghijklmopqrstuvwxyz
1 a banana anbcdefghijklmopqrstuvwxyz
0 a bananaa anbcdefghijklmopqrstuvwxyz
0 a bananaaa anbcdefghijklmopqrstuvwxyz
h 7 habcdefgijklmnopqrstuvwxyz
i 7,8 ihabcdefgjklmnopqrstuvwxyz
p 7,8,15 pihabcdefgjklmnoqrstuvwxyz
h 7,8,15,2 hpiabcdefgjklmnoqrstuvwxyz
o 7,8,15,2,15 ohpiabcdefgjklmnqrstuvwxyz
p 7,8,15,2,15,2 pohiabcdefgjklmnqrstuvwxyz
h 7,8,15,2,15,2,2 hpoiabcdefgjklmnqrstuvwxyz
i 7,8,15,2,15,2,2,3 ihpoabcdefgjklmnqrstuvwxyz
p 7,8,15,2,15,2,2,3,2 pihoabcdefgjklmnqrstuvwxyz
h 7,8,15,2,15,2,2,3,2,2 hpioabcdefgjklmnqrstuvwxyz
o 7,8,15,2,15,2,2,3,2,2,3 ohpiabcdefgjklmnqrstuvwxyz
p 7,8,15,2,15,2,2,3,2,2,3,2 pohiabcdefgjklmnqrstuvwxyz
7 h h habcdefgijklmnopqrstuvwxyz
8 i hi ihabcdefgjklmnopqrstuvwxyz
15 p hip pihabcdefgjklmnoqrstuvwxyz
2 h hiph hpiabcdefgjklmnoqrstuvwxyz
15 o hipho ohpiabcdefgjklmnqrstuvwxyz
2 p hiphop pohiabcdefgjklmnqrstuvwxyz
2 h hiphoph hpoiabcdefgjklmnqrstuvwxyz
3 i hiphophi ihpoabcdefgjklmnqrstuvwxyz
2 p hiphophip pihoabcdefgjklmnqrstuvwxyz
2 h hiphophiph hpioabcdefgjklmnqrstuvwxyz
3 o hiphophipho ohpiabcdefgjklmnqrstuvwxyz
2 p hiphophiphop pohiabcdefgjklmnqrstuvwxyz
</pre >
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">mtf[word_]:=Module[{f,f2,p,q},
f[{output_,symList_},next_]:=Module[{index},index=Position[symList,next][[1,1]]-1;
{output~Append~index,Prepend[Delete[symList,index+1],next]}];
Line 1,309 ⟶ 1,878:
{output~Append~index,Prepend[DeleteCases[symList,ToString[index]],index]}];
q=Fold[f2,{{},CharacterRange["a","z"]},p][[1]];
Print["'", word,"' encodes to: ",p, " - " ,p," decodes to: '",StringJoin@q,"' - Input equals Output: " ,word===StringJoin@q];]</
Testing out the function:
<
{{out}}
<pre>'broood' encodes to: {1,17,15,0,0,5} - {1,17,15,0,0,5} decodes to: 'broood' - Input equals Output: True
Line 1,318 ⟶ 1,887:
=={{header|MATLAB}}==
<
symTable = 'abcdefghijklmnopqrstuvwxyz';
inStr = {'broood' 'bananaaa' 'hiphophiphop'};
Line 1,347 ⟶ 1,916:
symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];
end
end</
{{out}}
<pre>broood: [ 1 17 15 0 0 5 ]
Line 1,355 ⟶ 1,924:
hiphophiphop: [ 7 8 15 2 15 2 2 3 2 2 3 2 ]
correctly decoded to hiphophiphop</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import algorithm, sequtils, strformat
const SymbolTable = toSeq('a'..'z')
func encode(s: string): seq[int] =
var symtable: seq[char] = SymbolTable
for c in s:
let idx = symtable.find(c)
result.add idx
symtable.rotateLeft(0..idx, -1)
func decode(s: seq[int]): string =
var symtable = SymbolTable
for idx in s:
result.add symtable[idx]
symtable.rotateLeft(0..idx, -1)
for word in ["broood", "babanaaa", "hiphophiphop"]:
let encoded = word.encode()
let decoded = encoded.decode()
let status = if decoded == word: "correctly" else: "incorrectly"
echo &"'{word}' encodes to {encoded} which {status} decodes to '{decoded}'."</syntaxhighlight>
{{out}}
<pre>'broood' encodes to @[1, 17, 15, 0, 0, 5] which correctly decodes to 'broood'.
'babanaaa' encodes to @[1, 1, 1, 1, 13, 1, 0, 0] which correctly decodes to 'babanaaa'.
'hiphophiphop' encodes to @[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] which correctly decodes to 'hiphophiphop'.</pre>
=={{header|Perl}}==
<
use warnings;
sub encode {
Line 1,383 ⟶ 1,981:
print "correctly decoded to $decoded\n";
}
</syntaxhighlight>
{{out}}
<pre>broood: 1 17 15 0 0 5
Line 1,392 ⟶ 1,990:
correctly decoded to hiphophiphop
</pre>
=={{header|Phix}}==
Equivalent longhand versions of the symtab reordering left in as comments
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">encode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">symtab</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"abcdefghijklmnopqrstuvwxyz"</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">symtab</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000080;font-style:italic;">-- for j=k to 2 by -1 do
-- symtab[j] = symtab[j-1]
-- end for
-- symtab[1] = ch</span>
<span style="color: #000000;">symtab</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">&</span><span style="color: #000000;">symtab</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">decode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">symtab</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"abcdefghijklmnopqrstuvwxyz"</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">symtab</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ch</span>
<span style="color: #000080;font-style:italic;">-- for j=k to 2 by -1 do
-- symtab[j] = symtab[j-1]
-- end for
-- symtab[1] = ch</span>
<span style="color: #000000;">symtab</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">&</span><span style="color: #000000;">symtab</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">encode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">decode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"**ERROR**"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ok"</span><span style="color: #0000FF;">}[(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"broood"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"bananaaa"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"hiphophiphop"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{"broood",{1,17,15,0,0,5},"broood","ok"}
{"bananaaa",{1,1,13,1,1,1,0,0},"bananaaa","ok"}
{"hiphophiphop",{7,8,15,2,15,2,2,3,2,2,3,2},"hiphophiphop","ok"}
</pre>
=={{header|PHP}}==
<syntaxhighlight lang="php"><?php
function symbolTable() {
$symbol = array();
for ($c = ord('a') ; $c <= ord('z') ; $c++) {
$symbol[$c - ord('a')] = chr($c);
}
return $symbol;
}
function mtfEncode($original, $symbol) {
$encoded[] = $position;
$mtf = $symbol[$position];
unset($symbol[$position]);
array_unshift($symbol, $mtf);
}
return $encoded;
}
function mtfDecode($encoded, $symbol) {
$decoded = '';
foreach ($encoded AS $position) {
array_unshift($symbol, $char);
}
return $decoded;
}
foreach (array('broood', 'bananaaa', 'hiphophiphop') AS $original) {
$encoded = mtfEncode($original, symbolTable());
$decoded = mtfDecode($encoded, symbolTable());
echo
$original,
' -> [', implode(',', $encoded), ']',
' -> ', $decoded,
' : ', ($original === $decoded ? 'OK' : 'Error'),
PHP_EOL;
}</syntaxhighlight>
{{out}}
<pre>broood -> [1,17,15,0,0,5] -> broood : OK
bananaaa -> [1,1,13,1,1,1,0,0] -> bananaaa : OK
hiphophiphop -> [7,8,15,2,15,2,2,3,2,2,3,2] -> hiphophiphop : OK</pre>
=={{header|
Picat has 1-based index so some adjustments was necessary.
<syntaxhighlight lang="picat">import util.
go =>
Strings = ["broood", "bananaaa", "hiphophiphop"],
foreach(String in Strings)
check(String)
end,
nl.
% adjustments to 1-based index
encode(String) = [Pos,Table] =>
Table = "abcdefghijklmnopqrstuvwxyz",
Pos =
Len = String.length,
foreach({C,I} in zip(String,1..Len))
Pos := Pos ++ [find_first_of(Table,C)-1],
if Len > I then
Table := [C] ++ delete(Table,C)
end
end.
decode(Pos) = String =>
Table = "abcdefghijklmnopqrstuvwxyz",
String = [],
foreach(P in Pos)
C = Table[P+1],
Table := [C] ++ delete(Table,C),
String := String ++ [C]
end.
% Check the result
check(String) =>
[Pos,Table] = encode(String),
String2 = decode(Pos),
if length(String) < 100 then
println(pos=Pos),
println(table=Table),
println(string2=String2)
else
printf("String is too long to print (%d chars)\n", length(String))
end,
println(cond(String != String2, "not ", "") ++ "same"),
nl.</syntaxhighlight>
{{out}}
<pre>pos = [1,17,15,0,0,5]
table = orbacdefghijklmnpqstuvwxyz
string2 = broood
same
pos = [1,1,13,1,1,1,0,0]
table = anbcdefghijklmopqrstuvwxyz
string2 = bananaaa
same
pos = [7,8,15,2,15,2,2,3,2,2,3,2]
table = ohpiabcdefgjklmnqrstuvwxyz
string2 = hiphophiphop
same</pre>
=={{header|PicoLisp}}==
<
(let Table (chop "abcdefghijklmnopqrstuvwxyz")
(mapcar
Line 1,488 ⟶ 2,175:
(get Table (inc 'N))
(rot Table N) ) )
Lst ) ) ) )</
Test:
<
(encode "broood") )
(test "broood"
Line 1,503 ⟶ 2,190:
(encode "hiphophiphop") )
(test "hiphophiphop"
(decode (7 8 15 2 15 2 2 3 2 2 3 2)) )</
=={{header|PL/I}}==
<
/*********************************************************************
* 25.5.2014 Walter Pachl translated from REXX
Line 1,545 ⟶ 2,232:
Else
Put Skip List('all wrong!!');
End;</
{{out}}
<pre> in=broood
Line 1,566 ⟶ 2,253:
=={{header|PowerShell}}==
<
{
[CmdletBinding()]
Line 1,640 ⟶ 2,327:
}
End{}
}</
{{out}}
Line 1,656 ⟶ 2,343:
===Python: Procedural===
<
from string import ascii_lowercase
Line 1,683 ⟶ 2,370:
decode = move2front_decode(encode, SYMBOLTABLE)
print('which decodes back to %r' % decode)
assert s == decode, 'Whoops!'</
{{out}}
Line 1,694 ⟶ 2,381:
For the functional forms a 2-item list of output to be accumulated and symboltable manipulation is calculated then only the former accumulated as the later works to transform the symbol table in-place.
<
return [[st.index(ch), st.insert(0, st.pop(st.index(ch)))][0] for ch in s]
Line 1,706 ⟶ 2,393:
decode = m2f_d(encode, ST[::])
print('decodes back to %r' % decode)
assert s == decode, 'Whoops!'</
{{out}}
Similar to that of the procedural version above.
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ []
26 times
[ char a i^ +
join ] ] constant is symbols ( --> $ )
[ [] symbols rot
witheach
[ over find
tuck pluck
swap join
dip join ]
drop ] is encode ( $ --> [ )
[ $ "" symbols rot
witheach
[ pluck
dup rot join
dip join ]
drop ] is decode ( [ --> $ )
[ dup echo$
say " --> "
dup encode
dup echo
say " --> "
decode
dup echo$
= iff
[ say " :-)" ]
else
[ say " :-(" ]
cr cr ] is task ( $ --> )
$ "broood bananaaa hiphophiphop"
nest$ witheach task</syntaxhighlight>
{{out}}
<pre>broood --> [ 1 17 15 0 0 5 ] --> broood :-)
bananaaa --> [ 1 1 13 1 1 1 0 0 ] --> bananaaa :-)
hiphophiphop --> [ 7 8 15 2 15 2 2 3 2 2 3 2 ] --> hiphophiphop :-)
</pre>
=={{header|Racket}}==
<
(define default-symtab "abcdefghijklmnopqrstuvwxyz")
Line 1,756 ⟶ 2,490:
(printf "~s encodes to ~s, which decodes ~s to ~s.~%" str enc crt dec))
(for-each encode+decode-string '("broood" "bananaaa" "hiphophiphop")))</
{{out}}
Line 1,762 ⟶ 2,496:
"bananaaa" encodes to (1 1 13 1 1 1 0 0), which decodes "correctly" to "bananaaa".
"hiphophiphop" encodes to (7 8 15 2 15 2 2 3 2 2 3 2), which decodes "correctly" to "hiphophiphop".</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2015-09-24}}
<syntaxhighlight lang="raku" line>sub encode ( Str $word ) {
my @sym = 'a' .. 'z';
gather for $word.comb -> $c {
die "Symbol '$c' not found in @sym" if $c eq @sym.none;
@sym[0 .. take (@sym ... $c).end] .= rotate(-1);
}
}
sub decode ( @enc ) {
my @sym = 'a' .. 'z';
[~] gather for @enc -> $pos {
take @sym[$pos];
@sym[0..$pos] .= rotate(-1);
}
}
use Test;
plan 3;
for <broood bananaaa hiphophiphop> -> $word {
my $enc = encode($word);
my $dec = decode($enc);
is $word, $dec, "$word.fmt('%-12s') ($enc[])";
}</syntaxhighlight>
{{out}}
<pre>1..3
ok 1 - broood (1 17 15 0 0 5)
ok 2 - bananaaa (1 1 13 1 1 1 0 0)
ok 3 - hiphophiphop (7 8 15 2 15 2 2 3 2 2 3 2)</pre>
=={{header|REXX}}==
===version 1===
<
* 25.05.2014 Walter Pachl
* REXX strings start with position 1
Line 1,800 ⟶ 2,566:
Say 'all wrong!!'
Return
</syntaxhighlight>
{{out}}
<pre> in=broood
Line 1,822 ⟶ 2,588:
===version 2===
Programming note: the two REXX statements that add/subtract <big> '''one''' </big> deal with the task's requirement that the symbol table be ''zero-indexed'' (the REXX language uses ''unity-based'' strings).
<
parse arg xxx; if xxx='' then xxx= 'broood bananaaa hiphophiphop' /*use the default?*/
one=
do j=1 for words(xxx);
@= 'abcdefghijklmnopqrstuvwxyz'; @@=
$= /*set the decode string to a null. */
do k=1 for length(x);
_= pos(z, @);
$= $ (_ - one);
end /*k*/ /* [↑] the move─to─front encoding. */
!= /*set the encode string to a null. */
do m=1 for words($);
y= substr(@@, n, 1);
@@= y || delstr(@@, n, 1)
end /*m*/ /* [↑] the move─to─front decoding. */
say ' word: '
end /*j*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default input:}}
<pre>
word: broood encoding: 1 17 15 0 0 5 OK
word: bananaaa encoding: 1 1 13 1 1 1 0 0 OK
word: hiphophiphop encoding: 7 8 15 2 15 2 2 3 2 2 3 2 OK
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Move-to-front algorithm
test("broood")
test("bananaaa")
test("hiphophiphop")
func encode(s)
symtab = "abcdefghijklmnopqrstuvwxyz"
res = ""
for i=1 to len(s)
ch = s[i]
k = substr(symtab, ch)
res = res + " " + (k-1)
for j=k to 2 step -1
symtab[j] = symtab[j-1]
next
symtab[1] = ch
next
return res
func decode(s)
s = str2list( substr(s, " ", nl) )
symtab = "abcdefghijklmnopqrstuvwxyz"
res = ""
for i=1 to len(s)
k = number(s[i]) + 1
ch = symtab[k]
res = res + " " + ch
for j=k to 2 step -1
symtab[j] = symtab[j-1]
next
symtab[1] = ch
next
return right(res, len(res)-2)
func test(s)
e = encode(s)
d = decode(e)
see "" + s + " => " + "(" + right(e, len(e) - 1) + ") " + " => " + substr(d, " ", "") + nl
</syntaxhighlight>
Output:
<pre>
broood => (1 17 15 0 0 5) => broood
bananaaa => (1 1 13 1 1 1 0 0) => bananaaa
hiphophiphop => (7 8 15 2 15 2 2 3 2 2 3 2) => hiphophiphop
</pre>
=={{header|Ruby}}==
Use a module as namespace:
<
ABC = ("a".."z").to_a.freeze
Line 1,877 ⟶ 2,692:
['broood', 'bananaaa', 'hiphophiphop'].each do |word|
p word == MoveToFront.decode(p MoveToFront.encode(p word))
end</
{{out}}
Line 1,890 ⟶ 2,705:
[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2]
true
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn main() {
let examples = vec!["broood", "bananaaa", "hiphophiphop"];
for example in examples {
let encoded = encode(example);
let decoded = decode(&encoded);
println!(
"{} encodes to {:?} decodes to {}",
example, encoded, decoded
);
}
}
fn get_symbols() -> Vec<u8> {
(b'a'..b'z').collect()
}
fn encode(input: &str) -> Vec<usize> {
input
.as_bytes()
.iter()
.fold((Vec::new(), get_symbols()), |(mut o, mut s), x| {
let i = s.iter().position(|c| c == x).unwrap();
let c = s.remove(i);
s.insert(0, c);
o.push(i);
(o, s)
})
.0
}
fn decode(input: &[usize]) -> String {
input
.iter()
.fold((Vec::new(), get_symbols()), |(mut o, mut s), x| {
o.push(s[*x]);
let c = s.remove(*x);
s.insert(0, c);
(o, s)
})
.0
.into_iter()
.map(|c| c as char)
.collect()
}</syntaxhighlight>
{{out}}
<pre>
broood encodes to [1, 17, 15, 0, 0, 5] decodes to broood
bananaaa encodes to [1, 1, 13, 1, 1, 1, 0, 0] decodes to bananaaa
hiphophiphop encodes to [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] decodes to hiphophiphop
</pre>
=={{header|Scala}}==
{{works with|Scala|2.11.8+}}
<
import scala.annotation.tailrec
Line 1,990 ⟶ 2,859:
MoveToFront.test("bananaaa", symTable)
MoveToFront.test("hiphophiphop", symTable)
}</
{{out}}
<pre>broood: List(1, 17, 15, 0, 0, 5)
Line 2,002 ⟶ 2,871:
{{trans|Perl}}
Implemented using regular expressions:
<
var table = ('a'..'z' -> join);
str.chars.map { |c|
Line 2,026 ⟶ 2,895:
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}</
Alternatively, implemented as a module, using arrays:
<
define ABC = @("a".."z")
Line 2,064 ⟶ 2,933:
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}</
{{out}}
Line 2,077 ⟶ 2,946:
=={{header|Swift}}==
<
var str="broood"
Line 2,148 ⟶ 3,017:
print(encarr)
print(decarr)
</syntaxhighlight>
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
oo::class create MoveToFront {
Line 2,190 ⟶ 3,059:
puts [format "'%s' encodes to %s. This decodes to '%s'. %s" \
$tester $enc $dec [expr {$tester eq $dec ? "Correct!" : "WRONG!"}]]
}</
{{out}}
<pre>
Line 2,199 ⟶ 3,068:
=={{header|VBScript}}==
<
'create the array list and populate it with the initial symbol position
Set symbol_table = CreateObject("System.Collections.ArrayList")
Line 2,247 ⟶ 3,116:
mtf_decode(mtf_encode(word)) & "."
WScript.StdOut.WriteBlankLines(1)
Next</
{{Out}}
Line 2,254 ⟶ 3,123:
bananaaa encodes as 1 1 13 1 1 1 0 0 and decodes as bananaaa.
hiphophiphop encodes as 7 8 15 2 15 2 2 3 2 2 3 2 and decodes as hiphophiphop.
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
{{libheader|Wren-seq}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./seq" for Lst
var encode = Fn.new { |s|
if (s.isEmpty) return []
var symbols = "abcdefghijklmnopqrstuvwxyz".toList
var result = List.filled(s.count, 0)
var i = 0
for (c in s) {
var index = Lst.indexOf(symbols, c)
if (index == -1) Fiber.abort("%(s) contains a non-alphabetic character")
result[i] = index
if (index > 0) {
for (j in index-1..0) symbols[j + 1] = symbols[j]
symbols[0] = c
}
i = i + 1
}
return result
}
var decode = Fn.new { |a|
if (a.isEmpty) return ""
var symbols = "abcdefghijklmnopqrstuvwxyz".toList
var result = List.filled(a.count, "")
var i = 0
for (n in a) {
if (n < 0 || n > 25) Fiber.abort("%(a) contains an invalid number")
result[i] = symbols[n]
if (n > 0) {
for (j in n-1..0) symbols[j + 1] = symbols[j]
symbols[0] = result[i]
}
i = i + 1
}
return result.join()
}
var strings = ["broood", "bananaaa", "hiphophiphop"]
var encoded = List.filled(strings.count, null)
var i = 0
for (s in strings) {
encoded[i] = encode.call(s)
Fmt.print("$-12s -> $n", s, encoded[i])
i = i + 1
}
System.print()
var decoded = List.filled(encoded.count, null)
i = 0
for (a in encoded) {
decoded[i] = decode.call(a)
var correct = (decoded[i] == strings[i]) ? "correct" : "incorrect"
Fmt.print("$-38n -> $-12s -> $s", a, decoded[i], correct)
i = i + 1
}</syntaxhighlight>
{{out}}
<pre>
broood -> [1, 17, 15, 0, 0, 5]
bananaaa -> [1, 1, 13, 1, 1, 1, 0, 0]
hiphophiphop -> [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2]
[1, 17, 15, 0, 0, 5] -> broood -> correct
[1, 1, 13, 1, 1, 1, 0, 0] -> bananaaa -> correct
[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] -> hiphophiphop -> correct
</pre>
=={{header|zkl}}==
<
st:=["a".."z"].pump(Data); //"abcd..z" as byte array
text.reduce(fcn(st,c,sink){
n:=st.index(c); sink.write(n); st.del(n).insert(0,c); },st,sink:=L());
sink;
}</
Strings are immutable so we create a bit bucket (which is mutable) to hold the symbol table which can then be modified in place.
<
st:=["a".."z"].pump(String); //"abcd..z"
sink:=Sink(String);
list.reduce('wrap(st,n){ c:=st[n]; sink.write(c); c+st.del(n); },st);
sink.close();
}</
Here, we create a new symbol table each round as we would have to convert the byte we got from the bit bucket to string (so it is a wash garbage wise).
<
out:=texts.apply(encode);
texts.zipWith(fcn(t,e){ println(t,"-->",e) },out);
out.apply(decode).println();
texts.zipWith('==,out.apply(decode)).println();</
{{out}}
<pre>
|