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 }