# 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 Low-level data manipulation.  Mostly bit-picking for Turing machines.

# log2(eps) returns the greatest integer i such that 2 ** i <= eps.
# That is, if l2 is the floating point logarithm to the base 2, then
# log2(eps) = floor(l2(eps))
def log2(eps):
    if eps > 1:
        result = 0
        while (1L << result) < eps:
            result += 1
        return result
    else:
        inveps = 1 / eps;
        result = 0
        while (1L << result) < inveps:
            result += 1
        return -result

def getbits(tapebits, start, length):
    return (tapebits >> start) & ((1 << length) - 1)

def setbit(tapebits, position, value):
    mask = 1L << position
    if value:
        tapebits |= mask
    elif tapebits & mask:
        tapebits -= mask
    return tapebits

def setbits(tape, start, bits):
    return long(tape) | (long(bits) << start)

# Return a sequence of all nonnegative integers with exactly n bits.
# Leading 0's are invisible, so it's the same as returning a sequence
# of all nonnegative integers with n bits or less.
def exact_bits(n):
    return range(0, 1L<<n)

# f should map values to lists.  Return f(v) appended together, for all v in l.
def map_append(f, l):
    result = []
    for v in l:
        result.extend(f(v))
    return result

# max_bits(n, generator) returns a list of all possible (bits,
# explanation) pairs, where bits is the number of the bits of the
# explanation, and 0 <= bits <= n, and the explanation comes from the
# given generator.  This isn't particularly useful in itself, but it
# is used by many_bits.
def max_bits(n, generator):
    def add_bits(i):
        return [(i, explanation) for explanation in generator(i)]
    return map_append(add_bits, range(0, n+1))

# many_bits(n, generators) returns a list of lists of explanations.
# The total complexity of each explanation is n.
# Each list of explanations has the same length as the generators
# list.  Each item in each explanation list will come from the
# corresponding generator.
# Each generator defines a type of explanation; it is required to
# take a bit-complexity and return a list of explanations of that
# complexity.  exactSpeedPrior and exactBits make fine generators.
def many_bits(n, generators):
    assert len(generators) > 0
    if len(generators) == 1:
        result = [[exp] for exp in generators[0](n)]
    else:
        result = []
        for (bitsSoFar, thisExplanation) in max_bits(n, generators[0]):
            for otherExplanations in many_bits(n-bitsSoFar, generators[1:]):
                result.append([thisExplanation]+otherExplanations)
    return result

# We raise Bad_argmax when argmax is given an empty list.
class Bad_argmax(Exception):
    pass

# We raise Ambiguous_argmax when argmax doesn't know which value to return.
class Ambiguous_argmax(Exception):
    def __init__(self, v1, v2, max):
        self.v1 = v1
        self.v2 = v2
        self.max = max
    def __str__(self):
        return "The two values %r and %r both give the maximal result %r" % (
            self.v1, self.v2, self.max)

# Return a value v in l for which f(v) is largest, or raise Bad_argmax
# if l is empty.  If there are multiple such values, it is unspecified
# which one you'll get.

# If paranoid is true, and there is not a unique maximum, raise
# Ambiguous_argmax.  This is good for situations where we are testing.
# The idea here is that a test is buggy if the success of a test
# depends on the unspecified choic of which maximal value to return.
def argmax(f, l, paranoid=False):
    ambiguous = False
    other_best_f = None
    if l == []:
        raise Bad_argmax()
    else:
        result = l[0]
        best_f = f(result)
        for v in l[1:]:
            fv = f(v)
            if fv == best_f:
                ambiguous = True
                other_best_v = v
            if fv > best_f:
                result = v
                best_f = fv
                ambiguous = False
        if ambiguous and paranoid and result != other_best_v:
            raise Ambiguous_argmax(result, other_best_v, best_f)
        return result

# We raise Doesnt_match when we discover that a hypothesis either
# doesn't match the past, or it doesn't predict a future.  It's
# important that exceptions reflecting bugs in the planner, such as
# Bad_argmax and Ambiguous_argmax, are not subclasses of Doesnt_match,
# otherwise the code that searches for a good hypothesis tends to hide
# bugs.
class Doesnt_match(Exception):
    pass

def ensure(b):
    if not b:
        raise Doesnt_match()

# parsebinary("101") == 5.
def parsebinary(s):
    if s == "":
        return 0
    else:
        return long(s, 2)
        
# unparsebinary(5) = "101".  Don't worry about behavior for negative numbers.
def unparsebinary(num):
    assert num >= 0
    if num == 0:
        return "0"
    else:
        result = ""
        while num > 0:
            if num & 1:
                digit = "1"
            else:
                digit = "0"
            result = digit + result
            num = num >> 1
        return result

# Add a (key, value) pair to a dictionary.  Return the new
# dictionary.  Leave the original dictionary unmodified.
def copy_add(d, key, value):
    result = d.copy()
    result[key] = value
    return result

# Make a dictionary that has all the keys and values of both dict1 and
# dict2.  Leave both unmodified.  If there's a conflict, dict2 wins.
def copy_add_all(dict1, dict2):
    result = dict1.copy();
    for k in dict2:
        result[k] = dict2[k]
    return result;