| BitwisePassage.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.BitSet;
26 import java.util.Iterator;
27 import java.util.NoSuchElementException;
28
29 import org.crosswire.jsword.versification.Versification;
30 import org.crosswire.jsword.versification.system.Versifications;
31
32 /**
33 * A Passage that is implemented using a BitSet - one for each verse. The
34 * attributes of the style are:
35 * <ul>
36 * <li>Fairly fast manipulation
37 * <li>Fairly getName()
38 * <li>Static size, poor for small Passages, good for large Passages
39 * </ul>
40 *
41 * <p>
42 * The BitSet has one more bit than the number of verses in the Bible. This
43 * would waste 1 bit per BitSet but since this doesn't cause BitSet to need an
44 * extra long it doesn't, and it saves us some maths.
45 * </p>
46 *
47 * @see gnu.lgpl.License The GNU Lesser General Public License for details.
48 * @author Joe Walker
49 * @author DM Smith
50 */
51 public class BitwisePassage extends AbstractPassage {
52 /**
53 * Create an empty BitwisePassage. There are no ctors from either Verse or
54 * VerseRange so you need to do new <code>DistinctPassage().add(...);</code>
55 *
56 * @param v11n
57 * The Versification to which this Passage belongs.
58 */
59 public BitwisePassage(Versification v11n) {
60 super(v11n);
61 store = new BitSet(v11n.maximumOrdinal() + 1);
62 }
63
64 /**
65 * Create a Verse from a human readable string. The opposite of toString(),
66 * Given any BitwisePassage v1, and the following
67 * <code>DistinctPassage v2 = new BitwisePassage(v1.toString());</code> Then
68 * <code>v1.equals(v2);</code> Theoretically, since there are many ways of
69 * representing a BitwisePassage as text string comparison along the lines
70 * of: <code>v1.toString().equals(v2.toString())</code> could be false.
71 * Practically since toString() is standardized this will be true however.
72 * We don't need to worry about thread safety in a ctor since we don't exist
73 * yet.
74 *
75 * @param v11n
76 * The Versification to which this Passage belongs.
77 * @param refs
78 * A String containing the text of the BitwisePassage
79 * @param basis
80 * The basis by which to interpret refs
81 * @throws NoSuchVerseException
82 * If the string is not parsable
83 */
84 protected BitwisePassage(Versification v11n, String refs, Key basis) throws NoSuchVerseException {
85 super(v11n, refs);
86 store = new BitSet(v11n.maximumOrdinal() + 1);
87 addVerses(refs, basis);
88 }
89
90 /**
91 * Create a Verse from a human readable string. The opposite of toString(),
92 * Given any BitwisePassage v1, and the following
93 * <code>DistinctPassage v2 = new BitwisePassage(v1.toString());</code> Then
94 * <code>v1.equals(v2);</code> Theoretically, since there are many ways of
95 * representing a BitwisePassage as text string comparison along the lines
96 * of: <code>v1.toString().equals(v2.toString())</code> could be false.
97 * Practically since toString() is standardized this will be true however.
98 * We don't need to worry about thread safety in a ctor since we don't exist
99 * yet.
100 *
101 * @param v11n
102 * The Versification to which this Passage belongs.
103 * @param refs
104 * A String containing the text of the BitwisePassage
105 * @throws NoSuchVerseException
106 * If the string is not parsable
107 */
108 protected BitwisePassage(Versification v11n, String refs) throws NoSuchVerseException {
109 this(v11n, refs, null);
110 }
111
112 @Override
113 public BitwisePassage clone() {
114 // This gets us a shallow copy
115 BitwisePassage copy = (BitwisePassage) super.clone();
116
117 copy.store = (BitSet) store.clone();
118
119 return copy;
120 }
121
122 @Override
123 public int countVerses() {
124 return store.cardinality();
125 }
126
127 @Override
128 public boolean isEmpty() {
129 return store.isEmpty();
130 }
131
132 /* (non-Javadoc)
133 * @see java.lang.Iterable#iterator()
134 */
135 public Iterator<Key> iterator() {
136 return new VerseIterator();
137 }
138
139 @Override
140 public boolean contains(Key obj) {
141 for (Key aKey : obj) {
142 Verse verse = (Verse) aKey;
143 if (!store.get(verse.getOrdinal())) {
144 return false;
145 }
146 }
147
148 return true;
149 }
150
151 /* (non-Javadoc)
152 * @see org.crosswire.jsword.passage.Passage#add(org.crosswire.jsword.passage.Key)
153 */
154 public void add(Key obj) {
155 optimizeWrites();
156
157 Verse firstVerse = null;
158 Verse lastVerse = null;
159 for (Key aKey : obj) {
160 lastVerse = (Verse) aKey;
161 if (firstVerse == null) {
162 firstVerse = lastVerse;
163 }
164 store.set(lastVerse.getOrdinal());
165 }
166
167 // we do an extra check here because the cost of calculating the
168 // params is non-zero and may be wasted
169 if (suppressEvents == 0) {
170 fireIntervalAdded(this, firstVerse, lastVerse);
171 }
172 }
173
174 /**
175 * A shortcut to adding a key, by ordinal. The ordinal needs to be taken
176 * from the same versification as the passage being created.
177 *
178 * @param ordinal
179 * the ordinal
180 */
181 public void addVersifiedOrdinal(int ordinal) {
182 optimizeWrites();
183 store.set(ordinal);
184
185 // we do an extra check here because the cost of calculating the
186 // params is non-zero and may be wasted
187 if (suppressEvents == 0) {
188 Verse verse = getVersification().decodeOrdinal(ordinal);
189 fireIntervalAdded(this, verse, verse);
190 }
191 }
192
193 /* (non-Javadoc)
194 * @see org.crosswire.jsword.passage.Passage#remove(org.crosswire.jsword.passage.Key)
195 */
196 public void remove(Key obj) {
197 optimizeWrites();
198
199 Verse firstVerse = null;
200 Verse lastVerse = null;
201 for (Key aKey : obj) {
202 lastVerse = (Verse) aKey;
203 if (firstVerse == null) {
204 firstVerse = lastVerse;
205 }
206 store.clear(lastVerse.getOrdinal());
207 }
208
209 // we do an extra check here because the cost of calculating the
210 // params is non-zero and may be wasted
211 if (suppressEvents == 0) {
212 fireIntervalAdded(this, firstVerse, lastVerse);
213 }
214 }
215
216 @Override
217 public void addAll(Key key) {
218 //check for key empty. This avoids the AIOBounds with that.getVerseAt, during event firing
219 if (key.isEmpty()) {
220 //nothing to add
221 return;
222 }
223
224 optimizeWrites();
225
226 if (key instanceof BitwisePassage) {
227 BitwisePassage thatRef = (BitwisePassage) key;
228 store.or(thatRef.store);
229 } else {
230 super.addAll(key);
231 }
232
233 // we do an extra check here because the cost of calculating the
234 // params is non-zero and may be wasted
235 if (suppressEvents == 0 && !key.isEmpty()) {
236 if (key instanceof Passage) {
237 Passage that = (Passage) key;
238 fireIntervalAdded(this, that.getVerseAt(0), that.getVerseAt(that.countVerses() - 1));
239 } else if (key instanceof VerseRange) {
240 VerseRange that = (VerseRange) key;
241 fireIntervalAdded(this, that.getStart(), that.getEnd());
242 } else if (key instanceof Verse) {
243 Verse that = (Verse) key;
244 fireIntervalAdded(this, that, that);
245 }
246 }
247 }
248
249 @Override
250 public void removeAll(Key key) {
251 optimizeWrites();
252
253 if (key instanceof BitwisePassage) {
254 BitwisePassage thatRef = (BitwisePassage) key;
255
256 store.andNot(thatRef.store);
257 } else {
258 super.removeAll(key);
259 }
260
261 // we do an extra check here because the cost of calculating the
262 // params is non-zero and may be wasted
263 if (suppressEvents == 0 && !key.isEmpty()) {
264 if (key instanceof Passage) {
265 Passage that = (Passage) key;
266 fireIntervalRemoved(this, that.getVerseAt(0), that.getVerseAt(that.countVerses() - 1));
267 } else if (key instanceof VerseRange) {
268 VerseRange that = (VerseRange) key;
269 fireIntervalRemoved(this, that.getStart(), that.getEnd());
270 } else if (key instanceof Verse) {
271 Verse that = (Verse) key;
272 fireIntervalRemoved(this, that, that);
273 }
274 }
275 }
276
277 @Override
278 public void retainAll(Key key) {
279 optimizeWrites();
280
281 BitSet thatStore = null;
282 if (key instanceof BitwisePassage) {
283 thatStore = ((BitwisePassage) key).store;
284 } else {
285 Versification v11n = getVersification();
286 thatStore = new BitSet(v11n.maximumOrdinal() + 1);
287
288 for (Key aKey : key) {
289 int ord = ((Verse) aKey).getOrdinal();
290 if (store.get(ord)) {
291 thatStore.set(ord);
292 }
293 }
294 }
295 store.and(thatStore);
296
297 fireIntervalRemoved(this, null, null);
298 }
299
300 @Override
301 public void clear() {
302 optimizeWrites();
303
304 store.clear();
305
306 fireIntervalRemoved(this, null, null);
307 }
308
309 @Override
310 public void blur(int verses, RestrictionType restrict) {
311 assert verses >= 0;
312 optimizeWrites();
313 raiseNormalizeProtection();
314
315 if (!restrict.equals(RestrictionType.NONE)) {
316 super.blur(verses, restrict);
317 } else {
318 optimizeWrites();
319 raiseEventSuppresion();
320 raiseNormalizeProtection();
321
322 int maximumOrdinal = getVersification().maximumOrdinal();
323 BitSet newStore = new BitSet(maximumOrdinal + 1);
324
325 for (int i = store.nextSetBit(0); i >= 0; i = store.nextSetBit(i + 1)) {
326 int start = Math.max(1, i - verses);
327 int end = Math.min(maximumOrdinal, i + verses);
328
329 for (int j = start; j <= end; j++) {
330 newStore.set(j);
331 }
332 }
333
334 store = newStore;
335
336 lowerNormalizeProtection();
337 if (lowerEventSuppressionAndTest()) {
338 fireIntervalAdded(this, null, null);
339 }
340 }
341 }
342
343 /**
344 * Iterate over the Verses
345 *
346 * @author Joe Walker
347 * @author DM Smith
348 */
349 private final class VerseIterator implements Iterator<Key> {
350 /**
351 * Find the first unused verse
352 */
353 VerseIterator() {
354 next = -1;
355 calculateNext();
356 }
357
358 /* (non-Javadoc)
359 * @see java.util.Iterator#hasNext()
360 */
361 public boolean hasNext() {
362 return next >= 0;
363 }
364
365 /* (non-Javadoc)
366 * @see java.util.Iterator#next()
367 */
368 public Key next() throws NoSuchElementException {
369 if (!hasNext()) {
370 throw new NoSuchElementException();
371 }
372
373 Key retcode = getVersification().decodeOrdinal(next);
374 calculateNext();
375
376 return retcode;
377 }
378
379 /* (non-Javadoc)
380 * @see java.util.Iterator#remove()
381 */
382 public void remove() throws UnsupportedOperationException {
383 store.clear(next);
384 }
385
386 /**
387 * Find the next bit
388 */
389 private void calculateNext() {
390 next = store.nextSetBit(next + 1);
391 }
392
393 /**
394 * What is the next Verse to be considered
395 */
396 private int next;
397 }
398
399 /**
400 * Call the support mechanism in AbstractPassage
401 *
402 * @param out
403 * The stream to write our state to
404 * @serialData Write the ordinal number of this verse
405 * @see AbstractPassage#writeObjectSupport(ObjectOutputStream)
406 * @throws IOException
407 * if the read fails
408 */
409 private void writeObject(ObjectOutputStream out) throws IOException {
410 out.defaultWriteObject();
411
412 // Save off the versification by name
413 out.writeUTF(getVersification().getName());
414
415 writeObjectSupport(out);
416 }
417
418 /**
419 * Call the support mechanism in AbstractPassage
420 *
421 * @param in
422 * The stream to read our state from
423 * @throws IOException
424 * if the read fails
425 * @throws ClassNotFoundException
426 * If the read data is incorrect
427 * @serialData Write the ordinal number of this verse
428 * @see AbstractPassage#readObjectSupport(ObjectInputStream)
429 */
430 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
431 optimizeWrites();
432
433 in.defaultReadObject();
434
435 // Read the versification by name
436 String v11nName = in.readUTF();
437 Versification v11n = Versifications.instance().getVersification(v11nName);
438
439 store = new BitSet(v11n.maximumOrdinal() + 1);
440
441 readObjectSupport(in);
442 }
443
444 /**
445 * To make serialization work across new versions
446 */
447 private static final long serialVersionUID = -5931560451407396276L;
448
449 /**
450 * The place the real data is stored
451 */
452 protected transient BitSet store;
453 }
454