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ₖ <
- * {@code latestValidityDate} < 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ₖ <
- * {@code earliestValidityDate} < 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;
- }
- }
- }