Move-to-front algorithm: Difference between revisions

 

;Example:

 

:::::{| class="wikitable" border="1"

 

;Task:

 

<br>

<big> hiphophiphop </big>

 

<br><br>

 

=={{header|Ada}}==

 

 

procedure Move_To_Front is

Encode_Write_Check("bananaaa");

Encode_Write_Check("hiphophiphop");

 

{{out}}

 

=={{header|Aime}}==

{

integer c, e;

}

 

{

integer c, e;

 

al = "abcdefghijklmnopqrstuvwxyz";

l.append(e = al.place(c));

al.delete(e).insert(0, c);

}

 

main(void)

{

 

0;

{{out}}

<pre> 1 17 15 0 0 5: broood

=={{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:

# ; test encode and decode( "zyxwvutsrqponmlkjihgfedcba" ) #

 

{{out}}

<pre>

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

return string

}

loop, parse, testStrings, `,

Output .= A_LoopField "`t" MTF_Encode(A_LoopField) "`t" MTF_Decode(MTF_Encode(A_LoopField)) "`n"

MsgBox % Output

Outputs:<pre>broood 1,17,15,0,0,5 broood

bananaaa 1,1,13,1,1,1,0,0 bananaaa

 

=={{header|Bracmat}}==

= string symboltable

. !arg:(?string.?symboltable)

& test$(broood.!symboltable)

& test$(bananaaa.!symboltable)

 

=={{header|C}}==

#include<stdlib.h>

#include<string.h>

}

return 0;

{{Out}}

<pre>broood : [1 17 15 0 0 5 ]

 

=={{header|C sharp|C#}}==

using System;

using System.Collections.Generic;

}

}

 

=={{header|C++}}==

#include <iostream>

#include <iterator>

return 0;

}

{{out}}

<pre>

 

=={{header|Clojure}}==

 

(defn move-to-front [x xs]

decoded (decode encoded lowercase)]

(println (format "%s encodes to %s which decodes back to %s."

 

{{Out}}

 

=={{header|Common Lisp}}==

 

(defun move-to-front (x xs)

(assert (string= word decoded))

(format T "~s encodes to ~a which decodes back to ~s.~%"

 

{{Out}}

 

=={{header|D}}==

 

ptrdiff_t[] mtfEncoder(in string data) pure nothrow @safe

assert(word == decoded);

}

{{out}}

<pre>'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'

 

=={{header|Elixir}}==

@table Enum.to_list(?a..?z)

IO.inspect enc = MoveToFront.encode(word)

IO.puts "#{word == MoveToFront.decode(enc)}\n"

 

{{out}}

</pre>

 

=={{header|Factor}}==

 

: to-front ( elt seq -- seq' ) over [ remove ] dip prefix ;

 

"broood" "bananaaa" "hiphophiphop"

{{out}}

<pre>

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|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

Next

 

Output:

<pre>

=={{header|Go}}==

{{trans|Python}}

 

import (

}

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

import Data.Maybe (fromJust)

(,) <*> uncurry ((==) . fst) <$> -- Test that ((fst . fst) x) == snd x)

((,) <*> (decode . snd) <$>

{{out}}

<pre>((("broood",[1,17,15,0,0,5]),"broood"),True)

 

Works in both languages:

every writes(s := !A, " -> [") do {

every writes(!(enc := encode(&lcase,s))," ")

procedure reorder(s1,s2,s3)

return s2||s1||s3

 

Sample run:

=={{header|J}}==

 

'seq table'=. y

ndx=.$0

end.

seq

 

Required examples:

 

1 17 15 0 0 5

spindizzy 'bananaaa';'abcdefghijklmnopqrstuvwxyz'

1 1 13 1 1 1 0 0

spindizzy 'hiphophiphop';'abcdefghijklmnopqrstuvwxyz'

 

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;

 

test("hiphophiphop", symTable);

}

{{out}}

<pre>broood: [1, 17, 15, 0, 0, 5]

 

=={{header|JavaScript}}==

var init = {wordAsNumbers: [], charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};

 

console.log(encoded);

console.log("from decoded:");

{{out}}

<pre>from encoded:

=={{header|jq}}==

{{works with|jq|q.4}}

# Output: the encoded string (an array)

def m2f_encode(st):

| [ (.[0] + [ $st[$ix] ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )

| .[0]

'''Example''':

| ("broood", "bananaaa", "hiphophiphop")

| . as $string

| if $string == $decoded then "\($string) => \($encoded) => \($decoded)"

else "INTERNAL ERROR: encoding of \($string) => \($encoded) => \($decoded)"

{{Out}}

broood => [1,17,15,0,0,5] => broood

bananaaa => [1,1,13,1,1,1,0,0] => bananaaa

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

function encode(ch::Char)

r = findfirst(symtable, ch)

@test str == dec

end

 

{{out}}

 

=={{header|Kotlin}}==

 

fun encode(s: String): IntArray {

println(" -> ${if (decoded[i] == strings[i]) "correct" else "incorrect"}")

}

 

{{out}}

 

=={{header|Lua}}==

function getAlphabet ()

local letters = {}

print("Decoded: " .. decode(output))

print()

{{out}}

<pre>Original string: broood

Number pop a number from stack of values, if no number found then raise error.

 

Module CheckIt {

Global All$, nl$

}

CheckIt

 

{{out}}

</pre >

 

 

f[{output_,symList_},next_]:=Module[{index},index=Position[symList,next][[1,1]]-1;

{output~Append~index,Prepend[Delete[symList,index+1],next]}];

{output~Append~index,Prepend[DeleteCases[symList,ToString[index]],index]}];

q=Fold[f2,{{},CharacterRange["a","z"]},p][[1]];

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

 

=={{header|MATLAB}}==

symTable = 'abcdefghijklmnopqrstuvwxyz';

inStr = {'broood' 'bananaaa' 'hiphophiphop'};

symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];

end

{{out}}

<pre>broood: [ 1 17 15 0 0 5 ]

hiphophiphop: [ 7 8 15 2 15 2 2 3 2 2 3 2 ]

correctly decoded to hiphophiphop</pre>

 

=={{header|Perl}}==

use warnings;

sub encode {

print "correctly decoded to $decoded\n";

}

{{out}}

<pre>broood: 1 17 15 0 0 5

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PHP}}==

 

 

function symbolTable() {

' : ', ($original === $decoded ? 'OK' : 'Error'),

PHP_EOL;

 

{{out}}

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|PicoLisp}}==

(let Table (chop "abcdefghijklmnopqrstuvwxyz")

(mapcar

(get Table (inc 'N))

(rot Table N) ) )

Test:

(encode "broood") )

(test "broood"

(encode "hiphophiphop") )

(test "hiphophiphop"

 

=={{header|PL/I}}==

/*********************************************************************

* 25.5.2014 Walter Pachl translated from REXX

Else

Put Skip List('all wrong!!');

{{out}}

<pre> in=broood

 

=={{header|PowerShell}}==

{

[CmdletBinding()]

}

End{}

 

{{out}}

 

===Python: Procedural===

from string import ascii_lowercase

 

decode = move2front_decode(encode, SYMBOLTABLE)

print('which decodes back to %r' % decode)

 

{{out}}

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]

 

decode = m2f_d(encode, ST[::])

print('decodes back to %r' % decode)

 

{{out}}

Similar to that of the procedural version above.

 

=={{header|Racket}}==

(define default-symtab "abcdefghijklmnopqrstuvwxyz")

 

(printf "~s encodes to ~s, which decodes ~s to ~s.~%" str enc crt dec))

 

{{out}}

(formerly Perl 6)

{{works with|rakudo|2015-09-24}}

my @sym = 'a' .. 'z';

gather for $word.comb -> $c {

my $dec = decode($enc);

is $word, $dec, "$word.fmt('%-12s') ($enc[])";

{{out}}

<pre>1..3

=={{header|REXX}}==

===version 1===

* 25.05.2014 Walter Pachl

* REXX strings start with position 1

Say 'all wrong!!'

Return

{{out}}

<pre> in=broood

===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).

parse arg xxx; if xxx='' then xxx= 'broood bananaaa hiphophiphop' /*use the default?*/

$= /*set the decode string to a null. */

end /*k*/ /* [↑] the move─to─front encoding. */

!= /*set the encode string to a null. */

end /*m*/ /* [↑] the move─to─front decoding. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

</pre>

 

=={{header|Ring}}==

# Project : Move-to-front algorithm

 

d = decode(e)

see "" + s + " => " + "(" + right(e, len(e) - 1) + ") " + " => " + substr(d, " ", "") + nl

Output:

<pre>

=={{header|Ruby}}==

Use a module as namespace:

ABC = ("a".."z").to_a.freeze

['broood', 'bananaaa', 'hiphophiphop'].each do |word|

p word == MoveToFront.decode(p MoveToFront.encode(p word))

 

{{out}}

=={{header|Rust}}==

 

let examples = vec!["broood", "bananaaa", "hiphophiphop"];

for example in examples {

.map(|c| c as char)

.collect()

 

{{out}}

=={{header|Scala}}==

{{works with|Scala|2.11.8+}}

 

import scala.annotation.tailrec

MoveToFront.test("bananaaa", symTable)

MoveToFront.test("hiphophiphop", symTable)

{{out}}

<pre>broood: List(1, 17, 15, 0, 0, 5)

{{trans|Perl}}

Implemented using regular expressions:

var table = ('a'..'z' -> join);

str.chars.map { |c|

print "in" if (decoded != test);

say "correctly decoded to #{decoded}";

 

Alternatively, implemented as a module, using arrays:

 

define ABC = @("a".."z")

print "in" if (decoded != test);

say "correctly decoded to #{decoded}";

 

{{out}}

 

=={{header|Swift}}==

 

var str="broood"

print(encarr)

print(decarr)

 

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

oo::class create MoveToFront {

puts [format "'%s' encodes to %s. This decodes to '%s'. %s" \

$tester $enc $dec [expr {$tester eq $dec ? "Correct!" : "WRONG!"}]]

{{out}}

<pre>

 

=={{header|VBScript}}==

'create the array list and populate it with the initial symbol position

Set symbol_table = CreateObject("System.Collections.ArrayList")

mtf_decode(mtf_encode(word)) & "."

WScript.StdOut.WriteBlankLines(1)

 

{{Out}}

{{libheader|Wren-fmt}}

{{libheader|Wren-seq}}

 

var encode = Fn.new { |s|

Fmt.print("$-38n -> $-12s -> $s", a, decoded[i], correct)

i = i + 1

 

{{out}}

 

=={{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();

{{out}}

<pre>