# Copyright (c) 2009 Tim Freeman
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
#
# (This is the standard MIT License, copied from
# http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.)
#desc Turing machine writing exercise.  Given an input tape with bits
#desc abcd, return a tape three times as long with bits 00a00b00c00d.
from compile import turing_program
from constants import left, right, done, truncate, end

# Replace the tape abcd with 00a00b00c00d.
# We need two bookkeeping bits per data bit, one to show where
# the boundaries between the data bits are, and another so whatever
# algorithm we're doing can make comments about the data bits.
# To do this, start by puting abc1d there.
# The rightmost one at position 1 mod 3 marks the right boundary of
# what we've rewritten, and the left end of the tape marks the
# left boundary.
# Then replace xxxz1qyyyyy, where we've interleaved yyyyyy but not
# xxxz or q, with xxx1z00qyyyyyy.
# When we get to the end, searching for the left side of that 1 puts
# us at the end of the tape.  Truncate away the 1 and put a 00 there,
# and we're done.
impossible = (truncate, right, "impossible")

interleave_as = turing_program(
    "start",
    # Special case: if the tape is empty at the start, we are done.
    start={0:(0, left, "initial1"), 1:(1, left, "initial1"), end:done},
    # Loop for shifting left one bit after inserting the initial 1.
    # The saved bit is 0.
    initial0={0:(0, left, "initial0"), 1:(0, left, "initial1"),
              end:(0, left, "scanright")},
    # The saved bit is 1.
    initial1={0:(1, left, "initial0"), 1:(1, left, "initial1"),
              end:(1, left, "scanright")},
    # Go here when things break to increase the chance of noticing
    # bugs.  Preserve what's left on the tape, seeking to the right
    # end and truncate there so we'll fail.
    impossible={0:(0, right, "impossible"),
                1:(1, right, "impossible"),
                end:(truncate, right, "impossible")},
    # We're just past the left end, and we want to be at the right end.
    # We know the tape isn't empty because we took that special case
    # at the start.
    scanright={end:(truncate, right, "scanright_in"),
               (0, 1):impossible},
    # Scanning right, but the head is on the tape somewhere.
    scanright_in={0:(0, right, "scanright_in"),
                  1:(1, right, "scanright_in"),
                  # end must mean past the right end.
                  end:(0, left, "findright_0")},
    # Now we're at the right end.  We want to find the rightmost 1 at a
    # position 1 mod 3 (counting from 0).  Now we're at 0 mod 3.
    findright_0={0:(0, left, "findright_1"),
                 1:(1, left, "findright_1"),
                 end:impossible},
    findright_1={0:(0, left, "findright_2"),
                 # 1 means we found it.
                 1:(0, left, "padqagain"),
                 end:impossible},
    # Everything at 2 mod 3 should be zero.
    findright_2={0:(0, left, "findright_0"),
                 (1, end):impossible},
    # Now we are at xx>x<0qyyyyy.  Put in another 0 and remember x.
    padqagain={0:(0, left, "padq_0"),
               1:(0, left, "padq_1"),
               end:(0, left, "done")},
    # At at x>x<00qyyyyy, shifting the x's left.  The rightmost original x was
    # a 0.  Put the original x there, then tell the shifter to put a 1
    # there.
    padq_0={0:(0, left, "shift_01"),
            1:(0, left, "shift_11"),
            end:(0, left, "shift_1")},
    # Same, but the rightmost original x was a 1.
    padq_1={0:(1, left, "shift_01"),
            1:(1, left, "shift_11"),
            end:(0, left, "shift_1")},
    shift_00={0:(0, left, "shift_00"),
              1:(0, left, "shift_10"),
              end:(0, left, "shift_0")},
    shift_0={(0,1): impossible,
             end:(0, left, "scanright")},
    shift_01={0:(1, left, "shift_00"),
              1:(1, left, "shift_10"),
              end:(1, left, "shift_0")},
    shift_10={0:(0, left, "shift_01"),
              1:(0, left, "shift_11"),
              end:(0, left, "shift_1")},
    shift_1={(0,1): impossible,
             end:(1, left, "scanright")},
    shift_11={0:(1, left, "shift_01"),
              1:(1, left, "shift_11"),
              end:(1, left, "shift_1")},
    # We're done, but we may not be at the left end.  Move the pointer
    # to the left end.  
    done={0: (0, left, "done"),
          1: (1, left, "done"),
          end: done}
    )