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 * A cache of pivot indices used for partitioning an array into multiple regions.
21 *
22 * <p>This extends the {@link PivotCache} interface to add support to traverse
23 * a region between pivot and non-pivot indices. It is intended to be used to
24 * allow unsorted gaps between pivots to be targeted using a full sort when
25 * the partition function is configured to partition several regions [ka, kb].
26 *
27 * <p>In the following example the partition algorithm must fully sort [k1, k2]
28 * and [k3, k4]. The first iteration detects pivots downstream from [k1, k2].
29 * The second iteration can fill in the gaps when processing [k3, k4]:
30 *
31 * <pre>
32 * Partition:
33 * 0------k1---k2-------k3--------------k4-N
34 *
35 * Iteration 1:
36 * 0------ppppppp----p------p--p-------p---N
37 *
38 * Iteration 2:
39 * ------- Partition (p, k3, p)
40 * ss sssssss Sort these regions
41 * -- Partition (p, k4, N)
42 * </pre>
43 *
44 * @since 1.2
45 */
46 interface ScanningPivotCache extends PivotCache {
47 /**
48 * Move the start (inclusive) of the range of indices supported.
49 *
50 * <p>Implementations may discard previously stored indices during this operation, for
51 * example all indices below {@code newLeft}.
52 *
53 * <p>This method can be used when partitioning keys {@code k1, k2, ...} in ascending
54 * order to indicate the next {@code k} that will be processed. The cache can optimise
55 * pivot storage to help partition downstream keys.
56 *
57 * <p>Note: If {@code newLeft < left} then the updated range is outside the current
58 * support. Implementations may choose to: move {@code left} so the new support is
59 * {@code [newLeft, right]}; return {@code false} to indicate the support was not changed;
60 * or to throw an exception (which should be documented).
61 *
62 * <p>Note: If {@code newLeft > right} then the updated range is outside the current
63 * support. Implementations may choose to: move {@code right} so the new support is
64 * {@code [newLeft, newleft]}; return {@code false} to indicate the support was not changed;
65 * or to throw an exception (which should be documented).
66 *
67 * @param newLeft Start of the supported range.
68 * @return true if the support was successfully modified
69 */
70 boolean moveLeft(int newLeft);
71
72 /**
73 * Returns the nearest non-pivot index that occurs on or after the specified starting
74 * index <em>within the supported range</em>. If no such
75 * indices exists then {@code right + n} is returned, where {@code n} is strictly positive.
76 *
77 * <p>If the starting index is less than the supported range {@code left}
78 * the result is undefined.
79 *
80 * <p>This method is intended to allow traversing the unsorted ranges between sorted
81 * pivot regions within the range {@code [left, right]}.
82 *
83 * @param k Index to start checking from (inclusive).
84 * @return the index of the next non-pivot, or {@code right + n} if there is no index
85 */
86 int nextNonPivot(int k);
87
88 /**
89 * Returns the nearest non-pivot index that occurs on or before the specified starting
90 * index <em>within the supported range</em>. If no such
91 * indices exists then {@code left - n} is returned, where {@code n} is strictly positive.
92 *
93 * <p>If the starting index is greater than the supported range {@code right}
94 * the result is undefined.
95 *
96 * <p>This method is intended to allow traversing the unsorted ranges between sorted
97 * pivot regions within the range {@code [left, right]}.
98 *
99 * @param k Index to start checking from (inclusive).
100 * @return the index of the next non-pivot, or {@code left - n} if there is no index
101 */
102 int previousNonPivot(int k);
103 }