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