1 /* Copyright 2002-2022 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.NavigableSet;
20 import java.util.TreeSet;
21 import java.util.function.Consumer;
22
23 import org.orekit.time.AbsoluteDate;
24 import org.orekit.time.ChronologicalComparator;
25 import org.orekit.time.TimeStamped;
26
27 /** Container for objects that apply to spans of time.
28 * <p>
29 * Time span maps can be seen either as an ordered collection of
30 * {@link Span time spans} or as an ordered collection
31 * of {@link Transition transitions}. Both views are dual one to
32 * each other. A time span extends from one transition to the
33 * next one, and a transition separates one time span from the
34 * next one. Each time span contains one entry that is valid during
35 * the time span; this entry may be null if nothing is valid during
36 * this time span.
37 * </p>
38 * <p>
39 * Typical uses of {@link TimeSpanMap} are to hold piecewise data, like for
40 * example an orbit count that changes at ascending nodes (in which case the
41 * entry would be an {@link Integer}), or a visibility status between several
42 * objects (in which case the entry would be a {@link Boolean}) or a drag
43 * coefficient that is expected to be estimated daily or three-hourly (this is
44 * how {@link org.orekit.forces.drag.TimeSpanDragForce TimeSpanDragForce} is
45 * implemented).
46 * </p>
47 * <p>
48 * Time span maps are built progressively. At first, they contain one
49 * {@link Span time span} only whose validity extends from past infinity to
50 * future infinity. Then new entries are added one at a time, associated with
51 * transition dates, in order to build up the complete map. The transition dates
52 * can be either the start of validity (when calling {@link #addValidAfter(Object,
53 * AbsoluteDate, boolean)}), or the end of the validity (when calling {@link
54 * #addValidBefore(Object, AbsoluteDate, boolean)}). Entries are often added at one
55 * end only (and mainly in chronological order), but this is not required. It is
56 * possible for example to first set up a map that cover a large range (say one day),
57 * and then to insert intermediate dates using for example propagation and event
58 * detectors to carve out some parts. This is akin to the way Binary Space Partitioning
59 * Trees work.
60 * </p>
61 * <p>
62 * Since 11.1, this class is thread-safe
63 * </p>
64 * @param <T> Type of the data.
65 * @author Luc Maisonobe
66 * @since 7.1
67 */
68 public class TimeSpanMap<T> {
69
70 /** Reference to last accessed data. */
71 private Span<T> current;
72
73 /** Number of time spans. */
74 private int nbSpans;
75
76 /** Create a map containing a single object, initially valid throughout the timeline.
77 * <p>
78 * The real validity of this first entry will be truncated as other
79 * entries are either {@link #addValidBefore(Object, AbsoluteDate, boolean)
80 * added before} it or {@link #addValidAfter(Object, AbsoluteDate, boolean)
81 * added after} it.
82 * </p>
83 * @param entry entry (initially valid throughout the timeline)
84 */
85 public TimeSpanMap(final T entry) {
86 current = new Span<>(entry);
87 nbSpans = 1;
88 }
89
90 /** Get the number of spans.
91 * <p>
92 * The number of spans is always at least 1. The number of transitions
93 * is always 1 less than the number of spans.
94 * </p>
95 * @return number of spans
96 * @since 11.1
97 */
98 public synchronized int getSpansNumber() {
99 return nbSpans;
100 }
101
102 /** Add an entry valid before a limit date.
103 * <p>
104 * Calling this method is equivalent to call {@link #addValidAfter(Object,
105 * AbsoluteDate, boolean) addValidAfter(entry, latestValidityDate, false)}.
106 * </p>
107 * @param entry entry to add
108 * @param latestValidityDate date before which the entry is valid
109 * @deprecated as of 11.1, replaced by {@link #addValidBefore(Object, AbsoluteDate, boolean)}
110 */
111 @Deprecated
112 public void addValidBefore(final T entry, final AbsoluteDate latestValidityDate) {
113 addValidBefore(entry, latestValidityDate, false);
114 }
115
116 /** Add an entry valid before a limit date.
117 * <p>
118 * As an entry is valid, it truncates or overrides the validity of the neighboring
119 * entries already present in the map.
120 * </p>
121 * <p>
122 * If the map already contains transitions that occur earlier than {@code latestValidityDate},
123 * the {@code erasesEarlier} parameter controls what to do with them. Lets consider
124 * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
125 * {@code latestValidityDate} prior to the call to the method (i.e. tₖ <
126 * {@code latestValidityDate} < tₖ₊₁).
127 * </p>
128 * <ul>
129 * <li>if {@code erasesEarlier} is {@code true}, then all earlier transitions
130 * up to and including tₖ are erased, and the {@code entry} will be valid from past infinity
131 * to {@code latestValidityDate}</li>
132 * <li>if {@code erasesEarlier} is {@code false}, then all earlier transitions
133 * are preserved, and the {@code entry} will be valid from tₖ
134 * to {@code latestValidityDate}</li>
135 * </ul>
136 * <p>
137 * In both cases, the existing entry eₖ time span will be truncated and will be valid
138 * only from {@code latestValidityDate} to tₖ₊₁.
139 * </p>
140 * @param entry entry to add
141 * @param latestValidityDate date before which the entry is valid
142 * @param erasesEarlier if true, the entry erases all existing transitions
143 * that are earlier than {@code latestValidityDate}
144 * @return span with added entry
145 * @since 11.1
146 */
147 public synchronized Span<T> addValidBefore(final T entry, final AbsoluteDate latestValidityDate, final boolean erasesEarlier) {
148
149 // update current reference to transition date
150 locate(latestValidityDate);
151
152 if (erasesEarlier) {
153
154 // drop everything before date
155 current.start = null;
156
157 // update count
158 nbSpans = 0;
159 for (Span<T> span = current; span != null; span = span.next()) {
160 ++nbSpans;
161 }
162
163 }
164
165 final Span<T> span = new Span<>(entry);
166
167 final Transition<T> start = current.getStartTransition();
168 if (start != null && start.getDate().equals(latestValidityDate)) {
169 // the transition at start of the current span is at the exact same date
170 // we update it, without adding a new transition
171 if (start.previous() != null) {
172 start.previous().setAfter(span);
173 }
174 start.setBefore(span);
175 } else {
176
177 if (current.getStartTransition() != null) {
178 current.getStartTransition().setAfter(span);
179 }
180
181 // we need to add a new transition somewhere inside the current span
182 insertTransition(latestValidityDate, span, current);
183
184 }
185
186 // we consider the last added transition as the new current one
187 current = span;
188
189 return span;
190
191 }
192
193 /** Add an entry valid after a limit date.
194 * <p>
195 * Calling this method is equivalent to call {@link #addValidAfter(Object,
196 * AbsoluteDate, boolean) addValidAfter(entry, earliestValidityDate, false)}.
197 * </p>
198 * @param entry entry to add
199 * @param earliestValidityDate date after which the entry is valid
200 * @deprecated as of 11.1, replaced by {@link #addValidAfter(Object, AbsoluteDate, boolean)}
201 */
202 @Deprecated
203 public void addValidAfter(final T entry, final AbsoluteDate earliestValidityDate) {
204 addValidAfter(entry, earliestValidityDate, false);
205 }
206
207 /** Add an entry valid after a limit date.
208 * <p>
209 * As an entry is valid, it truncates or overrides the validity of the neighboring
210 * entries already present in the map.
211 * </p>
212 * <p>
213 * If the map already contains transitions that occur earlier than {@code earliestValidityDate},
214 * the {@code erasesEarlier} parameter controls what to do with them. Lets consider
215 * the time span [tₖ ; tₖ₊₁[ associated with entry eₖ that would have been valid at time
216 * {@code earliestValidityDate} prior to the call to the method (i.e. tₖ <
217 * {@code earliestValidityDate} < tₖ₊₁).
218 * </p>
219 * <ul>
220 * <li>if {@code erasesEarlier} is {@code true}, then all earlier transitions
221 * up to and including tₖ are erased, and the {@code entry} will be valid from past infinity
222 * to {@code earliestValidityDate}</li>
223 * <li>if {@code erasesEarlier} is {@code false}, then all earlier transitions
224 * are preserved, and the {@code entry} will be valid from tₖ
225 * to {@code earliestValidityDate}</li>
226 * </ul>
227 * <p>
228 * In both cases, the existing entry eₖ time span will be truncated and will be valid
229 * only from {@code earliestValidityDate} to tₖ₊₁.
230 * </p>
231 * @param entry entry to add
232 * @param earliestValidityDate date after which the entry is valid
233 * @param erasesLater if true, the entry erases all existing transitions
234 * that are later than {@code earliestValidityDate}
235 * @return span with added entry
236 * @since 11.1
237 */
238 public synchronized Span<T> addValidAfter(final T entry, final AbsoluteDate earliestValidityDate, final boolean erasesLater) {
239
240 // update current reference to transition date
241 locate(earliestValidityDate);
242
243 if (erasesLater) {
244
245 // drop everything after date
246 current.end = null;
247
248 // update count
249 nbSpans = 0;
250 for (Span<T> span = current; span != null; span = span.previous()) {
251 ++nbSpans;
252 }
253
254 }
255
256 final Span<T> span = new Span<>(entry);
257 if (current.getEndTransition() != null) {
258 current.getEndTransition().setBefore(span);
259 }
260
261 final Transition<T> start = current.getStartTransition();
262 if (start != null && start.getDate().equals(earliestValidityDate)) {
263 // the transition at start of the current span is at the exact same date
264 // we update it, without adding a new transition
265 start.setAfter(span);
266 } else {
267 // we need to add a new transition somewhere inside the current span
268 insertTransition(earliestValidityDate, current, span);
269 }
270
271 // we consider the last added transition as the new current one
272 current = span;
273
274 return span;
275
276 }
277
278 /** Add an entry valid between two limit dates.
279 * <p>
280 * As an entry is valid, it truncates or overrides the validity of the neighboring
281 * entries already present in the map.
282 * </p>
283 * @param entry entry to add
284 * @param earliestValidityDate date after which the entry is valid
285 * @param latestValidityDate date before which the entry is valid
286 * @return span with added entry
287 * @since 11.1
288 */
289 public synchronized Span<T> addValidBetween(final T entry, final AbsoluteDate earliestValidityDate, final AbsoluteDate latestValidityDate) {
290
291 // handle special cases
292 if (AbsoluteDate.PAST_INFINITY.equals(earliestValidityDate)) {
293 if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
294 // we wipe everything in the map
295 current = new Span<>(entry);
296 return current;
297 } else {
298 // we wipe from past infinity
299 return addValidBefore(entry, latestValidityDate, true);
300 }
301 } else if (AbsoluteDate.FUTURE_INFINITY.equals(latestValidityDate)) {
302 // we wipe up to future infinity
303 return addValidAfter(entry, earliestValidityDate, true);
304 } else {
305
306 // locate spans at earliest and latest dates
307 locate(earliestValidityDate);
308 Span<T> latest = current;
309 while (latest.getEndTransition() != null && latest.getEnd().isBeforeOrEqualTo(latestValidityDate)) {
310 latest = latest.next();
311 --nbSpans;
312 }
313 if (latest == current) {
314 // the interval splits one transition in the middle, we need to duplicate the instance
315 latest = new Span<>(current.data);
316 if (current.getEndTransition() != null) {
317 current.getEndTransition().setBefore(latest);
318 }
319 }
320
321 final Span<T> span = new Span<>(entry);
322
323 // manage earliest transition
324 final Transition<T> start = current.getStartTransition();
325 if (start != null && start.getDate().equals(earliestValidityDate)) {
326 // the transition at start of the current span is at the exact same date
327 // we update it, without adding a new transition
328 start.setAfter(span);
329 } else {
330 // we need to add a new transition somewhere inside the current span
331 insertTransition(earliestValidityDate, current, span);
332 }
333
334 // manage latest transition
335 insertTransition(latestValidityDate, span, latest);
336
337 // we consider the last added transition as the new current one
338 current = span;
339
340 return span;
341
342 }
343
344 }
345
346 /** Get the entry valid at a specified date.
347 * <p>
348 * The expected complexity is O(1) for successive calls with
349 * neighboring dates, which is the more frequent use in propagation
350 * or orbit determination applications, and O(n) for random calls.
351 * </p>
352 * @param date date at which the entry must be valid
353 * @return valid entry at specified date
354 * @see #getSpan(AbsoluteDate)
355 */
356 public synchronized T get(final AbsoluteDate date) {
357 return getSpan(date).getData();
358 }
359
360 /** Get the time span containing a specified date.
361 * <p>
362 * The expected complexity is O(1) for successive calls with
363 * neighboring dates, which is the more frequent use in propagation
364 * or orbit determination applications, and O(n) for random calls.
365 * </p>
366 * @param date date belonging to the desired time span
367 * @return time span containing the specified date
368 * @since 9.3
369 */
370 public synchronized Span<T> getSpan(final AbsoluteDate date) {
371 locate(date);
372 return current;
373 }
374
375 /** Locate the time span containing a specified date.
376 * <p>
377 * The {@link current} field is updated to the located span.
378 * After the method returns, {@code current.getStartTransition()} is either
379 * null or its date is before or equal to date, and {@code
380 * current.getEndTransition()} is either null or its date is after date.
381 * </p>
382 * @param date date belonging to the desired time span
383 */
384 private synchronized void locate(final AbsoluteDate date) {
385
386 while (current.getStart().isAfter(date)) {
387 // current span is too late
388 current = current.previous();
389 }
390
391 while (current.getEnd().isBeforeOrEqualTo(date)) {
392
393 final Span<T> next = current.next();
394 if (next == null) {
395 // this happens when date is FUTURE_INFINITY
396 return;
397 }
398
399 // current span is too early
400 current = next;
401
402 }
403
404 }
405
406 /** Insert a transition.
407 * @param date transition date
408 * @param before span before transition
409 * @param after span after transition
410 * @since 11.1
411 */
412 private void insertTransition(final AbsoluteDate date, final Span<T> before, final Span<T> after) {
413 final Transition<T> transition = new Transition<>(date);
414 transition.setBefore(before);
415 transition.setAfter(after);
416 ++nbSpans;
417 }
418
419 /** Get the first (earliest) transition.
420 * @return first (earliest) transition, or null if there are no transitions
421 * @since 11.1
422 */
423 public synchronized Transition<T> getFirstTransition() {
424 return getFirstSpan().getEndTransition();
425 }
426
427 /** Get the last (latest) transition.
428 * @return last (latest) transition, or null if there are no transitions
429 * @since 11.1
430 */
431 public synchronized Transition<T> getLastTransition() {
432 return getLastSpan().getStartTransition();
433 }
434
435 /** Get the first (earliest) span.
436 * @return first (earliest) span
437 * @since 11.1
438 */
439 public synchronized Span<T> getFirstSpan() {
440 Span<T> span = current;
441 while (span.getStartTransition() != null) {
442 span = span.previous();
443 }
444 return span;
445 }
446
447 /** Get the last (latest) span.
448 * @return last (latest) span
449 * @since 11.1
450 */
451 public synchronized Span<T> getLastSpan() {
452 Span<T> span = current;
453 while (span.getEndTransition() != null) {
454 span = span.next();
455 }
456 return span;
457 }
458
459 /** Extract a range of the map.
460 * <p>
461 * The object returned will be a new independent instance that will contain
462 * only the transitions that lie in the specified range.
463 * </p>
464 * <p>
465 * Consider for example a map containing objects O₀ valid before t₁, O₁ valid
466 * between t₁ and t₂, O₂ valid between t₂ and t₃, O₃ valid between t₃ and t₄,
467 * and O₄ valid after t₄. then calling this method with a {@code start}
468 * date between t₁ and t₂ and a {@code end} date between t₃ and t₄
469 * will result in a new map containing objects O₁ valid before t₂, O₂
470 * valid between t₂ and t₃, and O₃ valid after t₃. The validity of O₁
471 * is therefore extended in the past, and the validity of O₃ is extended
472 * in the future.
473 * </p>
474 * @param start earliest date at which a transition is included in the range
475 * (may be set to {@link AbsoluteDate#PAST_INFINITY} to keep all early transitions)
476 * @param end latest date at which a transition is included in the r
477 * (may be set to {@link AbsoluteDate#FUTURE_INFINITY} to keep all late transitions)
478 * @return a new instance with all transitions restricted to the specified range
479 * @since 9.2
480 */
481 public synchronized TimeSpanMap<T> extractRange(final AbsoluteDate start, final AbsoluteDate end) {
482
483 Span<T> span = getSpan(start);
484 final TimeSpanMap<T> range = new TimeSpanMap<>(span.getData());
485 while (span.getEndTransition() != null && span.getEndTransition().getDate().isBeforeOrEqualTo(end)) {
486 span = span.next();
487 range.addValidAfter(span.getData(), span.getStartTransition().getDate(), false);
488 }
489
490 return range;
491
492 }
493
494 /** Get copy of the sorted transitions.
495 * @return copy of the sorted transitions
496 * @deprecated as of 11.1, replaced by {@link #getFirstSpan()}, {@link #getLastSpan()},
497 * {@link #getFirstTransition()}, {@link #getLastTransition()}, and {@link #getSpansNumber()}
498 */
499 @Deprecated
500 public synchronized NavigableSet<Transition<T>> getTransitions() {
501 final NavigableSet<Transition<T>> set = new TreeSet<>(new ChronologicalComparator());
502 for (Transition<T> transition = getFirstTransition(); transition != null; transition = transition.next()) {
503 set.add(transition);
504 }
505 return set;
506 }
507
508 /**
509 * Performs an action for each non-null element of map.
510 * <p>
511 * The action is performed chronologically.
512 * </p>
513 * @param action action to perform on the non-null elements
514 * @since 10.3
515 */
516 public synchronized void forEach(final Consumer<T> action) {
517 for (Span<T> span = getFirstSpan(); span != null; span = span.next()) {
518 if (span.getData() != null) {
519 action.accept(span.getData());
520 }
521 }
522 }
523
524 /** Class holding transition times.
525 * <p>
526 * This data type is dual to {@link Span}, it is
527 * focused on one transition date, and gives access to
528 * surrounding valid data whereas {@link Span} is focused
529 * on one valid data, and gives access to surrounding
530 * transition dates.
531 * </p>
532 * @param <S> Type of the data.
533 */
534 public static class Transition<S> implements TimeStamped {
535
536 /** Transition date. */
537 private AbsoluteDate date;
538
539 /** Entry valid before the transition. */
540 private Span<S> before;
541
542 /** Entry valid after the transition. */
543 private Span<S> after;
544
545 /** Simple constructor.
546 * @param date transition date
547 */
548 private Transition(final AbsoluteDate date) {
549 this.date = date;
550 }
551
552 /** Set the span valid before transition.
553 * @param before span valid before transition (must be non-null)
554 */
555 void setBefore(final Span<S> before) {
556 this.before = before;
557 before.end = this;
558 }
559
560 /** Set the span valid after transition.
561 * @param after span valid after transition (must be non-null)
562 */
563 void setAfter(final Span<S> after) {
564 this.after = after;
565 after.start = this;
566 }
567
568 /** Get the transition date.
569 * @return transition date
570 */
571 @Override
572 public AbsoluteDate getDate() {
573 return date;
574 }
575
576 /** Get the previous transition.
577 * @return previous transition, or null if this transition was the first one
578 * @since 11.1
579 */
580 public Transition<S> previous() {
581 return before.getStartTransition();
582 }
583
584 /** Get the next transition.
585 * @return next transition, or null if this transition was the last one
586 * @since 11.1
587 */
588 public Transition<S> next() {
589 return after.getEndTransition();
590 }
591
592 /** Get the entry valid before transition.
593 * @return entry valid before transition
594 * @see #getSpanBefore()
595 */
596 public S getBefore() {
597 return before.getData();
598 }
599
600 /** Get the {@link Span} valid before transition.
601 * @return {@link Span} valid before transition
602 * @since 11.1
603 */
604 public Span<S> getSpanBefore() {
605 return before;
606 }
607
608 /** Get the entry valid after transition.
609 * @return entry valid after transition
610 * @see #getSpanAfter()
611 */
612 public S getAfter() {
613 return after.getData();
614 }
615
616 /** Get the {@link Span} valid after transition.
617 * @return {@link Span} valid after transition
618 * @since 11.1
619 */
620 public Span<S> getSpanAfter() {
621 return after;
622 }
623
624 }
625
626 /** Holder for one time span.
627 * <p>
628 * This data type is dual to {@link Transition}, it
629 * is focused on one valid data, and gives access to
630 * surrounding transition dates whereas {@link Transition}
631 * is focused on one transition date, and gives access to
632 * surrounding valid data.
633 * </p>
634 * @param <S> Type of the data.
635 * @since 9.3
636 */
637 public static class Span<S> {
638
639 /** Valid data. */
640 private final S data;
641
642 /** Start of validity for the data (null if span extends to past infinity). */
643 private Transition<S> start;
644
645 /** End of validity for the data (null if span extends to future infinity). */
646 private Transition<S> end;
647
648 /** Simple constructor.
649 * @param data valid data
650 */
651 private Span(final S data) {
652 this.data = data;
653 }
654
655 /** Get the data valid during this time span.
656 * @return data valid during this time span
657 */
658 public S getData() {
659 return data;
660 }
661
662 /** Get the previous time span.
663 * @return previous time span, or null if this time span was the first one
664 * @since 11.1
665 */
666 public Span<S> previous() {
667 return start == null ? null : start.getSpanBefore();
668 }
669
670 /** Get the next time span.
671 * @return next time span, or null if this time span was the last one
672 * @since 11.1
673 */
674 public Span<S> next() {
675 return end == null ? null : end.getSpanAfter();
676 }
677
678 /** Get the start of this time span.
679 * @return start of this time span (will be {@link AbsoluteDate#PAST_INFINITY}
680 * if {@link #getStartTransition()} returns null)
681 * @see #getStartTransition()
682 */
683 public AbsoluteDate getStart() {
684 return start == null ? AbsoluteDate.PAST_INFINITY : start.getDate();
685 }
686
687 /** Get the transition at start of this time span.
688 * @return transition at start of this time span (null if span extends to past infinity)
689 * @see #getStart()
690 * @since 11.1
691 */
692 public Transition<S> getStartTransition() {
693 return start;
694 }
695
696 /** Get the end of this time span.
697 * @return end of this time span (will be {@link AbsoluteDate#FUTURE_INFINITY}
698 * if {@link #getEndTransition()} returns null)
699 * @see #getEndTransition()
700 */
701 public AbsoluteDate getEnd() {
702 return end == null ? AbsoluteDate.FUTURE_INFINITY : end.getDate();
703 }
704
705 /** Get the transition at end of this time span.
706 * @return transition at end of this time span (null if span extends to future infinity)
707 * @see #getEnd()
708 * @since 11.1
709 */
710 public Transition<S> getEndTransition() {
711 return end;
712 }
713
714 }
715
716 }