GenericTimeStampedCache.java

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

  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.      * @exception TimeStampedCacheException if entries are not chronologically
  284.      * sorted or if new data cannot be generated
  285.      * @see #getEarliest()
  286.      * @see #getLatest()
  287.      */
  288.     public Stream<T> getNeighbors(final AbsoluteDate central) throws TimeStampedCacheException {

  290.         lock.readLock().lock();
  291.         try {
  292.             getNeighborsCalls.incrementAndGet();
  293.             final long dateQuantum = quantum(central);
  294.             return selectSlot(central, dateQuantum).getNeighbors(central, dateQuantum);
  295.         } finally {
  296.             lock.readLock().unlock();
  297.         }

  299.     }

  301.     /** Convert a date to a rough global quantum.
  302.      * <p>
  303.      * We own a global read lock while calling this method.
  304.      * </p>
  305.      * @param date date to convert
  306.      * @return quantum corresponding to the date
  307.      */
  308.     private long quantum(final AbsoluteDate date) {
  309.         reference.compareAndSet(null, date);
  310.         return FastMath.round(date.durationFrom(reference.get()) / QUANTUM_STEP);
  311.     }

  313.     /** Select a slot containing a date.
  314.      * <p>
  315.      * We own a global read lock while calling this method.
  316.      * </p>
  317.      * @param date target date
  318.      * @param dateQuantum global quantum of the date
  319.      * @return slot covering the date
  320.      * @exception TimeStampedCacheException if entries are not chronologically
  321.      * sorted or if new data cannot be generated
  322.      */
  323.     private Slot selectSlot(final AbsoluteDate date, final long dateQuantum)
  324.         throws TimeStampedCacheException {

  326.         Slot selected = null;

  328.         int index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
  329.         if (slots.isEmpty() ||
  330.             slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
  331.             slots.get(index).getLatestQuantum()   < dateQuantum - newSlotQuantumGap) {
  332.             // no existing slot is suitable

  334.             // upgrade the read lock to a write lock so we can change the list of available slots
  335.             lock.readLock().unlock();
  336.             lock.writeLock().lock();

  338.             try {
  339.                 // check slots again as another thread may have changed
  340.                 // the list while we were waiting for the write lock
  341.                 index = slots.isEmpty() ? 0 : slotIndex(dateQuantum);
  342.                 if (slots.isEmpty() ||
  343.                     slots.get(index).getEarliestQuantum() > dateQuantum + newSlotQuantumGap ||
  344.                     slots.get(index).getLatestQuantum()   < dateQuantum - newSlotQuantumGap) {

  346.                     // we really need to create a new slot in the current thread
  347.                     // (no other threads have created it while we were waiting for the lock)
  348.                     if ((!slots.isEmpty()) &&
  349.                         slots.get(index).getLatestQuantum() < dateQuantum - newSlotQuantumGap) {
  350.                         ++index;
  351.                     }

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

  356.                         // select the oldest accessed slot for eviction
  357.                         int evict = 0;
  358.                         for (int i = 0; i < slots.size(); ++i) {
  359.                             if (slots.get(i).getLastAccess() < slots.get(evict).getLastAccess()) {
  360.                                 evict = i;
  361.                             }
  362.                         }

  364.                         // evict the selected slot
  365.                         evictions.incrementAndGet();
  366.                         slots.remove(evict);

  368.                         if (evict < index) {
  369.                             // adjust index of created slot as it was shifted by the eviction
  370.                             index--;
  371.                         }
  372.                     }

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

  376.                 }

  378.             } finally {
  379.                 // downgrade back to a read lock
  380.                 lock.readLock().lock();
  381.                 lock.writeLock().unlock();
  382.             }
  383.         }

  385.         selected = slots.get(index);


  388.         return selected;

  390.     }

  392.     /** Get the index of the slot in which a date could be cached.
  393.      * <p>
  394.      * We own a global read lock while calling this method.
  395.      * </p>
  396.      * @param dateQuantum quantum of the date to search for
  397.      * @return the slot in which the date could be cached
  398.      */
  399.     private int slotIndex(final long dateQuantum) {

  401.         int  iInf = 0;
  402.         final long qInf = slots.get(iInf).getEarliestQuantum();
  403.         int  iSup = slots.size() - 1;
  404.         final long qSup = slots.get(iSup).getLatestQuantum();
  405.         while (iSup - iInf > 0) {
  406.             final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
  407.             final int iMed    = FastMath.max(iInf, FastMath.min(iInterp, iSup));
  408.             final Slot slot   = slots.get(iMed);
  409.             if (dateQuantum < slot.getEarliestQuantum()) {
  410.                 iSup = iMed - 1;
  411.             } else if (dateQuantum > slot.getLatestQuantum()) {
  412.                 iInf = FastMath.min(iSup, iMed + 1);
  413.             } else {
  414.                 return iMed;
  415.             }
  416.         }

  418.         return iInf;

  420.     }

  422.     /** Time slot. */
  423.     private final class Slot {

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

  428.         /** Earliest quantum. */
  429.         private AtomicLong earliestQuantum;

  431.         /** Latest quantum. */
  432.         private AtomicLong latestQuantum;

  434.         /** Index from a previous recent call. */
  435.         private AtomicInteger guessedIndex;

  437.         /** Last access time. */
  438.         private AtomicLong lastAccess;

  440.         /** Simple constructor.
  441.          * @param date central date for initial entries to insert in the slot
  442.          * @exception TimeStampedCacheException if entries are not chronologically
  443.          * sorted or if new data cannot be generated
  444.          */
  445.         Slot(final AbsoluteDate date) throws TimeStampedCacheException {

  447.             // allocate cache
  448.             this.cache = new ArrayList<Entry>();

  450.             // set up first entries
  451.             AbsoluteDate generationDate = date;

  453.             generateCalls.incrementAndGet();
  454.             for (final T entry : generateAndCheck(null, generationDate)) {
  455.                 cache.add(new Entry(entry, quantum(entry.getDate())));
  456.             }
  457.             earliestQuantum = new AtomicLong(cache.get(0).getQuantum());
  458.             latestQuantum   = new AtomicLong(cache.get(cache.size() - 1).getQuantum());

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

  463.                 final AbsoluteDate entry0 = cache.get(0).getData().getDate();
  464.                 final AbsoluteDate entryN = cache.get(cache.size() - 1).getData().getDate();
  465.                 generateCalls.incrementAndGet();

  467.                 final AbsoluteDate existingDate;
  468.                 if (entryN.getDate().durationFrom(date) <= date.durationFrom(entry0.getDate())) {
  469.                     // generate additional point at the end of the slot
  470.                     existingDate = entryN;
  471.                     generationDate = entryN.getDate().shiftedBy(getMeanStep() * (neighborsSize - cache.size()));
  472.                     appendAtEnd(generateAndCheck(existingDate, generationDate));
  473.                 } else {
  474.                     // generate additional point at the start of the slot
  475.                     existingDate = entry0;
  476.                     generationDate = entry0.getDate().shiftedBy(-getMeanStep() * (neighborsSize - cache.size()));
  477.                     insertAtStart(generateAndCheck(existingDate, generationDate));
  478.                 }

  480.             }

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

  485.         }

  487.         /** Get the earliest entry contained in the slot.
  488.          * @return earliest entry contained in the slot
  489.          */
  490.         public T getEarliest() {
  491.             return cache.get(0).getData();
  492.         }

  494.         /** Get the quantum of the earliest date contained in the slot.
  495.          * @return quantum of the earliest date contained in the slot
  496.          */
  497.         public long getEarliestQuantum() {
  498.             return earliestQuantum.get();
  499.         }

  501.         /** Get the latest entry contained in the slot.
  502.          * @return latest entry contained in the slot
  503.          */
  504.         public T getLatest() {
  505.             return cache.get(cache.size() - 1).getData();
  506.         }

  508.         /** Get the quantum of the latest date contained in the slot.
  509.          * @return quantum of the latest date contained in the slot
  510.          */
  511.         public long getLatestQuantum() {
  512.             return latestQuantum.get();
  513.         }

  515.         /** Get the number of entries contained din the slot.
  516.          * @return number of entries contained din the slot
  517.          */
  518.         public int getEntries() {
  519.             return cache.size();
  520.         }

  522.         /** Get the mean step between entries.
  523.          * @return mean step between entries (or an arbitrary non-null value
  524.          * if there are fewer than 2 entries)
  525.          */
  526.         private double getMeanStep() {
  527.             if (cache.size() < 2) {
  528.                 return 1.0;
  529.             } else {
  530.                 final AbsoluteDate t0 = cache.get(0).getData().getDate();
  531.                 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  532.                 return tn.durationFrom(t0) / (cache.size() - 1);
  533.             }
  534.         }

  536.         /** Get last access time of slot.
  537.          * @return last known access time
  538.          */
  539.         public long getLastAccess() {
  540.             return lastAccess.get();
  541.         }

  543.         /** Get the entries surrounding a central date.
  544.          * <p>
  545.          * If the central date is well within covered slot, the returned array
  546.          * will be balanced with half the points before central date and half the
  547.          * points after it (depending on n parity, of course). If the central date
  548.          * is near slot boundary and the underlying {@link TimeStampedGenerator
  549.          * generator} cannot extend it (i.e. it returns null), then the returned
  550.          * array will be unbalanced and will contain only the n earliest (or latest)
  551.          * cached entries. A typical example of the later case is leap seconds cache,
  552.          * since the number of leap seconds cannot be arbitrarily increased.
  553.          * </p>
  554.          * @param central central date
  555.          * @param dateQuantum global quantum of the date
  556.          * @return a new array containing date neighbors
  557.          * @exception TimeStampedCacheException if entries are not chronologically
  558.          * sorted or if new data cannot be generated
  559.          * @see #getBefore(AbsoluteDate)
  560.          * @see #getAfter(AbsoluteDate)
  561.          */
  562.         public Stream<T> getNeighbors(final AbsoluteDate central, final long dateQuantum)
  563.             throws TimeStampedCacheException {

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

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

  571.                 // upgrade the read lock to a write lock so we can change the list of available slots
  572.                 lock.readLock().unlock();
  573.                 lock.writeLock().lock();

  575.                 try {
  576.                     // check entries again as another thread may have changed
  577.                     // the list while we were waiting for the write lock
  578.                     boolean loop = true;
  579.                     while (loop) {
  580.                         index         = entryIndex(central, dateQuantum);
  581.                         firstNeighbor = index - (neighborsSize - 1) / 2;
  582.                         if (firstNeighbor < 0 || firstNeighbor + neighborsSize > cache.size()) {

  584.                             // estimate which data we need to be generated
  585.                             final double step = getMeanStep();
  586.                             final AbsoluteDate existingDate;
  587.                             final AbsoluteDate generationDate;
  588.                             final boolean simplyRebalance;
  589.                             if (firstNeighbor < 0) {
  590.                                 existingDate    = cache.get(0).getData().getDate();
  591.                                 generationDate  = existingDate.getDate().shiftedBy(step * firstNeighbor);
  592.                                 simplyRebalance = existingDate.getDate().compareTo(central) <= 0;
  593.                             } else {
  594.                                 existingDate    = cache.get(cache.size() - 1).getData().getDate();
  595.                                 generationDate  = existingDate.getDate().shiftedBy(step * (firstNeighbor + neighborsSize - cache.size()));
  596.                                 simplyRebalance = existingDate.getDate().compareTo(central) >= 0;
  597.                             }
  598.                             generateCalls.incrementAndGet();

  600.                             // generated data and add it to the slot
  601.                             try {
  602.                                 if (firstNeighbor < 0) {
  603.                                     insertAtStart(generateAndCheck(existingDate, generationDate));
  604.                                 } else {
  605.                                     appendAtEnd(generateAndCheck(existingDate, generationDate));
  606.                                 }
  607.                             } catch (TimeStampedCacheException tce) {
  608.                                 if (simplyRebalance) {
  609.                                     // we were simply trying to rebalance an unbalanced interval near slot end
  610.                                     // we failed, but the central date is already covered by the existing (unbalanced) data
  611.                                     // so we ignore the exception and stop the loop, we will continue with what we have
  612.                                     loop = false;
  613.                                 } else {
  614.                                     throw tce;
  615.                                 }
  616.                             }

  618.                         } else {
  619.                             loop = false;
  620.                         }
  621.                     }
  622.                 } finally {
  623.                     // downgrade back to a read lock
  624.                     lock.readLock().lock();
  625.                     lock.writeLock().unlock();
  626.                 }

  628.             }

  630.             if (firstNeighbor + neighborsSize > cache.size()) {
  631.                 // we end up with a non-balanced neighborhood,
  632.                 // adjust the start point to fit within the cache
  633.                 firstNeighbor = cache.size() - neighborsSize;
  634.             }
  635.             if (firstNeighbor < 0) {
  636.                 firstNeighbor = 0;
  637.             }
  638.             final Stream.Builder<T> builder = Stream.builder();
  639.             for (int i = 0; i < neighborsSize; ++i) {
  640.                 builder.accept(cache.get(firstNeighbor + i).getData());
  641.             }

  643.             return builder.build();

  645.         }

  647.         /** Get the index of the entry corresponding to a date.
  648.          * <p>
  649.          * We own a local read lock while calling this method.
  650.          * </p>
  651.          * @param date date
  652.          * @param dateQuantum global quantum of the date
  653.          * @return index in the array such that entry[index] is before
  654.          * date and entry[index + 1] is after date (or they are at array boundaries)
  655.          */
  656.         private int entryIndex(final AbsoluteDate date, final long dateQuantum) {

  658.             // first quick guesses, assuming a recent search was close enough
  659.             final int guess = guessedIndex.get();
  660.             if (guess > 0 && guess < cache.size()) {
  661.                 if (cache.get(guess).getQuantum() <= dateQuantum) {
  662.                     if (guess + 1 < cache.size() && cache.get(guess + 1).getQuantum() > dateQuantum) {
  663.                         // good guess!
  664.                         return guess;
  665.                     } else {
  666.                         // perhaps we have simply shifted just one point forward ?
  667.                         if (guess + 2 < cache.size() && cache.get(guess + 2).getQuantum() > dateQuantum) {
  668.                             guessedIndex.set(guess + 1);
  669.                             return guess + 1;
  670.                         }
  671.                     }
  672.                 } else {
  673.                     // perhaps we have simply shifted just one point backward ?
  674.                     if (guess > 1 && cache.get(guess - 1).getQuantum() <= dateQuantum) {
  675.                         guessedIndex.set(guess - 1);
  676.                         return guess - 1;
  677.                     }
  678.                 }
  679.             }

  681.             // quick guesses have failed, we need to perform a full blown search
  682.             if (dateQuantum < getEarliestQuantum()) {
  683.                 // date if before the first entry
  684.                 return -1;
  685.             } else if (dateQuantum > getLatestQuantum()) {
  686.                 // date is after the last entry
  687.                 return cache.size();
  688.             } else {

  690.                 // try to get an existing entry
  691.                 int  iInf = 0;
  692.                 final long qInf = cache.get(iInf).getQuantum();
  693.                 int  iSup = cache.size() - 1;
  694.                 final long qSup = cache.get(iSup).getQuantum();
  695.                 while (iSup - iInf > 0) {
  696.                     // within a continuous slot, entries are expected to be roughly linear
  697.                     final int iInterp = (int) ((iInf * (qSup - dateQuantum) + iSup * (dateQuantum - qInf)) / (qSup - qInf));
  698.                     final int iMed    = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup));
  699.                     final Entry entry = cache.get(iMed);
  700.                     if (dateQuantum < entry.getQuantum()) {
  701.                         iSup = iMed - 1;
  702.                     } else if (dateQuantum > entry.getQuantum()) {
  703.                         iInf = iMed;
  704.                     } else {
  705.                         guessedIndex.set(iMed);
  706.                         return iMed;
  707.                     }
  708.                 }

  710.                 guessedIndex.set(iInf);
  711.                 return iInf;

  713.             }

  715.         }

  717.         /** Insert data at slot start.
  718.          * @param data data to insert
  719.          * @exception TimeStampedCacheException if new data cannot be generated
  720.          */
  721.         private void insertAtStart(final List<T> data) throws TimeStampedCacheException {

  723.             // insert data at start
  724.             boolean inserted = false;
  725.             final long q0 = earliestQuantum.get();
  726.             for (int i = 0; i < data.size(); ++i) {
  727.                 final long quantum = quantum(data.get(i).getDate());
  728.                 if (quantum < q0) {
  729.                     cache.add(i, new Entry(data.get(i), quantum));
  730.                     inserted = true;
  731.                 } else {
  732.                     break;
  733.                 }
  734.             }

  736.             if (!inserted) {
  737.                 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
  738.                                                               cache.get(0).getData().getDate());
  739.             }

  741.             // evict excess data at end
  742.             final AbsoluteDate t0 = cache.get(0).getData().getDate();
  743.             while (cache.size() > neighborsSize &&
  744.                    cache.get(cache.size() - 1).getData().getDate().durationFrom(t0) > maxSpan) {
  745.                 cache.remove(cache.size() - 1);
  746.             }

  748.             // update boundaries
  749.             earliestQuantum.set(cache.get(0).getQuantum());
  750.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  752.         }

  754.         /** Append data at slot end.
  755.          * @param data data to append
  756.          * @exception TimeStampedCacheException if new data cannot be generated
  757.          */
  758.         private void appendAtEnd(final List<T> data) throws TimeStampedCacheException {

  760.             // append data at end
  761.             boolean appended = false;
  762.             final long qn = latestQuantum.get();
  763.             final int  n  = cache.size();
  764.             for (int i = data.size() - 1; i >= 0; --i) {
  765.                 final long quantum = quantum(data.get(i).getDate());
  766.                 if (quantum > qn) {
  767.                     cache.add(n, new Entry(data.get(i), quantum));
  768.                     appended = true;
  769.                 } else {
  770.                     break;
  771.                 }
  772.             }

  774.             if (!appended) {
  775.                 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
  776.                                                     cache.get(cache.size() - 1).getData().getDate());
  777.             }

  779.             // evict excess data at start
  780.             final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  781.             while (cache.size() > neighborsSize &&
  782.                    tn.durationFrom(cache.get(0).getData().getDate()) > maxSpan) {
  783.                 cache.remove(0);
  784.             }

  786.             // update boundaries
  787.             earliestQuantum.set(cache.get(0).getQuantum());
  788.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  790.         }

  792.         /** Generate entries and check ordering.
  793.          * @param existingDate date of the closest already existing entry (may be null)
  794.          * @param date date that must be covered by the range of the generated array
  795.          * (guaranteed to lie between {@link #getEarliest()} and {@link #getLatest()})
  796.          * @return chronologically sorted list of generated entries
  797.          * @exception TimeStampedCacheException if if entries are not chronologically
  798.          * sorted or if new data cannot be generated
  799.          */
  800.         private List<T> generateAndCheck(final AbsoluteDate existingDate, final AbsoluteDate date)
  801.             throws TimeStampedCacheException {
  802.             final List<T> entries = generator.generate(existingDate, date);
  803.             if (entries.isEmpty()) {
  804.                 throw new TimeStampedCacheException(OrekitMessages.NO_DATA_GENERATED, date);
  805.             }
  806.             for (int i = 1; i < entries.size(); ++i) {
  807.                 if (entries.get(i).getDate().compareTo(entries.get(i - 1).getDate()) < 0) {
  808.                     throw new TimeStampedCacheException(OrekitMessages.NON_CHRONOLOGICALLY_SORTED_ENTRIES,
  809.                                                                   entries.get(i - 1).getDate(),
  810.                                                                   entries.get(i).getDate());
  811.                 }
  812.             }
  813.             return entries;
  814.         }

  816.         /** Container for entries. */
  817.         private class Entry {

  819.             /** Entry data. */
  820.             private final T data;

  822.             /** Global quantum of the entry. */
  823.             private final long quantum;

  825.             /** Simple constructor.
  826.              * @param data entry data
  827.              * @param quantum entry quantum
  828.              */
  829.             Entry(final T data, final long quantum) {
  830.                 this.quantum = quantum;
  831.                 this.data  = data;
  832.             }

  834.             /** Get the quantum.
  835.              * @return quantum
  836.              */
  837.             public long getQuantum() {
  838.                 return quantum;
  839.             }

  841.             /** Get the data.
  842.              * @return data
  843.              */
  844.             public T getData() {
  845.                 return data;
  846.             }

  848.         }
  849.     }

  851. }
Created with JaCoCo 0.7.9.201702052155