# Copyright (c) 2007 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 The input or output tape of a Turing machine, made into an object
#desc for code readability and so we get errors sooner if we're
#desc passing the wrong data around.  
from bits import setbit, unparsebinary, parsebinary, getbits

class turing_tape(object):
    __slots__=["length", "bits"]
    def __init__(self, length=None, bits=None):
        assert length != None
        assert bits != None
        assert type(length) == int
        assert type(bits) == int or type(bits) == long
        assert bits >= 0
        assert bits < (1L << length)
        self.length = length
        self.bits = bits

    def __cmp__(self, other):
        return cmp((self.length, self.bits), (other.length, other.bits))

    def __hash__(self):
        return hash((self.length, self.bits),)

    def __repr__(self):
        #return "turing_tape(length=%r, bits=%r)" % (self.length, self.bits)
        asbits = unparsebinary(self.bits)
        asbits = ("0" * (self.length - len(asbits))) + asbits
        return "<" + asbits + ">"

    def __str__(self):
        return repr(self)

# binarytape("101") = turing_tape(length=3, bits=5)
def binarytape(s):
    return turing_tape(length=len(s), bits=parsebinary(s))

# interleave_2 takes a tape and returns a new tape twice as long, with
# 0's interleaved at the odd positions with the original bits of the tape.
def interleave_2(tape):
    #(l, b) = tape
    try:
        (l, b) = (tape.length, tape.bits)
    except:
        raise Exception("Couldn't unpack tape %r" % (tape,))
    newb = 0
    for i in range(l):
        newb = setbit(newb, 2*i, getbits(b, i, 1))
    return turing_tape(length=2*l, bits=newb)

# uninterleave_2 is the inverse of interleave_2.
def uninterleave_2(tape):
    (length, b) = (tape.length, tape.bits)
    newb = 0
    for i in range(length >> 1):
        newb = setbit(newb, i, getbits(b, 2*i, 1))
    return turing_tape(length=length>>1, bits=newb)

def tape_concat(t1, t2):
    (l1, b1) = (t1.length, t1.bits)
    (l2, b2) = (t2.length, t2.bits)
    return turing_tape(l1 + l2, (long(b1) << l2) | b2)

# tape_tuple(tape1, tape2, ...) interleaves each tapei with 0's in all
# of the odd positions, then concatenates them inserting a 10 between
# each pair.
def tape_tuple(*args):
    result = interleave_2(args[0])
    for rest in args[1:]:
        result = tape_concat(result, turing_tape(length=2, bits=2))
        result = tape_concat(result, interleave_2(rest))
    return result

# tape_nth(t, n) returns a tape that's the nth value in the tape-tuple t. 
# tape_nth(tape_tuple(*v), n) == v[n], if v is a sequence of tapes and
# n is in bounds.
def tape_nth(tape, n):
    (length, b) = (tape.length, tape.bits)
    start = length-1
    for i in range(n):
        while getbits(b, start, 1) == 0:
            assert start >= 0
            start -= 2
        start -= 2
    end = start
    while end > 0 and getbits(b, end, 1) == 0:
        end -= 2
    return uninterleave_2(turing_tape(length=start - end,
                                      bits=getbits(b, end + 1, start - end)))

# Convert the given integer to a TM tape.
def make_tape(n):
    # Fail if n can't be made into a long.
    n = long(n)
    size = 1
    while (1L << size) < n:
        size += 1
    return turing_tape(length=size, bits=n)