constraints.py

#!/usr/bin/env python3

# Copyright (C) 2020
# ASTRON (Netherlands Institute for Radio Astronomy)
# P.O.Box 2, 7990 AA Dwingeloo, The Netherlands
#
# This file is part of the LOFAR software suite.
# The LOFAR software suite is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
#
# The LOFAR software suite is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with the LOFAR software suite. If not, see <http://www.gnu.org/licenses/>.
#

"""
This module defines the 'API' to:
 - filter a list of schedulable scheduling_units by checking their constraints: see method filter_scheduling_units_using_constraints
 - sort a (possibly filtered) list of schedulable scheduling_units evaluating their constraints and computing a 'fitness' score: see method get_sorted_scheduling_units_scored_by_constraints
These main methods are used in the dynamic_scheduler to pick the next best scheduling unit, and compute the midterm schedule.
"""

from datetime import datetime, timedelta
from dateutil import parser
from typing import Callable, Union, Tuple
from typing import Callable, Union, Tuple, Iterable
from astropy.coordinates import Angle, angular_separation, get_sun
from astropy.coordinates.earth import EarthLocation
import astropy.units
from functools import reduce, lru_cache
from copy import deepcopy
from django.db.models import QuerySet

from lofar.common.datetimeutils import round_to_second_precision
from lofar.sas.tmss.tmss.tmssapp.conversions import *
from lofar.common.util import noop
from lofar.sas.tmss.tmss.tmssapp import models
from lofar.sas.tmss.tmss.exceptions import *
from lofar.sas.tmss.tmss.tmssapp.subtasks import enough_stations_available_for_subtask, get_missing_stations
from lofar.sas.tmss.tmss.tmssapp.tasks import mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable, get_schedulable_stations, enough_stations_available_for_scheduling_unit,enough_stations_available_for_task

import logging
logger = logging.getLogger(__name__)

# rough estimate of how many units and timestamp evaluations can be cached
CACHE_SIZE = 1000 * 24 * 12 * 365

class Gridder:
    VERY_COARSE_TIME_GRID = 60  # minimum accuracy for distance
    COARSE_TIME_GRID = 30   # minimum accuracy for elevation
    DEFAULT_TIME_GRID = 5   # minimum accuracy for daily, transit (tolerance > 5 minutes)
    FINE_TIME_GRID = 1      # minimum accuracy for transit (tolerance <= 5 minutes)
    NO_TIME_GRID = None

    def __init__(self, grid_minutes=DEFAULT_TIME_GRID):
        self.grid_minutes = int(grid_minutes)

    def __str__(self):
        return "Gridder(grid_minutes=%s, n_grid_points=%s)" % (self.grid_minutes, self.n_grid_points())

    def __hash__(self):
        return hash(self.grid_minutes)

    def __eq__(self, other):
        return isinstance(other, Gridder) and self.grid_minutes == other.grid_minutes

    @staticmethod
    def ceil_gridder(minutes: int) -> 'Gridder':
        '''create and return a Gridder for which the grid just bigger than the given minutes.'''
        for grid_minutes in (Gridder.FINE_TIME_GRID, Gridder.DEFAULT_TIME_GRID, Gridder.COARSE_TIME_GRID, Gridder.VERY_COARSE_TIME_GRID):
            if minutes <= grid_minutes:
                return Gridder(grid_minutes)
        return Gridder()

    def n_grid_points(self) -> int:
        # provides an appropriate value for the n_grid_points parameter of astropy methods, reflecting an accuracy similar to the time grid of this Gridder.
        # According to https://readthedocs.org/projects/astroplan/downloads/pdf/latest/, n_grid_points of
        # - 150 means better than one minute precision (default)
        # - 10 means better than five minute precision
        # A value of 10 however breaks test_can_run_within_timewindow_with_sky_constraints_with_transit_offset_constraint_returns_true_when_met
        # because the calculated transit_time seems to be quite a bit more than 5 minutes off. So what this returns now is a more conservative
        # guesstimate.
        # todo: figure out how exactly this can be computed properly so that the required precision is always met.
        if self.grid_minutes <= 1:
            return 150
        if self.grid_minutes < 5:
            return 75
        if self.grid_minutes >= 5:
            return 30

    def as_timedelta(self):
        return timedelta(minutes=self.grid_minutes) if self.grid_minutes is not None else None

    def grid_time(self, dt: datetime) -> datetime:
        """
        Rounds a datetime object to the nearest tick on a configurable regular time grid.
        This is supposed to be used when evaluating constraint, so that caching is more effective.
        Checking contraints on a gridded time means that the check outcome may be inaccurate. We assume that this is
        acceptable, given that the difference between checked and real values is marginal and specified constraints
        include a certain margin of safety. This should be good enough at least for the medium or long-term scheduling,
        and a final non-gridded check before actually scheduling a unit can make sure that constraints are actually met.
        :param grid_minutes: Number of minutes between ticks on the time grid. Must be a number with multiple of 60 or a
        multiple of 60. A higher grid_minutes value increases the chance of cache hits, but also of false positive/negative
        results of the  constraints check.
        """
        if self.grid_minutes:
            if 60 % self.grid_minutes not in [0, 60]:
                raise ValueError('Please provide a time grid that has a multiple of 60 or is a multiple of 60')

            timestamp = round(dt.timestamp() / (60*self.grid_minutes)) * (60*self.grid_minutes)   # seconds since epoch, rounded to grid
            return datetime.fromtimestamp(timestamp)
        else:
            return dt

    def plus_margin(self, dt: datetime) -> datetime:
        """
        Adds a 'margin' of half grid_minutes to the given datetime.
        """
        if self.grid_minutes:
            try:
                return dt + timedelta(minutes=0.5*self.grid_minutes)
            except Exception:
                pass
        return dt

    def minus_margin(self, dt: datetime) -> datetime:
        """
        Subtracts a 'margin' of half grid_minutes from the given datetime.
        """
        if self.grid_minutes:
            try:
                return dt - timedelta(minutes=0.5*self.grid_minutes)
            except Exception:
                pass
        return dt

    # todo: add celestial coordinate grid



class SchedulingUnitAndStartTime():
    '''struct combining a scheduling_unit and a (proposed) start_time
    '''
    def __init__(self, scheduling_unit: models.SchedulingUnitBlueprint, start_time: datetime):
        self.scheduling_unit = scheduling_unit
        self.start_time = start_time

    def __str__(self):
        return "SUB id=%s '%s' %s %s start='%s'" % (self.scheduling_unit.id,
                                                    self.scheduling_unit.project.name,
                                                    self.scheduling_unit.priority_queue.value,
                                                    self.scheduling_unit.status.value,
                                                    self.start_time)

class ScoredSchedulingUnit(SchedulingUnitAndStartTime):
    '''struct for collecting scores per constraint for a scheduling_unit at the given start_time
    '''
    def __init__(self, scheduling_unit: models.SchedulingUnitBlueprint, scores: dict, start_time: datetime, weighted_score: float=None):
        for score_key, score_value in scores.items():
            assert score_value >= 0.0 and score_value <= 1.0, "scheduling_unit id=%s score %s=%.3f should be between 0.0 and 1.0" % (scheduling_unit.id, score_key, score_value)
        super().__init__(scheduling_unit, start_time)
        self.scores = scores
        self.weighted_score = weighted_score

    def __str__(self):
        str_weighted_score = "" if self.weighted_score is None else "weighted=%.4f " % (self.weighted_score,)
        return "%s %sscores: %s" % (super().__str__(),
                                    str_weighted_score,
                                    ' '.join(['%s=%.4f' % (key, self.scores[key]) for key in sorted(self.scores.keys())]))


class ConstraintResult():
    '''struct for the results of a constraint evaluation for a scheduling_unit at the given start_time'''
    def __init__(self, scheduling_unit: models.SchedulingUnitBlueprint, constraint_key: str, evaluation_timestamp: datetime, score: float=1.0, earliest_possible_start_time: datetime=None, optimal_start_time: datetime=None, message: str=None):
        self.scheduling_unit = scheduling_unit
        self.constraint_key = constraint_key
        self.evaluation_timestamp = evaluation_timestamp
        self.score = score
        self.earliest_possible_start_time = earliest_possible_start_time
        self.optimal_start_time = optimal_start_time
        self.message = message

    @property
    def is_constraint_met(self) -> bool:
        '''is the constraint met? implicitly we interpret having an earliest_possible_start_time and a score>0 as a yes'''
        return self.earliest_possible_start_time is not None and self.score > 0

    @property
    def has_constraint(self) -> bool:
        '''does the scheduling_unit have a constraint with the given constraint_key?'''
        return self.constraint_value is not None

    @property
    def constraint_value(self):
        '''get the constraint value for the given self.constraint_key from the scheduling_unit constraints doc'''
        try:
            return reduce(dict.get, self.constraint_key.split('.'), self.scheduling_unit.scheduling_constraints_doc or {})
        except:
            return None

    def __str__(self):
        if self.has_constraint:
            return "SUB id=%s constraint %s is %smet at evaluation='%s': score=%.4f earliest_possible='%s' optimal='%s'%s" % (
                   self.scheduling_unit.id,
                   self.constraint_key.ljust(18), # longest constrain_key is 18 chars. printing out many results with this ljust makes the log lines readible like a table.
                   'yes ' if self.is_constraint_met else 'not ', # yes/not are same length for same reason: reading as table in log.
                   self.evaluation_timestamp,
                   self.score,
                   self.earliest_possible_start_time,
                   self.optimal_start_time,
                   (" message='"+self.message+"'") if self.message else '')
        return "SUB id=%s has no '%s' constraint" % (self.scheduling_unit.id, self.constraint_key)


@lru_cache(100, typed=False)
def get_boundary_stations_from_list(stations: Tuple[str]) -> Tuple[str]:
    '''
    utility function to determine the stations at boundary locations. Meant to be used for constraint checks, since when
    constraints are met at these stations, this is typically also true at the other stations.
    Note: There are probably cases where this is not strictly true, but the error is acceptable to us. # todo: is something like geometric distance from core and per quartile a better criterion?
    returns a tuple with the most (northern, eastern, southern, western) station from the input list
    '''
    if not stations:
        return tuple()

    from lofar.common import station_coordinates
    min_lat, max_lat, min_lon, max_lon = None, None, None, None
    for station in stations:
        coords = station_coordinates.parse_station_coordinates()["%sLBA" % station.upper()]
        loc = EarthLocation.from_geocentric(x=coords['x'], y=coords['y'], z=coords['z'],  unit=astropy.units.m)
        if min_lat is None or loc.lat < min_lat:
            min_lat = loc.lat
            most_southern = station
        if max_lat is None or loc.lat > max_lat:
            max_lat = loc.lat
            most_northern = station
        if min_lon is None or loc.lon < min_lon:
            min_lon = loc.lon
            most_western = station
        if max_lon is None or loc.lon > max_lon:
            max_lon = loc.lon
            most_eastern = station
    return most_northern, most_eastern, most_southern, most_western


@lru_cache(100, typed=False)
def get_unique_sorted_boundary_stations_and_cs002(stations: Tuple[str], min_distance: float=None) -> Tuple[str]:
    '''
    Get a tuple of unique boundary stations, and the center core station cs002.
    When min_distance (in meters) is given, then only the boundary stations at least this far apart are returned (and always CS002).
    '''
    result = get_unique_sorted_boundary_stations_or_cs002(stations, min_distance)
    result = set(result) | {'CS002'}
    result = tuple(sorted(list(result)))
    return result


@lru_cache(100, typed=False)
def get_unique_sorted_boundary_stations_or_cs002(stations: Tuple[str], min_distance: float=None) -> Tuple[str]:
    '''
    Get a tuple of unique boundary stations, or just the center core station cs002 if there are no boundary stations within min_distance.
    When min_distance (in meters) is given, then only the boundary stations at least this far apart are returned.
    '''
    boundary_stations = set(get_boundary_stations_from_list(tuple(stations)))
    if min_distance is not None:
        # find EarthLocation for each boundary_station
        from lofar.common import station_coordinates
        locations = {}
        for station in boundary_stations:
            coords = station_coordinates.parse_station_coordinates()["%sLBA" % station.upper()]
            locations[station] = EarthLocation.from_geocentric(x=coords['x'], y=coords['y'], z=coords['z'], unit=astropy.units.m)

        # loop over all station combinations, except (self,self), and compute great-circle-distance in meters between the two
        # when gc-distance is too small, take the station out.
        too_close_stations = set()
        earth_circumference = 40e6 # 40,000km 40,000,000m
        for station1 in boundary_stations:
            location1 = locations[station1]
            for station2 in boundary_stations-too_close_stations:
                if station2 != station1:
                    location2 = locations[station2]
                    seperation = angular_separation(location1.lon, location1.lat, location2.lon, location2.lat)
                    distance = earth_circumference * seperation.value / 6.2832
                    if distance < min_distance:
                        too_close_stations.add(station2)

        # remove all too close stations
        boundary_stations = boundary_stations - too_close_stations

    result = boundary_stations or {'CS002'}
    result = tuple(sorted(list(result)))
    return result


def get_stations_to_be_evaluated(observation_task: models.TaskBlueprint, proposed_start_time: datetime=None, min_distance: float=None):
    '''Get a list of available stations for the given observation_task at the given proposed_start_time (or the task's on_sky_start_time if not given),
    taking the 'location' setting of the task's scheduling_unit's constraints into account (only center, edges, or both)'''
    stations = get_schedulable_stations(observation_task, proposed_start_time or observation_task.on_sky_start_time)
    location = observation_task.scheduling_unit.scheduling_constraints_doc.get('location', 'center')
    if location == 'center':
        stations = ('CS002',)
    elif location == 'edges':
        stations = get_unique_sorted_boundary_stations_or_cs002(stations, min_distance)
    else:
        stations = get_unique_sorted_boundary_stations_and_cs002(stations, min_distance)
    return stations


def fine_enough_gridder(scheduling_unit: models.SchedulingUnitBlueprint, gridder: Gridder) -> Gridder:
    # use the given gridder for "long" observations, use a fine-nough gridder for "short" observations
    main_obs_duration_in_minutes = scheduling_unit.specified_main_observation_duration.total_seconds() / 60.0
    if gridder.grid_minutes > 0.5*main_obs_duration_in_minutes:
        return Gridder.ceil_gridder(0.5*main_obs_duration_in_minutes)
    return gridder


def filter_scheduling_units_using_constraints(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound: datetime, upper_bound: datetime, raise_if_interruped: Callable=noop, gridder: Gridder=None) -> [models.SchedulingUnitBlueprint]:
    """
    Filter the given scheduling_units by whether their constraints are met within the given timewindow.
    :param lower_bound: evaluate and score the constrains at and after lower_bound_start_time. The returned unit has a start_time guaranteed at or after lower_bound_start_time.
    :param upper_bound: evaluate and score the constrains before upper_bound_stop_time. The returned unit has a stop_time guaranteed before upper_bound_stop_time.
    :param scheduling_units: evaluate/filter these scheduling_units.
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    Returns a list scheduling_units for which their constraints are met within the given timewindow.
    """
    _method_start_timestamp = datetime.utcnow()

    if gridder is None:
        gridder = Gridder()

    runnable_scheduling_units = []

    for i, scheduling_unit in enumerate(sorted(scheduling_units, key=lambda x: x.id)):
        raise_if_interruped() # interrupts the scheduling loop

        try:
            # should not happen, these are non-nullable in db
            assert(scheduling_unit.draft is not None)
            assert(scheduling_unit.scheduling_constraints_template is not None)

            unit_gridder = fine_enough_gridder(scheduling_unit, gridder)

            # check constraints and cycle bounds.
            # check reservations only once a starttime for a unit is found
            if can_run_within_cycles_bounds(scheduling_unit, lower_bound, upper_bound):
                if can_run_within_timewindow_with_constraints(scheduling_unit, lower_bound, upper_bound, unit_gridder):
                    runnable_scheduling_units.append(scheduling_unit)

            logger.info("filter_scheduling_units_using_constraints: checked unit [%d/%d] %.1f%% id=%d can %srun in window ['%s', '%s'] project='%s' C/R/I=%s",
                        i+1, len(scheduling_units), 100.0*(i+1)/len(scheduling_units), scheduling_unit.id,
                        'yes ' if scheduling_unit in runnable_scheduling_units else 'not ',
                        lower_bound, upper_bound,
                        scheduling_unit.project,
                        '/'.join(str(q) for q in scheduling_unit.main_observation_task.used_station_counts))
        except Exception as e:
            if isinstance(e, SchedulerInterruptedException):
                raise # bubble up
            else:
                logger.exception(e)
                mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, reason=str(e))

    _method_elapsed = datetime.utcnow() - _method_start_timestamp
    logger.info("filter_scheduling_units_using_constraints: filtered %d units of which %s are runnable between '%s' and '%s' (took %.1f[s])", len(scheduling_units), len(runnable_scheduling_units), lower_bound, upper_bound, _method_elapsed.total_seconds())

    return runnable_scheduling_units


def filter_scheduling_units_using_time_constraints(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound: datetime, upper_bound: datetime, raise_if_interruped: Callable=noop) -> [models.SchedulingUnitBlueprint]:
    """
    Filter the given scheduling_units by whether their time-constraints are met within the given timewindow.
    :param lower_bound: evaluate and score the constrains at and after lower_bound_start_time. The returned unit has a start_time guaranteed at or after lower_bound_start_time.
    :param upper_bound: evaluate and score the constrains before upper_bound_stop_time. The returned unit has a stop_time guaranteed before upper_bound_stop_time.
    :param scheduling_units: evaluate/filter these scheduling_units.
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    Returns a list scheduling_units for which their time-constraints are met within the given timewindow.
    """
    _method_start_timestamp = datetime.utcnow()

    filtered_scheduling_units = []

    for i, scheduling_unit in enumerate(sorted(scheduling_units, key=lambda x: x.id)):
        raise_if_interruped() # interrupts the scheduling loop

        try:
            # should not happen, these are non-nullable in db
            assert(scheduling_unit.draft is not None)
            assert(scheduling_unit.scheduling_constraints_template is not None)

            # check constraints and cycle bounds.
            # check reservations only once a starttime for a unit is found
            if can_run_within_cycles_bounds(scheduling_unit, lower_bound, upper_bound):
                if can_run_between_with_time_constraints(scheduling_unit, lower_bound, upper_bound):
                    filtered_scheduling_units.append(scheduling_unit)

            logger.debug("filter_scheduling_units_using_time_constraints: checked unit [%d/%d] %.1f%% id=%d time-constraints are %smet in window ['%s', '%s'] project='%s' C/R/I=%s",
                        i+1, len(scheduling_units), 100.0*(i+1)/len(scheduling_units), scheduling_unit.id,
                        'yes ' if scheduling_unit in filtered_scheduling_units else 'not ',
                        lower_bound, upper_bound,
                        scheduling_unit.project,
                        '/'.join(str(q) for q in scheduling_unit.main_observation_task.used_station_counts))
        except Exception as e:
            if isinstance(e, SchedulerInterruptedException):
                raise # bubble up
            else:
                logger.exception(e)
                mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, reason=str(e))

    _method_elapsed = datetime.utcnow() - _method_start_timestamp
    logger.info("filter_scheduling_units_using_time_constraints: filtered %d units of which %s meet their time-constraints between '%s' and '%s' (took %.1f[s])", len(scheduling_units), len(filtered_scheduling_units), lower_bound, upper_bound, _method_elapsed.total_seconds())

    return filtered_scheduling_units


def filter_scheduling_units_which_can_only_run_in_this_window(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound: datetime, upper_bound: datetime, raise_if_interruped: Callable=noop, gridder: Gridder=None) -> [models.SchedulingUnitBlueprint]:
    """
    Filter the given scheduling_units and return those which can run exclusively in the given timewindow.
    :param lower_bound: evaluate and score the constrains at and after lower_bound_start_time. The returned unit has a start_time guaranteed at or after lower_bound_start_time.
    :param upper_bound: evaluate and score the constrains before upper_bound_stop_time. The returned unit has a stop_time guaranteed before upper_bound_stop_time.
    :param scheduling_units: evaluate/filter these scheduling_units.
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    Returns a list scheduling_units which can only run in the given timewindow.
    """
    _method_start_timestamp = datetime.utcnow()

    if gridder is None:
        gridder = Gridder()

    runnable_exclusive_in_this_window_scheduling_units = []

    for i, scheduling_unit in enumerate(sorted(scheduling_units, key=lambda x: x.id)):
        raise_if_interruped() # interrupts the scheduling loop

        try:
            unit_gridder = fine_enough_gridder(scheduling_unit, gridder)

            if can_run_within_timewindow_with_constraints(scheduling_unit, lower_bound, upper_bound, gridder=unit_gridder):
                # ok, this unit can run within this window...
                # but can it also run later than this estimated earliest stop_time? If not, then it is exclusively bound to this window

                # what is the earliest_possible_start_time for this unit within this window?
                earliest_possible_start_time = get_earliest_possible_start_time(scheduling_unit, lower_bound=lower_bound, upper_bound=upper_bound, gridder=unit_gridder)
                assert earliest_possible_start_time is not None, "SUB id=%s can run in timewindow [%s, %s] so it should have an earliest_possible_start_time as well" % (scheduling_unit.id, lower_bound, upper_bound)
                earliest_possible_start_time = max(earliest_possible_start_time, lower_bound)
                earliest_possible_start_time = min(earliest_possible_start_time, upper_bound)

                if not can_run_after(scheduling_unit, earliest_possible_start_time, gridder=unit_gridder):
                    if (not can_run_before(scheduling_unit, lower_bound, gridder=unit_gridder) or
                        (lower_bound < datetime.utcnow() + timedelta(minutes=1)) ): # no unit can run before 'now'
                        runnable_exclusive_in_this_window_scheduling_units.append(scheduling_unit)

            logger.debug("filter_scheduling_units_which_can_only_run_in_this_window: checked unit [%d/%d] %.1f%% id=%d can %srun outside of window ['%s', '%s']",
                        i+1, len(scheduling_units), 100.0 *(i+1) / len(scheduling_units), scheduling_unit.id,
                        'not ' if scheduling_unit in runnable_exclusive_in_this_window_scheduling_units else '',
                        lower_bound, upper_bound)

        except Exception as e:
            logger.exception(e)

    _method_elapsed = datetime.utcnow() - _method_start_timestamp
    if runnable_exclusive_in_this_window_scheduling_units:
        logger.info("filter_scheduling_units_which_can_only_run_in_this_window: filtered %d units of which %s are runnable exclusively in window ['%s', '%s'] (took %.1f[s])", len(scheduling_units), len(runnable_exclusive_in_this_window_scheduling_units), lower_bound, upper_bound, _method_elapsed.total_seconds())
    else:
        logger.info("filter_scheduling_units_which_can_only_run_in_this_window: all %d units can run outside of window ['%s', '%s'] (took %.1f[s])", len(scheduling_units), lower_bound, upper_bound, _method_elapsed.total_seconds())

    return runnable_exclusive_in_this_window_scheduling_units


def get_best_scored_scheduling_unit_scored_by_constraints(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound_start_time:datetime, upper_bound_stop_time:datetime, check_reservations: bool=False, coarse_gridder: Gridder=None, fine_gridder: Gridder=None, raise_if_interruped: Callable=noop) -> ScoredSchedulingUnit:
    """
    get the best scored schedulable scheduling_unit which can run withing the given time window from the given scheduling_units.
    :param lower_bound_start_time: evaluate and score the constrains at and after lower_bound_start_time. The returned unit has a start_time guaranteed at or after lower_bound_start_time.
    :param upper_bound_stop_time: evaluate and score the constrains before upper_bound_stop_time. The returned unit has a stop_time guaranteed before upper_bound_stop_time.
    :param scheduling_units: evaluate these scheduling_units.
    :param check_reservations: if True, then filter out scheduling_units which are blocked by reservation(s)
    Returns a ScoredSchedulingUnit struct with the best next schedulable scheduling unit and its proposed start_time where it best fits its contraints.
    """
    _method_start_timestamp = datetime.utcnow()

    if coarse_gridder is None:
        coarse_gridder = Gridder(Gridder.COARSE_TIME_GRID)
    if fine_gridder is None:
        fine_gridder = Gridder(Gridder.FINE_TIME_GRID)

    # First score everything based on coarse grid
    logger.info("get_best_scored_scheduling_unit_scored_by_constraints: scoring and sorting %d units at coarse grid of %s[min]...", len(scheduling_units), coarse_gridder.grid_minutes)
    sorted_scored_scheduling_units_coarse = sort_scheduling_units_scored_by_constraints(scheduling_units, lower_bound_start_time, upper_bound_stop_time, coarse_gridder, raise_if_interruped)

    if sorted_scored_scheduling_units_coarse:
        if logger.level == logging.DEBUG:
            logger.debug("sorted %d scored_scheduling_units at coarse grid of %s[min]:", len(sorted_scored_scheduling_units_coarse), coarse_gridder.grid_minutes)
            for i, scored_scheduling_unit in enumerate(sorted_scored_scheduling_units_coarse):
                logger.debug("  [%03d] %s", i, scored_scheduling_unit)

        # For this coarse-grained evaluated units, we now have a rough estimate of a starttime
        # Distill a top 5 (or less), taking reservations at the rough starttime into account
        # Then re-evaluate the top 5 (or less) with fine grid
        top_sorted_scored_scheduling_units_coarse = [] if check_reservations else sorted_scored_scheduling_units_coarse[:5]
        for i, scored_unit in enumerate(sorted_scored_scheduling_units_coarse):
            runnable = can_run_within_station_reservations(scored_unit.scheduling_unit,
                                                           lower_bound=scored_unit.start_time,
                                                           upper_bound=scored_unit.start_time + scored_unit.scheduling_unit.specified_observation_duration)
            logger.info("  [%03d] can %s run within reservations %s C/R/I=%s", i, 'yes' if runnable else 'not', scored_unit, '/'.join(str(q) for q in scored_unit.scheduling_unit.main_observation_task.used_station_counts))
            if runnable:
                top_sorted_scored_scheduling_units_coarse.append(scored_unit)
                if len(top_sorted_scored_scheduling_units_coarse) >= 5:
                    break

        logger.info("get_best_scored_scheduling_unit_scored_by_constraints: (re)filtering, (re)scoring and sorting %d units at fine grid of %s[min]...", len(top_sorted_scored_scheduling_units_coarse), fine_gridder.grid_minutes)
        top_scheduling_units_coarse = [x.scheduling_unit for x in top_sorted_scored_scheduling_units_coarse]

        # First check if the top5 can also run when evaluated at the fine grid. There may be edge cases.
        top_scheduling_units_fine = filter_scheduling_units_using_constraints(top_scheduling_units_coarse, lower_bound_start_time, upper_bound_stop_time, gridder=fine_gridder, raise_if_interruped=raise_if_interruped)

        # compute the scores at the fine grid
        top_sorted_scored_scheduling_units_fine = sort_scheduling_units_scored_by_constraints(top_scheduling_units_fine, lower_bound_start_time, upper_bound_stop_time, fine_gridder)

        _method_elapsed = datetime.utcnow() - _method_start_timestamp
        logger.debug("get_best_scored_scheduling_unit_scored_by_constraints: scored and sorted %d units (took %.1f[s])", len(scheduling_units), _method_elapsed.total_seconds())

        if top_sorted_scored_scheduling_units_fine:
            logger.info("sorted top %d scored_scheduling_units at fine grid of %s[min]:", len(top_sorted_scored_scheduling_units_fine), fine_gridder.grid_minutes)
            for i, scored_scheduling_unit in enumerate(top_sorted_scored_scheduling_units_fine):
                logger.info("  [%03d] %s", i, scored_scheduling_unit)

            if check_reservations:
                # now that we have a select list of candidates, keep only the ones which are not blocked by a reservation at the computed start_time
                runnable_top_sorted_scored_scheduling_units_fine = [s for s in top_sorted_scored_scheduling_units_fine \
                                                                    if can_run_within_station_reservations(s.scheduling_unit,
                                                                                                           lower_bound=s.start_time,
                                                                                                           upper_bound=s.start_time+s.scheduling_unit.specified_observation_duration)]

                if runnable_top_sorted_scored_scheduling_units_fine:
                    logger.info("top %d runnable_within_reservations scored_scheduling_units at fine grid of %s[min]:", len(runnable_top_sorted_scored_scheduling_units_fine), fine_gridder.grid_minutes)
                    for i, scored_scheduling_unit in enumerate(runnable_top_sorted_scored_scheduling_units_fine):
                        logger.info("  [%03d] %s", i, scored_scheduling_unit)

                    # they are sorted best to worst, so return/use first.
                    best_scored_scheduling_unit = runnable_top_sorted_scored_scheduling_units_fine[0]
                    return best_scored_scheduling_unit
                else:
                    logger.info("0/%d top-scored units can run due to reservations", len(top_sorted_scored_scheduling_units_fine))
            else:
                # they are sorted best to worst, so return/use first.
                best_scored_scheduling_unit = top_sorted_scored_scheduling_units_fine[0]
                return best_scored_scheduling_unit

    return None


def sort_scheduling_units_scored_by_constraints(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound_start_time: datetime, upper_bound_stop_time: datetime, gridder: Gridder, raise_if_interruped: Callable=noop) -> [ScoredSchedulingUnit]:
    """
    Compute the score and proposed start_time for all given scheduling_units. Return them sorted by their weighted_score.
    :param lower_bound_start_time: evaluate and score the constrains at and after lower_bound_start_time. The returned unit has a start_time guaranteed at or after lower_bound_start_time.
    :param upper_bound_stop_time: evaluate and score the constrains before upper_bound_stop_time. The returned unit has a stop_time guaranteed before upper_bound_stop_time.
    :param scheduling_units: evaluate these scheduling_units.
    Returns a list of ScoredSchedulingUnit structs with the score details, a weighted_score and a proposed start_time where it best fits its contraints.
    """

    scored_scheduling_units = compute_start_times_and_scores_for_units(scheduling_units, lower_bound_start_time, upper_bound_stop_time, gridder, raise_if_interruped=raise_if_interruped)

    # filter out unstartable (and thus unsortable) units.
    scored_scheduling_units = [sssu for sssu in scored_scheduling_units if sssu.start_time is not None]

    # sort by weighted_score, then by start_time, then by created at
    return sorted(scored_scheduling_units, key=lambda x: (x.weighted_score,
                                                          (x.start_time-lower_bound_start_time).total_seconds(),
                                                          x.scheduling_unit.created_at), reverse=True)


def can_run_at_within_cycles_bounds(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    '''determine if the given scheduling_unit can run at the proposed_start_time withing the unit's cycle start/end times
    '''
    return can_run_within_cycles_bounds(scheduling_unit,
                                        proposed_start_time+scheduling_unit.relative_observation_start_time,
                                        proposed_start_time+scheduling_unit.relative_observation_stop_time)


def can_run_within_cycles_bounds(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime) -> bool:
    '''determine if the given scheduling_unit can run withing the unit's cycle start/end times for the given timewindow [lower_bound, upper_bound]
    '''
    if scheduling_unit.latest_possible_cycle_stop_time is None or scheduling_unit.earliest_possible_cycle_start_time is None:
        return False

    if upper_bound > scheduling_unit.latest_possible_cycle_stop_time:
        return False

    if lower_bound < scheduling_unit.earliest_possible_cycle_start_time:
        return False

    return True


def can_run_within_timewindow_with_constraints(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> bool:
    '''determine if the given scheduling_unit can run withing the given timewindow evaluating all constraints from the "constraints" version 1 template
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    '''
    if gridder is None:
        gridder = Gridder()

    # use quick and cheap time_constraints as a first order filter.
    if True: #ToDo: check the failing tests. I thinks this new method is correct. For now, just use the expesive method that yields the correct result. can_run_between_with_time_constraints(scheduling_unit, lower_bound, upper_bound):
        # time_constraints are ok. Now test the other constraints.
        # Seek the earliest_possible_start_time. If existing and within window, then the unit can run within this window
        earliest_possible_start_time = get_earliest_possible_start_time(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped)
        if earliest_possible_start_time is not None:
            earliest_possible_stop_time = earliest_possible_start_time + scheduling_unit.specified_observation_duration
            if earliest_possible_start_time >= lower_bound and earliest_possible_stop_time <= upper_bound:
                return True
    return False


def can_run_at(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder=None) -> bool:
    '''determine if the given scheduling_unit can run withing the given timewindow evaluating all constraints from the "constraints" version 1 template
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    '''
    try:
        if gridder is None:
            gridder = Gridder()

        if not can_run_at_within_cycles_bounds(scheduling_unit, proposed_start_time):
            return False

        if not can_run_at_with_time_constraints(scheduling_unit, proposed_start_time):
            return False

        if not can_run_at_with_daily_constraints(scheduling_unit, proposed_start_time, gridder=gridder):
            return False

        if not can_run_at_with_sky_constraints(scheduling_unit, proposed_start_time, gridder=gridder):
            return False

        return True
    except Exception as e:
        logger.error("can_run_at: unit id=%s proposed_start_time='%s' %s", scheduling_unit.id, proposed_start_time, e)
        return False


def can_run_before(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    '''Check if the given scheduling_unit can run somewhere before the given proposed_start_time timestamp depending on the sub's constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time, or is that forbidden by the constraints?
    '''
    logger.debug("can_run_before id=%s, proposed_start_time='%s'...", scheduling_unit.id, proposed_start_time)
    # check all fine-grained can_run_before_with_*_constraints
    # opt for early exit to save time.
    if not can_run_before_with_time_constraints(scheduling_unit, proposed_start_time):
        return False

    if not can_run_before_with_daily_constraints(scheduling_unit, proposed_start_time):
        return False

    if not can_run_before_with_sky_constraints(scheduling_unit, proposed_start_time, gridder):
        return False

    # no constraints above are blocking, so return True.
    return True

def can_run_after(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    '''Check if the given scheduling_unit can run somewhere after the given proposed_start_time timestamp depending on the sub's constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time as well, or is that forbidden by the constraints?
    '''
    # check all fine-grained can_run_after_with_*_constraints
    # opt for early exit to save computations and time.
    if not can_run_after_with_time_constraints(scheduling_unit, proposed_start_time):
        return False

    if not can_run_after_with_daily_constraints(scheduling_unit, proposed_start_time):
        return False

    if not can_run_after_with_sky_constraints(scheduling_unit, proposed_start_time, gridder):
        return False

    # no constraints above are blocking, so return True.
    return True


def can_run_before_with_time_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    '''Check if the given scheduling_unit can run somewhere before the given proposed_start_time timestamp depending on the sub's time-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time, or is that forbidden by the constraints?
    '''
    constraints = scheduling_unit.scheduling_constraints_doc
    if 'time' not in constraints:
        return True

    if 'after' in constraints['time']:
        start_after = parser.parse(constraints['time']['after'], ignoretz=True)
        return proposed_start_time >= start_after

    if 'before' in constraints['time']:
        # the full main observation should be able to complete before the 'before'timestamp
        stop_before = parser.parse(constraints['time']['before'], ignoretz=True)
        latest_possible_start_time = stop_before - scheduling_unit.specified_observation_duration
        return proposed_start_time <= latest_possible_start_time

    if 'at' in constraints['time']:
        at = get_at_constraint_timestamp(scheduling_unit)
        return at <= proposed_start_time

    if 'between' in constraints['time']:
        # loop over all between intervals.
        # exit early when a constraint cannot be met
        for between in constraints['time']['between']:
            start_after = parser.parse(between["from"], ignoretz=True)
            if proposed_start_time < start_after:
                return False

            stop_before = parser.parse(between["to"], ignoretz=True)
            latest_possible_start_time = stop_before - scheduling_unit.specified_observation_duration
            if latest_possible_start_time >= proposed_start_time:
                return False

    if 'not_between' in constraints['time']:
        for not_between in constraints['time']['not_between']:
            raise NotImplemented()

    # no constraint yielded an early False exit,
    # so this unit can run before the proposed start_time
    return True


def can_run_before_with_daily_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    '''Check if the given scheduling_unit can run somewhere before the given proposed_start_time timestamp depending on the sub's daily-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run before the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run before the proposed start_time, or is that forbidden by the constraints?
    '''
    # 'daily' day/night/twilight constraints can always be met before the proposed_start_time,
    # for example one day earlier, or a week earlier, etc.
    return True


def can_run_before_with_sky_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    '''Check if the given scheduling_unit can run somewhere before the given proposed_start_time timestamp depending on the sub's sky-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time, or is that forbidden by the constraints?
    '''
    constraints = scheduling_unit.scheduling_constraints_doc
    if 'sky' not in constraints:
        return True

    # do expensive search from proposed_start_time-24hours until proposed_start_time with half-hour steps
    # (sky constrains are (almost) cyclic over 24 hours).
    earlier_start_time = proposed_start_time - timedelta(hours=24)
    while earlier_start_time < proposed_start_time:
        if can_run_at_with_sky_constraints(scheduling_unit, earlier_start_time, gridder):
            return True
        earlier_start_time += gridder.as_timedelta()
    return False



def can_run_after_with_time_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    '''Check if the given scheduling_unit can run somewhere after the given proposed_start_time timestamp depending on the sub's time-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time as well, or is that forbidden by the constraints?
    '''
    constraints = scheduling_unit.scheduling_constraints_doc
    if 'time' not in constraints:
        return True

    if 'before' in constraints['time']:
        # the full main observation should be able to complete before the 'before'timestamp
        stop_before = parser.parse(constraints['time']['before'], ignoretz=True)
        latest_possible_start_time = stop_before - scheduling_unit.specified_observation_duration
        return proposed_start_time <= latest_possible_start_time

    if 'at' in constraints['time']:
        at = get_at_constraint_timestamp(scheduling_unit)
        return at > proposed_start_time

    if 'between' in constraints['time'] and constraints['time']['between']:
        stop_before = max([parser.parse(between["to"], ignoretz=True) for between in constraints['time']['between']])
        latest_possible_start_time = stop_before - scheduling_unit.specified_observation_duration
        return proposed_start_time < latest_possible_start_time

    return True


def can_run_between_with_time_constraints(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime) -> bool:
    '''Check if the given scheduling_unit can run somewhere between the given lower- and upper_bound depending on the sub's time-constrains-template/doc and its duration.'''
    earliest_possible_start_time = get_earliest_possible_start_time_for_time_constraints(scheduling_unit, lower_bound, upper_bound)
    if earliest_possible_start_time is not None:
        return earliest_possible_start_time >= lower_bound and earliest_possible_start_time < upper_bound-scheduling_unit.specified_observation_duration
    return False


def can_run_after_with_daily_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    '''Check if the given scheduling_unit can run somewhere after the given proposed_start_time timestamp depending on the sub's daily-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time, or is that forbidden by the constraints?
    '''
    # 'daily' day/night/twilight constraints can always be met after the proposed_start_time,
    # for example one day earlier, or a week later, etc.
    return True


def can_run_after_with_sky_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    '''Check if the given scheduling_unit can run somewhere after the given proposed_start_time timestamp depending on the sub's sky-constrains-template/doc and its duration.
    :param scheduling_unit: the scheduling_unit for which we want to check if it can run after the proposed_start_time given its constraints.
    :param proposed_start_time: the proposed start_time for this scheduling_unit. Can it run after the proposed start_time as well, or is that forbidden by the constraints?
    '''
    constraints = scheduling_unit.scheduling_constraints_doc
    if 'sky' not in constraints:
        return True

    # do expensive search from proposed_start_time until 24h later with 15min steps
    # (sky constrains are (almost) cyclic over 24 hours).
    later_start_time = proposed_start_time
    while later_start_time < proposed_start_time + timedelta(hours=24):
        if can_run_at_with_sky_constraints(scheduling_unit, later_start_time, gridder):
            return True
        later_start_time += gridder.as_timedelta()
    return False


def can_run_at_with_time_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime) -> bool:
    """
    Checks whether it is possible to place the scheduling unit arbitrarily in the given time window,
    i.e. the time constraints must be met over the full time window.
    :return: True if all time constraints are met over the entire time window, else False.
    """
    constraints = scheduling_unit.scheduling_constraints_doc

    if not "time" in constraints:
        return True

    can_run_at = True
    can_run_before = True
    can_run_with_after = True
    can_run_between = True
    can_run_not_between = True
    lower_bound = proposed_start_time
    upper_bound = proposed_start_time + scheduling_unit.specified_observation_duration

    if 'at' in constraints['time']:
        at = get_at_constraint_timestamp(scheduling_unit)
        can_run_at = (at >= lower_bound and at + scheduling_unit.specified_observation_duration <= upper_bound)

    # given time window needs to end before constraint
    if 'before' in constraints['time']:
        end_before = parser.parse(constraints['time']['before'], ignoretz=True)
        can_run_before = (upper_bound <= end_before)

    # given time window needs to start after constraint
    if 'after' in constraints['time']:
        after = parser.parse(constraints['time']['after'], ignoretz=True)
        can_run_with_after = (lower_bound >= after)

    # Run within one of these time windows
    if 'between' in constraints['time']:
        can_run_between = True  # empty list is no constraint
        for between in constraints['time']['between']:
            time_from = parser.parse(between["from"], ignoretz=True)
            time_to = parser.parse(between["to"], ignoretz=True)
            if time_from <= lower_bound and time_to >= upper_bound:
                can_run_between = True
                break  # constraint window completely covering the boundary, so True and don't look any further
            else:
                can_run_between = False

    # Do NOT run within any of these time windows
    if 'not_between' in constraints['time']:
        can_run_not_between = True  # empty list is no constraint
        for not_between in constraints['time']['not_between']:
            not_between_from = parser.parse(not_between["from"], ignoretz=True)
            not_between_to = parser.parse(not_between["to"], ignoretz=True)
            if not_between_from < upper_bound and not_between_to > lower_bound:
                can_run_not_between = False
                break  # constraint window at least partially inside the boundary, so False and don't look any further
            else:
                can_run_not_between = True

    return can_run_at & can_run_before & can_run_with_after & can_run_between & can_run_not_between


def can_run_at_with_daily_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    """
    Checks whether it is possible to run the scheduling unit /somewhere/ in the given time window,
    considering the duration of the involved observation.
    :return: True if there is at least one possibility to place the scheduling unit in a way that all time
             constraints are met over the runtime of the observation, else False.
    """
    result = evaluate_daily_constraints(scheduling_unit, proposed_start_time, gridder)
    logger.debug("can_run_at_with_daily_constraints: %s", result)
    if result.has_constraint:
        return result.is_constraint_met
    return True


def can_run_at_with_sky_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> bool:
    """
    Checks whether it is possible to place the scheduling unit arbitrarily in the given time window, i.e. the sky constraints must be met over the full time window.
    :return: True if all sky constraints are met at the proposed_start_time, else False.
    """
    constraints = scheduling_unit.scheduling_constraints_doc
    if "sky" not in constraints:
        return True

    for evaluate_constraint_method in (evaluate_sky_min_elevation_constraint,
                                       evaluate_sky_transit_constraint,
                                       evaluate_sky_min_distance_constraint):
        result = evaluate_constraint_method(scheduling_unit, proposed_start_time, gridder=gridder)
        logger.debug("can_run_at_with_sky_constraints: %s", result)
        if result.has_constraint and not result.is_constraint_met:
            return False

    return True

def get_target_sap_pointings(observation_task: models.TaskBlueprint) -> []:
    ''' get a list of all target pointings (result is an empty list if not a target observation)'''
    if observation_task.is_target_observation and 'station_configuration' in observation_task.specifications_doc:
        # all target and combined target/calibrator observations have a station_configuration entry with SAPs
        return [Pointing(**sap['digital_pointing']) for sap in observation_task.specifications_doc['station_configuration'].get('SAPs', [])]
    return []

def get_calibrator_sap_pointings(observation_task: models.TaskBlueprint) -> []:
    ''' get a list of all calibrator pointings (result is an empty list if not a calibrator observation)'''
    if observation_task.is_calibrator_observation and 'calibrator' in observation_task.specifications_doc:
        return [ Pointing(**observation_task.specifications_doc['calibrator']['pointing']) ]
    return []

def get_transit_offset_reference_pointing(observation_task: Union[models.TaskBlueprint, models.TaskDraft]) -> []:
    ''' return the sky constraints reference pointing if given, else None'''
    constraints = observation_task.scheduling_unit.scheduling_constraints_doc
    if constraints is not None and constraints.get('sky', {}).get('reference_pointing', {}).get('enabled', False):
        return Pointing(**constraints['sky']['reference_pointing']['pointing'])
    return None

def get_transit_offset_pointings(observation_task: models.TaskBlueprint) -> []:
    ''' determine the pointing(s) to use for checking the sky constraints.
        use reference pointing if given, else use all sap pointings '''
    if observation_task.is_target_observation:
        reference_pointing = get_transit_offset_reference_pointing(observation_task)
        if reference_pointing is not None:
            return [reference_pointing]

    # no enabled reference pointing? -> return normal sap pointings
    return get_target_sap_pointings(observation_task)


@lru_cache(10000)
def evaluate_sky_transit_constraint(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder, which: str='nearest') -> ConstraintResult:
    """ Evaluate the sky transit offset constraint: is it met? and what are the score, optimal- and earliest_possible_start_time?
    For this sky transit offset constraint we always compute the optimal_start_time, which is by definition the transit_time.
    If no sky transit offset constraint limits are given, the full +/- 12h limits are used.

    """
    result = ConstraintResult(scheduling_unit, 'sky.transit_offset', proposed_start_time)
    constraints = scheduling_unit.scheduling_constraints_doc
    constraint = constraints.get('sky', {}).get('transit_offset', {})

    # Determine the bounds/limits for the transit_offset constraint.
    # If not given, use default of +/- 12 hours, because transit is 'cyclic' over ~24h periods.
    # With these limits we can compute a score
    transit_from_limit = constraint.get('from', -12 * 60 * 60)
    transit_to_limit = constraint.get('to', +12 * 60 * 60)

    # add margins to take gridding/rounding effects into account
    transit_from_limit_with_margin = transit_from_limit - 60*gridder.grid_minutes
    transit_to_limit_with_margin   = transit_to_limit   + 60*gridder.grid_minutes

    logger.debug("evaluate_sky_transit_constraint: SUB id=%s proposed_start_time='%s'", scheduling_unit.id, proposed_start_time)

    # transits are only computed for target observations
    target_obs_tasks = [t for t in scheduling_unit.observation_tasks if t.is_target_observation]
    for target_obs_task in target_obs_tasks:
        transit_pointings = get_transit_offset_pointings(target_obs_task)
        if not transit_pointings:
            logger.warning("SUB id=%s task id=%s could not determine pointing to evaluate sky transit constraint", scheduling_unit.id, target_obs_task.id)
            result.score = 0
            return result
        elif transit_pointings[0].direction_type not in ['J2000', 'MOON', 'SUN']:
            logger.warning('SUB id=%s task id=%s contains a pointing of unsupported direction_type=%s' % (scheduling_unit.id, target_obs_task.id, transit_pointings[0].direction_type))
            return result

        # since the constraint only applies to the middle of the obs, only consider the proposed_center_time
        # take along the relative_start_time of this task compared to the scheduling unit's start_time
        task_proposed_start_time = proposed_start_time + target_obs_task.relative_start_time
        task_proposed_center_time = round_to_second_precision(task_proposed_start_time + (target_obs_task.specified_duration / 2))

        stations = get_stations_to_be_evaluated(target_obs_task, task_proposed_start_time, 50e4)

        # currently we only check at bounds and center, we probably want to add some more samples in between later on
        for pointing in transit_pointings:
            transits = coordinates_timestamps_and_stations_to_target_transit(pointing=pointing,
                                                                             timestamps=(task_proposed_center_time,),
                                                                             stations=tuple(stations),
                                                                             n_grid_points=gridder.n_grid_points(),
                                                                             which=which)
            for station, transit_timestamps in transits.items():
                assert len(transit_timestamps) == 1 # only one center time
                transit_timestamp = round_to_second_precision(transit_timestamps[0])
                if logger.level==logging.DEBUG:
                    transit_timestamp_lst = local_sidereal_time_for_utc_and_station(transit_timestamp, station)
                    logger.debug("SUB id=%s transit='%sUTC' '%sLST' for %s %s task_proposed_center_time='%s'", scheduling_unit.id, transit_timestamp, transit_timestamp_lst, station, pointing.str_astro(), task_proposed_center_time)

                # transit minus half duration is by definition the optimal start_time
                # also take the task relative start time against the su.starttime into account
                result.optimal_start_time = transit_timestamp - (target_obs_task.specified_duration / 2) - target_obs_task.relative_start_time

                # earliest_possible_start_time is the transit plus the lower limit (which is usually negative)
                result.earliest_possible_start_time = result.optimal_start_time + timedelta(seconds=transit_from_limit)

                # now check if the constraint is met, and compute/set score
                # include the margins for gridding effects when checking offset-within-window,
                # but not when computing score
                offset = int((task_proposed_center_time-transit_timestamp).total_seconds())
                if offset > transit_from_limit_with_margin and offset < transit_to_limit_with_margin:
                    # constraint is met. compute score.
                    # 1.0 when proposed_center_time==transit_timestamp
                    # 0.0 at either translit offset limit
                    if offset <= 0:
                        score = abs(transit_from_limit_with_margin - offset)/abs(transit_from_limit_with_margin)
                    else:
                        score = abs(transit_to_limit_with_margin - offset)/abs(transit_to_limit_with_margin)

                    result.score = min(1.0, max(0.0, score))
                else:
                    result.score = 0
                    result.message = "offset of %s[s] at task_center='%s' from transit at '%s' at %s for %s is not within [%s, %s]" % (offset, task_proposed_center_time, transit_timestamp, station, pointing, transit_from_limit, transit_to_limit)

                    # log and early exit, cause the constraint is not met.
                    logger.debug(result)
                    return result

    return result



@lru_cache(10000)
def evaluate_sky_min_elevation_constraint(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> ConstraintResult:
    """ Evaluate the sky min_elevation constraint: is it met? and what are the score, optimal- and earliest_possible_start_time?
    """
    result = ConstraintResult(scheduling_unit, 'sky.min_elevation', proposed_start_time)
    # for min_elevation there is no optimal start time.
    # any timestamp meeting the constraint is good enough.
    result.optimal_start_time = None

    constraints = scheduling_unit.scheduling_constraints_doc

    if 'sky' not in constraints or 'min_elevation' not in constraints['sky']:
        return result

    for task in scheduling_unit.observation_tasks.all():
        if get_target_sap_pointings(task) and get_target_sap_pointings(task)[0].direction_type not in ['J2000', 'MOON', 'SUN']:
            logger.warning('SUB id=%s task id=%s contains a pointing of unsupported direction_type=%s' % (scheduling_unit.id, task.id, get_target_sap_pointings(task)[0].direction_type))
            return result

        stations = get_stations_to_be_evaluated(task, proposed_start_time, 10e4)

        # determine the min_elevation and stations depending on observation type
        pointings_and_min_elevations = []

        if task.is_target_observation:
            # target imaging, and beamforming or combined observations all use min_elevation.target
            min_elevation = Angle(constraints['sky']['min_elevation']['target'], unit=astropy.units.rad)
            for pointing in get_target_sap_pointings(task):
                pointings_and_min_elevations.append((pointing, min_elevation))

        if task.is_calibrator_observation:
            # calibrator and/or combined observations all use min_elevation.calibrator
            min_elevation = Angle(constraints['sky']['min_elevation']['calibrator'], unit=astropy.units.rad)
            for pointing in get_calibrator_sap_pointings(task):
                pointings_and_min_elevations.append((pointing, min_elevation))

        if not pointings_and_min_elevations:
            logger.warning("SUB id=%s task id=%s could not determine pointing to evaluate sky constraints", scheduling_unit.id, task.id)
            return result

        # evaluate at start/stop/center of observation
        # take along the relative start_time of this task compared to the scheduling unit's start_time
        # currently we only check at bounds and center, we probably want to add some more samples in between later on
        task_proposed_start_time = proposed_start_time + task.relative_start_time
        task_proposed_center_time = task_proposed_start_time + task.specified_duration / 2
        task_proposed_end_time = task_proposed_start_time + task.specified_duration

        # loop over the (unique) gridded timestamps. => Hint, it helps if the grid-spacing is less than the task duration.
        gridded_timestamps = set([gridder.grid_time(t) for t in (task_proposed_start_time, task_proposed_center_time, task_proposed_end_time)])
        for gridded_timestamp in gridded_timestamps:
            for station in stations:
                for pointing, min_elevation in pointings_and_min_elevations:
                    station_target_rise_and_set_times = coordinates_timestamps_and_stations_to_target_rise_and_set(pointing=pointing,
                                                                                                                   timestamps=(gridded_timestamp,),
                                                                                                                   stations=(station,),
                                                                                                                   angle_to_horizon=min_elevation,
                                                                                                                   n_grid_points=gridder.n_grid_points())
                    assert len(station_target_rise_and_set_times) == 1
                    assert station in station_target_rise_and_set_times
                    target_rise_and_set_times = station_target_rise_and_set_times[station]
                    assert len(target_rise_and_set_times) == 1
                    rise_and_set_time = target_rise_and_set_times[0]
                    if rise_and_set_time['rise'] is not None:
                        rise_and_set_time['rise'] = round_to_second_precision(rise_and_set_time['rise'])
                    if rise_and_set_time['set'] is not None:
                        rise_and_set_time['set'] = round_to_second_precision(rise_and_set_time['set'])


                    if rise_and_set_time['always_below_horizon']:
                        # always below horizon -> min_elevation not met.
                        earliest_possible_start_time = None
                    elif rise_and_set_time['always_above_horizon']:
                        # always above horizon -> min_elevation is met
                        earliest_possible_start_time = proposed_start_time
                    else:
                        # when crossing the horizon somewhere,
                        # determine earliest_possible_start_time, even when constraint is not met, which may never be earlier than lower_bound
                        earliest_possible_start_time = rise_and_set_time.get('rise', None) or proposed_start_time

                    # determine latest earliest_possible_start_time over all possibilities in this loop
                    if result.earliest_possible_start_time is None or earliest_possible_start_time is None:
                        result.earliest_possible_start_time = earliest_possible_start_time
                    else:
                        result.earliest_possible_start_time = max(earliest_possible_start_time, result.earliest_possible_start_time)

                    # check if constraint is met...
                    if rise_and_set_time['always_below_horizon'] or rise_and_set_time['always_above_horizon'] or\
                            (rise_and_set_time['rise'] is not None and gridded_timestamp < gridder.minus_margin(rise_and_set_time['rise'])) or \
                            (rise_and_set_time['set'] is not None and gridded_timestamp > gridder.plus_margin(rise_and_set_time['set'])):
                        elevation = compute_elevation(pointing, gridded_timestamp, station)
                        if elevation < min_elevation.rad:
                            # constraint not met. update result, and do early exit.
                            result.score = 0
                            result.evaluation_timestamp = gridded_timestamp
                            result.optimal_start_time = None
                            result.message = "SUB id=%s task_id=%s task_name='%s' station=%s target='%s' elevation=%.3f[deg] < min_elevation=%.3f[deg] at '%s'" % (scheduling_unit.id, task.id, task.name, station, pointing.target, Angle(elevation, astropy.units.rad).deg, min_elevation.degree, gridded_timestamp)
                            logger.debug(result.message)
                            return result

    # if we reached this line, then the constraint is met for all station(s) and all (unique) gridded timestamp(s)
    # as a final check and in order to compute the score, evaluate the constraint again at the actual (gridded) proposed_start_time
    # elevation score range: 0.0 at min_elevation ...  1.0 at zenith (90deg or 1.57rad)
    min_elevation = Angle(constraints['sky']['min_elevation']['target'], unit=astropy.units.rad)
    result.evaluation_timestamp = gridder.grid_time(proposed_start_time)
    lowest_elevation, highest_elevation = get_minmax_elevation_over_stations_and_pointings(scheduling_unit, result.evaluation_timestamp)
    result.score = (lowest_elevation - min_elevation.rad) / (1.57079632679 - min_elevation.rad)
    if result.score <= 0.0:
        # this should hardly ever happen, only on real edge cases due to gridding and rounding. If that's the case, use a finer grid.
        result.score = 0
        result.message = "SUB id=%s task id=%s lowest_elevation=%.3f[deg] < min_elevation=%.3f[deg] at '%s' over all target observations, stations & pointings" % (
                          scheduling_unit.id, task.id,
                          Angle(lowest_elevation, astropy.units.rad).deg, min_elevation.degree, result.evaluation_timestamp)
        logger.debug(result.message)
        return result

    result.score = max(0.001, min(1.0, result.score)) # 0.001 as lowest score, cause 0 means constraint not met.
    logger.debug("SUB id=%s task id=%s lowest_elevation=%.3f[deg] >= min_elevation=%.3f[deg] at '%s' over all target observations, stations & pointings" % (
                  scheduling_unit.id, task.id,
                  Angle(lowest_elevation, astropy.units.rad).deg, min_elevation.degree, result.evaluation_timestamp))
    return result


@lru_cache(maxsize=CACHE_SIZE, typed=False)
def get_minmax_elevation_over_stations_and_pointings(scheduling_unit: models.SchedulingUnitBlueprint, timestamp: datetime) -> (float, float):
    '''Get the lowest and highest elevation at the given timestamp over all pointings and (boundary)stations for the unit's main observation(s).
    Returns: tuple of the lowest and highest elevations in radions.'''
    lowest_elevation = 1e99
    highest_elevation = -1e99
    target_obs_tasks = [t for t in scheduling_unit.observation_tasks if t.is_target_observation]
    for target_obs_task in target_obs_tasks:
        obs_lowest_elevation, obs_highest_elevation = get_minmax_elevation_over_stations_and_pointings_for_observation_task(target_obs_task, timestamp)
        lowest_elevation = min(obs_lowest_elevation, lowest_elevation)
        highest_elevation = max(obs_highest_elevation, highest_elevation)
    return (lowest_elevation, highest_elevation)


@lru_cache(maxsize=CACHE_SIZE, typed=False)
def get_minmax_elevation_over_stations_and_pointings_for_observation_task(obs_task: models.TaskBlueprint, timestamp: datetime, include_reference_pointing: bool=False) -> (float, float):
    '''Get the lowest and highest elevation at the given timestamp over all pointings and (boundary)stations for the observation_task.
    If the observation has a reference_pointing and include_reference_pointing=True, then the reference_pointing is considered as well.
    Returns: tuple of the lowest and highest elevations in radions.'''
    lowest_elevation = 1e99
    highest_elevation = -1e99
    stations = get_stations_to_be_evaluated(obs_task, timestamp, 10e4)
    pointings = get_target_sap_pointings(obs_task)
    if include_reference_pointing:
        reference_pointing = get_transit_offset_reference_pointing(obs_task)
        if reference_pointing:
            pointings.append(reference_pointing)

    for pointing in pointings:
        for station in stations:
            elevation = compute_elevation(pointing, timestamp, station)
            lowest_elevation = min(elevation, lowest_elevation)
            highest_elevation = max(elevation, highest_elevation)
    return (lowest_elevation, highest_elevation)


def get_timestamps_elevations_and_offset_to_transit(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder=None, station='CS002') -> (datetime, datetime, float, float, float, float):
    '''Get the center-of-the-main-observation-timestamp, the nearest transit timestamp, offset (in seconds) and elevations (in radions) for the main observation for the given proposed_start_time
    returns a tuple of (center_timestamp, transit_timestamp, offset_center_to_transit, lowest_elevation, elevation@center, elevation@transit)
    '''
    if proposed_start_time is None:
        proposed_start_time = scheduling_unit.scheduled_start_time

    if proposed_start_time is None: # still none? because scheduling_unit.scheduled_start_time is None
        return None, None, None, None, None, None

    if gridder is None:
        gridder = Gridder(1)

    observer = create_astroplan_observer_for_station(station)

    main_obs_task = scheduling_unit.main_observation_task
    transit_pointings = get_transit_offset_pointings(main_obs_task)

    # take along the relative_start_time of this task compared to the scheduling unit's start_time
    task_proposed_start_time = proposed_start_time + main_obs_task.relative_start_time
    task_proposed_center_time = task_proposed_start_time + main_obs_task.specified_duration / 2
    task_proposed_stop_time = task_proposed_start_time + main_obs_task.specified_duration
    gridded_start_time = gridder.grid_time(task_proposed_start_time)
    gridded_center_time = gridder.grid_time(task_proposed_center_time)
    gridded_stop_time = gridder.grid_time(task_proposed_stop_time)

    # loop over all pointings, and compute the elevations, transits and the offsets_to_transits
    elevations_at_center = []
    elevations_at_transit = []
    transits = []
    offsets_to_transits = []
    lowest_elevation = 1e99
    for pointing in transit_pointings:
        elevation_at_start = compute_elevation(pointing, gridded_start_time, station)
        elevation_at_stop = compute_elevation(pointing, gridded_stop_time, station)
        elevation_at_center = compute_elevation(pointing, gridded_center_time, station)
        elevations_at_center.append(elevation_at_center)
        lowest_elevation = min(elevation_at_start, elevation_at_center, elevation_at_stop, lowest_elevation)

        transit_timestamp = coordinates_timestamp_and_station_to_target_transit(pointing, gridded_center_time, observer, n_grid_points=gridder.n_grid_points())
        transits.append(transit_timestamp)

        offset_to_transits = (task_proposed_center_time - transit_timestamp).total_seconds()
        offsets_to_transits.append(offset_to_transits)

        elevation_at_transit = compute_elevation(pointing, gridder.grid_time(transit_timestamp), station)
        elevations_at_transit.append(elevation_at_transit)

    avg_elevation_at_center = sum(elevations_at_center)/float(len(elevations_at_center))
    avg_elevation_at_transit = sum(elevations_at_transit)/float(len(elevations_at_transit))
    avg_transit_timestamp = task_proposed_start_time + timedelta(seconds=sum([(t-task_proposed_start_time).total_seconds() for t in transits])/float(len(transits)))
    avg_offset_to_transit = sum(offsets_to_transits)/float(len(offsets_to_transits))

    return (task_proposed_center_time, avg_transit_timestamp, avg_offset_to_transit, lowest_elevation, avg_elevation_at_center, avg_elevation_at_transit)


@lru_cache(10000)
def evaluate_sky_min_distance_constraint(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> ConstraintResult:
    """ Evaluate the sky min_distance constraint: is it met? and what are the score, optimal- and earliest_possible_start_time?
    """
    result = ConstraintResult(scheduling_unit, 'sky.min_distance', proposed_start_time)
    constraints = scheduling_unit.scheduling_constraints_doc

    if 'sky' not in constraints or 'min_distance' not in constraints['sky']:
        return result

    # keep track of the smallest actual distance to compute the score
    smallest_actual_distance = 3.1415 # bodies can be at most half a great circle away, which is Pi radians.

    # min_distance constraints are only computed for target observations
    target_obs_tasks = [t for t in scheduling_unit.observation_tasks if t.is_target_observation]
    for target_obs_task in target_obs_tasks:
        sap_pointings = get_target_sap_pointings(target_obs_task)
        if not sap_pointings:
            logger.warning("SUB id=%s task id=%s could not determine pointing(s) to evaluate sky constraints", scheduling_unit.id, target_obs_task.id)
            return result

        # since the constraint only applies to the middle of the obs, only consider the proposed_center_time
        # take along the relative_start_time of this task compared to the scheduling unit's start_time
        task_proposed_start_time = proposed_start_time + target_obs_task.relative_start_time
        task_proposed_center_time = task_proposed_start_time + target_obs_task.specified_duration / 2
        task_proposed_end_time = task_proposed_start_time + target_obs_task.specified_duration
        gridded_timestamps = (gridder.grid_time(task_proposed_start_time),
                              gridder.grid_time(task_proposed_center_time),
                              gridder.grid_time(task_proposed_end_time))

        # currently we only check at bounds and center, we probably want to add some more samples in between later on
        # loop over all bodies and their respective min_distance constraints
        for pointing in sap_pointings:
            for body, min_distance in constraints['sky']['min_distance'].items():
                for gridded_timestamp in gridded_timestamps:
                    distances = coordinates_and_timestamps_to_separation_from_bodies(pointing=pointing,
                                                                                     timestamps=(gridded_timestamp,),
                                                                                     bodies=[body])
                    actual_distances = distances[body]
                    assert (len(actual_distances) == 1)
                    actual_distance = actual_distances[gridded_timestamp]
                    # logger.debug("min_distance: SUB id=%s task_id=%s task_name='%s' pointing='%s' distance=%.3f[deg] to body=%s %s min_distance=%.3f[deg] at '%s'",
                    #              scheduling_unit.id, target_obs_task.id, target_obs_task.name, pointing, actual_distance.degree, body,
                    #              '<' if actual_distance.rad < min_distance else '>=',
                    #              Angle(min_distance, astropy.units.rad).degree,
                    #              gridded_timestamp)

                    # keep track of the smallest actual distance to compute the score
                    smallest_actual_distance = min(smallest_actual_distance, actual_distance.rad)

                    if actual_distance.rad < min_distance:
                        # constraint not met. update result, and do early exit.
                        result.score = 0
                        result.earliest_possible_start_time = None
                        result.optimal_start_time = None
                        result.message = "%s distance=%.3f[deg] to body=%s %s min_distance=%.3f[deg] at '%s'" % (pointing,
                                                                                                                 actual_distance.degree,
                                                                                                                 body,
                                                                                                                 '<' if actual_distance.rad < min_distance else '>=',
                                                                                                                 Angle(min_distance, astropy.units.rad).degree,
                                                                                                                 gridded_timestamp)
                        logger.debug(result)
                        return result
                # no early exit, so constraint is met for this station and timestamp
                # continue with rest of stations & timestamps

        # no early exit, so constraint is met for all stations and timestamps
        result.earliest_possible_start_time = proposed_start_time

        # largest possible distance is half a great-circle, so Pi radians. Should yield a score of 0.
        # smallest possible distance is 0. Should yield a score of 1.
        # so just normalize the smallest_actual_distance over Pi
        result.score = 1.0 - (smallest_actual_distance/3.1415)

        # for min_distance there is no optimal start time.
        # any timestamp meeting the constraint is good enough.
        result.optimal_start_time = None

    return result

@lru_cache(maxsize=10000)
def get_earliest_possible_start_time_for_sky_min_elevation(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=Gridder(), raise_if_interruped: Callable=noop, timeout: timedelta=timedelta(seconds=30)) -> datetime:
    # do expensive search from lower_bound until 24 hours later with small steps
    # (sky constrains are (almost) cyclic over 24 hours).
    # first occurrence where min_elevation constraint is met is taken as rough estimate of earliest_possible_start_time
    at = get_at_constraint_timestamp(scheduling_unit)
    possible_start_time = at or lower_bound
    if upper_bound is None:
        if at:
            upper_bound = lower_bound + scheduling_unit.specified_observation_duration
        else:
            upper_bound = scheduling_unit.latest_possible_cycle_stop_time

    _start_search_timestamp = datetime.utcnow()

    upper_bound = max(lower_bound, upper_bound)
    while possible_start_time <= upper_bound-scheduling_unit.specified_observation_duration:
        raise_if_interruped()

        if timeout is not None:
            _search_elapsed = datetime.utcnow() - _start_search_timestamp
            if _search_elapsed > timeout:
                raise TimeoutError("timeout while searching for earliest_possible_start_time for sky_min_elevation")

        result = evaluate_sky_min_elevation_constraint(scheduling_unit, possible_start_time, gridder=gridder)
        logger.debug('get_earliest_possible_start_time_for_sky_min_elevation %s', result)

        if not result.has_constraint:
            # if there is no constraint, the earliest_possible_start_time is just right away, at the lower_bound
            return lower_bound

        if result.is_constraint_met:
            return result.earliest_possible_start_time

        # constraint is not met, advance possible_start_time and evaluate again
        if result.earliest_possible_start_time is None or result.earliest_possible_start_time < lower_bound:
            # advance with a grid step, and evaluate again
            possible_start_time += gridder.as_timedelta()
            continue

        if result.earliest_possible_start_time is not None:
            # advance straight to earliest_possible_start_time, and evaluate again to ensure the constraint is met
            next_possible_start_time = gridder.grid_time(result.earliest_possible_start_time)
            if next_possible_start_time > possible_start_time:
                possible_start_time = next_possible_start_time
            else:
                possible_start_time += gridder.as_timedelta()
            continue

    return None


def get_earliest_possible_start_time_for_sky_transit_offset(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    # compute the transit time, and thus the optimal_start_time and earliest_possible_start_time
    if gridder is None:
        gridder = Gridder()

    possible_start_time = lower_bound

    if upper_bound is None:
        upper_bound = lower_bound + timedelta(hours=24)
    upper_bound = max(lower_bound, upper_bound)

    allow_quick_jump = True # see below, we can quick jump once, but use monotonous increments so ensure an exit of the while loop.
    while possible_start_time < upper_bound:
        raise_if_interruped()

        gridded_possible_start_time = gridder.grid_time(possible_start_time)
        result = evaluate_sky_transit_constraint(scheduling_unit, gridded_possible_start_time, gridder=gridder, which='nearest')
        logger.debug('get_earliest_possible_start_time_for_sky_transit_offset %s', result)

        if not result.has_constraint:
            # if there is no constraint, the earliest_possible_start_time is just right away, at the lower_bound
            return lower_bound

        if result.is_constraint_met:
            if result.earliest_possible_start_time > lower_bound:
                return result.earliest_possible_start_time
            return lower_bound

        # constraint is not met, or before lower_bound... or equal to previous evaluation result
        if result.earliest_possible_start_time is not None and result.earliest_possible_start_time >= lower_bound and allow_quick_jump:
            # quick jump to earliest_possible_start_time and evaluate to confirm that constraint is met.
            possible_start_time = result.earliest_possible_start_time
            allow_quick_jump = False # prevent more quick jumps which may lead to an endless back-and-forth loop
        else:
            # advance with a step, and evaluate again
            possible_start_time += max(timedelta(hours=1), gridder.as_timedelta())

    return None

@lru_cache(maxsize=10000)
def get_earliest_possible_start_time_for_sky_min_distance(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop, timeout: timedelta=timedelta(seconds=30)) -> datetime:
    # do expensive search from lower_bound until 24 hours later with small steps
    # (sky constrains are (almost) cyclic over 24 hours).
    # first occurrence where min_distance constraint is met is taken as rough estimate of earliest_possible_start_time
    if gridder is None:
        gridder = Gridder()
    gridded_lower_bound = gridder.grid_time(lower_bound)
    possible_start_time = gridded_lower_bound
    if upper_bound is None:
        upper_bound = lower_bound + timedelta(hours=24)
    upper_bound = max(lower_bound, upper_bound)

    _start_search_timestamp = datetime.utcnow()

    while possible_start_time < upper_bound:
        raise_if_interruped()
        if timeout is not None:
            _search_elapsed = datetime.utcnow() - _start_search_timestamp
            if _search_elapsed > timeout:
                raise TimeoutError("timeout while searching for earliest_possible_start_time for sky_min_distance")

        result = evaluate_sky_min_distance_constraint(scheduling_unit, possible_start_time, gridder=gridder)
        logger.debug('get_earliest_possible_start_time_for_sky_min_distance %s', result)

        if not result.has_constraint:
            # if there is no constraint, the earliest_possible_start_time is just right away, at the lower_bound
            return lower_bound

        if result.is_constraint_met:
            return result.earliest_possible_start_time

        # constraint is not met, advance possible_start_time and evaluate again
        if result.earliest_possible_start_time is None or result.earliest_possible_start_time < lower_bound:
            # advance with a grid step, and evaluate again
            possible_start_time += gridder.as_timedelta()
            continue

        if result.earliest_possible_start_time is not None:
            # advance straight to earliest_possible_start_time, and evaluate again to ensure the constraint is met
            next_possible_start_time = gridder.grid_time(result.earliest_possible_start_time)
            if next_possible_start_time > possible_start_time:
                possible_start_time = next_possible_start_time
            else:
                possible_start_time += gridder.as_timedelta()
            continue

    return None


@lru_cache(10000)
def evaluate_daily_constraints(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime, gridder: Gridder) -> ConstraintResult:
    """ Evaluate the daily constraints: are they met? and what are the score, optimal- and earliest_possible_start_time?
    """
    result = ConstraintResult(scheduling_unit, 'daily', proposed_start_time)
    constraints = scheduling_unit.scheduling_constraints_doc

    if 'daily' not in constraints or not constraints['daily']:
        # no constraints
        result.score = 1
        result.earliest_possible_start_time = proposed_start_time
        return result

    daily_constraints = constraints['daily']

    if not daily_constraints.get('require_day') and not daily_constraints.get('require_night') and not daily_constraints.get('avoid_twilight'):
        # no constraints
        result.score = 1
        result.earliest_possible_start_time = proposed_start_time
        return result

    if daily_constraints.get('require_day') and daily_constraints.get('require_night'):
        # mutually exclusive options
        result.score = 0
        return result

    duration = scheduling_unit.specified_observation_duration
    proposed_end_time = proposed_start_time + duration

    stations = get_stations_to_be_evaluated(scheduling_unit.main_observation_task, proposed_start_time, 10e4)

    # the sun rise/set events do not depend on the actual time-of-day, but only on the date.
    # so, use one timstamp for 'today'-noon, one for 'yesterday'-noon and one for 'tomorrow'-noon
    # by using a 'gridded' noon timestamp, we get many cachehits for any proposed_start_time on this date.
    # We need the previous and next day events as well for reasoning about observations passing midnight
    today_noon = proposed_start_time.replace(hour=12, minute=0, second=0, microsecond=0)
    prevday_noon = today_noon - timedelta(days=1)
    nextday_noon = today_noon + timedelta(days=1)
    timestamps = (today_noon, nextday_noon, prevday_noon)
    all_sun_events = timestamps_and_stations_to_sun_rise_and_set(timestamps=timestamps,
                                                                 stations=tuple(stations),
                                                                 n_grid_points=gridder.n_grid_points())

    # start with a score of 1, assume constraint is met.
    # then loop over all station-sun-events below, and set score to 0 if one is not met.
    # if none are not met (thus all are met), then we keep this initial score of 1, indicating all are met.
    result.score = 1
    result.earliest_possible_start_time = None

    for station in stations:
        sun_events = all_sun_events[station]
        for event_name, event in list(sun_events.items()):
            if len(event) < len(timestamps):
                # sun is either always up, or always down on this day
                sun_events[event_name] = []
                for timestamp in timestamps:
                    sun_coord = get_sun(Time(timestamp))
                    sun_elevation = compute_elevation(Pointing.from_SkyCoord(sun_coord), timestamp, station)
                    if sun_elevation > SUN_SET_RISE_ANGLE_TO_HORIZON.rad:
                        # sun is always up
                        if event_name == 'day':
                            sun_events[event_name].append({'start': timestamp - timedelta(hours=12), # previous midnight
                                                           'end': timestamp + timedelta(hours=12)})  # next midnight
                        elif event_name == 'night':
                            sun_events[event_name].append({'start': timestamp,
                                                           'end': timestamp})
                        elif event_name == 'sunrise':
                            # accept brief sunrise at previous midnight
                            sun_events[event_name].append({'start': timestamp - timedelta(hours=12),
                                                           'end': timestamp - timedelta(hours=12)})
                        elif event_name == 'sunset':
                            # accept brief sunset at next midnight
                            sun_events[event_name].append({'start': timestamp + timedelta(hours=12),
                                                           'end': timestamp + timedelta(hours=12)})
                    else:
                        # sun is always down
                        if event_name == 'day':
                            sun_events[event_name].append({'start': timestamp,
                                                           'end': timestamp})
                        elif event_name == 'night':
                            sun_events[event_name].append({'start': timestamp - timedelta(hours=12),
                                                           'end': timestamp + timedelta(hours=12)})
                        elif event_name == 'sunrise':
                            # accept brief sunrise at previous midnight
                            sun_events[event_name].append({'start': timestamp - timedelta(hours=12),
                                                           'end': timestamp - timedelta(hours=12)})
                        elif event_name == 'sunset':
                            # accept brief sunset at next midnight
                            sun_events[event_name].append({'start': timestamp + timedelta(hours=12),
                                                           'end': timestamp + timedelta(hours=12)})

                logger.warning("get_earliest_possible_start_time for SUB id=%s: not all %s events could be computed for station %s lower_bound=%s. Using these always up/down alternatives: %s %s", scheduling_unit.id, event_name, station, proposed_start_time, event_name, sun_events[event_name])

        day = sun_events['day'][0]
        night = sun_events['night'][0]
        next_day = sun_events['day'][1]
        next_night = sun_events['night'][1]
        prev_day = sun_events['day'][2]
        prev_night = sun_events['night'][2]
        if daily_constraints.get('require_day'):
            if proposed_start_time >= gridder.minus_margin(day['start']) and proposed_end_time <= gridder.plus_margin(day['end']):
                # in principle, we could start immediately at the day.start
                # but, we're not allowed to start earlier than the proposed_start_time
                # so, use proposed_start_time as earliest_possible_start_time
                result.earliest_possible_start_time = max(proposed_start_time, result.earliest_possible_start_time or datetime.min)
            elif proposed_end_time > gridder.plus_margin(day['end']):
                # cannot start this day
                result.score = 0
                # but can start next day
                result.earliest_possible_start_time = max(next_day['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            else:
                result.score = 0
                result.earliest_possible_start_time = max(day['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit

        if daily_constraints.get('require_night'):
            if proposed_start_time >= gridder.minus_margin(night['start']) and proposed_end_time <= gridder.plus_margin(night['end']):
                # in principle, we could start immediately at the night.start
                # but, we're not allowed to start earlier than the proposed_start_time
                # so, use proposed_start_time as earliest_possible_start_time
                result.earliest_possible_start_time = max(proposed_start_time, result.earliest_possible_start_time or datetime.min)
            elif proposed_end_time > gridder.minus_margin(prev_night['end']):
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time or datetime.min)
                result.score = 0
                return result # early exit
            elif proposed_start_time >= gridder.minus_margin(prev_night['start']) and proposed_end_time <= gridder.plus_margin(prev_night['end']):
                # in principle, we could start immediately at the prev_night.start
                # but, we're not allowed to start earlier than the proposed_start_time
                # so, use proposed_start_time as earliest_possible_start_time
                result.earliest_possible_start_time = max(proposed_start_time, result.earliest_possible_start_time or datetime.min)
            else:
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time or datetime.min)

        if daily_constraints.get('avoid_twilight'):
            if proposed_start_time >= gridder.minus_margin(day['start']) and proposed_end_time <= gridder.plus_margin(day['end']):
                # obs fits in today's daytime
                result.score = 1
                result.earliest_possible_start_time = max(day['start'], result.earliest_possible_start_time or datetime.min)
            elif proposed_start_time >= gridder.minus_margin(night['start']) and proposed_end_time <= gridder.plus_margin(night['end']):
                # obs fits in today's upcoming nighttime
                result.score = 1
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time or datetime.min)
            elif proposed_start_time >= gridder.minus_margin(prev_night['start']) and proposed_end_time <= gridder.plus_margin(prev_night['end']):
                # obs fits in today's past nighttime
                result.score = 1
                result.earliest_possible_start_time = max(prev_night['start'], result.earliest_possible_start_time or datetime.min)
            elif proposed_start_time < gridder.plus_margin(night['start']) and proposed_end_time >= gridder.minus_margin(night['start']):
                # obs starts in afternoon twilight
                result.score = 0
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            elif proposed_start_time < gridder.plus_margin(day['end']) and proposed_end_time >= gridder.minus_margin(day['end']):
                # obs ends in afternoon twilight
                result.score = 0
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            elif proposed_start_time >= gridder.minus_margin(prev_night['end']) and proposed_start_time < gridder.plus_margin(day['start']):
                # obs starts in morning twilight
                result.score = 0
                result.earliest_possible_start_time = max(day['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            elif proposed_end_time >= gridder.minus_margin(prev_night['end']) and proposed_end_time < gridder.plus_margin(day['start']):
                # obs ends in morning twilight
                result.score = 0
                result.earliest_possible_start_time = max(day['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            elif proposed_start_time >= gridder.minus_margin(night['end']) and proposed_start_time < gridder.plus_margin(next_day['start']):
                # obs starts in next day in twilight
                result.score = 0
                result.earliest_possible_start_time = max(next_day['start'], result.earliest_possible_start_time or datetime.min)
                return result # early exit
            else:
                result.score = 0
                return result # early exit

    return result

@lru_cache(maxsize=10000)
def get_earliest_possible_start_time_for_daily_constraints(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    # search from lower_bound until 24 hours later with 6 hour steps
    # (daily constrains are (almost) cyclic over 24 hours)
    if gridder is None:
        gridder = Gridder()
    gridded_lower_bound = gridder.grid_time(lower_bound)
    possible_start_time = gridded_lower_bound
    while possible_start_time < lower_bound+timedelta(hours=24):
        raise_if_interruped()

        result = evaluate_daily_constraints(scheduling_unit, possible_start_time, gridder=gridder)
        logger.debug('get_earliest_possible_start_time_for_daily_constraints %s', result)

        if not result.has_constraint:
            # if there is no constraint, the earliest_possible_start_time is just right away, at the lower_bound
            return lower_bound

        if not result.is_constraint_met and result.earliest_possible_start_time is not None:
            # advance straight to earliest_possible_start_time, and evaluate again to ensure the constraint is met
            possible_start_time = gridder.grid_time(result.earliest_possible_start_time)
            continue

        if result.is_constraint_met:
            if result.earliest_possible_start_time >= lower_bound:
                if upper_bound is None or result.earliest_possible_start_time < upper_bound:
                    return result.earliest_possible_start_time
                else:
                    # do not advance past upper_bound
                    return None
            else:
                return lower_bound

        # advance with a grid step, and evaluate again
        possible_start_time += gridder.as_timedelta()

    return None


def get_earliest_possible_start_time_for_time_constraints(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    '''
    '''
    constraints = scheduling_unit.scheduling_constraints_doc

    # collect the earliest_possible_start_times per subtype of time-constraints.
    # then return the latest of all earliest_possible_start_times
    earliest_possible_start_times = set()

    if 'time' in constraints:
        if 'at' in constraints['time']:
            at = get_at_constraint_timestamp(scheduling_unit)
            return at

        if 'after' in constraints['time']:
            after = parser.parse(constraints['time']['after'], ignoretz=True)
            if upper_bound is None or after <= upper_bound - scheduling_unit.specified_observation_duration:
                if lower_bound is not None:
                    earliest_possible_start_times.add(max(lower_bound, after))
                else:
                    earliest_possible_start_times.add(after)

        if 'before' in constraints['time']:
            before = parser.parse(constraints['time']['before'], ignoretz=True)
            start_before = before - scheduling_unit.specified_observation_duration
            if lower_bound is not None and lower_bound <= start_before:
                earliest_possible_start_times.add(lower_bound)

        if 'between' in constraints['time'] and constraints['time']['between']:
            from_timestamps = [parser.parse(between["from"], ignoretz=True)
                               for between in constraints['time']['between']
                               if lower_bound is None or parser.parse(between["to"], ignoretz=True) > lower_bound]
            from_timestamps = [max(lower_bound, ts) for ts in from_timestamps]
            if from_timestamps:
                earliest_possible_start_times.add(min(from_timestamps))

        if 'not_between' in constraints['time'] and constraints['time']['not_between']:
            # parse string -> datetime first
            not_betweens = [{"from": parser.parse(not_between["from"], ignoretz=True),
                             "to": parser.parse(not_between["to"], ignoretz=True)}
                            for not_between in constraints['time']['not_between']]

            # only check > lower_bound
            not_betweens = [nb for nb in not_betweens if nb['to']>=lower_bound]

            if not_betweens:
                #sort them
                not_betweens = sorted(not_betweens, key=lambda nb: nb['to'])
                for i in range(len(not_betweens)-1):
                    potential_earliest_possible = not_betweens[i]['to']
                    gap_to_next = not_betweens[i+1]['from'] - potential_earliest_possible
                    if gap_to_next >= scheduling_unit.specified_observation_duration:
                        earliest_possible_start_times.add(potential_earliest_possible)
                        break

    if not earliest_possible_start_times and not (constraints.get('time', {}).get('at') or
                                                  constraints.get('time', {}).get('before') or
                                                  constraints.get('time', {}).get('after') or
                                                  constraints.get('time', {}).get('between') or
                                                  constraints.get('time', {}).get('not_between')):
        # an empty time constraint means it can just run at/after lower_bound
        return lower_bound

    if lower_bound is not None:
        earliest_possible_start_times = [t for t in earliest_possible_start_times if t >= lower_bound]

    if upper_bound is not None:
        start_before = upper_bound - scheduling_unit.specified_observation_duration
        earliest_possible_start_times = [t for t in earliest_possible_start_times if t <= start_before]

    if earliest_possible_start_times:
        return max(earliest_possible_start_times)

    return None


def get_at_constraint_timestamp(scheduling_unit: models.SchedulingUnitBlueprint) -> datetime:
    '''returns the 'at' timestamp if there is a 'time.at' constraint, else None'''
    if 'at' in scheduling_unit.scheduling_constraints_doc.get('time',{}):
        at = parser.parse(scheduling_unit.scheduling_constraints_doc['time']['at'], ignoretz=True)
        return at
    return None

def get_earliest_possible_start_time_taking_used_stations_into_account(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    '''same as get_earliest_possible_start_time, but taking any already-used-and-thus-blocking-stations into account.'''
    earliest_possible_start_time = get_earliest_possible_start_time(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped)

    if earliest_possible_start_time is not None and not scheduling_unit.interrupts_telescope: # triggered observations should cancel blocking observations if they have enough priority.
        try:
            # check for any overlapping units...
            blocking_units = get_blocking_scheduled_or_observing_units(scheduling_unit, earliest_possible_start_time)
            if blocking_units.exists():
                blocking_observing_units = blocking_units.filter(status__value=models.SchedulingUnitStatus.Choices.OBSERVING.value).all()
                blocking_scheduled_units = blocking_units.filter(status__value=models.SchedulingUnitStatus.Choices.SCHEDULED.value).all()

                if blocking_scheduled_units.exists():
                    # score both the cadidate and all blocking scheduled units, and check if the candidate has a better score.
                    logger.info("get_earliest_possible_start_time_taking_used_stations_into_account: re-scoring candidate unit id=%s and blocking units %s",
                                scheduling_unit.id, ','.join(str(u.id) for u in blocking_scheduled_units))

                    blocking_scheduled_units_with_start_time = compute_start_times_for_units(list(blocking_scheduled_units), lower_bound, upper_bound, gridder, raise_if_interruped)
                    scored_units = compute_scores_for_units_with_start_time(blocking_scheduled_units_with_start_time+[SchedulingUnitAndStartTime(scheduling_unit, earliest_possible_start_time)], lower_bound, upper_bound, gridder, raise_if_interruped)
                    scored_candidate = [su for su in scored_units if su.scheduling_unit.id==scheduling_unit.id][0]
                    scored_blocking_units = [su for su in scored_units if su.scheduling_unit.id!=scheduling_unit.id]

                    # if the candidate has a higher score, then it can override and unschedule the already scheduled units.
                    # so, in that case, ignore the overlap with the blocking scheduled units.
                    # else, the blocking units cannot/willnot be unscheduled, so advance the lower_bound until after the blocking units
                    better_scoring_blocking_units = [scored_blocking_unit for scored_blocking_unit in scored_blocking_units if scored_candidate.weighted_score < scored_blocking_unit.weighted_score]
                else:
                    # there are no better_scoring_blocking_units
                    better_scoring_blocking_units = []

                if better_scoring_blocking_units or blocking_observing_units.exists():
                    # there are blocking units, recurse with an advanced lower_bound
                    better_scoring_blocking_units_stop_times = [su.scheduling_unit.on_sky_stop_time for su in better_scoring_blocking_units]
                    blocking_observing_units_stop_times = [su.on_sky_stop_time for su in blocking_observing_units]
                    latest_blocking_stop_time = max(better_scoring_blocking_units_stop_times+blocking_observing_units_stop_times)
                    from .dynamic_scheduling import DEFAULT_INTER_OBSERVATION_GAP
                    advanced_lower_bound = latest_blocking_stop_time + DEFAULT_INTER_OBSERVATION_GAP
                    if advanced_lower_bound < upper_bound:
                        logger.debug("get_earliest_possible_start_time_taking_used_stations_into_account: SUB id=%s earliest_possible_start_time='%s' is blocked by units %s. Advancing window from lower_bound='%s' to new lower_bound='%s', upper_bound='%s'",
                                    scheduling_unit.id, earliest_possible_start_time, ','.join(str(u.id) for u in blocking_units), lower_bound, advanced_lower_bound, upper_bound)

                        advanced_earliest_possible_start_time = get_earliest_possible_start_time_taking_used_stations_into_account(scheduling_unit, advanced_lower_bound, upper_bound, gridder, raise_if_interruped)

                        if advanced_earliest_possible_start_time is not None:
                            logger.debug("get_earliest_possible_start_time_taking_used_stations_into_account: SUB id=%s advanced_earliest_possible_start_time='%s' lower_bound='%s', upper_bound='%s'",
                                        scheduling_unit.id, advanced_earliest_possible_start_time, advanced_lower_bound, upper_bound)
                            return advanced_earliest_possible_start_time

                logger.info("get_earliest_possible_start_time_taking_used_stations_into_account: SUB id=%s is blocked by units %s at earliest_possible_start_time='%s'",
                      scheduling_unit.id, ','.join(str(u.id) for u in blocking_units), earliest_possible_start_time)
                return None
        except Exception as e:
            logger.exception(e)

    return earliest_possible_start_time


def get_earliest_possible_start_time(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    '''
    '''
    _method_start_timestamp = datetime.utcnow()
    if gridder is None:
        gridder = Gridder()

    if lower_bound is not None and upper_bound is not None and lower_bound >= upper_bound:
        return None

    at = get_at_constraint_timestamp(scheduling_unit)
    if at:
        # if there is an 'at' constraint, then that is always earliest_possible_start_time
        # however... we should also check if all other constraints are met. So, can it run at 'at'?
        if can_run_at(scheduling_unit, at, gridder=gridder):
            return at
        return None

    # collect the earliest_possible_start_times per type of constraint.
    # then return the latest of all earliest_possible_start_times
    earliest_possible_start_times = set()
    for get_earliest_possible_start_time_method in (get_earliest_possible_start_time_for_time_constraints,
                                                    get_earliest_possible_start_time_for_daily_constraints,
                                                    get_earliest_possible_start_time_for_sky_transit_offset,
                                                    get_earliest_possible_start_time_for_sky_min_elevation,
                                                    get_earliest_possible_start_time_for_sky_min_distance):
        try:
            earliest_possible_start_time = get_earliest_possible_start_time_method(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped)
            if earliest_possible_start_time is None:
                # early exit. None result means no possible starttime at all for this unit with these constraints in this time window.
                logger.debug("get_earliest_possible_start_time SUB id=%s window=['%s', '%s'] early exit returning None, because %s returned None", scheduling_unit.id, lower_bound, upper_bound, get_earliest_possible_start_time_method.__name__)
                return None
            earliest_possible_start_times.add(earliest_possible_start_time)
        except SchedulerInterruptedException:
            raise
        except TimeoutError:
            raise
        except Exception as e:
            logger.exception(e)

    if len(earliest_possible_start_times) == 0:
        # it's possible that none of the above constraints yielded an earliest_possible_start_time (or that there are no constraints)
        # this might mean that the unit can start right away at the lower_bound
        # so, add lower_bound if the unit can directly run at lower_bound.
        if can_run_at(scheduling_unit, lower_bound, gridder):
            earliest_possible_start_times.add(lower_bound)

    # filter for non-None and within bound(s)
    earliest_possible_start_times = set([t for t in earliest_possible_start_times if t is not None and t >= lower_bound])
    if upper_bound is not None:
        start_before = upper_bound - scheduling_unit.specified_observation_duration
        earliest_possible_start_times = set([t for t in earliest_possible_start_times if t <= start_before])
    logger.debug("get_earliest_possible_start_time SUB id=%s lower_bound='%s' earliest_possible_start_times per constraint: %s", scheduling_unit.id, lower_bound, ', '.join([str(t) for t in sorted(earliest_possible_start_times)]))

    # the earliest_possible_start_times were computed per constraint-type.
    # it is possible that a unit can run at a certain time for one constraint, but cannot for the other.
    # filter and keep only those for which all constraints are met.
    runnable_earliest_possible_start_times = [t for t in earliest_possible_start_times if can_run_at(scheduling_unit, t, gridder)]

    if not runnable_earliest_possible_start_times and earliest_possible_start_times:
        # none of the possible start_times is actually runnable and > lower_bound...
        # so, 'advance' to the max of the known earliest_possible_start_times and try again (recurse)
        later_possible_start_times = [t for t in earliest_possible_start_times if t > lower_bound]
        if later_possible_start_times:
            advanced_lower_bound = max(later_possible_start_times)
            return get_earliest_possible_start_time(scheduling_unit, advanced_lower_bound, upper_bound, gridder)

    _method_elapsed = datetime.utcnow() - _method_start_timestamp

    if runnable_earliest_possible_start_times:
        logger.debug("get_earliest_possible_start_time SUB id=%s lower_bound='%s' runnable_earliest_possible_start_times: %s", scheduling_unit.id, lower_bound, ', '.join([str(t) for t in sorted(runnable_earliest_possible_start_times)]))
        # return the first of all runnable earliest_possible_start_times
        earliest_possible_start_time = min(runnable_earliest_possible_start_times)
        # make sure it's past lower_bound, and nicely rounded
        earliest_possible_start_time = max(lower_bound, earliest_possible_start_time)
        earliest_possible_start_time = round_to_second_precision(earliest_possible_start_time)

        logger.debug("get_earliest_possible_start_time SUB id=%s lower_bound='%s' earliest_possible_start_time='%s' (took %.1f[s])", scheduling_unit.id, lower_bound, earliest_possible_start_time, _method_elapsed.total_seconds())
        return earliest_possible_start_time

    # no constraints yielding a runnable earliest_possible_start_time?
    logger.debug("get_earliest_possible_start_time SUB id=%s lower_bound='%s' earliest_possible_start_time=None (took %.1f[s])", scheduling_unit.id, lower_bound, _method_elapsed.total_seconds())
    return None


def get_latest_possible_start_time(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    '''Get the latest possible starttime for the given unit withing the given lower- and upper_bound.'''
    # ToDo: implement more constraints. For now, only the time.before constraint is implemented.
    constraints = scheduling_unit.scheduling_constraints_doc

    latest_start_time_wrt_upper_bound = upper_bound - scheduling_unit.specified_observation_duration

    if 'before' in constraints.get('time', {}):
        # the full main observation should be able to complete before the 'before'timestamp
        stop_before = parser.parse(constraints['time']['before'], ignoretz=True)
        latest_possible_start_time = stop_before - scheduling_unit.specified_observation_duration
        return max(lower_bound, min(latest_possible_start_time, latest_start_time_wrt_upper_bound))

    return latest_start_time_wrt_upper_bound


def get_optimal_start_time(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, gridder: Gridder=None) -> datetime:
    '''get the most optimal start_time (where exposure is highest) AND where all constraints are met.
    If lower_bound is given and optimal>lower_bound then the earliest possible start_time is returned (which is close to optimal)'''
    if gridder is None:
        gridder = Gridder()

    at = get_at_constraint_timestamp(scheduling_unit)
    if at:
        # if there is an 'at' constraint, then that is always optimal_start_time
        # however... we should also check if all other constraints are met. So, can it run at 'at'?
        if can_run_at(scheduling_unit, at):
            logger.debug("get_optimal_start_time SUB id=%s lower_bound='%s' optimal_start_time='%s'", scheduling_unit.id, lower_bound, at)
            return at
        return None

    _method_start_timestamp = datetime.utcnow()

    # seek nearest transit around lower_bound
    result = evaluate_sky_transit_constraint(scheduling_unit, gridder.grid_time(lower_bound), gridder=gridder, which='nearest')
    if not result.is_constraint_met and result.optimal_start_time is None:
        # could not determine an optimal starttime (maybe no stations are available?)
        return None

    optimal_start_time = result.optimal_start_time

    if lower_bound is not None and optimal_start_time is not None and optimal_start_time < lower_bound:
        result = evaluate_sky_transit_constraint(scheduling_unit, gridder.grid_time(lower_bound), gridder=gridder, which='next')
        optimal_start_time = result.optimal_start_time

    if lower_bound is not None and optimal_start_time is not None and optimal_start_time < lower_bound:
        logger.debug("get_optimal_start_time SUB id=%s optimal_start_time='%s' < lower_bound='%s' computing earliest_possible_start_time...", scheduling_unit.id, optimal_start_time, lower_bound)
        # use the earliest_possible_start_time limited to lower_bound as optimal_start_time
        optimal_start_time = get_earliest_possible_start_time(scheduling_unit, lower_bound, lower_bound+timedelta(hours=24), gridder=gridder)
        logger.debug("get_optimal_start_time SUB id=%s earliest_possible_start_time and optimal_start_time='%s'", scheduling_unit.id, optimal_start_time)

    assert optimal_start_time is not None and optimal_start_time >= lower_bound, "SUB id=%s cannot find optimal start_time > %s" % (scheduling_unit.id, lower_bound)

    optimal_start_time = round_to_second_precision(optimal_start_time)
    logger.debug("get_optimal_start_time SUB id=%s lower_bound='%s' optimal_start_time='%s' (took %.1f[s])", scheduling_unit.id, lower_bound, optimal_start_time, (datetime.utcnow() - _method_start_timestamp).total_seconds())
    return optimal_start_time



def compute_start_times_for_units(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound:datetime, upper_bound:datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> [SchedulingUnitAndStartTime]:
    if gridder is None:
        gridder = Gridder()

    units_with_start_time = []
    for i, su in enumerate(scheduling_units):
        raise_if_interruped()

        try:
            result = compute_scheduling_unit_start_time(su, lower_bound, upper_bound, gridder)

            if result is not None and result.start_time is not None:
                units_with_start_time.append(result)
                logger.debug("compute_start_times_for_units: unit [%d/%d] %.1f%% %s",
                            i+1, len(scheduling_units), 100.0 * (i+1) / len(scheduling_units), result)
            else:
                logger.debug("compute_start_times_for_units: no start_time for unit [%d/%d] %.1f%% %s between ['%s', '%s']",
                               i+1, len(scheduling_units), 100.0 * (i+1) / len(scheduling_units), result or su.id, lower_bound, upper_bound)
        except Exception as e:
            logger.exception(e)
    return units_with_start_time


def compute_start_times_and_scores_for_units(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound: datetime, upper_bound: datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> [ScoredSchedulingUnit]:
    units_with_start_times = compute_start_times_for_units(scheduling_units, lower_bound, upper_bound, gridder, raise_if_interruped)
    scored_scheduling_units = compute_scores_for_units_with_start_time(units_with_start_times, lower_bound, upper_bound, gridder, raise_if_interruped)
    return scored_scheduling_units


def compute_scores_for_units_with_start_time(units_with_start_time: [SchedulingUnitAndStartTime], lower_bound: datetime, upper_bound: datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> [ScoredSchedulingUnit]:
    if gridder is None:
        gridder = Gridder()

    score_names = set() # keep track of all unique score_names while scoring, so we can one time create/get the their weight_factors.
    scored_units = []
    for i, unit_with_start_time in enumerate(units_with_start_time):
        raise_if_interruped()

        try:
            scored_su = compute_scores_at_start_time(unit_with_start_time, lower_bound, upper_bound, gridder)
            if scored_su is not None and scored_su.start_time is not None and len(scored_su.scores) > 0:
                scored_units.append(scored_su)
                for score_name in scored_su.scores.keys():
                    score_names.add(score_name)
                logger.debug("compute_scores_for_units_with_start_time: scored unit [%d/%d] %.1f%% %s",
                             i+1, len(units_with_start_time), 100.0 * (i+1) / len(units_with_start_time), scored_su)
            else:
                logger.debug("compute_scores_for_units_with_start_time: could not determine scores/start_time for unit [%d/%d] %.1f%% %s",
                                 i+1, len(units_with_start_time), 100.0 * (i+1) / len(units_with_start_time), unit_with_start_time)

        except Exception as e:
            logger.exception(e)

    logger.debug('compute_scores_for_units_with_start_time: scored %d/%d units', len(scored_units), len(units_with_start_time))

    if scored_units:
        # create/get a weight per unique score_name, caching it in a dict, thus reducing the number of db calls.
        weight_for_score_name = {}
        for score_name in sorted(list(score_names)):
            weight_factor, created = models.SchedulingConstraintsWeightFactor.objects.get_or_create(constraint_name=score_name,
                                                                                                    defaults={'weight': 1.0})
            weight_for_score_name[score_name] = weight_factor.weight

        logger.debug('compute_scores_for_units_with_start_time: applying weights: %s' , ' '.join(['%s=%.4f' % (score_name, weight_for_score_name[score_name]) for score_name in sorted(list(score_names))]))

        # do the actual weighting
        for i, scored_su in enumerate(scored_units):
            # compute weighted total score
            weighted_score = 0.0
            for score_key, score_value in scored_su.scores.items():
                weight = weight_for_score_name[score_key]
                weighted_score += weight * score_value
            scored_su.weighted_score = weighted_score / float(len(scored_su.scores))
            logger.debug("compute_scores_for_units_with_start_time: weighted scores for unit [%d/%d] %.1f%% %s", i+1, len(scored_units), 100.0 * (i + 1) / len(scored_units), scored_su)

    return scored_units


def compute_scheduling_unit_start_time(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime, gridder: Gridder) -> SchedulingUnitAndStartTime:
    '''Compute best fitting start_time, somewhere between the earliest_possible and the optimal at transit.
    At this start_time, compute the "fitness" scores per constraint for the given scheduling_unit depending on the sub's constrains-template/doc.'''
    # if the unit is already scheduled, evaluate the scores at the known scheduled_start_time,
    # else compute a weighted between earliest- and optimal start_time.
    if scheduling_unit.status.value in models.SchedulingUnitStatus.ACTIVE_OR_FINISHED_STATUS_VALUES:
        return SchedulingUnitAndStartTime(scheduling_unit=scheduling_unit, start_time=scheduling_unit.scheduled_start_time)

    at = get_at_constraint_timestamp(scheduling_unit)
    if at:
        return SchedulingUnitAndStartTime(scheduling_unit=scheduling_unit, start_time=at)

    unit_gridder = fine_enough_gridder(scheduling_unit, gridder)

    earliest_possible_start_time = get_earliest_possible_start_time_taking_used_stations_into_account(scheduling_unit, lower_bound, min(upper_bound, lower_bound+timedelta(hours=24)), gridder=unit_gridder)

    if earliest_possible_start_time is not None and can_run_at(scheduling_unit, earliest_possible_start_time, unit_gridder):
        assert earliest_possible_start_time >= lower_bound, "SUB id=%s earliest_possible_start_time='%s' should be >= lower_bound='%s'" % (scheduling_unit.id, earliest_possible_start_time, lower_bound)

        optimal_start_time = get_optimal_start_time(scheduling_unit, lower_bound, gridder=gridder)

        # because get_optimal_start_time only looks at the transit, and get_earliest_possible_start_time_taking_used_stations_into_account looks at all constraints
        # the optimal_start_time can be earlier than the overall earliest_possible_start_time.
        # so, only weight the start_time between these two if and only if optimal_start_time > (overall)earliest_possible_start_time
        if optimal_start_time is not None and optimal_start_time > earliest_possible_start_time:
            # are all (other) constraints met at optimal_start_time?
            if can_run_at(scheduling_unit, optimal_start_time, unit_gridder):
                # with the density_vs_optimal the user can optimize for:
                # - a dense schedule where all units are packed near to each other (weight=0)
                # - an optimal schedule where all units are positioned at/near the optimal (transit) time (weight=1)
                # - or a mix between both (0<weight<1)
                density_vs_optimal, created = models.SchedulingConstraintsWeightFactor.objects.get_or_create(
                    constraint_name='density_vs_optimal',
                    defaults={'weight': 1.0})

                latest_possible_start_time = get_latest_possible_start_time(scheduling_unit, lower_bound, upper_bound)

                weighted_start_time = earliest_possible_start_time + density_vs_optimal.weight * (optimal_start_time-earliest_possible_start_time)
                weighted_start_time = min(max(lower_bound, weighted_start_time), latest_possible_start_time)
                weighted_start_time = round_to_second_precision(weighted_start_time)

                if can_run_at(scheduling_unit, weighted_start_time, unit_gridder):
                    logger.debug("get_weighted_start_time: SUB id=%s  weighted='%s'  -  weight=%.3f earliest='%s' optimal='%s' latest='%s'  -  window=['%s', '%s']", scheduling_unit.id, weighted_start_time, density_vs_optimal.weight, earliest_possible_start_time, optimal_start_time, latest_possible_start_time, lower_bound, upper_bound)
                    return SchedulingUnitAndStartTime(scheduling_unit=scheduling_unit, start_time=weighted_start_time)

        # no weighted_start_time could be computed above, so return earliest_possible_start_time (after doing a just-to-be-sure check that all constraints are met)
        if can_run_at(scheduling_unit, earliest_possible_start_time, unit_gridder):
            logger.debug("get_weighted_start_time: SUB id=%s returning earliest='%s'  -  window=['%s', '%s']", scheduling_unit.id, earliest_possible_start_time, lower_bound, upper_bound)
            return SchedulingUnitAndStartTime(scheduling_unit=scheduling_unit, start_time=earliest_possible_start_time)

    logger.debug("get_weighted_start_time: SUB id=%s could not compute weighted_start_time  -  window=['%s', '%s']", scheduling_unit.id, lower_bound, upper_bound)
    return SchedulingUnitAndStartTime(scheduling_unit=scheduling_unit, start_time=None)


def compute_scores_at_start_time(unit_with_start_time: SchedulingUnitAndStartTime, lower_bound: datetime, upper_bound: datetime, gridder: Gridder) -> ScoredSchedulingUnit:
    '''Compute the "fitness" scores per constraint for the given scheduling_unit at the given start_time depending on the sub's constrains-template/doc.'''
    scores = {}

    scheduling_unit = unit_with_start_time.scheduling_unit
    proposed_start_time = unit_with_start_time.start_time
    unit_gridder = fine_enough_gridder(unit_with_start_time.scheduling_unit, gridder)

    # add individual scheduling_unit rank: rank is "inverse", meaning that a lower value is better. also, normalize it.
    scores['unit_rank'] = float(models.SchedulingUnitRank.LOWEST.value - scheduling_unit.rank) / float(models.SchedulingUnitRank.LOWEST.value-models.SchedulingUnitRank.HIGHEST.value)

    # add "common" scores which do not depend on constraints, such as project rank and creation date
    # rank is "inverse", meaning that a lower value is better. also, normalize it.
    scores['project_rank'] = float(models.ProjectRank.LOWEST.value - scheduling_unit.project.rank)/float(models.ProjectRank.LOWEST.value-models.ProjectRank.HIGHEST.value)

    if 'at' in scheduling_unit.scheduling_constraints_doc.get('time',{}):
        at = get_at_constraint_timestamp(scheduling_unit)
        scores['time.at'] = 1.0 if abs((at - proposed_start_time).total_seconds()) < 60 else 0.0

    # every unit has to run at least 'before' the latest possible cycle start time
    before = scheduling_unit.latest_possible_cycle_start_time
    # if there is a specific 'before' constraint, use that.
    if 'before' in scheduling_unit.scheduling_constraints_doc.get('time', {}):
        before = parser.parse(scheduling_unit.scheduling_constraints_doc['time']['before'], ignoretz=True)
    # if there are 'between' constraints as well, use the latest smaller than 'before' as 'before' if any.
    if len(scheduling_unit.scheduling_constraints_doc.get('time', {}).get('between', [])) > 0:
        between_tos = [parser.parse(between["to"], ignoretz=True) for between in scheduling_unit.scheduling_constraints_doc['time']['between']]
        between_tos = sorted([t for t in between_tos if t < before])
        if between_tos:
            before = between_tos[-1]
    # the closer we are to the before timestamp, the higher the need to run it, so the higher the score
    # max score is 1, when weighted_start_time==before
    # normalize over time_until_before
    scores['before'] = min(1, max(0, (proposed_start_time-lower_bound).total_seconds() / (before-lower_bound).total_seconds()))


    # density means less and smaller gaps in the schedule
    # so, if we start at lower_bound, then density should be 1
    # so, if we start at upper_bound, then density should be 0
    scores['density'] = min(1, max(0, (upper_bound-proposed_start_time).total_seconds() / (upper_bound-lower_bound).total_seconds()))

    # compute/get scores per constraint type
    gridded_weighted_start_time = unit_gridder.grid_time(proposed_start_time)
    for evaluate_method in (evaluate_sky_transit_constraint,
                            evaluate_sky_min_elevation_constraint,
                            evaluate_sky_min_distance_constraint,
                            evaluate_daily_constraints):
        # compute the result at the gridded weighted_start_time for cache hits. (margins at bounds are taken into account)
        result = evaluate_method(scheduling_unit, gridded_weighted_start_time, unit_gridder)
        if result.has_constraint:
            if result.is_constraint_met:
                scores[result.constraint_key] = result.score
            else:
                scores[result.constraint_key] = 0
                proposed_start_time = None

    return ScoredSchedulingUnit(scheduling_unit=scheduling_unit,
                                scores=scores,
                                # return the actual (not the gridded) weighted_start_time
                                start_time=proposed_start_time)

def get_min_earliest_possible_start_time(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound: datetime, upper_bound: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> datetime:
    '''deterimine the earliest possible starttime over all given scheduling units, taking into account all their constraints
    :param raise_if_interruped: a callable function which raises under an externally set condition (an 'interrupt' flag was set). This function is/can_be used to interrupt a long-running scheduling call to do an early exit and start a new scheduling call. Default used function is noop (no-operation), thus no interruptable behaviour.
    '''
    if gridder is None:
        gridder = Gridder()
    min_earliest_possible_start_time = None
    for scheduling_unit in scheduling_units:
        raise_if_interruped()

        if scheduling_unit.scheduling_constraints_template is not None:
            earliest_possible_start_time = get_earliest_possible_start_time(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped)
            if earliest_possible_start_time is not None:
                if min_earliest_possible_start_time is None or earliest_possible_start_time < min_earliest_possible_start_time:
                    min_earliest_possible_start_time = earliest_possible_start_time
    logger.debug("get_min_earliest_possible_start_time returning '%s' for window=['%s', '%s'] and unit_ids=%s", min_earliest_possible_start_time, lower_bound, upper_bound, ','.join(str(s.id) for s in scheduling_units))
    return min_earliest_possible_start_time


def get_missing_stations_for_scheduling_unit(scheduling_unit: models.SchedulingUnitBlueprint,
                                             proposed_start_time: datetime=None) -> []:
    observation_subtasks = models.Subtask.independent_subtasks().filter(task_blueprint__scheduling_unit_blueprint_id=scheduling_unit.id).filter(specifications_template__type__value=models.SubtaskType.Choices.OBSERVATION.value).all()
    missing_stations = set()

    lower_bound = proposed_start_time or scheduling_unit.scheduled_start_time
    upper_bound = proposed_start_time+scheduling_unit.specified_observation_duration if proposed_start_time else scheduling_unit.scheduled_stop_time

    for subtask in observation_subtasks:
        for station in get_missing_stations(subtask, lower_bound, upper_bound):
            missing_stations.add(station)

    return sorted((list(set(missing_stations))))

def can_run_within_station_reservations(scheduling_unit: models.SchedulingUnitBlueprint,
                                        lower_bound: datetime=None, upper_bound: datetime=None) -> bool:
    """
    Check if the given scheduling_unit can run if the reserved stations are taken into account.
    The station requirement will be evaluated. If a reserved station is used within the time window of
    the given lower/upper_bound (scheduled_start/stop_time is used when lower/upper_bound is None) for this scheduling unit then this function will return False.
    """
    observation_subtasks = models.Subtask.independent_subtasks().filter(task_blueprint__scheduling_unit_blueprint_id=scheduling_unit.id).filter(specifications_template__type__value=models.SubtaskType.Choices.OBSERVATION.value).all()

    for subtask in observation_subtasks:
        if not enough_stations_available_for_subtask(subtask, remove_reserved_stations=True, remove_used_stations=False,
                                         lower_bound=lower_bound, upper_bound=upper_bound):
            return False

    return True

def can_run_without_used_stations(scheduling_unit: models.SchedulingUnitBlueprint,
                                  lower_bound: datetime=None, upper_bound: datetime=None) -> bool:
    """
    Check if the given scheduling_unit can run if the already used  stations are taken into account.
    The station requirement is evaluated. If a station is used within the time window of
    the given lower/upper_bound (scheduled_start/stop_time is used when lower/upper_bound is None) for this scheduling unit then this function will return False.
    """
    observation_subtasks = models.Subtask.independent_subtasks().filter(task_blueprint__scheduling_unit_blueprint_id=scheduling_unit.id).filter(specifications_template__type__value=models.SubtaskType.Choices.OBSERVATION.value).all()

    for subtask in observation_subtasks:
        if not enough_stations_available_for_subtask(subtask, remove_reserved_stations=False, remove_used_stations=True,
                                         lower_bound=lower_bound, upper_bound=upper_bound):
            return False

    return True


def get_blocking_scheduled_units(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime=None) -> QuerySet:
    return get_blocking_units(scheduling_unit, proposed_start_time, (models.SchedulingUnitStatus.Choices.SCHEDULED.value,))

def get_blocking_scheduled_or_observing_units(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime=None) -> QuerySet:
    return get_blocking_units(scheduling_unit, proposed_start_time, (models.SchedulingUnitStatus.Choices.SCHEDULED.value, models.SchedulingUnitStatus.Choices.OBSERVING.value))

def get_blocking_units(scheduling_unit: models.SchedulingUnitBlueprint, proposed_start_time: datetime = None, blocking_statuses: Iterable[str]=None) -> QuerySet:
    from .dynamic_scheduling import DEFAULT_INTER_OBSERVATION_GAP
    units = models.SchedulingUnitBlueprint.objects.filter(obsolete_since__isnull=True)

    if blocking_statuses:
        units = units.filter(status__value__in=blocking_statuses)

    lower_bound = (proposed_start_time or scheduling_unit.scheduled_observation_start_time) - DEFAULT_INTER_OBSERVATION_GAP
    upper_bound = (proposed_start_time or scheduling_unit.scheduled_observation_start_time) + scheduling_unit.relative_observation_stop_time + DEFAULT_INTER_OBSERVATION_GAP

    # do three stage filtering.
    # First in the db which is fast, but sometimes yields too many overlapping units, because we overlap the entire unit instead of just the observation part...
    overlapping_units = units.filter(scheduled_stop_time__gt=lower_bound)
    overlapping_units = overlapping_units.filter(scheduled_start_time__lt=upper_bound)

    # Second, loop over the small number of overlapping scheduled units, and only keep the ones overlapping in the observation part
    # (scheduled_observation_start/stop_time properties are not available as db columns, they are evaluated in python)
    observation_overlapping_units = [s for s in overlapping_units.all()
                                               if s.scheduled_observation_stop_time >  lower_bound and
                                               s.scheduled_observation_start_time <= upper_bound]

    # Third, loop over the small number of overlapping scheduled units, and only keep the ones sharing one or more stations
    blocking_scheduled_unit_ids = set()
    for obs_task in scheduling_unit.observation_tasks.filter(obsolete_since__isnull=True).all():
        for overlapping_scheduled_unit in observation_overlapping_units:
            for overlapping_scheduled_obs_task in overlapping_scheduled_unit.observation_tasks.all():
                if not enough_stations_available_for_task(obs_task, unavailable_stations=overlapping_scheduled_obs_task.used_stations):
                    blocking_scheduled_unit_ids.add(overlapping_scheduled_unit.id)
                    continue

    # TMSS-2610: remove the scheduling_unit id itself if it was found as a blocking unit
    if scheduling_unit.id in blocking_scheduled_unit_ids:
        blocking_scheduled_unit_ids.remove(scheduling_unit.id)

    # Finally, return the result as a queryset, so the caller can do further queries on it.
    return units.filter(id__in=[x for x in blocking_scheduled_unit_ids]).all()


def determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime, proposed_start_time: datetime=None, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> models.SchedulingUnitBlueprint:
    try:
        logger.debug("determine_unschedulable_reason_and_mark_unschedulable_if_needed: id=%s project=%s lower='%s' upper='%s' proposed_start_time='%s'", scheduling_unit.id, scheduling_unit.project.name, lower_bound, upper_bound, proposed_start_time)
        if proposed_start_time is not None:
            # only check reservations as unschedulable reason for a concrete proposed_start_time, not for a window.
            if not can_run_within_station_reservations(scheduling_unit,
                                                       lower_bound=proposed_start_time,
                                                       upper_bound=proposed_start_time+scheduling_unit.specified_observation_duration):
                missing_stations = get_missing_stations_for_scheduling_unit(scheduling_unit, proposed_start_time=proposed_start_time)
                if missing_stations:
                    msg = "Stations %s are reserved at start_time='%s'" % (','.join([str(s) for s in missing_stations]), proposed_start_time)
                    return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

        blocking_units = get_blocking_scheduled_or_observing_units(scheduling_unit)
        if blocking_units.exists():
            if len(blocking_units) == 1:
                msg = "Scheduling unit id=%s is blocking this unit from being scheduled" % (blocking_units[0].id, )
                return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)
            else:
                msg = "Scheduling units id=%s are blocking this unit from being scheduled" % (','.join(str(s.id) for s in blocking_units),)
                return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

        if not can_run_without_used_stations(scheduling_unit, lower_bound=scheduling_unit.scheduled_observation_start_time, upper_bound=scheduling_unit.scheduled_observation_stop_time):
            missing_stations = get_missing_stations_for_scheduling_unit(scheduling_unit)
            msg = "Stations %s are already used" % (','.join([str(s) for s in missing_stations]), )
            return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

        if scheduling_unit.earliest_possible_cycle_start_time is None or scheduling_unit.latest_possible_cycle_stop_time is None:
            return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, "unknown cycle bounds")

        at = get_at_constraint_timestamp(scheduling_unit)
        if at:
            if not can_run_at_within_cycles_bounds(scheduling_unit, at):
                msg = "constraint time.at='%s' falls outside of cycle bounds ['%s', '%s']" % (round_to_second_precision(at),
                                                                                              round_to_second_precision(scheduling_unit.earliest_possible_cycle_start_time),
                                                                                              round_to_second_precision(scheduling_unit.latest_possible_cycle_stop_time))
                return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

        if gridder is None:
            gridder = Gridder(Gridder.FINE_TIME_GRID)

        run_window_lower = proposed_start_time if proposed_start_time else at if at else lower_bound
        run_window_upper = proposed_start_time+scheduling_unit.specified_observation_duration if proposed_start_time else at+scheduling_unit.specified_observation_duration if at else upper_bound
        if not can_run_within_timewindow_with_constraints(scheduling_unit,
                                                          run_window_lower,
                                                          run_window_upper,
                                                          gridder, raise_if_interruped):
            logger.debug("determine_unschedulable_reason_and_mark_unschedulable_if_needed: id=%s cannot run with constraints in window [%s, %s]. Checking each constraint...",
                         scheduling_unit.id, run_window_lower, run_window_upper)

            # nope, can't run, so check each type of constraint
            unmet_constraints = []
            reasons = []

            if 'time' in scheduling_unit.scheduling_constraints_doc:
                if scheduling_unit.scheduling_constraints_doc['time'].get('between', []):
                    # recurse for each of the 'between' intervals until unschedulable
                    for between in scheduling_unit.scheduling_constraints_doc['time']['between']:
                        between_from = parser.parse(between["from"], ignoretz=True)
                        between_to = parser.parse(between["to"], ignoretz=True)
                        if between_from != lower_bound or between_to != upper_bound:
                            # recurse with this between-constraint as window
                            scheduling_unit = determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit, between_from, between_to, proposed_start_time=proposed_start_time, gridder=gridder, raise_if_interruped=raise_if_interruped)
                            if scheduling_unit.status.value == models.SchedulingUnitStatus.Choices.UNSCHEDULABLE.value:
                                return scheduling_unit

                    # the above for loop did not yield an unschedulable status.
                    # check if the proposed_start_time is within any between-window
                    if proposed_start_time is not None:
                        proposed_start_time_in_a_between_window = False
                        for between in scheduling_unit.scheduling_constraints_doc['time']['between']:
                            between_from = parser.parse(between["from"], ignoretz=True)
                            between_to = parser.parse(between["to"], ignoretz=True)
                            if proposed_start_time >= between_from and proposed_start_time <= between_to:
                                proposed_start_time_in_a_between_window = True
                                break
                        if not proposed_start_time_in_a_between_window:
                            return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, "the proposed start_time='%s' is not within any between constraint window: %s" % (proposed_start_time, ', '.join('[%s, %s]' % (b['from'], b['to']) for b in scheduling_unit.scheduling_constraints_doc['time']['between'])))

                if 'after' in scheduling_unit.scheduling_constraints_doc['time']:
                    after = parser.parse(scheduling_unit.scheduling_constraints_doc['time']['after'], ignoretz=True)
                    if after > run_window_lower:
                        # recurse with the after as new lower_bound
                        scheduling_unit = determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit, after, max(after, upper_bound), proposed_start_time=proposed_start_time, gridder=gridder, raise_if_interruped=raise_if_interruped)
                        if scheduling_unit.status.value == models.SchedulingUnitStatus.Choices.UNSCHEDULABLE.value:
                            return scheduling_unit

                if 'before' in scheduling_unit.scheduling_constraints_doc['time']:
                    before = parser.parse(scheduling_unit.scheduling_constraints_doc['time']['before'], ignoretz=True)
                    if before < datetime.utcnow():
                        return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, "constraint time.before='%s' has already passed" % (before,))

                    if before < upper_bound:
                        # recurse with the before as new upper_bound
                        scheduling_unit = determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit, min(lower_bound, before), before, proposed_start_time=proposed_start_time, gridder=gridder, raise_if_interruped=raise_if_interruped)
                        if scheduling_unit.status.value == models.SchedulingUnitStatus.Choices.UNSCHEDULABLE.value:
                            return scheduling_unit

                # check 'at' constraint
                at = get_at_constraint_timestamp(scheduling_unit)
                if at:
                    proposed_start = at
                    proposed_stop = at + scheduling_unit.specified_observation_duration
                    if proposed_start < lower_bound or proposed_stop > upper_bound:
                        msg = "constraint time.at='%s' (start='%s' stop='%s') falls outside of window ['%s', '%s']" % (round_to_second_precision(at),
                                                                                                                       round_to_second_precision(proposed_start),
                                                                                                                       round_to_second_precision(proposed_stop),
                                                                                                                       round_to_second_precision(lower_bound),
                                                                                                                       round_to_second_precision(upper_bound))
                        return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

            if 'sky' in scheduling_unit.scheduling_constraints_doc:
                if 'min_elevation' in scheduling_unit.scheduling_constraints_doc['sky']:
                    try:
                        if get_earliest_possible_start_time_for_sky_min_elevation(scheduling_unit, run_window_lower, run_window_upper, gridder, raise_if_interruped, timeout=timedelta(30)) is None:
                            result = evaluate_sky_min_elevation_constraint(scheduling_unit, run_window_lower, gridder=gridder)
                            if not result.is_constraint_met and (result.earliest_possible_start_time is None or result.earliest_possible_start_time > run_window_lower):
                                unmet_constraints.append("sky min_elevation")
                                reasons.append(result.message)
                    except TimeoutError as e:
                        unmet_constraints.append("sky min_elevation")
                        reasons.append(str(e))

                if 'transit_offset' in scheduling_unit.scheduling_constraints_doc['sky']:
                    earliest_possible_start_time = get_earliest_possible_start_time_for_sky_transit_offset(scheduling_unit, run_window_lower, run_window_upper, gridder, raise_if_interruped)
                    if earliest_possible_start_time is None or earliest_possible_start_time < run_window_lower  or earliest_possible_start_time >= run_window_upper:
                        result = evaluate_sky_transit_constraint(scheduling_unit, earliest_possible_start_time or run_window_lower, gridder=gridder)
                        if not result.is_constraint_met or result.earliest_possible_start_time is None or result.earliest_possible_start_time < run_window_lower:
                            unmet_constraints.append("sky transit_offset")
                            reasons.append(result.message)

                if 'min_distance' in scheduling_unit.scheduling_constraints_doc['sky']:
                    try:
                        if get_earliest_possible_start_time_for_sky_min_distance(scheduling_unit, run_window_lower, run_window_upper, gridder, raise_if_interruped, timeout=timedelta(30)) is None:
                            result = evaluate_sky_min_distance_constraint(scheduling_unit, run_window_lower, gridder=gridder)
                            if not result.is_constraint_met and (result.earliest_possible_start_time is None or result.earliest_possible_start_time > run_window_lower):
                                unmet_constraints.append("sky min_distance")
                                reasons.append(result.message)
                    except TimeoutError as e:
                        unmet_constraints.append("sky min_distance")
                        reasons.append(str(e))

            if 'time' in scheduling_unit.scheduling_constraints_doc:
                if get_earliest_possible_start_time_for_time_constraints(scheduling_unit, run_window_lower, run_window_upper, gridder, raise_if_interruped) is None:
                    unmet_constraints.append("time")

            if 'daily' in scheduling_unit.scheduling_constraints_doc:
                if get_earliest_possible_start_time_for_daily_constraints(scheduling_unit, run_window_lower, run_window_upper, gridder, raise_if_interruped) is None:
                    result = evaluate_daily_constraints(scheduling_unit, run_window_lower, gridder=gridder)
                    if not result.is_constraint_met and (result.earliest_possible_start_time is None or result.earliest_possible_start_time > run_window_lower):
                        unmet_constraints.append("daily")
                        reasons.append(result.message)

            if unmet_constraints:
                at = get_at_constraint_timestamp(scheduling_unit)
                msg = ', '.join(unmet_constraints) + (" constraint is" if len(unmet_constraints)==1 else " constraints are") + " not met " + ("at '%s'" % (round_to_second_precision(at),) if at else "anywhere between '%s' and '%s'" % (round_to_second_precision(lower_bound), round_to_second_precision(upper_bound)))
                reasons = [r for r in reasons if isinstance(r, str) and len(r)]
                if reasons:
                    msg += '\nreason(s):\n * ' + '\n * '.join(reasons)
                mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)
            else:
                if proposed_start_time is not None:
                    mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, "sorry, unknown unschedulable reason.")
                # else recurse, see below

    except SchedulerInterruptedException:
        raise
    except Exception as e:
        logger.exception(e)
        mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, str(e))

    if proposed_start_time is None:
        # recurse, let's try to determine a reason with the scheduling_unit's scheduled_starttime
        return determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit, lower_bound,
                                                                               upper_bound,
                                                                               proposed_start_time=scheduling_unit.scheduled_start_time,
                                                                               gridder=gridder,
                                                                               raise_if_interruped=raise_if_interruped)

    scheduling_unit.refresh_from_db()
    return scheduling_unit




def wipe_evaluate_constraints_caches():
    '''wipe the evaluate_*constraints caches'''
    # TODO: in TMSS-1980 the function calls are/shouldbe replaced with SU id and SU constraints as arguments. Then the cache does not need to be wiped anymore.
    evaluate_daily_constraints.cache_clear()
    evaluate_sky_transit_constraint.cache_clear()
    evaluate_sky_min_elevation_constraint.cache_clear()
    evaluate_sky_min_distance_constraint.cache_clear()

    get_earliest_possible_start_time_for_daily_constraints.cache_clear()
    get_earliest_possible_start_time_for_sky_min_distance.cache_clear()
    get_earliest_possible_start_time_for_sky_min_elevation.cache_clear()

    get_boundary_stations_from_list.cache_clear()
    get_unique_sorted_boundary_stations_or_cs002.cache_clear()
    get_unique_sorted_boundary_stations_and_cs002.cache_clear()
    get_schedulable_stations.cache_clear()