1/*
2 *  FlatCharArrayRope.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.Writer;
27import java.util.Arrays;
28import java.util.Iterator;
29
30import org.ahmadsoft.ropes.Rope;
31
32/**
33 * A rope constructed from a character array. This rope is even
34 * flatter than a regular flat rope.
35 * @author Amin Ahmad
36 */
37public final class FlatCharArrayRope extends AbstractRope implements FlatRope {
38
39	private final char[] sequence;
40
41	/**
42	 * Constructs a new rope from a character array.
43	 * @param sequence the character array.
44	 */
45	public FlatCharArrayRope(final char[] sequence) {
46		this(sequence, 0, sequence.length);
47	}
48
49	/**
50	 * Constructs a new rope from a character array range.
51	 * @param sequence the character array.
52	 * @param offset the offset in the array.
53	 * @param length the length of the array.
54	 */
55	public FlatCharArrayRope(final char[] sequence, final int offset, final int length) {
56		if (length > sequence.length)
57			throw new IllegalArgumentException("Length must be less than " + sequence.length);
58		this.sequence = new char[length];
59		System.arraycopy(sequence, offset, this.sequence, 0, length);
60	}
61
62	@Override
63	public char charAt(final int index) {
64		return this.sequence[index];
65	}
66
67	@Override
68	public byte depth() {
69		return 0;
70	}
71
72	/*
73	 * Implementation Note: This is a reproduction of the AbstractRope
74	 * indexOf implementation. Calls to charAt have been replaced
75	 * with direct array access to improve speed.
76	 */
77	@Override
78	public int indexOf(final char ch) {
79		for (int j=0; j<this.sequence.length; ++j)
80			if (this.sequence[j] == ch)
81				return j;
82		return -1;
83	}
84
85	/*
86	 * Implementation Note: This is a reproduction of the AbstractRope
87	 * indexOf implementation. Calls to charAt have been replaced
88	 * with direct array access to improve speed.
89	 */
90	@Override
91	public int indexOf(final char ch, final int fromIndex) {
92		if (fromIndex < 0 || fromIndex >= this.length())
93			throw new IndexOutOfBoundsException("Rope index out of range: " + fromIndex);
94		for (int j=fromIndex; j<this.sequence.length; ++j)
95			if (this.sequence[j] == ch)
96				return j;
97		return -1;
98	}
99
100	/*
101	 * Implementation Note: This is a reproduction of the AbstractRope
102	 * indexOf implementation. Calls to charAt have been replaced
103	 * with direct array access to improve speed.
104	 */
105	@Override
106	public int indexOf(final CharSequence sequence, final int fromIndex) {
107		// Implementation of Boyer-Moore-Horspool algorithm with
108		// special support for unicode.
109
110		// step 0. sanity check.
111		final int length = sequence.length();
112		if (length == 0)
113			return -1;
114		if (length == 1)
115			return this.indexOf(sequence.charAt(0), fromIndex);
116
117		final int[] bcs = new int[256]; // bad character shift
118		Arrays.fill(bcs, length);
119
120		// step 1. preprocessing.
121		for (int j=0; j<length-1; ++j) {
122			final char c = sequence.charAt(j);
123			final int l = (c & 0xFF);
124			bcs[l] = Math.min(length - j - 1, bcs[l]);
125		}
126
127		// step 2. search.
128		for (int j=fromIndex+length-1; j<this.length();) {
129			int x=j, y=length-1;
130			while (true) {
131				if (sequence.charAt(y) != this.sequence[x]) {
132					j += bcs[(this.sequence[x] & 0xFF)];
133					break;
134				}
135				if (y == 0)
136					return x;
137				--x; --y;
138			}
139
140		}
141
142		return -1;
143	}
144
145	@Override
146	public Iterator<Character> iterator(final int start) {
147		if (start < 0 || start > this.length())
148			throw new IndexOutOfBoundsException("Rope index out of range: " + start);
149		return new Iterator<Character>() {
150			int current = start;
151			@Override
152			public boolean hasNext() {
153				return this.current < FlatCharArrayRope.this.length();
154			}
155
156			@Override
157			public Character next() {
158				return FlatCharArrayRope.this.sequence[this.current++];
159			}
160
161			@Override
162			public void remove() {
163				throw new UnsupportedOperationException("Rope iterator is read-only.");
164			}
165		};
166	}
167
168	@Override
169	public int length() {
170		return this.sequence.length;
171	}
172
173	@Override
174	public Rope reverse() {
175		return new ReverseRope(this);
176	}
177
178	@Override
179	public Iterator<Character> reverseIterator(final int start) {
180		if (start < 0 || start > this.length())
181			throw new IndexOutOfBoundsException("Rope index out of range: " + start);
182		return new Iterator<Character>() {
183			int current = FlatCharArrayRope.this.length() - start;
184			@Override
185			public boolean hasNext() {
186				return this.current > 0;
187			}
188
189			@Override
190			public Character next() {
191				return FlatCharArrayRope.this.sequence[--this.current];
192			}
193
194			@Override
195			public void remove() {
196				throw new UnsupportedOperationException("Rope iterator is read-only.");
197			}
198		};
199	}
200
201	@Override
202	public Rope subSequence(final int start, final int end) {
203		if (start == 0 && end == this.length())
204			return this;
205		if (end - start < 16) {
206			return new FlatCharArrayRope(this.sequence, start, end-start);
207		} else {
208			return new SubstringRope(this, start, end-start);
209		}
210	}
211
212	@Override
213	public String toString() {
214		return new String(this.sequence);
215	}
216
217
218	public String toString(final int offset, final int length) {
219		return new String(this.sequence, offset, length);
220	}
221
222	@Override
223	public void write(final Writer out) throws IOException {
224		this.write(out, 0, this.length());
225	}
226
227	@Override
228	public void write(final Writer out, final int offset, final int length) throws IOException {
229		out.write(this.sequence, offset, length);
230	}
231}
232