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.arrays;
19
20 /**
21 * An {@link UpdatingInterval} backed by an array of ordered keys.
22 *
23 * @since 1.2
24 */
25 final class KeyUpdatingInterval implements UpdatingInterval {
26 /** Size to use a scan of the keys when splitting instead of binary search.
27 * Note binary search has an overhead on small size due to the random left/right
28 * branching per iteration. It is much faster on very large sizes. */
29 private static final int SCAN_SIZE = 256;
30
31 /** The ordered keys. */
32 private final int[] keys;
33 /** Index of the left key. */
34 private int l;
35 /** Index of the right key. */
36 private int r;
37
38 /**
39 * Create an instance with the provided {@code indices}.
40 *
41 * <p><strong>Warning:</strong> Indices must be sorted and distinct.
42 *
43 * @param indices Indices.
44 * @param n Number of indices.
45 */
46 KeyUpdatingInterval(int[] indices, int n) {
47 this(indices, 0, n - 1);
48 }
49
50 /**
51 * @param indices Indices.
52 * @param l Index of left key.
53 * @param r Index of right key.
54 */
55 private KeyUpdatingInterval(int[] indices, int l, int r) {
56 keys = indices;
57 this.l = l;
58 this.r = r;
59 }
60
61 @Override
62 public int left() {
63 return keys[l];
64 }
65
66 @Override
67 public int right() {
68 return keys[r];
69 }
70
71 @Override
72 public int updateLeft(int k) {
73 // Assume left < k <= right (i.e. we must move left at least 1)
74 // Search using a scan on the assumption that k is close to the end
75 int i = l;
76 do {
77 ++i;
78 } while (keys[i] < k);
79 l = i;
80 return keys[i];
81 }
82
83 @Override
84 public int updateRight(int k) {
85 // Assume left <= k < right (i.e. we must move right at least 1)
86 // Search using a scan on the assumption that k is close to the end
87 int i = r;
88 do {
89 --i;
90 } while (keys[i] > k);
91 r = i;
92 return keys[i];
93 }
94
95 @Override
96 public UpdatingInterval splitLeft(int ka, int kb) {
97 // left < ka <= kb < right
98
99 // Find the new left bound for the upper interval.
100 // Switch to a linear scan if length is small.
101 int i;
102 if (r - l < SCAN_SIZE) {
103 i = r;
104 do {
105 --i;
106 } while (keys[i] > kb);
107 } else {
108 // Binary search
109 i = searchLessOrEqual(keys, l, r, kb);
110 }
111 final int lowerLeft = l;
112 l = i + 1;
113
114 // Find the new right bound for the lower interval using a scan since a
115 // typical use case has ka == kb and this is faster than a second binary search.
116 while (keys[i] >= ka) {
117 --i;
118 }
119 // return left
120 return new KeyUpdatingInterval(keys, lowerLeft, i);
121 }
122
123 /**
124 * Return the current number of indices in the interval.
125 *
126 * @return the size
127 */
128 int size() {
129 return r - l + 1;
130 }
131
132 /**
133 * Search the data for the largest index {@code i} where {@code a[i]} is
134 * less-than-or-equal to the {@code key}; else return {@code left - 1}.
135 * <pre>
136 * a[i] <= k : left <= i <= right, or (left - 1)
137 * </pre>
138 *
139 * <p>The data is assumed to be in ascending order, otherwise the behaviour is undefined.
140 * If the range contains multiple elements with the {@code key} value, the result index
141 * may be any that match.
142 *
143 * <p>This is similar to using {@link java.util.Arrays#binarySearch(int[], int, int, int)
144 * Arrays.binarySearch}. The method differs in:
145 * <ul>
146 * <li>use of an inclusive upper bound;
147 * <li>returning the closest index with a value below {@code key} if no match was not found;
148 * <li>performing no range checks: it is assumed {@code left <= right} and they are valid
149 * indices into the array.
150 * </ul>
151 *
152 * <p>An equivalent use of binary search is:
153 * <pre>{@code
154 * int i = Arrays.binarySearch(a, left, right + 1, k);
155 * if (i < 0) {
156 * i = ~i - 1;
157 * }
158 * }</pre>
159 *
160 * <p>This specialisation avoids the caller checking the binary search result for the use
161 * case when the presence or absence of a key is not important; only that the returned
162 * index for an absence of a key is the largest index. When used on unique keys this
163 * method can be used to update an upper index so all keys are known to be below a key:
164 *
165 * <pre>{@code
166 * int[] keys = ...
167 * // [i0, i1] contains all keys
168 * int i0 = 0;
169 * int i1 = keys.length - 1;
170 * // Update: [i0, i1] contains all keys <= k
171 * i1 = searchLessOrEqual(keys, i0, i1, k);
172 * }</pre>
173 *
174 * @param a Data.
175 * @param left Lower bound (inclusive).
176 * @param right Upper bound (inclusive).
177 * @param k Key.
178 * @return largest index {@code i} such that {@code a[i] <= k}, or {@code left - 1} if no
179 * such index exists
180 */
181 static int searchLessOrEqual(int[] a, int left, int right, int k) {
182 int l = left;
183 int r = right;
184 while (l <= r) {
185 // Middle value
186 final int m = (l + r) >>> 1;
187 final int v = a[m];
188 // Test:
189 // l------m------r
190 // v k update left
191 // k v update right
192 if (v < k) {
193 l = m + 1;
194 } else if (v > k) {
195 r = m - 1;
196 } else {
197 // Equal
198 return m;
199 }
200 }
201 // Return largest known value below:
202 // r is always moved downward when a middle index value is too high
203 return r;
204 }
205 }