Coverage Report - org.crosswire.jsword.passage.RangedPassage
 
Classes in this File Line Coverage Branch Coverage Complexity
RangedPassage
0%
0/126
0%
0/48
2.407
RangedPassage$VerseIterator
0%
0/15
0%
0/4
2.407
RangedPassage$VerseRangeIterator
0%
0/23
0%
0/14
2.407
 
 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  
  * © CrossWire Bible Society, 2005 - 2016
 18  
  *
 19  
  */
 20  
 package org.crosswire.jsword.passage;
 21  
 
 22  
 import java.io.IOException;
 23  
 import java.io.ObjectInputStream;
 24  
 import java.io.ObjectOutputStream;
 25  
 import java.util.Iterator;
 26  
 import java.util.NoSuchElementException;
 27  
 import java.util.Set;
 28  
 import java.util.TreeSet;
 29  
 
 30  
 import org.crosswire.jsword.versification.Versification;
 31  
 
 32  
 /**
 33  
  * A Passage that is implemented using a TreeSet of VerseRanges. The attributes
 34  
  * of the style are:
 35  
  * <ul>
 36  
  * <li>Compact storage of large amounts of data
 37  
  * <li>Fast getName()
 38  
  * <li>Slow manipulation
 39  
  * </ul>
 40  
  * 
 41  
  * <p>
 42  
  * When to normalize()? This is a slow process, but one that is perhaps done
 43  
  * bit-by-bit instead of killing everything just to do getName(). The options
 44  
  * are:
 45  
  * <ul>
 46  
  * <li>Before every read</li>
 47  
  * <li>Before reads with a background thread</li>
 48  
  * <li>After every change</li>
 49  
  * <li>After every change with a caching scheme</li>
 50  
  * </ul>
 51  
  * I'm not sure which will be best. So I'm starting with 1 and optimizing later
 52  
  * ... Maybe the best is to allow the user to choose?
 53  
  * 
 54  
  * @see gnu.lgpl.License The GNU Lesser General Public License for details.
 55  
  * @author Joe Walker
 56  
  */
 57  0
 public class RangedPassage extends AbstractPassage {
 58  
     /**
 59  
      * Create an empty RangedPassage. There are no ctors from either Verse or
 60  
      * VerseRange so you need to do new <code>RangedPassage().add(...);</code>
 61  
      * 
 62  
      * @param refSystem
 63  
      *            The Versification to which this Passage belongs.
 64  
      */
 65  
     public RangedPassage(Versification refSystem) {
 66  0
         super(refSystem);
 67  0
         store = new TreeSet<VerseRange>();
 68  0
     }
 69  
 
 70  
     /**
 71  
      * Create a Verse from a human readable string. The opposite of getName(),
 72  
      * Given any RangedPassage v1, and the following
 73  
      * <code>RangedPassage v2 = new RangedPassage(v1.getName());</code> Then
 74  
      * <code>v1.equals(v2);</code> Theoretically, since there are many ways of
 75  
      * representing a RangedPassage as text string comparison along the lines
 76  
      * of: <code>v1.getName().equals(v2.getName())</code> could be false.
 77  
      * However since getName() is standardized this will be true. We don't need
 78  
      * to worry about thread safety in a ctor since we don't exist yet.
 79  
      * 
 80  
      * @param v11n
 81  
      *            The Versification to which this Passage belongs.
 82  
      * @param refs
 83  
      *            A String containing the text of the RangedPassage
 84  
      * @param basis
 85  
      *           The basis by which to interpret refs
 86  
      * @throws NoSuchVerseException
 87  
      *             if refs is invalid
 88  
      */
 89  
     protected RangedPassage(Versification v11n, String refs, Key basis) throws NoSuchVerseException {
 90  0
         super(v11n, refs);
 91  
 
 92  0
         store = new TreeSet<VerseRange>();
 93  0
         addVerses(refs, basis);
 94  0
         normalize();
 95  0
     }
 96  
 
 97  
     protected RangedPassage(Versification v11n, String refs) throws NoSuchVerseException {
 98  0
         this(v11n, refs, null);
 99  0
     }
 100  
 
 101  
     @Override
 102  
     public RangedPassage clone() {
 103  
         // This gets us a shallow copy
 104  0
         RangedPassage copy = (RangedPassage) super.clone();
 105  
 
 106  
         // I want to just do the following
 107  
         // copy.store = (SortedSet) store.clone();
 108  
         // However SortedSet is not Cloneable so I can't
 109  
         // Watch out for this, I'm not sure if it breaks anything.
 110  0
         copy.store = new TreeSet<VerseRange>();
 111  0
         copy.store.addAll(store);
 112  
 
 113  0
         return copy;
 114  
     }
 115  
 
 116  
     @Override
 117  
     public int countRanges(RestrictionType restrict) {
 118  0
         if (restrict.equals(RestrictionType.NONE)) {
 119  0
             return store.size();
 120  
         }
 121  
 
 122  0
         return super.countRanges(restrict);
 123  
     }
 124  
 
 125  
     @Override
 126  
     public int countVerses() {
 127  0
         Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE);
 128  0
         int count = 0;
 129  
 
 130  0
         while (it.hasNext()) {
 131  0
             VerseRange range = it.next();
 132  0
             count += range.getCardinality();
 133  0
         }
 134  
 
 135  0
         return count;
 136  
     }
 137  
 
 138  
     /* (non-Javadoc)
 139  
      * @see java.lang.Iterable#iterator()
 140  
      */
 141  
     public Iterator<Key> iterator() {
 142  0
         return new VerseIterator(getVersification(), rangeIterator(RestrictionType.NONE));
 143  
     }
 144  
 
 145  
     @Override
 146  
     public final Iterator<VerseRange> rangeIterator(RestrictionType restrict) {
 147  0
         if (restrict.equals(RestrictionType.NONE)) {
 148  0
             return store.iterator();
 149  
         }
 150  
 
 151  0
         return new VerseRangeIterator(store.iterator(), restrict);
 152  
     }
 153  
 
 154  
     @Override
 155  
     public boolean isEmpty() {
 156  0
         return store.isEmpty();
 157  
     }
 158  
 
 159  
     @Override
 160  
     public boolean contains(Key obj) {
 161  
         // Even for the contains(VerseRange) case, the simple
 162  
         // 'return store.contains(that);' will not work because
 163  
         // VerseRanges can contain others but not be equal to them.
 164  
 
 165  0
         VerseRange thatRange = toVerseRange(getVersification(), obj);
 166  
 
 167  0
         Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE);
 168  0
         while (it.hasNext()) {
 169  0
             VerseRange thisRange = it.next();
 170  0
             if (thisRange.contains(thatRange)) {
 171  0
                 return true;
 172  
             }
 173  0
         }
 174  
 
 175  
         // If it is not a Verse or a VerseRange then it's not here,
 176  
         // this also copes with the searches failing.
 177  0
         return false;
 178  
     }
 179  
 
 180  
     /* (non-Javadoc)
 181  
      * @see org.crosswire.jsword.passage.Passage#add(org.crosswire.jsword.passage.Key)
 182  
      */
 183  
     public void add(Key obj) {
 184  0
         optimizeWrites();
 185  
 
 186  0
         VerseRange thatRange = toVerseRange(getVersification(), obj);
 187  0
         store.add(thatRange);
 188  
 
 189  0
         normalize();
 190  
 
 191  
         // we do an extra check here because the cost of calculating the
 192  
         // params is non-zero an may be wasted
 193  0
         if (suppressEvents == 0) {
 194  0
             fireIntervalAdded(this, thatRange.getStart(), thatRange.getEnd());
 195  
         }
 196  0
     }
 197  
 
 198  
     @Override
 199  
     public void clear() {
 200  0
         optimizeWrites();
 201  
 
 202  0
         store.clear();
 203  0
         fireIntervalRemoved(this, null, null);
 204  0
     }
 205  
 
 206  
     /* (non-Javadoc)
 207  
      * @see org.crosswire.jsword.passage.Passage#remove(org.crosswire.jsword.passage.Key)
 208  
      */
 209  
     public void remove(Key obj) {
 210  0
         optimizeWrites();
 211  
 
 212  0
         VerseRange thatRange = toVerseRange(getVersification(), obj);
 213  0
         boolean removed = false;
 214  
 
 215  
         // This allows us to modify store which iterating through a copy
 216  0
         Set<Key> newStore = new TreeSet<Key>();
 217  0
         newStore.addAll(store);
 218  
 
 219  
         // go through all the VerseRanges
 220  0
         for (Key aKey : newStore) {
 221  
             // if this range touches the range to be removed ...
 222  0
             VerseRange thisRange = (VerseRange) aKey;
 223  0
             if (thisRange.overlaps(thatRange)) {
 224  
                 // ... remove it and add the remainder
 225  0
                 store.remove(thisRange);
 226  0
                 VerseRange[] vra = VerseRange.remainder(thisRange, thatRange);
 227  
 
 228  0
                 for (int i = 0; i < vra.length; i++) {
 229  0
                     store.add(vra[i]);
 230  
                 }
 231  
 
 232  0
                 removed = true;
 233  
             }
 234  0
         }
 235  
 
 236  0
         if (removed) {
 237  0
             normalize();
 238  
         }
 239  
 
 240  
         // we do an extra check here because the cost of calculating the
 241  
         // params is non-zero an may be wasted
 242  0
         if (suppressEvents == 0) {
 243  0
             fireIntervalRemoved(this, thatRange.getStart(), thatRange.getEnd());
 244  
         }
 245  0
     }
 246  
 
 247  
     @Override
 248  
     public void retainAll(Key key) {
 249  0
         optimizeWrites();
 250  
 
 251  0
         Set<VerseRange> newStore = new TreeSet<VerseRange>();
 252  
 
 253  0
         if (key instanceof RangedPassage) {
 254  0
             Iterator<VerseRange> thatIter = ((RangedPassage) key).rangeIterator(RestrictionType.CHAPTER);
 255  0
             while (thatIter.hasNext()) {
 256  0
                 VerseRange thatRange = thatIter.next();
 257  
 
 258  
                 // go through all the VerseRanges
 259  0
                 Iterator<VerseRange> thisIter = rangeIterator(RestrictionType.NONE);
 260  0
                 while (thisIter.hasNext()) {
 261  
                     // if this range touches the range to be removed ...
 262  0
                     VerseRange thisRange = thisIter.next();
 263  0
                     if (thisRange.overlaps(thatRange)) {
 264  
                         // ... remove it and add the remainder
 265  0
                         VerseRange interstect = VerseRange.intersection(thisRange, thatRange);
 266  0
                         if (interstect != null) {
 267  0
                             newStore.add(interstect);
 268  
                         }
 269  
                     }
 270  0
                 }
 271  0
             }
 272  0
         } else {
 273  0
             Iterator<Key> thatIter = key.iterator();
 274  0
             while (thatIter.hasNext()) {
 275  0
                 VerseRange thatRange = toVerseRange(getVersification(), thatIter.next());
 276  
 
 277  
                 // go through all the VerseRanges
 278  0
                 Iterator<VerseRange> thisIter = rangeIterator(RestrictionType.NONE);
 279  0
                 while (thisIter.hasNext()) {
 280  
                     // if this range touches the range to be removed ...
 281  0
                     VerseRange thisRange = thisIter.next();
 282  0
                     if (thisRange.overlaps(thatRange)) {
 283  
                         // ... remove it and add the remainder
 284  0
                         VerseRange interstect = VerseRange.intersection(thisRange, thatRange);
 285  0
                         if (interstect != null) {
 286  0
                             newStore.add(interstect);
 287  
                         }
 288  
                     }
 289  0
                 }
 290  0
             }
 291  
         }
 292  
 
 293  
 
 294  0
         store = newStore;
 295  0
         normalize();
 296  
 
 297  0
         fireIntervalRemoved(this, null, null);
 298  0
     }
 299  
 
 300  
     /**
 301  
      * We sometimes need to sort ourselves out ...
 302  
      * <p>
 303  
      * I don't think we need to be synchronized since we are private and we
 304  
      * could check that all public calling of normalize() are synchronized,
 305  
      * however this is safe, and I don't think there is a cost associated with a
 306  
      * double synchronize. (?)
 307  
      */
 308  
     @Override
 309  
     /* protected */final void normalize() {
 310  0
         if (skipNormalization != 0) {
 311  0
             return;
 312  
         }
 313  
 
 314  0
         VerseRange last = null;
 315  0
         VerseRange next = null;
 316  0
         Set<VerseRange> newStore = new TreeSet<VerseRange>();
 317  
 
 318  0
         Iterator<VerseRange> it = rangeIterator(RestrictionType.NONE);
 319  0
         while (it.hasNext()) {
 320  0
             next = it.next();
 321  
 
 322  0
             if (last != null && next.adjacentTo(last)) {
 323  0
                 VerseRange merge = new VerseRange(last, next);
 324  
 
 325  0
                 newStore.remove(last);
 326  0
                 newStore.add(merge);
 327  
 
 328  0
                 last = merge;
 329  0
             } else {
 330  0
                 newStore.add(next);
 331  0
                 last = next;
 332  
             }
 333  
         }
 334  
 
 335  0
         store = newStore;
 336  0
     }
 337  
 
 338  
     /**
 339  
      * This class is here to prevent users of RangedPassage.iterator() from
 340  
      * altering the underlying store and getting us out of sync. Right now there
 341  
      * are no issues with someone else removing a RangedPassage without telling
 342  
      * us, however there may be some day, and I'm not sure that we need the
 343  
      * functionality right now. Also buy using this we get to ensure
 344  
      * synchronization. Everything is final so to save the proxying performace
 345  
      * hit.
 346  
      */
 347  0
     private static final class VerseIterator implements Iterator<Key> {
 348  
         /**
 349  
          * Create a basic iterator that is a proxy for the RangedPassage
 350  
          * Passages iterator, with remove() overridden.
 351  
          * @param v11n
 352  
          *            the versification to which this reference pertains
 353  
          * @param it 
 354  
          */
 355  0
         protected VerseIterator(Versification v11n, Iterator<VerseRange> it) {
 356  0
             Set<Key> temp = new TreeSet<Key>();
 357  
 
 358  0
             while (it.hasNext()) {
 359  0
                 VerseRange range = it.next();
 360  0
                 int start = range.getStart().getOrdinal();
 361  0
                 int end = range.getCardinality();
 362  
 
 363  0
                 for (int i = 0; i < end; i++) {
 364  0
                     temp.add(v11n.decodeOrdinal(start + i));
 365  
                 }
 366  0
             }
 367  
 
 368  0
             real = temp.iterator();
 369  0
         }
 370  
 
 371  
         /* (non-Javadoc)
 372  
          * @see java.util.Iterator#hasNext()
 373  
          */
 374  
         public boolean hasNext() {
 375  0
             return real.hasNext();
 376  
         }
 377  
 
 378  
         /* (non-Javadoc)
 379  
          * @see java.util.Iterator#next()
 380  
          */
 381  
         public Key next() throws NoSuchElementException {
 382  0
             return real.next();
 383  
         }
 384  
 
 385  
         /* (non-Javadoc)
 386  
          * @see java.util.Iterator#remove()
 387  
          */
 388  
         public void remove() throws UnsupportedOperationException {
 389  0
             throw new UnsupportedOperationException();
 390  
         }
 391  
 
 392  
         /**
 393  
          * The Iterator that we are proxying to
 394  
          */
 395  
         private Iterator<Key> real;
 396  
     }
 397  
 
 398  
     /**
 399  
      * Loop over the VerseRanges and check that they do not require digging into
 400  
      */
 401  0
     private static final class VerseRangeIterator implements Iterator<VerseRange> {
 402  
         /**
 403  
          * Simple ctor
 404  
          * @param it 
 405  
          * @param restrict 
 406  
          */
 407  0
         protected VerseRangeIterator(Iterator<VerseRange> it, RestrictionType restrict) {
 408  0
             this.restrict = restrict;
 409  0
             this.real = it;
 410  0
         }
 411  
 
 412  
         /* (non-Javadoc)
 413  
          * @see java.util.Iterator#remove()
 414  
          */
 415  
         public void remove() {
 416  0
             throw new UnsupportedOperationException();
 417  
         }
 418  
 
 419  
         /* (non-Javadoc)
 420  
          * @see java.util.Iterator#hasNext()
 421  
          */
 422  
         public boolean hasNext() {
 423  0
             return next != null || real.hasNext();
 424  
         }
 425  
 
 426  
         /* (non-Javadoc)
 427  
          * @see java.util.Iterator#next()
 428  
          */
 429  
         public VerseRange next() {
 430  0
             if (next == null) {
 431  0
                 next = real.next();
 432  
             }
 433  
 
 434  0
             if (next == null) {
 435  0
                 throw new NoSuchElementException();
 436  
             }
 437  
 
 438  
             // So we know what is broadly next, however the range might need
 439  
             // splitting according to restrict
 440  0
             if (restrict.isSameScope(next.getVersification(), next.getStart(), next.getEnd())) {
 441  0
                 return replyNext();
 442  
             }
 443  0
             return splitNext();
 444  
         }
 445  
 
 446  
         /**
 447  
          * The next object is correct, use that one
 448  
          */
 449  
         private VerseRange replyNext() {
 450  0
             VerseRange reply = next;
 451  0
             next = null;
 452  0
             return reply;
 453  
         }
 454  
 
 455  
         /**
 456  
          * The next object is too big, so cut it up
 457  
          */
 458  
         private VerseRange splitNext() {
 459  0
             Iterator<VerseRange> chop = next.rangeIterator(restrict);
 460  0
             VerseRange first = chop.next();
 461  0
             VerseRange[] ranges = VerseRange.remainder(next, first);
 462  
 
 463  0
             assert ranges.length == 1;
 464  0
             next = ranges[0];
 465  
 
 466  0
             return first;
 467  
         }
 468  
 
 469  
         /**
 470  
          * What are we going to reply with next?
 471  
          */
 472  
         private VerseRange next;
 473  
 
 474  
         /**
 475  
          * Where do we break ranges
 476  
          */
 477  
         private RestrictionType restrict;
 478  
 
 479  
         /**
 480  
          * Where we read our base ranges from
 481  
          */
 482  
         private Iterator<VerseRange> real;
 483  
     }
 484  
 
 485  
     /**
 486  
      * Call the support mechanism in AbstractPassage
 487  
      * 
 488  
      * @param out
 489  
      *            The stream to write our state to
 490  
      * @serialData Write the ordinal number of this verse
 491  
      * @throws IOException
 492  
      *             if the read fails
 493  
      * @see AbstractPassage#writeObjectSupport(ObjectOutputStream)
 494  
      */
 495  
     private void writeObject(ObjectOutputStream out) throws IOException {
 496  0
         out.defaultWriteObject();
 497  
 
 498  0
         writeObjectSupport(out);
 499  0
     }
 500  
 
 501  
     /**
 502  
      * Call the support mechanism in AbstractPassage
 503  
      * 
 504  
      * @param in
 505  
      *            The stream to read our state from
 506  
      * @serialData Write the ordinal number of this verse
 507  
      * @throws IOException
 508  
      *             if the read fails
 509  
      * @throws ClassNotFoundException
 510  
      *             If the read data is incorrect
 511  
      * @see AbstractPassage#readObjectSupport(ObjectInputStream)
 512  
      */
 513  
     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 514  0
         optimizeWrites();
 515  
 
 516  0
         store = new TreeSet<VerseRange>();
 517  
 
 518  0
         in.defaultReadObject();
 519  
 
 520  0
         readObjectSupport(in);
 521  0
     }
 522  
 
 523  
     /**
 524  
      * To make serialization work across new versions
 525  
      */
 526  
     private static final long serialVersionUID = 955115811339960826L;
 527  
 
 528  
     /**
 529  
      * The place the real data is stored
 530  
      */
 531  
     private transient Set<VerseRange> store;
 532  
 }