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>A pivot is an index position that contains a value equal to the value in a fully
23 * sorted array.
24 *
25 * <p>For a pivot {@code p}:
26 *
27 * <pre>{@code
28 * i < p < j
29 * data[i] <= data[p] <= data[j]
30 * }</pre>
31 *
32 * <p>Partitioning moves data in a range {@code [lower, upper]} so that the pivot
33 * {@code p} partitions the data. During this process many pivots may be found
34 * before the search ends. A pivot cache supports storing these pivots so that
35 * they can be used to bracket further searches in the array.
36 *
37 * <p>A pivot cache supports finding a search bracket to partition an index {@code k}
38 * within an array of length {@code n}. The bracket should be an enclosing bound
39 * of known pivots. All data can be rearranged within this bracket without destroying
40 * other regions of the partitioned array. The support for {@code k} is provided within
41 * an inclusive range {@code [left, right]} where {@code 0 <= left <= right < n}.
42 * Thus {@code [left, right]} denotes the region containing all target indices {@code k}
43 * for multi-region partitioning.
44 *
45 * <p>The cache provides the following functionality:
46 *
47 * <ul>
48 * <li>Test if an index {@code [left <= k <= right]} is a known pivot.
49 * <li>Return a {@code lower} bounding pivot for a partition of an index {@code [left <= k <= right]}.
50 * <li>Return an {@code upper} bounding pivot for a partition of an index {@code [left <= k <= right]}.
51 * </ul>
52 *
53 * <p>Note that searching with the bound {@code [lower, upper]} will reorder data
54 * and pivots within this range may be invalidated by moving of data. To prevent
55 * error the bound provided by a cache must use the closest bracketing pivots.
56 *
57 * <p>At least two strategies can be used:
58 *
59 * <ol>
60 * <li>Process {@code k} indices in any order. Store all pivots during the partitioning.
61 * Each subsequent search after the first can use adjacent pivots to bracket the search.
62 * <li>Process {@code k} indices in sorted order. The {@code lower} bound for {@code k+1}
63 * will be {@code k <= lower}. This does not require a cache as {@code upper} can be set
64 * using the end of the data {@code n}. For this case a cache can store pivots which can
65 * be used to bracket the search for {@code k+1}.
66 * </ol>
67 *
68 * <p>Implementations may assume indices are positive.
69 *
70 * @since 1.2
71 */
72 interface PivotCache extends PivotStore {
73 /**
74 * The start (inclusive) of the range of indices supported.
75 *
76 * @return start of the supported range
77 */
78 int left();
79
80 /**
81 * The end (inclusive) of the range of indices supported.
82 *
83 * @return end of the supported range
84 */
85 int right();
86
87 /**
88 * Returns {@code true} if the cache supports storing some of the pivots in the supported
89 * range. A sparse cache can provide approximate bounds for partitioning. These bounds may be
90 * smaller than using the bounds of the entire array. Note that partitioning may destroy
91 * previous pivots within a range. Thus a sparse cache should be used to partition indices
92 * in sorted order so that bounds generated by each iteration do not overlap the bounds
93 * of a previous partition. This can be done by using the previous {@code k} as the left
94 * bound.
95 *
96 * <p>A sparse cache can be created to store 1 pivot between all {@code k} of interest
97 * after the first {@code k}, and optionally two pivots that bracket the entire supported
98 * range. In the following example the partition of {@code k1} stores pivots {@code p}.
99 * These can be used to bracket {@code k2, k3}. An alternative scheme
100 * where no pivots are stored is shown for comparison:
101 *
102 * <pre>
103 * Partition:
104 * 0------k1----------k2------k3---------N
105 *
106 * Iteration 1:
107 * 0------k1------p--------p---------p---N
108 *
109 * Iteration 2:
110 * l---k2---r
111 * or: l-----------k2-----------------N
112 *
113 * Iteration 3:
114 * l--k3-----r
115 * or: l-------k3---------N
116 * </pre>
117 *
118 * <p>If false then the cache will store all pivots within the supported range and
119 * ideally provide the closest bounding pivot around the supported range.
120 *
121 * @return true if sparse
122 */
123 boolean sparse();
124
125 /**
126 * Test if the index {@code k} is a pivot.
127 *
128 * <p><em>If {@code index < left} or {@code index > right} the behavior is not
129 * defined.</em></p>
130 *
131 * @param k Index.
132 * @return true if the index is a pivot within the supported range
133 */
134 boolean contains(int k);
135
136 /**
137 * Returns the nearest pivot index that occurs on or before the specified starting
138 * index. If none exist then {@code -1} is returned.
139 *
140 * @param k Index to start checking from (inclusive).
141 * @return the index of the previous pivot, or {@code -1} if there is no index
142 */
143 int previousPivot(int k);
144
145 /**
146 * Returns the nearest pivot index that occurs on or after the specified starting
147 * index. If none exist then {@code -1} is returned.
148 *
149 * @param k Index to start checking from (inclusive).
150 * @return the index of the next pivot, or {@code -1} if there is no index
151 */
152 default int nextPivot(int k) {
153 return nextPivotOrElse(k, -1);
154 }
155
156 /**
157 * Returns the nearest pivot index that occurs on or after the specified starting
158 * index. If none exist then {@code other} is returned.
159 *
160 * @param k Index to start checking from (inclusive).
161 * @param other Other value.
162 * @return the index of the next pivot, or {@code other} if there is no index
163 */
164 int nextPivotOrElse(int k, int other);
165 }