| RangedPassage.java |
1 /**
2 * Distribution License:
3 * JSword is free software; you can redistribute it and/or modify it under
4 * the terms of the GNU Lesser General Public License, version 2.1 as published by
5 * the Free Software Foundation. This program is distributed in the hope
6 * that it will be useful, but WITHOUT ANY WARRANTY; without even the
7 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
8 * See the GNU Lesser General Public License for more details.
9 *
10 * The License is available on the internet at:
11 * http://www.gnu.org/copyleft/lgpl.html
12 * or by writing to:
13 * Free Software Foundation, Inc.
14 * 59 Temple Place - Suite 330
15 * Boston, MA 02111-1307, USA
16 *
17 * Copyright: 2005
18 * The copyright to this program is held by it's authors.
19 *
20 * ID: $Id: RangedPassage.java 2226 2012-02-02 19:25:21Z dmsmith $
21 */
22 package org.crosswire.jsword.passage;
23
24 import java.io.IOException;
25 import java.io.ObjectInputStream;
26 import java.io.ObjectOutputStream;
27 import java.util.Iterator;
28 import java.util.NoSuchElementException;
29 import java.util.Set;
30 import java.util.TreeSet;
31
32 import org.crosswire.jsword.versification.Versification;
33
34 /**
35 * A Passage that is implemented using a TreeSet of VerseRanges. The attributes
36 * of the style are:
37 * <ul>
38 * <li>Compact storage of large amounts of data
39 * <li>Fast getName()
40 * <li>Slow manipulation
41 * </ul>
42 *
43 * <p>
44 * When to normalize()? This is a slow process, but one that is perhaps done
45 * bit-by-bit instead of killing everything just to do getName(). The options
46 * are:
47 * <ul>
48 * <li>Before every read</li>
49 * <li>Before reads with a background thread</li>
50 * <li>After every change</li>
51 * <li>After every change with a caching scheme</li>
52 * </ul>
53 * I'm not sure which will be best. So I'm starting with 1 and optimizing later
54 * ... Maybe the best is to allow the user to choose?
55 *
56 * @see gnu.lgpl.License for license details.<br>
57 * The copyright to this program is held by it's authors.
58 * @author Joe Walker [joe at eireneh dot com]
59 */
60 public class RangedPassage extends AbstractPassage {
61 /**
62 * Create an empty RangedPassage. There are no ctors from either Verse or
63 * VerseRange so you need to do new <code>RangedPassage().add(...);</code>
64 *
65 * @param refSystem
66 * The Versification to which this Passage belongs.
67 */
68 protected RangedPassage(Versification refSystem) {
69 super(refSystem);
70 store = new TreeSet<Key>();
71 }
72
73 /**
74 * Create a Verse from a human readable string. The opposite of getName(),
75 * Given any RangedPassage v1, and the following
76 * <code>RangedPassage v2 = new RangedPassage(v1.getName());</code> Then
77 * <code>v1.equals(v2);</code> Theoretically, since there are many ways of
78 * representing a RangedPassage as text string comparison along the lines
79 * of: <code>v1.getName().equals(v2.getName())</code> could be false.
80 * However since getName() is standardized this will be true. We don't need
81 * to worry about thread safety in a ctor since we don't exist yet.
82 *
83 * @param refs
84 * A String containing the text of the RangedPassage
85 * @throws NoSuchVerseException
86 * if refs is invalid
87 */
88 protected RangedPassage(Versification refSystem, String refs) throws NoSuchVerseException {
89 super(refSystem, refs);
90
91 store = new TreeSet<Key>();
92 addVerses(refs);
93 normalize();
94 }
95
96 @Override
97 public RangedPassage clone() {
98 // This gets us a shallow copy
99 RangedPassage copy = (RangedPassage) super.clone();
100
101 // I want to just do the following
102 // copy.store = (SortedSet) store.clone();
103 // However SortedSet is not Cloneable so I can't
104 // Watch out for this, I'm not sure if it breaks anything.
105 copy.store = new TreeSet<Key>();
106 copy.store.addAll(store);
107
108 return copy;
109 }
110
111 @Override
112 public int countRanges(RestrictionType restrict) {
113 if (restrict.equals(RestrictionType.NONE)) {
114 return store.size();
115 }
116
117 return super.countRanges(restrict);
118 }
119
120 @Override
121 public int countVerses() {
122 Iterator<Key> it = rangeIterator(RestrictionType.NONE);
123 int count = 0;
124
125 while (it.hasNext()) {
126 VerseRange range = (VerseRange) it.next();
127 count += range.getCardinality();
128 }
129
130 return count;
131 }
132
133 /* (non-Javadoc)
134 * @see java.lang.Iterable#iterator()
135 */
136 public Iterator<Key> iterator() {
137 return new VerseIterator(getVersification(), rangeIterator(RestrictionType.NONE));
138 }
139
140 @Override
141 public final Iterator<Key> rangeIterator(RestrictionType restrict) {
142 if (restrict.equals(RestrictionType.NONE)) {
143 return store.iterator();
144 }
145
146 return new VerseRangeIterator(store.iterator(), restrict);
147 }
148
149 @Override
150 public boolean isEmpty() {
151 return store.isEmpty();
152 }
153
154 @Override
155 public boolean contains(Key obj) {
156 // Even for the contains(VerseRange) case, the simple
157 // 'return store.contains(that);' will not work because
158 // VerseRanges can contain others but not be equal to them.
159
160 VerseRange that_range = toVerseRange(getVersification(), obj);
161
162 Iterator<Key> it = rangeIterator(RestrictionType.NONE);
163 while (it.hasNext()) {
164 VerseRange this_range = (VerseRange) it.next();
165 if (this_range.contains(that_range)) {
166 return true;
167 }
168 }
169
170 // If it is not a Verse or a VerseRange then it's not here,
171 // this also copes with the searches failing.
172 return false;
173 }
174
175 /* (non-Javadoc)
176 * @see org.crosswire.jsword.passage.Passage#add(org.crosswire.jsword.passage.Key)
177 */
178 public void add(Key obj) {
179 optimizeWrites();
180
181 VerseRange that_range = toVerseRange(getVersification(), obj);
182 store.add(that_range);
183
184 normalize();
185
186 // we do an extra check here because the cost of calculating the
187 // params is non-zero an may be wasted
188 if (suppressEvents == 0) {
189 fireIntervalAdded(this, that_range.getStart(), that_range.getEnd());
190 }
191 }
192
193 @Override
194 public void clear() {
195 optimizeWrites();
196
197 store.clear();
198 fireIntervalRemoved(this, null, null);
199 }
200
201 /* (non-Javadoc)
202 * @see org.crosswire.jsword.passage.Passage#remove(org.crosswire.jsword.passage.Key)
203 */
204 public void remove(Key obj) {
205 optimizeWrites();
206
207 VerseRange that_range = toVerseRange(getVersification(), obj);
208 boolean removed = false;
209
210 // This allows us to modify store which iterating through a copy
211 Set<Key> new_store = new TreeSet<Key>();
212 new_store.addAll(store);
213
214 // go through all the VerseRanges
215 for (Key aKey : new_store) {
216 // if this range touches the range to be removed ...
217 VerseRange this_range = (VerseRange) aKey;
218 if (this_range.overlaps(that_range)) {
219 // ... remove it and add the remainder
220 store.remove(this_range);
221 VerseRange[] vra = VerseRange.remainder(this_range, that_range);
222
223 for (int i = 0; i < vra.length; i++) {
224 store.add(vra[i]);
225 }
226
227 removed = true;
228 }
229 }
230
231 if (removed) {
232 normalize();
233 }
234
235 // we do an extra check here because the cost of calculating the
236 // params is non-zero an may be wasted
237 if (suppressEvents == 0) {
238 fireIntervalRemoved(this, that_range.getStart(), that_range.getEnd());
239 }
240 }
241
242 @Override
243 public void retainAll(Key key) {
244 Passage that = KeyUtil.getPassage(key);
245
246 optimizeWrites();
247
248 Set<Key> new_store = new TreeSet<Key>();
249
250 Iterator<Key> that_it = null;
251 if (that instanceof RangedPassage) {
252 that_it = that.rangeIterator(RestrictionType.CHAPTER);
253 } else {
254 that_it = that.iterator();
255 }
256
257 while (that_it.hasNext()) {
258 VerseRange that_range = toVerseRange(getVersification(), that_it.next());
259
260 // go through all the VerseRanges
261 Iterator<Key> this_it = rangeIterator(RestrictionType.NONE);
262 while (this_it.hasNext()) {
263 // if this range touches the range to be removed ...
264 VerseRange this_range = (VerseRange) this_it.next();
265 if (this_range.overlaps(that_range)) {
266 // ... remove it and add the remainder
267 VerseRange interstect = VerseRange.intersection(this_range, that_range);
268 if (interstect != null) {
269 new_store.add(interstect);
270 }
271 }
272 }
273 }
274
275 store = new_store;
276 normalize();
277
278 fireIntervalRemoved(this, null, null);
279 }
280
281 /**
282 * We sometimes need to sort ourselves out ...
283 * <p>
284 * I don't think we need to be synchronized since we are private and we
285 * could check that all public calling of normalize() are synchronized,
286 * however this is safe, and I don't think there is a cost associated with a
287 * double synchronize. (?)
288 */
289 @Override
290 /* protected */final void normalize() {
291 if (skipNormalization != 0) {
292 return;
293 }
294
295 VerseRange last = null;
296 VerseRange next = null;
297 Set<Key> new_store = new TreeSet<Key>();
298
299 Iterator<Key> it = rangeIterator(RestrictionType.NONE);
300 while (it.hasNext()) {
301 next = (VerseRange) it.next();
302
303 if (last != null && next.adjacentTo(last)) {
304 VerseRange merge = new VerseRange(last, next);
305
306 new_store.remove(last);
307 new_store.add(merge);
308
309 last = merge;
310 } else {
311 new_store.add(next);
312 last = next;
313 }
314 }
315
316 store = new_store;
317 }
318
319 /**
320 * This class is here to prevent users of RangedPassage.iterator() from
321 * altering the underlying store and getting us out of sync. Right now there
322 * are no issues with someone else removing a RangedPassage without telling
323 * us, however there may be some day, and I'm not sure that we need the
324 * functionality right now. Also buy using this we get to ensure
325 * synchronization. Everything is final so to save the proxying performace
326 * hit.
327 */
328 private static final class VerseIterator implements Iterator<Key> {
329 /**
330 * Create a basic iterator that is a proxy for the RangedPassage
331 * Passages iterator, with remove() overridden.
332 */
333 public VerseIterator(Versification v11n, Iterator<Key> it) {
334 Set<Key> temp = new TreeSet<Key>();
335
336 while (it.hasNext()) {
337 VerseRange range = (VerseRange) it.next();
338 int start = v11n.getOrdinal(range.getStart());
339 int end = range.getCardinality();
340
341 for (int i = 0; i < end; i++) {
342 temp.add(v11n.decodeOrdinal(start + i));
343 }
344 }
345
346 real = temp.iterator();
347 }
348
349 /* (non-Javadoc)
350 * @see java.util.Iterator#hasNext()
351 */
352 public boolean hasNext() {
353 return real.hasNext();
354 }
355
356 /* (non-Javadoc)
357 * @see java.util.Iterator#next()
358 */
359 public Key next() throws NoSuchElementException {
360 return real.next();
361 }
362
363 /* (non-Javadoc)
364 * @see java.util.Iterator#remove()
365 */
366 public void remove() throws UnsupportedOperationException {
367 throw new UnsupportedOperationException();
368 }
369
370 /**
371 * The Iterator that we are proxying to
372 */
373 private Iterator<Key> real;
374 }
375
376 /**
377 * Loop over the VerseRanges and check that they do not require digging into
378 */
379 private static final class VerseRangeIterator implements Iterator<Key> {
380 /**
381 * Simple ctor
382 */
383 public VerseRangeIterator(Iterator<Key> it, RestrictionType restrict) {
384 this.restrict = restrict;
385 this.real = it;
386 }
387
388 /* (non-Javadoc)
389 * @see java.util.Iterator#remove()
390 */
391 public void remove() {
392 throw new UnsupportedOperationException();
393 }
394
395 /* (non-Javadoc)
396 * @see java.util.Iterator#hasNext()
397 */
398 public boolean hasNext() {
399 return next != null || real.hasNext();
400 }
401
402 /* (non-Javadoc)
403 * @see java.util.Iterator#next()
404 */
405 public Key next() {
406 if (next == null) {
407 next = (VerseRange) real.next();
408 }
409
410 if (next == null) {
411 throw new NoSuchElementException();
412 }
413
414 // So we know what is broadly next, however the range might need
415 // splitting according to restrict
416 if (restrict.isSameScope(next.getVersification(), next.getStart(), next.getEnd())) {
417 return replyNext();
418 }
419 return splitNext();
420 }
421
422 /**
423 * The next object is correct, use that one
424 */
425 private Key replyNext() {
426 VerseRange reply = next;
427 next = null;
428 return reply;
429 }
430
431 /**
432 * The next object is too big, so cut it up
433 */
434 private Key splitNext() {
435 Iterator<Key> chop = next.rangeIterator(restrict);
436 VerseRange first = (VerseRange) chop.next();
437 VerseRange[] ranges = VerseRange.remainder(next, first);
438
439 assert ranges.length == 1;
440 next = ranges[0];
441
442 return first;
443 }
444
445 /**
446 * What are we going to reply with next?
447 */
448 private VerseRange next;
449
450 /**
451 * Where do we break ranges
452 */
453 private RestrictionType restrict;
454
455 /**
456 * Where we read our base ranges from
457 */
458 private Iterator<Key> real;
459 }
460
461 /**
462 * Call the support mechanism in AbstractPassage
463 *
464 * @param out
465 * The stream to write our state to
466 * @serialData Write the ordinal number of this verse
467 * @throws IOException
468 * if the read fails
469 * @see AbstractPassage#writeObjectSupport(ObjectOutputStream)
470 */
471 private void writeObject(ObjectOutputStream out) throws IOException {
472 out.defaultWriteObject();
473
474 writeObjectSupport(out);
475 }
476
477 /**
478 * Call the support mechanism in AbstractPassage
479 *
480 * @param in
481 * The stream to read our state from
482 * @serialData Write the ordinal number of this verse
483 * @throws IOException
484 * if the read fails
485 * @throws ClassNotFoundException
486 * If the read data is incorrect
487 * @see AbstractPassage#readObjectSupport(ObjectInputStream)
488 */
489 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
490 optimizeWrites();
491
492 store = new TreeSet<Key>();
493
494 in.defaultReadObject();
495
496 readObjectSupport(in);
497 }
498
499 /**
500 * To make serialization work across new versions
501 */
502 static final long serialVersionUID = 955115811339960826L;
503
504 /**
505 * The place the real data is stored
506 */
507 private transient Set<Key> store;
508 }
509