in accord-core/src/main/java/accord/utils/RelationMultiMap.java [619:868]
T linearUnion(K[] leftKeys, int leftKeysLength, V[] leftValues, int leftValuesLength, int[] left, int leftLength,
K[] rightKeys, int rightKeysLength, V[] rightValues, int rightValuesLength, int[] right, int rightLength,
SymmetricComparator<? super K> keyComparator, SymmetricComparator<? super V> valueComparator,
@Nullable BiFunction<? super K, ? super K, ? extends K> keyMerger, @Nullable BiFunction<? super V, ? super V, ? extends V> valueMerger,
ObjectBuffers<K> keyBuffers, ObjectBuffers<V> valueBuffers, IntBuffers intBuffers, Constructor<K, V, T> constructor)
{
int[] remapLeft = null, remapRight = null, out = null;
int outLength = 0, outKeysLength = 0, outValuesLength = 0;
try
{
K[] outKeys = SortedArrays.linearUnion(leftKeys, 0, leftKeysLength, rightKeys, 0, rightKeysLength, keyComparator, keyMerger, keyBuffers);
outKeysLength = keyBuffers.sizeOfLast(outKeys);
V[] outValues = SortedArrays.linearUnion(leftValues, 0, leftValuesLength, rightValues, 0, rightValuesLength, valueComparator, valueMerger, valueBuffers);
outValuesLength = valueBuffers.sizeOfLast(outValues);
remapLeft = remapToSuperset(leftValues, leftValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
remapRight = remapToSuperset(rightValues, rightValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
if (remapLeft == null && remapRight == null && leftLength == rightLength && leftKeysLength == rightKeysLength
&& arraysEqual(left, right, rightLength)
&& arraysEqual(leftKeys, rightKeys, rightKeysLength)
)
{
return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
}
int lk = 0, rk = 0, ok = 0, l = leftKeysLength, r = rightKeysLength;
outLength = outKeysLength;
if (remapLeft == null && outKeys == leftKeys)
{
// "this" knows all the TxnId and Keys already, but do both agree on what Keys map to TxnIds?
noOp: while (lk < leftKeysLength && rk < rightKeysLength)
{
int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
if (ck < 0)
{
// "this" knows of a key not present in "that"
outLength += left[lk] - l; // logically append the key's TxnIds to the size
l = left[lk];
assert outLength == l && ok == lk && left[ok] == outLength;
ok++;
lk++;
}
else if (ck > 0)
{
// if this happened there is a bug with keys.union or keys are not actually sorted
throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, true);
}
else
{
// both "this" and "that" know of the key
while (l < left[lk] && r < right[rk])
{
int nextLeft = left[l];
int nextRight = remap(right[r], remapRight);
if (nextLeft < nextRight)
{
// "this" knows of the txn that "that" didn't
outLength++;
l++;
}
else if (nextRight < nextLeft)
{
out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
break noOp;
}
else
{
outLength++;
l++;
r++;
}
}
if (l < left[lk])
{
outLength += left[lk] - l;
l = left[lk];
}
else if (r < right[rk])
{
// "that" thinks a key includes a TxnId as a dependency but "this" doesn't, need to include this knowledge
out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
break;
}
assert outLength == l && ok == lk && left[ok] == outLength;
ok++;
rk++;
lk++;
}
}
if (out == null)
return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
}
else if (remapRight == null && outKeys == rightKeys)
{
// "that" knows all the TxnId and keys already, but "this" does not
noOp: while (lk < leftKeysLength && rk < rightKeysLength)
{
int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
if (ck < 0)
{
// if this happened there is a bug with keys.union or keys are not actually sorted
throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, false);
}
else if (ck > 0)
{
outLength += right[rk] - r;
r = right[rk];
assert outLength == r && ok == rk && right[ok] == outLength;
ok++;
rk++;
}
else
{
// both "this" and "that" know of the key
while (l < left[lk] && r < right[rk])
{
int nextLeft = remap(left[l], remapLeft);
int nextRight = right[r];
if (nextLeft < nextRight)
{
// "this" thinks a TxnID depends on Key but "that" doesn't, need to include this knowledge
out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
break noOp;
}
else if (nextRight < nextLeft)
{
// "that" knows of the txn that "this" didn't
outLength++;
r++;
}
else
{
outLength++;
l++;
r++;
}
}
if (l < left[lk])
{
out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
break;
}
else if (r < right[rk])
{
outLength += right[rk] - r;
r = right[rk];
}
assert outLength == r && ok == rk && right[ok] == outLength;
ok++;
rk++;
lk++;
}
}
if (out == null)
return constructor.construct(rightKeys, rightKeysLength, rightValues, rightValuesLength, right, rightLength);
}
else
{
out = intBuffers.getInts(leftLength + rightLength);
}
while (lk < leftKeysLength && rk < rightKeysLength)
{
int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
if (ck < 0)
{
while (l < left[lk])
out[outLength++] = remap(left[l++], remapLeft);
out[ok++] = outLength;
lk++;
}
else if (ck > 0)
{
while (r < right[rk])
out[outLength++] = remap(right[r++], remapRight);
out[ok++] = outLength;
rk++;
}
else
{
while (l < left[lk] && r < right[rk])
{
int nextLeft = remap(left[l], remapLeft);
int nextRight = remap(right[r], remapRight);
if (nextLeft <= nextRight)
{
out[outLength++] = nextLeft;
l += 1;
r += nextLeft == nextRight ? 1 : 0;
}
else
{
out[outLength++] = nextRight;
++r;
}
}
while (l < left[lk])
out[outLength++] = remap(left[l++], remapLeft);
while (r < right[rk])
out[outLength++] = remap(right[r++], remapRight);
out[ok++] = outLength;
rk++;
lk++;
}
}
while (lk < leftKeysLength)
{
while (l < left[lk])
out[outLength++] = remap(left[l++], remapLeft);
out[ok++] = outLength;
lk++;
}
while (rk < rightKeysLength)
{
while (r < right[rk])
out[outLength++] = remap(right[r++], remapRight);
out[ok++] = outLength;
rk++;
}
return constructor.construct(outKeys, outKeysLength, outValues, outValuesLength, out, outLength);
}
finally
{
if (out != null)
intBuffers.discard(out, outLength);
if (remapLeft != null)
intBuffers.forceDiscard(remapLeft);
if (remapRight != null)
intBuffers.forceDiscard(remapRight);
}
}