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