1 /* Copyright 2002-2025 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.ArrayList;
20 import java.util.List;
21 import java.util.concurrent.atomic.AtomicInteger;
22 import java.util.concurrent.atomic.AtomicLong;
23 import java.util.concurrent.atomic.AtomicReference;
24 import java.util.concurrent.locks.ReadWriteLock;
25 import java.util.concurrent.locks.ReentrantReadWriteLock;
26 import java.util.stream.Stream;
27
28 import org.hipparchus.exception.LocalizedCoreFormats;
29 import org.hipparchus.util.FastMath;
30 import org.orekit.errors.OrekitException;
31 import org.orekit.errors.OrekitIllegalArgumentException;
32 import org.orekit.errors.OrekitIllegalStateException;
33 import org.orekit.errors.OrekitMessages;
34 import org.orekit.errors.TimeStampedCacheException;
35 import org.orekit.time.AbsoluteDate;
36 import org.orekit.time.TimeStamped;
37
38 /** Generic thread-safe cache for {@link TimeStamped time-stamped} data.
39
40 * @param <T> Type of the cached data.
41
42 * @author Luc Maisonobe
43 */
44 public class GenericTimeStampedCache<T extends TimeStamped> implements TimeStampedCache<T> {
45
46 /** Default number of independent cached time slots. */
47 public static final int DEFAULT_CACHED_SLOTS_NUMBER = 10;
48
49 /** Quantum step. */
50 private static final double QUANTUM_STEP = 1.0e-6;
51
52 /** Reference date for indexing. */
53 private final AtomicReference<AbsoluteDate> reference;
54
55 /** Maximum number of independent cached time slots. */
56 private final int maxSlots;
57
58 /** Maximum duration span in seconds of one slot. */
59 private final double maxSpan;
60
61 /** Quantum gap above which a new slot is created instead of extending an existing one. */
62 private final long newSlotQuantumGap;
63
64 /** Generator to use for yet non-cached data. */
65 private final TimeStampedGenerator<T> generator;
66
67 /** Overriding mean step. */
68 private final double overridingMeanStep;
69
70 /** Maximum number of entries in a neighbors array. */
71 private final int maxNeighborsSize;
72
73 /** Independent time slots cached. */
74 private final List<Slot> slots;
75
76 /** Number of calls to the getNeighbors method. */
77 private final AtomicInteger getNeighborsCalls;
78
79 /** Number of calls to the generate method. */
80 private final AtomicInteger generateCalls;
81
82 /** Number of evictions. */
83 private final AtomicInteger evictions;
84
85 /** Global lock. */
86 private final ReadWriteLock lock;
87
88 /** Simple constructor.
89 * @param maxNeighborsSize maximum size of the arrays to be returned by {@link
90 * #getNeighbors(AbsoluteDate, int)}, must be at least 2
91 * @param maxSlots maximum number of independent cached time slots
92 * @param maxSpan maximum duration span in seconds of one slot
93 * (can be set to {@code Double.POSITIVE_INFINITY} if desired)
94 * @param newSlotInterval time interval above which a new slot is created
95 * instead of extending an existing one
96 * @param generator generator to use for yet non-existent data
97 */
98 public GenericTimeStampedCache(final int maxNeighborsSize, final int maxSlots, final double maxSpan,
99 final double newSlotInterval, final TimeStampedGenerator<T> generator) {
100 this(maxNeighborsSize, maxSlots, maxSpan, newSlotInterval, generator, Double.NaN);
101
102 }
103
104 /** Simple constructor with overriding minimum step.
105 * @param maxNeighborsSize maximum size of the arrays to be returned by {@link
106 * #getNeighbors(AbsoluteDate, int)}, must be at least 2
107 * @param maxSlots maximum number of independent cached time slots
108 * @param maxSpan maximum duration span in seconds of one slot
109 * (can be set to {@code Double.POSITIVE_INFINITY} if desired)
110 * @param newSlotInterval time interval above which a new slot is created
111 * instead of extending an existing one
112 * @param generator generator to use for yet non-existent data
113 * @param overridingMeanStep overriding mean step designed for non-homogeneous tabulated values. To be used for example
114 * when caching monthly tabulated values. Use {@code Double.NaN} otherwise.
115 * @throws OrekitIllegalArgumentException if :
116 * <ul>
117 * <li>neighbors size < 2 </li>
118 * <li>maximum allowed number of slots < 1</li>
119 * <li>minimum step ≤ 0 </li>
120 * </ul>
121 */
122 public GenericTimeStampedCache(final int maxNeighborsSize, final int maxSlots, final double maxSpan,
123 final double newSlotInterval, final TimeStampedGenerator<T> generator,
124 final double overridingMeanStep) {
125
126 // safety check
127 if (maxSlots < 1) {
128 throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, maxSlots, 1);
129 }
130 if (overridingMeanStep <= 0) {
131 throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL_BOUND_EXCLUDED,
132 overridingMeanStep, 0);
133 }
134 if (maxNeighborsSize < 2) {
135 throw new OrekitIllegalArgumentException(OrekitMessages.NOT_ENOUGH_CACHED_NEIGHBORS, maxNeighborsSize, 2);
136 }
137
138 this.reference = new AtomicReference<>();
139 this.maxSlots = maxSlots;
140 this.maxSpan = maxSpan;
141 this.newSlotQuantumGap = FastMath.round(newSlotInterval / QUANTUM_STEP);
142 this.generator = generator;
143 this.overridingMeanStep = overridingMeanStep;
144 this.maxNeighborsSize = maxNeighborsSize;
145 this.slots = new ArrayList<>(maxSlots);
146 this.getNeighborsCalls = new AtomicInteger(0);
147 this.generateCalls = new AtomicInteger(0);
148 this.evictions = new AtomicInteger(0);
149 this.lock = new ReentrantReadWriteLock();
150
151 }
152
153 /** Get the generator.
154 * @return generator
155 */
156 public TimeStampedGenerator<T> getGenerator() {
157 return generator;
158 }
159
160 /** Get the maximum number of independent cached time slots.
161 * @return maximum number of independent cached time slots
162 */
163 public int getMaxSlots() {
164 return maxSlots;
165 }
166
167 /** Get the maximum duration span in seconds of one slot.
168 * @return maximum duration span in seconds of one slot
169 */
170 public double getMaxSpan() {
171 return maxSpan;
172 }
173
174 /** Get quantum gap above which a new slot is created instead of extending an existing one.
175 * <p>
176 * The quantum gap is the {@code newSlotInterval} value provided at construction
177 * rounded to the nearest quantum step used internally by the cache.
178 * </p>
179 * @return quantum gap in seconds
180 */
181 public double getNewSlotQuantumGap() {
182 return newSlotQuantumGap * QUANTUM_STEP;
183 }
184
185 /** Get the number of calls to the {@link #getNeighbors(AbsoluteDate)} method.
186 * <p>
187 * This number of calls is used as a reference to interpret {@link #getGenerateCalls()}.
188 * </p>
189 * @return number of calls to the {@link #getNeighbors(AbsoluteDate)} method
190 * @see #getGenerateCalls()
191 */
192 public int getGetNeighborsCalls() {
193 return getNeighborsCalls.get();
194 }
195
196 /** Get the number of calls to the generate method.
197 * <p>
198 * This number of calls is related to the number of cache misses and may
199 * be used to tune the cache configuration. Each cache miss implies at
200 * least one call is performed, but may require several calls if the new
201 * date is far offset from the existing cache, depending on the number of
202 * elements and step between elements in the arrays returned by the generator.
203 * </p>
204 * @return number of calls to the generate method
205 * @see #getGetNeighborsCalls()
206 */
207 public int getGenerateCalls() {
208 return generateCalls.get();
209 }
210
211 /** Get the number of slots evictions.
212 * <p>
213 * This number should remain small when the max number of slots is sufficient
214 * with respect to the number of concurrent requests to the cache. If it
215 * increases too much, then the cache configuration is probably bad and cache
216 * does not really improve things (in this case, the {@link #getGenerateCalls()
217 * number of calls to the generate method} will probably increase too.
218 * </p>
219 * @return number of slots evictions
220 */
221 public int getSlotsEvictions() {
222 return evictions.get();
223 }
224
225 /** Get the number of slots in use.
226 * @return number of slots in use
227 */
228 public int getSlots() {
229
230 lock.readLock().lock();
231 try {
232 return slots.size();
233 } finally {
234 lock.readLock().unlock();
235 }
236
237 }
238
239 /** Get the total number of entries cached.
240 * @return total number of entries cached
241 */
242 public int getEntries() {
243
244 lock.readLock().lock();
245 try {
246 int entries = 0;
247 for (final Slot slot : slots) {
248 entries += slot.getEntries();
249 }
250 return entries;
251 } finally {
252 lock.readLock().unlock();
253 }
254
255 }
256
257 /** {@inheritDoc} */
258 @Override
259 public T getEarliest() throws IllegalStateException {
260
261 lock.readLock().lock();
262 try {
263 if (slots.isEmpty()) {
264 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
265 }
266 return slots.get(0).getEarliest();
267 } finally {
268 lock.readLock().unlock();
269 }
270
271 }
272
273 /** {@inheritDoc} */
274 @Override
275 public T getLatest() throws IllegalStateException {
276
277 lock.readLock().lock();
278 try {
279 if (slots.isEmpty()) {
280 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
281 }
282 return slots.get(slots.size() - 1).getLatest();
283 } finally {
284 lock.readLock().unlock();
285 }
286
287 }
288
289 /** {@inheritDoc} */
290 @Override
291 public int getMaxNeighborsSize() {
292 return maxNeighborsSize;
293 }
294
295 /** {@inheritDoc} */
296 @Override
297 public Stream<T> getNeighbors(final AbsoluteDate central, final int n) {
298
299 if (n > maxNeighborsSize) {
300 throw new OrekitException(OrekitMessages.NOT_ENOUGH_DATA, maxNeighborsSize);
301 }
302
303 lock.readLock().lock();
304 try {
305 getNeighborsCalls.incrementAndGet();
306 final long dateQuantum = quantum(central);
307 return selectSlot(central, dateQuantum).getNeighbors(central, dateQuantum, n);
308 } finally {
309 lock.readLock().unlock();
310 }
311
312 }
313
314 /** Convert a date to a rough global quantum.
315 * <p>
316 * We own a global read lock while calling this method.
317 * </p>
318 * @param date date to convert
319 * @return quantum corresponding to the date
320 */
321 private long quantum(final AbsoluteDate date) {
322 reference.compareAndSet(null, date);
323 return FastMath.round(date.durationFrom(reference.get()) / QUANTUM_STEP);
324 }
325
326 /** Select a slot containing a date.
327 * <p>
328 * We own a global read lock while calling this method.
329 * </p>
330 * @param date target date
331 * @param dateQuantum global quantum of the date
332 * @return slot covering the date
333 */
334 private Slot selectSlot(final AbsoluteDate date, final long dateQuantum) {
335
336 Slot selected = null;
337
338 int index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
339 if (slots.isEmpty() ||
340 slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
341 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
342 // no existing slot is suitable
343
344 // upgrade the read lock to a write lock so we can change the list of available slots
345 lock.readLock().unlock();
346 lock.writeLock().lock();
347
348 try {
349 // check slots again as another thread may have changed
350 // the list while we were waiting for the write lock
351 index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
352 if (slots.isEmpty() ||
353 slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
354 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
355
356 // we really need to create a new slot in the current thread
357 // (no other threads have created it while we were waiting for the lock)
358 if (!slots.isEmpty() &&
359 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
360 ++index;
361 }
362
363 if (slots.size() >= maxSlots) {
364 // we must prevent exceeding allowed max
365
366 // select the oldest accessed slot for eviction
367 int evict = 0;
368 for (int i = 0; i < slots.size(); ++i) {
369 if (slots.get(i).getLastAccess() < slots.get(evict).getLastAccess()) {
370 evict = i;
371 }
372 }
373
374 // evict the selected slot
375 evictions.incrementAndGet();
376 slots.remove(evict);
377
378 if (evict < index) {
379 // adjust index of created slot as it was shifted by the eviction
380 index--;
381 }
382 }
383
384 slots.add(index, new Slot(date));
385
386 }
387
388 } finally {
389 // downgrade back to a read lock
390 lock.readLock().lock();
391 lock.writeLock().unlock();
392 }
393 }
394
395 selected = slots.get(index);
396
397
398 return selected;
399
400 }
401
402 /** Get the index of the slot in which a date could be cached.
403 * <p>
404 * We own a global read lock while calling this method.
405 * </p>
406 * @param dateQuantum quantum of the date to search for
407 * @return the slot in which the date could be cached
408 */
409 private int slotIndex(final long dateQuantum) {
410
411 int iInf = 0;
412 final long qInf = slots.get(iInf).getEarliestQuantum();
413 int iSup = slots.size() - 1;
414 final long qSup = slots.get(iSup).getLatestQuantum();
415 while (iSup - iInf > 0) {
416 final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
417 final int iMed = FastMath.max(iInf, FastMath.min(iInterp, iSup));
418 final Slot slot = slots.get(iMed);
419 if (dateQuantum < slot.getEarliestQuantum()) {
420 iSup = iMed - 1;
421 } else if (dateQuantum > slot.getLatestQuantum()) {
422 iInf = FastMath.min(iSup, iMed + 1);
423 } else {
424 return iMed;
425 }
426 }
427
428 return iInf;
429
430 }
431
432 /** Time slot. */
433 private final class Slot {
434
435 /** Cached time-stamped entries. */
436 private final List<Entry> cache;
437
438 /** Earliest quantum. */
439 private AtomicLong earliestQuantum;
440
441 /** Latest quantum. */
442 private AtomicLong latestQuantum;
443
444 /** Index from a previous recent call. */
445 private AtomicInteger guessedIndex;
446
447 /** Last access time. */
448 private AtomicLong lastAccess;
449
450 /** Simple constructor.
451 * @param date central date for initial entries to insert in the slot
452 */
453 Slot(final AbsoluteDate date) {
454
455 // allocate cache
456 this.cache = new ArrayList<>();
457
458 // set up first entries
459 AbsoluteDate generationDate = date;
460
461 generateCalls.incrementAndGet();
462 for (final T entry : generateAndCheck(null, generationDate)) {
463 cache.add(new Entry(entry, quantum(entry.getDate())));
464 }
465 earliestQuantum = new AtomicLong(cache.get(0).getQuantum());
466 latestQuantum = new AtomicLong(cache.get(cache.size() - 1).getQuantum());
467
468 while (cache.size() < maxNeighborsSize) {
469 // we need to generate more entries
470
471 final AbsoluteDate entry0 = cache.get(0).getData().getDate();
472 final AbsoluteDate entryN = cache.get(cache.size() - 1).getData().getDate();
473 generateCalls.incrementAndGet();
474
475 final AbsoluteDate existingDate;
476 if (entryN.getDate().durationFrom(date) <= date.durationFrom(entry0.getDate())) {
477 // generate additional point at the end of the slot
478 existingDate = entryN;
479 generationDate = entryN.getDate().shiftedBy(getMeanStep() * (maxNeighborsSize - cache.size()));
480 appendAtEnd(generateAndCheck(existingDate, generationDate), date);
481 } else {
482 // generate additional point at the start of the slot
483 existingDate = entry0;
484 generationDate = entry0.getDate().shiftedBy(-getMeanStep() * (maxNeighborsSize - cache.size()));
485 insertAtStart(generateAndCheck(existingDate, generationDate), date);
486 }
487
488 }
489
490 guessedIndex = new AtomicInteger(cache.size() / 2);
491 lastAccess = new AtomicLong(System.currentTimeMillis());
492
493 }
494
495 /** Get the earliest entry contained in the slot.
496 * @return earliest entry contained in the slot
497 */
498 public T getEarliest() {
499 return cache.get(0).getData();
500 }
501
502 /** Get the quantum of the earliest date contained in the slot.
503 * @return quantum of the earliest date contained in the slot
504 */
505 public long getEarliestQuantum() {
506 return earliestQuantum.get();
507 }
508
509 /** Get the latest entry contained in the slot.
510 * @return latest entry contained in the slot
511 */
512 public T getLatest() {
513 return cache.get(cache.size() - 1).getData();
514 }
515
516 /** Get the quantum of the latest date contained in the slot.
517 * @return quantum of the latest date contained in the slot
518 */
519 public long getLatestQuantum() {
520 return latestQuantum.get();
521 }
522
523 /** Get the number of entries contained in the slot.
524 * @return number of entries contained in the slot
525 */
526 public int getEntries() {
527 return cache.size();
528 }
529
530 /** Get the mean step between entries.
531 * <p>
532 * If an overriding mean step has been defined at construction, then it will be returned instead.
533 * @return mean step between entries (or an arbitrary non-null value
534 * if there are fewer than 2 entries)
535 */
536 private double getMeanStep() {
537 if (cache.size() < 2) {
538 return 1.0;
539 } else {
540 if (!Double.isNaN(overridingMeanStep)) {
541 return overridingMeanStep;
542 } else {
543 final AbsoluteDate t0 = cache.get(0).getData().getDate();
544 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
545 return tn.durationFrom(t0) / (cache.size() - 1);
546 }
547 }
548 }
549
550 /** Get last access time of slot.
551 * @return last known access time
552 */
553 public long getLastAccess() {
554 return lastAccess.get();
555 }
556
557 /** Get the entries surrounding a central date.
558 * <p>
559 * If the central date is well within covered slot, the returned array
560 * will be balanced with half the points before central date and half the
561 * points after it (depending on n parity, of course). If the central date
562 * is near slot boundary and the underlying {@link TimeStampedGenerator
563 * generator} cannot extend it (i.e. it returns null), then the returned
564 * array will be unbalanced and will contain only the n earliest (or latest)
565 * cached entries. A typical example of the later case is leap seconds cache,
566 * since the number of leap seconds cannot be arbitrarily increased.
567 * </p>
568 * @param central central date
569 * @param dateQuantum global quantum of the date
570 * @param n number of neighbors
571 * @return a new array containing date neighbors
572 */
573 public Stream<T> getNeighbors(final AbsoluteDate central, final long dateQuantum, final int n) {
574 int index = entryIndex(central, dateQuantum);
575 int firstNeighbor = index - (n - 1) / 2;
576
577 if (firstNeighbor < 0 || firstNeighbor + n > cache.size()) {
578 // the cache is not balanced around the desired date, we can try to generate new data
579
580 // upgrade the read lock to a write lock so we can change the list of available slots
581 lock.readLock().unlock();
582 lock.writeLock().lock();
583
584 try {
585 // check entries again as another thread may have changed
586 // the list while we were waiting for the write lock
587 boolean loop = true;
588 while (loop) {
589 index = entryIndex(central, dateQuantum);
590 firstNeighbor = index - (n - 1) / 2;
591 if (firstNeighbor < 0 || firstNeighbor + n > cache.size()) {
592
593 // estimate which data we need to be generated
594 final double step = getMeanStep();
595 final AbsoluteDate existingDate;
596 final AbsoluteDate generationDate;
597 final boolean simplyRebalance;
598 if (firstNeighbor < 0) {
599 existingDate = cache.get(0).getData().getDate();
600 generationDate = existingDate.getDate().shiftedBy(step * firstNeighbor);
601 simplyRebalance = existingDate.getDate().compareTo(central) <= 0;
602 } else {
603 existingDate = cache.get(cache.size() - 1).getData().getDate();
604 generationDate = existingDate.getDate().shiftedBy(step * (firstNeighbor + n - cache.size()));
605 simplyRebalance = existingDate.getDate().compareTo(central) >= 0;
606 }
607 generateCalls.incrementAndGet();
608
609 // generated data and add it to the slot
610 try {
611 if (firstNeighbor < 0) {
612 insertAtStart(generateAndCheck(existingDate, generationDate), central);
613 } else {
614 appendAtEnd(generateAndCheck(existingDate, generationDate), central);
615 }
616 } catch (TimeStampedCacheException tce) {
617 if (simplyRebalance) {
618 // we were simply trying to rebalance an unbalanced interval near slot end
619 // we failed, but the central date is already covered by the existing (unbalanced) data
620 // so we ignore the exception and stop the loop, we will continue with what we have
621 loop = false;
622 } else {
623 throw tce;
624 }
625 }
626
627 } else {
628 loop = false;
629 }
630 }
631 } finally {
632 // downgrade back to a read lock
633 lock.readLock().lock();
634 lock.writeLock().unlock();
635 }
636
637 }
638
639 if (firstNeighbor + n > cache.size()) {
640 // we end up with a non-balanced neighborhood,
641 // adjust the start point to fit within the cache
642 firstNeighbor = cache.size() - n;
643 }
644 if (firstNeighbor < 0) {
645 firstNeighbor = 0;
646 }
647 final Stream.Builder<T> builder = Stream.builder();
648 for (int i = 0; i < n; ++i) {
649 builder.accept(cache.get(firstNeighbor + i).getData());
650 }
651
652 return builder.build();
653
654 }
655
656 /** Get the index of the entry corresponding to a date.
657 * <p>
658 * We own a local read lock while calling this method.
659 * </p>
660 * @param date date
661 * @param dateQuantum global quantum of the date
662 * @return index in the array such that entry[index] is before
663 * date and entry[index + 1] is after date (or they are at array boundaries)
664 */
665 private int entryIndex(final AbsoluteDate date, final long dateQuantum) {
666
667 // first quick guesses, assuming a recent search was close enough
668 final int guess = guessedIndex.get();
669 if (guess > 0 && guess < cache.size()) {
670 if (cache.get(guess).getQuantum() <= dateQuantum) {
671 if (guess + 1 < cache.size() && cache.get(guess + 1).getQuantum() > dateQuantum) {
672 // good guess!
673 return guess;
674 } else {
675 // perhaps we have simply shifted just one point forward ?
676 if (guess + 2 < cache.size() && cache.get(guess + 2).getQuantum() > dateQuantum) {
677 guessedIndex.set(guess + 1);
678 return guess + 1;
679 }
680 }
681 } else {
682 // perhaps we have simply shifted just one point backward ?
683 if (guess > 1 && cache.get(guess - 1).getQuantum() <= dateQuantum) {
684 guessedIndex.set(guess - 1);
685 return guess - 1;
686 }
687 }
688 }
689
690 // quick guesses have failed, we need to perform a full blown search
691 if (dateQuantum < getEarliestQuantum()) {
692 // date if before the first entry
693 return -1;
694 } else if (dateQuantum > getLatestQuantum()) {
695 // date is after the last entry
696 return cache.size();
697 } else {
698
699 // try to get an existing entry
700 int iInf = 0;
701 final long qInf = cache.get(iInf).getQuantum();
702 int iSup = cache.size() - 1;
703 final long qSup = cache.get(iSup).getQuantum();
704 while (iSup - iInf > 0) {
705 // within a continuous slot, entries are expected to be roughly linear
706 final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
707 final int iMed = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup));
708 final Entry entry = cache.get(iMed);
709 if (dateQuantum < entry.getQuantum()) {
710 iSup = iMed - 1;
711 } else if (dateQuantum > entry.getQuantum()) {
712 iInf = iMed;
713 } else {
714 guessedIndex.set(iMed);
715 return iMed;
716 }
717 }
718
719 guessedIndex.set(iInf);
720 return iInf;
721
722 }
723
724 }
725
726 /** Insert data at slot start.
727 * @param data data to insert
728 * @param requestedDate use for the error message.
729 */
730 private void insertAtStart(final List<T> data, final AbsoluteDate requestedDate) {
731
732 // insert data at start
733 boolean inserted = false;
734 final long q0 = earliestQuantum.get();
735 for (int i = 0; i < data.size(); ++i) {
736 final long quantum = quantum(data.get(i).getDate());
737 if (quantum < q0) {
738 cache.add(i, new Entry(data.get(i), quantum));
739 inserted = true;
740 } else {
741 break;
742 }
743 }
744
745 if (!inserted) {
746 final AbsoluteDate earliest = cache.get(0).getData().getDate();
747 throw new TimeStampedCacheException(
748 OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
749 earliest, requestedDate, earliest.durationFrom(requestedDate));
750 }
751
752 // evict excess data at end
753 final AbsoluteDate t0 = cache.get(0).getData().getDate();
754 while (cache.size() > maxNeighborsSize &&
755 cache.get(cache.size() - 1).getData().getDate().durationFrom(t0) > maxSpan) {
756 cache.remove(cache.size() - 1);
757 }
758
759 // update boundaries
760 earliestQuantum.set(cache.get(0).getQuantum());
761 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
762
763 }
764
765 /** Append data at slot end.
766 * @param data data to append
767 * @param requestedDate use for error message.
768 */
769 private void appendAtEnd(final List<T> data, final AbsoluteDate requestedDate) {
770
771 // append data at end
772 boolean appended = false;
773 final long qn = latestQuantum.get();
774 final int n = cache.size();
775 for (int i = data.size() - 1; i >= 0; --i) {
776 final long quantum = quantum(data.get(i).getDate());
777 if (quantum > qn) {
778 cache.add(n, new Entry(data.get(i), quantum));
779 appended = true;
780 } else {
781 break;
782 }
783 }
784
785 if (!appended) {
786 final AbsoluteDate latest = cache.get(cache.size() - 1).getData().getDate();
787 throw new TimeStampedCacheException(
788 OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
789 latest, requestedDate, requestedDate.durationFrom(latest));
790 }
791
792 // evict excess data at start
793 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
794 while (cache.size() > maxNeighborsSize &&
795 tn.durationFrom(cache.get(0).getData().getDate()) > maxSpan) {
796 cache.remove(0);
797 }
798
799 // update boundaries
800 earliestQuantum.set(cache.get(0).getQuantum());
801 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
802
803 }
804
805 /** Generate entries and check ordering.
806 * @param existingDate date of the closest already existing entry (may be null)
807 * @param date date that must be covered by the range of the generated array
808 * (guaranteed to lie between {@link #getEarliest()} and {@link #getLatest()})
809 * @return chronologically sorted list of generated entries
810 */
811 private List<T> generateAndCheck(final AbsoluteDate existingDate, final AbsoluteDate date) {
812 final List<T> entries = generator.generate(existingDate, date);
813 if (entries.isEmpty()) {
814 throw new TimeStampedCacheException(OrekitMessages.NO_DATA_GENERATED, date);
815 }
816 for (int i = 1; i < entries.size(); ++i) {
817 final AbsoluteDate previous = entries.get(i - 1).getDate();
818 final AbsoluteDate current = entries.get(i).getDate();
819 if (current.compareTo(previous) < 0) {
820 throw new TimeStampedCacheException(OrekitMessages.NON_CHRONOLOGICALLY_SORTED_ENTRIES,
821 previous, current, previous.durationFrom(current));
822 }
823 }
824 return entries;
825 }
826
827 /** Container for entries. */
828 private class Entry {
829
830 /** Entry data. */
831 private final T data;
832
833 /** Global quantum of the entry. */
834 private final long quantum;
835
836 /** Simple constructor.
837 * @param data entry data
838 * @param quantum entry quantum
839 */
840 Entry(final T data, final long quantum) {
841 this.quantum = quantum;
842 this.data = data;
843 }
844
845 /** Get the quantum.
846 * @return quantum
847 */
848 public long getQuantum() {
849 return quantum;
850 }
851
852 /** Get the data.
853 * @return data
854 */
855 public T getData() {
856 return data;
857 }
858
859 }
860 }
861
862 }