View Javadoc
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 }