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 @android.ravenwood.annotation.RavenwoodKeepWholeClass 43 public abstract class SegmentFinder { 44 /** 45 * Return value of previousStartBoundary(int), previousEndBoundary(int), nextStartBoundary(int), 46 * and nextEndBoundary(int) when there are no boundaries of the specified type in the specified 47 * direction. 48 */ 49 public static final int DONE = -1; 50 51 /** 52 * Returns the character offset of the previous text segment start boundary before the specified 53 * character offset, or {@code DONE} if there are none. 54 */ previousStartBoundary(@ntRangefrom = 0) int offset)55 public abstract int previousStartBoundary(@IntRange(from = 0) int offset); 56 57 /** 58 * Returns the character offset of the previous text segment end boundary before the specified 59 * character offset, or {@code DONE} if there are none. 60 */ previousEndBoundary(@ntRangefrom = 0) int offset)61 public abstract int previousEndBoundary(@IntRange(from = 0) int offset); 62 63 /** 64 * Returns the character offset of the next text segment start boundary after the specified 65 * character offset, or {@code DONE} if there are none. 66 */ nextStartBoundary(@ntRangefrom = 0) int offset)67 public abstract int nextStartBoundary(@IntRange(from = 0) int offset); 68 69 /** 70 * Returns the character offset of the next text segment end boundary after the specified 71 * character offset, or {@code DONE} if there are none. 72 */ nextEndBoundary(@ntRangefrom = 0) int offset)73 public abstract int nextEndBoundary(@IntRange(from = 0) int offset); 74 75 /** 76 * The default {@link SegmentFinder} implementation based on given segment ranges. 77 */ 78 public static class PrescribedSegmentFinder extends SegmentFinder { 79 private final int[] mSegments; 80 81 /** 82 * Create a SegmentFinder with segments stored in an array, where i-th segment's start is 83 * stored at segments[2 * i] and end is stored at segments[2 * i + 1] respectively. 84 * 85 * <p> It is required that segments do not overlap, and are already sorted by their start 86 * indices. </p> 87 * @param segments the array that stores the segment ranges. 88 * @throws IllegalArgumentException if the given segments array's length is not even; the 89 * given segments are not sorted or there are segments overlap with others. 90 */ PrescribedSegmentFinder(@onNull int[] segments)91 public PrescribedSegmentFinder(@NonNull int[] segments) { 92 checkSegmentsValid(segments); 93 mSegments = segments; 94 } 95 96 /** {@inheritDoc} */ 97 @Override previousStartBoundary(@ntRangefrom = 0) int offset)98 public int previousStartBoundary(@IntRange(from = 0) int offset) { 99 return findPrevious(offset, /* isStart = */ true); 100 } 101 102 /** {@inheritDoc} */ 103 @Override previousEndBoundary(@ntRangefrom = 0) int offset)104 public int previousEndBoundary(@IntRange(from = 0) int offset) { 105 return findPrevious(offset, /* isStart = */ false); 106 } 107 108 /** {@inheritDoc} */ 109 @Override nextStartBoundary(@ntRangefrom = 0) int offset)110 public int nextStartBoundary(@IntRange(from = 0) int offset) { 111 return findNext(offset, /* isStart = */ true); 112 } 113 114 /** {@inheritDoc} */ 115 @Override nextEndBoundary(@ntRangefrom = 0) int offset)116 public int nextEndBoundary(@IntRange(from = 0) int offset) { 117 return findNext(offset, /* isStart = */ false); 118 } 119 findNext(int offset, boolean isStart)120 private int findNext(int offset, boolean isStart) { 121 if (offset < 0) return DONE; 122 if (mSegments.length < 1 || offset > mSegments[mSegments.length - 1]) return DONE; 123 124 if (offset < mSegments[0]) { 125 return isStart ? mSegments[0] : mSegments[1]; 126 } 127 128 int index = Arrays.binarySearch(mSegments, offset); 129 if (index >= 0) { 130 // mSegments may have duplicate elements (The previous segments end equals 131 // to the following segments start.) Move the index forwards since we are searching 132 // for the next segment. 133 if (index + 1 < mSegments.length && mSegments[index + 1] == offset) { 134 index = index + 1; 135 } 136 // Point the index to the first segment boundary larger than the given offset. 137 index += 1; 138 } else { 139 // binarySearch returns the insertion point, it's the first segment boundary larger 140 // than the given offset. 141 index = -(index + 1); 142 } 143 if (index >= mSegments.length) return DONE; 144 145 // +---------------------------------------+ 146 // | | isStart | isEnd | 147 // |---------------+-----------+-----------| 148 // | indexIsStart | index | index + 1 | 149 // |---------------+-----------+-----------| 150 // | indexIsEnd | index + 1 | index | 151 // +---------------------------------------+ 152 boolean indexIsStart = index % 2 == 0; 153 if (isStart != indexIsStart) { 154 return (index + 1 < mSegments.length) ? mSegments[index + 1] : DONE; 155 } 156 return mSegments[index]; 157 } 158 findPrevious(int offset, boolean isStart)159 private int findPrevious(int offset, boolean isStart) { 160 if (mSegments.length < 1 || offset < mSegments[0]) return DONE; 161 162 if (offset > mSegments[mSegments.length - 1]) { 163 return isStart ? mSegments[mSegments.length - 2] : mSegments[mSegments.length - 1]; 164 } 165 166 int index = Arrays.binarySearch(mSegments, offset); 167 if (index >= 0) { 168 // mSegments may have duplicate elements (when the previous segments end equal 169 // to the following segments start). Move the index backwards since we are searching 170 // for the previous segment. 171 if (index > 0 && mSegments[index - 1] == offset) { 172 index = index - 1; 173 } 174 // Point the index to the first segment boundary smaller than the given offset. 175 index -= 1; 176 } else { 177 // binarySearch returns the insertion point, insertionPoint - 1 is the first 178 // segment boundary smaller than the given offset. 179 index = -(index + 1) - 1; 180 } 181 if (index < 0) return DONE; 182 183 // +---------------------------------------+ 184 // | | isStart | isEnd | 185 // |---------------+-----------+-----------| 186 // | indexIsStart | index | index - 1 | 187 // |---------------+-----------+-----------| 188 // | indexIsEnd | index - 1 | index | 189 // +---------------------------------------+ 190 boolean indexIsStart = index % 2 == 0; 191 if (isStart != indexIsStart) { 192 return (index > 0) ? mSegments[index - 1] : DONE; 193 } 194 return mSegments[index]; 195 } 196 checkSegmentsValid(int[] segments)197 private static void checkSegmentsValid(int[] segments) { 198 Objects.requireNonNull(segments); 199 Preconditions.checkArgument(segments.length % 2 == 0, 200 "the length of segments must be even"); 201 if (segments.length == 0) return; 202 int lastSegmentEnd = Integer.MIN_VALUE; 203 for (int index = 0; index < segments.length; index += 2) { 204 if (segments[index] < lastSegmentEnd) { 205 throw new IllegalArgumentException("segments can't overlap"); 206 } 207 if (segments[index] >= segments[index + 1]) { 208 throw new IllegalArgumentException("the segment range can't be empty"); 209 } 210 lastSegmentEnd = segments[index + 1]; 211 } 212 } 213 } 214 } 215