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.arrays;
18
19 /**
20 * An 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 interval {@code [left <= right]}.
26 * <li>Update the left or right bound of the interval using an index {@code k} inside the interval.
27 * <li>Split the interval around two indices {@code k1} and {@code k2}.
28 * </ul>
29 *
30 * <p>Note that the interval provides the supported bounds. If an search index {@code k} is
31 * outside the supported bounds the result is undefined.
32 *
33 * <p>Implementations may assume indices are positive.
34 *
35 * @since 1.2
36 */
37 interface UpdatingInterval {
38 /**
39 * The start (inclusive) of the interval.
40 *
41 * @return start of the interval
42 */
43 int left();
44
45 /**
46 * The end (inclusive) of the interval.
47 *
48 * @return end of the interval
49 */
50 int right();
51
52 /**
53 * Update the left bound of the interval so {@code k <= left}.
54 *
55 * <p>Note: Requires {@code left < k <= right}, i.e. there exists a valid interval
56 * above the index.
57 *
58 * <pre>{@code
59 * l-----------k----------r
60 * |--> l
61 * }</pre>
62 *
63 * @param k Index to start checking from (inclusive).
64 * @return the new left
65 */
66 int updateLeft(int k);
67
68 /**
69 * Update the right bound of the interval so {@code right <= k}.
70 *
71 * <p>Note: Requires {@code left <= k < right}, i.e. there exists a valid interval
72 * below the index.
73 *
74 * <pre>{@code
75 * l-----------k----------r
76 * r <--|
77 * }</pre>
78 *
79 * @param k Index to start checking from (inclusive).
80 * @return the new right
81 */
82 int updateRight(int k);
83
84 /**
85 * Split the interval using two splitting indices. Returns the left interval that occurs
86 * before the specified split index {@code ka}, and updates the current interval left bound
87 * to after the specified split index {@code kb}.
88 *
89 * <p>Note: Requires {@code left < ka <= kb < right}, i.e. there exists a valid interval
90 * both above and below the splitting indices.
91 *
92 * <pre>{@code
93 * l-----------ka-kb----------r
94 * r1 <--| |--> l1
95 *
96 * r1 < ka
97 * l1 > kb
98 * }</pre>
99 *
100 * <p>If {@code ka <= left} or {@code kb >= right} the result is undefined.
101 *
102 * @param ka Split index.
103 * @param kb Split index.
104 * @return the left interval
105 */
106 UpdatingInterval splitLeft(int ka, int kb);
107 }