1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF 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.apache.commons.numbers.examples.jmh.arrays;
18
19 /**
20 * Support for creating {@link PivotCache} implementations.
21 *
22 * @since 1.2
23 */
24 final class PivotCaches {
25 /** Default value for an unset upper floating pivot.
26 * Set as a value higher than any valid array index. */
27 private static final int UPPER_DEFAULT = Integer.MAX_VALUE;
28
29 /** No instances. */
30 private PivotCaches() {}
31
32 /**
33 * Return a {@link PivotCache} for a single {@code k}.
34 *
35 * @param k Index.
36 * @return the pivot cache
37 */
38 static PivotCache ofIndex(int k) {
39 return new PointPivotCache(k);
40 }
41
42 /**
43 * Return a {@link PivotCache} for a single {@code k},
44 * or a pair of indices {@code (k, k+1)}. A pair is
45 * signalled using the sign bit.
46 *
47 * @param k Paired index.
48 * @return the pivot cache
49 */
50 static PivotCache ofPairedIndex(int k) {
51 if (k >= 0) {
52 return new PointPivotCache(k);
53 }
54 // Remove sign bit
55 final int ka = k & Integer.MAX_VALUE;
56 return new RangePivotCache(ka, ka + 1);
57 }
58
59 /**
60 * Return a {@link PivotCache} for the range {@code [left, right]}.
61 *
62 * <p>If the range contains internal indices, the {@link PivotCache} will not
63 * store them and will be {@link PivotCache#sparse() sparse}.
64 *
65 * <p>The range returned instance may implement {@link ScanningPivotCache}.
66 * It should only be cast to a {@link ScanningPivotCache} and used for scanning
67 * if it reports itself as non-{@link PivotCache#sparse() sparse}.
68 *
69 * @param left Lower bound (inclusive).
70 * @param right Upper bound (inclusive).
71 * @return the pivot cache
72 * @see #ofFullRange(int, int)
73 */
74 static PivotCache ofRange(int left, int right) {
75 validateRange(left, right);
76 return left == right ?
77 new PointPivotCache(left) :
78 new RangePivotCache(left, right);
79 }
80
81 /**
82 * Return a {@link PivotCache} for the full-range {@code [left, right]}.
83 * The returned implementation will be non-{@link PivotCache#sparse() sparse}.
84 *
85 * <p>The range returned instance may implement {@link ScanningPivotCache}.
86 *
87 * @param left Lower bound (inclusive).
88 * @param right Upper bound (inclusive).
89 * @return the pivot cache
90 */
91 static PivotCache ofFullRange(int left, int right) {
92 validateRange(left, right);
93 if (right - left <= 1) {
94 return left == right ?
95 new PointPivotCache(left) :
96 new RangePivotCache(left, right);
97 }
98 return IndexSet.ofRange(left, right);
99 }
100
101 /**
102 * Validate the range {@code left <= right}.
103 *
104 * @param left Lower bound (inclusive).
105 * @param right Upper bound (inclusive).
106 */
107 private static void validateRange(int left, int right) {
108 if (right < left) {
109 throw new IllegalArgumentException("Invalid range");
110 }
111 }
112
113 /**
114 * PivotCache for range {@code [left, right]} consisting of a single point.
115 */
116 private static class PointPivotCache implements ScanningPivotCache {
117 /** The target point. */
118 private final int target;
119 /** The upstream pivot closest to the left bound of the support.
120 * Provides a lower search bound for the range [left, right]. */
121 private int lowerPivot = -1;
122 /** The downstream pivot closest to the right bound of the support.
123 * Provides an upper search bound for the range [left, right]. */
124 private int upperPivot = UPPER_DEFAULT;
125
126 /**
127 * @param index Index defining {@code [left, right]}.
128 */
129 PointPivotCache(int index) {
130 this.target = index;
131 }
132
133 @Override
134 public void add(int index) {
135 // Update the floating pivots
136 if (index <= target) {
137 // This does not update upperPivot if index == target.
138 // This case is checked in nextPivot(int).
139 lowerPivot = Math.max(index, lowerPivot);
140 } else {
141 upperPivot = Math.min(index, upperPivot);
142 }
143 }
144
145 @Override
146 public void add(int fromIndex, int toIndex) {
147 // Update the floating pivots
148 if (toIndex <= target) {
149 // This does not update upperPivot if toIndex == target.
150 // This case is checked in nextPivot(int).
151 lowerPivot = Math.max(toIndex, lowerPivot);
152 } else if (fromIndex > target) {
153 upperPivot = Math.min(fromIndex, upperPivot);
154 } else {
155 // Range brackets the target
156 lowerPivot = upperPivot = target;
157 }
158 }
159
160 @Override
161 public int left() {
162 return target;
163 }
164
165 @Override
166 public int right() {
167 return target;
168 }
169
170 @Override
171 public boolean sparse() {
172 // Not sparse between [left, right]
173 return false;
174 }
175
176 @Override
177 public boolean moveLeft(int newLeft) {
178 // Unsupported
179 return false;
180 }
181
182 @Override
183 public boolean contains(int k) {
184 return lowerPivot == k;
185 }
186
187 @Override
188 public int previousPivot(int k) {
189 // Only support scanning within [left, right] => assume k == target
190 return lowerPivot;
191 }
192
193 // Do not override: int nextPivot(int k)
194
195 @Override
196 public int nextPivotOrElse(int k, int other) {
197 // Only support scanning within [left, right]
198 // assume lowerPivot <= left <= k <= right <= upperPivot
199 if (lowerPivot == target) {
200 return target;
201 }
202 return upperPivot == UPPER_DEFAULT ? other : upperPivot;
203 }
204
205 @Override
206 public int nextNonPivot(int k) {
207 // Only support scanning within [left, right] => assume k == target
208 return lowerPivot == target ? target + 1 : target;
209 }
210
211 @Override
212 public int previousNonPivot(int k) {
213 // Only support scanning within [left, right] => assume k == target
214 return lowerPivot == target ? target - 1 : target;
215 }
216 }
217
218 /**
219 * PivotCache for range {@code [left, right]} consisting of a bracketing range
220 * {@code lower <= left < right <= upper}.
221 *
222 * <p>Behaviour is undefined if {@code left == right}. This cache is intended to
223 * bracket a range [left, right] that can be entirely sorted, e.g. if the separation
224 * between left and right is small.
225 */
226 private static class RangePivotCache implements ScanningPivotCache {
227 /** Left bound of the support. */
228 private final int left;
229 /** Right bound of the support. */
230 private final int right;
231 /** The upstream pivot closest to the left bound of the support.
232 * Provides a lower search bound for the range [left, right]. */
233 private int lowerPivot = -1;
234 /** The downstream pivot closest to the right bound of the support.
235 * Provides an upper search bound for the range [left, right]. */
236 private int upperPivot = UPPER_DEFAULT;
237
238 /**
239 * @param left Lower bound (inclusive).
240 * @param right Upper bound (inclusive).
241 */
242 RangePivotCache(int left, int right) {
243 this.left = left;
244 this.right = right;
245 }
246
247 @Override
248 public void add(int index) {
249 // Update the floating pivots
250 if (index <= left) {
251 lowerPivot = Math.max(index, lowerPivot);
252 } else if (index >= right) {
253 upperPivot = Math.min(index, upperPivot);
254 }
255 }
256
257 @Override
258 public void add(int fromIndex, int toIndex) {
259 // Update the floating pivots
260 if (toIndex <= left) {
261 // l-------------r
262 // f---t
263 lowerPivot = Math.max(toIndex, lowerPivot);
264 } else if (fromIndex >= right) {
265 // l-------------r
266 // f---t
267 upperPivot = Math.min(fromIndex, upperPivot);
268 } else {
269 // Range [left, right] overlaps [from, to]
270 // toIndex > left && fromIndex < right
271 // l-------------r
272 // f---t
273 // f----t
274 // f----t
275 if (fromIndex <= left) {
276 lowerPivot = left;
277 }
278 if (toIndex >= right) {
279 upperPivot = right;
280 }
281 }
282 }
283
284 @Override
285 public int left() {
286 return left;
287 }
288
289 @Override
290 public int right() {
291 return right;
292 }
293
294 @Override
295 public boolean sparse() {
296 // Sparse if there are internal points between [left, right]
297 return right - left > 1;
298 }
299
300 @Override
301 public boolean moveLeft(int newLeft) {
302 // Unsupported
303 return false;
304 }
305
306 @Override
307 public boolean contains(int k) {
308 return lowerPivot == k || upperPivot == k;
309 }
310
311 @Override
312 public int previousPivot(int k) {
313 // Only support scanning within [left, right]
314 // assume lowerPivot <= left <= k <= right <= upperPivot
315 return k == upperPivot ? k : lowerPivot;
316 }
317
318 // Do not override: int nextPivot(int k)
319
320 @Override
321 public int nextPivotOrElse(int k, int other) {
322 // Only support scanning within [left, right]
323 // assume lowerPivot <= left <= k <= right <= upperPivot
324 if (k == lowerPivot) {
325 return k;
326 }
327 return upperPivot == UPPER_DEFAULT ? other : upperPivot;
328 }
329
330 @Override
331 public int nextNonPivot(int k) {
332 // Only support scanning within [left, right]
333 // assume lowerPivot <= left <= k <= right <= upperPivot
334 if (sparse()) {
335 throw new UnsupportedOperationException();
336 }
337 // range of size 2
338 // scan right
339 int i = k;
340 if (i == left) {
341 if (lowerPivot != left) {
342 return left;
343 }
344 i++;
345 }
346 if (i == right && upperPivot == right) {
347 i++;
348 }
349 return i;
350 }
351
352 @Override
353 public int previousNonPivot(int k) {
354 // Only support scanning within [left, right]
355 // assume lowerPivot <= left <= k <= right <= upperPivot
356 if (sparse()) {
357 throw new UnsupportedOperationException();
358 }
359 // range of size 2
360 // scan left
361 int i = k;
362 if (i == right) {
363 if (upperPivot != right) {
364 return right;
365 }
366 i--;
367 }
368 if (i == left && lowerPivot == left) {
369 i--;
370 }
371 return i;
372 }
373 }
374 }