GenericTimeStampedCache.java

  1. /* Copyright 2002-2025 CS GROUP
  2.  * Licensed to CS GROUP (CS) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * CS licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *   http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.orekit.utils;

  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;

  28. import org.hipparchus.exception.LocalizedCoreFormats;
  29. import org.hipparchus.util.FastMath;
  30. import org.orekit.errors.OrekitException;
  31. import org.orekit.errors.OrekitIllegalArgumentException;
  32. import org.orekit.errors.OrekitIllegalStateException;
  33. import org.orekit.errors.OrekitMessages;
  34. import org.orekit.errors.TimeStampedCacheException;
  35. import org.orekit.time.AbsoluteDate;
  36. import org.orekit.time.TimeStamped;

  38. /** Generic thread-safe cache for {@link TimeStamped time-stamped} data.

  40.  * @param <T> Type of the cached data.

  42.  * @author Luc Maisonobe
  43.  */
  44. public class GenericTimeStampedCache<T extends TimeStamped> implements TimeStampedCache<T> {

  46.     /** Default number of independent cached time slots. */
  47.     public static final int DEFAULT_CACHED_SLOTS_NUMBER = 10;

  49.     /** Quantum step. */
  50.     private static final double QUANTUM_STEP = 1.0e-6;

  52.     /** Reference date for indexing. */
  53.     private final AtomicReference<AbsoluteDate> reference;

  55.     /** Maximum number of independent cached time slots. */
  56.     private final int maxSlots;

  58.     /** Maximum duration span in seconds of one slot. */
  59.     private final double maxSpan;

  61.     /** Quantum gap above which a new slot is created instead of extending an existing one. */
  62.     private final long newSlotQuantumGap;

  64.     /** Generator to use for yet non-cached data. */
  65.     private final TimeStampedGenerator<T> generator;

  67.     /** Overriding mean step. */
  68.     private final double overridingMeanStep;

  70.     /** Maximum number of entries in a neighbors array. */
  71.     private final int maxNeighborsSize;

  73.     /** Independent time slots cached. */
  74.     private final List<Slot> slots;

  76.     /** Number of calls to the getNeighbors method. */
  77.     private final AtomicInteger getNeighborsCalls;

  79.     /** Number of calls to the generate method. */
  80.     private final AtomicInteger generateCalls;

  82.     /** Number of evictions. */
  83.     private final AtomicInteger evictions;

  85.     /** Global lock. */
  86.     private final ReadWriteLock lock;

  88.     /** Simple constructor.
  89.      * @param maxNeighborsSize maximum size of the arrays to be returned by {@link
  90.      * #getNeighbors(AbsoluteDate, int)}, must be at least 2
  91.      * @param maxSlots maximum number of independent cached time slots
  92.      * @param maxSpan maximum duration span in seconds of one slot
  93.      * (can be set to {@code Double.POSITIVE_INFINITY} if desired)
  94.      * @param newSlotInterval time interval above which a new slot is created
  95.      * instead of extending an existing one
  96.      * @param generator generator to use for yet non-existent data
  97.      */
  98.     public GenericTimeStampedCache(final int maxNeighborsSize, final int maxSlots, final double maxSpan,
  99.                                    final double newSlotInterval, final TimeStampedGenerator<T> generator) {
  100.         this(maxNeighborsSize, maxSlots, maxSpan, newSlotInterval, generator, Double.NaN);

  102.     }

  104.     /** Simple constructor with overriding minimum step.
  105.      * @param maxNeighborsSize maximum size of the arrays to be returned by {@link
  106.      * #getNeighbors(AbsoluteDate, int)}, must be at least 2
  107.      * @param maxSlots maximum number of independent cached time slots
  108.      * @param maxSpan maximum duration span in seconds of one slot
  109.      * (can be set to {@code Double.POSITIVE_INFINITY} if desired)
  110.      * @param newSlotInterval time interval above which a new slot is created
  111.      * instead of extending an existing one
  112.      * @param generator generator to use for yet non-existent data
  113.      * @param overridingMeanStep overriding mean step designed for non-homogeneous tabulated values. To be used for example
  114.      *                    when caching monthly tabulated values. Use {@code Double.NaN} otherwise.
  115.      * @throws OrekitIllegalArgumentException if :
  116.      * <ul>
  117.      *     <li>neighbors size &lt; 2 </li>
  118.      *     <li>maximum allowed number of slots &lt; 1</li>
  119.      *     <li>minimum step ≤ 0 </li>
  120.      * </ul>
  121.      */
  122.     public GenericTimeStampedCache(final int maxNeighborsSize, final int maxSlots, final double maxSpan,
  123.                                    final double newSlotInterval, final TimeStampedGenerator<T> generator,
  124.                                    final double overridingMeanStep) {

  126.         // safety check
  127.         if (maxSlots < 1) {
  128.             throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL, maxSlots, 1);
  129.         }
  130.         if (overridingMeanStep <= 0) {
  131.             throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL_BOUND_EXCLUDED,
  132.                                                      overridingMeanStep, 0);
  133.         }
  134.         if (maxNeighborsSize < 2) {
  135.             throw new OrekitIllegalArgumentException(OrekitMessages.NOT_ENOUGH_CACHED_NEIGHBORS, maxNeighborsSize, 2);
  136.         }

  138.         this.reference          = new AtomicReference<>();
  139.         this.maxSlots           = maxSlots;
  140.         this.maxSpan            = maxSpan;
  141.         this.newSlotQuantumGap  = FastMath.round(newSlotInterval / QUANTUM_STEP);
  142.         this.generator          = generator;
  143.         this.overridingMeanStep = overridingMeanStep;
  144.         this.maxNeighborsSize   = maxNeighborsSize;
  145.         this.slots              = new ArrayList<>(maxSlots);
  146.         this.getNeighborsCalls  = new AtomicInteger(0);
  147.         this.generateCalls      = new AtomicInteger(0);
  148.         this.evictions          = new AtomicInteger(0);
  149.         this.lock               = new ReentrantReadWriteLock();

  151.     }

  153.     /** Get the generator.
  154.      * @return generator
  155.      */
  156.     public TimeStampedGenerator<T> getGenerator() {
  157.         return generator;
  158.     }

  160.     /** Get the maximum number of independent cached time slots.
  161.      * @return maximum number of independent cached time slots
  162.      */
  163.     public int getMaxSlots() {
  164.         return maxSlots;
  165.     }

  167.     /** Get the maximum duration span in seconds of one slot.
  168.      * @return maximum duration span in seconds of one slot
  169.      */
  170.     public double getMaxSpan() {
  171.         return maxSpan;
  172.     }

  174.     /** Get quantum gap above which a new slot is created instead of extending an existing one.
  175.      * <p>
  176.      * The quantum gap is the {@code newSlotInterval} value provided at construction
  177.      * rounded to the nearest quantum step used internally by the cache.
  178.      * </p>
  179.      * @return quantum gap in seconds
  180.      */
  181.     public double getNewSlotQuantumGap() {
  182.         return newSlotQuantumGap * QUANTUM_STEP;
  183.     }

  185.     /** Get the number of calls to the {@link #getNeighbors(AbsoluteDate)} method.
  186.      * <p>
  187.      * This number of calls is used as a reference to interpret {@link #getGenerateCalls()}.
  188.      * </p>
  189.      * @return number of calls to the {@link #getNeighbors(AbsoluteDate)} method
  190.      * @see #getGenerateCalls()
  191.      */
  192.     public int getGetNeighborsCalls() {
  193.         return getNeighborsCalls.get();
  194.     }

  196.     /** Get the number of calls to the generate method.
  197.      * <p>
  198.      * This number of calls is related to the number of cache misses and may
  199.      * be used to tune the cache configuration. Each cache miss implies at
  200.      * least one call is performed, but may require several calls if the new
  201.      * date is far offset from the existing cache, depending on the number of
  202.      * elements and step between elements in the arrays returned by the generator.
  203.      * </p>
  204.      * @return number of calls to the generate method
  205.      * @see #getGetNeighborsCalls()
  206.      */
  207.     public int getGenerateCalls() {
  208.         return generateCalls.get();
  209.     }

  211.     /** Get the number of slots evictions.
  212.      * <p>
  213.      * This number should remain small when the max number of slots is sufficient
  214.      * with respect to the number of concurrent requests to the cache. If it
  215.      * increases too much, then the cache configuration is probably bad and cache
  216.      * does not really improve things (in this case, the {@link #getGenerateCalls()
  217.      * number of calls to the generate method} will probably increase too.
  218.      * </p>
  219.      * @return number of slots evictions
  220.      */
  221.     public int getSlotsEvictions() {
  222.         return evictions.get();
  223.     }

  225.     /** Get the number of slots in use.
  226.      * @return number of slots in use
  227.      */
  228.     public int getSlots() {

  230.         lock.readLock().lock();
  231.         try {
  232.             return slots.size();
  233.         } finally {
  234.             lock.readLock().unlock();
  235.         }

  237.     }

  239.     /** Get the total number of entries cached.
  240.      * @return total number of entries cached
  241.      */
  242.     public int getEntries() {

  244.         lock.readLock().lock();
  245.         try {
  246.             int entries = 0;
  247.             for (final Slot slot : slots) {
  248.                 entries += slot.getEntries();
  249.             }
  250.             return entries;
  251.         } finally {
  252.             lock.readLock().unlock();
  253.         }

  255.     }

  257.     /** {@inheritDoc} */
  258.     @Override
  259.     public T getEarliest() throws IllegalStateException {

  261.         lock.readLock().lock();
  262.         try {
  263.             if (slots.isEmpty()) {
  264.                 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
  265.             }
  266.             return slots.get(0).getEarliest();
  267.         } finally {
  268.             lock.readLock().unlock();
  269.         }

  271.     }

  273.     /** {@inheritDoc} */
  274.     @Override
  275.     public T getLatest() throws IllegalStateException {

  277.         lock.readLock().lock();
  278.         try {
  279.             if (slots.isEmpty()) {
  280.                 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
  281.             }
  282.             return slots.get(slots.size() - 1).getLatest();
  283.         } finally {
  284.             lock.readLock().unlock();
  285.         }

  287.     }

  289.     /** {@inheritDoc} */
  290.     @Override
  291.     public int getMaxNeighborsSize() {
  292.         return maxNeighborsSize;
  293.     }

  295.     /** {@inheritDoc} */
  296.     @Override
  297.     public Stream<T> getNeighbors(final AbsoluteDate central, final int n) {

  299.         if (n > maxNeighborsSize) {
  300.             throw new OrekitException(OrekitMessages.NOT_ENOUGH_DATA, maxNeighborsSize);
  301.         }

  303.         lock.readLock().lock();
  304.         try {
  305.             getNeighborsCalls.incrementAndGet();
  306.             final long dateQuantum = quantum(central);
  307.             return selectSlot(central, dateQuantum).getNeighbors(central, dateQuantum, n);
  308.         } finally {
  309.             lock.readLock().unlock();
  310.         }

  312.     }

  314.     /** Convert a date to a rough global quantum.
  315.      * <p>
  316.      * We own a global read lock while calling this method.
  317.      * </p>
  318.      * @param date date to convert
  319.      * @return quantum corresponding to the date
  320.      */
  321.     private long quantum(final AbsoluteDate date) {
  322.         reference.compareAndSet(null, date);
  323.         return FastMath.round(date.durationFrom(reference.get()) / QUANTUM_STEP);
  324.     }

  326.     /** Select a slot containing a date.
  327.      * <p>
  328.      * We own a global read lock while calling this method.
  329.      * </p>
  330.      * @param date target date
  331.      * @param dateQuantum global quantum of the date
  332.      * @return slot covering the date
  333.      */
  334.     private Slot selectSlot(final AbsoluteDate date, final long dateQuantum) {

  336.         Slot selected = null;

  338.         int index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
  339.         if (slots.isEmpty() ||
  340.             slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
  341.             slots.get(index).getLatestQuantum()   < dateQuantum - newSlotQuantumGap) {
  342.             // no existing slot is suitable

  344.             // upgrade the read lock to a write lock so we can change the list of available slots
  345.             lock.readLock().unlock();
  346.             lock.writeLock().lock();

  348.             try {
  349.                 // check slots again as another thread may have changed
  350.                 // the list while we were waiting for the write lock
  351.                 index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
  352.                 if (slots.isEmpty() ||
  353.                     slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
  354.                     slots.get(index).getLatestQuantum()   < dateQuantum - newSlotQuantumGap) {

  356.                     // we really need to create a new slot in the current thread
  357.                     // (no other threads have created it while we were waiting for the lock)
  358.                     if (!slots.isEmpty() &&
  359.                         slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
  360.                         ++index;
  361.                     }

  363.                     if (slots.size() >= maxSlots) {
  364.                         // we must prevent exceeding allowed max

  366.                         // select the oldest accessed slot for eviction
  367.                         int evict = 0;
  368.                         for (int i = 0; i < slots.size(); ++i) {
  369.                             if (slots.get(i).getLastAccess() < slots.get(evict).getLastAccess()) {
  370.                                 evict = i;
  371.                             }
  372.                         }

  374.                         // evict the selected slot
  375.                         evictions.incrementAndGet();
  376.                         slots.remove(evict);

  378.                         if (evict < index) {
  379.                             // adjust index of created slot as it was shifted by the eviction
  380.                             index--;
  381.                         }
  382.                     }

  384.                     slots.add(index, new Slot(date));

  386.                 }

  388.             } finally {
  389.                 // downgrade back to a read lock
  390.                 lock.readLock().lock();
  391.                 lock.writeLock().unlock();
  392.             }
  393.         }

  395.         selected = slots.get(index);


  398.         return selected;

  400.     }

  402.     /** Get the index of the slot in which a date could be cached.
  403.      * <p>
  404.      * We own a global read lock while calling this method.
  405.      * </p>
  406.      * @param dateQuantum quantum of the date to search for
  407.      * @return the slot in which the date could be cached
  408.      */
  409.     private int slotIndex(final long dateQuantum) {

  411.         int  iInf = 0;
  412.         final long qInf = slots.get(iInf).getEarliestQuantum();
  413.         int  iSup = slots.size() - 1;
  414.         final long qSup = slots.get(iSup).getLatestQuantum();
  415.         while (iSup - iInf > 0) {
  416.             final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
  417.             final int iMed    = FastMath.max(iInf, FastMath.min(iInterp, iSup));
  418.             final Slot slot   = slots.get(iMed);
  419.             if (dateQuantum < slot.getEarliestQuantum()) {
  420.                 iSup = iMed - 1;
  421.             } else if (dateQuantum > slot.getLatestQuantum()) {
  422.                 iInf = FastMath.min(iSup, iMed + 1);
  423.             } else {
  424.                 return iMed;
  425.             }
  426.         }

  428.         return iInf;

  430.     }

  432.     /** Time slot. */
  433.     private final class Slot {

  435.         /** Cached time-stamped entries. */
  436.         private final List<Entry> cache;

  438.         /** Earliest quantum. */
  439.         private AtomicLong earliestQuantum;

  441.         /** Latest quantum. */
  442.         private AtomicLong latestQuantum;

  444.         /** Index from a previous recent call. */
  445.         private AtomicInteger guessedIndex;

  447.         /** Last access time. */
  448.         private AtomicLong lastAccess;

  450.         /** Simple constructor.
  451.          * @param date central date for initial entries to insert in the slot
  452.          */
  453.         Slot(final AbsoluteDate date) {

  455.             // allocate cache
  456.             this.cache = new ArrayList<>();

  458.             // set up first entries
  459.             AbsoluteDate generationDate = date;

  461.             generateCalls.incrementAndGet();
  462.             for (final T entry : generateAndCheck(null, generationDate)) {
  463.                 cache.add(new Entry(entry, quantum(entry.getDate())));
  464.             }
  465.             earliestQuantum = new AtomicLong(cache.get(0).getQuantum());
  466.             latestQuantum   = new AtomicLong(cache.get(cache.size() - 1).getQuantum());

  468.             while (cache.size() < maxNeighborsSize) {
  469.                 // we need to generate more entries

  471.                 final AbsoluteDate entry0 = cache.get(0).getData().getDate();
  472.                 final AbsoluteDate entryN = cache.get(cache.size() - 1).getData().getDate();
  473.                 generateCalls.incrementAndGet();

  475.                 final AbsoluteDate existingDate;
  476.                 if (entryN.getDate().durationFrom(date) <= date.durationFrom(entry0.getDate())) {
  477.                     // generate additional point at the end of the slot
  478.                     existingDate = entryN;
  479.                     generationDate = entryN.getDate().shiftedBy(getMeanStep() * (maxNeighborsSize - cache.size()));
  480.                     appendAtEnd(generateAndCheck(existingDate, generationDate), date);
  481.                 } else {
  482.                     // generate additional point at the start of the slot
  483.                     existingDate = entry0;
  484.                     generationDate = entry0.getDate().shiftedBy(-getMeanStep() * (maxNeighborsSize - cache.size()));
  485.                     insertAtStart(generateAndCheck(existingDate, generationDate), date);
  486.                 }

  488.             }

  490.             guessedIndex    = new AtomicInteger(cache.size() / 2);
  491.             lastAccess      = new AtomicLong(System.currentTimeMillis());

  493.         }

  495.         /** Get the earliest entry contained in the slot.
  496.          * @return earliest entry contained in the slot
  497.          */
  498.         public T getEarliest() {
  499.             return cache.get(0).getData();
  500.         }

  502.         /** Get the quantum of the earliest date contained in the slot.
  503.          * @return quantum of the earliest date contained in the slot
  504.          */
  505.         public long getEarliestQuantum() {
  506.             return earliestQuantum.get();
  507.         }

  509.         /** Get the latest entry contained in the slot.
  510.          * @return latest entry contained in the slot
  511.          */
  512.         public T getLatest() {
  513.             return cache.get(cache.size() - 1).getData();
  514.         }

  516.         /** Get the quantum of the latest date contained in the slot.
  517.          * @return quantum of the latest date contained in the slot
  518.          */
  519.         public long getLatestQuantum() {
  520.             return latestQuantum.get();
  521.         }

  523.         /** Get the number of entries contained in the slot.
  524.          * @return number of entries contained in the slot
  525.          */
  526.         public int getEntries() {
  527.             return cache.size();
  528.         }

  530.         /** Get the mean step between entries.
  531.          * <p>
  532.          * If an overriding mean step has been defined at construction, then it will be returned instead.
  533.          * @return mean step between entries (or an arbitrary non-null value
  534.          * if there are fewer than 2 entries)
  535.          */
  536.         private double getMeanStep() {
  537.             if (cache.size() < 2) {
  538.                 return 1.0;
  539.             } else {
  540.                 if (!Double.isNaN(overridingMeanStep)) {
  541.                     return overridingMeanStep;
  542.                 } else {
  543.                     final AbsoluteDate t0 = cache.get(0).getData().getDate();
  544.                     final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  545.                     return tn.durationFrom(t0) / (cache.size() - 1);
  546.                 }
  547.             }
  548.         }

  550.         /** Get last access time of slot.
  551.          * @return last known access time
  552.          */
  553.         public long getLastAccess() {
  554.             return lastAccess.get();
  555.         }

  557.         /** Get the entries surrounding a central date.
  558.          * <p>
  559.          * If the central date is well within covered slot, the returned array
  560.          * will be balanced with half the points before central date and half the
  561.          * points after it (depending on n parity, of course). If the central date
  562.          * is near slot boundary and the underlying {@link TimeStampedGenerator
  563.          * generator} cannot extend it (i.e. it returns null), then the returned
  564.          * array will be unbalanced and will contain only the n earliest (or latest)
  565.          * cached entries. A typical example of the later case is leap seconds cache,
  566.          * since the number of leap seconds cannot be arbitrarily increased.
  567.          * </p>
  568.          * @param central central date
  569.          * @param dateQuantum global quantum of the date
  570.          * @param n number of neighbors
  571.          * @return a new array containing date neighbors
  572.          */
  573.         public Stream<T> getNeighbors(final AbsoluteDate central, final long dateQuantum, final int n) {
  574.             int index         = entryIndex(central, dateQuantum);
  575.             int firstNeighbor = index - (n - 1) / 2;

  577.             if (firstNeighbor < 0 || firstNeighbor + n > cache.size()) {
  578.                 // the cache is not balanced around the desired date, we can try to generate new data

  580.                 // upgrade the read lock to a write lock so we can change the list of available slots
  581.                 lock.readLock().unlock();
  582.                 lock.writeLock().lock();

  584.                 try {
  585.                     // check entries again as another thread may have changed
  586.                     // the list while we were waiting for the write lock
  587.                     boolean loop = true;
  588.                     while (loop) {
  589.                         index         = entryIndex(central, dateQuantum);
  590.                         firstNeighbor = index - (n - 1) / 2;
  591.                         if (firstNeighbor < 0 || firstNeighbor + n > cache.size()) {

  593.                             // estimate which data we need to be generated
  594.                             final double step = getMeanStep();
  595.                             final AbsoluteDate existingDate;
  596.                             final AbsoluteDate generationDate;
  597.                             final boolean simplyRebalance;
  598.                             if (firstNeighbor < 0) {
  599.                                 existingDate    = cache.get(0).getData().getDate();
  600.                                 generationDate  = existingDate.getDate().shiftedBy(step * firstNeighbor);
  601.                                 simplyRebalance = existingDate.getDate().compareTo(central) <= 0;
  602.                             } else {
  603.                                 existingDate    = cache.get(cache.size() - 1).getData().getDate();
  604.                                 generationDate  = existingDate.getDate().shiftedBy(step * (firstNeighbor + n - cache.size()));
  605.                                 simplyRebalance = existingDate.getDate().compareTo(central) >= 0;
  606.                             }
  607.                             generateCalls.incrementAndGet();

  609.                             // generated data and add it to the slot
  610.                             try {
  611.                                 if (firstNeighbor < 0) {
  612.                                     insertAtStart(generateAndCheck(existingDate, generationDate), central);
  613.                                 } else {
  614.                                     appendAtEnd(generateAndCheck(existingDate, generationDate), central);
  615.                                 }
  616.                             } catch (TimeStampedCacheException tce) {
  617.                                 if (simplyRebalance) {
  618.                                     // we were simply trying to rebalance an unbalanced interval near slot end
  619.                                     // we failed, but the central date is already covered by the existing (unbalanced) data
  620.                                     // so we ignore the exception and stop the loop, we will continue with what we have
  621.                                     loop = false;
  622.                                 } else {
  623.                                     throw tce;
  624.                                 }
  625.                             }

  627.                         } else {
  628.                             loop = false;
  629.                         }
  630.                     }
  631.                 } finally {
  632.                     // downgrade back to a read lock
  633.                     lock.readLock().lock();
  634.                     lock.writeLock().unlock();
  635.                 }

  637.             }

  639.             if (firstNeighbor + n > cache.size()) {
  640.                 // we end up with a non-balanced neighborhood,
  641.                 // adjust the start point to fit within the cache
  642.                 firstNeighbor = cache.size() - n;
  643.             }
  644.             if (firstNeighbor < 0) {
  645.                 firstNeighbor = 0;
  646.             }
  647.             final Stream.Builder<T> builder = Stream.builder();
  648.             for (int i = 0; i < n; ++i) {
  649.                 builder.accept(cache.get(firstNeighbor + i).getData());
  650.             }

  652.             return builder.build();

  654.         }

  656.         /** Get the index of the entry corresponding to a date.
  657.          * <p>
  658.          * We own a local read lock while calling this method.
  659.          * </p>
  660.          * @param date date
  661.          * @param dateQuantum global quantum of the date
  662.          * @return index in the array such that entry[index] is before
  663.          * date and entry[index + 1] is after date (or they are at array boundaries)
  664.          */
  665.         private int entryIndex(final AbsoluteDate date, final long dateQuantum) {

  667.             // first quick guesses, assuming a recent search was close enough
  668.             final int guess = guessedIndex.get();
  669.             if (guess > 0 && guess < cache.size()) {
  670.                 if (cache.get(guess).getQuantum() <= dateQuantum) {
  671.                     if (guess + 1 < cache.size() && cache.get(guess + 1).getQuantum() > dateQuantum) {
  672.                         // good guess!
  673.                         return guess;
  674.                     } else {
  675.                         // perhaps we have simply shifted just one point forward ?
  676.                         if (guess + 2 < cache.size() && cache.get(guess + 2).getQuantum() > dateQuantum) {
  677.                             guessedIndex.set(guess + 1);
  678.                             return guess + 1;
  679.                         }
  680.                     }
  681.                 } else {
  682.                     // perhaps we have simply shifted just one point backward ?
  683.                     if (guess > 1 && cache.get(guess - 1).getQuantum() <= dateQuantum) {
  684.                         guessedIndex.set(guess - 1);
  685.                         return guess - 1;
  686.                     }
  687.                 }
  688.             }

  690.             // quick guesses have failed, we need to perform a full blown search
  691.             if (dateQuantum < getEarliestQuantum()) {
  692.                 // date if before the first entry
  693.                 return -1;
  694.             } else if (dateQuantum > getLatestQuantum()) {
  695.                 // date is after the last entry
  696.                 return cache.size();
  697.             } else {

  699.                 // try to get an existing entry
  700.                 int  iInf = 0;
  701.                 final long qInf = cache.get(iInf).getQuantum();
  702.                 int  iSup = cache.size() - 1;
  703.                 final long qSup = cache.get(iSup).getQuantum();
  704.                 while (iSup - iInf > 0) {
  705.                     // within a continuous slot, entries are expected to be roughly linear
  706.                     final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
  707.                     final int iMed    = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup));
  708.                     final Entry entry = cache.get(iMed);
  709.                     if (dateQuantum < entry.getQuantum()) {
  710.                         iSup = iMed - 1;
  711.                     } else if (dateQuantum > entry.getQuantum()) {
  712.                         iInf = iMed;
  713.                     } else {
  714.                         guessedIndex.set(iMed);
  715.                         return iMed;
  716.                     }
  717.                 }

  719.                 guessedIndex.set(iInf);
  720.                 return iInf;

  722.             }

  724.         }

  726.         /** Insert data at slot start.
  727.          * @param data data to insert
  728.          * @param requestedDate use for the error message.
  729.          */
  730.         private void insertAtStart(final List<T> data, final AbsoluteDate requestedDate) {

  732.             // insert data at start
  733.             boolean inserted = false;
  734.             final long q0 = earliestQuantum.get();
  735.             for (int i = 0; i < data.size(); ++i) {
  736.                 final long quantum = quantum(data.get(i).getDate());
  737.                 if (quantum < q0) {
  738.                     cache.add(i, new Entry(data.get(i), quantum));
  739.                     inserted = true;
  740.                 } else {
  741.                     break;
  742.                 }
  743.             }

  745.             if (!inserted) {
  746.                 final AbsoluteDate earliest = cache.get(0).getData().getDate();
  747.                 throw new TimeStampedCacheException(
  748.                         OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
  749.                         earliest, requestedDate, earliest.durationFrom(requestedDate));
  750.             }

  752.             // evict excess data at end
  753.             final AbsoluteDate t0 = cache.get(0).getData().getDate();
  754.             while (cache.size() > maxNeighborsSize &&
  755.                    cache.get(cache.size() - 1).getData().getDate().durationFrom(t0) > maxSpan) {
  756.                 cache.remove(cache.size() - 1);
  757.             }

  759.             // update boundaries
  760.             earliestQuantum.set(cache.get(0).getQuantum());
  761.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  763.         }

  765.         /** Append data at slot end.
  766.          * @param data data to append
  767.          * @param requestedDate use for error message.
  768.          */
  769.         private void appendAtEnd(final List<T> data, final AbsoluteDate requestedDate) {

  771.             // append data at end
  772.             boolean appended = false;
  773.             final long qn = latestQuantum.get();
  774.             final int  n  = cache.size();
  775.             for (int i = data.size() - 1; i >= 0; --i) {
  776.                 final long quantum = quantum(data.get(i).getDate());
  777.                 if (quantum > qn) {
  778.                     cache.add(n, new Entry(data.get(i), quantum));
  779.                     appended = true;
  780.                 } else {
  781.                     break;
  782.                 }
  783.             }

  785.             if (!appended) {
  786.                 final AbsoluteDate latest = cache.get(cache.size() - 1).getData().getDate();
  787.                 throw new TimeStampedCacheException(
  788.                         OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
  789.                         latest, requestedDate, requestedDate.durationFrom(latest));
  790.             }

  792.             // evict excess data at start
  793.             final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  794.             while (cache.size() > maxNeighborsSize &&
  795.                    tn.durationFrom(cache.get(0).getData().getDate()) > maxSpan) {
  796.                 cache.remove(0);
  797.             }

  799.             // update boundaries
  800.             earliestQuantum.set(cache.get(0).getQuantum());
  801.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  803.         }

  805.         /** Generate entries and check ordering.
  806.          * @param existingDate date of the closest already existing entry (may be null)
  807.          * @param date date that must be covered by the range of the generated array
  808.          * (guaranteed to lie between {@link #getEarliest()} and {@link #getLatest()})
  809.          * @return chronologically sorted list of generated entries
  810.          */
  811.         private List<T> generateAndCheck(final AbsoluteDate existingDate, final AbsoluteDate date) {
  812.             final List<T> entries = generator.generate(existingDate, date);
  813.             if (entries.isEmpty()) {
  814.                 throw new TimeStampedCacheException(OrekitMessages.NO_DATA_GENERATED, date);
  815.             }
  816.             for (int i = 1; i < entries.size(); ++i) {
  817.                 final AbsoluteDate previous = entries.get(i - 1).getDate();
  818.                 final AbsoluteDate current = entries.get(i).getDate();
  819.                 if (current.compareTo(previous) < 0) {
  820.                     throw new TimeStampedCacheException(OrekitMessages.NON_CHRONOLOGICALLY_SORTED_ENTRIES,
  821.                             previous, current, previous.durationFrom(current));
  822.                 }
  823.             }
  824.             return entries;
  825.         }

  827.         /** Container for entries. */
  828.         private class Entry {

  830.             /** Entry data. */
  831.             private final T data;

  833.             /** Global quantum of the entry. */
  834.             private final long quantum;

  836.             /** Simple constructor.
  837.              * @param data entry data
  838.              * @param quantum entry quantum
  839.              */
  840.             Entry(final T data, final long quantum) {
  841.                 this.quantum = quantum;
  842.                 this.data  = data;
  843.             }

  845.             /** Get the quantum.
  846.              * @return quantum
  847.              */
  848.             public long getQuantum() {
  849.                 return quantum;
  850.             }

  852.             /** Get the data.
  853.              * @return data
  854.              */
  855.             public T getData() {
  856.                 return data;
  857.             }

  859.         }
  860.     }

  862. }
Created with JaCoCo 0.8.12.202403310830