1 /* Copyright 2002-2024 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;
18
19 import java.util.function.Consumer;
20
21 import org.orekit.errors.OrekitException;
22 import org.orekit.errors.OrekitMessages;
23 import org.orekit.time.AbsoluteDate;
24 import org.orekit.time.TimeStamped;
25
26 /** Container for objects that apply to spans of time.
27 * <p>
28 * Time span maps can be seen either as an ordered collection of
29 * {@link Span time spans} or as an ordered collection
30 * of {@link Transition transitions}. Both views are dual one to
31 * each other. A time span extends from one transition to the
32 * next one, and a transition separates one time span from the
33 * next one. Each time span contains one entry that is valid during
34 * the time span; this entry may be null if nothing is valid during
35 * this time span.
36 * </p>
37 * <p>
38 * Typical uses of {@link TimeSpanMap} are to hold piecewise data, like for
39 * example an orbit count that changes at ascending nodes (in which case the
40 * entry would be an {@link Integer}), or a visibility status between several
41 * objects (in which case the entry would be a {@link Boolean}) or a drag
42 * coefficient that is expected to be estimated daily or three-hourly.
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> {
66
67 /** Reference to last accessed data. */
68 private Span<T> current;
69
70 /** Number of time spans. */
71 private int nbSpans;
72
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 }
86
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 }
98
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ₖ <
109 * {@code latestValidityDate} < 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) {
131
132 // update current reference to transition date
133 locate(latestValidityDate);
134
135 if (erasesEarlier) {
136
137 // drop everything before date
138 current.start = null;
139
140 // update count
141 nbSpans = 0;
142 for (Span<T> span = current; span != null; span = span.next()) {
143 ++nbSpans;
144 }
145
146 }
147
148 final Span<T> span = new Span<>(entry);
149
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 {
159
160 if (current.getStartTransition() != null) {
161 current.getStartTransition().setAfter(span);
162 }
163
164 // we need to add a new transition somewhere inside the current span
165 insertTransition(latestValidityDate, span, current);
166
167 }
168
169 // we consider the last added transition as the new current one
170 current = span;
171
172 return span;
173
174 }
175
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ₖ <
186 * {@code earliestValidityDate} < 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) {
208
209 // update current reference to transition date
210 locate(earliestValidityDate);
211
212 if (erasesLater) {
213
214 // drop everything after date
215 current.end = null;
216
217 // update count
218 nbSpans = 0;
219 for (Span<T> span = current; span != null; span = span.previous()) {
220 ++nbSpans;
221 }
222
223 }
224
225 final Span<T> span = new Span<>(entry);
226 if (current.getEndTransition() != null) {
227 current.getEndTransition().setBefore(span);
228 }
229
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 }
239
240 // we consider the last added transition as the new current one
241 current = span;
242
243 return span;
244
245 }
246
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) {
259
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 {
274
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 }
289
290 final Span<T> span = new Span<>(entry);
291
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 }
302
303 // manage latest transition
304 insertTransition(latestValidityDate, span, latest);
305
306 // we consider the last added transition as the new current one
307 current = span;
308
309 return span;
310
311 }
312
313 }
314
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 }
328
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 }
343
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) {
354
355 while (current.getStart().isAfter(date)) {
356 // current span is too late
357 current = current.previous();
358 }
359
360 while (current.getEnd().isBeforeOrEqualTo(date)) {
361
362 final Span<T> next = current.next();
363 if (next == null) {
364 // this happens when date is FUTURE_INFINITY
365 return;
366 }
367
368 // current span is too early
369 current = next;
370
371 }
372
373 }
374
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 }
387
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 }
395
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 }
403
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 }
415
416 /** Get the first (earliest) span with non-null data.
417 * @return first (earliest) span with non-null data
418 * @since 12.1
419 */
420 public synchronized Span<T> getFirstNonNullSpan() {
421 Span<T> span = getFirstSpan();
422 while (span.getData() == null) {
423 if (span.getEndTransition() == null) {
424 throw new OrekitException(OrekitMessages.NO_CACHED_ENTRIES);
425 }
426 span = span.next();
427 }
428 return span;
429 }
430
431 /** Get the last (latest) span.
432 * @return last (latest) span
433 * @since 11.1
434 */
435 public synchronized Span<T> getLastSpan() {
436 Span<T> span = current;
437 while (span.getEndTransition() != null) {
438 span = span.next();
439 }
440 return span;
441 }
442
443 /** Get the last (latest) span with non-null data.
444 * @return last (latest) span with non-null data
445 * @since 12.1
446 */
447 public synchronized Span<T> getLastNonNullSpan() {
448 Span<T> span = getLastSpan();
449 while (span.getData() == null) {
450 if (span.getStartTransition() == null) {
451 throw new OrekitException(OrekitMessages.NO_CACHED_ENTRIES);
452 }
453 span = span.previous();
454 }
455 return span;
456 }
457
458 /** Extract a range of the map.
459 * <p>
460 * The object returned will be a new independent instance that will contain
461 * only the transitions that lie in the specified range.
462 * </p>
463 * <p>
464 * Consider for example a map containing objects O₀ valid before t₁, O₁ valid
465 * between t₁ and t₂, O₂ valid between t₂ and t₃, O₃ valid between t₃ and t₄,
466 * and O₄ valid after t₄. then calling this method with a {@code start}
467 * date between t₁ and t₂ and a {@code end} date between t₃ and t₄
468 * will result in a new map containing objects O₁ valid before t₂, O₂
469 * valid between t₂ and t₃, and O₃ valid after t₃. The validity of O₁
470 * is therefore extended in the past, and the validity of O₃ is extended
471 * in the future.
472 * </p>
473 * @param start earliest date at which a transition is included in the range
474 * (may be set to {@link AbsoluteDate#PAST_INFINITY} to keep all early transitions)
475 * @param end latest date at which a transition is included in the r
476 * (may be set to {@link AbsoluteDate#FUTURE_INFINITY} to keep all late transitions)
477 * @return a new instance with all transitions restricted to the specified range
478 * @since 9.2
479 */
480 public synchronized TimeSpanMap<T> extractRange(final AbsoluteDate start, final AbsoluteDate end) {
481
482 Span<T> span = getSpan(start);
483 final TimeSpanMap<T> range = new TimeSpanMap<>(span.getData());
484 while (span.getEndTransition() != null && span.getEndTransition().getDate().isBeforeOrEqualTo(end)) {
485 span = span.next();
486 range.addValidAfter(span.getData(), span.getStartTransition().getDate(), false);
487 }
488
489 return range;
490
491 }
492
493 /**
494 * Performs an action for each non-null element of map.
495 * <p>
496 * The action is performed chronologically.
497 * </p>
498 * @param action action to perform on the non-null elements
499 * @since 10.3
500 */
501 public synchronized void forEach(final Consumer<T> action) {
502 for (Span<T> span = getFirstSpan(); span != null; span = span.next()) {
503 if (span.getData() != null) {
504 action.accept(span.getData());
505 }
506 }
507 }
508
509 /** Class holding transition times.
510 * <p>
511 * This data type is dual to {@link Span}, it is
512 * focused on one transition date, and gives access to
513 * surrounding valid data whereas {@link Span} is focused
514 * on one valid data, and gives access to surrounding
515 * transition dates.
516 * </p>
517 * @param <S> Type of the data.
518 */
519 public static class Transition<S> implements TimeStamped {
520
521 /** Transition date. */
522 private AbsoluteDate date;
523
524 /** Entry valid before the transition. */
525 private Span<S> before;
526
527 /** Entry valid after the transition. */
528 private Span<S> after;
529
530 /** Simple constructor.
531 * @param date transition date
532 */
533 private Transition(final AbsoluteDate date) {
534 this.date = date;
535 }
536
537 /** Set the span valid before transition.
538 * @param before span valid before transition (must be non-null)
539 */
540 void setBefore(final Span<S> before) {
541 this.before = before;
542 before.end = this;
543 }
544
545 /** Set the span valid after transition.
546 * @param after span valid after transition (must be non-null)
547 */
548 void setAfter(final Span<S> after) {
549 this.after = after;
550 after.start = this;
551 }
552
553 /** Get the transition date.
554 * @return transition date
555 */
556 @Override
557 public AbsoluteDate getDate() {
558 return date;
559 }
560
561 /** Get the previous transition.
562 * @return previous transition, or null if this transition was the first one
563 * @since 11.1
564 */
565 public Transition<S> previous() {
566 return before.getStartTransition();
567 }
568
569 /** Get the next transition.
570 * @return next transition, or null if this transition was the last one
571 * @since 11.1
572 */
573 public Transition<S> next() {
574 return after.getEndTransition();
575 }
576
577 /** Get the entry valid before transition.
578 * @return entry valid before transition
579 * @see #getSpanBefore()
580 */
581 public S getBefore() {
582 return before.getData();
583 }
584
585 /** Get the {@link Span} valid before transition.
586 * @return {@link Span} valid before transition
587 * @since 11.1
588 */
589 public Span<S> getSpanBefore() {
590 return before;
591 }
592
593 /** Get the entry valid after transition.
594 * @return entry valid after transition
595 * @see #getSpanAfter()
596 */
597 public S getAfter() {
598 return after.getData();
599 }
600
601 /** Get the {@link Span} valid after transition.
602 * @return {@link Span} valid after transition
603 * @since 11.1
604 */
605 public Span<S> getSpanAfter() {
606 return after;
607 }
608
609 }
610
611 /** Holder for one time span.
612 * <p>
613 * This data type is dual to {@link Transition}, it
614 * is focused on one valid data, and gives access to
615 * surrounding transition dates whereas {@link Transition}
616 * is focused on one transition date, and gives access to
617 * surrounding valid data.
618 * </p>
619 * @param <S> Type of the data.
620 * @since 9.3
621 */
622 public static class Span<S> {
623
624 /** Valid data. */
625 private final S data;
626
627 /** Start of validity for the data (null if span extends to past infinity). */
628 private Transition<S> start;
629
630 /** End of validity for the data (null if span extends to future infinity). */
631 private Transition<S> end;
632
633 /** Simple constructor.
634 * @param data valid data
635 */
636 private Span(final S data) {
637 this.data = data;
638 }
639
640 /** Get the data valid during this time span.
641 * @return data valid during this time span
642 */
643 public S getData() {
644 return data;
645 }
646
647 /** Get the previous time span.
648 * @return previous time span, or null if this time span was the first one
649 * @since 11.1
650 */
651 public Span<S> previous() {
652 return start == null ? null : start.getSpanBefore();
653 }
654
655 /** Get the next time span.
656 * @return next time span, or null if this time span was the last one
657 * @since 11.1
658 */
659 public Span<S> next() {
660 return end == null ? null : end.getSpanAfter();
661 }
662
663 /** Get the start of this time span.
664 * @return start of this time span (will be {@link AbsoluteDate#PAST_INFINITY}
665 * if {@link #getStartTransition()} returns null)
666 * @see #getStartTransition()
667 */
668 public AbsoluteDate getStart() {
669 return start == null ? AbsoluteDate.PAST_INFINITY : start.getDate();
670 }
671
672 /** Get the transition at start of this time span.
673 * @return transition at start of this time span (null if span extends to past infinity)
674 * @see #getStart()
675 * @since 11.1
676 */
677 public Transition<S> getStartTransition() {
678 return start;
679 }
680
681 /** Get the end of this time span.
682 * @return end of this time span (will be {@link AbsoluteDate#FUTURE_INFINITY}
683 * if {@link #getEndTransition()} returns null)
684 * @see #getEndTransition()
685 */
686 public AbsoluteDate getEnd() {
687 return end == null ? AbsoluteDate.FUTURE_INFINITY : end.getDate();
688 }
689
690 /** Get the transition at end of this time span.
691 * @return transition at end of this time span (null if span extends to future infinity)
692 * @see #getEnd()
693 * @since 11.1
694 */
695 public Transition<S> getEndTransition() {
696 return end;
697 }
698
699 }
700
701 }