1 /* Copyright 2002-2017 CS Systèmes d'Information
2 * Licensed to CS Systèmes d'Information (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 * @exception TimeStampedCacheException if entries are not chronologically
284 * sorted or if new data cannot be generated
285 * @see #getEarliest()
286 * @see #getLatest()
287 */
288 public Stream<T> getNeighbors(final AbsoluteDate central) throws TimeStampedCacheException {
289
290 lock.readLock().lock();
291 try {
292 getNeighborsCalls.incrementAndGet();
293 final long dateQuantum = quantum(central);
294 return selectSlot(central, dateQuantum).getNeighbors(central, dateQuantum);
295 } finally {
296 lock.readLock().unlock();
297 }
298
299 }
300
301 /** Convert a date to a rough global quantum.
302 * <p>
303 * We own a global read lock while calling this method.
304 * </p>
305 * @param date date to convert
306 * @return quantum corresponding to the date
307 */
308 private long quantum(final AbsoluteDate date) {
309 reference.compareAndSet(null, date);
310 return FastMath.round(date.durationFrom(reference.get()) / QUANTUM_STEP);
311 }
312
313 /** Select a slot containing a date.
314 * <p>
315 * We own a global read lock while calling this method.
316 * </p>
317 * @param date target date
318 * @param dateQuantum global quantum of the date
319 * @return slot covering the date
320 * @exception TimeStampedCacheException if entries are not chronologically
321 * sorted or if new data cannot be generated
322 */
323 private Slot selectSlot(final AbsoluteDate date, final long dateQuantum)
324 throws TimeStampedCacheException {
325
326 Slot selected = null;
327
328 int index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
329 if (slots.isEmpty() ||
330 slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
331 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
332 // no existing slot is suitable
333
334 // upgrade the read lock to a write lock so we can change the list of available slots
335 lock.readLock().unlock();
336 lock.writeLock().lock();
337
338 try {
339 // check slots again as another thread may have changed
340 // the list while we were waiting for the write lock
341 index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
342 if (slots.isEmpty() ||
343 slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
344 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
345
346 // we really need to create a new slot in the current thread
347 // (no other threads have created it while we were waiting for the lock)
348 if ((!slots.isEmpty()) &&
349 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
350 ++index;
351 }
352
353 if (slots.size() >= maxSlots) {
354 // we must prevent exceeding allowed max
355
356 // select the oldest accessed slot for eviction
357 int evict = 0;
358 for (int i = 0; i < slots.size(); ++i) {
359 if (slots.get(i).getLastAccess() < slots.get(evict).getLastAccess()) {
360 evict = i;
361 }
362 }
363
364 // evict the selected slot
365 evictions.incrementAndGet();
366 slots.remove(evict);
367
368 if (evict < index) {
369 // adjust index of created slot as it was shifted by the eviction
370 index--;
371 }
372 }
373
374 slots.add(index, new Slot(date));
375
376 }
377
378 } finally {
379 // downgrade back to a read lock
380 lock.readLock().lock();
381 lock.writeLock().unlock();
382 }
383 }
384
385 selected = slots.get(index);
386
387
388 return selected;
389
390 }
391
392 /** Get the index of the slot in which a date could be cached.
393 * <p>
394 * We own a global read lock while calling this method.
395 * </p>
396 * @param dateQuantum quantum of the date to search for
397 * @return the slot in which the date could be cached
398 */
399 private int slotIndex(final long dateQuantum) {
400
401 int iInf = 0;
402 final long qInf = slots.get(iInf).getEarliestQuantum();
403 int iSup = slots.size() - 1;
404 final long qSup = slots.get(iSup).getLatestQuantum();
405 while (iSup - iInf > 0) {
406 final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
407 final int iMed = FastMath.max(iInf, FastMath.min(iInterp, iSup));
408 final Slot slot = slots.get(iMed);
409 if (dateQuantum < slot.getEarliestQuantum()) {
410 iSup = iMed - 1;
411 } else if (dateQuantum > slot.getLatestQuantum()) {
412 iInf = FastMath.min(iSup, iMed + 1);
413 } else {
414 return iMed;
415 }
416 }
417
418 return iInf;
419
420 }
421
422 /** Time slot. */
423 private final class Slot {
424
425 /** Cached time-stamped entries. */
426 private final List<Entry> cache;
427
428 /** Earliest quantum. */
429 private AtomicLong earliestQuantum;
430
431 /** Latest quantum. */
432 private AtomicLong latestQuantum;
433
434 /** Index from a previous recent call. */
435 private AtomicInteger guessedIndex;
436
437 /** Last access time. */
438 private AtomicLong lastAccess;
439
440 /** Simple constructor.
441 * @param date central date for initial entries to insert in the slot
442 * @exception TimeStampedCacheException if entries are not chronologically
443 * sorted or if new data cannot be generated
444 */
445 Slot(final AbsoluteDate date) throws TimeStampedCacheException {
446
447 // allocate cache
448 this.cache = new ArrayList<Entry>();
449
450 // set up first entries
451 AbsoluteDate generationDate = date;
452
453 generateCalls.incrementAndGet();
454 for (final T entry : generateAndCheck(null, generationDate)) {
455 cache.add(new Entry(entry, quantum(entry.getDate())));
456 }
457 earliestQuantum = new AtomicLong(cache.get(0).getQuantum());
458 latestQuantum = new AtomicLong(cache.get(cache.size() - 1).getQuantum());
459
460 while (cache.size() < neighborsSize) {
461 // we need to generate more entries
462
463 final AbsoluteDate entry0 = cache.get(0).getData().getDate();
464 final AbsoluteDate entryN = cache.get(cache.size() - 1).getData().getDate();
465 generateCalls.incrementAndGet();
466
467 final AbsoluteDate existingDate;
468 if (entryN.getDate().durationFrom(date) <= date.durationFrom(entry0.getDate())) {
469 // generate additional point at the end of the slot
470 existingDate = entryN;
471 generationDate = entryN.getDate().shiftedBy(getMeanStep() * (neighborsSize - cache.size()));
472 appendAtEnd(generateAndCheck(existingDate, generationDate));
473 } else {
474 // generate additional point at the start of the slot
475 existingDate = entry0;
476 generationDate = entry0.getDate().shiftedBy(-getMeanStep() * (neighborsSize - cache.size()));
477 insertAtStart(generateAndCheck(existingDate, generationDate));
478 }
479
480 }
481
482 guessedIndex = new AtomicInteger(cache.size() / 2);
483 lastAccess = new AtomicLong(System.currentTimeMillis());
484
485 }
486
487 /** Get the earliest entry contained in the slot.
488 * @return earliest entry contained in the slot
489 */
490 public T getEarliest() {
491 return cache.get(0).getData();
492 }
493
494 /** Get the quantum of the earliest date contained in the slot.
495 * @return quantum of the earliest date contained in the slot
496 */
497 public long getEarliestQuantum() {
498 return earliestQuantum.get();
499 }
500
501 /** Get the latest entry contained in the slot.
502 * @return latest entry contained in the slot
503 */
504 public T getLatest() {
505 return cache.get(cache.size() - 1).getData();
506 }
507
508 /** Get the quantum of the latest date contained in the slot.
509 * @return quantum of the latest date contained in the slot
510 */
511 public long getLatestQuantum() {
512 return latestQuantum.get();
513 }
514
515 /** Get the number of entries contained din the slot.
516 * @return number of entries contained din the slot
517 */
518 public int getEntries() {
519 return cache.size();
520 }
521
522 /** Get the mean step between entries.
523 * @return mean step between entries (or an arbitrary non-null value
524 * if there are fewer than 2 entries)
525 */
526 private double getMeanStep() {
527 if (cache.size() < 2) {
528 return 1.0;
529 } else {
530 final AbsoluteDate t0 = cache.get(0).getData().getDate();
531 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
532 return tn.durationFrom(t0) / (cache.size() - 1);
533 }
534 }
535
536 /** Get last access time of slot.
537 * @return last known access time
538 */
539 public long getLastAccess() {
540 return lastAccess.get();
541 }
542
543 /** Get the entries surrounding a central date.
544 * <p>
545 * If the central date is well within covered slot, the returned array
546 * will be balanced with half the points before central date and half the
547 * points after it (depending on n parity, of course). If the central date
548 * is near slot boundary and the underlying {@link TimeStampedGenerator
549 * generator} cannot extend it (i.e. it returns null), then the returned
550 * array will be unbalanced and will contain only the n earliest (or latest)
551 * cached entries. A typical example of the later case is leap seconds cache,
552 * since the number of leap seconds cannot be arbitrarily increased.
553 * </p>
554 * @param central central date
555 * @param dateQuantum global quantum of the date
556 * @return a new array containing date neighbors
557 * @exception TimeStampedCacheException if entries are not chronologically
558 * sorted or if new data cannot be generated
559 * @see #getBefore(AbsoluteDate)
560 * @see #getAfter(AbsoluteDate)
561 */
562 public Stream<T> getNeighbors(final AbsoluteDate central, final long dateQuantum)
563 throws TimeStampedCacheException {
564
565 int index = entryIndex(central, dateQuantum);
566 int firstNeighbor = index - (neighborsSize - 1) / 2;
567
568 if (firstNeighbor < 0 || firstNeighbor + neighborsSize > cache.size()) {
569 // the cache is not balanced around the desired date, we can try to generate new data
570
571 // upgrade the read lock to a write lock so we can change the list of available slots
572 lock.readLock().unlock();
573 lock.writeLock().lock();
574
575 try {
576 // check entries again as another thread may have changed
577 // the list while we were waiting for the write lock
578 boolean loop = true;
579 while (loop) {
580 index = entryIndex(central, dateQuantum);
581 firstNeighbor = index - (neighborsSize - 1) / 2;
582 if (firstNeighbor < 0 || firstNeighbor + neighborsSize > cache.size()) {
583
584 // estimate which data we need to be generated
585 final double step = getMeanStep();
586 final AbsoluteDate existingDate;
587 final AbsoluteDate generationDate;
588 final boolean simplyRebalance;
589 if (firstNeighbor < 0) {
590 existingDate = cache.get(0).getData().getDate();
591 generationDate = existingDate.getDate().shiftedBy(step * firstNeighbor);
592 simplyRebalance = existingDate.getDate().compareTo(central) <= 0;
593 } else {
594 existingDate = cache.get(cache.size() - 1).getData().getDate();
595 generationDate = existingDate.getDate().shiftedBy(step * (firstNeighbor + neighborsSize - cache.size()));
596 simplyRebalance = existingDate.getDate().compareTo(central) >= 0;
597 }
598 generateCalls.incrementAndGet();
599
600 // generated data and add it to the slot
601 try {
602 if (firstNeighbor < 0) {
603 insertAtStart(generateAndCheck(existingDate, generationDate));
604 } else {
605 appendAtEnd(generateAndCheck(existingDate, generationDate));
606 }
607 } catch (TimeStampedCacheException tce) {
608 if (simplyRebalance) {
609 // we were simply trying to rebalance an unbalanced interval near slot end
610 // we failed, but the central date is already covered by the existing (unbalanced) data
611 // so we ignore the exception and stop the loop, we will continue with what we have
612 loop = false;
613 } else {
614 throw tce;
615 }
616 }
617
618 } else {
619 loop = false;
620 }
621 }
622 } finally {
623 // downgrade back to a read lock
624 lock.readLock().lock();
625 lock.writeLock().unlock();
626 }
627
628 }
629
630 if (firstNeighbor + neighborsSize > cache.size()) {
631 // we end up with a non-balanced neighborhood,
632 // adjust the start point to fit within the cache
633 firstNeighbor = cache.size() - neighborsSize;
634 }
635 if (firstNeighbor < 0) {
636 firstNeighbor = 0;
637 }
638 final Stream.Builder<T> builder = Stream.builder();
639 for (int i = 0; i < neighborsSize; ++i) {
640 builder.accept(cache.get(firstNeighbor + i).getData());
641 }
642
643 return builder.build();
644
645 }
646
647 /** Get the index of the entry corresponding to a date.
648 * <p>
649 * We own a local read lock while calling this method.
650 * </p>
651 * @param date date
652 * @param dateQuantum global quantum of the date
653 * @return index in the array such that entry[index] is before
654 * date and entry[index + 1] is after date (or they are at array boundaries)
655 */
656 private int entryIndex(final AbsoluteDate date, final long dateQuantum) {
657
658 // first quick guesses, assuming a recent search was close enough
659 final int guess = guessedIndex.get();
660 if (guess > 0 && guess < cache.size()) {
661 if (cache.get(guess).getQuantum() <= dateQuantum) {
662 if (guess + 1 < cache.size() && cache.get(guess + 1).getQuantum() > dateQuantum) {
663 // good guess!
664 return guess;
665 } else {
666 // perhaps we have simply shifted just one point forward ?
667 if (guess + 2 < cache.size() && cache.get(guess + 2).getQuantum() > dateQuantum) {
668 guessedIndex.set(guess + 1);
669 return guess + 1;
670 }
671 }
672 } else {
673 // perhaps we have simply shifted just one point backward ?
674 if (guess > 1 && cache.get(guess - 1).getQuantum() <= dateQuantum) {
675 guessedIndex.set(guess - 1);
676 return guess - 1;
677 }
678 }
679 }
680
681 // quick guesses have failed, we need to perform a full blown search
682 if (dateQuantum < getEarliestQuantum()) {
683 // date if before the first entry
684 return -1;
685 } else if (dateQuantum > getLatestQuantum()) {
686 // date is after the last entry
687 return cache.size();
688 } else {
689
690 // try to get an existing entry
691 int iInf = 0;
692 final long qInf = cache.get(iInf).getQuantum();
693 int iSup = cache.size() - 1;
694 final long qSup = cache.get(iSup).getQuantum();
695 while (iSup - iInf > 0) {
696 // within a continuous slot, entries are expected to be roughly linear
697 final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
698 final int iMed = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup));
699 final Entry entry = cache.get(iMed);
700 if (dateQuantum < entry.getQuantum()) {
701 iSup = iMed - 1;
702 } else if (dateQuantum > entry.getQuantum()) {
703 iInf = iMed;
704 } else {
705 guessedIndex.set(iMed);
706 return iMed;
707 }
708 }
709
710 guessedIndex.set(iInf);
711 return iInf;
712
713 }
714
715 }
716
717 /** Insert data at slot start.
718 * @param data data to insert
719 * @exception TimeStampedCacheException if new data cannot be generated
720 */
721 private void insertAtStart(final List<T> data) throws TimeStampedCacheException {
722
723 // insert data at start
724 boolean inserted = false;
725 final long q0 = earliestQuantum.get();
726 for (int i = 0; i < data.size(); ++i) {
727 final long quantum = quantum(data.get(i).getDate());
728 if (quantum < q0) {
729 cache.add(i, new Entry(data.get(i), quantum));
730 inserted = true;
731 } else {
732 break;
733 }
734 }
735
736 if (!inserted) {
737 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
738 cache.get(0).getData().getDate());
739 }
740
741 // evict excess data at end
742 final AbsoluteDate t0 = cache.get(0).getData().getDate();
743 while (cache.size() > neighborsSize &&
744 cache.get(cache.size() - 1).getData().getDate().durationFrom(t0) > maxSpan) {
745 cache.remove(cache.size() - 1);
746 }
747
748 // update boundaries
749 earliestQuantum.set(cache.get(0).getQuantum());
750 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
751
752 }
753
754 /** Append data at slot end.
755 * @param data data to append
756 * @exception TimeStampedCacheException if new data cannot be generated
757 */
758 private void appendAtEnd(final List<T> data) throws TimeStampedCacheException {
759
760 // append data at end
761 boolean appended = false;
762 final long qn = latestQuantum.get();
763 final int n = cache.size();
764 for (int i = data.size() - 1; i >= 0; --i) {
765 final long quantum = quantum(data.get(i).getDate());
766 if (quantum > qn) {
767 cache.add(n, new Entry(data.get(i), quantum));
768 appended = true;
769 } else {
770 break;
771 }
772 }
773
774 if (!appended) {
775 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
776 cache.get(cache.size() - 1).getData().getDate());
777 }
778
779 // evict excess data at start
780 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
781 while (cache.size() > neighborsSize &&
782 tn.durationFrom(cache.get(0).getData().getDate()) > maxSpan) {
783 cache.remove(0);
784 }
785
786 // update boundaries
787 earliestQuantum.set(cache.get(0).getQuantum());
788 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
789
790 }
791
792 /** Generate entries and check ordering.
793 * @param existingDate date of the closest already existing entry (may be null)
794 * @param date date that must be covered by the range of the generated array
795 * (guaranteed to lie between {@link #getEarliest()} and {@link #getLatest()})
796 * @return chronologically sorted list of generated entries
797 * @exception TimeStampedCacheException if if entries are not chronologically
798 * sorted or if new data cannot be generated
799 */
800 private List<T> generateAndCheck(final AbsoluteDate existingDate, final AbsoluteDate date)
801 throws TimeStampedCacheException {
802 final List<T> entries = generator.generate(existingDate, date);
803 if (entries.isEmpty()) {
804 throw new TimeStampedCacheException(OrekitMessages.NO_DATA_GENERATED, date);
805 }
806 for (int i = 1; i < entries.size(); ++i) {
807 if (entries.get(i).getDate().compareTo(entries.get(i - 1).getDate()) < 0) {
808 throw new TimeStampedCacheException(OrekitMessages.NON_CHRONOLOGICALLY_SORTED_ENTRIES,
809 entries.get(i - 1).getDate(),
810 entries.get(i).getDate());
811 }
812 }
813 return entries;
814 }
815
816 /** Container for entries. */
817 private class Entry {
818
819 /** Entry data. */
820 private final T data;
821
822 /** Global quantum of the entry. */
823 private final long quantum;
824
825 /** Simple constructor.
826 * @param data entry data
827 * @param quantum entry quantum
828 */
829 Entry(final T data, final long quantum) {
830 this.quantum = quantum;
831 this.data = data;
832 }
833
834 /** Get the quantum.
835 * @return quantum
836 */
837 public long getQuantum() {
838 return quantum;
839 }
840
841 /** Get the data.
842 * @return data
843 */
844 public T getData() {
845 return data;
846 }
847
848 }
849 }
850
851 }