GenericTimeStampedCache.java

  1. /* Copyright 2002-2013 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.OrekitException;
  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.     /** Class of the cached entries. */
  64.     private final Class<T> entriesClass;

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

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

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

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

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

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

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

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

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

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

  124.     }

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

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

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

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

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

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

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

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

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

  210.     }

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

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

  228.     }

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

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

  247.     }

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

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

  266.     }

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

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

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

  306.     }

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

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

  333.         Slot selected = null;

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

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

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

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

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

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

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

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

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

  383.                 }

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

  392.         selected = slots.get(index);


  395.         return selected;

  397.     }

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

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

  425.         return iInf;

  427.     }

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

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

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

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

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

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

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

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

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

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

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

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

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

  487.             }

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

  492.         }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  635.             }

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

  651.             return array;

  653.         }

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

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

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

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

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

  721.             }

  723.         }

  725.         /** Insert data at slot start.
  726.          * @param data data to insert
  727.          * @exception TimeStampedCacheException if new data cannot be generated
  728.          */
  729.         private void insertAtStart(final List<T> data) throws TimeStampedCacheException {

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

  744.             if (!inserted) {
  745.                 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
  746.                                                               cache.get(0).getData().getDate());
  747.             }

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

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

  760.         }

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

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

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

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

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

  798.         }

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

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

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

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

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

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

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

  856.         }
  857.     }

  859. }
Created with JaCoCo 0.6.3.201306030806