1 /* Contributed in the public domain.
2 * Licensed to CS GROUP (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;
18
19 import org.hipparchus.exception.LocalizedCoreFormats;
20 import org.hipparchus.util.FastMath;
21 import org.orekit.errors.OrekitException;
22 import org.orekit.errors.OrekitIllegalArgumentException;
23 import org.orekit.errors.OrekitMessages;
24 import org.orekit.errors.TimeStampedCacheException;
25 import org.orekit.time.AbsoluteDate;
26 import org.orekit.time.TimeStamped;
27
28 import java.util.List;
29
30 /** A trimmer for externally stored chronologically sorted lists.
31 *
32 * @author Evan Ward
33 * @since 12.1
34 */
35 public class SortedListTrimmer {
36
37 /** Size of the list to return from {@link #getNeighborsSubList(AbsoluteDate, List)}. */
38 private final int neighborsSize;
39
40 /** Create a new trimmer with the given neighbors size.
41 * @param neighborsSize size of the list returned from {@link #getNeighborsSubList(AbsoluteDate, List)}
42 */
43 public SortedListTrimmer(final int neighborsSize) {
44 if (neighborsSize < 1) {
45 throw new OrekitIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL,
46 neighborsSize, 1);
47 }
48 // assign instance variables
49 this.neighborsSize = neighborsSize;
50 }
51
52 /** Get size of the list returned from {@link #getNeighborsSubList(AbsoluteDate, List)}.
53 * @return size of the list returned from {@link #getNeighborsSubList(AbsoluteDate, List)}
54 */
55 public int getNeighborsSize() {
56 return neighborsSize;
57 }
58
59 /** Get the entries surrounding a central date.
60 * <p>
61 * If the central date is well within covered range, the returned array will
62 * be balanced with half the points before central date and half the points
63 * after it (depending on n parity, of course). If the central date is near
64 * the boundary, then the returned array will be unbalanced and will contain
65 * only the n earliest (or latest) entries. A typical example of the later
66 * case is leap seconds cache, since the number of leap seconds cannot be
67 * arbitrarily increased.
68 * </p>
69 * @param <T> the type of data
70 * @param central central date
71 * @param data complete list of entries (must be chronologically sorted)
72 * @return entries surrounding the specified date (sublist of {@code data})
73 */
74 public <T extends TimeStamped> List<T> getNeighborsSubList(final AbsoluteDate central, final List<T> data) {
75
76 if (neighborsSize > data.size()) {
77 throw new OrekitException(OrekitMessages.NOT_ENOUGH_DATA, data.size());
78 }
79
80 // find central index
81 final int i = findIndex(central, data);
82
83 // check index in in the range of the data
84 if (i < 0) {
85 final AbsoluteDate earliest = data.get(0).getDate();
86 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_BEFORE,
87 earliest, central, earliest.durationFrom(central));
88 } else if (i >= data.size()) {
89 final AbsoluteDate latest = data.get(data.size() - 1).getDate();
90 throw new TimeStampedCacheException(OrekitMessages.UNABLE_TO_GENERATE_NEW_DATA_AFTER,
91 latest, central, central.durationFrom(latest));
92 }
93
94 // force unbalanced range if necessary
95 int start = FastMath.max(0, i - (neighborsSize - 1) / 2);
96 final int end = FastMath.min(data.size(), start + neighborsSize);
97 start = end - neighborsSize;
98
99 // return list without copying
100 return data.subList(start, end);
101
102 }
103
104 /**
105 * Find the index, i, to {@code data} such that {@code data[i] <= t} and
106 * {@code data[i+1] > t} if {@code data[i+1]} exists.
107 *
108 * @param <T> the type of data
109 * @param t the time
110 * @param data complete list of entries (must be chronologically sorted)
111 * @return the index of the data at or just before {@code t}, {@code -1} if
112 * {@code t} is before the first entry, or {@code data.size()} if
113 * {@code t} is after the last entry.
114 */
115 private <T extends TimeStamped> int findIndex(final AbsoluteDate t, final List<T> data) {
116
117 // left bracket of search algorithm
118 int iInf = 0;
119 double dtInf = t.durationFrom(data.get(0));
120 if (dtInf < 0) {
121 // before first entry
122 return -1;
123 }
124
125 // right bracket of search algorithm
126 int iSup = data.size() - 1;
127 double dtSup = t.durationFrom(data.get(data.size() - 1));
128 if (dtSup > 0) {
129 // after last entry
130 return data.size();
131 }
132
133 // search entries, using linear interpolation
134 // this should take only 2 iterations for near linear entries (most frequent use case)
135 // regardless of the number of entries
136 // this is much faster than binary search for large number of entries
137 while (iSup - iInf > 1) {
138 final int iInterp = (int) FastMath.rint((iInf * dtSup - iSup * dtInf) / (dtSup - dtInf));
139 final int iMed = FastMath.max(iInf + 1, FastMath.min(iInterp, iSup - 1));
140 final double dtMed = t.durationFrom(data.get(iMed).getDate());
141 if (dtMed < 0) {
142 iSup = iMed;
143 dtSup = dtMed;
144 } else {
145 iInf = iMed;
146 dtInf = dtMed;
147 }
148 }
149
150 // at this point data[iInf] <= t <= data[iSup], but the javadoc for this method
151 // says the upper bound is exclusive, so check for equality to make a half open
152 // interval.
153 if (dtSup == 0.0) {
154 return iSup;
155 }
156
157 return iInf;
158
159 }
160
161 }