Text.java

Go to the documentation of this file.

/*
 * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
 * Copyright (C) 2012 - Javolution (http://javolution.org/)
 * All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software is
 * freely granted, provided that this notice is preserved.
 */
package javolution.text;
 
import java.io.PrintStream;
 
import javolution.lang.MathLib;
import javolution.lang.Realtime;
import javolution.lang.ValueType;
import javolution.util.FastMap;
import javolution.util.function.Equalities;
import javolution.xml.XMLSerializable;
 
@Realtime
public final class Text implements CharSequence, Comparable<CharSequence>,
        XMLSerializable, ValueType<Text> {
 
    private static final long serialVersionUID = 0x600L; // Version.
 
    private static final int BLOCK_SIZE = 1 << 5;
 
    private static final int BLOCK_MASK = ~(BLOCK_SIZE - 1);
 
    private static final FastMap<Text, Text> INTERN = new FastMap<Text, Text>()
            .shared();
 
    public static final Text EMPTY = new Text("").intern();
 
    private final char[] _data;
 
    private int _count;
 
    private Text _head;
 
    private Text _tail;
 
    private Text(boolean isPrimitive) {
        _data = isPrimitive ? new char[BLOCK_SIZE] : null;
    }
 
    public Text(String str) {
        this(str.length() <= BLOCK_SIZE);
        _count = str.length();
        if (_data != null) { // Primitive.
            str.getChars(0, _count, _data, 0);
        } else { // Composite, splits on a block boundary. 
            int half = ((_count + BLOCK_SIZE) >> 1) & BLOCK_MASK;
            _head = new Text(str.substring(0, half));
            _tail = new Text(str.substring(half, _count));
        }
    }
 
    public static Text valueOf(Object obj) {
        return new TextBuilder().append(obj).toText();
    }
 
    private static Text valueOf(String str) {
        return Text.valueOf(str, 0, str.length());
    }
 
    private static Text valueOf(String str, int start, int end) {
        int length = end - start;
        if (length <= BLOCK_SIZE) {
            Text text = newPrimitive(length);
            str.getChars(start, end, text._data, 0);
            return text;
        } else { // Splits on a block boundary.
            int half = ((length + BLOCK_SIZE) >> 1) & BLOCK_MASK;
            return newComposite(Text.valueOf(str, start, start + half),
                    Text.valueOf(str, start + half, end));
        }
    }
 
    public static Text valueOf(char[] chars) {
        return Text.valueOf(chars, 0, chars.length);
    }
 
    public static Text valueOf(char[] chars, int offset, int length) {
        if ((offset < 0) || (length < 0) || ((offset + length) > chars.length))
            throw new IndexOutOfBoundsException();
        if (length <= BLOCK_SIZE) {
            Text text = Text.newPrimitive(length);
            System.arraycopy(chars, offset, text._data, 0, length);
            return text;
        } else { // Splits on a block boundary.
            int half = ((length + BLOCK_SIZE) >> 1) & BLOCK_MASK;
            return Text.newComposite(Text.valueOf(chars, offset, half),
                    Text.valueOf(chars, offset + half, length - half));
        }
    }
 
    static Text valueOf(TextBuilder tb, int start, int end) {
        int length = end - start;
        if (length <= BLOCK_SIZE) {
            Text text = Text.newPrimitive(length);
            tb.getChars(start, end, text._data, 0);
            return text;
        } else { // Splits on a block boundary.
            int half = ((length + BLOCK_SIZE) >> 1) & BLOCK_MASK;
            return Text.newComposite(Text.valueOf(tb, start, start + half),
                    Text.valueOf(tb, start + half, end));
        }
    }
 
    public static Text valueOf(boolean b) {
        return b ? TRUE : FALSE;
    }
 
    private static final Text TRUE = new Text("true").intern();
 
    private static final Text FALSE = new Text("false").intern();
 
    public static Text valueOf(char c) {
        Text text = Text.newPrimitive(1);
        text._data[0] = c;
        return text;
    }
 
    public static Text valueOf(int i) {
        TextBuilder tb = new TextBuilder();
        return tb.append(i).toText();
    }
 
    public static Text valueOf(int i, int radix) {
        TextBuilder tb = new TextBuilder();
        return tb.append(i, radix).toText();
    }
 
    public static Text valueOf(long l) {
        TextBuilder tb = new TextBuilder();
        return tb.append(l).toText();
    }
 
    public static Text valueOf(long l, int radix) {
        TextBuilder tb = new TextBuilder();
        return tb.append(l, radix).toText();
    }
 
    public static Text valueOf(float f) {
        TextBuilder tb = new TextBuilder();
        return tb.append(f).toText();
    }
 
    public static Text valueOf(double d) {
        TextBuilder tb = new TextBuilder();
        return tb.append(d).toText();
    }
 
    public static Text valueOf(double d, int digits, boolean scientific,
            boolean showZero) {
        TextBuilder tb = new TextBuilder();
        return tb.append(d, digits, scientific, showZero).toText();
    }
 
    public int length() {
        return _count;
    }
 
    public Text plus(Object obj) {
        return this.concat(Text.valueOf(obj));
    }
 
    public Text plus(String str) {
 
        Text merge = this.append(str);
        return merge != null ? merge : concat(Text.valueOf(str));
    }
 
    private Text append(String str) { // Try to append, returns null if cannot.
        int length = str.length();
        if (_data == null) {
            Text merge = _tail.append(str);
            return merge != null ? Text.newComposite(_head, merge) : null;
        } else { // Primitive.
            if (_count + length > BLOCK_SIZE)
                return null; // Cannot merge.
            Text text = Text.newPrimitive(_count + length);
            System.arraycopy(_data, 0, text._data, 0, _count);
            str.getChars(0, length, text._data, _count);
            return text;
        }
    }
 
    public Text concat(Text that) {
        // All Text instances are maintained balanced:
        //   (head < tail * 2) & (tail < head * 2)
 
        final int length = this._count + that._count;
        if (length <= BLOCK_SIZE) { // Merges to primitive.
            Text text = Text.newPrimitive(length);
            this.getChars(0, this._count, text._data, 0);
            that.getChars(0, that._count, text._data, this._count);
            return text;
 
        } else { // Returns a composite.
            Text head = this;
            Text tail = that;
 
            if (((head._count << 1) < tail._count) && (tail._data == null)) { // tail is composite
                // head too small, returns (head + tail/2) + (tail/2) 
                if (tail._head._count > tail._tail._count) {
                    // Rotates to concatenate with smaller part.
                    tail = tail.rightRotation();
                }
                head = head.concat(tail._head);
                tail = tail._tail;
 
            } else if (((tail._count << 1) < head._count)
                    && (head._data == null)) { // head is composite.
                // tail too small, returns (head/2) + (head/2 concat tail)
                if (head._tail._count > head._head._count) {
                    // Rotates to concatenate with smaller part.
                    head = head.leftRotation();
                }
                tail = head._tail.concat(tail);
                head = head._head;
            }
            return Text.newComposite(head, tail);
        }
    }
 
    private Text rightRotation() {
        // See: http://en.wikipedia.org/wiki/Tree_rotation
        Text P = this._head;
        if (P._data != null)
            return this; // Head not a composite, cannot rotate.
        Text A = P._head;
        Text B = P._tail;
        Text C = this._tail;
        return Text.newComposite(A, Text.newComposite(B, C));
    }
 
    private Text leftRotation() {
        // See: http://en.wikipedia.org/wiki/Tree_rotation
        Text Q = this._tail;
        if (Q._data != null)
            return this; // Tail not a composite, cannot rotate.
        Text B = Q._head;
        Text C = Q._tail;
        Text A = this._head;
        return Text.newComposite(Text.newComposite(A, B), C);
    }
 
    public Text subtext(int start) {
        return subtext(start, length());
    }
 
    public Text insert(int index, Text txt) {
        return subtext(0, index).concat(txt).concat(subtext(index));
    }
 
    public Text delete(int start, int end) {
        if (start > end)
            throw new IndexOutOfBoundsException();
        return subtext(0, start).concat(subtext(end));
    }
 
    public Text replace(java.lang.CharSequence target,
            java.lang.CharSequence replacement) {
        int i = indexOf(target);
        return (i < 0) ? this : // No target sequence found.
                subtext(0, i).concat(Text.valueOf(replacement)).concat(
                        subtext(i + target.length()).replace(target,
                                replacement));
    }
 
    public Text replace(CharSet charSet, java.lang.CharSequence replacement) {
        int i = indexOfAny(charSet);
        return (i < 0) ? this : // No character to replace.
                subtext(0, i).concat(Text.valueOf(replacement)).concat(
                        subtext(i + 1).replace(charSet, replacement));
    }
 
    public java.lang.CharSequence subSequence(int start, int end) {
        return subtext(start, end);
    }
 
    public int indexOf(java.lang.CharSequence csq) {
        return indexOf(csq, 0);
    }
 
    public int indexOf(java.lang.CharSequence csq, int fromIndex) {
 
        // Limit cases.
        final int csqLength = csq.length();
        final int min = Math.max(0, fromIndex);
        final int max = _count - csqLength;
        if (csqLength == 0) { return (min > max) ? -1 : min; }
 
        // Searches for csq.
        final char c = csq.charAt(0);
        for (int i = indexOf(c, min); (i >= 0) && (i <= max); i = indexOf(c,
                ++i)) {
            boolean match = true;
            for (int j = 1; j < csqLength; j++) {
                if (this.charAt(i + j) != csq.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) { return i; }
        }
        return -1;
    }
 
    public int lastIndexOf(java.lang.CharSequence csq) {
        return lastIndexOf(csq, _count);
    }
 
    public int lastIndexOf(java.lang.CharSequence csq, int fromIndex) {
 
        // Limit cases.
        final int csqLength = csq.length();
        final int min = 0;
        final int max = Math.min(fromIndex, _count - csqLength);
        if (csqLength == 0) { return (min > max) ? -1 : max; }
 
        // Searches for csq.
        final char c = csq.charAt(0);
        for (int i = lastIndexOf(c, max); (i >= 0); i = lastIndexOf(c, --i)) {
            boolean match = true;
            for (int j = 1; j < csqLength; j++) {
                if (this.charAt(i + j) != csq.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) { return i; }
        }
        return -1;
 
    }
 
    public boolean startsWith(java.lang.CharSequence prefix) {
        return startsWith(prefix, 0);
    }
 
    public boolean endsWith(java.lang.CharSequence suffix) {
        return startsWith(suffix, length() - suffix.length());
    }
 
    public boolean startsWith(java.lang.CharSequence prefix, int index) {
        final int prefixLength = prefix.length();
        if ((index >= 0) && (index <= (this.length() - prefixLength))) {
            for (int i = 0, j = index; i < prefixLength;) {
                if (prefix.charAt(i++) != this.charAt(j++)) { return false; }
            }
            return true;
        } else {
            return false;
        }
    }
 
    public Text trim() {
        int first = 0; // First character index.
        int last = length() - 1; // Last character index.
        while ((first <= last) && (charAt(first) <= ' ')) {
            first++;
        }
        while ((last >= first) && (charAt(last) <= ' ')) {
            last--;
        }
        return subtext(first, last + 1);
    }
 
    public Text intern() {
        Text txt = INTERN.putIfAbsent(this, this);
        return txt == null ? this : txt;
    }
 
    public boolean contentEquals(java.lang.CharSequence csq) {
        if (csq.length() != _count)
            return false;
        for (int i = 0; i < _count;) {
            if (this.charAt(i) != csq.charAt(i++))
                return false;
        }
        return true;
    }
 
    public boolean contentEqualsIgnoreCase(java.lang.CharSequence csq) {
        if (this._count != csq.length())
            return false;
        for (int i = 0; i < _count;) {
            char u1 = this.charAt(i);
            char u2 = csq.charAt(i++);
            if (u1 != u2) {
                u1 = Character.toUpperCase(u1);
                u2 = Character.toUpperCase(u2);
                if ((u1 != u2)
                        && (Character.toLowerCase(u1) != Character
                                .toLowerCase(u2)))
                    return false;
 
            }
        }
        return true;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof Text))
            return false;
        final Text that = (Text) obj;
        if (this._count != that._count)
            return false;
        for (int i = 0; i < _count;) {
            if (this.charAt(i) != that.charAt(i++))
                return false;
        }
        return true;
    }
 
    @Override
    public int hashCode() {
        int h = 0;
        final int length = this.length();
        for (int i = 0; i < length;) {
            h = 31 * h + charAt(i++);
        }
        return h;
    }
 
    public int compareTo(CharSequence csq) {
        return Equalities.LEXICAL.compare(this, csq);
    }
 
    public Text toText() {
        return this;
    }
 
    public void printStatistics(PrintStream out) {
        int length = this.length();
        int leaves = getNbrOfLeaves();
        synchronized (out) {
            out.print("LENGTH: " + length());
            out.print(", MAX DEPTH: " + getDepth());
            out.print(", NBR OF BRANCHES: " + getNbrOfBranches());
            out.print(", NBR OF LEAVES: " + leaves);
            out.print(", AVG LEAVE LENGTH: " + (length + (leaves >> 1))
                    / leaves);
            out.println();
        }
    }
 
    private int getDepth() {
        if (_data != null) // Primitive.
            return 0;
        return MathLib.max(_head.getDepth(), _tail.getDepth()) + 1;
    }
 
    private int getNbrOfBranches() {
        return (_data == null) ? _head.getNbrOfBranches()
                + _tail.getNbrOfBranches() + 1 : 0;
    }
 
    private int getNbrOfLeaves() {
        return (_data == null) ? _head.getNbrOfLeaves()
                + _tail.getNbrOfLeaves() : 1;
    }
 
    public Text toLowerCase() {
        if (_data == null) // Composite.
            return Text.newComposite(_head.toLowerCase(), _tail.toLowerCase());
        Text text = Text.newPrimitive(_count);
        for (int i = 0; i < _count;) {
            text._data[i] = Character.toLowerCase(_data[i++]);
        }
        return text;
    }
 
    public Text toUpperCase() {
        if (_data == null) // Composite.
            return newComposite(_head.toUpperCase(), _tail.toUpperCase());
        Text text = Text.newPrimitive(_count);
        for (int i = 0; i < _count;) {
            text._data[i] = Character.toUpperCase(_data[i++]);
        }
        return text;
    }
 
    public char charAt(int index) {
        if (index >= _count)
            throw new IndexOutOfBoundsException();
        return (_data != null) ? _data[index] : (index < _head._count) ? _head
                .charAt(index) : _tail.charAt(index - _head._count);
    }
 
    public int indexOf(char c) {
        return indexOf(c, 0);
    }
 
    public int indexOf(char c, int fromIndex) {
        if (_data != null) { // Primitive.
            for (int i = MathLib.max(fromIndex, 0); i < _count; i++) {
                if (_data[i] == c)
                    return i;
            }
            return -1;
        } else { // Composite.
            final int cesure = _head._count;
            if (fromIndex < cesure) {
                final int headIndex = _head.indexOf(c, fromIndex);
                if (headIndex >= 0)
                    return headIndex; // Found in head.
            }
            final int tailIndex = _tail.indexOf(c, fromIndex - cesure);
            return (tailIndex >= 0) ? tailIndex + cesure : -1;
        }
    }
 
    public int lastIndexOf(char c, int fromIndex) {
        if (_data != null) { // Primitive.
            for (int i = MathLib.min(fromIndex, _count - 1); i >= 0; i--) {
                if (_data[i] == c)
                    return i;
            }
            return -1;
        } else { // Composite.
            final int cesure = _head._count;
            if (fromIndex >= cesure) {
                final int tailIndex = _tail.lastIndexOf(c, fromIndex - cesure);
                if (tailIndex >= 0)
                    return tailIndex + cesure; // Found in tail.
            }
            return _head.lastIndexOf(c, fromIndex);
        }
    }
 
    public Text subtext(int start, int end) {
        if (_data != null) { // Primitive.
            if ((start < 0) || (start > end) || (end > _count))
                throw new IndexOutOfBoundsException();
            if ((start == 0) && (end == _count))
                return this;
            if (start == end)
                return Text.EMPTY;
            int length = end - start;
            Text text = Text.newPrimitive(length);
            System.arraycopy(_data, start, text._data, 0, length);
            return text;
        } else { // Composite.
            final int cesure = _head._count;
            if (end <= cesure)
                return _head.subtext(start, end);
            if (start >= cesure)
                return _tail.subtext(start - cesure, end - cesure);
            if ((start == 0) && (end == _count))
                return this;
            // Overlaps head and tail.
            return _head.subtext(start, cesure).concat(
                    _tail.subtext(0, end - cesure));
        }
    }
 
    public void getChars(int start, int end, char dest[], int destPos) {
        if (_data != null) { // Primitive.
            if ((start < 0) || (end > _count) || (start > end))
                throw new IndexOutOfBoundsException();
            System.arraycopy(_data, start, dest, destPos, end - start);
        } else { // Composite.
            final int cesure = _head._count;
            if (end <= cesure) {
                _head.getChars(start, end, dest, destPos);
            } else if (start >= cesure) {
                _tail.getChars(start - cesure, end - cesure, dest, destPos);
            } else { // Overlaps head and tail.
                _head.getChars(start, cesure, dest, destPos);
                _tail.getChars(0, end - cesure, dest, destPos + cesure - start);
            }
        }
    }
 
    public String toString() {
        if (_data != null) { // Primitive.
            return new String(_data, 0, _count);
        } else { // Composite.
            char[] data = new char[_count];
            this.getChars(0, _count, data, 0);
            return new String(data, 0, _count);
        }
    }
 
    // Implements ValueType interface.
    public Text copy() {
        if (_data != null) { // Primitive.
            Text text = Text.newPrimitive(_count);
            System.arraycopy(_data, 0, text._data, 0, _count);
            return text;
        } else { // Composite.
            return Text.newComposite((Text) _head.copy(), (Text) _tail.copy());
        }
    }
 
    // Wilfried add-ons (methods provided by Microsoft .Net in C#)
    //
    public static Text valueOf(char c, int length) {
        if (length < 0)
            throw new IndexOutOfBoundsException();
        if (length <= BLOCK_SIZE) {
            Text text = Text.newPrimitive(length);
            for (int i = 0; i < length;) {
                text._data[i++] = c;
            }
            return text;
        } else {
            final int middle = (length >> 1);
            return Text.newComposite(Text.valueOf(c, middle),
                    Text.valueOf(c, length - middle));
        }
    }
 
    public boolean isBlank() {
        return isBlank(0, length());
    }
 
    public boolean isBlank(int start, int length) {
        for (; start < length; start++) {
            if (charAt(start) > ' ')
                return false;
        }
        return true;
    }
 
    public Text trimStart() {
        int first = 0; // First character index.
        int last = length() - 1; // Last character index.
        while ((first <= last) && (charAt(first) <= ' ')) {
            first++;
        }
        return subtext(first, last + 1);
    }
 
    public Text trimEnd() {
        int first = 0; // First character index.
        int last = length() - 1; // Last character index.
        while ((last >= first) && (charAt(last) <= ' ')) {
            last--;
        }
        return subtext(first, last + 1);
    }
 
    public Text padLeft(int len) {
        return padLeft(len, ' ');
    }
 
    public Text padLeft(int len, char c) {
        final int padSize = (len <= length()) ? 0 : len - length();
        return insert(0, Text.valueOf(c, padSize));
    }
 
    public Text padRight(int len) {
        return padRight(len, ' ');
    }
 
    public Text padRight(int len, char c) {
        final int padSize = (len <= length()) ? 0 : len - length();
        return concat(Text.valueOf(c, padSize));
    }
 
    public int indexOfAny(CharSet charSet) {
        return indexOfAny(charSet, 0, length());
    }
 
    public int indexOfAny(CharSet charSet, int start) {
        return indexOfAny(charSet, start, length() - start);
    }
 
    public int indexOfAny(CharSet charSet, int start, int length) {
        final int stop = start + length;
        for (int i = start; i < stop; i++) {
            if (charSet.contains(charAt(i)))
                return i;
        }
        return -1;
    }
 
    public int lastIndexOfAny(CharSet charSet) {
        return lastIndexOfAny(charSet, 0, length());
    }
 
    public int lastIndexOfAny(CharSet charSet, int start) {
        return lastIndexOfAny(charSet, start, length() - start);
    }
 
    public int lastIndexOfAny(CharSet charSet, int start, int length) {
        for (int i = start + length; --i >= start;) {
            if (charSet.contains(charAt(i)))
                return i;
        }
        return -1;
    }
 
    //
 
    private static Text newPrimitive(int length) {
        Text text = new Text(true);
        text._count = length;
        return text;
    }
 
    private static Text newComposite(Text head, Text tail) {
        Text text = new Text(false);
        text._count = head._count + tail._count;
        text._head = head;
        text._tail = tail;
        return text;
    }
 
    @Override
    public Text value() {
        return this;
    }
 
}