src/intervalstore/nonc/IntervalStore0.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 IntervalStore0<T extends IntervalI>
  68         extends AbstractCollection<T> implements IntervalStoreI<T>
  69 {
  70   private static int NOT_CONTAINED = Integer.MIN_VALUE;
  71
  72   /**
  73    * Search for the last interval that starts before or at the specified from/to
  74    * range and the first interval that starts after it. In the situation that
  75    * there are multiple intervals starting at from, this method returns the
  76    * first of those.
  77    *
  78    * @param a
  79    * @param from
  80    * @param to
  81    * @param ret
  82    * @return
  83    */
  84   public int binaryLastIntervalSearch(long from, 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   protected IntervalI[] intervals = new IntervalI[capacity];
 163
 164   private int[] offsets;
 165
 166   private int[] ret = new int[1];
 167
 168   protected int intervalCount;
 169
 170   private int added;
 171
 172   private int deleted;
 173
 174   private BitSet bsDeleted;
 175
 176   /**
 177    * Constructor
 178    */
 179   public IntervalStore0()
 180   {
 181     this(true);
 182   }
 183
 184   public IntervalStore0(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 IntervalStore0(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 IntervalStore0(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 IntervalStore0(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.COMPARE_BEGIN_ASC_END_DESC
 235                     : IntervalI.COMPARE_BEGIN_ASC_END_ASC);
 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, false);
 255   }
 256
 257   /**
 258    * Adds one interval to the store, optionally checking for duplicates.
 259    *
 260    * @param interval
 261    * @param allowDuplicates
 262    */
 263   @Override
 264   public boolean add(T interval, boolean allowDuplicates)
 265   {
 266     if (interval == null)
 267     {
 268       return false;
 269     }
 270
 271     if (deleted > 0)
 272     {
 273       finalizeDeletion();
 274     }
 275     if (!isTainted)
 276     {
 277       offsets = null;
 278       isTainted = true;
 279     }
 280
 281     synchronized (intervals)
 282     {
 283       int index = intervalCount;
 284       int start = interval.getBegin();
 285
 286       if (intervalCount + added + 1 >= capacity)
 287       {
 288         intervals = finalizeAddition(
 289                 new IntervalI[capacity = capacity << 1]);
 290
 291       }
 292
 293       if (DO_PRESORT && isSorted)
 294       {
 295         if (intervalCount == 0)
 296         {
 297           // ignore
 298         }
 299         else
 300         {
 301           index = findInterval(interval);
 302           if (!allowDuplicates && index >= 0)
 303           {
 304             return false;
 305           }
 306           if (index < 0)
 307           {
 308             index = -1 - index;
 309           }
 310           else
 311           {
 312             index++;
 313           }
 314         }
 315
 316       }
 317       else
 318       {
 319         if (!allowDuplicates && findInterval(interval) >= 0)
 320         {
 321           return false;
 322         }
 323         isSorted = false;
 324       }
 325
 326       if (index == intervalCount)
 327       {
 328         intervals[intervalCount++] = interval;
 329         // System.out.println("added " + intervalCount + " " + interval);
 330       }
 331       else
 332       {
 333         int pt = capacity - ++added;
 334         intervals[pt] = interval;
 335         // System.out.println("stashed " + pt + " " + interval + " for "
 336         // + index + " " + intervals[index]);
 337         if (offsets == null)
 338         {
 339           offsets = new int[capacity];
 340         }
 341
 342         offsets[pt] = offsets[index];
 343
 344         offsets[index] = pt;
 345       }
 346
 347       minStart = Math.min(minStart, start);
 348       maxStart = Math.max(maxStart, start);
 349       return true;
 350     }
 351   }
 352
 353   private IntervalI[] finalizeAddition(IntervalI[] dest)
 354   {
 355     if (dest == null)
 356     {
 357       dest = intervals;
 358     }
 359     if (added == 0)
 360     {
 361       if (intervalCount > 0 && dest != intervals)
 362       {
 363         System.arraycopy(intervals, 0, dest, 0, intervalCount);
 364       }
 365       capacity = dest.length;
 366       return dest;
 367     }
 368
 369     // array is [(intervalCount)...null...(added)]
 370
 371     int ntotal = intervalCount + added;
 372     for (int ptShift = intervalCount + added, pt = intervalCount; pt >= 0;)
 373     {
 374       int pt0 = pt;
 375       while (--pt >= 0 && offsets[pt] == 0)
 376       {
 377
 378       }
 379       if (pt < 0)
 380       {
 381         pt = 0;
 382       }
 383       int nOK = pt0 - pt;
 384       // shift upper intervals right
 385       ptShift -= nOK;
 386       if (nOK > 0)
 387       {
 388         System.arraycopy(intervals, pt, dest, ptShift, nOK);
 389       }
 390       if (added == 0)
 391       {
 392         break;
 393       }
 394       for (int offset = offsets[pt]; offset > 0; offset = offsets[offset])
 395       {
 396         dest[--ptShift] = intervals[offset];
 397         --added;
 398       }
 399     }
 400     offsets = null;
 401     intervalCount = ntotal;
 402     capacity = dest.length;
 403     return dest;
 404   }
 405
 406   public int binaryIdentitySearch(IntervalI interval)
 407   {
 408     return binaryIdentitySearch(interval, null);
 409   }
 410
 411   /**
 412    * for remove() and contains()
 413    *
 414    * @param list
 415    * @param interval
 416    * @param bsIgnore
 417    *          for deleted
 418    * @return index or, if not found, -1 - "would be here"
 419    */
 420   public int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore)
 421   {
 422     int start = 0;
 423     int r0 = interval.getBegin();
 424     int r1 = interval.getEnd();
 425     int end = intervalCount - 1;
 426     if (end < 0 || r0 < minStart)
 427     {
 428       return -1;
 429     }
 430     if (r0 > maxStart)
 431     {
 432       return -1 - intervalCount;
 433     }
 434     while (start <= end)
 435     {
 436       int mid = (start + end) >>> 1;
 437       IntervalI r = intervals[mid];
 438       switch (compareRange(r, r0, r1))
 439       {
 440       case -1:
 441         start = mid + 1;
 442         continue;
 443       case 1:
 444         end = mid - 1;
 445         continue;
 446       case 0:
 447         IntervalI iv = intervals[mid];
 448         if ((bsIgnore == null || !bsIgnore.get(mid))
 449                 && sameInterval(interval, iv))
 450         {
 451           return mid;
 452           // found one; just scan up and down now, first checking the range, but
 453           // also checking other possible aspects of equivalence.
 454         }
 455
 456         for (int i = mid; ++i <= end;)
 457         {
 458           if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() != r1)
 459           {
 460             break;
 461           }
 462           if ((bsIgnore == null || !bsIgnore.get(i))
 463                   && sameInterval(interval, iv))
 464           {
 465             return i;
 466           }
 467         }
 468         for (int i = mid; --i >= start;)
 469         {
 470           if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() < r1)
 471           {
 472             return -1 - ++i;
 473           }
 474           if ((bsIgnore == null || !bsIgnore.get(i))
 475                   && sameInterval(interval, iv))
 476           {
 477             return i;
 478           }
 479         }
 480         return -1 - start;
 481       }
 482     }
 483     return -1 - start;
 484   }
 485
 486   boolean sameInterval(IntervalI i1, IntervalI i2)
 487   {
 488     /*
 489      * do the quick test of begin/end first for speed
 490      */
 491     return i1.equalsInterval(i2) && i1.equals(i2);
 492   }
 493
 494   @Override
 495   public void clear()
 496   {
 497     intervalCount = added = 0;
 498     isSorted = true;
 499     isTainted = true;
 500     offsets = null;
 501     minStart = maxEnd = Integer.MAX_VALUE;
 502     maxStart = Integer.MIN_VALUE;
 503   }
 504
 505   /**
 506    * Compare an interval t to a from/to range for insertion purposes
 507    *
 508    * @param t
 509    * @param from
 510    * @param to
 511    * @return 0 if same, 1 if start is after from, or start equals from and
 512    *         [bigendian: end is before to | littleendian: end is after to], else
 513    *         -1
 514    */
 515   private int compareRange(IntervalI t, long from, long to)
 516   {
 517     int order = Long.signum(t.getBegin() - from);
 518     return (order == 0
 519             ? Long.signum(bigendian ? to - t.getEnd() : t.getEnd() - to)
 520             : order);
 521   }
 522
 523   @Override
 524   public boolean contains(Object entry)
 525   {
 526     if (entry == null || intervalCount == 0)
 527     {
 528       return false;
 529     }
 530     if (!isSorted || deleted > 0)
 531     {
 532       sort();
 533     }
 534     return (findInterval((IntervalI) entry) >= 0);
 535   }
 536
 537   public boolean containsInterval(IntervalI outer, IntervalI inner)
 538   {
 539     ensureFinalized();
 540     int index = binaryIdentitySearch(inner, null);
 541     if (index >= 0)
 542     {
 543       while ((index = index - Math.abs(offsets[index])) >= 0)
 544       {
 545         if (intervals[index] == outer)
 546         {
 547           return true;
 548         }
 549       }
 550     }
 551     return false;
 552   }
 553
 554   private void ensureFinalized()
 555   {
 556     if (isTainted)
 557     {
 558       if (!isSorted || added > 0 || deleted > 0)
 559       {
 560         sort();
 561       }
 562       if (offsets == null || offsets.length < intervalCount)
 563       {
 564         offsets = new int[intervalCount];
 565       }
 566       linkFeatures();
 567       isTainted = false;
 568     }
 569   }
 570
 571   /**
 572    * Find all overlaps within the given range, inclusively.
 573    *
 574    * @return a list sorted in ascending order of start position
 575    *
 576    */
 577   @Override
 578   public List<T> findOverlaps(long from, long to)
 579   {
 580     List<T> list = findOverlaps(from, to, null);
 581     Collections.reverse(list);
 582     return list;
 583   }
 584
 585   /**
 586    * Find all overlaps within the given range, inclusively.
 587    *
 588    * @return a list sorted in descending order of start position
 589    *
 590    */
 591
 592   @SuppressWarnings("unchecked")
 593   @Override
 594   public List<T> findOverlaps(long from, long to, List<T> result)
 595   {
 596     if (result == null)
 597     {
 598       result = new ArrayList<>();
 599     }
 600     switch (intervalCount + added)
 601     {
 602     case 0:
 603       return result;
 604     case 1:
 605       IntervalI sf = intervals[0];
 606       if (sf.getBegin() <= to && sf.getEnd() >= from)
 607       {
 608         result.add((T) sf);
 609       }
 610       return result;
 611     }
 612
 613     ensureFinalized();
 614
 615     if (from > maxEnd || to < minStart)
 616     {
 617       return result;
 618     }
 619     int index = binaryLastIntervalSearch(from, to, ret);
 620     int index1 = ret[0];
 621     if (index1 < 0)
 622     {
 623       return result;
 624     }
 625
 626     if (index1 > index + 1)
 627     {
 628       while (--index1 > index)
 629       {
 630         result.add((T) intervals[index1]);
 631       }
 632     }
 633     boolean isMonotonic = false;
 634     while (index >= 0)
 635     {
 636       IntervalI sf = intervals[index];
 637       if (sf.getEnd() >= from)
 638       {
 639         result.add((T) sf);
 640       }
 641       else if (isMonotonic)
 642       {
 643         break;
 644       }
 645       int offset = offsets[index];
 646       isMonotonic = (offset < 0);
 647       index -= (isMonotonic ? -offset : offset);
 648     }
 649     return result;
 650   }
 651
 652   private int getContainedBy(int index, int begin)
 653   {
 654     while (index >= 0)
 655     {
 656       IntervalI sf = intervals[index];
 657       if (sf.getEnd() >= begin)
 658       {
 659         // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
 660         // + "\nFS in " + sf.getIndex1() + ":" + sf);
 661         return index;
 662       }
 663       index -= Math.abs(offsets[index]);
 664     }
 665     return NOT_CONTAINED;
 666   }
 667
 668   @Override
 669   public int getDepth()
 670   {
 671     ensureFinalized();
 672     if (intervalCount < 2)
 673     {
 674       return intervalCount;
 675     }
 676     int maxDepth = 1;
 677     IntervalI root = null;
 678     for (int i = 0; i < intervalCount; i++)
 679     {
 680       IntervalI element = intervals[i];
 681       if (offsets[i] == NOT_CONTAINED)
 682       {
 683         root = element;
 684       }
 685       int depth = 1;
 686       int index = i;
 687       int offset;
 688       while ((index = index - Math.abs(offset = offsets[index])) >= 0)
 689       {
 690         element = intervals[index];
 691         if (++depth > maxDepth && (element == root || offset < 0))
 692         {
 693           maxDepth = depth;
 694           break;
 695         }
 696       }
 697     }
 698     return maxDepth;
 699   }
 700
 701   /**
 702    * Answers an iterator over the intervals in the store, with no particular
 703    * ordering guaranteed. The iterator does not support the optional
 704    * <code>remove</code> operation (throws
 705    * <code>UnsupportedOperationException</code> if attempted).
 706    */
 707   @Override
 708   public Iterator<T> iterator()
 709   {
 710     ensureFinalized();
 711     return new Iterator<T>()
 712     {
 713
 714       private int next;
 715
 716       @Override
 717       public boolean hasNext()
 718       {
 719         return next < intervalCount;
 720       }
 721
 722       @SuppressWarnings("unchecked")
 723       @Override
 724       public T next()
 725       {
 726         if (next >= intervalCount)
 727         {
 728           throw new NoSuchElementException();
 729         }
 730         return (T) intervals[next++];
 731       }
 732
 733     };
 734   }
 735
 736   private void linkFeatures()
 737   {
 738     if (intervalCount == 0)
 739     {
 740       return;
 741     }
 742     maxEnd = intervals[0].getEnd();
 743     offsets[0] = NOT_CONTAINED;
 744     if (intervalCount == 1)
 745     {
 746       return;
 747     }
 748     boolean isMonotonic = true;
 749     for (int i = 1; i < intervalCount; i++)
 750     {
 751       IntervalI sf = intervals[i];
 752       int begin = sf.getBegin();
 753       int index = (begin <= maxEnd ? getContainedBy(i - 1, begin) : -1);
 754       // System.out.println(sf + " is contained by "
 755       // + (index < 0 ? null : starts[index]));
 756
 757       offsets[i] = (index < 0 ? NOT_CONTAINED
 758               : isMonotonic ? index - i : i - index);
 759       isMonotonic = (sf.getEnd() > maxEnd);
 760       if (isMonotonic)
 761       {
 762         maxEnd = sf.getEnd();
 763       }
 764     }
 765
 766   }
 767
 768   @Override
 769   public String prettyPrint()
 770   {
 771     switch (intervalCount + added)
 772     {
 773     case 0:
 774       return "";
 775     case 1:
 776       return intervals[0] + "\n";
 777     }
 778     ensureFinalized();
 779     String sep = "\t";
 780     StringBuffer sb = new StringBuffer();
 781     for (int i = 0; i < intervalCount; i++)
 782     {
 783       IntervalI range = intervals[i];
 784       int index = i;
 785       while ((index = index - Math.abs(offsets[index])) >= 0)
 786       {
 787         sb.append(sep);
 788       }
 789       sb.append(range.toString()).append('\n');
 790     }
 791     return sb.toString();
 792   }
 793
 794   @Override
 795   public synchronized boolean remove(Object o)
 796   {
 797     // if (o == null)
 798     // {
 799     // throw new NullPointerException();
 800     // }
 801     return (o != null && intervalCount > 0
 802             && removeInterval((IntervalI) o));
 803   }
 804
 805   /**
 806    * Find the interval or return where it should go, possibly into the add
 807    * buffer
 808    *
 809    * @param interval
 810    * @return index (nonnegative) or index where it would go (negative)
 811    */
 812
 813   private int findInterval(IntervalI interval)
 814   {
 815
 816     if (isSorted)
 817     {
 818       int pt = binaryIdentitySearch(interval, null);
 819       // if (addPt == intervalCount || offsets[pt] == 0)
 820       // return pt;
 821       if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
 822       {
 823         return pt;
 824       }
 825       pt = -1 - pt;
 826       int start = interval.getBegin();
 827       int end = interval.getEnd();
 828
 829       int match = pt;
 830
 831       while ((pt = offsets[pt]) != 0)
 832       {
 833         IntervalI iv = intervals[pt];
 834         switch (compareRange(iv, start, end))
 835         {
 836         case -1:
 837           break;
 838         case 0:
 839           if (sameInterval(interval, iv))
 840           {
 841             return pt;
 842           }
 843           // fall through
 844         case 1:
 845           match = pt;
 846           continue;
 847         }
 848       }
 849       return -1 - match;
 850     }
 851     else
 852     {
 853       int i = intervalCount;
 854       while (--i >= 0 && !sameInterval(intervals[i], interval))
 855       {
 856
 857       }
 858       return i;
 859     }
 860   }
 861
 862   /**
 863    * Uses a binary search to find the entry and removes it if found.
 864    *
 865    * @param interval
 866    * @return
 867    */
 868   protected boolean removeInterval(IntervalI interval)
 869   {
 870
 871     if (!isSorted || added > 0)
 872     {
 873       sort();
 874     }
 875     int i = binaryIdentitySearch(interval, bsDeleted);
 876     if (i < 0)
 877     {
 878       return false;
 879     }
 880     if (deleted == 0)
 881     {
 882       if (bsDeleted == null)
 883       {
 884         bsDeleted = new BitSet(intervalCount);
 885       }
 886       else
 887       {
 888         bsDeleted.clear();
 889       }
 890     }
 891     bsDeleted.set(i);
 892     deleted++;
 893     return (isTainted = true);
 894   }
 895
 896   private void finalizeDeletion()
 897   {
 898     if (deleted == 0)
 899     {
 900       return;
 901     }
 902
 903     // ......xxx.....xxxx.....xxxxx....
 904     // ......^i,pt
 905     // ...... .......
 906     // ............
 907     for (int i = bsDeleted.nextSetBit(0), pt = i; i >= 0;)
 908     {
 909       i = bsDeleted.nextClearBit(i + 1);
 910       int pt1 = bsDeleted.nextSetBit(i + 1);
 911       if (pt1 < 0)
 912       {
 913         pt1 = intervalCount;
 914       }
 915       int n = pt1 - i;
 916       System.arraycopy(intervals, i, intervals, pt, n);
 917       pt += n;
 918       if (pt1 == intervalCount)
 919       {
 920         for (i = pt1; --i >= pt;)
 921         {
 922           intervals[i] = null;
 923         }
 924         intervalCount -= deleted;
 925         deleted = 0;
 926         bsDeleted.clear();
 927         break;
 928       }
 929       i = pt1;
 930     }
 931
 932   }
 933
 934   @Override
 935   public int size()
 936   {
 937     return intervalCount + added - deleted;
 938   }
 939
 940   @Override
 941   public Object[] toArray()
 942   {
 943     ensureFinalized();
 944     return super.toArray();
 945   }
 946
 947   /**
 948    * Sort intervals by start (lowest first) and end (highest first).
 949    */
 950   private void sort()
 951   {
 952     if (added > 0)
 953     {
 954       intervals = finalizeAddition(new IntervalI[intervalCount + added]);
 955     }
 956     else if (deleted > 0)
 957     {
 958       finalizeDeletion();
 959     }
 960     else
 961     {
 962       Arrays.sort(intervals, 0, intervalCount, icompare);
 963     }
 964     updateMinMaxStart();
 965     isSorted = true;
 966   }
 967
 968   private void updateMinMaxStart()
 969   {
 970     if (intervalCount > 0)
 971     {
 972       minStart = intervals[0].getBegin();
 973       maxStart = intervals[intervalCount - 1].getBegin();
 974     }
 975     else
 976     {
 977       minStart = Integer.MAX_VALUE;
 978       maxStart = Integer.MIN_VALUE;
 979     }
 980   }
 981
 982   @Override
 983   public String toString()
 984   {
 985     return prettyPrint();
 986   }
 987 }