1/* 2 * AbstractRope.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.impl; 24 25import java.io.IOException; 26import java.io.ObjectStreamException; 27import java.io.StringWriter; 28import java.util.Arrays; 29import java.util.Iterator; 30import java.util.regex.Matcher; 31import java.util.regex.Pattern; 32 33import org.ahmadsoft.ropes.Rope; 34 35/** 36 * Abstract base class for ropes that implements many of the common operations. 37 * @author Amin Ahmad 38 */ 39public abstract class AbstractRope implements Rope { 40 41 protected int hashCode = 0; 42 43 @Override 44 public Rope append(final char c) { 45 return RopeUtilities.INSTANCE.concatenate(this, Rope.BUILDER.build(String.valueOf(c))); 46 } 47 48 @Override 49 public Rope append(final CharSequence suffix) { 50 return RopeUtilities.INSTANCE.concatenate(this, Rope.BUILDER.build(suffix)); 51 } 52 53 @Override 54 public Rope append(final CharSequence csq, final int start, final int end) { 55 return RopeUtilities.INSTANCE.concatenate(this, Rope.BUILDER.build(csq).subSequence(start, end)); 56 } 57 58 @Override 59 public int compareTo(final CharSequence sequence) { 60 final int compareTill = Math.min(sequence.length(), this.length()); 61 final Iterator<Character> i = this.iterator(); 62 for (int j=0; j<compareTill; ++j) { 63 final char x = i.next(); 64 final char y = sequence.charAt(j); 65 if (x != y) 66 return x - y; 67 } 68 return this.length() - sequence.length(); 69 } 70 71 @Override 72 public Rope delete(final int start, final int end) { 73 if (start == end) 74 return this; 75 return this.subSequence(0, start).append(this.subSequence(end, this.length())); 76 } 77 78 /* 79 * The depth of the current rope, as defined in "Ropes: an Alternative 80 * to Strings". 81 */ 82 public abstract byte depth(); 83 84 @Override 85 public boolean equals(final Object other) { 86 if (other instanceof Rope) { 87 final Rope rope = (Rope) other; 88 if (rope.hashCode() != this.hashCode() || rope.length() != this.length()) 89 return false; 90 final Iterator<Character> i1 = this.iterator(); 91 final Iterator<Character> i2 = rope.iterator(); 92 93 while (i1.hasNext()) { 94 final char a = i1.next(); 95 final char b = i2.next(); 96 if (a != b) 97 return false; 98 } 99 return true; 100 } 101 return false; 102 } 103 104 /** 105 * A utility method that returns an instance of this rope optimized 106 * for sequential access. 107 * @return 108 */ 109 protected CharSequence getForSequentialAccess() { 110 return this; 111 } 112 113 @Override 114 public int hashCode() { 115 if (this.hashCode == 0 && this.length() > 0) { 116 if (this.length() < 6) { 117 for (final char c: this) 118 this.hashCode = 31 * this.hashCode + c; 119 } else { 120 final Iterator<Character> i = this.iterator(); 121 for (int j=0;j<5; ++j) 122 this.hashCode = 31 * this.hashCode + i.next(); 123 this.hashCode = 31 * this.hashCode + this.charAt(this.length() - 1); 124 } 125 } 126 return this.hashCode; 127 } 128 129 @Override 130 public int indexOf(final char ch) { 131 int index = -1; 132 for (final char c: this) { 133 ++index; 134 if (c == ch) 135 return index; 136 } 137 return -1; 138 } 139 140 @Override 141 public boolean startsWith(CharSequence prefix) { 142 return startsWith(prefix, 0); 143 } 144 145 @Override 146 public boolean startsWith(CharSequence prefix, int offset) { 147 if (offset < 0 || offset > this.length()) 148 throw new IndexOutOfBoundsException("Rope offset out of range: " + offset); 149 if (offset + prefix.length() > this.length()) 150 return false; 151 152 int x=0; 153 for (Iterator<Character> i=this.iterator(offset); i.hasNext() && x < prefix.length(); ) { 154 if (i.next().charValue() != prefix.charAt(x++)) 155 return false; 156 } 157 return true; 158 } 159 160 @Override 161 public boolean endsWith(CharSequence suffix) { 162 return endsWith(suffix, 0); 163 } 164 165 @Override 166 public boolean endsWith(CharSequence suffix, int offset) { 167 return startsWith(suffix, length() - suffix.length() - offset); 168 } 169 170 @Override 171 public int indexOf(final char ch, final int fromIndex) { 172 if (fromIndex < 0 || fromIndex >= this.length()) 173 throw new IndexOutOfBoundsException("Rope index out of range: " + fromIndex); 174 int index = fromIndex - 1; 175 for (final Iterator<Character> i=this.iterator(fromIndex); i.hasNext(); ) { 176 ++index; 177 if (i.next().charValue() == ch) 178 return index; 179 } 180 return -1; 181 } 182 183 @Override 184 public int indexOf(final CharSequence sequence) { 185 return this.indexOf(sequence, 0); 186 } 187 188 @Override 189 public int indexOf(final CharSequence sequence, final int fromIndex) { 190 final CharSequence me = this.getForSequentialAccess(); 191 192 // Implementation of Boyer-Moore-Horspool algorithm with 193 // special support for unicode. 194 195 // step 0. sanity check. 196 final int length = sequence.length(); 197 if (length == 0) 198 return -1; 199 if (length == 1) 200 return this.indexOf(sequence.charAt(0), fromIndex); 201 202 final int[] bcs = new int[256]; // bad character shift 203 Arrays.fill(bcs, length); 204 205 // step 1. preprocessing. 206 for (int j=0; j<length-1; ++j) { 207 final char c = sequence.charAt(j); 208 final int l = (c & 0xFF); 209 bcs[l] = Math.min(length - j - 1, bcs[l]); 210 } 211 212 // step 2. search. 213 for (int j=fromIndex+length-1; j<this.length();) { 214 int x=j, y=length-1; 215 while (true) { 216 final char c = me.charAt(x); 217 if (sequence.charAt(y) != c) { 218 j += bcs[(c & 0xFF)]; 219 break; 220 } 221 if (y == 0) 222 return x; 223 --x; --y; 224 } 225 226 } 227 228 return -1; 229 } 230 231 @Override 232 public Rope insert(final int dstOffset, final CharSequence s) { 233 final Rope r = (s == null) ? Rope.BUILDER.build("null"): Rope.BUILDER.build(s); 234 if (dstOffset == 0) 235 return r.append(this); 236 else if (dstOffset == this.length()) 237 return this.append(r); 238 else if (dstOffset < 0 || dstOffset > this.length()) 239 throw new IndexOutOfBoundsException(dstOffset + " is out of insert range [" + 0 + ":" + this.length() + "]"); 240 return this.subSequence(0, dstOffset).append(r).append(this.subSequence(dstOffset, this.length())); 241 } 242 243 @Override 244 public Iterator<Character> iterator() { 245 return this.iterator(0); 246 } 247 248 @Override 249 public Rope trimStart() { 250 int index = -1; 251 for (final char c: this) { 252 ++index; 253 if (c > 0x20 && !Character.isWhitespace(c)) 254 break; 255 } 256 if (index <= 0) 257 return this; 258 else 259 return this.subSequence(index, this.length()); 260 } 261 262 @Override 263 public Matcher matcher(final Pattern pattern) { 264 return pattern.matcher(this.getForSequentialAccess()); 265 } 266 267 @Override 268 public boolean matches(final Pattern regex) { 269 return regex.matcher(this.getForSequentialAccess()).matches(); 270 } 271 272 @Override 273 public boolean matches(final String regex) { 274 return Pattern.matches(regex, this.getForSequentialAccess()); 275 } 276 277 @Override 278 public Rope rebalance() { 279 return this; 280 } 281 282 @Override 283 public Iterator<Character> reverseIterator() { 284 return this.reverseIterator(0); 285 } 286 287 @Override 288 public Rope trimEnd() { 289 int index = this.length() + 1; 290 for (final Iterator<Character> i=this.reverseIterator(); i.hasNext();) { 291 final char c = i.next(); 292 --index; 293 if (c > 0x20 && !Character.isWhitespace(c)) 294 break; 295 } 296 if (index >= this.length()) 297 return this; 298 else 299 return this.subSequence(0, index); 300 } 301 302 @Override 303 public String toString() { 304 final StringWriter out = new StringWriter(this.length()); 305 try { 306 this.write(out); 307 out.close(); 308 } catch (final IOException e) { 309 throw new RuntimeException(e); 310 } 311 return out.toString(); 312 } 313 314 @Override 315 public Rope trim() { 316 return this.trimStart().trimEnd(); 317 } 318 319 public Object writeReplace() throws ObjectStreamException { 320 return new SerializedRope(this); 321 } 322 323 324 @Override 325 public Rope padStart(final int toWidth) { 326 return padStart(toWidth, ' '); 327 } 328 329 @Override 330 public Rope padStart(final int toWidth, final char padChar) { 331 final int toPad = toWidth - this.length(); 332 if (toPad < 1) 333 return this; 334 return RopeUtilities.INSTANCE.concatenate( 335 Rope.BUILDER.build(new RepeatedCharacterSequence(padChar, toPad)), 336 this); 337 } 338 339 @Override 340 public Rope padEnd(final int toWidth) { 341 return padEnd(toWidth, ' '); 342 } 343 344 @Override 345 public Rope padEnd(final int toWidth, final char padChar) { 346 final int toPad = toWidth - this.length(); 347 if (toPad < 1) 348 return this; 349 return RopeUtilities.INSTANCE.concatenate( 350 this, 351 Rope.BUILDER.build(new RepeatedCharacterSequence(padChar, toPad))); 352 } 353 354 @Override 355 public boolean isEmpty() { 356 return length() == 0; 357 } 358} 359