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 }