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
18 package org.apache.commons.numbers.examples.jmh.arrays;
19
20 /**
21 * An {@link SearchableInterval} backed by an array of ordered keys. The interval is searched using
22 * a linear scan of the data. The scan start point is chosen from reference points within the data.
23 *
24 * <p>The scan is fast when the number of keys is small.
25 *
26 * @since 1.2
27 */
28 final class ScanningKeyInterval implements SearchableInterval, SearchableInterval2 {
29 // Note:
30 // Using 4 markers into the data allows this class to return the same
31 // performance as using a binary search within the data when n < 1600.
32 // Benchmarked by searching once for next and previous from median points between k.
33
34 /** The ordered keys. */
35 private final int[] keys;
36 /** The original number of keys. */
37 private final int n;
38 /** Index into the keys (used for fast-forward). */
39 private final int i1;
40 /** Index into the keys (used for fast-forward). */
41 private final int i2;
42 /** Index into the keys (used for fast-forward). */
43 private final int i3;
44
45 /**
46 * Create an instance with the provided keys.
47 *
48 * @param indices Indices.
49 * @param n Number of indices.
50 */
51 ScanningKeyInterval(int[] indices, int n) {
52 keys = indices;
53 this.n = n;
54 // Divide into quarters for fast-forward
55 i1 = n >>> 2;
56 i2 = n >>> 1;
57 i3 = i1 + i2;
58 }
59
60 /**
61 * Initialise an instance with {@code n} initial {@code indices}. The indices are used in place.
62 *
63 * @param indices Indices.
64 * @param n Number of indices.
65 * @return the interval
66 * @throws IllegalArgumentException if the indices are not unique and ordered; or not
67 * in the range {@code [0, 2^31-1)}; or {@code n <= 0}
68 */
69 static ScanningKeyInterval of(int[] indices, int n) {
70 // Check the indices are uniquely ordered
71 if (n <= 0) {
72 throw new IllegalArgumentException("No indices to define the range");
73 }
74 int p = indices[0];
75 for (int i = 0; ++i < n;) {
76 final int c = indices[i];
77 if (c <= p) {
78 throw new IllegalArgumentException("Indices are not unique and ordered");
79 }
80 p = c;
81 }
82 if (indices[0] < 0) {
83 throw new IllegalArgumentException("Unsupported min value: " + indices[0]);
84 }
85 if (indices[n - 1] == Integer.MAX_VALUE) {
86 throw new IllegalArgumentException("Unsupported max value: " + Integer.MAX_VALUE);
87 }
88 return new ScanningKeyInterval(indices, n);
89 }
90
91 @Override
92 public int left() {
93 return keys[0];
94 }
95
96 @Override
97 public int right() {
98 return keys[n - 1];
99 }
100
101 @Override
102 public int previousIndex(int k) {
103 return keys[previous(k)];
104 }
105
106 @Override
107 public int nextIndex(int k) {
108 return keys[next(k)];
109 }
110
111 @Override
112 public int split(int ka, int kb, int[] upper) {
113 int i = next(kb + 1);
114 upper[0] = keys[i];
115 // Find the lower
116 do {
117 --i;
118 } while (keys[i] >= ka);
119 return keys[i];
120 }
121
122 /**
123 * Find the key index {@code i} of {@code keys[i] <= k}.
124 *
125 * @param k Target key.
126 * @return the key index
127 */
128 private int previous(int k) {
129 // Scan the sorted keys from the end.
130 // Assume left <= k <= right thus no index checks required.
131 // IndexOutOfBoundsException indicates incorrect usage by the caller.
132
133 // Attempt fast-forward
134 int i;
135 if (keys[i2] > k) {
136 i = keys[i1] > k ? i1 : i2;
137 } else {
138 i = keys[i3] > k ? i3 : n;
139 }
140 do {
141 --i;
142 } while (keys[i] > k);
143 return i;
144 }
145
146 /**
147 * Find the key index {@code i} of {@code keys[i] >= k}.
148 *
149 * @param k Target key.
150 * @return the key index
151 */
152 private int next(int k) {
153 // Scan the sorted keys from the start.
154 // Assume left <= k <= right thus no index checks required.
155 // IndexOutOfBoundsException indicates incorrect usage by the caller.
156
157 // Attempt fast-forward
158 int i;
159 if (keys[i2] < k) {
160 i = keys[i3] < k ? i3 : i2;
161 } else {
162 i = keys[i1] < k ? i1 : -1;
163 }
164 do {
165 ++i;
166 } while (keys[i] < k);
167 return i;
168 }
169
170 @Override
171 public int start() {
172 return 0;
173 }
174
175 @Override
176 public int end() {
177 return n - 1;
178 }
179
180 @Override
181 public int index(int i) {
182 return keys[i];
183 }
184
185 @Override
186 public int previous(int i, int k) {
187 // index(start) <= k < index(i)
188 int j = i;
189 do {
190 --j;
191 } while (keys[j] > k);
192 return j;
193 }
194
195 @Override
196 public int next(int i, int k) {
197 // index(i) < k <= index(end)
198 int j = i;
199 do {
200 ++j;
201 } while (keys[j] < k);
202 return j;
203 }
204
205 @Override
206 public int split(int lo, int hi, int ka, int kb, int[] upper) {
207 // index(lo) < ka <= kb < index(hi)
208
209 // We could test if ka/kb is above or below the
210 // median (keys[lo] + keys[hi]) >>> 1 to pick the side to search
211
212 int j = hi;
213 do {
214 --j;
215 } while (keys[j] > kb);
216 upper[0] = j + 1;
217 // Find the lower
218 while (keys[j] >= ka) {
219 --j;
220 }
221 return j;
222 }
223 }