Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
RangedPassage |
|
| 2.4074074074074074;2.407 | ||||
RangedPassage$VerseIterator |
|
| 2.4074074074074074;2.407 | ||||
RangedPassage$VerseRangeIterator |
|
| 2.4074074074074074;2.407 |
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 | 0 | 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 | 0 | super(refSystem); |
67 | 0 | store = new TreeSet<VerseRange>(); |
68 | 0 | } |
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 | 0 | super(v11n, refs); |
91 | ||
92 | 0 | store = new TreeSet<VerseRange>(); |
93 | 0 | addVerses(refs, basis); |
94 | 0 | normalize(); |
95 | 0 | } |
96 | ||
97 | protected RangedPassage(Versification v11n, String refs) throws NoSuchVerseException { | |
98 | 0 | this(v11n, refs, null); |
99 | 0 | } |
100 | ||
101 | @Override | |
102 | public RangedPassage clone() { | |
103 | // This gets us a shallow copy | |
104 | 0 | 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 | 0 | copy.store = new TreeSet<VerseRange>(); |
111 | 0 | copy.store.addAll(store); |
112 | ||
113 | 0 | return copy; |
114 | } | |
115 | ||
116 | @Override | |
117 | public int countRanges(RestrictionType restrict) { | |
118 | 0 | if (restrict.equals(RestrictionType.NONE)) { |
119 | 0 | return store.size(); |
120 | } | |
121 | ||
122 | 0 | return super.countRanges(restrict); |
123 | } | |
124 | ||
125 | @Override | |
126 | public int countVerses() { | |
127 | 0 | Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE); |
128 | 0 | int count = 0; |
129 | ||
130 | 0 | while (it.hasNext()) { |
131 | 0 | VerseRange range = it.next(); |
132 | 0 | count += range.getCardinality(); |
133 | 0 | } |
134 | ||
135 | 0 | return count; |
136 | } | |
137 | ||
138 | /* (non-Javadoc) | |
139 | * @see java.lang.Iterable#iterator() | |
140 | */ | |
141 | public Iterator<Key> iterator() { | |
142 | 0 | return new VerseIterator(getVersification(), rangeIterator(RestrictionType.NONE)); |
143 | } | |
144 | ||
145 | @Override | |
146 | public final Iterator<VerseRange> rangeIterator(RestrictionType restrict) { | |
147 | 0 | if (restrict.equals(RestrictionType.NONE)) { |
148 | 0 | return store.iterator(); |
149 | } | |
150 | ||
151 | 0 | return new VerseRangeIterator(store.iterator(), restrict); |
152 | } | |
153 | ||
154 | @Override | |
155 | public boolean isEmpty() { | |
156 | 0 | 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 | 0 | VerseRange thatRange = toVerseRange(getVersification(), obj); |
166 | ||
167 | 0 | Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE); |
168 | 0 | while (it.hasNext()) { |
169 | 0 | VerseRange thisRange = it.next(); |
170 | 0 | if (thisRange.contains(thatRange)) { |
171 | 0 | return true; |
172 | } | |
173 | 0 | } |
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 | 0 | 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 | 0 | optimizeWrites(); |
185 | ||
186 | 0 | VerseRange thatRange = toVerseRange(getVersification(), obj); |
187 | 0 | store.add(thatRange); |
188 | ||
189 | 0 | 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 | 0 | if (suppressEvents == 0) { |
194 | 0 | fireIntervalAdded(this, thatRange.getStart(), thatRange.getEnd()); |
195 | } | |
196 | 0 | } |
197 | ||
198 | @Override | |
199 | public void clear() { | |
200 | 0 | optimizeWrites(); |
201 | ||
202 | 0 | store.clear(); |
203 | 0 | fireIntervalRemoved(this, null, null); |
204 | 0 | } |
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 | 0 | optimizeWrites(); |
211 | ||
212 | 0 | VerseRange thatRange = toVerseRange(getVersification(), obj); |
213 | 0 | boolean removed = false; |
214 | ||
215 | // This allows us to modify store which iterating through a copy | |
216 | 0 | Set<Key> newStore = new TreeSet<Key>(); |
217 | 0 | newStore.addAll(store); |
218 | ||
219 | // go through all the VerseRanges | |
220 | 0 | for (Key aKey : newStore) { |
221 | // if this range touches the range to be removed ... | |
222 | 0 | VerseRange thisRange = (VerseRange) aKey; |
223 | 0 | if (thisRange.overlaps(thatRange)) { |
224 | // ... remove it and add the remainder | |
225 | 0 | store.remove(thisRange); |
226 | 0 | VerseRange[] vra = VerseRange.remainder(thisRange, thatRange); |
227 | ||
228 | 0 | for (int i = 0; i < vra.length; i++) { |
229 | 0 | store.add(vra[i]); |
230 | } | |
231 | ||
232 | 0 | removed = true; |
233 | } | |
234 | 0 | } |
235 | ||
236 | 0 | if (removed) { |
237 | 0 | 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 | 0 | if (suppressEvents == 0) { |
243 | 0 | fireIntervalRemoved(this, thatRange.getStart(), thatRange.getEnd()); |
244 | } | |
245 | 0 | } |
246 | ||
247 | @Override | |
248 | public void retainAll(Key key) { | |
249 | 0 | optimizeWrites(); |
250 | ||
251 | 0 | Set<VerseRange> newStore = new TreeSet<VerseRange>(); |
252 | ||
253 | 0 | if (key instanceof RangedPassage) { |
254 | 0 | Iterator<VerseRange> thatIter = ((RangedPassage) key).rangeIterator(RestrictionType.CHAPTER); |
255 | 0 | while (thatIter.hasNext()) { |
256 | 0 | VerseRange thatRange = thatIter.next(); |
257 | ||
258 | // go through all the VerseRanges | |
259 | 0 | Iterator<VerseRange> thisIter = rangeIterator(RestrictionType.NONE); |
260 | 0 | while (thisIter.hasNext()) { |
261 | // if this range touches the range to be removed ... | |
262 | 0 | VerseRange thisRange = thisIter.next(); |
263 | 0 | if (thisRange.overlaps(thatRange)) { |
264 | // ... remove it and add the remainder | |
265 | 0 | VerseRange interstect = VerseRange.intersection(thisRange, thatRange); |
266 | 0 | if (interstect != null) { |
267 | 0 | newStore.add(interstect); |
268 | } | |
269 | } | |
270 | 0 | } |
271 | 0 | } |
272 | 0 | } else { |
273 | 0 | Iterator<Key> thatIter = key.iterator(); |
274 | 0 | while (thatIter.hasNext()) { |
275 | 0 | VerseRange thatRange = toVerseRange(getVersification(), thatIter.next()); |
276 | ||
277 | // go through all the VerseRanges | |
278 | 0 | Iterator<VerseRange> thisIter = rangeIterator(RestrictionType.NONE); |
279 | 0 | while (thisIter.hasNext()) { |
280 | // if this range touches the range to be removed ... | |
281 | 0 | VerseRange thisRange = thisIter.next(); |
282 | 0 | if (thisRange.overlaps(thatRange)) { |
283 | // ... remove it and add the remainder | |
284 | 0 | VerseRange interstect = VerseRange.intersection(thisRange, thatRange); |
285 | 0 | if (interstect != null) { |
286 | 0 | newStore.add(interstect); |
287 | } | |
288 | } | |
289 | 0 | } |
290 | 0 | } |
291 | } | |
292 | ||
293 | ||
294 | 0 | store = newStore; |
295 | 0 | normalize(); |
296 | ||
297 | 0 | fireIntervalRemoved(this, null, null); |
298 | 0 | } |
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 | 0 | if (skipNormalization != 0) { |
311 | 0 | return; |
312 | } | |
313 | ||
314 | 0 | VerseRange last = null; |
315 | 0 | VerseRange next = null; |
316 | 0 | Set<VerseRange> newStore = new TreeSet<VerseRange>(); |
317 | ||
318 | 0 | Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE); |
319 | 0 | while (it.hasNext()) { |
320 | 0 | next = it.next(); |
321 | ||
322 | 0 | if (last != null && next.adjacentTo(last)) { |
323 | 0 | VerseRange merge = new VerseRange(last, next); |
324 | ||
325 | 0 | newStore.remove(last); |
326 | 0 | newStore.add(merge); |
327 | ||
328 | 0 | last = merge; |
329 | 0 | } else { |
330 | 0 | newStore.add(next); |
331 | 0 | last = next; |
332 | } | |
333 | } | |
334 | ||
335 | 0 | store = newStore; |
336 | 0 | } |
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 | 0 | 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 | 0 | protected VerseIterator(Versification v11n, Iterator<VerseRange> it) { |
356 | 0 | Set<Key> temp = new TreeSet<Key>(); |
357 | ||
358 | 0 | while (it.hasNext()) { |
359 | 0 | VerseRange range = it.next(); |
360 | 0 | int start = range.getStart().getOrdinal(); |
361 | 0 | int end = range.getCardinality(); |
362 | ||
363 | 0 | for (int i = 0; i < end; i++) { |
364 | 0 | temp.add(v11n.decodeOrdinal(start + i)); |
365 | } | |
366 | 0 | } |
367 | ||
368 | 0 | real = temp.iterator(); |
369 | 0 | } |
370 | ||
371 | /* (non-Javadoc) | |
372 | * @see java.util.Iterator#hasNext() | |
373 | */ | |
374 | public boolean hasNext() { | |
375 | 0 | return real.hasNext(); |
376 | } | |
377 | ||
378 | /* (non-Javadoc) | |
379 | * @see java.util.Iterator#next() | |
380 | */ | |
381 | public Key next() throws NoSuchElementException { | |
382 | 0 | return real.next(); |
383 | } | |
384 | ||
385 | /* (non-Javadoc) | |
386 | * @see java.util.Iterator#remove() | |
387 | */ | |
388 | public void remove() throws UnsupportedOperationException { | |
389 | 0 | 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 | 0 | private static final class VerseRangeIterator implements Iterator<VerseRange> { |
402 | /** | |
403 | * Simple ctor | |
404 | * @param it | |
405 | * @param restrict | |
406 | */ | |
407 | 0 | protected VerseRangeIterator(Iterator<VerseRange> it, RestrictionType restrict) { |
408 | 0 | this.restrict = restrict; |
409 | 0 | this.real = it; |
410 | 0 | } |
411 | ||
412 | /* (non-Javadoc) | |
413 | * @see java.util.Iterator#remove() | |
414 | */ | |
415 | public void remove() { | |
416 | 0 | throw new UnsupportedOperationException(); |
417 | } | |
418 | ||
419 | /* (non-Javadoc) | |
420 | * @see java.util.Iterator#hasNext() | |
421 | */ | |
422 | public boolean hasNext() { | |
423 | 0 | return next != null || real.hasNext(); |
424 | } | |
425 | ||
426 | /* (non-Javadoc) | |
427 | * @see java.util.Iterator#next() | |
428 | */ | |
429 | public VerseRange next() { | |
430 | 0 | if (next == null) { |
431 | 0 | next = real.next(); |
432 | } | |
433 | ||
434 | 0 | if (next == null) { |
435 | 0 | throw new NoSuchElementException(); |
436 | } | |
437 | ||
438 | // So we know what is broadly next, however the range might need | |
439 | // splitting according to restrict | |
440 | 0 | if (restrict.isSameScope(next.getVersification(), next.getStart(), next.getEnd())) { |
441 | 0 | return replyNext(); |
442 | } | |
443 | 0 | return splitNext(); |
444 | } | |
445 | ||
446 | /** | |
447 | * The next object is correct, use that one | |
448 | */ | |
449 | private VerseRange replyNext() { | |
450 | 0 | VerseRange reply = next; |
451 | 0 | next = null; |
452 | 0 | return reply; |
453 | } | |
454 | ||
455 | /** | |
456 | * The next object is too big, so cut it up | |
457 | */ | |
458 | private VerseRange splitNext() { | |
459 | 0 | Iterator<VerseRange> chop = next.rangeIterator(restrict); |
460 | 0 | VerseRange first = chop.next(); |
461 | 0 | VerseRange[] ranges = VerseRange.remainder(next, first); |
462 | ||
463 | 0 | assert ranges.length == 1; |
464 | 0 | next = ranges[0]; |
465 | ||
466 | 0 | 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 | 0 | out.defaultWriteObject(); |
497 | ||
498 | 0 | writeObjectSupport(out); |
499 | 0 | } |
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 | 0 | optimizeWrites(); |
515 | ||
516 | 0 | store = new TreeSet<VerseRange>(); |
517 | ||
518 | 0 | in.defaultReadObject(); |
519 | ||
520 | 0 | readObjectSupport(in); |
521 | 0 | } |
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 | } |