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