Source code: com/eireneh/bible/passage/BitwisePassage.java
1
2 package com.eireneh.bible.passage;
3
4 import java.io.*;
5 import java.util.BitSet;
6 import java.util.Enumeration;
7 import java.util.NoSuchElementException;
8
9 import com.eireneh.util.LogicError;
10
11 /**
12 * A Passage that is implemented using a BitSet - one for each verse.
13 * The attributes of the style are:<ul>
14 * <li>Fairly fast manipulation
15 * <li>Fairly getName()
16 * <li>Static size, poor for small Passages, good for large Passages
17 * </ul>
18 *
19 * <p>There is some optimization we could do here: The benchmark I have
20 * been using spends a lot of time in VerseEnumeration. There is some
21 * inefficiency here due to having to examine the bits of the BitSet
22 * one by one, rather than being able to compare the underlying longs
23 * with zero (clearing 64 bits in one shot). This would speed up the
24 * (usual) case where there are relatively few matches in the BitSet,
25 * but be a slowdown for fuller Passages.<br />
26 * The bad news is that this would mean re-writing BitSet which I am
27 * not all that keen to do right now.</p>
28 *
29 * <p>The BitSet has one more bit than the number of verses in the
30 * Bible. This would waste 1 bit per BitSet but since this doesn't
31 * cause BitSet to need an extra long it doesn't, and it saves us some
32 * maths.</p>
33 *
34 * <table border='1' cellPadding='3' cellSpacing='0' width="100%">
35 * <tr><td bgColor='white'class='TableRowColor'><font size='-7'>
36 * Distribution Licence:<br />
37 * Project B is free software; you can redistribute it
38 * and/or modify it under the terms of the GNU General Public License,
39 * version 2 as published by the Free Software Foundation.<br />
40 * This program is distributed in the hope that it will be useful,
41 * but WITHOUT ANY WARRANTY; without even the implied warranty of
42 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
43 * General Public License for more details.<br />
44 * The License is available on the internet
45 * <a href='http://www.gnu.org/copyleft/gpl.html'>here</a>, by writing to
46 * <i>Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
47 * MA 02111-1307, USA</i>, Or locally at the Licence link below.<br />
48 * The copyright to this program is held by it's authors.
49 * </font></td></tr></table>
50 * @see <a href='http://www.eireneh.com/servlets/Web'>Project B Home</a>
51 * @see docs.Licence
52 * @author Joe Walker
53 * @stereotype container
54 * @version $Id:$
55 */
56 public class BitwisePassage extends AbstractPassage
57 {
58 /**
59 * Create an empty BitwisePassage. There are no ctors from either Verse
60 * or VerseRange so you need to do new <code>DistinctPassage().add(...);</code>
61 */
62 protected BitwisePassage()
63 {
64 }
65
66 /**
67 * Create a Verse from a human readable string. The opposite
68 * of toString(), Given any BitwisePassage v1, and the following
69 * <code>DistinctPassage v2 = new BitwisePassage(v1.toString());</code>
70 * Then <code>v1.equals(v2);</code>
71 * Theoretically, since there are many ways of representing a BitwisePassage as text
72 * string comparision along the lines of:
73 * <code>v1.toString().equals(v2.toString())</code> could be false.
74 * Practically since toString() is standardized this will be true however.
75 * We don't need to worry about thread safety in a ctor since we don't exist yet.
76 * @param refs A String containing the text of the BitwisePassage
77 * @throws NoSuchVerseException If the string is not parsable
78 */
79 protected BitwisePassage(String refs) throws NoSuchVerseException
80 {
81 super(refs);
82 addVerses(refs);
83 }
84
85 /**
86 * Get a copy of ourselves. Points to note:
87 * Call clone() not new() on member Objects, and on us.
88 * Do not use Copy Constructors! - they do not inherit well.
89 * Think about this needing to be synchronized
90 * If this is not cloneable then writing cloneable children is harder
91 * @return A complete copy of ourselves
92 * @exception java.lang.CloneNotSupportedException We don't do this but our kids might
93 */
94 public Object clone() throws CloneNotSupportedException
95 {
96 // This gets us a shallow copy
97 BitwisePassage copy = (BitwisePassage) super.clone();
98
99 copy.store = (BitSet) store.clone();
100
101 return copy;
102 }
103
104 /**
105 * @return the number of Verses in this Passage
106 */
107 public int countVerses()
108 {
109 int count = 0;
110
111 int vib = Books.versesInBible();
112 for (int i=1; i<=vib; i++)
113 if (store.get(i)) count++;
114
115 return count;
116 }
117
118 /**
119 * @returns true if this Passage contains no Verses
120 */
121 public boolean isEmpty()
122 {
123 int vib = Books.versesInBible();
124 for (int i=1; i<=vib; i++)
125 if (store.get(i)) return false;
126
127 return true;
128 }
129
130 /**
131 * Iterate over the Verses
132 * @return A list enumerator
133 */
134 public Enumeration verseElements()
135 {
136 return new VerseEnumeration();
137 }
138
139 /**
140 * Enumerate over the VerseRanges
141 * @return A list enumerator
142 */
143 public Enumeration rangeElements()
144 {
145 return new VerseRangeEnumeration();
146 }
147
148 /**
149 * Returns true if this Passage contains the specified Verse
150 * @param obj Verse whose presence in this Passage is to be tested
151 * @return true if this Passage contains the specified Verse
152 */
153 public boolean contains(VerseBase obj)
154 {
155 Verse[] verses = toVerseArray(obj);
156
157 for (int i=0; i<verses.length; i++)
158 {
159 if (!store.get(verses[i].getOrdinal()))
160 return false;
161 }
162
163 return true;
164 }
165
166 /**
167 * Ensures that this Passage contains the specified Verse
168 * @param obj Verse whose presence in this Passage is to be ensured
169 */
170 public void add(VerseBase obj)
171 {
172 optimizeWrites();
173
174 Verse[] verses = toVerseArray(obj);
175
176 for (int i=0; i<verses.length; i++)
177 {
178 store.set(verses[i].getOrdinal());
179 }
180
181 // we do an extra check here because the cost of calculating the
182 // params is non-zero an may be wasted
183 if (suppress_events == 0)
184 fireIntervalAdded(this, verses[0], verses[verses.length-1]);
185 }
186
187 /**
188 * Removes a single instance of the specified Verse from this Passage
189 * @param obj Verse to be removed from this Passage, if present
190 */
191 public void remove(VerseBase obj)
192 {
193 optimizeWrites();
194
195 Verse[] verses = toVerseArray(obj);
196
197 for (int i=0; i<verses.length; i++)
198 store.clear(verses[i].getOrdinal());
199
200 // we do an extra check here because the cost of calculating the
201 // params is non-zero an may be wasted
202 if (suppress_events == 0)
203 fireIntervalRemoved(this, verses[0], verses[verses.length-1]);
204 }
205
206 /**
207 * Adds the Verses in that Passage to this Passage
208 * @param that Verses to be added to this Passage
209 */
210 public void addAll(Passage that)
211 {
212 optimizeWrites();
213
214 if (that instanceof BitwisePassage)
215 {
216 BitwisePassage that_ref = (BitwisePassage) that;
217 store.or(that_ref.store);
218 }
219 else
220 {
221 super.addAll(that);
222 }
223
224 // we do an extra check here because the cost of calculating the
225 // params is non-zero an may be wasted
226 if (suppress_events == 0)
227 fireIntervalAdded(this, that.getVerseAt(0), that.getVerseAt(that.countVerses()-1));
228 }
229
230 /**
231 * Removes the Verses in this Passage that are contained in the
232 * specified Passage. In other words, removes from this Passage
233 * all of its Verses that are not contained in the specified Passage
234 * @param that Verses to be removed from this Passage
235 */
236 public void removeAll(Passage that)
237 {
238 optimizeWrites();
239
240 if (that instanceof BitwisePassage)
241 {
242 BitwisePassage that_ref = (BitwisePassage) that;
243
244 // We'd like to use store.andNot(that_ref.store); which would
245 // probably be quicker (they can work on the longs) but it is
246 // not available on JDK 1.1
247 int vib = Books.versesInBible();
248 for (int i=1; i<=vib; i++)
249 if (that_ref.store.get(i)) store.clear(i);
250 }
251 else
252 {
253 super.removeAll(that);
254 }
255
256 // we do an extra check here because the cost of calculating the
257 // params is non-zero an may be wasted
258 if (suppress_events == 0)
259 fireIntervalRemoved(this, that.getVerseAt(0), that.getVerseAt(that.countVerses()-1));
260 }
261
262 /**
263 * Retains only the Verses in this Passage that are contained in the
264 * specified Passage. In other words, removes from this Passage
265 * all of its Verses that are not contained in the specified Passage
266 * @param that Verses to be retained in this Passage.
267 */
268 public void retainAll(Passage that)
269 {
270 optimizeWrites();
271
272 if (that instanceof BitwisePassage)
273 {
274 BitSet that_store = ((BitwisePassage) that).store;
275 store.and(that_store);
276 }
277 else
278 {
279 BitSet new_store = new BitSet(Books.versesInBible());
280
281 Enumeration en = that.verseElements();
282 while (en.hasMoreElements())
283 {
284 int ord = ((Verse) en.nextElement()).getOrdinal();
285 if (store.get(ord))
286 new_store.set(ord);
287 }
288
289 store = new_store;
290 }
291
292 fireIntervalRemoved(this, null, null);
293 }
294
295 /**
296 * Removes all of the Verses from this Passage
297 */
298 public void clear()
299 {
300 optimizeWrites();
301
302 int vib = Books.versesInBible();
303 for (int i=1; i<=vib; i++)
304 {
305 store.clear(i);
306 }
307
308 fireIntervalRemoved(this, null, null);
309 }
310
311 /**
312 * Widen the range of the verses in this list. This is primarily for
313 * "find x within n verses of y" type applications.
314 * @param verses The number of verses to widen by
315 * @param restrict How should we restrict the blurring?
316 * @exception java.lang.IllegalArgumentException If a blurring is negative or the restrict mode is illegal
317 * @see Passage
318 */
319 public void blur(int verses, int restrict)
320 {
321 optimizeWrites();
322 raiseNormalizeProtection();
323
324 if (verses < 0)
325 throw new IllegalArgumentException(PassageUtil.getResource("bitwise_error_blur"));
326
327 if (restrict != RESTRICT_NONE)
328 {
329 // This is a bit of a cheat, but there is no way I'm going
330 // to do the maths to speed up the restricted version
331 try
332 {
333 BitwisePassage temp = (BitwisePassage) this.clone();
334 Enumeration en = temp.rangeElements();
335
336 while (en.hasMoreElements())
337 {
338 VerseRange range = new VerseRange((VerseRange) en.nextElement(), verses, verses, restrict);
339 add(range);
340 }
341 }
342 catch (CloneNotSupportedException ex)
343 {
344 throw new LogicError(ex);
345 }
346 }
347 else
348 {
349 BitSet new_store = new BitSet(Books.versesInBible());
350
351 int vib = Books.versesInBible();
352 for (int i=1; i<=vib; i++)
353 {
354 if (store.get(i))
355 {
356 int start = Math.max(0, i-verses);
357 int end = Math.min(Books.versesInBible(), i+verses);
358
359 for (int j=start; j<=end; j++)
360 new_store.set(j);
361 }
362 }
363
364 store = new_store;
365 }
366
367 lowerNormalizeProtection();
368 fireIntervalAdded(this, null, null);
369 }
370
371 /**
372 * Iterate over the Verses
373 * @author Joe Walker
374 */
375 private final class VerseEnumeration implements Enumeration
376 {
377 /** Find the first unused verse */
378 public VerseEnumeration()
379 {
380 calculateNext();
381 }
382
383 /** Returns true if the iteration has more Verses */
384 public boolean hasMoreElements()
385 {
386 return next <= Books.versesInBible();
387 }
388
389 /** Returns the next Verse in the interation */
390 public Object nextElement() throws NoSuchElementException
391 {
392 try
393 {
394 if (next > Books.versesInBible()) throw new NoSuchElementException();
395
396 Object retcode = new Verse(next);
397 calculateNext();
398
399 return retcode;
400 }
401 catch (NoSuchVerseException ex)
402 {
403 throw new LogicError(ex);
404 }
405 }
406
407 /** Find the next bit */
408 private void calculateNext()
409 {
410 while (next <= Books.versesInBible())
411 {
412 next++;
413 if (store.get(next)) break;
414 }
415 }
416
417 /** What is the next Verse to be considered */
418 private int next = 0;
419 }
420
421 /**
422 * Call the support mechanism in AbstractPassage
423 * @param out The stream to write our state to
424 * @serialData Write the ordinal number of this verse
425 * @see AbstractPassage#writeObjectSupport(ObjectOutputStream)
426 */
427 private void writeObject(ObjectOutputStream out) throws IOException
428 {
429 writeObjectSupport(out);
430 }
431
432 /**
433 * Call the support mechanism in AbstractPassage
434 * @param in The stream to read our state from
435 * @serialData Write the ordinal number of this verse
436 * @see AbstractPassage#readObjectSupport(ObjectInputStream)
437 */
438 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException
439 {
440 optimizeWrites();
441
442 store = new BitSet(Books.versesInBible()+1);
443 readObjectSupport(in);
444 }
445
446 /** To make serialization work across new versions */
447 static final long serialVersionUID = -5931560451407396276L;
448
449 /** The place the real data is stored */
450 private transient BitSet store = new BitSet(Books.versesInBible()+1);
451 }