from datetime import datetime


def find_file_weather_ids(start_ts: datetime, finish_ts: datetime, ordered_weather_ids: tuple,
                          ordered_weather_timestamps: tuple) -> tuple:
    """Finds the minimum and maximum weather timestamps associated with the files start and finish timestamps
    Arguments:
        start_ts: the starting timestamp to look for
        finish_ts: the finishing timestamp to look for
        ordered_weather_ids: the ordered list of weather IDs
        ordered_weather_timestamps: the ordered list of timestamps
    Return:
        A tuple containing the ID of the starting and ending weather timestamps that encompass the file's timestamps
    Notes:
        Assumes the ascending numerical order of weather IDs are directly related to the ascending temporal order of
        the weather timestamp (in other words a larger ID value occurs later than any of the smaller ID values)
    """
    assert len(ordered_weather_ids) == len(ordered_weather_timestamps)

    def b_search(search_timestamp: datetime, ordered_timestamps: tuple) -> tuple:
        """Find the nearest min and max timestamp indexes for the specified search timestamp
        Arguments:
            search_timestamp: the timestamp to look for
            ordered_timestamps: the ordered list of timestamps to search
        Return:
            A tuple containing the min and max indexes encompassing the timestamp
        Notes:
            If a timestamp index can't be found, None is returned in the tuple
        """
        min_index, max_index = None, None

        first_idx = 0
        last_idx = len(ordered_timestamps) - 1

        # Simple cases first (empty tuple, one element tuple)
        if last_idx < first_idx:
            return min_index, max_index
        if first_idx == last_idx:
            if ordered_timestamps[first_idx] == search_timestamp:
                min_index, max_index = first_idx, last_idx
            elif ordered_timestamps[first_idx] < search_timestamp:
                min_index = first_idx
            else:
                max_index = last_idx
            return min_index, max_index

        # Check the cases the loop doesn't handle
        if ordered_timestamps[last_idx] == search_timestamp:
            return last_idx, last_idx
        if ordered_timestamps[last_idx] < search_timestamp:
            return last_idx, None

        # Perform search
        while True:
            mid_idx = int((first_idx + last_idx) / 2)
            if ordered_timestamps[mid_idx] == search_timestamp:
                min_index, max_index = mid_idx, mid_idx
                break
            if ordered_timestamps[mid_idx] < search_timestamp:
                first_idx = mid_idx
            else:
                last_idx = mid_idx
            if last_idx - first_idx <= 1:
                if ordered_timestamps[first_idx] < search_timestamp:
                    min_index = first_idx
                if ordered_timestamps[last_idx] > search_timestamp:
                    max_index = last_idx
                break

        return min_index, max_index

    min_start_index, max_start_index = b_search(start_ts, ordered_weather_timestamps)
    min_finish_index, max_finish_index = b_search(finish_ts, ordered_weather_timestamps)
    if None in (min_start_index, max_start_index, min_finish_index, max_finish_index):
        raise RuntimeError("Unable to find weather associated with file timestamps: %s %s" % (start_ts, finish_ts))
    if min_start_index > min_finish_index:
        raise RuntimeError("Something went horribly wrong finding weather associated with file timestamps: %s %s" % (
            start_ts, finish_ts))

    start_index = min_start_index
    finish_index = max_finish_index
    # Return the closest weather (comment out the next few lines to keep the weather bracketing the timestamp)
    if abs((start_ts - ordered_weather_timestamps[min_start_index]).total_seconds()) > \
            abs((start_ts - ordered_weather_timestamps[max_start_index]).total_seconds()):
        start_index = max_start_index
    if abs((finish_ts - ordered_weather_timestamps[min_finish_index]).total_seconds()) < \
            abs((finish_ts - ordered_weather_timestamps[max_finish_index]).total_seconds()):
        finish_index = min_finish_index

    return ordered_weather_ids[start_index], ordered_weather_ids[finish_index]