| PassageTally.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: PassageTally.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.common.util.Logger;
33 import org.crosswire.jsword.JSOtherMsg;
34 import org.crosswire.jsword.versification.Versification;
35
36 /**
37 * Similar to a Passage, but that stores a ranking for each of the Verses that
38 * it contains.
39 *
40 * <p>
41 * Currently there is no well defined spec for what the rank of a verse means -
42 * it is just an int. Since this number is exposed in 2 places
43 * (getNameAndTally() and getTallyFor()) we should specify what the numbers
44 * mean. Trouble is most tallies come from searches where the numbers only have
45 * relative meaning.
46 * </p>
47 *
48 * <p>
49 * This class exactly implements the Passage interface when the ordering is set
50 * to Order.BIBLICAL, however an additional setting of Order.TALLY sorts the
51 * verses by the rank in this tally.
52 *
53 * <p>
54 * Calling <code>tally.add(Gen 1:1); tally.add(Gen 1:1);</code> is redundant for
55 * a Passage however a PassageTally will increase the rank of Gen 1:1, there are
56 * additional methods <code>unAdd()</code> and <code>unAddAll()</code> that do
57 * the reverse, of decreasing the rank of the specified verse(s).
58 * </p>
59 *
60 * <p>
61 * The point is to allow a search for
62 * "God loves us, and gave Jesus to die to save us" to correctly identify John
63 * 3:16. So we are using fuzzy matching big style, but I think this will be very
64 * useful.
65 * </p>
66 *
67 * <p>
68 * How should we rank VerseRanges? We could use a sum of the ranks of the verses
69 * in a range or the maximum value of a range. The former would seem to be more
70 * mathematically correct, but I think that the latter is better because: the
71 * concept of max value is preserved, because a wide blurred match is generally
72 * not as good as a sharply defined one.
73 * </p>
74 *
75 * <p>
76 * Should we be going for a PassageTallyFactory type approach? Of the 3
77 * implementations of Passage, The RangedPassage does not make sense here, and a
78 * PassageTally will not have the range of uses that a Passage has, so I think
79 * there is more likely to be a correct answer. So right now the answer is no.
80 * </p>
81 *
82 * <p>
83 * Memory considerations: The BitSet approach will always use a
84 * <code>int[31000]</code> = 128k of memory.<br />
85 * The Distinct approach will be n * int[4] where n is the number of verses
86 * stored. I expect most searches to have at least n=1000. Also 128k<br />
87 * Given this, (A Distinct style PassageTally will usually use more memory than
88 * a BitSet style PassageTally) And the intuitive result that the BitSet will be
89 * faster, I'm going to start by implementing the latter only.
90 * </p>
91 *
92 * <p>
93 * To think about - I've upped the MAX_TALLY to 20000 to help the new mapper
94 * program. I'm not sure why it was originally 100?
95 *
96 * <p>
97 * LATER(joe): Specify how passage ranks work.
98 *
99 * @see gnu.lgpl.License for license details.<br>
100 * The copyright to this program is held by it's authors.
101 * @author Joe Walker [joe at eireneh dot com]
102 */
103 public class PassageTally extends AbstractPassage {
104 /**
105 * Create an empty PassageTally
106 *
107 * @param v11n
108 * The Versification to which this Passage belongs.
109 */
110 public PassageTally(Versification v11n) {
111 super(v11n);
112 board = new int[v11n.maximumOrdinal() + 1];
113 }
114
115 /**
116 * Create a Verse from a human readable string. The opposite of toString()
117 *
118 * @param v11n
119 * The Versification to which this Passage belongs.
120 * @param refs
121 * The text to interpret
122 * @throws NoSuchVerseException
123 * If refs is invalid
124 */
125 public PassageTally(Versification v11n, String refs) throws NoSuchVerseException {
126 super(v11n, refs);
127 board = new int[v11n.maximumOrdinal() + 1];
128 addVerses(refs);
129 }
130
131 @Override
132 public boolean isEmpty() {
133 return size == 0;
134 }
135
136 @Override
137 public int countVerses() {
138 return size;
139 }
140
141 /**
142 * Set how we sort the verses we output. The options are:
143 * <ul>
144 * <li>Order.BIBLICAL: Natural Biblical order</li>
145 * <li>Order.TALLY: In an order specified by this class</li>
146 * </ul>
147 *
148 * @param order
149 * the sort order
150 */
151 public void setOrdering(Order order) {
152 this.order = order;
153 }
154
155 /**
156 * Get how we sort the verses we output.
157 *
158 * @return the sort order
159 */
160 public Order getOrdering() {
161 return order;
162 }
163
164 /**
165 * @return the total
166 */
167 public int getTotal() {
168 return total;
169 }
170
171 /**
172 * @param total
173 * the total to set
174 */
175 public void setTotal(int total) {
176 this.total = total;
177 }
178
179 @Override
180 public PassageTally clone() {
181 // This gets us a shallow copy
182 PassageTally copy = (PassageTally) super.clone();
183
184 copy.board = board.clone();
185
186 return copy;
187 }
188
189 @Override
190 public String toString() {
191 return getName(0);
192 }
193
194 @Override
195 public String getName() {
196 return getName(0);
197 }
198
199 /**
200 * A Human readable version of the verse list. Uses short books names, and
201 * the shortest possible rendering eg "Mat 3:1-4, 6"
202 *
203 * @param cnt
204 * The number of matches to return, 0 gives all matches
205 * @return a String containing a description of the verses
206 */
207 public String getName(int cnt) {
208 int max_count = cnt;
209 if (PassageUtil.isPersistentNaming() && originalName != null) {
210 return originalName;
211 }
212
213 StringBuilder retcode = new StringBuilder();
214
215 if (order == Order.BIBLICAL) {
216 Iterator<Key> it = rangeIterator(RestrictionType.NONE);
217 Verse current = null;
218 while (it.hasNext()) {
219 VerseRange range = (VerseRange) it.next();
220 retcode.append(range.getName(current));
221
222 if (it.hasNext()) {
223 retcode.append(AbstractPassage.REF_PREF_DELIM);
224 }
225
226 current = range.getStart();
227 }
228 } else {
229 if (max_count == 0) {
230 max_count = Integer.MAX_VALUE;
231 }
232
233 Iterator<Key> it = new OrderedVerseIterator(getVersification(), board);
234 Key current = null;
235 int count = 0;
236
237 while (it.hasNext() && count < max_count) {
238 Key verse = it.next();
239 retcode.append(verse.getName(current));
240
241 current = verse;
242 count++;
243
244 if (it.hasNext() && count < max_count) {
245 retcode.append(AbstractPassage.REF_PREF_DELIM);
246 }
247 }
248 }
249
250 return retcode.toString();
251 }
252
253 /**
254 * A Human readable version of the PassageTally. Uses short books names, and
255 * the shortest possible rendering eg "Mat 3:1-4"
256 *
257 * @return a String containing a description of the verses
258 */
259 public String getNameAndTally() {
260 return getNameAndTally(0);
261 }
262
263 /**
264 * A Human readable version of the PassageTally. Uses short books names, and
265 * the shortest possible rendering eg "Mat 3:1-4"
266 *
267 * @param cnt
268 * The number of matches to return, 0 gives all matches
269 * @return a String containing a description of the verses
270 */
271 public String getNameAndTally(int cnt) {
272 int max_count = cnt;
273 StringBuilder retcode = new StringBuilder();
274 if (max_count == 0) {
275 max_count = Integer.MAX_VALUE;
276 }
277
278 OrderedVerseIterator it = new OrderedVerseIterator(getVersification(), board);
279 int count = 0;
280
281 while (it.hasNext() && count < max_count) {
282 Key verse = it.next();
283 retcode.append(verse.getName());
284 retcode.append(" (");
285 retcode.append(100 * it.lastRank() / max);
286 retcode.append("%)");
287
288 count++;
289
290 if (it.hasNext() && count < max_count) {
291 retcode.append(AbstractPassage.REF_PREF_DELIM);
292 }
293 }
294
295 return retcode.toString();
296 }
297
298 /**
299 * Iterate through the verse elements in the current sort order
300 *
301 * @return A verse Iterator
302 */
303 public Iterator<Key> iterator() {
304 if (order == Order.BIBLICAL) {
305 return new VerseIterator();
306 }
307 return new OrderedVerseIterator(getVersification(), board);
308 }
309
310 @Override
311 public Iterator<Key> rangeIterator(RestrictionType restrict) {
312 if (order == Order.BIBLICAL) {
313 return new VerseRangeIterator(getVersification(), iterator(), restrict);
314 }
315 return new OrderedVerseRangeIterator(getVersification(), iterator(), board);
316 }
317
318 /**
319 * Does this tally contain all the specified verses?
320 *
321 * @param that
322 * The verses to test for
323 * @return true if all the verses exist in this tally
324 */
325 @Override
326 public boolean contains(Key that) {
327 Versification v11n = getVersification();
328 for (Key aKey : that) {
329 Verse verse = (Verse) aKey;
330 if (board[v11n.getOrdinal(verse)] == 0) {
331 return false;
332 }
333 }
334
335 return true;
336 }
337
338 /**
339 * The ranking given to a specific verse
340 *
341 * @param verse
342 * The verse to get the ranking of
343 * @return The rank of the verse in question
344 */
345 public int getTallyOf(Verse verse) {
346 Versification v11n = getVersification();
347 return board[v11n.getOrdinal(verse)];
348 }
349
350 /**
351 * What is the index of the give verse in the current ordering scheme
352 *
353 * @param verse
354 * The verse to get the index of
355 * @return The index of the verse or -1 if the verse was not found
356 */
357 public int getIndexOf(Verse verse) {
358 Versification v11n = getVersification();
359 int pos = v11n.getOrdinal(verse);
360 int tally = board[pos];
361 return tally > 0 ? pos : -1;
362 }
363
364 /**
365 * Add/Increment this verses in the rankings
366 *
367 * @param that
368 * The verses to add/increment
369 */
370 public void add(Key that) {
371 optimizeWrites();
372
373 alterVerseBase(that, 1);
374 fireIntervalAdded(this, null, null);
375 }
376
377 /**
378 * DONT USE THIS. It makes public something of the ratings scheme which is
379 * not generally recommended. This method is likely to be removed at a
380 * moments notice, and it only here to keep Mapper happy. Add/Increment this
381 * verses in the rankings
382 *
383 * @param that
384 * The verses to add/increment
385 * @param count
386 * The amount to increment by
387 */
388 public void add(Key that, int count) {
389 optimizeWrites();
390
391 alterVerseBase(that, count);
392 fireIntervalAdded(this, null, null);
393 }
394
395 /**
396 * Remove/Decrement this verses in the rankings
397 *
398 * @param that
399 * The verses to remove/decrement
400 */
401 public void unAdd(Key that) {
402 optimizeWrites();
403
404 alterVerseBase(that, -1);
405 fireIntervalRemoved(this, null, null);
406 }
407
408 /**
409 * Remove these verses from the rankings, ie, set their rank to zero.
410 *
411 * @param that
412 * The verses to remove/decrement
413 */
414 public void remove(Key that) {
415 Versification v11n = getVersification();
416 optimizeWrites();
417
418 for (Key aKey : that) {
419 Verse verse = (Verse) aKey;
420 kill(v11n.getOrdinal(verse));
421 }
422
423 fireIntervalRemoved(this, null, null);
424 }
425
426 @Override
427 public void addAll(Key that) {
428 Versification v11n = getVersification();
429 optimizeWrites();
430
431 if (that instanceof PassageTally) {
432 PassageTally that_rt = (PassageTally) that;
433
434 int vib = getVersification().maximumOrdinal();
435 for (int i = 0; i <= vib; i++) {
436 increment(i, that_rt.board[i]);
437 }
438
439 incrementMax(that_rt.max);
440 } else {
441 for (Key aKey : that) {
442 Verse verse = (Verse) aKey;
443 increment(v11n.getOrdinal(verse), 1);
444 }
445
446 incrementMax(1);
447 }
448
449 fireIntervalAdded(this, null, null);
450 }
451
452 /**
453 * Remove/Decrement these verses in the rankings
454 *
455 * @param that
456 * The verses to remove/decrement
457 */
458 public void unAddAll(Passage that) {
459 Versification v11n = getVersification();
460 optimizeWrites();
461
462 if (that instanceof PassageTally) {
463 PassageTally that_rt = (PassageTally) that;
464
465 int vib = getVersification().maximumOrdinal();
466 for (int i = 0; i <= vib; i++) {
467 increment(i, -that_rt.board[i]);
468 }
469 } else {
470 for (Key aKey : that) {
471 Verse verse = (Verse) aKey;
472 increment(v11n.getOrdinal(verse), -1);
473 }
474 }
475
476 fireIntervalRemoved(this, null, null);
477
478 // Just because we've decremented some doesn't
479 // change the max. So we don't need to do:
480 // incrementMax(-1);
481 }
482
483 @Override
484 public void removeAll(Key key) {
485 Versification v11n = getVersification();
486 Passage that = KeyUtil.getPassage(key);
487
488 optimizeWrites();
489
490 if (that instanceof PassageTally) {
491 PassageTally that_rt = (PassageTally) that;
492
493 int vib = getVersification().maximumOrdinal();
494 for (int i = 0; i <= vib; i++) {
495 if (that_rt.board[i] != 0) {
496 kill(i);
497 }
498 }
499 } else {
500 for (Key aKey : that) {
501 Verse verse = (Verse) aKey;
502 kill(v11n.getOrdinal(verse));
503 }
504 }
505
506 fireIntervalRemoved(this, null, null);
507
508 // Just because we've decremented some doesn't
509 // change the max. So we don't need to do:
510 // incrementMax(-1);
511 }
512
513 @Override
514 public void clear() {
515 optimizeWrites();
516
517 for (int i = 0; i < board.length; i++) {
518 board[i] = 0;
519 }
520
521 size = 0;
522
523 fireIntervalRemoved(this, null, null);
524 }
525
526 /**
527 * Ensures that there are a maximum of <code>count</code> Verses in this
528 * Passage. If there were more than <code>count</code> Verses then a new
529 * Passage is created containing the Verses from <code>count</code> + 1
530 * onwards. If there was not greater than <code>count</code> in the Passage,
531 * then the passage remains unchanged, and null is returned.
532 *
533 * @param count
534 * The maximum number of Verses to allow in this collection
535 * @return A new Passage containing the remaining verses or null
536 * @see Verse
537 */
538 @Override
539 public Passage trimVerses(int count) {
540 optimizeWrites();
541
542 int i = 0;
543 boolean overflow = false;
544
545 Passage remainder = this.clone();
546
547 for (Key verse : this) {
548 if (i > count) {
549 remove(verse);
550 overflow = true;
551 } else {
552 remainder.remove(verse);
553 }
554
555 i++;
556 }
557
558 if (overflow) {
559 return remainder;
560 }
561 return null;
562 }
563
564 /**
565 * Take the verses in the tally and give them all and equal rank of 1. After
566 * this method has executed then both sorting methods for a.
567 */
568 public void flatten() {
569 optimizeWrites();
570
571 for (int i = 0; i < board.length; i++) {
572 if (board[i] != 0) {
573 board[i] = 1;
574 }
575 }
576
577 max = 1;
578 }
579
580 @Override
581 public void blur(int verses, RestrictionType restrict) {
582 assert verses > 0;
583
584 optimizeWrites();
585 raiseEventSuppresion();
586 raiseNormalizeProtection();
587
588 if (!restrict.equals(RestrictionType.NONE)) {
589 log.warn("Restrict=" + restrict + " is not properly supported.");
590
591 // This is a bit of a cheat, but there is no way I'm going
592 // to do the math to speed up the restricted version
593 PassageTally temp = this.clone();
594 Iterator<Key> it = temp.rangeIterator(RestrictionType.NONE);
595
596 while (it.hasNext()) {
597 VerseRange range = (VerseRange) it.next();
598 for (int i = 0; i <= verses; i++) {
599 add(restrict.blur(getVersification(), range, i, i));
600 }
601 }
602 } else {
603 int[] new_board = new int[board.length];
604
605 for (int i = 0; i < board.length; i++) {
606 if (board[i] != 0) {
607 // This could be re-written more simply:
608 // for (int j = -verses; j <= verses; j++) {
609 // int k = i + j;
610 // if (k >= 0 && k <= BibleInfo.maximumOrdinal()) {
611 // new_board[k] += board[i] + verses - mod(j);
612 // }
613 // }
614 // However splitting the loop in 2 will speed it up quite a bit.
615
616 for (int j = -verses; j < 0; j++) {
617 int k = i + j;
618 if (k >= 0) {
619 new_board[k] += board[i] + verses + j;
620 }
621 }
622
623 new_board[i] += board[i] + verses;
624
625 for (int j = 1; j <= verses; j++) {
626 int k = i + j;
627 if (k < board.length - 1) {
628 new_board[k] += board[i] + verses - j;
629 }
630 }
631 }
632 }
633
634 board = new_board;
635 }
636
637 resetMax();
638
639 lowerNormalizeProtection();
640 if (lowerEventSuppresionAndTest()) {
641 fireIntervalAdded(this, null, null);
642 }
643 }
644
645 /**
646 * Sometimes we end up not knowing what the max is - this makes sure we know
647 * accurately. Same with size.
648 */
649 private void resetMax() {
650 optimizeWrites();
651
652 max = 0;
653 size = 0;
654 for (int i = 0; i < board.length; i++) {
655 if (board[i] > 0) {
656 size++;
657 }
658 if (board[i] > max) {
659 max = board[i];
660 }
661 }
662 }
663
664 /**
665 * Increment/Decrement this verses in the rankings
666 *
667 * @param that
668 * The verses to add/increment
669 * @param tally
670 * The amount to increment/decrement by
671 */
672 private void alterVerseBase(Key that, int tally) {
673 Versification v11n = getVersification();
674 for (Key aKey : that) {
675 Verse verse = (Verse) aKey;
676 increment(v11n.getOrdinal(verse), tally);
677 }
678
679 if (tally > 0) {
680 incrementMax(tally);
681 }
682 }
683
684 /**
685 * Increment a verse by an amount
686 *
687 * @param ord
688 * The verse to increment
689 * @param tally
690 * The amount to increase by
691 */
692 private void increment(int ord, int tally) {
693 boolean exists = board[ord] > 0;
694 board[ord] += tally;
695 if (board[ord] > MAX_TALLY) {
696 board[ord] = MAX_TALLY;
697 }
698 if (board[ord] < 0) {
699 board[ord] = 0;
700 }
701
702 // Recompute the size
703 if (exists && board[ord] == 0) {
704 size--;
705 } else if (!exists && board[ord] > 0) {
706 size++;
707 }
708 }
709
710 /**
711 * Increment a verse by an amount
712 *
713 * @param tally
714 * The amount to increase by
715 */
716 private void incrementMax(int tally) {
717 max += tally;
718 if (max > MAX_TALLY) {
719 max = MAX_TALLY;
720 }
721 if (max < 0) {
722 max = 0;
723 }
724 }
725
726 /**
727 * Wipe the rank of the given verse to zero
728 *
729 * @param ord
730 * The verse to increment
731 */
732 private void kill(int ord) {
733 if (board[ord] > 0) {
734 size--;
735 }
736
737 board[ord] = 0;
738 }
739
740 /**
741 * Call the support mechanism in AbstractPassage
742 *
743 * @param out
744 * The stream to write our state to
745 * @serialData Write the ordinal number of this verse
746 * @see AbstractPassage#writeObjectSupport(ObjectOutputStream)
747 * @throws IOException
748 * if the read fails
749 */
750 private void writeObject(ObjectOutputStream out) throws IOException {
751 out.defaultWriteObject();
752
753 writeObjectSupport(out);
754 }
755
756 /**
757 * Call the support mechanism in AbstractPassage
758 *
759 * @param in
760 * The stream to read our state from
761 * @throws IOException
762 * if the read fails
763 * @throws ClassNotFoundException
764 * If the read data is incorrect
765 * @serialData Write the ordinal number of this verse
766 * @see AbstractPassage#readObjectSupport(ObjectInputStream)
767 */
768 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
769 optimizeWrites();
770
771 in.defaultReadObject();
772
773 readObjectSupport(in);
774 }
775
776 /**
777 * Indicates how this PassageTally is to order it's Verses.
778 */
779 public enum Order {
780 /**
781 * Sort in Biblical order
782 */
783 BIBLICAL,
784
785 /**
786 * Sort in tally rank order
787 */
788 TALLY
789 }
790
791 /**
792 * The highest tally possible
793 */
794 public static final int MAX_TALLY = 20000;
795
796 /*
797 * The number of verses in the tally.
798 */
799 private int size;
800
801 /*
802 * The total number of verses that this tally represents.
803 */
804 private int total;
805
806 /**
807 * The tally board itself
808 */
809 protected int[] board;
810
811 /**
812 * The maximum tally possible
813 */
814 private int max;
815
816 /**
817 * The maximum tally possible
818 */
819 private Order order = Order.BIBLICAL;
820
821 /**
822 * The log stream
823 */
824 private static final Logger log = Logger.getLogger(PassageTally.class);
825
826 /**
827 * Serialization ID
828 */
829 private static final long serialVersionUID = 3761128240928274229L;
830
831 /**
832 * Iterate over the Verses in normal verse order
833 *
834 * @author Joe Walker
835 */
836 private final class VerseIterator implements Iterator<Key> {
837 /**
838 * Find the first unused verse
839 */
840 public VerseIterator() {
841 calculateNext();
842 }
843
844 /* (non-Javadoc)
845 * @see java.util.Iterator#hasNext()
846 */
847 public boolean hasNext() {
848 return next <= board.length - 1;
849 }
850
851 /* (non-Javadoc)
852 * @see java.util.Iterator#next()
853 */
854 public Key next() throws NoSuchElementException {
855 if (next >= board.length) {
856 throw new NoSuchElementException();
857 }
858
859 Key retcode = getVersification().decodeOrdinal(next);
860 calculateNext();
861
862 return retcode;
863 }
864
865 /* (non-Javadoc)
866 * @see java.util.Iterator#remove()
867 */
868 public void remove() throws UnsupportedOperationException {
869 throw new UnsupportedOperationException();
870 }
871
872 /**
873 * Find the next bit
874 */
875 private void calculateNext() {
876 do {
877 next++;
878 } while (next < board.length && board[next] == 0);
879 }
880
881 /** What is the next Verse to be considered */
882 private int next;
883 }
884
885 /**
886 * Iterate over the Verses in order of their rank in the tally
887 *
888 * @author Joe Walker
889 */
890 private static final class OrderedVerseIterator implements Iterator<Key> {
891 /**
892 * Find the first unused verse
893 */
894 protected OrderedVerseIterator(Versification v11n, int[] board) {
895 referenceSystem = v11n;
896 TreeSet<TalliedVerse> output = new TreeSet<TalliedVerse>();
897
898 int vib = board.length - 1;
899 for (int i = 0; i <= vib; i++) {
900 if (board[i] != 0) {
901 output.add(new TalliedVerse(i, board[i]));
902 }
903 }
904
905 it = output.iterator();
906 last = null;
907 }
908
909 /* (non-Javadoc)
910 * @see java.util.Iterator#hasNext()
911 */
912 public boolean hasNext() {
913 return it.hasNext();
914 }
915
916 /* (non-Javadoc)
917 * @see java.util.Iterator#next()
918 */
919 public Key next() throws NoSuchElementException {
920 last = it.next();
921 return referenceSystem.decodeOrdinal(last.ord);
922 }
923
924 /* (non-Javadoc)
925 * @see java.util.Iterator#remove()
926 */
927 public void remove() throws UnsupportedOperationException {
928 throw new UnsupportedOperationException();
929 }
930
931 /**
932 * @return the next Verse in the iteration
933 * @throws NoSuchElementException
934 * if hasNext() == false
935 */
936 public int lastRank() throws NoSuchElementException {
937 if (last != null) {
938 return last.tally;
939 }
940 throw new NoSuchElementException(JSOtherMsg.lookupText("nextElement() has not been called yet."));
941 }
942
943 /**
944 * The Versification is needed to decode board positions.
945 */
946 private Versification referenceSystem;
947 /**
948 * So that we can get at the ranking of the given verse
949 */
950 private TalliedVerse last;
951
952 /**
953 * The Iterator we are converting
954 */
955 private Iterator<TalliedVerse> it;
956 }
957
958 /**
959 * Hack to make this work with J2SE 1.1 as well as J2SE 1.2 This compared 2
960 * Integers
961 */
962 private static class TalliedVerse implements Comparable<TalliedVerse> {
963 /**
964 * Convenience ctor to set the public variables
965 *
966 * @param ord
967 * the verse id
968 * @param tally
969 * the rank of the verse
970 */
971 public TalliedVerse(int ord, int tally) {
972 this.ord = ord;
973 this.tally = tally;
974 }
975
976 @Override
977 public int hashCode() {
978 int result = 31 + ord;
979 return 31 * result + tally;
980 }
981
982 @Override
983 public boolean equals(Object obj) {
984 if (this == obj) {
985 return true;
986 }
987 if (obj == null) {
988 return false;
989 }
990 if (getClass() != obj.getClass()) {
991 return false;
992 }
993 final TalliedVerse other = (TalliedVerse) obj;
994 if (tally != other.tally) {
995 return false;
996 }
997 if (ord != other.ord) {
998 return false;
999 }
1000 return true;
1001 }
1002
1003 /* (non-Javadoc)
1004 * @see java.lang.Comparable#compareTo(java.lang.Object)
1005 */
1006 public int compareTo(TalliedVerse that) {
1007 if (that.tally == this.tally) {
1008 return this.ord - that.ord;
1009 }
1010
1011 return that.tally - this.tally;
1012 }
1013
1014 /**
1015 * The verse id
1016 */
1017 protected int ord;
1018
1019 /**
1020 * The rank of the verse
1021 */
1022 protected int tally;
1023 }
1024
1025 /**
1026 * Iterate over the Ranges in order of their rank in the tally
1027 *
1028 * @author Joe Walker
1029 */
1030 private static final class OrderedVerseRangeIterator implements Iterator<Key> {
1031 /**
1032 * Find the first unused verse
1033 */
1034 public OrderedVerseRangeIterator(Versification v11n, Iterator<Key> vit, int[] board) {
1035 Set<TalliedVerseRange> output = new TreeSet<TalliedVerseRange>();
1036
1037 Iterator<Key> rit = new VerseRangeIterator(v11n, vit, RestrictionType.NONE);
1038 while (rit.hasNext()) {
1039 VerseRange range = (VerseRange) rit.next();
1040
1041 // Calculate the maximum rank for a verse
1042 int rank = 0;
1043 for (Key aKey : range) {
1044 Verse verse = (Verse) aKey;
1045 int temp = board[v11n.getOrdinal(verse)];
1046 if (temp > rank) {
1047 rank = temp;
1048 }
1049 }
1050
1051 output.add(new TalliedVerseRange(range, rank));
1052 }
1053
1054 this.it = output.iterator();
1055 last = null;
1056 }
1057
1058 /* (non-Javadoc)
1059 * @see java.util.Iterator#hasNext()
1060 */
1061 public boolean hasNext() {
1062 return it.hasNext();
1063 }
1064
1065 /* (non-Javadoc)
1066 * @see java.util.Iterator#next()
1067 */
1068 public VerseRange next() throws NoSuchElementException {
1069 last = it.next();
1070 return last.range;
1071 }
1072
1073 /* (non-Javadoc)
1074 * @see java.util.Iterator#remove()
1075 */
1076 public void remove() throws UnsupportedOperationException {
1077 throw new UnsupportedOperationException();
1078 }
1079
1080 /**
1081 * So that we can get at the ranking of the given verse
1082 */
1083 private TalliedVerseRange last;
1084
1085 /**
1086 * The Iterator we are converting
1087 */
1088 private Iterator<TalliedVerseRange> it;
1089 }
1090
1091 /**
1092 * Hack to make this work with JDK1.1 as well as JDK1.2 This compared 2
1093 * Integers
1094 */
1095 private static class TalliedVerseRange implements Comparable<TalliedVerseRange> {
1096 /**
1097 * Convenience ctor to set the public variables
1098 *
1099 * @param range
1100 * The verse range
1101 * @param tally
1102 * The rank of the verse
1103 */
1104 public TalliedVerseRange(VerseRange range, int tally) {
1105 this.range = range;
1106 this.tally = tally;
1107 }
1108
1109 @Override
1110 public int hashCode() {
1111 int result = 31 + tally;
1112 return 31 * result + ((range == null) ? 0 : range.hashCode());
1113 }
1114
1115 @Override
1116 public boolean equals(Object obj) {
1117 if (this == obj) {
1118 return true;
1119 }
1120 if (obj == null) {
1121 return false;
1122 }
1123 if (getClass() != obj.getClass()) {
1124 return false;
1125 }
1126 final TalliedVerseRange other = (TalliedVerseRange) obj;
1127 if (tally != other.tally) {
1128 return false;
1129 }
1130 if (range == null) {
1131 if (other.range != null) {
1132 return false;
1133 }
1134 } else if (!range.equals(other.range)) {
1135 return false;
1136 }
1137 return true;
1138 }
1139
1140 /* (non-Javadoc)
1141 * @see java.lang.Comparable#compareTo(java.lang.Object)
1142 */
1143 public int compareTo(TalliedVerseRange that) {
1144 if (that.tally == this.tally) {
1145 return this.range.compareTo(that.range);
1146 }
1147
1148 return that.tally - this.tally;
1149 }
1150
1151 /**
1152 * The verse range
1153 */
1154 protected VerseRange range;
1155
1156 /**
1157 * The rank of the verse
1158 */
1159 protected int tally;
1160 }
1161}
1162