GenericTimeStampedCache.java

  1. /* Copyright 2002-2016 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.lang.reflect.Array;
  20. import java.util.ArrayList;
  21. import java.util.Arrays;
  22. import java.util.List;
  23. import java.util.concurrent.atomic.AtomicInteger;
  24. import java.util.concurrent.atomic.AtomicLong;
  25. import java.util.concurrent.atomic.AtomicReference;
  26. import java.util.concurrent.locks.ReadWriteLock;
  27. import java.util.concurrent.locks.ReentrantReadWriteLock;

  29. import org.apache.commons.math3.exception.util.LocalizedFormats;
  30. import org.apache.commons.math3.util.FastMath;
  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.     /** Class of the cached entries. */
  65.     private final Class<T> entriesClass;

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

  70.     /** Number of entries in a neighbors array. */
  71.     private final int neighborsSize;

  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 neighborsSize fixed size of the arrays to be returned by {@link
  90.      * #getNeighbors(AbsoluteDate)}, 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.      * @param entriesClass class of the cached entries
  98.      */
  99.     public GenericTimeStampedCache(final int neighborsSize, final int maxSlots, final double maxSpan,
  100.                                    final double newSlotInterval, final TimeStampedGenerator<T> generator,
  101.                                    final Class<T> entriesClass) {

  103.         // safety check
  104.         if (maxSlots < 1) {
  105.             throw new OrekitIllegalArgumentException(LocalizedFormats.NUMBER_TOO_SMALL, maxSlots, 1);
  106.         }
  107.         if (neighborsSize < 2) {
  108.             throw new OrekitIllegalArgumentException(OrekitMessages.NOT_ENOUGH_CACHED_NEIGHBORS,
  109.                                                       neighborsSize, 2);
  110.         }

  112.         this.reference         = new AtomicReference<AbsoluteDate>();
  113.         this.maxSlots          = maxSlots;
  114.         this.maxSpan           = maxSpan;
  115.         this.newSlotQuantumGap = FastMath.round(newSlotInterval / QUANTUM_STEP);
  116.         this.entriesClass      = entriesClass;
  117.         this.generator         = generator;
  118.         this.neighborsSize     = neighborsSize;
  119.         this.slots             = new ArrayList<Slot>(maxSlots);
  120.         this.getNeighborsCalls = new AtomicInteger(0);
  121.         this.generateCalls     = new AtomicInteger(0);
  122.         this.evictions         = new AtomicInteger(0);
  123.         this.lock              = new ReentrantReadWriteLock();

  125.     }

  127.     /** Get the generator.
  128.      * @return generator
  129.      */
  130.     public TimeStampedGenerator<T> getGenerator() {
  131.         return generator;
  132.     }

  134.     /** Get the maximum number of independent cached time slots.
  135.      * @return maximum number of independent cached time slots
  136.      */
  137.     public int getMaxSlots() {
  138.         return maxSlots;
  139.     }

  141.     /** Get the maximum duration span in seconds of one slot.
  142.      * @return maximum duration span in seconds of one slot
  143.      */
  144.     public double getMaxSpan() {
  145.         return maxSpan;
  146.     }

  148.     /** Get quantum gap above which a new slot is created instead of extending an existing one.
  149.      * <p>
  150.      * The quantum gap is the {@code newSlotInterval} value provided at construction
  151.      * rounded to the nearest quantum step used internally by the cache.
  152.      * </p>
  153.      * @return quantum gap in seconds
  154.      */
  155.     public double getNewSlotQuantumGap() {
  156.         return newSlotQuantumGap * QUANTUM_STEP;
  157.     }

  159.     /** Get the number of calls to the {@link #getNeighbors(AbsoluteDate)} method.
  160.      * <p>
  161.      * This number of calls is used as a reference to interpret {@link #getGenerateCalls()}.
  162.      * </p>
  163.      * @return number of calls to the {@link #getNeighbors(AbsoluteDate)} method
  164.      * @see #getGenerateCalls()
  165.      */
  166.     public int getGetNeighborsCalls() {
  167.         return getNeighborsCalls.get();
  168.     }

  170.     /** Get the number of calls to the generate method.
  171.      * <p>
  172.      * This number of calls is related to the number of cache misses and may
  173.      * be used to tune the cache configuration. Each cache miss implies at
  174.      * least one call is performed, but may require several calls if the new
  175.      * date is far offset from the existing cache, depending on the number of
  176.      * elements and step between elements in the arrays returned by the generator.
  177.      * </p>
  178.      * @return number of calls to the generate method
  179.      * @see #getGetNeighborsCalls()
  180.      */
  181.     public int getGenerateCalls() {
  182.         return generateCalls.get();
  183.     }

  185.     /** Get the number of slots evictions.
  186.      * <p>
  187.      * This number should remain small when the max number of slots is sufficient
  188.      * with respect to the number of concurrent requests to the cache. If it
  189.      * increases too much, then the cache configuration is probably bad and cache
  190.      * does not really improve things (in this case, the {@link #getGenerateCalls()
  191.      * number of calls to the generate method} will probably increase too.
  192.      * </p>
  193.      * @return number of slots evictions
  194.      */
  195.     public int getSlotsEvictions() {
  196.         return evictions.get();
  197.     }

  199.     /** Get the number of slots in use.
  200.      * @return number of slots in use
  201.      */
  202.     public int getSlots() {

  204.         lock.readLock().lock();
  205.         try {
  206.             return slots.size();
  207.         } finally {
  208.             lock.readLock().unlock();
  209.         }

  211.     }

  213.     /** Get the total number of entries cached.
  214.      * @return total number of entries cached
  215.      */
  216.     public int getEntries() {

  218.         lock.readLock().lock();
  219.         try {
  220.             int entries = 0;
  221.             for (final Slot slot : slots) {
  222.                 entries += slot.getEntries();
  223.             }
  224.             return entries;
  225.         } finally {
  226.             lock.readLock().unlock();
  227.         }

  229.     }

  231.     /** Get the earliest cached entry.
  232.      * @return earliest cached entry
  233.      * @exception IllegalStateException if the cache has no slots at all
  234.      * @see #getSlots()
  235.      */
  236.     public T getEarliest() throws IllegalStateException {

  238.         lock.readLock().lock();
  239.         try {
  240.             if (slots.isEmpty()) {
  241.                 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
  242.             }
  243.             return slots.get(0).getEarliest();
  244.         } finally {
  245.             lock.readLock().unlock();
  246.         }

  248.     }

  250.     /** Get the latest cached entry.
  251.      * @return latest cached entry
  252.      * @exception IllegalStateException if the cache has no slots at all
  253.      * @see #getSlots()
  254.      */
  255.     public T getLatest() throws IllegalStateException {

  257.         lock.readLock().lock();
  258.         try {
  259.             if (slots.isEmpty()) {
  260.                 throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
  261.             }
  262.             return slots.get(slots.size() - 1).getLatest();
  263.         } finally {
  264.             lock.readLock().unlock();
  265.         }

  267.     }

  269.     /** Get the fixed size of the arrays to be returned by {@link #getNeighbors(AbsoluteDate)}.
  270.      * @return size of the array
  271.      */
  272.     public int getNeighborsSize() {
  273.         return neighborsSize;
  274.     }

  276.     /** Get the entries surrounding a central date.
  277.      * <p>
  278.      * If the central date is well within covered range, the returned array
  279.      * will be balanced with half the points before central date and half the
  280.      * points after it (depending on n parity, of course). If the central date
  281.      * is near the generator range boundary, then the returned array will be
  282.      * unbalanced and will contain only the n earliest (or latest) generated
  283.      * (and cached) entries. A typical example of the later case is leap seconds
  284.      * cache, since the number of leap seconds cannot be arbitrarily increased.
  285.      * </p>
  286.      * @param central central date
  287.      * @return array of cached entries surrounding specified date (the size
  288.      * of the array is fixed to the one specified in the {@link
  289.      * #GenericTimeStampedCache(int, int, double, double, TimeStampedGenerator,
  290.      * Class) constructor})
  291.      * @exception TimeStampedCacheException if entries are not chronologically
  292.      * sorted or if new data cannot be generated
  293.      * @see #getEarliest()
  294.      * @see #getLatest()
  295.      */
  296.     public List<T> getNeighbors(final AbsoluteDate central) throws TimeStampedCacheException {

  298.         lock.readLock().lock();
  299.         try {
  300.             getNeighborsCalls.incrementAndGet();
  301.             final long dateQuantum = quantum(central);
  302.             return Arrays.asList(selectSlot(central, dateQuantum).getNeighbors(central, dateQuantum));
  303.         } finally {
  304.             lock.readLock().unlock();
  305.         }

  307.     }

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

  321.     /** Select a slot containing a date.
  322.      * <p>
  323.      * We own a global read lock while calling this method.
  324.      * </p>
  325.      * @param date target date
  326.      * @param dateQuantum global quantum of the date
  327.      * @return slot covering the date
  328.      * @exception TimeStampedCacheException if entries are not chronologically
  329.      * sorted or if new data cannot be generated
  330.      */
  331.     private Slot selectSlot(final AbsoluteDate date, final long dateQuantum)
  332.         throws TimeStampedCacheException {

  334.         Slot selected = null;

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

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

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

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

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

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

  372.                         // evict the selected slot
  373.                         evictions.incrementAndGet();
  374.                         slots.remove(evict);

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

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

  384.                 }

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

  393.         selected = slots.get(index);


  396.         return selected;

  398.     }

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

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

  426.         return iInf;

  428.     }

  430.     /** Time slot. */
  431.     private final class Slot {

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

  436.         /** Earliest quantum. */
  437.         private AtomicLong earliestQuantum;

  439.         /** Latest quantum. */
  440.         private AtomicLong latestQuantum;

  442.         /** Index from a previous recent call. */
  443.         private AtomicInteger guessedIndex;

  445.         /** Last access time. */
  446.         private AtomicLong lastAccess;

  448.         /** Simple constructor.
  449.          * @param date central date for initial entries to insert in the slot
  450.          * @exception TimeStampedCacheException if entries are not chronologically
  451.          * sorted or if new data cannot be generated
  452.          */
  453.         Slot(final AbsoluteDate date) throws TimeStampedCacheException {

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

  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() < neighborsSize) {
  469.                 // we need to generate more entries

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

  475.                 final T existing;
  476.                 if (entryN.getDate().durationFrom(date) <= date.durationFrom(entry0.getDate())) {
  477.                     // generate additional point at the end of the slot
  478.                     existing = entryN;
  479.                     generationDate = entryN.getDate().shiftedBy(getMeanStep() * (neighborsSize - cache.size()));
  480.                     appendAtEnd(generateAndCheck(existing, generationDate));
  481.                 } else {
  482.                     // generate additional point at the start of the slot
  483.                     existing = entry0;
  484.                     generationDate = entry0.getDate().shiftedBy(-getMeanStep() * (neighborsSize - cache.size()));
  485.                     insertAtStart(generateAndCheck(existing, generationDate));
  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 din the slot.
  524.          * @return number of entries contained din the slot
  525.          */
  526.         public int getEntries() {
  527.             return cache.size();
  528.         }

  530.         /** Get the mean step between entries.
  531.          * @return mean step between entries (or an arbitrary non-null value
  532.          * if there are fewer than 2 entries)
  533.          */
  534.         private double getMeanStep() {
  535.             if (cache.size() < 2) {
  536.                 return 1.0;
  537.             } else {
  538.                 final AbsoluteDate t0 = cache.get(0).getData().getDate();
  539.                 final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  540.                 return tn.durationFrom(t0) / (cache.size() - 1);
  541.             }
  542.         }

  544.         /** Get last access time of slot.
  545.          * @return last known access time
  546.          */
  547.         public long getLastAccess() {
  548.             return lastAccess.get();
  549.         }

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

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

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

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

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

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

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

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

  636.             }

  638.             @SuppressWarnings("unchecked")
  639.             final T[] array = (T[]) Array.newInstance(entriesClass, neighborsSize);
  640.             if (firstNeighbor + neighborsSize > cache.size()) {
  641.                 // we end up with a non-balanced neighborhood,
  642.                 // adjust the start point to fit within the cache
  643.                 firstNeighbor = cache.size() - neighborsSize;
  644.             }
  645.             if (firstNeighbor < 0) {
  646.                 firstNeighbor = 0;
  647.             }
  648.             for (int i = 0; i < neighborsSize; ++i) {
  649.                 array[i] = cache.get(firstNeighbor + i).getData();
  650.             }

  652.             return array;

  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.          * @exception TimeStampedCacheException if new data cannot be generated
  729.          */
  730.         private void insertAtStart(final List<T> data) throws TimeStampedCacheException {

  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.                 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
  747.                                                               cache.get(0).getData().getDate());
  748.             }

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

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

  761.         }

  763.         /** Append data at slot end.
  764.          * @param data data to append
  765.          * @exception TimeStampedCacheException if new data cannot be generated
  766.          */
  767.         private void appendAtEnd(final List<T> data) throws TimeStampedCacheException {

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

  783.             if (!appended) {
  784.                 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
  785.                                                               cache.get(cache.size() - 1).getData().getDate());
  786.             }

  788.             // evict excess data at start
  789.             final AbsoluteDate tn = cache.get(cache.size() - 1).getData().getDate();
  790.             while (cache.size() > neighborsSize &&
  791.                    tn.durationFrom(cache.get(0).getData().getDate()) > maxSpan) {
  792.                 cache.remove(0);
  793.             }

  795.             // update boundaries
  796.             earliestQuantum.set(cache.get(0).getQuantum());
  797.             latestQuantum.set(cache.get(cache.size() - 1).getQuantum());

  799.         }

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

  825.         /** Container for entries. */
  826.         private class Entry {

  828.             /** Entry data. */
  829.             private final T data;

  831.             /** Global quantum of the entry. */
  832.             private final long quantum;

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

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

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

  857.         }
  858.     }

  860. }
Created with JaCoCo 0.7.4.201502262128