# 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 Speed prior explanations.  These incorporate a Turing machine and a
#desc runtime limit, and they present methods for running subject to
#desc the time limit and for
#desc computing the complexity.
from animate import default_animation
from turing_tape import tape_tuple, make_tape, tape_nth
from machine import empty_tape
import bits
import machine
import compile
import compile_and_run
from mpmath import mpf
# A speed prior explanation.
class Speed_prior(object):
    __slots__ = ["logtime", "__size", "program", "statemap"]
    # logtime is the logarithm of the run time limit.
    # size is the length of the program, not the size of the hypothesis
    # (which would be the length of the program plus logtime).
    # FIXME We have a size parameter but __repr__ prints a
    # program_length parameter. We have a program_length method.  Confusing.
    def __init__(self, logtime, program = None, program_length = None,
                 absyn = None):
        if program is None:
            assert absyn is not None
            compiled = compile.turing_compile(absyn)
            program = compiled.program
            self.statemap = compiled.statemap
        else:
            self.statemap = None
        # Fail if the program can't be converted to a long.  Once I
        # passed in the abstract syntax of a program instead.
        program = long(program)
        self.logtime = logtime
        if program_length is None:
            # Compute the size ourselves.
            program_length = 0;
            while (1L << program_length) < program:
                program_length += 1
        self.__size = program_length
        # Fail if the caller gave us a program_length that is too small.
        assert program < (1L << program_length)
        self.program = program 
    def __repr__(self):
        # This doesn't print statemap.  Statemap seems big and uninteresting.
        return "Speed_prior(logtime=%r, program_length=%r, program=%r)" % (
            self.logtime, self.program_length(), self.program)
    def __cmp__(self, other):
        if self.__class__ != other.__class__:
            return -1
        else:
            return cmp((self.logtime, self.__size, self.program),
                       (other.logtime, other.__size, other.program))
    #def simplicity(self):
    #    return self.logtime + 2 * self.__size
    def measure(self):
        return mpf(2.0) ** (- (self.logtime + 2 * self.__size))
    # size returns the size of the explanation for the purposes of
    # enumerating explanations by increasing size.  It's not the
    # length of the program (use self.program_length() for that) and
    # it's not the simplicity (use self.simplicity() for that).
    def size(self):
        return self.logtime + self.__size
    # generator(n) returns speed prior explanations with exactly the
    # given size.
    def generator(n):
        result = []
        for time in range(0, n+1):        
            result.extend([Speed_prior(logtime=time, program_length=n-time,
                                       program=program)
                           for program in bits.exact_bits(n-time)])
        return result
    generator = staticmethod(generator)
    def program_length(self):
        return self.__size
    def is_prefix(self, other):
        # Say whether self is a prefix of other.
        return self.program_length() <= other.program_length() and \
               self.logtime <= other.logtime and \
               self.program == other.program & ((1L << self.__size) - 1)
    # Run, given a value, and return a value.
    def run(self, tape, animate=False):
        steps = 1L<<self.logtime
        if animate:
            if self.statemap:
                animator = compile_and_run.animator(self.statemap)
            else:
                animator = default_animation
            return machine.turing(self.program, tape, steps, animate=animator)
        return machine.turing(self.program, tape, steps)
    # The following methods are here so we can take a subclass to
    # implement a Speed_prior with Python code substituted for the
    # Turing machine.

    # build_tuple builds a list of values to pass to run, if we want
    # to pass values.
    def build_tuple(self, *values):
        return tape_tuple(*values)
    # Extract the nth value from the result of run, assuming it
    # returned a tuple of values.
    def nth(self, value, n):
        return tape_nth(value, n)
    def value_to_num(self, value):
        return value.bits
    def num_to_value(self, num):
        return make_tape(num)
    def null_value(self):
        return machine.empty_tape

def prefix_in(list, explanation):
    # Say whether the explanation has a prefix in the given list.
    for l in list:
        if l.is_prefix(explanation):
            return True
    return False