}
if (deleted > 0)
+ {
finalizeDeletion();
+ }
if (!isTainted)
{
offsets = null;
return false;
}
if (index < 0)
+ {
index = -1 - index;
+ }
else
+ {
index++;
+ }
}
}
{
return false;
}
-
+ isSorted = false;
}
if (index == intervalCount)
// System.out.println("stashed " + pt + " " + interval + " for "
// + index + " " + intervals[index]);
if (offsets == null)
+ {
offsets = new int[capacity];
+ }
offsets[pt] = offsets[index];
private IntervalI[] finalizeAddition(IntervalI[] dest)
{
if (dest == null)
+ {
dest = intervals;
+ }
if (added == 0)
{
if (intervalCount > 0 && dest != intervals)
{
int pt0 = pt;
while (--pt >= 0 && offsets[pt] == 0)
+ {
;
+ }
if (pt < 0)
+ {
pt = 0;
+ }
int nOK = pt0 - pt;
// shift upper intervals right
ptShift -= nOK;
if (nOK > 0)
+ {
System.arraycopy(intervals, pt, dest, ptShift, nOK);
+ }
if (added == 0)
+ {
break;
+ }
for (int offset = offsets[pt]; offset > 0; offset = offsets[offset])
{
dest[--ptShift] = intervals[offset];
int r1 = interval.getEnd();
int end = intervalCount - 1;
if (end < 0 || r0 < minStart)
+ {
return -1;
+ }
if (r0 > maxStart)
+ {
return -1 - intervalCount;
+ }
while (start <= end)
{
int mid = (start + end) >>> 1;
IntervalI iv = intervals[mid];
if ((bsIgnore == null || !bsIgnore.get(mid))
&& iv.equalsInterval(interval))
+ {
return mid;
// found one; just scan up and down now, first checking the range, but
// also checking other possible aspects of equivalence.
+ }
for (int i = mid; ++i <= end;)
{
if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() != r1)
+ {
break;
+ }
if ((bsIgnore == null || !bsIgnore.get(i))
&& iv.equalsInterval(interval))
+ {
return i;
+ }
}
for (int i = mid; --i >= start;)
{
if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() < r1)
+ {
return -1 - ++i;
+ }
if ((bsIgnore == null || !bsIgnore.get(i))
&& iv.equalsInterval(interval))
+ {
return i;
+ }
}
return -1 - start;
}
private int compareRange(IntervalI t, long from, long to)
{
if (t == null)
+ {
System.out.println("???");
+ }
int order = Long.signum(t.getBegin() - from);
return (order == 0
? Long.signum(bigendian ? to - t.getEnd() : t.getEnd() - to)
public boolean contains(Object entry)
{
if (entry == null || intervalCount == 0)
+ {
return false;
+ }
if (!isSorted || deleted > 0)
{
sort();
ensureFinalized();
int index = binaryIdentitySearch(inner, null);
if (index >= 0)
+ {
while ((index = index - Math.abs(offsets[index])) >= 0)
{
if (intervals[index] == outer)
return true;
}
}
+ }
return false;
}
private void ensureFinalized()
{
- if (isTainted && intervalCount + added > 1)
+ if (isTainted)
{
if (!isSorted || added > 0 || deleted > 0)
{
sort();
}
if (offsets == null || offsets.length < intervalCount)
+ {
offsets = new int[intervalCount];
+ }
linkFeatures();
isTainted = false;
}
ensureFinalized();
if (from > maxEnd || to < minStart)
+ {
return result;
+ }
int index = binaryLastIntervalSearch(from, to, ret);
int index1 = ret[0];
if (index1 < 0)
+ {
return result;
+ }
if (index1 > index + 1)
{
public IntervalI get(int i)
{
if (i < 0 || i >= intervalCount + added)
+ {
return null;
+ }
ensureFinalized();
return intervals[i];
}
@Override
public Iterator<T> iterator()
{
- finalizeAddition(null);
+ ensureFinalized();
return new Iterator<T>()
{
public T next()
{
if (next >= intervalCount)
+ {
throw new NoSuchElementException();
+ }
return (T) intervals[next++];
}
private void linkFeatures()
{
if (intervalCount == 0)
+ {
return;
+ }
maxEnd = intervals[0].getEnd();
offsets[0] = IntervalI.NOT_CONTAINED;
if (intervalCount == 1)
// if (addPt == intervalCount || offsets[pt] == 0)
// return pt;
if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
+ {
return pt;
+ }
pt = -1 - pt;
int start = interval.getBegin();
int end = interval.getEnd();
break;
case 0:
if (iv.equalsInterval(interval))
+ {
return pt;
+ }
// fall through
case 1:
match = pt;
{
int i = intervalCount;
while (--i >= 0 && !intervals[i].equalsInterval(interval))
+ {
;
+ }
return i;
}
}
}
int i = binaryIdentitySearch(interval, bsDeleted);
if (i < 0)
+ {
return false;
+ }
if (deleted == 0)
{
if (bsDeleted == null)
+ {
bsDeleted = new BitSet(intervalCount);
+ }
else
+ {
bsDeleted.clear();
+ }
}
bsDeleted.set(i);
deleted++;
private void finalizeDeletion()
{
if (deleted == 0)
+ {
return;
+ }
// ......xxx.....xxxx.....xxxxx....
// ......^i,pt
i = bsDeleted.nextClearBit(i + 1);
int pt1 = bsDeleted.nextSetBit(i + 1);
if (pt1 < 0)
+ {
pt1 = intervalCount;
+ }
int n = pt1 - i;
System.arraycopy(intervals, i, intervals, pt, n);
pt += n;
if (pt1 == intervalCount)
{
for (i = pt1; --i >= pt;)
+ {
intervals[i] = null;
+ }
intervalCount -= deleted;
deleted = 0;
bsDeleted.clear();
return intervalCount + added - deleted;
}
+ @Override
+ public Object[] toArray()
+ {
+ ensureFinalized();
+ return super.toArray();
+ }
+
/**
* Sort intervals by start (lowest first) and end (highest first).
*/