1/*
2 * Copyright (C) 2006 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
17package android.text;
18
19import com.android.internal.util.ArrayUtils;
20import com.android.internal.util.GrowingArrayUtils;
21
22import libcore.util.EmptyArray;
23
24import java.lang.reflect.Array;
25
26/* package */ abstract class SpannableStringInternal
27{
28    /* package */ SpannableStringInternal(CharSequence source,
29                                          int start, int end) {
30        if (start == 0 && end == source.length())
31            mText = source.toString();
32        else
33            mText = source.toString().substring(start, end);
34
35        mSpans = EmptyArray.OBJECT;
36        // Invariant: mSpanData.length = mSpans.length * COLUMNS
37        mSpanData = EmptyArray.INT;
38
39        if (source instanceof Spanned) {
40            if (source instanceof SpannableStringInternal) {
41                copySpans((SpannableStringInternal) source, start, end);
42            } else {
43                copySpans((Spanned) source, start, end);
44            }
45        }
46    }
47
48    /**
49     * Copies another {@link Spanned} object's spans between [start, end] into this object.
50     *
51     * @param src Source object to copy from.
52     * @param start Start index in the source object.
53     * @param end End index in the source object.
54     */
55    private final void copySpans(Spanned src, int start, int end) {
56        Object[] spans = src.getSpans(start, end, Object.class);
57
58        for (int i = 0; i < spans.length; i++) {
59            int st = src.getSpanStart(spans[i]);
60            int en = src.getSpanEnd(spans[i]);
61            int fl = src.getSpanFlags(spans[i]);
62
63            if (st < start)
64                st = start;
65            if (en > end)
66                en = end;
67
68            setSpan(spans[i], st - start, en - start, fl);
69        }
70    }
71
72    /**
73     * Copies a {@link SpannableStringInternal} object's spans between [start, end] into this
74     * object.
75     *
76     * @param src Source object to copy from.
77     * @param start Start index in the source object.
78     * @param end End index in the source object.
79     */
80    private final void copySpans(SpannableStringInternal src, int start, int end) {
81        if (start == 0 && end == src.length()) {
82            mSpans = ArrayUtils.newUnpaddedObjectArray(src.mSpans.length);
83            mSpanData = new int[src.mSpanData.length];
84            mSpanCount = src.mSpanCount;
85            System.arraycopy(src.mSpans, 0, mSpans, 0, src.mSpans.length);
86            System.arraycopy(src.mSpanData, 0, mSpanData, 0, mSpanData.length);
87        } else {
88            int count = 0;
89            int[] srcData = src.mSpanData;
90            int limit = src.mSpanCount;
91            for (int i = 0; i < limit; i++) {
92                int spanStart = srcData[i * COLUMNS + START];
93                int spanEnd = srcData[i * COLUMNS + END];
94                if (isOutOfCopyRange(start, end, spanStart, spanEnd)) continue;
95                count++;
96            }
97
98            if (count == 0) return;
99
100            Object[] srcSpans = src.mSpans;
101            mSpanCount = count;
102            mSpans = ArrayUtils.newUnpaddedObjectArray(mSpanCount);
103            mSpanData = new int[mSpans.length * COLUMNS];
104            for (int i = 0, j = 0; i < limit; i++) {
105                int spanStart = srcData[i * COLUMNS + START];
106                int spanEnd = srcData[i * COLUMNS + END];
107                if (isOutOfCopyRange(start, end, spanStart, spanEnd)) continue;
108                if (spanStart < start) spanStart = start;
109                if (spanEnd > end) spanEnd = end;
110
111                mSpans[j] = srcSpans[i];
112                mSpanData[j * COLUMNS + START] = spanStart - start;
113                mSpanData[j * COLUMNS + END] = spanEnd - start;
114                mSpanData[j * COLUMNS + FLAGS] = srcData[i * COLUMNS + FLAGS];
115                j++;
116            }
117        }
118    }
119
120    /**
121     * Checks if [spanStart, spanEnd] interval is excluded from [start, end].
122     *
123     * @return True if excluded, false if included.
124     */
125    private final boolean isOutOfCopyRange(int start, int end, int spanStart, int spanEnd) {
126        if (spanStart > end || spanEnd < start) return true;
127        if (spanStart != spanEnd && start != end) {
128            if (spanStart == end || spanEnd == start) return true;
129        }
130        return false;
131    }
132
133    public final int length() {
134        return mText.length();
135    }
136
137    public final char charAt(int i) {
138        return mText.charAt(i);
139    }
140
141    public final String toString() {
142        return mText;
143    }
144
145    /* subclasses must do subSequence() to preserve type */
146
147    public final void getChars(int start, int end, char[] dest, int off) {
148        mText.getChars(start, end, dest, off);
149    }
150
151    /* package */ void setSpan(Object what, int start, int end, int flags) {
152        int nstart = start;
153        int nend = end;
154
155        checkRange("setSpan", start, end);
156
157        if ((flags & Spannable.SPAN_PARAGRAPH) == Spannable.SPAN_PARAGRAPH) {
158            if (start != 0 && start != length()) {
159                char c = charAt(start - 1);
160
161                if (c != '\n')
162                    throw new RuntimeException(
163                            "PARAGRAPH span must start at paragraph boundary" +
164                            " (" + start + " follows " + c + ")");
165            }
166
167            if (end != 0 && end != length()) {
168                char c = charAt(end - 1);
169
170                if (c != '\n')
171                    throw new RuntimeException(
172                            "PARAGRAPH span must end at paragraph boundary" +
173                            " (" + end + " follows " + c + ")");
174            }
175        }
176
177        int count = mSpanCount;
178        Object[] spans = mSpans;
179        int[] data = mSpanData;
180
181        for (int i = 0; i < count; i++) {
182            if (spans[i] == what) {
183                int ostart = data[i * COLUMNS + START];
184                int oend = data[i * COLUMNS + END];
185
186                data[i * COLUMNS + START] = start;
187                data[i * COLUMNS + END] = end;
188                data[i * COLUMNS + FLAGS] = flags;
189
190                sendSpanChanged(what, ostart, oend, nstart, nend);
191                return;
192            }
193        }
194
195        if (mSpanCount + 1 >= mSpans.length) {
196            Object[] newtags = ArrayUtils.newUnpaddedObjectArray(
197                    GrowingArrayUtils.growSize(mSpanCount));
198            int[] newdata = new int[newtags.length * 3];
199
200            System.arraycopy(mSpans, 0, newtags, 0, mSpanCount);
201            System.arraycopy(mSpanData, 0, newdata, 0, mSpanCount * 3);
202
203            mSpans = newtags;
204            mSpanData = newdata;
205        }
206
207        mSpans[mSpanCount] = what;
208        mSpanData[mSpanCount * COLUMNS + START] = start;
209        mSpanData[mSpanCount * COLUMNS + END] = end;
210        mSpanData[mSpanCount * COLUMNS + FLAGS] = flags;
211        mSpanCount++;
212
213        if (this instanceof Spannable)
214            sendSpanAdded(what, nstart, nend);
215    }
216
217    /* package */ void removeSpan(Object what) {
218        int count = mSpanCount;
219        Object[] spans = mSpans;
220        int[] data = mSpanData;
221
222        for (int i = count - 1; i >= 0; i--) {
223            if (spans[i] == what) {
224                int ostart = data[i * COLUMNS + START];
225                int oend = data[i * COLUMNS + END];
226
227                int c = count - (i + 1);
228
229                System.arraycopy(spans, i + 1, spans, i, c);
230                System.arraycopy(data, (i + 1) * COLUMNS,
231                                 data, i * COLUMNS, c * COLUMNS);
232
233                mSpanCount--;
234
235                sendSpanRemoved(what, ostart, oend);
236                return;
237            }
238        }
239    }
240
241    public int getSpanStart(Object what) {
242        int count = mSpanCount;
243        Object[] spans = mSpans;
244        int[] data = mSpanData;
245
246        for (int i = count - 1; i >= 0; i--) {
247            if (spans[i] == what) {
248                return data[i * COLUMNS + START];
249            }
250        }
251
252        return -1;
253    }
254
255    public int getSpanEnd(Object what) {
256        int count = mSpanCount;
257        Object[] spans = mSpans;
258        int[] data = mSpanData;
259
260        for (int i = count - 1; i >= 0; i--) {
261            if (spans[i] == what) {
262                return data[i * COLUMNS + END];
263            }
264        }
265
266        return -1;
267    }
268
269    public int getSpanFlags(Object what) {
270        int count = mSpanCount;
271        Object[] spans = mSpans;
272        int[] data = mSpanData;
273
274        for (int i = count - 1; i >= 0; i--) {
275            if (spans[i] == what) {
276                return data[i * COLUMNS + FLAGS];
277            }
278        }
279
280        return 0;
281    }
282
283    public <T> T[] getSpans(int queryStart, int queryEnd, Class<T> kind) {
284        int count = 0;
285
286        int spanCount = mSpanCount;
287        Object[] spans = mSpans;
288        int[] data = mSpanData;
289        Object[] ret = null;
290        Object ret1 = null;
291
292        for (int i = 0; i < spanCount; i++) {
293            int spanStart = data[i * COLUMNS + START];
294            int spanEnd = data[i * COLUMNS + END];
295
296            if (spanStart > queryEnd) {
297                continue;
298            }
299            if (spanEnd < queryStart) {
300                continue;
301            }
302
303            if (spanStart != spanEnd && queryStart != queryEnd) {
304                if (spanStart == queryEnd) {
305                    continue;
306                }
307                if (spanEnd == queryStart) {
308                    continue;
309                }
310            }
311
312            // verify span class as late as possible, since it is expensive
313            if (kind != null && kind != Object.class && !kind.isInstance(spans[i])) {
314                continue;
315            }
316
317            if (count == 0) {
318                ret1 = spans[i];
319                count++;
320            } else {
321                if (count == 1) {
322                    ret = (Object[]) Array.newInstance(kind, spanCount - i + 1);
323                    ret[0] = ret1;
324                }
325
326                int prio = data[i * COLUMNS + FLAGS] & Spanned.SPAN_PRIORITY;
327                if (prio != 0) {
328                    int j;
329
330                    for (j = 0; j < count; j++) {
331                        int p = getSpanFlags(ret[j]) & Spanned.SPAN_PRIORITY;
332
333                        if (prio > p) {
334                            break;
335                        }
336                    }
337
338                    System.arraycopy(ret, j, ret, j + 1, count - j);
339                    ret[j] = spans[i];
340                    count++;
341                } else {
342                    ret[count++] = spans[i];
343                }
344            }
345        }
346
347        if (count == 0) {
348            return (T[]) ArrayUtils.emptyArray(kind);
349        }
350        if (count == 1) {
351            ret = (Object[]) Array.newInstance(kind, 1);
352            ret[0] = ret1;
353            return (T[]) ret;
354        }
355        if (count == ret.length) {
356            return (T[]) ret;
357        }
358
359        Object[] nret = (Object[]) Array.newInstance(kind, count);
360        System.arraycopy(ret, 0, nret, 0, count);
361        return (T[]) nret;
362    }
363
364    public int nextSpanTransition(int start, int limit, Class kind) {
365        int count = mSpanCount;
366        Object[] spans = mSpans;
367        int[] data = mSpanData;
368
369        if (kind == null) {
370            kind = Object.class;
371        }
372
373        for (int i = 0; i < count; i++) {
374            int st = data[i * COLUMNS + START];
375            int en = data[i * COLUMNS + END];
376
377            if (st > start && st < limit && kind.isInstance(spans[i]))
378                limit = st;
379            if (en > start && en < limit && kind.isInstance(spans[i]))
380                limit = en;
381        }
382
383        return limit;
384    }
385
386    private void sendSpanAdded(Object what, int start, int end) {
387        SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
388        int n = recip.length;
389
390        for (int i = 0; i < n; i++) {
391            recip[i].onSpanAdded((Spannable) this, what, start, end);
392        }
393    }
394
395    private void sendSpanRemoved(Object what, int start, int end) {
396        SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
397        int n = recip.length;
398
399        for (int i = 0; i < n; i++) {
400            recip[i].onSpanRemoved((Spannable) this, what, start, end);
401        }
402    }
403
404    private void sendSpanChanged(Object what, int s, int e, int st, int en) {
405        SpanWatcher[] recip = getSpans(Math.min(s, st), Math.max(e, en),
406                                       SpanWatcher.class);
407        int n = recip.length;
408
409        for (int i = 0; i < n; i++) {
410            recip[i].onSpanChanged((Spannable) this, what, s, e, st, en);
411        }
412    }
413
414    private static String region(int start, int end) {
415        return "(" + start + " ... " + end + ")";
416    }
417
418    private void checkRange(final String operation, int start, int end) {
419        if (end < start) {
420            throw new IndexOutOfBoundsException(operation + " " +
421                                                region(start, end) +
422                                                " has end before start");
423        }
424
425        int len = length();
426
427        if (start > len || end > len) {
428            throw new IndexOutOfBoundsException(operation + " " +
429                                                region(start, end) +
430                                                " ends beyond length " + len);
431        }
432
433        if (start < 0 || end < 0) {
434            throw new IndexOutOfBoundsException(operation + " " +
435                                                region(start, end) +
436                                                " starts before 0");
437        }
438    }
439
440    // Same as SpannableStringBuilder
441    @Override
442    public boolean equals(Object o) {
443        if (o instanceof Spanned &&
444                toString().equals(o.toString())) {
445            Spanned other = (Spanned) o;
446            // Check span data
447            Object[] otherSpans = other.getSpans(0, other.length(), Object.class);
448            if (mSpanCount == otherSpans.length) {
449                for (int i = 0; i < mSpanCount; ++i) {
450                    Object thisSpan = mSpans[i];
451                    Object otherSpan = otherSpans[i];
452                    if (thisSpan == this) {
453                        if (other != otherSpan ||
454                                getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
455                                getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
456                                getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
457                            return false;
458                        }
459                    } else if (!thisSpan.equals(otherSpan) ||
460                            getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
461                            getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
462                            getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
463                        return false;
464                    }
465                }
466                return true;
467            }
468        }
469        return false;
470    }
471
472    // Same as SpannableStringBuilder
473    @Override
474    public int hashCode() {
475        int hash = toString().hashCode();
476        hash = hash * 31 + mSpanCount;
477        for (int i = 0; i < mSpanCount; ++i) {
478            Object span = mSpans[i];
479            if (span != this) {
480                hash = hash * 31 + span.hashCode();
481            }
482            hash = hash * 31 + getSpanStart(span);
483            hash = hash * 31 + getSpanEnd(span);
484            hash = hash * 31 + getSpanFlags(span);
485        }
486        return hash;
487    }
488
489    private String mText;
490    private Object[] mSpans;
491    private int[] mSpanData;
492    private int mSpanCount;
493
494    /* package */ static final Object[] EMPTY = new Object[0];
495
496    private static final int START = 0;
497    private static final int END = 1;
498    private static final int FLAGS = 2;
499    private static final int COLUMNS = 3;
500}
501