dcapwell commented on code in PR #6:
URL: https://github.com/apache/cassandra-accord/pull/6#discussion_r942839177
##########
accord-core/src/main/java/accord/utils/SortedArrays.java:
##########
@@ -0,0 +1,535 @@
+package accord.utils;
+
+import java.util.Arrays;
+import java.util.function.IntFunction;
+
+import org.apache.cassandra.utils.concurrent.Inline;
+
+import static java.util.Arrays.*;
+
+public class SortedArrays
+{
+ /**
+ * Given two sorted arrays, return an array containing the elements
present in either, preferentially returning one
+ * of the inputs if it contains all elements of the other.
+ *
+ * TODO: introduce exponential search optimised version
+ */
+ public static <T extends Comparable<? super T>> T[] linearUnion(T[] left,
T[] right, IntFunction<T[]> allocate)
+ {
+ int leftIdx = 0;
+ int rightIdx = 0;
+
+ T[] result = null;
+ int resultSize = 0;
+
+ // first, pick the superset candidate and merge the two until we find
the first missing item
+ // if none found, return the superset candidate
+ if (left.length >= right.length)
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp <= 0)
+ {
+ leftIdx += 1;
+ rightIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = leftIdx;
+ result = allocate.apply(resultSize + (left.length -
leftIdx) + (right.length - (rightIdx - 1)));
+ System.arraycopy(left, 0, result, 0, resultSize);
+ result[resultSize++] = right[rightIdx++];
+ break;
+ }
+ }
+
+ if (result == null)
+ {
+ if (rightIdx == right.length)
+ return left;
+ result = allocate.apply(left.length + (right.length -
rightIdx));
+ resultSize = leftIdx;
+ System.arraycopy(left, 0, result, 0, resultSize);
+ }
+ }
+ else
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp >= 0)
+ {
+ rightIdx += 1;
+ leftIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = rightIdx;
+ result = allocate.apply(resultSize + (left.length -
(leftIdx - 1)) + (right.length - rightIdx));
+ System.arraycopy(right, 0, result, 0, resultSize);
+ result[resultSize++] = left[leftIdx++];
+ break;
+ }
+ }
+
+ if (result == null)
+ {
+ if (leftIdx == left.length)
+ return right;
+ result = allocate.apply(right.length + (left.length -
leftIdx));
+ resultSize = rightIdx;
+ System.arraycopy(right, 0, result, 0, resultSize);
+ }
+ }
+
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ T leftKey = left[leftIdx];
+ T rightKey = right[rightIdx];
+ int cmp = leftKey.compareTo(rightKey);
+ T minKey;
+ if (cmp == 0)
+ {
+ leftIdx++;
+ rightIdx++;
+ minKey = leftKey;
+ }
+ else if (cmp < 0)
+ {
+ leftIdx++;
+ minKey = leftKey;
+ }
+ else
+ {
+ rightIdx++;
+ minKey = rightKey;
+ }
+ result[resultSize++] = minKey;
+ }
+
+ while (leftIdx < left.length)
+ result[resultSize++] = left[leftIdx++];
+
+ while (rightIdx < right.length)
+ result[resultSize++] = right[rightIdx++];
+
+ if (resultSize < result.length)
+ result = copyOf(result, resultSize);
+
+ return result;
+ }
+
+ /**
+ * Given two sorted arrays, return the elements present only in both,
preferentially returning one of the inputs if
+ * it contains no elements not present in the other.
+ *
+ * TODO: introduce exponential search optimised version
+ */
+ @SuppressWarnings("unused") // was used until recently, might be used
again?
+ public static <T extends Comparable<? super T>> T[] linearIntersection(T[]
left, T[] right, IntFunction<T[]> allocate)
+ {
+ int leftIdx = 0;
+ int rightIdx = 0;
+
+ T[] result = null;
+ int resultSize = 0;
+
+ // first pick a subset candidate, and merge both until we encounter an
element not present in the other array
+ if (left.length <= right.length)
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp >= 0)
+ {
+ rightIdx += 1;
+ leftIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = leftIdx++;
+ result = allocate.apply(resultSize + Math.min(left.length
- leftIdx, right.length - rightIdx));
+ System.arraycopy(left, 0, result, 0, resultSize);
+ break;
+ }
+ }
+
+ if (result == null)
+ return left;
+ }
+ else
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp <= 0)
+ {
+ leftIdx += 1;
+ rightIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = rightIdx++;
+ result = allocate.apply(resultSize + Math.min(left.length
- leftIdx, right.length - rightIdx));
+ System.arraycopy(right, 0, result, 0, resultSize);
+ break;
+ }
+ }
+
+ if (result == null)
+ return right;
Review Comment:
same comment as above, why return `right` when we don't have any
intersections?
##########
accord-core/src/main/java/accord/utils/SortedArrays.java:
##########
@@ -0,0 +1,535 @@
+package accord.utils;
+
+import java.util.Arrays;
+import java.util.function.IntFunction;
+
+import org.apache.cassandra.utils.concurrent.Inline;
+
+import static java.util.Arrays.*;
+
+public class SortedArrays
+{
+ /**
+ * Given two sorted arrays, return an array containing the elements
present in either, preferentially returning one
+ * of the inputs if it contains all elements of the other.
+ *
+ * TODO: introduce exponential search optimised version
+ */
+ public static <T extends Comparable<? super T>> T[] linearUnion(T[] left,
T[] right, IntFunction<T[]> allocate)
+ {
+ int leftIdx = 0;
+ int rightIdx = 0;
+
+ T[] result = null;
+ int resultSize = 0;
+
+ // first, pick the superset candidate and merge the two until we find
the first missing item
+ // if none found, return the superset candidate
+ if (left.length >= right.length)
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp <= 0)
+ {
+ leftIdx += 1;
+ rightIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = leftIdx;
+ result = allocate.apply(resultSize + (left.length -
leftIdx) + (right.length - (rightIdx - 1)));
+ System.arraycopy(left, 0, result, 0, resultSize);
+ result[resultSize++] = right[rightIdx++];
+ break;
+ }
+ }
+
+ if (result == null)
+ {
+ if (rightIdx == right.length)
+ return left;
+ result = allocate.apply(left.length + (right.length -
rightIdx));
+ resultSize = leftIdx;
+ System.arraycopy(left, 0, result, 0, resultSize);
+ }
+ }
+ else
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp >= 0)
+ {
+ rightIdx += 1;
+ leftIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = rightIdx;
+ result = allocate.apply(resultSize + (left.length -
(leftIdx - 1)) + (right.length - rightIdx));
+ System.arraycopy(right, 0, result, 0, resultSize);
+ result[resultSize++] = left[leftIdx++];
+ break;
+ }
+ }
+
+ if (result == null)
+ {
+ if (leftIdx == left.length)
+ return right;
+ result = allocate.apply(right.length + (left.length -
leftIdx));
+ resultSize = rightIdx;
+ System.arraycopy(right, 0, result, 0, resultSize);
+ }
+ }
+
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ T leftKey = left[leftIdx];
+ T rightKey = right[rightIdx];
+ int cmp = leftKey.compareTo(rightKey);
+ T minKey;
+ if (cmp == 0)
+ {
+ leftIdx++;
+ rightIdx++;
+ minKey = leftKey;
+ }
+ else if (cmp < 0)
+ {
+ leftIdx++;
+ minKey = leftKey;
+ }
+ else
+ {
+ rightIdx++;
+ minKey = rightKey;
+ }
+ result[resultSize++] = minKey;
+ }
+
+ while (leftIdx < left.length)
+ result[resultSize++] = left[leftIdx++];
+
+ while (rightIdx < right.length)
+ result[resultSize++] = right[rightIdx++];
+
+ if (resultSize < result.length)
+ result = copyOf(result, resultSize);
+
+ return result;
+ }
+
+ /**
+ * Given two sorted arrays, return the elements present only in both,
preferentially returning one of the inputs if
+ * it contains no elements not present in the other.
+ *
+ * TODO: introduce exponential search optimised version
+ */
+ @SuppressWarnings("unused") // was used until recently, might be used
again?
+ public static <T extends Comparable<? super T>> T[] linearIntersection(T[]
left, T[] right, IntFunction<T[]> allocate)
+ {
+ int leftIdx = 0;
+ int rightIdx = 0;
+
+ T[] result = null;
+ int resultSize = 0;
+
+ // first pick a subset candidate, and merge both until we encounter an
element not present in the other array
+ if (left.length <= right.length)
+ {
+ while (leftIdx < left.length && rightIdx < right.length)
+ {
+ int cmp = left[leftIdx].compareTo(right[rightIdx]);
+ if (cmp >= 0)
+ {
+ rightIdx += 1;
+ leftIdx += cmp == 0 ? 1 : 0;
+ }
+ else
+ {
+ resultSize = leftIdx++;
+ result = allocate.apply(resultSize + Math.min(left.length
- leftIdx, right.length - rightIdx));
+ System.arraycopy(left, 0, result, 0, resultSize);
+ break;
+ }
+ }
+
+ if (result == null)
+ return left;
Review Comment:
why return left in this case? Been working on tests for this class and this
fails in the following case
```
Property error detected:
Seed = 3576953691942488024
Examples = 1000000
Pure = true
Error: array lengths differ, expected: <0> but was: <1>
Values:
0 = [1459905072]
1 = [-1799119784, -1117722578, -1072178078, -1012124199, -804935562,
-688955866, 95532926, 410144613, 604870749, 1070710384]
```
test
```
@Test
public void testLinearIntersection()
{
Gen<Integer[]> gen = Gens.arrays(Integer.class, Gens.ints().all())
.unique()
.ofSizeBetween(0, 100)
.map(a -> {
Arrays.sort(a);
return a;
});
qt().withSeed(3576953691942488024L).forAll(gen, gen).check((a, b) ->
{
Set<Integer> left = new HashSet<>(Arrays.asList(a));
Set<Integer> right = new HashSet<>(Arrays.asList(b));
Set<Integer> intersection = Sets.intersection(left, right);
Integer[] expected = intersection.toArray(Integer[]::new);
Arrays.sort(expected);
Integer[] actual = SortedArrays.linearIntersection(a, b,
Integer[]::new);
Assertions.assertArrayEquals(expected, actual);
});
}
```
So, when we see there isn't an overlap we return `left` when left is
smaller than right, else we return `right`? This seems confusing to me as the
caller can never detect the case where there is zero intersections
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
