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 searchable interval that contains indices used for partitioning an array into multiple regions.
21 *
22 * <p>The interval provides the following functionality:
23 *
24 * <ul>
25 * <li>Return the supported bounds of the search {@code [left <= right]}.
26 * <li>Return the previous index contained in the interval from a search point {@code k}.
27 * <li>Return the next index contained in the interval from a search point {@code k}.
28 * </ul>
29 *
30 * <p>Note that the interval provides the supported bounds. If a search begins outside
31 * the supported bounds the result is undefined.
32 *
33 * <p>Implementations may assume indices are positive.
34 *
35 * @see SearchableInterval2
36 * @since 1.2
37 */
38 interface SearchableInterval {
39 /**
40 * The start (inclusive) of the range of indices supported.
41 *
42 * @return start of the supported range
43 */
44 int left();
45
46 /**
47 * The end (inclusive) of the range of indices supported.
48 *
49 * @return end of the supported range
50 */
51 int right();
52
53 /**
54 * Returns the nearest index that occurs on or before the specified starting
55 * index.
56 *
57 * <p>If {@code k < left} or {@code k > right} the result is undefined.
58 *
59 * @param k Index to start checking from (inclusive).
60 * @return the previous index
61 */
62 int previousIndex(int k);
63
64 /**
65 * Returns the nearest index that occurs on or after the specified starting
66 * index.
67 *
68 * <p>If {@code k < left} or {@code k > right} the result is undefined.
69 *
70 * @param k Index to start checking from (inclusive).
71 * @return the next index
72 */
73 int nextIndex(int k);
74
75 /**
76 * Split the interval using two splitting indices. Returns the nearest index that occurs
77 * before the specified split index {@code ka}, and the nearest index that occurs after the
78 * specified split index {@code kb}.
79 *
80 * <p>Note: Requires {@code left < ka <= kb < right}, i.e. there exists a valid interval
81 * above and below the split indices.
82 *
83 * <pre>{@code
84 * l-----------ka-kb----------r
85 * lower <--|
86 * |--> upper
87 *
88 * lower < ka
89 * upper > kb
90 * }</pre>
91 *
92 * <p>The default implementation uses:
93 *
94 * <pre>{@code
95 * upper = nextIndex(kb + 1);
96 * lower = previousIndex(ka - 1);
97 * }</pre>
98 *
99 * <p>Implementations may override this method if both indices can be obtained together.
100 *
101 * <p>If {@code ka <= left} or {@code kb >= right} the result is undefined.
102 *
103 * @param ka Split index.
104 * @param kb Split index.
105 * @param upper Upper index.
106 * @return the lower index
107 */
108 default int split(int ka, int kb, int[] upper) {
109 upper[0] = nextIndex(kb + 1);
110 return previousIndex(ka - 1);
111 }
112 }