1/* 2 * Rope.java 3 * Copyright (C) 2007 Amin Ahmad. 4 * 5 * This file is part of Java Ropes. 6 * 7 * Java Ropes is free software: you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation, either version 3 of the License, or 10 * (at your option) any later version. 11 * 12 * Java Ropes is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with Java Ropes. If not, see <http://www.gnu.org/licenses/>. 19 * 20 * Amin Ahmad can be contacted at amin.ahmad@gmail.com or on the web at 21 * www.ahmadsoft.org. 22 */ 23package org.ahmadsoft.ropes; 24 25import java.io.IOException; 26import java.io.Serializable; 27import java.io.Writer; 28import java.util.Iterator; 29import java.util.regex.Matcher; 30import java.util.regex.Pattern; 31 32 33/** 34 * <p> 35 * A rope represents character strings. Ropes are immutable which 36 * means that once they are created, they cannot be changed. This 37 * makes them suitable for sharing in multi-threaded environments. 38 * </p><p> 39 * Rope operations, unlike string operations, scale well to very 40 * long character strings. Most mutation operations run in O(log n) 41 * time or better. However, random-access character retrieval is 42 * generally slower than for a String. By traversing consecutive 43 * characters with an iterator instead, performance improves to 44 * O(1). 45 * </p><p> 46 * This rope implementation implements all performance optimizations 47 * outlined in "<a href="http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf">Ropes: an Alternative to Strings</a>" 48 * by Hans-J. Boehm, Russ Atkinson and Michael Plass, including, 49 * notably, deferred evaluation of long substrings and automatic 50 * rebalancing. 51 * </p> 52 * <h4>Immutability (a Caveat)</h4> 53 * A rope is immutable. Specifically, calling any mutator function 54 * on a rope always returns a modified copy; the original rope is 55 * left untouched. However, care must be taken to build ropes from 56 * immutable <code>CharSequences</code> such as <code>Strings</code>, 57 * or else from mutable <code>CharSequences</code> that your program 58 * <emph>guarantees will not change</emph>. Failure to do so will result in 59 * logic errors. 60 * 61 * @author Amin Ahmad 62 */ 63public interface Rope extends CharSequence, Iterable<Character>, Comparable<CharSequence>, Serializable { 64 65 /** 66 * A factory used for constructing ropes. 67 */ 68 RopeBuilder BUILDER = new RopeBuilder(); 69 70 /** 71 * Returns a new rope created by appending the specified character to 72 * this rope. 73 * @param c the specified character. 74 * @return a new rope. 75 */ 76 Rope append(char c); 77 78 /** 79 * Returns a new rope created by appending the specified character sequence to 80 * this rope. 81 * @param suffix the specified suffix. 82 * @return a new rope. 83 */ 84 Rope append(CharSequence suffix); 85 86 /** 87 * Returns a new rope created by appending the specified character range to 88 * this rope. 89 * @param csq the specified character. 90 * @param start the start index, inclusive. 91 * @param end the end index, non-inclusive. 92 * @return a new rope. 93 */ 94 Rope append(CharSequence csq, int start, int end); 95 96 /** 97 * Creats a new rope by delete the specified character substring. 98 * The substring begins at the specified <code>start</code> and extends to 99 * the character at index <code>end - 1</code> or to the end of the 100 * sequence if no such character exists. If 101 * <code>start</code> is equal to <code>end</code>, no changes are made. 102 * 103 * @param start The beginning index, inclusive. 104 * @param end The ending index, exclusive. 105 * @return This object. 106 * @throws StringIndexOutOfBoundsException if <code>start</code> 107 * is negative, greater than <code>length()</code>, or 108 * greater than <code>end</code>. 109 */ 110 Rope delete(int start, int end); 111 112 /** 113 * Returns the index within this rope of the first occurrence of the 114 * specified character. If a character with value <code>ch</code> occurs 115 * in the character sequence represented by this <code>Rope</code> 116 * object, then the index of the first such occurrence is returned -- 117 * that is, the smallest value k such that: 118 * <p> 119 * <code>this.charAt(k) == ch</code> 120 * <p> 121 * is <code>true</code>. If no such character occurs in this string, then 122 * <code>-1</code> is returned. 123 * @param ch a character. 124 * @return the index of the first occurrence of the character in the character 125 * sequence represented by this object, or <code>-1</code> if the character 126 * does not occur. 127 */ 128 int indexOf(char ch); 129 130 /** 131 * Returns the index within this rope of the first occurrence of the 132 * specified character, beginning at the specified index. If a character 133 * with value <code>ch</code> occurs in the character sequence 134 * represented by this <code>Rope</code> object, then the index of the 135 * first such occurrence is returned—that is, the smallest value k 136 * such that: 137 * <p> 138 * <code>this.charAt(k) == ch</code> 139 * <p> 140 * is <code>true</code>. If no such character occurs in this string, then 141 * <code>-1</code> is returned. 142 * @param ch a character. 143 * @param fromIndex the index to start searching from. 144 * @return the index of the first occurrence of the character in the character 145 * sequence represented by this object, or -1 if the character does not occur. 146 */ 147 int indexOf(char ch, int fromIndex); 148 149 /** 150 * Returns the index within this rope of the first occurrence of the 151 * specified string. The value returned is the smallest <i>k</i> such 152 * that: 153 * <pre> 154 * this.startsWith(str, k) 155 * </pre> 156 * If no such <i>k</i> exists, then -1 is returned. 157 * @param sequence the string to find. 158 * @return the index of the first occurrence of the specified string, or 159 * -1 if the specified string does not occur. 160 */ 161 int indexOf(CharSequence sequence); 162 163 /** 164 * Returns the index within this rope of the first occurrence of the 165 * specified string, beginning at the specified index. The value returned 166 * is the smallest <i>k</i> such that: 167 * <pre> 168 * k >= fromIndex && this.startsWith(str, k) 169 * </pre> 170 * If no such <i>k</i> exists, then -1 is returned. 171 * @param sequence the string to find. 172 * @param fromIndex the index to start searching from. 173 * @return the index of the first occurrence of the specified string, or 174 * -1 if the specified string does not occur. 175 */ 176 int indexOf(CharSequence sequence, int fromIndex); 177 178 /** 179 * Creates a new rope by inserting the specified <code>CharSequence</code> 180 * into this rope. 181 * <p> 182 * The characters of the <code>CharSequence</code> argument are inserted, 183 * in order, into this rope at the indicated offset. 184 * 185 * <p>If <code>s</code> is <code>null</code>, then the four characters 186 * <code>"null"</code> are inserted into this sequence. 187 * 188 * @param dstOffset the offset. 189 * @param s the sequence to be inserted 190 * @return a reference to the new Rope. 191 * @throws IndexOutOfBoundsException if the offset is invalid. 192 */ 193 Rope insert(int dstOffset, CharSequence s); 194 195 /** 196 * Returns an iterator positioned to start at the specified index. 197 * @param start the start position. 198 * @return an iterator positioned to start at the specified index. 199 */ 200 Iterator<Character> iterator(int start); 201 202 /** 203 * Trims all whitespace as well as characters less than 0x20 from 204 * the beginning of this string. 205 * @return a rope with all leading whitespace trimmed. 206 */ 207 Rope ltrim(); 208 209 /** 210 * Creates a matcher that will match this rope against the 211 * specified pattern. This method produces a higher performance 212 * matcher than: 213 * <pre> 214 * Matcher m = pattern.matcher(this); 215 * </pre> 216 * The difference may be asymptotically better in many cases. 217 * @param pattern the pattern to match this rope against. 218 * @return a matcher. 219 */ 220 Matcher matcher(Pattern pattern); 221 222 /** 223 * Returns <code>true</code> if this rope matches the specified 224 * <code>Pattern</code>, or <code>false</code> otherwise. 225 * @see java.util.regex.Pattern 226 * @param regex the specified regular expression. 227 * @return <code>true</code> if this rope matches the specified 228 * <code>Pattern</code>, or <code>false</code> otherwise. 229 */ 230 public boolean matches(Pattern regex); 231 232 /** 233 * Returns <code>true</code> if this rope matches the specified 234 * regular expression, or <code>false</code> otherwise. 235 * @see java.util.regex.Pattern 236 * @param regex the specified regular expression. 237 * @return <code>true</code> if this rope matches the specified 238 * regular expression, or <code>false</code> otherwise. 239 */ 240 public boolean matches(String regex); 241 242 243 /** 244 * Rebalances the current rope, returning the rebalanced rope. In general, 245 * rope rebalancing is handled automatically, but this method is provided 246 * to give users more control. 247 * 248 * @return a rebalanced rope. 249 */ 250 public Rope rebalance(); 251 252 /** 253 * Reverses this rope. 254 * @return a reversed copy of this rope. 255 */ 256 public Rope reverse(); 257 258 /** 259 * Returns a reverse iterator positioned to start at the end of this 260 * rope. A reverse iterator moves backwards instead of forwards through 261 * a rope. 262 * @return A reverse iterator positioned at the end of this rope. 263 * @see Rope#reverseIterator(int) 264 */ 265 Iterator<Character> reverseIterator(); 266 267 /** 268 * Returns a reverse iterator positioned to start at the specified index. 269 * A reverse iterator moves backwards instead of forwards through a rope. 270 * @param start the start position. 271 * @return a reverse iterator positioned to start at the specified index from 272 * the end of the rope. For example, a value of 1 indicates the iterator 273 * should start 1 character before the end of the rope. 274 * @see Rope#reverseIterator() 275 */ 276 Iterator<Character> reverseIterator(int start); 277 278 /** 279 * Trims all whitespace as well as characters less than <code>0x20</code> from 280 * the end of this string. 281 * @return a rope with all trailing whitespace trimmed. 282 */ 283 Rope rtrim(); 284 285 @Override 286 Rope subSequence(int start, int end); 287 288 /** 289 * Trims all whitespace as well as characters less than <code>0x20</code> from 290 * the beginnning and end of this string. 291 * @return a rope with all leading and trailing whitespace trimmed. 292 */ 293 Rope trim(); 294 295 /** 296 * Write this rope to a <code>Writer</code>. 297 * @param out the writer object. 298 */ 299 public void write(Writer out) throws IOException; 300 301 /** 302 * Write a range of this rope to a <code>Writer</code>. 303 * @param out the writer object. 304 * @param offset the range offset. 305 * @param length the range length. 306 */ 307 public void write(Writer out, int offset, int length) throws IOException; 308} 309