/* 

  Move to front algorithm (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Move-to-front_algorithm
  """
  Given a symbol table of a zero-indexed array of all possible input symbols 
  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 useful in some compression algorithms.

  Encoding algorithm

    for each symbol of the input sequence:
        output the index of the symbol in the symbol table
        move that symbol to the front of the symbol table

  Decoding algorithm

    # Using the same starting symbol table
    for each index of the input sequence:
        output the symbol at that index of the symbol table
        move that symbol to the front of the symbol table

  Example

  Encoding the string of character symbols 'broood' using a symbol table of the 
  characters 'a'-to-'z'
  Input 	Output 	SymbolTable
  broood 	1 	'abcdefghijklmnopqrstuvwxyz'
  broood 	1 17 	'bacdefghijklmnopqrstuvwxyz'
  broood 	1 17 15 	'rbacdefghijklmnopqstuvwxyz'
  broood 	1 17 15 0 	'orbacdefghijklmnpqstuvwxyz'
  broood 	1 17 15 0 0 	'orbacdefghijklmnpqstuvwxyz'
  broood 	1 17 15 0 0 5 	'orbacdefghijklmnpqstuvwxyz'

  Decoding the indices back to the original symbol order:
  Input 	Output 	SymbolTable
  1 17 15 0 0 5 	b 	'abcdefghijklmnopqrstuvwxyz'
  1 17 15 0 0 5 	br 	'bacdefghijklmnopqrstuvwxyz'
  1 17 15 0 0 5 	bro 	'rbacdefghijklmnopqstuvwxyz'
  1 17 15 0 0 5 	broo 	'orbacdefghijklmnpqstuvwxyz'
  1 17 15 0 0 5 	brooo 	'orbacdefghijklmnpqstuvwxyz'
  1 17 15 0 0 5 	broood 	'orbacdefghijklmnpqstuvwxyz'

  Task

    - Encode and decode the following three strings of characters using the symbol 
      table of the 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. 

  The strings are: 'broood', 'bananaaa', and 'hiphophiphop'. (Note the spellings). 

  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import util.


main => go.


go =>
  Strings = ["broood", "bananaaa", "hiphophiphop","kjellerstrand","zbmcfkukwmeogkhgkspansqgytihgwudpevgaelx"],
  foreach(String in Strings) 
    check(String)
  end,
  nl.

% testing larger instances
go2 =>
  Table = "abcdefghijklmnopqrstuvwxyz",
  Len = Table.length,
  N = 5000,
  String = [Table[1 + random2() mod Len]  : _ in 1..N],
  check(String),
  nl.

% Note: we must adjust for 0-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),
    % alternative
    % once(select(C,Table,Rest)),
    % Table := [C] ++ Rest,
    String := String ++ [C]
  end.
  

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.