1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
38
39
40
41
42
43 public class GenericTimeStampedCache<T extends TimeStamped> implements TimeStampedCache<T> {
44
45
46 public static final int DEFAULT_CACHED_SLOTS_NUMBER = 10;
47
48
49 private static final double QUANTUM_STEP = 1.0e-6;
50
51
52 private final AtomicReference<AbsoluteDate> reference;
53
54
55 private final int maxSlots;
56
57
58 private final double maxSpan;
59
60
61 private final long newSlotQuantumGap;
62
63
64 private final TimeStampedGenerator<T> generator;
65
66
67 private final int neighborsSize;
68
69
70 private final List<Slot> slots;
71
72
73 private final AtomicInteger getNeighborsCalls;
74
75
76 private final AtomicInteger generateCalls;
77
78
79 private final AtomicInteger evictions;
80
81
82 private final ReadWriteLock lock;
83
84
85
86
87
88
89
90
91
92
93
94 public GenericTimeStampedCache(final int neighborsSize, final int maxSlots, final double maxSpan,
95 final double newSlotInterval, final TimeStampedGenerator<T> generator) {
96
97
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
121
122
123 public TimeStampedGenerator<T> getGenerator() {
124 return generator;
125 }
126
127
128
129
130 public int getMaxSlots() {
131 return maxSlots;
132 }
133
134
135
136
137 public double getMaxSpan() {
138 return maxSpan;
139 }
140
141
142
143
144
145
146
147
148 public double getNewSlotQuantumGap() {
149 return newSlotQuantumGap * QUANTUM_STEP;
150 }
151
152
153
154
155
156
157
158
159 public int getGetNeighborsCalls() {
160 return getNeighborsCalls.get();
161 }
162
163
164
165
166
167
168
169
170
171
172
173
174 public int getGenerateCalls() {
175 return generateCalls.get();
176 }
177
178
179
180
181
182
183
184
185
186
187
188 public int getSlotsEvictions() {
189 return evictions.get();
190 }
191
192
193
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
207
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
225
226
227
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
244
245
246
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
263
264
265 public int getNeighborsSize() {
266 return neighborsSize;
267 }
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
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
300
301
302
303
304
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
312
313
314
315
316
317
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
328
329
330 lock.readLock().unlock();
331 lock.writeLock().lock();
332
333 try {
334
335
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
342
343 if (!slots.isEmpty() &&
344 slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
345 ++index;
346 }
347
348 if (slots.size() >= maxSlots) {
349
350
351
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
360 evictions.incrementAndGet();
361 slots.remove(evict);
362
363 if (evict < index) {
364
365 index--;
366 }
367 }
368
369 slots.add(index, new Slot(date));
370
371 }
372
373 } finally {
374
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
388
389
390
391
392
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
418 private final class Slot {
419
420
421 private final List<Entry> cache;
422
423
424 private AtomicLong earliestQuantum;
425
426
427 private AtomicLong latestQuantum;
428
429
430 private AtomicInteger guessedIndex;
431
432
433 private AtomicLong lastAccess;
434
435
436
437
438 Slot(final AbsoluteDate date) {
439
440
441 this.cache = new ArrayList<Entry>();
442
443
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
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
463 existingDate = entryN;
464 generationDate = entryN.getDate().shiftedBy(getMeanStep() * (neighborsSize - cache.size()));
465 appendAtEnd(generateAndCheck(existingDate, generationDate), date);
466 } else {
467
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
481
482
483 public T getEarliest() {
484 return cache.get(0).getData();
485 }
486
487
488
489
490 public long getEarliestQuantum() {
491 return earliestQuantum.get();
492 }
493
494
495
496
497 public T getLatest() {
498 return cache.get(cache.size() - 1).getData();
499 }
500
501
502
503
504 public long getLatestQuantum() {
505 return latestQuantum.get();
506 }
507
508
509
510
511 public int getEntries() {
512 return cache.size();
513 }
514
515
516
517
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
530
531
532 public long getLastAccess() {
533 return lastAccess.get();
534 }
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
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
560
561
562 lock.readLock().unlock();
563 lock.writeLock().lock();
564
565 try {
566
567
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
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
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
600
601
602 loop = false;
603 } else {
604 throw tce;
605 }
606 }
607
608 } else {
609 loop = false;
610 }
611 }
612 } finally {
613
614 lock.readLock().lock();
615 lock.writeLock().unlock();
616 }
617
618 }
619
620 if (firstNeighbor + neighborsSize > cache.size()) {
621
622
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
638
639
640
641
642
643
644
645
646 private int entryIndex(final AbsoluteDate date, final long dateQuantum) {
647
648
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
654 return guess;
655 } else {
656
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
664 if (guess > 1 && cache.get(guess - 1).getQuantum() <= dateQuantum) {
665 guessedIndex.set(guess - 1);
666 return guess - 1;
667 }
668 }
669 }
670
671
672 if (dateQuantum < getEarliestQuantum()) {
673
674 return -1;
675 } else if (dateQuantum > getLatestQuantum()) {
676
677 return cache.size();
678 } else {
679
680
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
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
708
709
710
711 private void insertAtStart(final List<T> data, final AbsoluteDate requestedDate) {
712
713
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
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
741 earliestQuantum.set(cache.get(0).getQuantum());
742 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
743
744 }
745
746
747
748
749
750 private void appendAtEnd(final List<T> data, final AbsoluteDate requestedDate) {
751
752
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
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
781 earliestQuantum.set(cache.get(0).getQuantum());
782 latestQuantum.set(cache.get(cache.size() - 1).getQuantum());
783
784 }
785
786
787
788
789
790
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
809 private class Entry {
810
811
812 private final T data;
813
814
815 private final long quantum;
816
817
818
819
820
821 Entry(final T data, final long quantum) {
822 this.quantum = quantum;
823 this.data = data;
824 }
825
826
827
828
829 public long getQuantum() {
830 return quantum;
831 }
832
833
834
835
836 public T getData() {
837 return data;
838 }
839
840 }
841 }
842
843 }