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