import collections


def average_headway_over_time(aggregated_headways, start_time, end_time):
    """
    Given a continuous headway dicts (from aggregate_headways_with_time) and
    a start_time and end_time included in its time range, returns the
    average headway over the given duration.

    :param aggregated_headways:(dict of start times and headways
        {start time: headway}
        Example: {0: 0, 21600: 1800.0, 36000: 0, 64800: 1800.0, 79200: 0}
    :param start_time: (int) start_time to compute avg headway, in gtfs format.
        It must be greater than the min time in aggregated_headways
    :param end_time: (int) end_time to compute avg headway, in gtfs format.
        If it is greater than the max time in aggregated headways, the function
        will assume the last headways is valid until the given end_time.

    :returns: (int) the average headway

    Examples :
    average_headway_over_time({21600: 1800.0, 36000: 0}, 21600, 28800)
        --> returns 1800
    average_headway_over_time({21600: 1800.0, 36000: 0}, 21600, 72000)
        --> assumes the 0 headway is valid in the range 36000-72000 and returns
            therefore ((36000-21600)*1800 + (72000-36000)*0)/(72000-21600)
    """
    # Create reduced time intervals
    new_intervals = [time for time in aggregated_headways.keys()
                     if time > start_time and time < end_time]
    new_intervals = new_intervals + [start_time, end_time]
    new_intervals = sorted(set(new_intervals))
    # Create a reduced headway aggregate over the given time range
    reduced_aggregated_headways = {}
    for time in new_intervals:
        if time in aggregated_headways.keys():
            # if time is an already existing key we take its headway value
            reduced_aggregated_headways[time] = aggregated_headways[time]
        else:
            # Otherwise we take the headway of the interval it is in
            keys = sorted(list(aggregated_headways.keys()))
            headway_found = False
            for i in range(len(keys) - 1):
                if time > keys[i]\
                        and time < keys[i + 1]:
                    reduced_aggregated_headways[
                        time] = aggregated_headways[keys[i]]
                    headway_found = True
                    break
            if not headway_found:
                reduced_aggregated_headways[
                    time] = aggregated_headways[keys[-1]]

    # dict sort
    reduced_aggregated_headways = collections.OrderedDict(
        sorted(reduced_aggregated_headways.items()))
    # Now we compute the average value
    nb_trips = 0
    keys = list(reduced_aggregated_headways.keys())
    for i in range(len(reduced_aggregated_headways) - 1):
        if reduced_aggregated_headways[keys[i]]:
            nb_trips += (keys[i + 1] - keys[i]) / \
                reduced_aggregated_headways[keys[i]]
    if nb_trips > 0:
        averaged_headway = (end_time - start_time) / nb_trips
    else:
        averaged_headway = 0
    return round(averaged_headway)