GenericTimeStampedCache.java

  1. /* Copyright 2002-2022 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.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;

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

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

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

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

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

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

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

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

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

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

  66.     /** Number of entries in a neighbors array. */
  67.     private final int neighborsSize;

  69.     /** Independent time slots cached. */
  70.     private final List<Slot> slots;

  72.     /** Number of calls to the getNeighbors method. */
  73.     private final AtomicInteger getNeighborsCalls;

  75.     /** Number of calls to the generate method. */
  76.     private final AtomicInteger generateCalls;

  78.     /** Number of evictions. */
  79.     private final AtomicInteger evictions;

  81.     /** Global lock. */
  82.     private final ReadWriteLock lock;

  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) {

  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.         }

  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();

  118.     }

  120.     /** Get the generator.
  121.      * @return generator
  122.      */
  123.     public TimeStampedGenerator<T> getGenerator() {
  124.         return generator;
  125.     }

  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.     }

  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.     }

  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.     }

  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.     }

  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.     }

  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.     }

  192.     /** Get the number of slots in use.
  193.      * @return number of slots in use
  194.      */
  195.     public int getSlots() {

  197.         lock.readLock().lock();
  198.         try {
  199.             return slots.size();
  200.         } finally {
  201.             lock.readLock().unlock();
  202.         }

  204.     }

  206.     /** Get the total number of entries cached.
  207.      * @return total number of entries cached
  208.      */
  209.     public int getEntries() {

  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.         }

  222.     }

  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 {

  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.         }

  241.     }

  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 {

  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.         }

  260.     }

  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.     }

  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) {

  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.         }

  297.     }

  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.     }

  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) {

  321.         Slot selected = null;

  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

  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();

  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) {

  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.                     }

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

  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.                         }

  359.                         // evict the selected slot
  360.                         evictions.incrementAndGet();
  361.                         slots.remove(evict);

  363.                         if (evict < index) {
  364.                             // adjust index of created slot as it was shifted by the eviction
  365.                             index--;
  366.                         }
  367.                     }

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

  371.                 }

  373.             } finally {
  374.                 // downgrade back to a read lock
  375.                 lock.readLock().lock();
  376.                 lock.writeLock().unlock();
  377.             }
  378.         }

  380.         selected = slots.get(index);


  383.         return selected;

  385.     }

  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) {

  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.         }

  413.         return iInf;

  415.     }

  417.     /** Time slot. */
  418.     private final class Slot {

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

  423.         /** Earliest quantum. */
  424.         private AtomicLong earliestQuantum;

  426.         /** Latest quantum. */
  427.         private AtomicLong latestQuantum;

  429.         /** Index from a previous recent call. */
  430.         private AtomicInteger guessedIndex;

  432.         /** Last access time. */
  433.         private AtomicLong lastAccess;

  435.         /** Simple constructor.
  436.          * @param date central date for initial entries to insert in the slot
  437.          */
  438.         Slot(final AbsoluteDate date) {

  440.             // allocate cache
  441.             this.cache = new ArrayList<Entry>();

  443.             // set up first entries
  444.             AbsoluteDate generationDate = date;

  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());

  453.             while (cache.size() < neighborsSize) {
  454.                 // we need to generate more entries

  456.                 final AbsoluteDate entry0 = cache.get(0).getData().getDate();
  457.                 final AbsoluteDate entryN = cache.get(cache.size() - 1).getData().getDate();
  458.                 generateCalls.incrementAndGet();

  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.                 }

  473.             }

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

  478.         }

  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.         }

  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.         }

  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.         }

  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.         }

  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.         }

  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.         }

  529.         /** Get last access time of slot.
  530.          * @return last known access time
  531.          */
  532.         public long getLastAccess() {
  533.             return lastAccess.get();
  534.         }

  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) {

  555.             int index         = entryIndex(central, dateQuantum);
  556.             int firstNeighbor = index - (neighborsSize - 1) / 2;

  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

  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();

  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()) {

  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();

  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.                             }

  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.                 }

  618.             }

  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.             }

  633.             return builder.build();

  635.         }

  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) {

  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.             }

  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 {

  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.                 }

  700.                 guessedIndex.set(iInf);
  701.                 return iInf;

  703.             }

  705.         }

  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) {

  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.             }

  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.             }

  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.             }

  740.             // update boundaries
  741.             earliestQuantum.set(cache.get(0).getQuantum());
  742.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  744.         }

  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) {

  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.             }

  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.             }

  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.             }

  780.             // update boundaries
  781.             earliestQuantum.set(cache.get(0).getQuantum());
  782.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  784.         }

  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.         }

  808.         /** Container for entries. */
  809.         private class Entry {

  811.             /** Entry data. */
  812.             private final T data;

  814.             /** Global quantum of the entry. */
  815.             private final long quantum;

  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.             }

  826.             /** Get the quantum.
  827.              * @return quantum
  828.              */
  829.             public long getQuantum() {
  830.                 return quantum;
  831.             }

  833.             /** Get the data.
  834.              * @return data
  835.              */
  836.             public T getData() {
  837.                 return data;
  838.             }

  840.         }
  841.     }

  843. }
Created with JaCoCo 0.8.7.202105040129