Rosetta Code

Move-to-front algorithm: Difference between revisions

Page Discussion

Move-to-front algorithm (view source)

Revision as of 11:37, 4 January 2024

23,541 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
(24 intermediate revisions by 15 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).<br>
 
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 &nbsp; '''a'''-to-'''z'''
the 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:
:* &nbsp; Encode and decode the following three strings of characters using the symbol table of the lowercase characters &nbsp; '''a'''-to-'''z''' &nbsp; as above.
:* &nbsp; Show the strings and their encoding here.
:* &nbsp; Add a check to ensure that the decoded string is the same as the original.
 
<br>
Line 100 ⟶ 105:
<big> hiphophiphop </big>
 
 
(Note the spellings.)
<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}}==
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
 
procedure Move_To_Front is
Line 186 ⟶ 347:
Encode_Write_Check("bananaaa");
Encode_Write_Check("hiphophiphop");
end Move_To_Front;</langsyntaxhighlight>
 
{{out}}
Line 195 ⟶ 356:
 
=={{header|Aime}}==
<syntaxhighlight lang="aime">decode(list l)
<lang aime>text
decode(list l)
{
integer c, e;
Line 210 ⟶ 370:
}
 
encode(data s)
list
encode(text s)
{
integer c, e;
Line 218 ⟶ 377:
 
al = "abcdefghijklmnopqrstuvwxyz";
for (, c in b_draft(s)) {
l.append(e = al.place(c));
al.delete(e).insert(0, c);
Line 226 ⟶ 385:
}
 
integer
main(void)
{
for (, text s in list("broood", "bananaaa", "hiphophiphop")) {
integer i;
text s;
 
for (i, s in list("broood", "bananaaa", "hiphophiphop")) {
list l;
 
Line 241 ⟶ 396:
 
0;
}</langsyntaxhighlight>
{{out}}
<pre> 1 17 15 0 0 5: broood
Line 249 ⟶ 404:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<langsyntaxhighlight lang="algol68"># move the character at text pos to the front of text #
# note text pos is based from 0 #
PROC move to front = ( STRING text, INT text pos )STRING:
Line 385 ⟶ 540:
# ; test encode and decode( "zyxwvutsrqponmlkjihgfedcba" ) #
 
)</langsyntaxhighlight>
{{out}}
<pre>
Line 392 ⟶ 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}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">MTF_Encode(string){
str := "abcdefghijklmnopqrstuvwxyz"
loop, parse, string
Line 407 ⟶ 599:
return string
}
</syntaxhighlight>
</lang>
Examples:<langsyntaxhighlight AutoHotkeylang="autohotkey">testStrings = broood,bananaaa,hiphophiphop
loop, parse, testStrings, `,
Output .= A_LoopField "`t" MTF_Encode(A_LoopField) "`t" MTF_Decode(MTF_Encode(A_LoopField)) "`n"
MsgBox % Output
return</langsyntaxhighlight>
Outputs:<pre>broood 1,17,15,0,0,5 broood
bananaaa 1,1,13,1,1,1,0,0 bananaaa
Line 418 ⟶ 610:
 
=={{header|Bracmat}}==
<langsyntaxhighlight lang="bracmat"> ( encode
= string symboltable
. !arg:(?string.?symboltable)
Line 463 ⟶ 655:
& test$(broood.!symboltable)
& test$(bananaaa.!symboltable)
& test$(hiphophiphop.!symboltable)</langsyntaxhighlight>
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include<stdio.h>
#include<stdlib.h>
#include<string.h>
Line 553 ⟶ 745:
}
return 0;
}</langsyntaxhighlight>
{{Out}}
<pre>broood : [1 17 15 0 0 5 ]
Line 561 ⟶ 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">
<lang Cpp>
#include <iostream>
#include <iterator>
Line 646 ⟶ 915:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 653 ⟶ 922:
hiphophiphop -> encoded = 7 8 15 2 15 2 2 3 2 2 3 2 ; decoded = hiphophiphop
</pre>
 
=={{header|C#}}==
<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");
}
}
}
}
</lang>
 
=={{header|Clojure}}==
<langsyntaxhighlight lang="clojure">(def lowercase (map char (range (int \a) (inc (int \z)))))
 
(defn move-to-front [x xs]
Line 752 ⟶ 944:
decoded (decode encoded lowercase)]
(println (format "%s encodes to %s which decodes back to %s."
word encoded decoded))))</langsyntaxhighlight>
 
{{Out}}
Line 762 ⟶ 954:
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defconstant +lower+ (coerce "abcdefghijklmnopqrstuvwxyz" 'list))
 
(defun move-to-front (x xs)
Line 788 ⟶ 980:
(assert (string= word decoded))
(format T "~s encodes to ~a which decodes back to ~s.~%"
word encoded decoded)))</langsyntaxhighlight>
 
{{Out}}
Line 796 ⟶ 988:
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio, std.string, std.ascii, std.algorithm;
 
ptrdiff_t[] mtfEncoder(in string data) pure nothrow @safe
Line 844 ⟶ 1,036:
assert(word == decoded);
}
}</langsyntaxhighlight>
{{out}}
<pre>'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'
Line 851 ⟶ 1,043:
 
=={{header|Elixir}}==
<langsyntaxhighlight lang="elixir">defmodule MoveToFront do
@table Enum.to_list(?a..?z)
Line 876 ⟶ 1,068:
IO.inspect enc = MoveToFront.encode(word)
IO.puts "#{word == MoveToFront.decode(enc)}\n"
end)</langsyntaxhighlight>
 
{{out}}
Line 893 ⟶ 1,085:
</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}}==
<langsyntaxhighlight lang="factor">USING: formatting kernel locals make sequences ;
 
: to-front ( elt seq -- seq' ) over [ remove ] dip prefix ;
Line 911 ⟶ 1,118:
 
"broood" "bananaaa" "hiphophiphop"
[ "abcdefghijklmnopqrstuvwxyz" round-trip ] tri@</langsyntaxhighlight>
{{out}}
<pre>
Line 917 ⟶ 1,124:
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]'''
<langsyntaxhighlight lang="gambas">Public Sub Main()
Dim sToCode As String[] = ["broood", "bananaaa", "hiphophiphop"] 'Samples to process
Dim sHold As New String[] 'To store results
Line 953 ⟶ 1,272:
Next
 
End</langsyntaxhighlight>
Output:
<pre>
Line 967 ⟶ 1,286:
=={{header|Go}}==
{{trans|Python}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,010 ⟶ 1,329:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,019 ⟶ 1,338:
 
=={{header|Haskell}}==
<langsyntaxhighlight Haskelllang="haskell">import Data.List (delete, elemIndex, mapAccumL)
 
import Data.Maybe (fromJust)
Line 1,043 ⟶ 1,362:
(,) <*> uncurry ((==) . fst) <$> -- Test that ((fst . fst) x) == snd x)
((,) <*> (decode . snd) <$>
((,) <*> encode <$> ["broood", "bananaaa", "hiphophiphop"]))</langsyntaxhighlight>
{{out}}
<pre>((("broood",[1,17,15,0,0,5]),"broood"),True)
Line 1,052 ⟶ 1,371:
 
Works in both languages:
<langsyntaxhighlight lang="unicon">procedure main(A)
every writes(s := !A, " -> [") do {
every writes(!(enc := encode(&lcase,s))," ")
Line 1,080 ⟶ 1,399:
procedure reorder(s1,s2,s3)
return s2||s1||s3
end</langsyntaxhighlight>
 
Sample run:
Line 1,093 ⟶ 1,412:
=={{header|J}}==
 
<langsyntaxhighlight Jlang="j">spindizzy=:3 :0
'seq table'=. y
ndx=.$0
Line 1,113 ⟶ 1,432:
end.
seq
)</langsyntaxhighlight>
 
Required examples:
 
<langsyntaxhighlight Jlang="j"> spindizzy 'broood';'abcdefghijklmnopqrstuvwxyz'
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</langsyntaxhighlight>
 
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+}}
<langsyntaxhighlight lang="java5">import java.util.LinkedList;
import java.util.List;
 
Line 1,166 ⟶ 1,486:
test("hiphophiphop", symTable);
}
}</langsyntaxhighlight>
{{out}}
<pre>broood: [1, 17, 15, 0, 0, 5]
Line 1,176 ⟶ 1,496:
 
=={{header|JavaScript}}==
<langsyntaxhighlight lang="javascript">var encodeMTF = function (word) {
var init = {wordAsNumbers: [], charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};
 
Line 1,206 ⟶ 1,526:
console.log(encoded);
console.log("from decoded:");
console.log(decoded);</langsyntaxhighlight>
{{out}}
<pre>from encoded:
Line 1,219 ⟶ 1,539:
=={{header|jq}}==
{{works with|jq|q.4}}
<langsyntaxhighlight lang="jq"># Input is the string to be encoded, st is the initial symbol table (an array)
# Output: the encoded string (an array)
def m2f_encode(st):
Line 1,237 ⟶ 1,557:
| [ (.[0] + [ $st[$ix] ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )
| .[0]
| implode;</langsyntaxhighlight>
'''Example''':
<langsyntaxhighlight lang="jq">("abcdefghijklmnopqrstuvwxyz" | explode) as $ST
| ("broood", "bananaaa", "hiphophiphop")
| . as $string
Line 1,247 ⟶ 1,567:
| if $string == $decoded then "\($string) => \($encoded) => \($decoded)"
else "INTERNAL ERROR: encoding of \($string) => \($encoded) => \($decoded)"
end</langsyntaxhighlight>
{{Out}}
<langsyntaxhighlight lang="sh">$ jq -r -n -f move_to_front.jq
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</langsyntaxhighlight>
 
=={{header|Julia}}==
{{works with|Julia|0.6}}
<langsyntaxhighlight lang="julia">function encodeMTF(str::AbstractString, symtable::Vector{Char}=collect('a':'z'))
function encode(ch::Char)
r = findfirst(symtable, ch)
Line 1,288 ⟶ 1,608:
@test str == dec
end
end</langsyntaxhighlight>
 
{{out}}
Line 1,304 ⟶ 1,624:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">// version 1.1.2
 
fun encode(s: String): IntArray {
Line 1,351 ⟶ 1,671:
println(" -> ${if (decoded[i] == strings[i]) "correct" else "incorrect"}")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,365 ⟶ 1,685:
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">-- Return table of the alphabet in lower case
function getAlphabet ()
local letters = {}
Line 1,410 ⟶ 1,730:
print("Decoded: " .. decode(output))
print()
end</langsyntaxhighlight>
{{out}}
<pre>Original string: broood
Line 1,425 ⟶ 1,745:
 
edit
 
=={{header|M2000 Interpreter}}==
In Encode$() we use a string of parameters (function Quote$() make this)
Line 1,438 ⟶ 1,759:
Number pop a number from stack of values, if no number found then raise error.
 
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module CheckIt {
Global All$, nl$
Line 1,483 ⟶ 1,804:
}
CheckIt
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,548 ⟶ 1,869:
</pre >
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
 
<langsyntaxhighlight Mathematicalang="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,557 ⟶ 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];]</langsyntaxhighlight>
Testing out the function:
<langsyntaxhighlight Mathematicalang="mathematica">mtf /@ {"broood", "bananaaa", "hiphophiphop"}</langsyntaxhighlight>
{{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,566 ⟶ 1,887:
 
=={{header|MATLAB}}==
<langsyntaxhighlight MATLABlang="matlab">function testMTF
symTable = 'abcdefghijklmnopqrstuvwxyz';
inStr = {'broood' 'bananaaa' 'hiphophiphop'};
Line 1,595 ⟶ 1,916:
symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];
end
end</langsyntaxhighlight>
{{out}}
<pre>broood: [ 1 17 15 0 0 5 ]
Line 1,603 ⟶ 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}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
sub encode {
Line 1,631 ⟶ 1,981:
print "correctly decoded to $decoded\n";
}
</syntaxhighlight>
</lang>
{{out}}
<pre>broood: 1 17 15 0 0 5
Line 1,640 ⟶ 1,990:
correctly decoded to hiphophiphop
</pre>
 
=={{header|Perl 6}}==
=={{header|Phix}}==
{{works with|rakudo|2015-09-24}}
Equivalent longhand versions of the symtab reordering left in as comments
<lang perl6>sub encode ( Str $word ) {
<!--<syntaxhighlight lang="phix">(phixonline)-->
my @sym = 'a' .. 'z';
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
gather for $word.comb -> $c {
<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>
die "Symbol '$c' not found in @sym" if $c eq @sym.none;
<span style="color: #004080;">string</span> <span style="color: #000000;">symtab</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"abcdefghijklmnopqrstuvwxyz"</span>
@sym[0 .. take (@sym ... $c).end] .= rotate(-1);
<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) {
sub decode ( @enc ) {
my @sym$encoded = 'a' .. 'z'array();
[~]for gather($i for= @enc0 ; $i < strlen($original) ->; $posi++) {
take$char @sym= $original[$posi];
@sym[0..$pos]position .= rotatearray_search(-1$char, $symbol);
$encoded[] = $position;
$mtf = $symbol[$position];
unset($symbol[$position]);
array_unshift($symbol, $mtf);
}
return $encoded;
}
 
function mtfDecode($encoded, $symbol) {
use Test;
$decoded = '';
plan 3;
foreach ($encoded AS $position) {
for <broood bananaaa hiphophiphop> -> $word {
my $encchar = encode($word)symbol[$position];
my $decdecoded .= decode($enc)char;
is $word, $dec, "$word.fmt('%-12s') unset($encsymbol[$position])";
array_unshift($symbol, $char);
}</lang>
}
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
<pre>1..3
bananaaa -> [1,1,13,1,1,1,0,0] -> bananaaa : OK
ok 1 - broood (1 17 15 0 0 5)
hiphophiphop -> [7,8,15,2,15,2,2,3,2,2,3,2] -> hiphophiphop : OK</pre>
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|PhixPicat}}==
Picat has 1-based index so some adjustments was necessary.
<lang Phix>function encode(string s)
<syntaxhighlight lang="picat">import util.
string symtab = "abcdefghijklmnopqrstuvwxyz"
sequence res = {}
for i=1 to length(s) do
integer ch = s[i]
integer k = find(ch,symtab)
res &= k-1
for j=k to 2 by -1 do
symtab[j] = symtab[j-1]
end for
symtab[1] = ch
end for
return res
end function
 
go =>
function decode(sequence s)
Strings = ["broood", "bananaaa", "hiphophiphop"],
string symtab = "abcdefghijklmnopqrstuvwxyz"
foreach(String in Strings)
string res = ""
check(String)
for i=1 to length(s) do
end,
integer k = s[i]+1
nl.
integer ch = symtab[k]
 
res &= ch
% adjustments to 1-based index
for j=k to 2 by -1 do
encode(String) = [Pos,Table] =>
symtab[j] = symtab[j-1]
Table = "abcdefghijklmnopqrstuvwxyz",
end for
Pos = symtab[1] = ch,
Len = String.length,
end for
foreach({C,I} in zip(String,1..Len))
return res
Pos := Pos ++ [find_first_of(Table,C)-1],
end function
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>
 
procedure test(string s)
sequence e = encode(s)
string d = decode(e)
?{s,e,d,{"**ERROR**","ok"}[(s=d)+1]}
end procedure
test("broood")
test("bananaaa")
test("hiphophiphop")</lang>
{{out}}
<pre>pos = [1,17,15,0,0,5]
<pre>
table = orbacdefghijklmnpqstuvwxyz
{"broood",{1,17,15,0,0,5},"broood","ok"}
string2 = broood
{"bananaaa",{1,1,13,1,1,1,0,0},"bananaaa","ok"}
same
{"hiphophiphop",{7,8,15,2,15,2,2,3,2,2,3,2},"hiphophiphop","ok"}
 
</pre>
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}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de encode (Str)
(let Table (chop "abcdefghijklmnopqrstuvwxyz")
(mapcar
Line 1,736 ⟶ 2,175:
(get Table (inc 'N))
(rot Table N) ) )
Lst ) ) ) )</langsyntaxhighlight>
Test:
<langsyntaxhighlight PicoLisplang="picolisp">(test (1 17 15 0 0 5)
(encode "broood") )
(test "broood"
Line 1,751 ⟶ 2,190:
(encode "hiphophiphop") )
(test "hiphophiphop"
(decode (7 8 15 2 15 2 2 3 2 2 3 2)) )</langsyntaxhighlight>
 
=={{header|PL/I}}==
<langsyntaxhighlight lang="pli">*process source attributes xref or(!);
/*********************************************************************
* 25.5.2014 Walter Pachl translated from REXX
Line 1,793 ⟶ 2,232:
Else
Put Skip List('all wrong!!');
End;</langsyntaxhighlight>
{{out}}
<pre> in=broood
Line 1,814 ⟶ 2,253:
 
=={{header|PowerShell}}==
<langsyntaxhighlight PowerShelllang="powershell">Function Test-MTF
{
[CmdletBinding()]
Line 1,888 ⟶ 2,327:
}
End{}
}</langsyntaxhighlight>
 
{{out}}
Line 1,904 ⟶ 2,343:
 
===Python: Procedural===
<langsyntaxhighlight lang="python">from __future__ import print_function
from string import ascii_lowercase
 
Line 1,931 ⟶ 2,370:
decode = move2front_decode(encode, SYMBOLTABLE)
print('which decodes back to %r' % decode)
assert s == decode, 'Whoops!'</langsyntaxhighlight>
 
{{out}}
Line 1,942 ⟶ 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.
 
<langsyntaxhighlight lang="python">def m2f_e(s, st):
return [[st.index(ch), st.insert(0, st.pop(st.index(ch)))][0] for ch in s]
 
Line 1,954 ⟶ 2,393:
decode = m2f_d(encode, ST[::])
print('decodes back to %r' % decode)
assert s == decode, 'Whoops!'</langsyntaxhighlight>
 
{{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}}==
<langsyntaxhighlight lang="racket">#lang racket
(define default-symtab "abcdefghijklmnopqrstuvwxyz")
 
Line 2,004 ⟶ 2,490:
(printf "~s encodes to ~s, which decodes ~s to ~s.~%" str enc crt dec))
(for-each encode+decode-string '("broood" "bananaaa" "hiphophiphop")))</langsyntaxhighlight>
 
{{out}}
Line 2,010 ⟶ 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===
<langsyntaxhighlight lang="rexx">/* REXX ***************************************************************
* 25.05.2014 Walter Pachl
* REXX strings start with position 1
Line 2,048 ⟶ 2,566:
Say 'all wrong!!'
Return
</syntaxhighlight>
</lang>
{{out}}
<pre> in=broood
Line 2,070 ⟶ 2,588:
===version 2===
Programming note: &nbsp; the two REXX statements that add/subtract &nbsp; <big> '''one''' </big>&nbsp; deal with the task's requirement that the symbol table be &nbsp; ''zero-indexed'' &nbsp; (the REXX language uses &nbsp; ''unity-based'' &nbsp; strings).
<langsyntaxhighlight lang="rexx">/*REXX program demonstrates the move─to─front algorithm encode/decode symbol table. */
parse arg xxx; if xxx='' then xxx= 'broood bananaaa hiphophiphop' /*use the default?*/
one=1 1 /*(offset) for this task's requirement.*/
do j=1 for words(xxx); x= word(xxx, j) /*process a single word at a time. */
@= 'abcdefghijklmnopqrstuvwxyz'; @@=@ @ /*symbol table: the lowercase alphabet */
$= /*set the decode string to a null. */
do k=1 for length(x); z= substr(x, k, 1) /*encrypt a symbol in the word. */
_= pos(z, @); if _==0 then iterate /*the symbol position in symbol table. */
$= $ (_ - one); @= z || delstr(@, _, 1) /*(re─)adjust the symbol table string. */
end /*k*/ /* [↑] the move─to─front encoding. */
!= /*set the encode string to a null. */
do m=1 for words($); n= word($, m) + one /*decode the sequence table string. */
y= substr(@@, n, 1); != ! || y /*the decode symbol for the N word.*/
@@= y || delstr(@@, n, 1) /*rebuild the symbol table string. */
end /*m*/ /* [↑] the move─to─front decoding. */
say ' word: ' left(x, 20) "encoding:" left($, 35) word('wrong OK', 1 + (!==x) )
end /*j*/ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text=&nbsp; 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}}==
<langsyntaxhighlight lang="ring">
# Project : Move-to-front algorithm
 
Line 2,135 ⟶ 2,653:
d = decode(e)
see "" + s + " => " + "(" + right(e, len(e) - 1) + ") " + " => " + substr(d, " ", "") + nl
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,145 ⟶ 2,663:
=={{header|Ruby}}==
Use a module as namespace:
<langsyntaxhighlight lang="ruby">module MoveToFront
ABC = ("a".."z").to_a.freeze
Line 2,174 ⟶ 2,692:
['broood', 'bananaaa', 'hiphophiphop'].each do |word|
p word == MoveToFront.decode(p MoveToFront.encode(p word))
end</langsyntaxhighlight>
 
{{out}}
Line 2,191 ⟶ 2,709:
=={{header|Rust}}==
 
<langsyntaxhighlight lang="rust">fn main() {
let examples = vec!["broood", "bananaaa", "hiphophiphop"];
for example in examples {
Line 2,234 ⟶ 2,752:
.map(|c| c as char)
.collect()
}</langsyntaxhighlight>
 
{{out}}
Line 2,245 ⟶ 2,763:
=={{header|Scala}}==
{{works with|Scala|2.11.8+}}
<langsyntaxhighlight lang="scala">package rosetta
 
import scala.annotation.tailrec
Line 2,341 ⟶ 2,859:
MoveToFront.test("bananaaa", symTable)
MoveToFront.test("hiphophiphop", symTable)
}</langsyntaxhighlight>
{{out}}
<pre>broood: List(1, 17, 15, 0, 0, 5)
Line 2,353 ⟶ 2,871:
{{trans|Perl}}
Implemented using regular expressions:
<langsyntaxhighlight lang="ruby">func encode(str) {
var table = ('a'..'z' -> join);
str.chars.map { |c|
Line 2,377 ⟶ 2,895:
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}</langsyntaxhighlight>
 
Alternatively, implemented as a module, using arrays:
<langsyntaxhighlight lang="ruby">module MoveToFront {
 
define ABC = @("a".."z")
Line 2,415 ⟶ 2,933:
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}</langsyntaxhighlight>
 
{{out}}
Line 2,428 ⟶ 2,946:
 
=={{header|Swift}}==
<langsyntaxhighlight lang="swift">
 
var str="broood"
Line 2,499 ⟶ 3,017:
print(encarr)
print(decarr)
</syntaxhighlight>
</lang>
 
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
oo::class create MoveToFront {
Line 2,541 ⟶ 3,059:
puts [format "'%s' encodes to %s. This decodes to '%s'. %s" \
$tester $enc $dec [expr {$tester eq $dec ? "Correct!" : "WRONG!"}]]
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,550 ⟶ 3,068:
 
=={{header|VBScript}}==
<langsyntaxhighlight lang="vb">Function mtf_encode(s)
'create the array list and populate it with the initial symbol position
Set symbol_table = CreateObject("System.Collections.ArrayList")
Line 2,598 ⟶ 3,116:
mtf_decode(mtf_encode(word)) & "."
WScript.StdOut.WriteBlankLines(1)
Next</langsyntaxhighlight>
 
{{Out}}
Line 2,605 ⟶ 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}}==
<langsyntaxhighlight lang="zkl">fcn encode(text){ //-->List
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;
}</langsyntaxhighlight>
Strings are immutable so we create a bit bucket (which is mutable) to hold the symbol table which can then be modified in place.
<langsyntaxhighlight lang="zkl">fcn decode(list){ //-->String
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();
}</langsyntaxhighlight>
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).
<langsyntaxhighlight lang="zkl">texts:=T("broood","bananaaa","hiphophiphop");
out:=texts.apply(encode);
texts.zipWith(fcn(t,e){ println(t,"-->",e) },out);
 
out.apply(decode).println();
texts.zipWith('==,out.apply(decode)).println();</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/247166...352476"