org.ahmadsoft.ropes
Interface Rope

All Superinterfaces:
java.lang.CharSequence, java.lang.Comparable<java.lang.CharSequence>, java.lang.Iterable<java.lang.Character>, java.io.Serializable
All Known Implementing Classes:
AbstractRope, ConcatenationRope, FlatCharArrayRope, FlatCharSequenceRope, ReverseRope, SubstringRope

public interface Rope
extends java.lang.CharSequence, java.lang.Iterable<java.lang.Character>, java.lang.Comparable<java.lang.CharSequence>, java.io.Serializable

A rope represents character strings. Ropes are immutable which means that once they are created, they cannot be changed. This makes them suitable for sharing in multi-threaded environments.

Rope operations, unlike string operations, scale well to very long character strings. Most mutation operations run in O(log n) time or better. However, random-access character retrieval is generally slower than for a String. By traversing consecutive characters with an iterator instead, performance improves to O(1).

This rope implementation implements all performance optimizations outlined in "Ropes: an Alternative to Strings" by Hans-J. Boehm, Russ Atkinson and Michael Plass, including, notably, deferred evaluation of long substrings and automatic rebalancing.

Immutability (a Caveat)

A rope is immutable. Specifically, calling any mutator function on a rope always returns a modified copy; the original rope is left untouched. However, care must be taken to build ropes from immutable CharSequences such as Strings, or else from mutable CharSequences that your program guarantees will not change. Failure to do so will result in logic errors.

Author:
Amin Ahmad

Field Summary
static RopeBuilder BUILDER
          A factory used for constructing ropes.
 
Method Summary
 Rope append(char c)
          Returns a new rope created by appending the specified character to this rope.
 Rope append(java.lang.CharSequence suffix)
          Returns a new rope created by appending the specified character sequence to this rope.
 Rope append(java.lang.CharSequence csq, int start, int end)
          Returns a new rope created by appending the specified character range to this rope.
 Rope delete(int start, int end)
          Creats a new rope by delete the specified character substring.
 boolean endsWith(java.lang.CharSequence suffix)
          Returns true if this rope ends with the specified suffix.
 boolean endsWith(java.lang.CharSequence suffix, int offset)
          Returns true if this rope, terminated at a specified offset, ends with the specified suffix.
 int indexOf(char ch)
          Returns the index within this rope of the first occurrence of the specified character.
 int indexOf(char ch, int fromIndex)
          Returns the index within this rope of the first occurrence of the specified character, beginning at the specified index.
 int indexOf(java.lang.CharSequence sequence)
          Returns the index within this rope of the first occurrence of the specified string.
 int indexOf(java.lang.CharSequence sequence, int fromIndex)
          Returns the index within this rope of the first occurrence of the specified string, beginning at the specified index.
 Rope insert(int dstOffset, java.lang.CharSequence s)
          Creates a new rope by inserting the specified CharSequence into this rope.
 boolean isEmpty()
          Returns true if and only if the length of this rope is zero.
 java.util.Iterator<java.lang.Character> iterator(int start)
          Returns an iterator positioned to start at the specified index.
 java.util.regex.Matcher matcher(java.util.regex.Pattern pattern)
          Creates a matcher that will match this rope against the specified pattern.
 boolean matches(java.util.regex.Pattern regex)
          Returns true if this rope matches the specified Pattern, or false otherwise.
 boolean matches(java.lang.String regex)
          Returns true if this rope matches the specified regular expression, or false otherwise.
 Rope padEnd(int toLength)
          Increase the length of this rope to the specified length by appending spaces to this rope.
 Rope padEnd(int toLength, char padChar)
          Increase the length of this rope to the specified length by repeatedly appending the specified character to this rope.
 Rope padStart(int toLength)
          Increase the length of this rope to the specified length by prepending spaces to this rope.
 Rope padStart(int toLength, char padChar)
          Increase the length of this rope to the specified length by repeatedly prepending the specified character to this rope.
 Rope rebalance()
          Rebalances the current rope, returning the rebalanced rope.
 Rope reverse()
          Reverses this rope.
 java.util.Iterator<java.lang.Character> reverseIterator()
          Returns a reverse iterator positioned to start at the end of this rope.
 java.util.Iterator<java.lang.Character> reverseIterator(int start)
          Returns a reverse iterator positioned to start at the specified index.
 boolean startsWith(java.lang.CharSequence prefix)
          Returns true if this rope starts with the specified prefix.
 boolean startsWith(java.lang.CharSequence prefix, int offset)
          Returns true if this rope, beginning from a specified offset, starts with the specified prefix.
 Rope subSequence(int start, int end)
           
 Rope trim()
          Trims all whitespace as well as characters less than 0x20 from the beginning and end of this string.
 Rope trimEnd()
          Trims all whitespace as well as characters less than 0x20 from the end of this rope.
 Rope trimStart()
          Trims all whitespace as well as characters less than 0x20 from the beginning of this string.
 void write(java.io.Writer out)
          Write this rope to a Writer.
 void write(java.io.Writer out, int offset, int length)
          Write a range of this rope to a Writer.
 
Methods inherited from interface java.lang.CharSequence
charAt, length, toString
 
Methods inherited from interface java.lang.Iterable
iterator
 
Methods inherited from interface java.lang.Comparable
compareTo
 

Field Detail

BUILDER

static final RopeBuilder BUILDER
A factory used for constructing ropes.

Method Detail

append

Rope append(char c)
Returns a new rope created by appending the specified character to this rope.

Parameters:
c - the specified character.
Returns:
a new rope.

append

Rope append(java.lang.CharSequence suffix)
Returns a new rope created by appending the specified character sequence to this rope.

Parameters:
suffix - the specified suffix.
Returns:
a new rope.

append

Rope append(java.lang.CharSequence csq,
            int start,
            int end)
Returns a new rope created by appending the specified character range to this rope.

Parameters:
csq - the specified character.
start - the start index, inclusive.
end - the end index, non-inclusive.
Returns:
a new rope.

delete

Rope delete(int start,
            int end)
Creats a new rope by delete the specified character substring. The substring begins at the specified start and extends to the character at index end - 1 or to the end of the sequence if no such character exists. If start is equal to end, no changes are made.

Parameters:
start - The beginning index, inclusive.
end - The ending index, exclusive.
Returns:
This object.
Throws:
java.lang.StringIndexOutOfBoundsException - if start is negative, greater than length(), or greater than end.

indexOf

int indexOf(char ch)
Returns the index within this rope of the first occurrence of the specified character. If a character with value ch occurs in the character sequence represented by this Rope object, then the index of the first such occurrence is returned -- that is, the smallest value k such that:

this.charAt(k) == ch

is true. If no such character occurs in this string, then -1 is returned.

Parameters:
ch - a character.
Returns:
the index of the first occurrence of the character in the character sequence represented by this object, or -1 if the character does not occur.

indexOf

int indexOf(char ch,
            int fromIndex)
Returns the index within this rope of the first occurrence of the specified character, beginning at the specified index. If a character with value ch occurs in the character sequence represented by this Rope object, then the index of the first such occurrence is returned—that is, the smallest value k such that:

this.charAt(k) == ch

is true. If no such character occurs in this string, then -1 is returned.

Parameters:
ch - a character.
fromIndex - the index to start searching from.
Returns:
the index of the first occurrence of the character in the character sequence represented by this object, or -1 if the character does not occur.

indexOf

int indexOf(java.lang.CharSequence sequence)
Returns the index within this rope of the first occurrence of the specified string. The value returned is the smallest k such that:
     this.startsWith(str, k)
 
If no such k exists, then -1 is returned.

Parameters:
sequence - the string to find.
Returns:
the index of the first occurrence of the specified string, or -1 if the specified string does not occur.

indexOf

int indexOf(java.lang.CharSequence sequence,
            int fromIndex)
Returns the index within this rope of the first occurrence of the specified string, beginning at the specified index. The value returned is the smallest k such that:
     k >= fromIndex && this.startsWith(str, k)
 
If no such k exists, then -1 is returned.

Parameters:
sequence - the string to find.
fromIndex - the index to start searching from.
Returns:
the index of the first occurrence of the specified string, or -1 if the specified string does not occur.

insert

Rope insert(int dstOffset,
            java.lang.CharSequence s)
Creates a new rope by inserting the specified CharSequence into this rope.

The characters of the CharSequence argument are inserted, in order, into this rope at the indicated offset.

If s is null, then the four characters "null" are inserted into this sequence.

Parameters:
dstOffset - the offset.
s - the sequence to be inserted
Returns:
a reference to the new Rope.
Throws:
java.lang.IndexOutOfBoundsException - if the offset is invalid.

iterator

java.util.Iterator<java.lang.Character> iterator(int start)
Returns an iterator positioned to start at the specified index.

Parameters:
start - the start position.
Returns:
an iterator positioned to start at the specified index.

trimStart

Rope trimStart()
Trims all whitespace as well as characters less than 0x20 from the beginning of this string.

Returns:
a rope with all leading whitespace trimmed.

matcher

java.util.regex.Matcher matcher(java.util.regex.Pattern pattern)
Creates a matcher that will match this rope against the specified pattern. This method produces a higher performance matcher than:
 Matcher m = pattern.matcher(this);
 
The difference may be asymptotically better in some cases.

Parameters:
pattern - the pattern to match this rope against.
Returns:
a matcher.

matches

boolean matches(java.util.regex.Pattern regex)
Returns true if this rope matches the specified Pattern, or false otherwise.

Parameters:
regex - the specified regular expression.
Returns:
true if this rope matches the specified Pattern, or false otherwise.
See Also:
Pattern

matches

boolean matches(java.lang.String regex)
Returns true if this rope matches the specified regular expression, or false otherwise.

Parameters:
regex - the specified regular expression.
Returns:
true if this rope matches the specified regular expression, or false otherwise.
See Also:
Pattern

rebalance

Rope rebalance()
Rebalances the current rope, returning the rebalanced rope. In general, rope rebalancing is handled automatically, but this method is provided to give users more control.

Returns:
a rebalanced rope.

reverse

Rope reverse()
Reverses this rope.

Returns:
a reversed copy of this rope.

reverseIterator

java.util.Iterator<java.lang.Character> reverseIterator()
Returns a reverse iterator positioned to start at the end of this rope. A reverse iterator moves backwards instead of forwards through a rope.

Returns:
A reverse iterator positioned at the end of this rope.
See Also:
reverseIterator(int)

reverseIterator

java.util.Iterator<java.lang.Character> reverseIterator(int start)
Returns a reverse iterator positioned to start at the specified index. A reverse iterator moves backwards instead of forwards through a rope.

Parameters:
start - the start position.
Returns:
a reverse iterator positioned to start at the specified index from the end of the rope. For example, a value of 1 indicates the iterator should start 1 character before the end of the rope.
See Also:
reverseIterator()

trimEnd

Rope trimEnd()
Trims all whitespace as well as characters less than 0x20 from the end of this rope.

Returns:
a rope with all trailing whitespace trimmed.

subSequence

Rope subSequence(int start,
                 int end)
Specified by:
subSequence in interface java.lang.CharSequence

trim

Rope trim()
Trims all whitespace as well as characters less than 0x20 from the beginning and end of this string.

Returns:
a rope with all leading and trailing whitespace trimmed.

write

void write(java.io.Writer out)
           throws java.io.IOException
Write this rope to a Writer.

Parameters:
out - the writer object.
Throws:
java.io.IOException

write

void write(java.io.Writer out,
           int offset,
           int length)
           throws java.io.IOException
Write a range of this rope to a Writer.

Parameters:
out - the writer object.
offset - the range offset.
length - the range length.
Throws:
java.io.IOException

padStart

Rope padStart(int toLength)
Increase the length of this rope to the specified length by prepending spaces to this rope. If the specified length is less than or equal to the current length of the rope, the rope is returned unmodified.

Parameters:
toLength - the desired length.
Returns:
the padded rope.
See Also:
padStart(int, char)

padStart

Rope padStart(int toLength,
              char padChar)
Increase the length of this rope to the specified length by repeatedly prepending the specified character to this rope. If the specified length is less than or equal to the current length of the rope, the rope is returned unmodified.

Parameters:
toLength - the desired length.
padChar - the character to use for padding.
Returns:
the padded rope.
See Also:
padStart(int, char)

padEnd

Rope padEnd(int toLength)
Increase the length of this rope to the specified length by appending spaces to this rope. If the specified length is less than or equal to the current length of the rope, the rope is returned unmodified.

Parameters:
toLength - the desired length.
Returns:
the padded rope.
See Also:
padStart(int, char)

padEnd

Rope padEnd(int toLength,
            char padChar)
Increase the length of this rope to the specified length by repeatedly appending the specified character to this rope. If the specified length is less than or equal to the current length of the rope, the rope is returned unmodified.

Parameters:
toLength - the desired length.
padChar - the character to use for padding.
Returns:
the padded rope.
See Also:
padStart(int, char)

isEmpty

boolean isEmpty()
Returns true if and only if the length of this rope is zero.

Returns:
true if and only if the length of this rope is zero, and false otherwise.

startsWith

boolean startsWith(java.lang.CharSequence prefix)
Returns true if this rope starts with the specified prefix.

Parameters:
prefix - the prefix to test.
Returns:
true if this rope starts with the specified prefix and false otherwise.
See Also:
startsWith(CharSequence, int)

startsWith

boolean startsWith(java.lang.CharSequence prefix,
                   int offset)
Returns true if this rope, beginning from a specified offset, starts with the specified prefix.

Parameters:
prefix - the prefix to test.
offset - the start offset.
Returns:
true if this rope starts with the specified prefix and false otherwise.

endsWith

boolean endsWith(java.lang.CharSequence suffix)
Returns true if this rope ends with the specified suffix.

Parameters:
suffix - the suffix to test.
Returns:
true if this rope starts with the specified suffix and false otherwise.
See Also:
endsWith(CharSequence, int)

endsWith

boolean endsWith(java.lang.CharSequence suffix,
                 int offset)
Returns true if this rope, terminated at a specified offset, ends with the specified suffix.

Parameters:
suffix - the suffix to test.
offset - the termination offset, counted from the end of the rope.
Returns:
true if this rope starts with the specified prefix and false otherwise.


Copyright © 2007 Amin Ahmad. All Rights Reserved.