#!/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
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, get_missing_stations
from lofar.sas.tmss.tmss.tmssapp.tasks import mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable, get_schedulable_stations

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 ScoredSchedulingUnit():
    '''struct for collecting scores per constraint and a weighted_score for a scheduling_unit at the given start_time
    '''
    def __init__(self, scheduling_unit: models.SchedulingUnitBlueprint, scores: dict, start_time: datetime, weighted_score: float=0):
        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)
        self.scheduling_unit = scheduling_unit
        self.scores = scores
        self.start_time = start_time
        self.weighted_score = weighted_score

    def __str__(self):
        return "SUB id=%s start='%s' weighted_score=%.4f scores: %s" % (
                     self.scheduling_unit.id,
                     self.start_time,
                     self.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.lta.sip 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()["%s_LBA" % station.upper()]
        loc = EarthLocation.from_geocentric(x=coords['x'], y=coords['y'], z=coords['z'],  unit=astropy.units.m)
        if not min_lat or loc.lat < min_lat:
            min_lat = loc.lat
            most_southern = station
        if not max_lat or loc.lat > max_lat:
            max_lat = loc.lat
            most_northern = station
        if not min_lon or loc.lon < min_lon:
            min_lon = loc.lon
            most_western = station
        if not max_lon 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_or_cs002(stations: Tuple[str], min_distance: float=None) -> Tuple[str]:
    '''
    Get a tuple of unique boundary stations, or only the center core station cs002.
    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.lta.sip import station_coordinates
        locations = {}
        for station in boundary_stations:
            coords = station_coordinates.parse_station_coordinates()["%s_LBA" % 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

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

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)

            if can_run_within_station_reservations(scheduling_unit, lower_bound=lower_bound, upper_bound=upper_bound):
                if can_run_within_timewindow_with_constraints(scheduling_unit, lower_bound, upper_bound, unit_gridder):
                    if can_run_within_cycles_bounds(scheduling_unit, lower_bound, upper_bound):
                        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']",
                        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)
        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_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.info("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
    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())

    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, coarse_gridder: Gridder, fine_gridder: Gridder, 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.
    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()

    # 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)

    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)

        # Re-evaluate top 5(or less) with fine grid
        top_sorted_scored_scheduling_units_coarse = sorted_scored_scheduling_units_coarse[:5]
        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 te 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)

            # 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) -> [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_individual_and_weighted_scores(scheduling_units, lower_bound_start_time, upper_bound_stop_time, gridder)

    unstartable_scheduling_units = [sssu for sssu in scored_scheduling_units if sssu.start_time is None]
    if unstartable_scheduling_units:
        logger.warning("unstartable_scheduling_units: %s", ','.join([x.scheduling_unit.id for x in unstartable_scheduling_units]))

    # 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 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()

    # 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 'after' in constraints['time']:
        start_after = parser.parse(constraints['time']['after'], ignoretz=True)
        return start_after >= proposed_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_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


    # 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 = task_proposed_start_time + (target_obs_task.specified_duration / 2)

        stations = get_schedulable_stations(target_obs_task, task_proposed_start_time)
        stations = get_unique_sorted_boundary_stations_or_cs002(stations, 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])
                logger.debug("SUB id=%s transit='%s' for %s %s", scheduling_unit.id, transit_timestamp, station, pointing)

                # 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

        # limit stations to be evaluated to the edge stations
        stations = get_schedulable_stations(task, proposed_start_time)
        stations = get_unique_sorted_boundary_stations_or_cs002(stations, 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 not rise_and_set_time['always_below_horizon']:
                        # 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['rise'] or proposed_start_time
                        if result.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['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 = "task_id=%s task_name='%s' station=%s target='%s' elevation=%.3f[deg] < min_elevation=%.3f[deg] at '%s'" % (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)
    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 = "lowest_elevation=%.3f[deg] < min_elevation=%.3f[deg] at '%s' over all target observations, stations & pointings" % (
                          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("lowest_elevation=%.3f[deg] >= min_elevation=%.3f[deg] at '%s' over all target observations, stations & pointings" % (
                  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 = min(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_schedulable_stations(obs_task, timestamp)
    stations = get_unique_sorted_boundary_stations_or_cs002(stations, 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

    # 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)

                    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

        # ToDo: compute score based on actual distance at earliest/optimal timestamp
        # for now, just use a score=1 (it's far enough away)
        result.score = 1

        # 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) -> 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

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

        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:
            return None

        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:
            return None

        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 evaulation 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 += 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) -> 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)

    while possible_start_time < upper_bound:
        raise_if_interruped()

        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:
            return None

        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_schedulable_stations(scheduling_unit.main_observation_task, proposed_start_time)
    stations = get_unique_sorted_boundary_stations_or_cs002(stations, 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
    # start with earliest_possible_start_time = min
    # find latest (max) earliest_possible_start_time looping over all stations
    result.earliest_possible_start_time = datetime.min

    for station in stations:
        sun_events = all_sun_events[station]
        for event_name, event in list(sun_events.items()):
            if len(event) < len(timestamps):
                logger.warning("get_earliest_possible_start_time for SUB id=%s: not all %s events could be computed for station %s lower_bound=%s.", scheduling_unit.id, event_name, station, proposed_start_time)
                # use datetime.max as defaults, which have no influence on getting an earliest start_time
                sun_events[event_name] = [{'start': datetime.max, 'end': datetime.max} for _ in timestamps]
        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)
            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)
            else:
                result.score = 0
                result.earliest_possible_start_time = max(day['start'], result.earliest_possible_start_time)

        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)
            elif proposed_end_time > gridder.minus_margin(prev_night['end']):
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time)
                result.score = 0
            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)
            else:
                result.earliest_possible_start_time = max(night['start'], result.earliest_possible_start_time)

        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)
            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)
            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)
            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)
            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)
            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)
            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)
            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)
            else:
                result.score = 0


    if result.earliest_possible_start_time == datetime.min:
        # No start possible at any station. Set to None.
        result.earliest_possible_start_time = None

    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:
            return None

        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]
            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:
        earliest_possible_start_times = [t for t in earliest_possible_start_times if t <= upper_bound]

    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(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_min_elevation,
                                                    get_earliest_possible_start_time_for_sky_transit_offset,
                                                    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 not None:
                earliest_possible_start_times.add(earliest_possible_start_time)
        except SchedulerInterruptedException:
            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, always add lower_bound, and evaluate it below (along with the other possible earliest_possible_start_times) if it can actually run.
        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:
        earliest_possible_start_times = set([t for t in earliest_possible_start_times if t <= upper_bound])
    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

    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, upper_bound))

    return upper_bound - scheduling_unit.specified_observation_duration

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 get_weighted_start_time(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound:datetime, gridder: Gridder) -> datetime:
    '''get a weighted start_time balanced between the earliest_possible_start_time and the optimal_start_time.'''
    at = get_at_constraint_timestamp(scheduling_unit)
    if at:
        return at

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

    if earliest_possible_start_time is not None:
        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)

        # get the optimal_start_time with the earliest_possible_start_time as lower_bound
        optimal_start_time = get_optimal_start_time(scheduling_unit, earliest_possible_start_time, gridder=gridder)

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

            # 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(
                scheduling_constraints_template=scheduling_unit.scheduling_constraints_template,
                constraint_name='density_vs_optimal',
                defaults={'weight': 0.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)

            logger.debug("get_weighted_start_time: SUB id=%s weight=%.3f earliest='%s' optimal='%s' weighted='%s'", scheduling_unit.id, density_vs_optimal.weight, earliest_possible_start_time, optimal_start_time, weighted_start_time)
            return weighted_start_time

        logger.debug("get_weighted_start_time: SUB id=%s returning earliest='%s' because optimal is None", scheduling_unit.id, earliest_possible_start_time)
        return earliest_possible_start_time

    logger.debug("get_weighted_start_time: SUB id=%s could not compute weighted_start_time", scheduling_unit.id)
    return None


def compute_individual_and_weighted_scores(scheduling_units: [models.SchedulingUnitBlueprint], lower_bound:datetime, upper_bound:datetime, gridder: Gridder=None) -> [ScoredSchedulingUnit]:
    if gridder is None:
        gridder = Gridder()

    scored_scheduling_units = []
    for i, su in enumerate(scheduling_units):
        try:
            unit_gridder = fine_enough_gridder(su, gridder)

            scored_su = compute_scheduling_unit_scores(su, lower_bound, upper_bound, unit_gridder)
            if scored_su is not None and scored_su.start_time is not None:
                scored_scheduling_units.append(scored_su)

            logger.info("compute_individual_and_weighted_scores: checked unit [%d/%d] %.1f%% id=%d",
                        i+1, len(scheduling_units), 100.0 * (i+1) / len(scheduling_units), su.id)

        except Exception as e:
            logger.exception(e)

    # compute weighted total score
    for scored_scheduling_unit in sorted(scored_scheduling_units, key=lambda x: x.scheduling_unit.id):
        scored_scheduling_unit.weighted_score = 0.0
        count = len(scored_scheduling_unit.scores)
        if count > 0:
            weighted_score = 0.0
            for score_key, score_value in scored_scheduling_unit.scores.items():
                weight_factor, created = models.SchedulingConstraintsWeightFactor.objects.get_or_create(scheduling_constraints_template=scored_scheduling_unit.scheduling_unit.scheduling_constraints_template,
                                                                                                        constraint_name=score_key,
                                                                                                        defaults={'weight': 1.0})

                weighted_score += weight_factor.weight * score_value

            scored_scheduling_unit.weighted_score = weighted_score / float(count)
            logger.debug("computed (weighted) score(s): %s", scored_scheduling_unit)

    return scored_scheduling_units

def compute_scheduling_unit_scores(scheduling_unit: models.SchedulingUnitBlueprint, 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 = {}

    # add individual scheduling_unit rank: rank is "inverse", meaning that a lower value is better. also, normalize it.
    scores['scheduling_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)

    weighted_start_time = get_weighted_start_time(scheduling_unit, lower_bound, upper_bound, gridder=gridder)
    if weighted_start_time is None:
        return ScoredSchedulingUnit(scheduling_unit=scheduling_unit,
                                    scores={},
                                    weighted_score=0,
                                    start_time=None)

    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 - weighted_start_time).total_seconds()) < 60 else 0.0

    # 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-weighted_start_time).total_seconds() / (upper_bound-lower_bound).total_seconds()))

    # compute/get scores per constraint type
    gridded_weighted_start_time = gridder.grid_time(weighted_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, gridder)
        if result.is_constraint_met:
            scores[result.constraint_key] = result.score

    return ScoredSchedulingUnit(scheduling_unit=scheduling_unit,
                                scores=scores,
                                # return the actual (not the gridded) weighted_start_time
                                start_time=weighted_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
    return min_earliest_possible_start_time


def get_missing_stations_for_scheduling_unit(scheduling_unit: models.SchedulingUnitBlueprint) -> []:
    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()

    for subtask in observation_subtasks:
        for station in get_missing_stations(subtask):
            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(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(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:
    '''Get a list (tuple) of scheduled scheduling_units overlapping with the scheduled_observation_start/stop_time of the given scheduling_unit'''
    from .dynamic_scheduling import DEFAULT_INTER_OBSERVATION_GAP
    scheduled_units = models.SchedulingUnitBlueprint.objects.filter(status__value=models.SchedulingUnitStatus.Choices.SCHEDULED.value)

    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_scheduled_units = scheduled_units.filter(scheduled_stop_time__gt=lower_bound)
    overlapping_scheduled_units = overlapping_scheduled_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_scheduled_units = [s for s in overlapping_scheduled_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
    candidate_stations = set(scheduling_unit.main_observation_stations)
    observation_overlapping_scheduled_units = [s for s in observation_overlapping_scheduled_units
                                               if any(set(s.main_observation_stations).intersection(candidate_stations))]

    # Finally, return the result as a queryset, so the caller can do furter queries on it.
    return scheduled_units.filter(id__in=[s.id for s in observation_overlapping_scheduled_units]).all()


def determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit: models.SchedulingUnitBlueprint, lower_bound: datetime, upper_bound: datetime, gridder: Gridder=None, raise_if_interruped: Callable=noop) -> models.SchedulingUnitBlueprint:
    try:
        logger.debug("determine_unschedulable_reason_and_mark_unschedulable_if_needed: scheduling_unit id=%s", scheduling_unit.id)
        if not can_run_within_station_reservations(scheduling_unit, lower_bound=lower_bound, upper_bound=upper_bound):
            missing_stations = get_missing_stations_for_scheduling_unit(scheduling_unit)
            msg = "Stations %s are reserved" % (','.join([str(s) for s in missing_stations]), )
            return mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)

        blocking_units = get_blocking_scheduled_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)

        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()

        if not can_run_within_timewindow_with_constraints(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped):
            # 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:
                            scheduling_unit = determine_unschedulable_reason_and_mark_unschedulable_if_needed(scheduling_unit, between_from, between_to, gridder)
                            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)

                    # use the 'at' timestamp as bounds for the remaining checks below
                    lower_bound = proposed_start
                    upper_bound = proposed_stop

            if 'sky' in scheduling_unit.scheduling_constraints_doc:
                if 'min_elevation' in scheduling_unit.scheduling_constraints_doc['sky']:
                    if get_earliest_possible_start_time_for_sky_min_elevation(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped) is None:
                        unmet_constraints.append("sky min_elevation")
                        result = evaluate_sky_min_elevation_constraint(scheduling_unit, lower_bound, gridder=gridder)
                        reasons.append(result.message)

                if 'transit_offset' in scheduling_unit.scheduling_constraints_doc['sky']:
                    if get_earliest_possible_start_time_for_sky_transit_offset(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped) is None:
                        unmet_constraints.append("sky transit_offset")
                        result = evaluate_sky_transit_constraint(scheduling_unit, lower_bound, gridder=gridder)
                        reasons.append(result.message)

                if 'min_distance' in scheduling_unit.scheduling_constraints_doc['sky']:
                    if get_earliest_possible_start_time_for_sky_min_distance(scheduling_unit, lower_bound, upper_bound, gridder, raise_if_interruped) is None:
                        unmet_constraints.append("sky min_distance")
                        result = evaluate_sky_min_distance_constraint(scheduling_unit, lower_bound, gridder=gridder)
                        reasons.append(result.message)

            if 'time' in scheduling_unit.scheduling_constraints_doc:
                if get_earliest_possible_start_time_for_time_constraints(scheduling_unit, lower_bound, upper_bound, 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, lower_bound, upper_bound, gridder, raise_if_interruped) is None:
                    unmet_constraints.append("daily")
                    result = evaluate_daily_constraints(scheduling_unit, lower_bound, gridder=gridder)
                    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'.join(reasons)
                mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, msg)
            else:
                mark_independent_subtasks_in_scheduling_unit_blueprint_as_unschedulable(scheduling_unit, "sorry, unknown unschedulable reason.")

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

    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_schedulable_stations.cache_clear()