FieldSortedListTrimmer

/* Copyright 2002-2025 CS GROUP
 * 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 org.hipparchus.CalculusFieldElement;
import org.hipparchus.exception.LocalizedCoreFormats;
import org.hipparchus.util.FastMath;
import org.orekit.errors.OrekitException;
import org.orekit.errors.OrekitIllegalArgumentException;
import org.orekit.errors.OrekitMessages;
import org.orekit.errors.TimeStampedCacheException;
import org.orekit.time.FieldAbsoluteDate;
import org.orekit.time.FieldTimeStamped;

import java.util.List;

/** A trimmer for externally stored chronologically sorted lists.
 * @author Evan Ward
 * @author Vincent Cucchietti
 * @since 12.1
 */
public class FieldSortedListTrimmer {

    /** Size list to return from {@link #getNeighborsSubList(FieldAbsoluteDate, List)}. */
    private final int neighborsSize;

    /**
     * Create a new cache with the given neighbors size and data.
     *
     * @param neighborsSize size of the list returned from {@link #getNeighborsSubList(FieldAbsoluteDate, List)}.
     */
    public FieldSortedListTrimmer(final int neighborsSize) {
        if (neighborsSize < 1) {
            throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL,
                                                     neighborsSize, 1);
        }
        // assign instance variables
        this.neighborsSize = neighborsSize;
    }

    /** Get size of the list returned from {@link #getNeighborsSubList(FieldAbsoluteDate, List)}.
     * @return size of the list returned from {@link #getNeighborsSubList(FieldAbsoluteDate, List)}
     */
    public int getNeighborsSize() {
        return neighborsSize;
    }

    /** Get the entries surrounding a central date.
     * <p>
     * If the central date is well within covered range, the returned array will
     * be balanced with half the points before central date and half the points
     * after it (depending on n parity, of course). If the central date is near
     * the boundary, then the returned array will be unbalanced and will contain
     * only the n earliest (or latest) entries. A typical example of the later
     * case is leap seconds cache, since the number of leap seconds cannot be
     * arbitrarily increased.
     * </p>
     * @param <T>  the type of data
     * @param <K>  the type of the field elements
     * @param central central date
     * @param data complete list of entries (must be chronologically sorted)
     * @return entries surrounding the specified date (sublist of {@code data})
     */
    public <T extends FieldTimeStamped<K>, K extends CalculusFieldElement<K>>
        List<T> getNeighborsSubList(final FieldAbsoluteDate<K> central, final List<T> data) {

        if (neighborsSize > data.size()) {
            throw new OrekitException(OrekitMessages.NOT_ENOUGH_DATA, data.size());
        }

        // Find central index
        final int i = findIndex(central, data);

        // Check index in the range of the data
        if (i < 0) {
            final FieldAbsoluteDate<K> earliest = data.get(0).getDate();
            throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
                                                earliest, central, earliest.durationFrom(central).getReal());
        }
        else if (i >= data.size()) {
            final FieldAbsoluteDate<K> latest = data.get(data.size() - 1).getDate();
            throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
                                                latest, central, central.durationFrom(latest).getReal());
        }

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

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

    /**
     * Find the index, i, to {@code data} such that {@code data[i] <= t} and
     * {@code data[i+1] > t} if {@code data[i+1]} exists.
     *
     * @param <T>  the type of data
     * @param <K>  the type of the field elements
     * @param t the time
     * @param data complete list of entries (must be chronologically sorted)
     *
     * @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 <T extends FieldTimeStamped<K>, K extends CalculusFieldElement<K>>
        int findIndex(final FieldAbsoluteDate<K> t, final List<T> data) {
        // left bracket of search algorithm
        int iInf  = 0;
        K   dtInf = t.durationFrom(data.get(0));
        if (dtInf.getReal() < 0) {
            // before first entry
            return -1;
        }

        // right bracket of search algorithm
        int iSup  = data.size() - 1;
        K   dtSup = t.durationFrom(data.get(data.size() - 1));
        if (dtSup.getReal() > 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(dtSup.multiply(iInf).subtract(dtInf.multiply(iSup)).divide(dtSup.subtract(dtInf)).getReal());
            final int iMed    = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup - 1));
            final K   dtMed   = t.durationFrom(data.get(iMed).getDate());
            if (dtMed.getReal() < 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.getReal() == 0.0) {
            return iSup;
        }

        return iInf;

    }

}