# 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 A warm-up exercise in writing a decision procedure that
#desc could in principle extrapolate future frames of video based on
#desc past frames.
import machine
from bits import many_bits, ensure
from speed_prior import Speed_prior
import physics
from physics import Speed_prior_explanation, Generic_physics_problem

class Generic_video_prediction_explanation(Speed_prior_explanation):
    def __init__(self, physics=None, perception=None, explanations=None,
                 name="Unnamed"):
        if explanations is None:
            explanations = [physics, perception]
        Speed_prior_explanation.__init__(self, explanations=explanations,
                                         name=name)
    def physics(self): return self.explanations[0]
    def perception(self): return self.explanations[1]

class Video_prediction_explanation(Generic_video_prediction_explanation):
    # Return the first framecount frames from the given world-model
    # candidate, or None if the explanation makes no prediction.
    # If we had requirements on the syntax of a frame of video, we'd
    # enforce them here by making run_physics return None if the syntax
    # doesn't fit.
    def run_physics(self, framecount):
        p = self.physics()
        state = p.run(p.null_value())
        result = []
        for i in range(0, framecount):
            frame = self.perception().run(state)
            result.append(frame)
            state = self.physics().run(state)
        return result
    def extrapolated_frame(self, frameno):
        # Return the frameno'th frame from the physical evolution for
        # the current explanation.
        l = self.run_physics(frameno+1)
        return l[frameno]

class Video_prediction_problem(Generic_physics_problem):
    def __init__(self, video):
        Generic_physics_problem.__init__(
            self, explanation_class=Video_prediction_explanation)
        # Video is an array of video frames.
        self.video = video
    def matches(self, explanation):
        l = explanation.run_physics(len(self.video)+1)
        ensure(l[0:len(self.video)] == self.video)

# For example, we can try to find the most likely next frame of video,
# assuming that the speed prior is the right probability distribution
# for the possible laws of physics.
# eps is the probability of the possibilities we ignore.

# If there are multiple frames with about the same total probability,
# and those probabilities differ by less than eps, then the laws of
# physics we ignored might have determined the most probable one and
# therefore we might return the wrong frame.
def next_frame(video, eps = 0.000001,
               # Pass in a non-default problem_class for unit testing.
               problem_class = Video_prediction_problem):
    problem = problem_class(video)
    # frames maps each potential frame to its estimated probability.
    frames={}
    for explanation in physics.laws_of_physics(problem, eps):
        frame = explanation.extrapolated_frame(len(video))
        if frame not in frames:
            frames[frame] = 0
        frames[frame] += explanation.measure()
    # Now pick the most probable.
    result = None
    for frame in frames:
        if result is None or frames[frame] > frames[result]:
            result = frame
    return result