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