TimeSpanMap.java

/* Copyright 2002-2022 CS GROUP
 * Licensed to CS GROUP (CS) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * CS licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.orekit.utils;

import java.util.NavigableSet;
import java.util.TreeSet;
import java.util.function.Consumer;

import org.orekit.time.AbsoluteDate;
import org.orekit.time.ChronologicalComparator;
import org.orekit.time.TimeStamped;

/** Container for objects that apply to spans of time.
 * <p>
 * Time span maps can be seen either as an ordered collection of
 * {@link Span time spans} or as an ordered collection
 * of {@link Transition transitions}. Both views are dual one to
 * each other. A time span extends from one transition to the
 * next one, and a transition separates one time span from the
 * next one. Each time span contains one entry that is valid during
 * the time span; this entry may be null if nothing is valid during
 * this time span.
 * </p>
 * <p>
 * Typical uses of {@link TimeSpanMap} are to hold piecewise data, like for
 * example an orbit count that changes at ascending nodes (in which case the
 * entry would be an {@link Integer}), or a visibility status between several
 * objects (in which case the entry would be a {@link Boolean}) or a drag
 * coefficient that is expected to be estimated daily or three-hourly (this is
 * how {@link org.orekit.forces.drag.TimeSpanDragForce TimeSpanDragForce} is
 * implemented).
 * </p>
 * <p>
 * Time span maps are built progressively. At first, they contain one
 * {@link Span time span} only whose validity extends from past infinity to
 * future infinity. Then new entries are added one at a time, associated with
 * transition dates, in order to build up the complete map. The transition dates
 * can be either the start of validity (when calling {@link #addValidAfter(Object,
 * AbsoluteDate, boolean)}), or the end of the validity (when calling {@link
 * #addValidBefore(Object, AbsoluteDate, boolean)}). Entries are often added at one
 * end only (and mainly in chronological order), but this is not required. It is
 * possible for example to first set up a map that cover a large range (say one day),
 * and then to insert intermediate dates using for example propagation and event
 * detectors to carve out some parts. This is akin to the way Binary Space Partitioning
 * Trees work.
 * </p>
 * <p>
 * Since 11.1, this class is thread-safe
 * </p>
 * @param <T> Type of the data.
 * @author Luc Maisonobe
 * @since 7.1
 */
public class TimeSpanMap<T> {

    /** Reference to last accessed data. */
    private Span<T> current;

    /** Number of time spans. */
    private int nbSpans;

    /** Create a map containing a single object, initially valid throughout the timeline.
     * <p>
     * The real validity of this first entry will be truncated as other
     * entries are either {@link #addValidBefore(Object, AbsoluteDate, boolean)
     * added before} it or {@link #addValidAfter(Object, AbsoluteDate, boolean)
     * added after} it.
     * </p>
     * @param entry entry (initially valid throughout the timeline)
     */
    public TimeSpanMap(final T entry) {
        current = new Span<>(entry);
        nbSpans = 1;
    }

    /** Get the number of spans.
     * <p>
     * The number of spans is always at least 1. The number of transitions
     * is always 1 less than the number of spans.
     * </p>
     * @return number of spans
     * @since 11.1
     */
    public synchronized int getSpansNumber() {
        return nbSpans;
    }

    /** Add an entry valid before a limit date.
     * <p>
     * Calling this method is equivalent to call {@link #addValidAfter(Object,
     * AbsoluteDate, boolean) addValidAfter(entry, latestValidityDate, false)}.
     * </p>
     * @param entry entry to add
     * @param latestValidityDate date before which the entry is valid
     * @deprecated as of 11.1, replaced by {@link #addValidBefore(Object, AbsoluteDate, boolean)}
     */
    @Deprecated
    public void addValidBefore(final T entry, final AbsoluteDate latestValidityDate) {
        addValidBefore(entry, latestValidityDate, false);
    }

    /** Add an entry valid before a limit date.
     * <p>
     * As an entry is valid, it truncates or overrides the validity of the neighboring
     * entries already present in the map.
     * </p>
     * <p>
     * If the map already contains transitions that occur earlier than {@code latestValidityDate},
     * the {@code erasesEarlier} parameter controls what to do with them. Lets consider
     * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
     * {@code latestValidityDate} prior to the call to the method (i.e. tₖ &lt;
     * {@code latestValidityDate} &lt; tₖ₊₁).
     * </p>
     * <ul>
     *  <li>if {@code erasesEarlier} is {@code true}, then all earlier transitions
     *      up to and including tₖ are erased, and the {@code entry} will be valid from past infinity
     *      to {@code latestValidityDate}</li>
     *  <li>if {@code erasesEarlier} is {@code false}, then all earlier transitions
     *      are preserved, and the {@code entry} will be valid from tₖ
     *      to {@code latestValidityDate}</li>
     *  </ul>
     * <p>
     * In both cases, the existing entry eₖ time span will be truncated and will be valid
     * only from {@code latestValidityDate} to tₖ₊₁.
     * </p>
     * @param entry entry to add
     * @param latestValidityDate date before which the entry is valid
     * @param erasesEarlier if true, the entry erases all existing transitions
     * that are earlier than {@code latestValidityDate}
     * @return span with added entry
     * @since 11.1
     */
    public synchronized Span<T> addValidBefore(final T entry, final AbsoluteDate latestValidityDate, final boolean erasesEarlier) {

        // update current reference to transition date
        locate(latestValidityDate);

        if (erasesEarlier) {

            // drop everything before date
            current.start = null;

            // update count
            nbSpans = 0;
            for (Span<T> span = current; span != null; span = span.next()) {
                ++nbSpans;
            }

        }

        final Span<T> span = new Span<>(entry);

        final Transition<T> start = current.getStartTransition();
        if (start != null && start.getDate().equals(latestValidityDate)) {
            // the transition at start of the current span is at the exact same date
            // we update it, without adding a new transition
            if (start.previous() != null) {
                start.previous().setAfter(span);
            }
            start.setBefore(span);
        } else {

            if (current.getStartTransition() != null) {
                current.getStartTransition().setAfter(span);
            }

            // we need to add a new transition somewhere inside the current span
            insertTransition(latestValidityDate, span, current);

        }

        // we consider the last added transition as the new current one
        current = span;

        return span;

    }

    /** Add an entry valid after a limit date.
     * <p>
     * Calling this method is equivalent to call {@link #addValidAfter(Object,
     * AbsoluteDate, boolean) addValidAfter(entry, earliestValidityDate, false)}.
     * </p>
     * @param entry entry to add
     * @param earliestValidityDate date after which the entry is valid
     * @deprecated as of 11.1, replaced by {@link #addValidAfter(Object, AbsoluteDate, boolean)}
     */
    @Deprecated
    public void addValidAfter(final T entry, final AbsoluteDate earliestValidityDate) {
        addValidAfter(entry, earliestValidityDate, false);
    }

    /** Add an entry valid after a limit date.
     * <p>
     * As an entry is valid, it truncates or overrides the validity of the neighboring
     * entries already present in the map.
     * </p>
     * <p>
     * If the map already contains transitions that occur earlier than {@code earliestValidityDate},
     * the {@code erasesEarlier} parameter controls what to do with them. Lets consider
     * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
     * {@code earliestValidityDate} prior to the call to the method (i.e. tₖ &lt;
     * {@code earliestValidityDate} &lt; tₖ₊₁).
     * </p>
     * <ul>
     *  <li>if {@code erasesEarlier} is {@code true}, then all earlier transitions
     *      up to and including tₖ are erased, and the {@code entry} will be valid from past infinity
     *      to {@code earliestValidityDate}</li>
     *  <li>if {@code erasesEarlier} is {@code false}, then all earlier transitions
     *      are preserved, and the {@code entry} will be valid from tₖ
     *      to {@code earliestValidityDate}</li>
     *  </ul>
     * <p>
     * In both cases, the existing entry eₖ time span will be truncated and will be valid
     * only from {@code earliestValidityDate} to tₖ₊₁.
     * </p>
     * @param entry entry to add
     * @param earliestValidityDate date after which the entry is valid
     * @param erasesLater if true, the entry erases all existing transitions
     * that are later than {@code earliestValidityDate}
     * @return span with added entry
     * @since 11.1
     */
    public synchronized Span<T> addValidAfter(final T entry, final AbsoluteDate earliestValidityDate, final boolean erasesLater) {

        // update current reference to transition date
        locate(earliestValidityDate);

        if (erasesLater) {

            // drop everything after date
            current.end = null;

            // update count
            nbSpans = 0;
            for (Span<T> span = current; span != null; span = span.previous()) {
                ++nbSpans;
            }

        }

        final Span<T> span = new Span<>(entry);
        if (current.getEndTransition() != null) {
            current.getEndTransition().setBefore(span);
        }

        final Transition<T> start = current.getStartTransition();
        if (start != null && start.getDate().equals(earliestValidityDate)) {
            // the transition at start of the current span is at the exact same date
            // we update it, without adding a new transition
            start.setAfter(span);
        } else {
            // we need to add a new transition somewhere inside the current span
            insertTransition(earliestValidityDate, current, span);
        }

        // we consider the last added transition as the new current one
        current = span;

        return span;

    }

    /** Add an entry valid between two limit dates.
     * <p>
     * As an entry is valid, it truncates or overrides the validity of the neighboring
     * entries already present in the map.
     * </p>
     * @param entry entry to add
     * @param earliestValidityDate date after which the entry is valid
     * @param latestValidityDate date before which the entry is valid
     * @return span with added entry
     * @since 11.1
     */
    public synchronized Span<T> addValidBetween(final T entry, final AbsoluteDate earliestValidityDate, final AbsoluteDate latestValidityDate) {

        // handle special cases
        if (AbsoluteDate.PAST_INFINITY.equals(earliestValidityDate)) {
            if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
                // we wipe everything in the map
                current = new Span<>(entry);
                return current;
            } else {
                // we wipe from past infinity
                return addValidBefore(entry, latestValidityDate, true);
            }
        } else if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
            // we wipe up to future infinity
            return addValidAfter(entry, earliestValidityDate, true);
        } else {

            // locate spans at earliest and latest dates
            locate(earliestValidityDate);
            Span<T> latest = current;
            while (latest.getEndTransition() != null && latest.getEnd().isBeforeOrEqualTo(latestValidityDate)) {
                latest = latest.next();
                --nbSpans;
            }
            if (latest == current) {
                // the interval splits one transition in the middle, we need to duplicate the instance
                latest = new Span<>(current.data);
                if (current.getEndTransition() != null) {
                    current.getEndTransition().setBefore(latest);
                }
            }

            final Span<T> span = new Span<>(entry);

            // manage earliest transition
            final Transition<T> start = current.getStartTransition();
            if (start != null && start.getDate().equals(earliestValidityDate)) {
                // the transition at start of the current span is at the exact same date
                // we update it, without adding a new transition
                start.setAfter(span);
            } else {
                // we need to add a new transition somewhere inside the current span
                insertTransition(earliestValidityDate, current, span);
            }

            // manage latest transition
            insertTransition(latestValidityDate, span, latest);

            // we consider the last added transition as the new current one
            current = span;

            return span;

        }

    }

    /** Get the entry valid at a specified date.
     * <p>
     * The expected complexity is O(1) for successive calls with
     * neighboring dates, which is the more frequent use in propagation
     * or orbit determination applications, and O(n) for random calls.
     * </p>
     * @param date date at which the entry must be valid
     * @return valid entry at specified date
     * @see #getSpan(AbsoluteDate)
     */
    public synchronized T get(final AbsoluteDate date) {
        return getSpan(date).getData();
    }

    /** Get the time span containing a specified date.
     * <p>
     * The expected complexity is O(1) for successive calls with
     * neighboring dates, which is the more frequent use in propagation
     * or orbit determination applications, and O(n) for random calls.
     * </p>
     * @param date date belonging to the desired time span
     * @return time span containing the specified date
     * @since 9.3
     */
    public synchronized Span<T> getSpan(final AbsoluteDate date) {
        locate(date);
        return current;
    }

    /** Locate the time span containing a specified date.
     * <p>
     * The {@link current} field is updated to the located span.
     * After the method returns, {@code current.getStartTransition()} is either
     * null or its date is before or equal to date, and {@code
     * current.getEndTransition()} is either null or its date is after date.
     * </p>
     * @param date date belonging to the desired time span
     */
    private synchronized void locate(final AbsoluteDate date) {

        while (current.getStart().isAfter(date)) {
            // current span is too late
            current = current.previous();
        }

        while (current.getEnd().isBeforeOrEqualTo(date)) {

            final Span<T> next = current.next();
            if (next == null) {
                // this happens when date is FUTURE_INFINITY
                return;
            }

            // current span is too early
            current = next;

        }

    }

    /** Insert a transition.
     * @param date transition date
     * @param before span before transition
     * @param after span after transition
     * @since 11.1
     */
    private void insertTransition(final AbsoluteDate date, final Span<T> before, final Span<T> after) {
        final Transition<T> transition = new Transition<>(date);
        transition.setBefore(before);
        transition.setAfter(after);
        ++nbSpans;
    }

    /** Get the first (earliest) transition.
     * @return first (earliest) transition, or null if there are no transitions
     * @since 11.1
     */
    public synchronized Transition<T> getFirstTransition() {
        return getFirstSpan().getEndTransition();
    }

    /** Get the last (latest) transition.
     * @return last (latest) transition, or null if there are no transitions
     * @since 11.1
     */
    public synchronized Transition<T> getLastTransition() {
        return getLastSpan().getStartTransition();
    }

    /** Get the first (earliest) span.
     * @return first (earliest) span
     * @since 11.1
     */
    public synchronized Span<T> getFirstSpan() {
        Span<T> span = current;
        while (span.getStartTransition() != null) {
            span = span.previous();
        }
        return span;
    }

    /** Get the last (latest) span.
     * @return last (latest) span
     * @since 11.1
     */
    public synchronized Span<T> getLastSpan() {
        Span<T> span = current;
        while (span.getEndTransition() != null) {
            span = span.next();
        }
        return span;
    }

    /** Extract a range of the map.
     * <p>
     * The object returned will be a new independent instance that will contain
     * only the transitions that lie in the specified range.
     * </p>
     * <p>
     * Consider for example a map containing objects O₀ valid before t₁, O₁ valid
     * between t₁ and t₂, O₂ valid between t₂ and t₃, O₃ valid between t₃ and t₄,
     * and O₄ valid after t₄. then calling this method with a {@code start}
     * date between t₁ and t₂ and a {@code end} date between t₃ and t₄
     * will result in a new map containing objects O₁ valid before t₂, O₂
     * valid between t₂ and t₃, and O₃ valid after t₃. The validity of O₁
     * is therefore extended in the past, and the validity of O₃ is extended
     * in the future.
     * </p>
     * @param start earliest date at which a transition is included in the range
     * (may be set to {@link AbsoluteDate#PAST_INFINITY} to keep all early transitions)
     * @param end latest date at which a transition is included in the r
     * (may be set to {@link AbsoluteDate#FUTURE_INFINITY} to keep all late transitions)
     * @return a new instance with all transitions restricted to the specified range
     * @since 9.2
     */
    public synchronized TimeSpanMap<T> extractRange(final AbsoluteDate start, final AbsoluteDate end) {

        Span<T> span = getSpan(start);
        final TimeSpanMap<T> range = new TimeSpanMap<>(span.getData());
        while (span.getEndTransition() != null && span.getEndTransition().getDate().isBeforeOrEqualTo(end)) {
            span = span.next();
            range.addValidAfter(span.getData(), span.getStartTransition().getDate(), false);
        }

        return range;

    }

    /** Get copy of the sorted transitions.
     * @return copy of the sorted transitions
     * @deprecated as of 11.1, replaced by {@link #getFirstSpan()}, {@link #getLastSpan()},
     * {@link #getFirstTransition()}, {@link #getLastTransition()}, and {@link #getSpansNumber()}
     */
    @Deprecated
    public synchronized NavigableSet<Transition<T>> getTransitions() {
        final NavigableSet<Transition<T>> set = new TreeSet<>(new ChronologicalComparator());
        for (Transition<T> transition = getFirstTransition(); transition != null; transition = transition.next()) {
            set.add(transition);
        }
        return set;
    }

    /**
     * Performs an action for each non-null element of map.
     * <p>
     * The action is performed chronologically.
     * </p>
     * @param action action to perform on the non-null elements
     * @since 10.3
     */
    public synchronized void forEach(final Consumer<T> action) {
        for (Span<T> span = getFirstSpan(); span != null; span = span.next()) {
            if (span.getData() != null) {
                action.accept(span.getData());
            }
        }
    }

    /** Class holding transition times.
     * <p>
     * This data type is dual to {@link Span}, it is
     * focused on one transition date, and gives access to
     * surrounding valid data whereas {@link Span} is focused
     * on one valid data, and gives access to surrounding
     * transition dates.
     * </p>
     * @param <S> Type of the data.
     */
    public static class Transition<S> implements TimeStamped {

        /** Transition date. */
        private AbsoluteDate date;

        /** Entry valid before the transition. */
        private Span<S> before;

        /** Entry valid after the transition. */
        private Span<S> after;

        /** Simple constructor.
         * @param date transition date
         */
        private Transition(final AbsoluteDate date) {
            this.date = date;
        }

        /** Set the span valid before transition.
         * @param before span valid before transition (must be non-null)
         */
        void setBefore(final Span<S> before) {
            this.before = before;
            before.end  = this;
        }

        /** Set the span valid after transition.
         * @param after span valid after transition (must be non-null)
         */
        void setAfter(final Span<S> after) {
            this.after  = after;
            after.start = this;
        }

        /** Get the transition date.
         * @return transition date
         */
        @Override
        public AbsoluteDate getDate() {
            return date;
        }

        /** Get the previous transition.
         * @return previous transition, or null if this transition was the first one
         * @since 11.1
         */
        public Transition<S> previous() {
            return before.getStartTransition();
        }

        /** Get the next transition.
         * @return next transition, or null if this transition was the last one
         * @since 11.1
         */
        public Transition<S> next() {
            return after.getEndTransition();
        }

        /** Get the entry valid before transition.
         * @return entry valid before transition
         * @see #getSpanBefore()
         */
        public S getBefore() {
            return before.getData();
        }

        /** Get the {@link Span} valid before transition.
         * @return {@link Span} valid before transition
         * @since 11.1
         */
        public Span<S> getSpanBefore() {
            return before;
        }

        /** Get the entry valid after transition.
         * @return entry valid after transition
         * @see #getSpanAfter()
         */
        public S getAfter() {
            return after.getData();
        }

        /** Get the {@link Span} valid after transition.
         * @return {@link Span} valid after transition
         * @since 11.1
         */
        public Span<S> getSpanAfter() {
            return after;
        }

    }

    /** Holder for one time span.
     * <p>
     * This data type is dual to {@link Transition}, it
     * is focused on one valid data, and gives access to
     * surrounding transition dates whereas {@link Transition}
     * is focused on one transition date, and gives access to
     * surrounding valid data.
     * </p>
     * @param <S> Type of the data.
     * @since 9.3
     */
    public static class Span<S> {

        /** Valid data. */
        private final S data;

        /** Start of validity for the data (null if span extends to past infinity). */
        private Transition<S> start;

        /** End of validity for the data (null if span extends to future infinity). */
        private Transition<S> end;

        /** Simple constructor.
         * @param data valid data
         */
        private Span(final S data) {
            this.data = data;
        }

        /** Get the data valid during this time span.
         * @return data valid during this time span
         */
        public S getData() {
            return data;
        }

        /** Get the previous time span.
         * @return previous time span, or null if this time span was the first one
         * @since 11.1
         */
        public Span<S> previous() {
            return start == null ? null : start.getSpanBefore();
        }

        /** Get the next time span.
         * @return next time span, or null if this time span was the last one
         * @since 11.1
         */
        public Span<S> next() {
            return end == null ? null : end.getSpanAfter();
        }

        /** Get the start of this time span.
         * @return start of this time span (will be {@link AbsoluteDate#PAST_INFINITY}
         * if {@link #getStartTransition()} returns null)
         * @see #getStartTransition()
         */
        public AbsoluteDate getStart() {
            return start == null ? AbsoluteDate.PAST_INFINITY : start.getDate();
        }

        /** Get the transition at start of this time span.
         * @return transition at start of this time span (null if span extends to past infinity)
         * @see #getStart()
         * @since 11.1
         */
        public Transition<S> getStartTransition() {
            return start;
        }

        /** Get the end of this time span.
         * @return end of this time span (will be {@link AbsoluteDate#FUTURE_INFINITY}
         * if {@link #getEndTransition()} returns null)
         * @see #getEndTransition()
         */
        public AbsoluteDate getEnd() {
            return end == null ? AbsoluteDate.FUTURE_INFINITY : end.getDate();
        }

        /** Get the transition at end of this time span.
         * @return transition at end of this time span (null if span extends to future infinity)
         * @see #getEnd()
         * @since 11.1
         */
        public Transition<S> getEndTransition() {
            return end;
        }

    }

}