1 /*
2  * Copyright (C) 2022 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package android.text;
18 
19 import android.annotation.IntRange;
20 import android.graphics.RectF;
21 
22 import androidx.annotation.NonNull;
23 
24 import com.android.internal.util.Preconditions;
25 
26 import java.util.Arrays;
27 import java.util.Objects;
28 
29 /**
30  * Finds text segment boundaries within text. Subclasses can implement different types of text
31  * segments. Grapheme clusters and words are examples of possible text segments. These are
32  * implemented by {@link GraphemeClusterSegmentFinder} and {@link WordSegmentFinder}.
33  *
34  * <p>Text segments may not overlap, so every character belongs to at most one text segment. A
35  * character may belong to no text segments.
36  *
37  * <p>For example, WordSegmentFinder subdivides the text "Hello, World!" into four text segments:
38  * "Hello", ",", "World", "!". The space character does not belong to any text segments.
39  *
40  * @see Layout#getRangeForRect(RectF, SegmentFinder, Layout.TextInclusionStrategy)
41  */
42 public abstract class SegmentFinder {
43     /**
44      * Return value of previousStartBoundary(int), previousEndBoundary(int), nextStartBoundary(int),
45      * and nextEndBoundary(int) when there are no boundaries of the specified type in the specified
46      * direction.
47      */
48     public static final int DONE = -1;
49 
50     /**
51      * Returns the character offset of the previous text segment start boundary before the specified
52      * character offset, or {@code DONE} if there are none.
53      */
previousStartBoundary(@ntRangefrom = 0) int offset)54     public abstract int previousStartBoundary(@IntRange(from = 0) int offset);
55 
56     /**
57      * Returns the character offset of the previous text segment end boundary before the specified
58      * character offset, or {@code DONE} if there are none.
59      */
previousEndBoundary(@ntRangefrom = 0) int offset)60     public abstract int previousEndBoundary(@IntRange(from = 0) int offset);
61 
62     /**
63      * Returns the character offset of the next text segment start boundary after the specified
64      * character offset, or {@code DONE} if there are none.
65      */
nextStartBoundary(@ntRangefrom = 0) int offset)66     public abstract int nextStartBoundary(@IntRange(from = 0) int offset);
67 
68     /**
69      * Returns the character offset of the next text segment end boundary after the specified
70      * character offset, or {@code DONE} if there are none.
71      */
nextEndBoundary(@ntRangefrom = 0) int offset)72     public abstract int nextEndBoundary(@IntRange(from = 0) int offset);
73 
74     /**
75      * The default {@link SegmentFinder} implementation based on given segment ranges.
76      */
77     public static class PrescribedSegmentFinder extends SegmentFinder {
78         private final int[] mSegments;
79 
80         /**
81          * Create a SegmentFinder with segments stored in an array, where i-th segment's start is
82          * stored at segments[2 * i] and end is stored at segments[2 * i + 1] respectively.
83          *
84          * <p> It is required that segments do not overlap, and are already sorted by their start
85          * indices. </p>
86          * @param segments the array that stores the segment ranges.
87          * @throws IllegalArgumentException if the given segments array's length is not even; the
88          * given segments are not sorted or there are segments overlap with others.
89          */
PrescribedSegmentFinder(@onNull int[] segments)90         public PrescribedSegmentFinder(@NonNull int[] segments) {
91             checkSegmentsValid(segments);
92             mSegments = segments;
93         }
94 
95         /** {@inheritDoc} */
96         @Override
previousStartBoundary(@ntRangefrom = 0) int offset)97         public int previousStartBoundary(@IntRange(from = 0) int offset) {
98             return findPrevious(offset, /* isStart = */ true);
99         }
100 
101         /** {@inheritDoc} */
102         @Override
previousEndBoundary(@ntRangefrom = 0) int offset)103         public int previousEndBoundary(@IntRange(from = 0) int offset) {
104             return findPrevious(offset, /* isStart = */ false);
105         }
106 
107         /** {@inheritDoc} */
108         @Override
nextStartBoundary(@ntRangefrom = 0) int offset)109         public int nextStartBoundary(@IntRange(from = 0) int offset) {
110             return findNext(offset, /* isStart = */ true);
111         }
112 
113         /** {@inheritDoc} */
114         @Override
nextEndBoundary(@ntRangefrom = 0) int offset)115         public int nextEndBoundary(@IntRange(from = 0) int offset) {
116             return findNext(offset, /* isStart = */ false);
117         }
118 
findNext(int offset, boolean isStart)119         private int findNext(int offset, boolean isStart) {
120             if (offset < 0) return DONE;
121             if (mSegments.length < 1 || offset > mSegments[mSegments.length - 1]) return DONE;
122 
123             if (offset < mSegments[0]) {
124                 return isStart ? mSegments[0] : mSegments[1];
125             }
126 
127             int index = Arrays.binarySearch(mSegments, offset);
128             if (index >= 0) {
129                 // mSegments may have duplicate elements (The previous segments end equals
130                 // to the following segments start.) Move the index forwards since we are searching
131                 // for the next segment.
132                 if (index + 1 < mSegments.length && mSegments[index + 1] == offset) {
133                     index = index + 1;
134                 }
135                 // Point the index to the first segment boundary larger than the given offset.
136                 index += 1;
137             } else {
138                 // binarySearch returns the insertion point, it's the first segment boundary larger
139                 // than the given offset.
140                 index = -(index + 1);
141             }
142             if (index >= mSegments.length) return DONE;
143 
144             //  +---------------------------------------+
145             //  |               | isStart   | isEnd     |
146             //  |---------------+-----------+-----------|
147             //  | indexIsStart  | index     | index + 1 |
148             //  |---------------+-----------+-----------|
149             //  | indexIsEnd    | index + 1 | index     |
150             //  +---------------------------------------+
151             boolean indexIsStart = index % 2 == 0;
152             if (isStart != indexIsStart) {
153                 return (index + 1 < mSegments.length) ? mSegments[index + 1] : DONE;
154             }
155             return mSegments[index];
156         }
157 
findPrevious(int offset, boolean isStart)158         private int findPrevious(int offset, boolean isStart) {
159             if (mSegments.length < 1 || offset < mSegments[0]) return DONE;
160 
161             if (offset > mSegments[mSegments.length - 1]) {
162                 return isStart ? mSegments[mSegments.length - 2] : mSegments[mSegments.length - 1];
163             }
164 
165             int index = Arrays.binarySearch(mSegments, offset);
166             if (index >= 0) {
167                 // mSegments may have duplicate elements (when the previous segments end equal
168                 // to the following segments start). Move the index backwards since we are searching
169                 // for the previous segment.
170                 if (index > 0 && mSegments[index - 1] == offset) {
171                     index = index - 1;
172                 }
173                 // Point the index to the first segment boundary smaller than the given offset.
174                 index -= 1;
175             } else {
176                 // binarySearch returns the insertion point, insertionPoint - 1 is the first
177                 // segment boundary smaller than the given offset.
178                 index = -(index + 1) - 1;
179             }
180             if (index < 0) return DONE;
181 
182             //  +---------------------------------------+
183             //  |               | isStart   | isEnd     |
184             //  |---------------+-----------+-----------|
185             //  | indexIsStart  | index     | index - 1 |
186             //  |---------------+-----------+-----------|
187             //  | indexIsEnd    | index - 1 | index     |
188             //  +---------------------------------------+
189             boolean indexIsStart = index % 2 == 0;
190             if (isStart != indexIsStart) {
191                 return (index > 0) ? mSegments[index - 1] : DONE;
192             }
193             return mSegments[index];
194         }
195 
checkSegmentsValid(int[] segments)196         private static void checkSegmentsValid(int[] segments) {
197             Objects.requireNonNull(segments);
198             Preconditions.checkArgument(segments.length % 2 == 0,
199                     "the length of segments must be even");
200             if (segments.length == 0) return;
201             int lastSegmentEnd = Integer.MIN_VALUE;
202             for (int index = 0; index < segments.length; index += 2) {
203                 if (segments[index] < lastSegmentEnd) {
204                     throw new IllegalArgumentException("segments can't overlap");
205                 }
206                 if (segments[index] >= segments[index + 1]) {
207                     throw new IllegalArgumentException("the segment range can't be empty");
208                 }
209                 lastSegmentEnd = segments[index + 1];
210             }
211         }
212     }
213 }
214