% $Id: Generation.oz,v 1.3 2011/04/21 14:51:29 leavens Exp leavens $
% Generations for One-Dimensional Finite Automata
% These are essentially infinitely-sized (sparse) arrays.
% They track the lowest and highest index at which there is a non-zero value.
%
% Generations are represented by records containing a function
% that maps the index to the value at that index:
% <Generation> ::= gen(low: <Int> map: <fun {$ <Int>}: <Cell>> high: <Int>)
% <Cell> ::= 0 | 1
%
% AUTHOR: Gary T. Leavens

declare
fun {MakeGeneration OneList}
   if OneList == nil
   then
      gen(low:0 map: fun {$ N} 0 end high: 1)
   else
      gen(low: {FoldR OneList Min OneList.1}
          map: fun {$ N} if {Member N OneList} then 1 else 0 end end
          high: {FoldR OneList Max OneList.1})
   end
end

fun {FunToGeneration F L H}
   %% REQUIRES L < H
   gen(low: L map: F high: H)
end

fun {Low gen(low: L ...)} L end
fun {High gen(high: H ...)} H end

fun {GetContents gen(map: M ...) N}
   {M N}
end

fun {MapNeighborhoods Generation F}
   %% REQUIRES: Generation is not empty and F is a 3 argument function
   %% that returns an Int
   %% ENSURES: Result is a list what is returned by F on each neighborhood
   {MakeGeneration
    for N in {Low Generation}-2 .. {High Generation}+2 collect: Res
    do
       if {F
           {GetContents Generation N-1}
           {GetContents Generation N}
           {GetContents Generation N+1}
          } == 1
       then {Res N}
       end
    end
   }
end

%% FromString and ToString are approximately inverses
%% So for all Generations G, {FromString {ToString G} {Low G}} == G.
local
   Blank = &  % a blank
   Filled = &*
in
   fun {GetChar Generation N}
      if {GetContents Generation N} == 0
      then Blank else Filled end
   end
   
   fun {ToString Generation}
      {StringSlice Generation {Low Generation} {High Generation}}
   end

   fun {StringSlice Generation L H}
      for N in L .. H collect: Res
      do
         {Res {GetChar Generation N}}
      end
   end

   fun {FromString Str N}
      %% ENSURES: Result is a generation made so that its ToString is Str
      %% and its low index is N
      {MakeGeneration
       for I in 1 .. {Length Str} collect: Ones
       do
          if {Nth Str I} == Filled then {Ones N+I-1} end
       end
      }
   end
end