ImmutableTimeStampedCache.java

/* Contributed in the public domain.
 * Licensed to CS GROUP (CS) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * CS licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.orekit.utils;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;

import org.hipparchus.exception.LocalizedCoreFormats;
import org.hipparchus.util.FastMath;
import org.orekit.errors.OrekitException;
import org.orekit.errors.OrekitIllegalArgumentException;
import org.orekit.errors.OrekitIllegalStateException;
import org.orekit.errors.OrekitMessages;
import org.orekit.errors.TimeStampedCacheException;
import org.orekit.time.AbsoluteDate;
import org.orekit.time.ChronologicalComparator;
import org.orekit.time.TimeStamped;

/**
 * A cache of {@link TimeStamped} data that provides concurrency through
 * immutability. This strategy is suitable when all of the cached data is stored
 * in memory. (For example, {@link org.orekit.time.UTCScale UTCScale}) This
 * class then provides convenient methods for accessing the data.
 *
 * @author Evan Ward
 * @param <T>  the type of data
 */
public class ImmutableTimeStampedCache<T extends TimeStamped>
    implements TimeStampedCache<T> {

    /**
     * An empty immutable cache that always throws an exception on attempted
     * access.
     */
    @SuppressWarnings("rawtypes")
    private static final ImmutableTimeStampedCache EMPTY_CACHE =
        new EmptyTimeStampedCache<TimeStamped>();

    /**
     * the cached data. Be careful not to modify it after the constructor, or
     * return a reference that allows mutating this list.
     */
    private final List<T> data;

    /**
     * the maximum size list to return from {@link #getNeighbors(AbsoluteDate, int)}.
     * @since 12.0
     */
    private final int maxNeighborsSize;

    /** Earliest date.
     * @since 12.0
     */
    private final AbsoluteDate earliestDate;

    /** Latest date.
     * @since 12.0
     */
    private final AbsoluteDate latestDate;

    /**
     * Create a new cache with the given neighbors size and data.
     *
     * @param maxNeighborsSize the maximum size of the list returned from
     *        {@link #getNeighbors(AbsoluteDate, int)}. Must be less than or equal to
     *        {@code data.size()}.
     * @param data the backing data for this cache. The list will be copied to
     *        ensure immutability. To guarantee immutability the entries in
     *        {@code data} must be immutable themselves. There must be more data
     *        than {@code maxNeighborsSize}.
     * @throws IllegalArgumentException if {@code neightborsSize > data.size()}
     *         or if {@code neighborsSize} is negative
     */
    public ImmutableTimeStampedCache(final int maxNeighborsSize,
                                     final Collection<? extends T> data) {
        // parameter check
        if (maxNeighborsSize > data.size()) {
            throw new OrekitIllegalArgumentException(OrekitMessages.NOT_ENOUGH_CACHED_NEIGHBORS,
                                                     data.size(), maxNeighborsSize);
        }
        if (maxNeighborsSize < 1) {
            throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL,
                                                     maxNeighborsSize, 0);
        }

        // assign instance variables
        this.maxNeighborsSize = maxNeighborsSize;
        // sort and copy data first
        this.data = new ArrayList<>(data);
        Collections.sort(this.data, new ChronologicalComparator());

        this.earliestDate = this.data.get(0).getDate();
        this.latestDate   = this.data.get(this.data.size() - 1).getDate();

    }

    /**
     * private constructor for {@link #EMPTY_CACHE}.
     */
    private ImmutableTimeStampedCache() {
        this.data             = null;
        this.maxNeighborsSize = 0;
        this.earliestDate     = AbsoluteDate.ARBITRARY_EPOCH;
        this.latestDate       = AbsoluteDate.ARBITRARY_EPOCH;
    }

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

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

        // find central index
        final int i = findIndex(central);

        // check index in in the range of the data
        if (i < 0) {
            final AbsoluteDate earliest = this.getEarliest().getDate();
            throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
                    earliest, central, earliest.durationFrom(central));
        } else if (i >= this.data.size()) {
            final AbsoluteDate latest = this.getLatest().getDate();
            throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
                    latest, central, central.durationFrom(latest));
        }

        // force unbalanced range if necessary
        int start = FastMath.max(0, i - (n - 1) / 2);
        final int end = FastMath.min(this.data.size(), start + n);
        start = end - n;

        // return list without copying
        return this.data.subList(start, end).stream();
    }

    /**
     * Find the index, i, to {@link #data} such that {@code data[i] <= t} and
     * {@code data[i+1] > t} if {@code data[i+1]} exists.
     *
     * @param t the time
     * @return the index of the data at or just before {@code t}, {@code -1} if
     *         {@code t} is before the first entry, or {@code data.size()} if
     *         {@code t} is after the last entry.
     */
    private int findIndex(final AbsoluteDate t) {

        // left bracket of search algorithm
        int    iInf  = 0;
        double dtInf = t.durationFrom(earliestDate);
        if (dtInf < 0) {
            // before first entry
            return -1;
        }

        // right bracket of search algorithm
        int    iSup  = data.size() - 1;
        double dtSup = t.durationFrom(latestDate);
        if (dtSup > 0) {
            // after last entry
            return data.size();
        }

        // search entries, using linear interpolation
        // this should take only 2 iterations for near linear entries (most frequent use case)
        // regardless of the number of entries
        // this is much faster than binary search for large number of entries
        while (iSup - iInf > 1) {
            final int    iInterp = (int) FastMath.rint((iInf * dtSup - iSup * dtInf) / (dtSup - dtInf));
            final int    iMed    = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup - 1));
            final double dtMed   = t.durationFrom(data.get(iMed).getDate());
            if (dtMed < 0) {
                iSup  = iMed;
                dtSup = dtMed;
            } else {
                iInf  = iMed;
                dtInf = dtMed;
            }
        }

        // at this point data[iInf] <= t <= data[iSup], but the javadoc for this method
        // says the upper bound is exclusive, so check for equality to make a half open
        // interval.
        if (dtSup == 0.0) {
            return iSup;
        }
        return iInf;
    }

    /** {@inheritDoc} */
    public int getMaxNeighborsSize() {
        return maxNeighborsSize;
    }

    /** {@inheritDoc} */
    public T getEarliest() {
        return this.data.get(0);
    }

    /** {@inheritDoc} */
    public T getLatest() {
        return this.data.get(this.data.size() - 1);
    }

    /**
     * Get all of the data in this cache.
     *
     * @return a sorted collection of all data passed in the
     *         {@link #ImmutableTimeStampedCache(int, Collection) constructor}.
     */
    public List<T> getAll() {
        return Collections.unmodifiableList(this.data);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return "Immutable cache with " + this.data.size() + " entries";
    }

    /**
     * An empty immutable cache that always throws an exception on attempted
     * access.
     */
    private static class EmptyTimeStampedCache<T extends TimeStamped> extends ImmutableTimeStampedCache<T> {

        /** {@inheritDoc} */
        @Override
        public Stream<T> getNeighbors(final AbsoluteDate central) {
            throw new TimeStampedCacheException(OrekitMessages.NO_CACHED_ENTRIES);
        }

        /** {@inheritDoc} */
        @Override
        public int getMaxNeighborsSize() {
            return 0;
        }

        /** {@inheritDoc} */
        @Override
        public T getEarliest() {
            throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
        }

        /** {@inheritDoc} */
        @Override
        public T getLatest() {
            throw new OrekitIllegalStateException(OrekitMessages.NO_CACHED_ENTRIES);
        }

        /** {@inheritDoc} */
        @Override
        public List<T> getAll() {
            return Collections.emptyList();
        }

        /** {@inheritDoc} */
        @Override
        public String toString() {
            return "Empty immutable cache";
        }

    }

    /**
     * Get an empty immutable cache, cast to the correct type.
     * @param <TS>  the type of data
     * @return an empty {@link ImmutableTimeStampedCache}.
     */
    @SuppressWarnings("unchecked")
    public static final <TS extends TimeStamped> ImmutableTimeStampedCache<TS> emptyCache() {
        return (ImmutableTimeStampedCache<TS>) EMPTY_CACHE;
    }

}