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 * A {@link SearchableInterval} backed by an array of ordered keys. The interval is searched using
22 * a binary search.
23 *
24 * @since 1.2
25 */
26 final class BinarySearchKeyInterval implements SearchableInterval, SearchableInterval2 {
27 /** The ordered keys for descending search. */
28 private final int[] keys;
29 /** The original number of keys - 1. This is more convenient to store for the use cases. */
30 private final int nm1;
31
32 /**
33 * Create an instance with the provided keys.
34 *
35 * @param indices Indices.
36 * @param n Number of indices.
37 */
38 BinarySearchKeyInterval(int[] indices, int n) {
39 nm1 = n - 1;
40 keys = indices;
41 }
42
43 /**
44 * Initialise an instance with the {@code indices}. The indices are used in place.
45 *
46 * @param indices Indices.
47 * @param n Number of indices.
48 * @return the interval
49 * @throws IllegalArgumentException if the indices are not unique and ordered;
50 * or {@code n <= 0}
51 */
52 static BinarySearchKeyInterval of(int[] indices, int n) {
53 // Check the indices are uniquely ordered
54 if (n <= 0) {
55 throw new IllegalArgumentException("No indices to define the range");
56 }
57 int p = indices[0];
58 for (int i = 0; ++i < n;) {
59 final int c = indices[i];
60 if (c <= p) {
61 throw new IllegalArgumentException("Indices are not unique and ordered");
62 }
63 p = c;
64 }
65 return new BinarySearchKeyInterval(indices, n);
66 }
67
68 @Override
69 public int left() {
70 return keys[0];
71 }
72
73 @Override
74 public int right() {
75 return keys[nm1];
76 }
77
78 @Override
79 public int previousIndex(int k) {
80 // Assume left <= k <= right thus no index checks required.
81 // IndexOutOfBoundsException indicates incorrect usage by the caller.
82 return keys[Partition.searchLessOrEqual(keys, 0, nm1, k)];
83 }
84
85 @Override
86 public int nextIndex(int k) {
87 // Assume left <= k <= right thus no index checks required.
88 // IndexOutOfBoundsException indicates incorrect usage by the caller.
89 return keys[Partition.searchGreaterOrEqual(keys, 0, nm1, k)];
90 }
91
92 @Override
93 public int split(int ka, int kb, int[] upper) {
94 int i = Partition.searchGreaterOrEqual(keys, 0, nm1, kb + 1);
95 upper[0] = keys[i];
96 // Find the lower using a scan since a typical use case has ka == kb
97 // and a scan is faster than a second binary search.
98 do {
99 --i;
100 } while (keys[i] >= ka);
101 return keys[i];
102 }
103
104 @Override
105 public int start() {
106 return 0;
107 }
108
109 @Override
110 public int end() {
111 return nm1;
112 }
113
114 @Override
115 public int index(int i) {
116 return keys[i];
117 }
118
119 // Use case for previous/next is when left/right is within
120 // a partition pivot [p0, p1]. Most likely case is p0 == p1
121 // and a scan is faster.
122
123 @Override
124 public int previous(int i, int k) {
125 // index(start) <= k < index(i)
126 int j = i;
127 do {
128 --j;
129 } while (keys[j] > k);
130 return j;
131 }
132
133 @Override
134 public int next(int i, int k) {
135 // index(i) < k <= index(end)
136 int j = i;
137 do {
138 ++j;
139 } while (keys[j] < k);
140 return j;
141 }
142
143 @Override
144 public int split(int lo, int hi, int ka, int kb, int[] upper) {
145 // index(lo) < ka <= kb < index(hi)
146
147 // We could test if ka/kb is above or below the
148 // median (keys[lo] + keys[hi]) >>> 1 to pick the side to search
149
150 int j = Partition.searchGreaterOrEqual(keys, lo, hi, kb + 1);
151 upper[0] = j;
152 // Find the lower using a scan since a typical use case has ka == kb
153 // and a scan is faster than a second binary search.
154 do {
155 --j;
156 } while (keys[j] >= ka);
157 return j;
158 }
159 }