src/intervalstore/nonc/IntervalStore.java

   1 /*
   2 BSD 3-Clause License
   3
   4 Copyright (c) 2018, Mungo Carstairs
   5 All rights reserved.
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, are permitted provided that the following conditions are met:
   9
  10 * Redistributions of source code must retain the above copyright notice, this
  11   list of conditions and the following disclaimer.
  12
  13 * Redistributions in binary form must reproduce the above copyright notice,
  14   this list of conditions and the following disclaimer in the documentation
  15   and/or other materials provided with the distribution.
  16
  17 * Neither the name of the copyright holder nor the names of its
  18   contributors may be used to endorse or promote products derived from
  19   this software without specific prior written permission.
  20
  21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31 */
  32 package intervalstore.nonc;
  33
  34 import java.util.AbstractCollection;
  35 import java.util.ArrayList;
  36 import java.util.Arrays;
  37 import java.util.BitSet;
  38 import java.util.Collections;
  39 import java.util.Comparator;
  40 import java.util.Iterator;
  41 import java.util.List;
  42 import java.util.NoSuchElementException;
  43
  44 import intervalstore.api.IntervalI;
  45 import intervalstore.api.IntervalStoreI;
  46
  47 /**
  48  *
  49  * A second idea, doing a double binary sort for the full interval. Seemed like
  50  * a good idea, but is 50% slower.
  51  *
  52  * A Collection class to store interval-associated data, with options for "lazy"
  53  * sorting so as to speed incremental construction of the data prior to issuing
  54  * a findOverlap call.
  55  *
  56  *
  57  * Accepts duplicate entries but not null values.
  58  *
  59  *
  60  *
  61  * @author Bob Hanson 2019.08.06
  62  *
  63  * @param <T>
  64  *          any type providing <code>getBegin()</code>, <code>getEnd()</code>
  65  *          <code>getContainedBy()</code>, and <code>setContainedBy()</code>
  66  */
  67 public class IntervalStore<T extends IntervalI>
  68         extends AbstractCollection<T> implements IntervalStoreI<T>
  69 {
  70
  71   /**
  72    * Search for the last interval that starts before or at the specified from/to
  73    * range and the first interval that starts after it. In the situation that
  74    * there are multiple intervals starting at from, this method returns the
  75    * first of those.
  76    *
  77    * @param a
  78    * @param from
  79    * @param to
  80    * @param ret
  81    * @return
  82    */
  83   public int binaryLastIntervalSearch(long from,
  84           long to, int[] ret)
  85   {
  86     int start = 0, start2 = 0;
  87     int matched = 0;
  88     int end = intervalCount - 1, end2 = intervalCount;
  89     int mid, begin;
  90     IntervalI e;
  91     while (start <= end)
  92     {
  93       mid = (start + end) >>> 1;
  94       e = intervals[mid];
  95       begin = e.getBegin();
  96       switch (Long.signum(begin - from))
  97       {
  98       case -1:
  99         matched = mid;
 100         start = mid + 1;
 101         break;
 102       case 0:
 103       case 1:
 104         end = mid - 1;
 105         if (begin > to)
 106         {
 107           end2 = mid;
 108         }
 109         else
 110         {
 111           start2 = mid;
 112         }
 113         break;
 114       }
 115     }
 116     ret[0] = end2;
 117     start = Math.max(start2, end);
 118     end = end2 - 1;
 119
 120     while (start <= end)
 121     {
 122       mid = (start + end) >>> 1;
 123       e = intervals[mid];
 124       begin = e.getBegin();
 125       if (begin > to)
 126       {
 127         ret[0] = mid;
 128         end = mid - 1;
 129       }
 130       else
 131       {
 132         start = mid + 1;
 133       }
 134
 135     }
 136     return matched;
 137   }
 138
 139   /**
 140    * My preference is for a bigendian comparison, but you may differ.
 141    */
 142   private Comparator<? super IntervalI> icompare;
 143
 144   /**
 145    * bigendian is what NCList does; change icompare to switch to that
 146    */
 147   private boolean bigendian;
 148
 149   private final boolean DO_PRESORT;
 150
 151   private boolean isSorted;
 152
 153   private int minStart = Integer.MAX_VALUE, maxStart = Integer.MIN_VALUE,
 154           maxEnd = Integer.MAX_VALUE;
 155
 156   // private Comparator<IntervalI> icompare = new IntervalComparator();
 157
 158   private boolean isTainted;
 159
 160   private int capacity = 8;
 161
 162   private IntervalI[] intervals = new IntervalI[capacity];
 163
 164   private int[] offsets;
 165
 166   private int[] ret = new int[1];
 167
 168   private int intervalCount;
 169
 170   private int added;
 171
 172   private int deleted;
 173
 174   private BitSet bsDeleted;
 175
 176   /**
 177    * Constructor
 178    */
 179   public IntervalStore()
 180   {
 181     this(true);
 182   }
 183
 184   public IntervalStore(boolean presort)
 185   {
 186     this(null, presort);
 187   }
 188
 189   /**
 190    * Constructor given a list of intervals. Note that the list may get sorted as
 191    * a side-effect of calling this constructor.
 192    */
 193   public IntervalStore(List<T> intervals)
 194   {
 195     this(intervals, true);
 196   }
 197
 198   /**
 199    * Allows a presort option, which can speed up initial loading of individual
 200    * features but will delay the first findOverlap if set to true.
 201    *
 202    * @param intervals
 203    * @param presort
 204    */
 205   public IntervalStore(List<T> intervals, boolean presort)
 206   {
 207     this(intervals, presort, null, false);
 208   }
 209
 210   /**
 211    *
 212    * @param intervals
 213    *          intervals to initialize with (others may still be added)
 214    * @param presort
 215    *          whether or not to presort the list as additions are made
 216    * @param comparator
 217    *          IntervalI.COMPARATOR_LITTLEENDIAN or
 218    *          IntervalI.COMPARATOR_BIGENDIAN, but this could also be one that
 219    *          sorts by description as well, for example.
 220    * @param bigendian
 221    *          true if the comparator sorts [10-30] before [10-20]
 222    */
 223   public IntervalStore(List<T> intervals, boolean presort,
 224           Comparator<? super IntervalI> comparator, boolean bigendian)
 225   {
 226     if (intervals != null)
 227     {
 228       intervals.toArray(
 229               this.intervals = new IntervalI[capacity = intervalCount = intervals
 230                       .size()]);
 231     }
 232     DO_PRESORT = presort;
 233     icompare = (comparator != null ? comparator
 234             : bigendian ? IntervalI.COMPARATOR_BIGENDIAN
 235                     : IntervalI.COMPARATOR_LITTLEENDIAN);
 236     this.bigendian = bigendian;
 237
 238     if (DO_PRESORT && intervalCount > 1)
 239     {
 240       sort();
 241     }
 242     isSorted = DO_PRESORT;
 243     isTainted = true;
 244   }
 245
 246   /**
 247    * Adds one interval to the store, allowing duplicates.
 248    *
 249    * @param interval
 250    */
 251   @Override
 252   public boolean add(T interval)
 253   {
 254     return add(interval, true);
 255   }
 256
 257   /**
 258    * Adds one interval to the store, optionally checking for duplicates.
 259    *
 260    * @param interval
 261    * @param allowDuplicates
 262    */
 263   public boolean add(T interval, boolean allowDuplicates)
 264   {
 265     if (interval == null)
 266     {
 267       return false;
 268     }
 269
 270     if (deleted > 0)
 271       finalizeDeletion();
 272     if (!isTainted)
 273     {
 274       offsets = null;
 275       isTainted = true;
 276     }
 277
 278     synchronized (intervals)
 279     {
 280       int index = intervalCount;
 281       int start = interval.getBegin();
 282
 283       if (intervalCount + added + 1 >= capacity)
 284       {
 285         intervals = finalizeAddition(
 286                 new IntervalI[capacity = capacity << 1]);
 287
 288       }
 289
 290       if (DO_PRESORT && isSorted)
 291       {
 292         if (intervalCount == 0)
 293         {
 294           // ignore
 295         }
 296         else
 297         {
 298           index = findInterval(interval);
 299           if (!allowDuplicates && index >= 0)
 300           {
 301             return false;
 302           }
 303           if (index < 0)
 304             index = -1 - index;
 305           else
 306             index++;
 307         }
 308
 309       }
 310       else
 311       {
 312         if (!allowDuplicates && findInterval(interval) >= 0)
 313         {
 314           return false;
 315         }
 316
 317       }
 318
 319       if (index == intervalCount)
 320       {
 321         intervals[intervalCount++] = interval;
 322         // System.out.println("added " + intervalCount + " " + interval);
 323       }
 324       else
 325       {
 326         int pt = capacity - ++added;
 327         intervals[pt] = interval;
 328         // System.out.println("stashed " + pt + " " + interval + " for "
 329         // + index + " " + intervals[index]);
 330         if (offsets == null)
 331           offsets = new int[capacity];
 332
 333         offsets[pt] = offsets[index];
 334
 335         offsets[index] = pt;
 336       }
 337
 338       minStart = Math.min(minStart, start);
 339       maxStart = Math.max(maxStart, start);
 340       return true;
 341     }
 342   }
 343
 344   private IntervalI[] finalizeAddition(IntervalI[] dest)
 345   {
 346     if (dest == null)
 347       dest = intervals;
 348     if (added == 0)
 349     {
 350       if (intervalCount > 0 && dest != intervals)
 351       {
 352         System.arraycopy(intervals, 0, dest, 0, intervalCount);
 353       }
 354       capacity = dest.length;
 355       return dest;
 356     }
 357
 358     // array is [(intervalCount)...null...(added)]
 359
 360     int ntotal = intervalCount + added;
 361     for (int ptShift = intervalCount + added, pt = intervalCount; pt >= 0;)
 362     {
 363       int pt0 = pt;
 364       while (--pt >= 0 && offsets[pt] == 0)
 365         ;
 366       if (pt < 0)
 367         pt = 0;
 368       int nOK = pt0 - pt;
 369       // shift upper intervals right
 370       ptShift -= nOK;
 371       if (nOK > 0)
 372         System.arraycopy(intervals, pt, dest, ptShift, nOK);
 373       if (added == 0)
 374         break;
 375         for (int offset = offsets[pt]; offset > 0; offset = offsets[offset])
 376         {
 377           dest[--ptShift] = intervals[offset];
 378           --added;
 379         }
 380     }
 381     offsets = null;
 382     intervalCount = ntotal;
 383     capacity = dest.length;
 384     return dest;
 385   }
 386
 387   public int binaryIdentitySearch(IntervalI interval)
 388   {
 389     return binaryIdentitySearch(interval, null);
 390   }
 391   /**
 392    * for remove() and contains()
 393    *
 394    * @param list
 395    * @param interval
 396    * @param bsIgnore
 397    *          for deleted
 398    * @return index or, if not found, -1 - "would be here"
 399    */
 400   public int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore)
 401   {
 402     int start = 0;
 403     int r0 = interval.getBegin();
 404     int r1 = interval.getEnd();
 405     int end = intervalCount - 1;
 406     if (end < 0 || r0 < minStart)
 407       return -1;
 408     if (r0 > maxStart)
 409       return -1 - intervalCount;
 410     while (start <= end)
 411     {
 412       int mid = (start + end) >>> 1;
 413       IntervalI r = intervals[mid];
 414       switch (compareRange(r, r0, r1))
 415       {
 416       case -1:
 417         start = mid + 1;
 418         continue;
 419       case 1:
 420         end = mid - 1;
 421         continue;
 422       case 0:
 423         IntervalI iv = intervals[mid];
 424         if ((bsIgnore == null || !bsIgnore.get(mid))
 425                 && iv.equalsInterval(interval))
 426           return mid;
 427         // found one; just scan up and down now, first checking the range, but
 428         // also checking other possible aspects of equivalence.
 429
 430         for (int i = mid; ++i <= end;)
 431         {
 432           if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() != r1)
 433             break;
 434           if ((bsIgnore == null || !bsIgnore.get(i))
 435                   && iv.equalsInterval(interval))
 436             return i;
 437         }
 438         for (int i = mid; --i >= start;)
 439         {
 440           if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() < r1)
 441             return -1 - ++i;
 442           if ((bsIgnore == null || !bsIgnore.get(i))
 443                   && iv.equalsInterval(interval))
 444             return i;
 445         }
 446         return -1 - start;
 447       }
 448     }
 449     return -1 - start;
 450   }
 451
 452   // private int binaryInsertionSearch(long from, long to)
 453   // {
 454   // int matched = intervalCount;
 455   // int end = matched - 1;
 456   // int start = matched;
 457   // if (end < 0 || from > intervals[end].getEnd()
 458   // || from < intervals[start = 0].getBegin())
 459   // return start;
 460   // while (start <= end)
 461   // {
 462   // int mid = (start + end) >>> 1;
 463   // switch (compareRange(intervals[mid], from, to))
 464   // {
 465   // case 0:
 466   // return mid;
 467   // case 1:
 468   // matched = mid;
 469   // end = mid - 1;
 470   // continue;
 471   // case -1:
 472   // start = mid + 1;
 473   // continue;
 474   // }
 475   //
 476   // }
 477   // return matched;
 478   // }
 479
 480
 481   @Override
 482   public void clear()
 483   {
 484     intervalCount = added = 0;
 485     isSorted = true;
 486     isTainted = true;
 487     offsets = null;
 488     minStart = maxEnd = Integer.MAX_VALUE;
 489     maxStart = Integer.MIN_VALUE;
 490   }
 491   /**
 492    * Compare an interval t to a from/to range for insertion purposes
 493    *
 494    * @param t
 495    * @param from
 496    * @param to
 497    * @return 0 if same, 1 if start is after from, or start equals from and
 498    *         [bigendian: end is before to | littleendian: end is after to], else
 499    *         -1
 500    */
 501   private int compareRange(IntervalI t, long from, long to)
 502   {
 503     if (t == null)
 504       System.out.println("???");
 505     int order = Long.signum(t.getBegin() - from);
 506     return (order == 0
 507             ? Long.signum(bigendian ? to - t.getEnd() : t.getEnd() - to)
 508             : order);
 509   }
 510
 511   @Override
 512   public boolean contains(Object entry)
 513   {
 514     if (entry == null || intervalCount == 0)
 515       return false;
 516     if (!isSorted || deleted > 0)
 517     {
 518       sort();
 519     }
 520     return (findInterval((IntervalI) entry) >= 0);
 521   }
 522
 523   public boolean containsInterval(IntervalI outer, IntervalI inner)
 524   {
 525     ensureFinalized();
 526     int index = binaryIdentitySearch(inner, null);
 527     if (index >= 0)
 528       while ((index = index - Math.abs(offsets[index])) >= 0)
 529       {
 530         if (intervals[index] == outer)
 531         {
 532           return true;
 533         }
 534       }
 535     return false;
 536   }
 537
 538   private void ensureFinalized()
 539   {
 540     if (isTainted && intervalCount + added > 1)
 541     {
 542       if (!isSorted || added > 0 || deleted > 0)
 543       {
 544         sort();
 545       }
 546       if (offsets == null || offsets.length < intervalCount)
 547         offsets = new int[intervalCount];
 548       linkFeatures();
 549       isTainted = false;
 550     }
 551   }
 552
 553   /**
 554    * Find all overlaps within the given range, inclusively.
 555    *
 556    * @return a list sorted in ascending order of start position
 557    *
 558    */
 559   @Override
 560   public List<T> findOverlaps(long from, long to)
 561   {
 562     List<T> list = findOverlaps(from, to, null);
 563     Collections.reverse(list);
 564     return list;
 565   }
 566
 567   /**
 568    * Find all overlaps within the given range, inclusively.
 569    *
 570    * @return a list sorted in descending order of start position
 571    *
 572    */
 573
 574   @SuppressWarnings("unchecked")
 575   @Override
 576   public List<T> findOverlaps(long from, long to, List<T> result)
 577   {
 578     if (result == null)
 579     {
 580       result = new ArrayList<>();
 581     }
 582     switch (intervalCount)
 583     {
 584     case 0:
 585       return result;
 586     case 1:
 587       IntervalI sf = intervals[0];
 588       if (sf.getBegin() <= to && sf.getEnd() >= from)
 589       {
 590         result.add((T) sf);
 591       }
 592       return result;
 593     }
 594
 595     ensureFinalized();
 596
 597     if (from > maxEnd || to < minStart)
 598       return result;
 599     int index = binaryLastIntervalSearch(from, to, ret);
 600     int index1 = ret[0];
 601     if (index1 < 0)
 602       return result;
 603
 604     if (index1 > index + 1)
 605     {
 606       while (--index1 > index)
 607       {
 608         result.add((T) intervals[index1]);
 609       }
 610     }
 611     boolean isMonotonic = false;
 612     while (index >= 0)
 613     {
 614       IntervalI sf = intervals[index];
 615       if (sf.getEnd() >= from)
 616       {
 617         result.add((T) sf);
 618       }
 619       else if (isMonotonic)
 620       {
 621         break;
 622       }
 623       int offset = offsets[index];
 624       isMonotonic = (offset < 0);
 625       index -= (isMonotonic ? -offset : offset);
 626     }
 627     return result;
 628   }
 629
 630   @Override
 631   public IntervalI get(int i)
 632   {
 633     if (i < 0 || i >= intervalCount + added)
 634       return null;
 635     ensureFinalized();
 636     return intervals[i];
 637   }
 638
 639   private int getContainedBy(int index, int begin)
 640   {
 641     while (index >= 0)
 642     {
 643       IntervalI sf = intervals[index];
 644       if (sf.getEnd() >= begin)
 645       {
 646         // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
 647         // + "\nFS in " + sf.getIndex1() + ":" + sf);
 648         return index;
 649       }
 650       index -= Math.abs(offsets[index]);
 651     }
 652     return IntervalI.NOT_CONTAINED;
 653   }
 654
 655   @Override
 656   public int getDepth()
 657   {
 658     ensureFinalized();
 659     if (intervalCount < 2)
 660     {
 661       return intervalCount;
 662     }
 663     int maxDepth = 1;
 664     IntervalI root = null;
 665     for (int i = 0; i < intervalCount; i++)
 666     {
 667       IntervalI element = intervals[i];
 668       if (offsets[i] == IntervalI.NOT_CONTAINED)
 669       {
 670         root = element;
 671       }
 672       int depth = 1;
 673       int index = i;
 674       int offset;
 675       while ((index = index - Math.abs(offset = offsets[index])) >= 0)
 676       {
 677         element = intervals[index];
 678         if (++depth > maxDepth && (element == root || offset < 0))
 679         {
 680           maxDepth = depth;
 681           break;
 682         }
 683       }
 684     }
 685     return maxDepth;
 686   }
 687
 688   @Override
 689   public int getWidth()
 690   {
 691     ensureFinalized();
 692     int w = 0;
 693     for (int i = offsets.length; --i >= 0;)
 694     {
 695       if (offsets[i] > 0)
 696       {
 697         w++;
 698       }
 699     }
 700     return w;
 701   }
 702
 703   @Override
 704   public boolean isValid()
 705   {
 706     ensureFinalized();
 707     return true;
 708   }
 709
 710   /**
 711    * Answers an iterator over the intervals in the store, with no particular
 712    * ordering guaranteed. The iterator does not support the optional
 713    * <code>remove</code> operation (throws
 714    * <code>UnsupportedOperationException</code> if attempted).
 715    */
 716   @Override
 717   public Iterator<T> iterator()
 718   {
 719     finalizeAddition(null);
 720     return new Iterator<T>()
 721     {
 722
 723       private int next;
 724
 725       @Override
 726       public boolean hasNext()
 727       {
 728         return next < intervalCount;
 729       }
 730
 731       @SuppressWarnings("unchecked")
 732       @Override
 733       public T next()
 734       {
 735         if (next >= intervalCount)
 736           throw new NoSuchElementException();
 737         return (T) intervals[next++];
 738       }
 739
 740     };
 741   }
 742
 743   private void linkFeatures()
 744   {
 745     if (intervalCount == 0)
 746       return;
 747     maxEnd = intervals[0].getEnd();
 748     offsets[0] = IntervalI.NOT_CONTAINED;
 749     if (intervalCount == 1)
 750     {
 751       return;
 752     }
 753     boolean isMonotonic = true;
 754     for (int i = 1; i < intervalCount; i++)
 755     {
 756       IntervalI sf = intervals[i];
 757       int begin = sf.getBegin();
 758       int index = (begin <= maxEnd ? getContainedBy(i - 1, begin) : -1);
 759         // System.out.println(sf + " is contained by "
 760       // + (index < 0 ? null : starts[index]));
 761
 762       offsets[i] = (index < 0 ? IntervalI.NOT_CONTAINED
 763               : isMonotonic ? index - i : i - index);
 764       isMonotonic = (sf.getEnd() > maxEnd);
 765       if (isMonotonic)
 766       {
 767         maxEnd = sf.getEnd();
 768       }
 769     }
 770
 771   }
 772
 773   @Override
 774   public String prettyPrint()
 775   {
 776     switch (intervalCount)
 777     {
 778     case 0:
 779       return "";
 780     case 1:
 781       return intervals[0] + "\n";
 782     }
 783     ensureFinalized();
 784     String sep = "\t";
 785     StringBuffer sb = new StringBuffer();
 786     for (int i = 0; i < intervalCount; i++)
 787     {
 788       IntervalI range = intervals[i];
 789       int index = i;
 790       while ((index = index - Math.abs(offsets[index])) >= 0)
 791       {
 792         sb.append(sep);
 793       }
 794       sb.append(range.toString()).append('\n');
 795     }
 796     return sb.toString();
 797   }
 798
 799   @Override
 800   public synchronized boolean remove(Object o)
 801   {
 802     // if (o == null)
 803     // {
 804     // throw new NullPointerException();
 805     // }
 806     return (o != null && intervalCount > 0
 807             && removeInterval((IntervalI) o));
 808   }
 809
 810   /**
 811    * Find the interval or return where it should go, possibly into the add
 812    * buffer
 813    *
 814    * @param interval
 815    * @return index (nonnegative) or index where it would go (negative)
 816    */
 817
 818   private int findInterval(IntervalI interval)
 819   {
 820
 821     if (isSorted)
 822     {
 823       int pt = binaryIdentitySearch(interval, null);
 824       // if (addPt == intervalCount || offsets[pt] == 0)
 825       // return pt;
 826       if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
 827         return pt;
 828       pt = -1 - pt;
 829         int start = interval.getBegin();
 830         int end = interval.getEnd();
 831
 832         int match = pt;
 833
 834         while ((pt = offsets[pt]) != 0)
 835         {
 836           IntervalI iv = intervals[pt];
 837           switch (compareRange(iv, start, end))
 838           {
 839           case -1:
 840             break;
 841           case 0:
 842             if (iv.equalsInterval(interval))
 843               return pt;
 844           // fall through
 845           case 1:
 846           match = pt;
 847             continue;
 848           }
 849         }
 850       return -1 - match;
 851     }
 852     else
 853     {
 854       int i = intervalCount;
 855       while (--i >= 0 && !intervals[i].equalsInterval(interval))
 856         ;
 857       return i;
 858     }
 859   }
 860
 861   /**
 862    * Uses a binary search to find the entry and removes it if found.
 863    *
 864    * @param interval
 865    * @return
 866    */
 867   protected boolean removeInterval(IntervalI interval)
 868   {
 869
 870     if (!isSorted || added > 0)
 871     {
 872       sort();
 873     }
 874     int i = binaryIdentitySearch(interval, bsDeleted);
 875     if (i < 0)
 876       return false;
 877     if (deleted == 0)
 878     {
 879       if (bsDeleted == null)
 880         bsDeleted = new BitSet(intervalCount);
 881       else
 882         bsDeleted.clear();
 883     }
 884     bsDeleted.set(i);
 885     deleted++;
 886     return (isTainted = true);
 887   }
 888
 889   private void finalizeDeletion()
 890   {
 891     if (deleted == 0)
 892       return;
 893
 894     // ......xxx.....xxxx.....xxxxx....
 895     // ......^i,pt
 896     // ...... .......
 897     // ............
 898     for (int i = bsDeleted.nextSetBit(0); i >= 0;)
 899     {
 900       int pt = i;
 901       i = bsDeleted.nextClearBit(i + 1);
 902       int pt1 = bsDeleted.nextSetBit(i + 1);
 903       if (pt1 < 0)
 904         pt1 = intervalCount;
 905       if (pt1 == pt)
 906         break;
 907       System.arraycopy(intervals, i, intervals, pt, pt1 - i);
 908       i = pt1;
 909     }
 910     intervalCount -= deleted;
 911     deleted = 0;
 912     bsDeleted.clear();
 913
 914   }
 915
 916   @Override
 917   public boolean revalidate()
 918   {
 919     isTainted = true;
 920     isSorted = false;
 921     ensureFinalized();
 922     return true;
 923   }
 924
 925   @Override
 926   public int size()
 927   {
 928     return intervalCount + added - deleted;
 929   }
 930
 931   /**
 932    * Sort intervals by start (lowest first) and end (highest first).
 933    */
 934   private void sort()
 935   {
 936     if (added > 0)
 937     {
 938       intervals = finalizeAddition(new IntervalI[intervalCount + added]);
 939     }
 940     else if (deleted > 0)
 941     {
 942       finalizeDeletion();
 943     }
 944     else
 945     {
 946       Arrays.sort(intervals, 0, intervalCount, icompare);
 947     }
 948     updateMinMaxStart();
 949     isSorted = true;
 950   }
 951
 952   private void updateMinMaxStart()
 953   {
 954     if (intervalCount > 0)
 955     {
 956       minStart = intervals[0].getBegin();
 957       maxStart = intervals[intervalCount - 1].getBegin();
 958     }
 959     else
 960     {
 961       minStart = Integer.MAX_VALUE;
 962       maxStart = Integer.MIN_VALUE;
 963     }
 964   }
 965
 966   @Override
 967   public String toString()
 968   {
 969     return prettyPrint();
 970   }
 971
 972 }