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[(me.charAt(j) & 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