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 pointers to indices in the interval. These pointers are used
23 * to assist in searching the interval and can be used to access the index value.
24 *
25 * <p>The interval provides the following functionality:
26 *
27 * <ul>
28 * <li>Return the supported bounds of the search pointers {@code [start <= end]}.
29 * <li>Return a pointer {@code j} to the previous index contained in the interval from a search point {@code i}.
30 * <li>Return a pointer {@code j} to the next index contained in the interval from a search point {@code i}.
31 * <li>Split the interval around two indices given search points {@code i1} and {@code i2}.
32 * </ul>
33 *
34 * <p>Note that the interval provides the supported bounds. If a search begins outside
35 * the supported bounds the result is undefined.
36 *
37 * <p>Implementations may assume indices are positive.
38 *
39 * <p>This differs from {@link SearchableInterval} by providing pointers into the interval to
40 * assist the search.
41 *
42 * @see SearchableInterval
43 * @since 1.2
44 */
45 interface SearchableInterval2 {
46 /**
47 * Start pointer of the interval.
48 *
49 * @return the start pointer
50 */
51 int start();
52
53 /**
54 * End pointer of the interval.
55 *
56 * @return the end pointer
57 */
58 int end();
59
60 /**
61 * Return the index value {@code k} for the pointer.
62 *
63 * <p>If {@code i < start} or {@code i > end} the result is undefined.
64 *
65 * @param i Pointer.
66 * @return the index value of {@code i}
67 */
68 int index(int i);
69
70 /**
71 * Returns a pointer to the nearest index that occurs on or before the specified starting index.
72 *
73 * <p>Assumes {@code index(start) <= k < index(i)}.
74 *
75 * @param i Pointer.
76 * @param k Index to start checking from (inclusive).
77 * @return the previous pointer
78 */
79 int previous(int i, int k);
80
81 /**
82 * Returns a pointer to the nearest index that occurs on or after the specified starting
83 * index.
84 *
85 * <p>Assumes {@code index(i) < k <= index(end)}.
86 *
87 * @param i Pointer.
88 * @param k Index to start checking from (inclusive).
89 * @return the next index
90 */
91 int next(int i, int k);
92
93 /**
94 * Split the interval using two splitting indices. Returns a pointer to the the
95 * nearest index that occurs before the specified split index {@code ka}, and a
96 * pointer to the nearest index that occurs after the specified split index
97 * {@code kb}.
98 *
99 * <p>Requires {@code index(lo) < ka <= kb < index(hi)}, i.e. there exists a
100 * valid interval above and below the split indices.
101 *
102 * <pre>{@code
103 * lo-----------ka-kb----------hi
104 * lower <--|
105 * |--> upper
106 *
107 * index(lower) < ka
108 * index(upper) > kb
109 * }</pre>
110 *
111 * <p>The default implementation uses:
112 *
113 * <pre>{@code
114 * upper = next(hi, kb + 1);
115 * lower = previous(lo, ka - 1);
116 * }</pre>
117 *
118 * <p>Implementations may override this method if both pointers can be obtained
119 * together.
120 *
121 * <p>If {@code lo < start} or {@code hi > end} the result is undefined.
122 *
123 * @param lo Lower pointer.
124 * @param hi Upper pointer.
125 * @param ka Split index.
126 * @param kb Split index.
127 * @param upper Upper pointer.
128 * @return the lower pointer
129 */
130 default int split(int lo, int hi, int ka, int kb, int[] upper) {
131 upper[0] = next(hi, kb + 1);
132 return previous(lo, ka - 1);
133 }
134 }