TimeSpanMap.java

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

  19. import java.util.function.Consumer;

  21. import org.orekit.time.AbsoluteDate;
  22. import org.orekit.time.TimeStamped;

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

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

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

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

  87.     /** Get the number of spans.
  88.      * <p>
  89.      * The number of spans is always at least 1. The number of transitions
  90.      * is always 1 less than the number of spans.
  91.      * </p>
  92.      * @return number of spans
  93.      * @since 11.1
  94.      */
  95.     public synchronized int getSpansNumber() {
  96.         return nbSpans;
  97.     }

  99.     /** Add an entry valid before a limit date.
  100.      * <p>
  101.      * As an entry is valid, it truncates or overrides the validity of the neighboring
  102.      * entries already present in the map.
  103.      * </p>
  104.      * <p>
  105.      * If the map already contains transitions that occur earlier than {@code latestValidityDate},
  106.      * the {@code erasesEarlier} parameter controls what to do with them. Lets consider
  107.      * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
  108.      * {@code latestValidityDate} prior to the call to the method (i.e. tₖ &lt;
  109.      * {@code latestValidityDate} &lt; tₖ₊₁).
  110.      * </p>
  111.      * <ul>
  112.      *  <li>if {@code erasesEarlier} is {@code true}, then all earlier transitions
  113.      *      up to and including tₖ are erased, and the {@code entry} will be valid from past infinity
  114.      *      to {@code latestValidityDate}</li>
  115.      *  <li>if {@code erasesEarlier} is {@code false}, then all earlier transitions
  116.      *      are preserved, and the {@code entry} will be valid from tₖ
  117.      *      to {@code latestValidityDate}</li>
  118.      *  </ul>
  119.      * <p>
  120.      * In both cases, the existing entry eₖ time span will be truncated and will be valid
  121.      * only from {@code latestValidityDate} to tₖ₊₁.
  122.      * </p>
  123.      * @param entry entry to add
  124.      * @param latestValidityDate date before which the entry is valid
  125.      * @param erasesEarlier if true, the entry erases all existing transitions
  126.      * that are earlier than {@code latestValidityDate}
  127.      * @return span with added entry
  128.      * @since 11.1
  129.      */
  130.     public synchronized Span<T> addValidBefore(final T entry, final AbsoluteDate latestValidityDate, final boolean erasesEarlier) {

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

  135.         if (erasesEarlier) {

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

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

  146.         }

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

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

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

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

  167.         }

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

  172.         return span;

  174.     }

  176.     /** Add an entry valid after a limit date.
  177.      * <p>
  178.      * As an entry is valid, it truncates or overrides the validity of the neighboring
  179.      * entries already present in the map.
  180.      * </p>
  181.      * <p>
  182.      * If the map already contains transitions that occur later than {@code earliestValidityDate},
  183.      * the {@code erasesLater} parameter controls what to do with them. Lets consider
  184.      * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
  185.      * {@code earliestValidityDate} prior to the call to the method (i.e. tₖ &lt;
  186.      * {@code earliestValidityDate} &lt; tₖ₊₁).
  187.      * </p>
  188.      * <ul>
  189.      *  <li>if {@code erasesLater} is {@code true}, then all later transitions
  190.      *      from and including tₖ₊₁ are erased, and the {@code entry} will be valid from
  191.      *      {@code earliestValidityDate} to future infinity</li>
  192.      *  <li>if {@code erasesLater} is {@code false}, then all later transitions
  193.      *      are preserved, and the {@code entry} will be valid from {@code earliestValidityDate}
  194.      *      to tₖ₊₁</li>
  195.      *  </ul>
  196.      * <p>
  197.      * In both cases, the existing entry eₖ time span will be truncated and will be valid
  198.      * only from tₖ to {@code earliestValidityDate}.
  199.      * </p>
  200.      * @param entry entry to add
  201.      * @param earliestValidityDate date after which the entry is valid
  202.      * @param erasesLater if true, the entry erases all existing transitions
  203.      * that are later than {@code earliestValidityDate}
  204.      * @return span with added entry
  205.      * @since 11.1
  206.      */
  207.     public synchronized Span<T> addValidAfter(final T entry, final AbsoluteDate earliestValidityDate, final boolean erasesLater) {

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

  212.         if (erasesLater) {

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

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

  223.         }

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

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

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

  243.         return span;

  245.     }

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

  260.         // handle special cases
  261.         if (AbsoluteDate.PAST_INFINITY.equals(earliestValidityDate)) {
  262.             if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
  263.                 // we wipe everything in the map
  264.                 current = new Span<>(entry);
  265.                 return current;
  266.             } else {
  267.                 // we wipe from past infinity
  268.                 return addValidBefore(entry, latestValidityDate, true);
  269.             }
  270.         } else if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
  271.             // we wipe up to future infinity
  272.             return addValidAfter(entry, earliestValidityDate, true);
  273.         } else {

  275.             // locate spans at earliest and latest dates
  276.             locate(earliestValidityDate);
  277.             Span<T> latest = current;
  278.             while (latest.getEndTransition() != null && latest.getEnd().isBeforeOrEqualTo(latestValidityDate)) {
  279.                 latest = latest.next();
  280.                 --nbSpans;
  281.             }
  282.             if (latest == current) {
  283.                 // the interval splits one transition in the middle, we need to duplicate the instance
  284.                 latest = new Span<>(current.data);
  285.                 if (current.getEndTransition() != null) {
  286.                     current.getEndTransition().setBefore(latest);
  287.                 }
  288.             }

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

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

  303.             // manage latest transition
  304.             insertTransition(latestValidityDate, span, latest);

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

  309.             return span;

  311.         }

  313.     }

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

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

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

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

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

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

  368.             // current span is too early
  369.             current = next;

  371.         }

  373.     }

  375.     /** Insert a transition.
  376.      * @param date transition date
  377.      * @param before span before transition
  378.      * @param after span after transition
  379.      * @since 11.1
  380.      */
  381.     private void insertTransition(final AbsoluteDate date, final Span<T> before, final Span<T> after) {
  382.         final Transition<T> transition = new Transition<>(date);
  383.         transition.setBefore(before);
  384.         transition.setAfter(after);
  385.         ++nbSpans;
  386.     }

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

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

  404.     /** Get the first (earliest) span.
  405.      * @return first (earliest) span
  406.      * @since 11.1
  407.      */
  408.     public synchronized Span<T> getFirstSpan() {
  409.         Span<T> span = current;
  410.         while (span.getStartTransition() != null) {
  411.             span = span.previous();
  412.         }
  413.         return span;
  414.     }

  416.     /** Get the last (latest) span.
  417.      * @return last (latest) span
  418.      * @since 11.1
  419.      */
  420.     public synchronized Span<T> getLastSpan() {
  421.         Span<T> span = current;
  422.         while (span.getEndTransition() != null) {
  423.             span = span.next();
  424.         }
  425.         return span;
  426.     }

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

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

  459.         return range;

  461.     }

  463.     /**
  464.      * Performs an action for each non-null element of map.
  465.      * <p>
  466.      * The action is performed chronologically.
  467.      * </p>
  468.      * @param action action to perform on the non-null elements
  469.      * @since 10.3
  470.      */
  471.     public synchronized void forEach(final Consumer<T> action) {
  472.         for (Span<T> span = getFirstSpan(); span != null; span = span.next()) {
  473.             if (span.getData() != null) {
  474.                 action.accept(span.getData());
  475.             }
  476.         }
  477.     }

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

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

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

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

  500.         /** Simple constructor.
  501.          * @param date transition date
  502.          */
  503.         private Transition(final AbsoluteDate date) {
  504.             this.date = date;
  505.         }

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

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

  523.         /** Get the transition date.
  524.          * @return transition date
  525.          */
  526.         @Override
  527.         public AbsoluteDate getDate() {
  528.             return date;
  529.         }

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

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

  547.         /** Get the entry valid before transition.
  548.          * @return entry valid before transition
  549.          * @see #getSpanBefore()
  550.          */
  551.         public S getBefore() {
  552.             return before.getData();
  553.         }

  555.         /** Get the {@link Span} valid before transition.
  556.          * @return {@link Span} valid before transition
  557.          * @since 11.1
  558.          */
  559.         public Span<S> getSpanBefore() {
  560.             return before;
  561.         }

  563.         /** Get the entry valid after transition.
  564.          * @return entry valid after transition
  565.          * @see #getSpanAfter()
  566.          */
  567.         public S getAfter() {
  568.             return after.getData();
  569.         }

  571.         /** Get the {@link Span} valid after transition.
  572.          * @return {@link Span} valid after transition
  573.          * @since 11.1
  574.          */
  575.         public Span<S> getSpanAfter() {
  576.             return after;
  577.         }

  579.     }

  581.     /** Holder for one time span.
  582.      * <p>
  583.      * This data type is dual to {@link Transition}, it
  584.      * is focused on one valid data, and gives access to
  585.      * surrounding transition dates whereas {@link Transition}
  586.      * is focused on one transition date, and gives access to
  587.      * surrounding valid data.
  588.      * </p>
  589.      * @param <S> Type of the data.
  590.      * @since 9.3
  591.      */
  592.     public static class Span<S> {

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

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

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

  603.         /** Simple constructor.
  604.          * @param data valid data
  605.          */
  606.         private Span(final S data) {
  607.             this.data = data;
  608.         }

  610.         /** Get the data valid during this time span.
  611.          * @return data valid during this time span
  612.          */
  613.         public S getData() {
  614.             return data;
  615.         }

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

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

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

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

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

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

  669.     }

  671. }
Created with JaCoCo 0.8.11.202310140853