#!/usr/bin/python

""" Rational Street Performer Protocol round calculator

    To use this module, first create a list of Pledge objects. Pass this list
    to "solve" to find the maximum that can be raised. Given this maximum,
    individual donations can be calculated with the Pledge.donation_given
    method.
    
    See the end of the file for an example.

    The Pledge class defines a simple bounded linear pledge, but other
    pledge curves are possible. To define your own pledge curve, make
    a class with "upper_bound" and "donation_given" methods. A pledge curve
    in this implementation must be monotonically increasing (but it would
    be fairly straightforward to remove this constraint).
"""

__version__ = "0.1"


class Pledge:
    """ Represent a conditional pledge of form
        
	I will donate one dollar in every <dollar_in_every> raised
	over <must_raise_over>, up to a total donation of <upper_bound> """

    def __init__(self, name, must_raise_over, dollar_in_every, upper_bound):
        self._name = name
        self._must_raise_over = must_raise_over
        self._dollar_in_every = dollar_in_every
        self._upper_bound = upper_bound

    def name(self):
        return self._name

    def upper_bound(self):
        """ What is the most that I would ever pay? """
        return self._upper_bound

    def donation_given(self, total):
        """ Given that the total raised is <total>, how much am I willing to
	    pay? """

	donation = (total - self._must_raise_over) / self._dollar_in_every
	if donation < 0.0:
	    return 0.0
	elif donation > self._upper_bound:
	    return self._upper_bound
	else:
	    return donation

def _solve_range(list, lower_bound, upper_bound, accuracy):
    """ Find the maximum solution for the pledges given in <list> within the
        range <lower_bound, upper_bound>.

	If there is no solution, return 0.0 """

    # What would be raised, given the upper bound?
    total = 0.0
    for item in list:
        total = total + item.donation_given(upper_bound)

    # Is the upper bound itself a solution?
    if total >= upper_bound:
	return total

    # Is a solution impossible within this range?
    # Have we reached the desired accuracy and not found a solution?
    if total < lower_bound or upper_bound - lower_bound < accuracy:
        return 0.0

    # Is there a solution in the upper half of the range?
    mid_point = (lower_bound + upper_bound) / 2.0
    result = _solve_range(list, mid_point, upper_bound, accuracy)
    if result:
        return result

    # Is there a solution in the lower half of the range?
    return _solve_range(list, lower_bound, mid_point, accuracy)

def solve(list, accuracy=0.0001):
    """ Find the maximum solution for the pledges given in <list>, to a
        given <accuracy>. """
	
    # What is an upper bound on the amount that could be raised?
    max = 0.0
    for item in list:
        max = max + item.upper_bound()

    # Search for a solution within the largest possible range
    return _solve_range(list, 0.0, max, accuracy)

if __name__ == "__main__":
    # Specify a set of pledges
    pledges = [
        # Peter will pay $1 in every $2 raised over $10 up to a maximum of $100
        Pledge("Peter", 10.0, 2.0, 100.0),
	
	Pledge("Robin",  0.0, 3.0, 200.0),
	Pledge("Garry",  10.0, 3.0, 15.0)
    ]

    # Find the total amount raised
    solution = solve(pledges)

    print "Total raised: $%.2f\n" % solution

    # Calculate each donator's contribution
    for item in pledges:
        print item.name(), "pays $%.2f" % item.donation_given(solution)