dcapwell commented on code in PR #6:
URL: https://github.com/apache/cassandra-accord/pull/6#discussion_r943688428
##########
accord-core/src/main/java/accord/primitives/Keys.java:
##########
@@ -0,0 +1,449 @@
+package accord.primitives;
+
+import java.util.*;
+import java.util.function.IntFunction;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import accord.api.Key;
+import accord.utils.IndexedFold;
+import accord.utils.IndexedFoldIntersectToLong;
+import accord.utils.IndexedFoldToLong;
+import accord.utils.IndexedPredicate;
+import accord.utils.IndexedRangeFoldToLong;
+import accord.utils.SortedArrays;
+import org.apache.cassandra.utils.concurrent.Inline;
+
+@SuppressWarnings("rawtypes")
+// TODO: this should probably be a BTree
+// TODO: check that foldl call-sites are inlined and optimised by HotSpot
+public class Keys implements Iterable<Key>
+{
+ public static final Keys EMPTY = new Keys(new Key[0]);
+
+ final Key[] keys;
+
+ public Keys(SortedSet<? extends Key> keys)
+ {
+ this.keys = keys.toArray(Key[]::new);
+ }
+
+ public Keys(Collection<? extends Key> keys)
+ {
+ this.keys = keys.toArray(Key[]::new);
+ Arrays.sort(this.keys);
+ }
+
+ public Keys(Key[] keys)
+ {
+ this.keys = keys;
+ Arrays.sort(keys);
+ }
+
+ @Override
+ public boolean equals(Object o)
+ {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+ Keys keys1 = (Keys) o;
+ return Arrays.equals(keys, keys1.keys);
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return Arrays.hashCode(keys);
+ }
+
+ public int indexOf(Key key)
+ {
+ return Arrays.binarySearch(keys, key);
+ }
+
+ public boolean contains(Key key)
+ {
+ return indexOf(key) >= 0;
+ }
+
+ public Key get(int indexOf)
+ {
+ return keys[indexOf];
+ }
+
+ public boolean isEmpty()
+ {
+ return keys.length == 0;
+ }
+
+ public int size()
+ {
+ return keys.length;
+ }
+
+ public Keys select(int[] indexes)
+ {
+ Key[] selection = new Key[indexes.length];
+ for (int i = 0 ; i < indexes.length ; ++i)
+ selection[i] = keys[indexes[i]];
+ return new Keys(selection);
+ }
+
+ /**
+ * return true if this keys collection contains all keys found in the
given keys
+ */
+ public boolean containsAll(Keys that)
+ {
+ if (that.isEmpty())
+ return true;
+
+ return foldlIntersect(that, (li, ri, k, p, v) -> v + 1, 0, 0, 0) ==
that.size();
+ }
+
+ public Keys union(Keys that)
+ {
+ return wrap(SortedArrays.linearUnion(keys, that.keys, Key[]::new),
that);
+ }
+
+ public Keys intersect(Keys that)
+ {
+ return wrap(SortedArrays.linearIntersection(keys, that.keys,
Key[]::new), that);
+ }
+
+ public Keys slice(KeyRanges ranges)
+ {
+ return wrap(SortedArrays.sliceWithOverlaps(keys, ranges.ranges,
Key[]::new, (k, r) -> -r.compareTo(k), KeyRange::compareTo));
Review Comment:
> KeyRanges self enforces sorting and no overlaps for all of its own actions
Where do we `enforce`? Most methods make an assumption that the data is
sorted and without overlaps, but nothing sorts this or fails on overlaps, and
the only caller in `src` is topology, which uses the order from the user (in
our case C*)... so I have yet to find anything that makes this a sorted array
or disallow range overlaps.
> Perhaps the method is poorly named ... not that either side may permit
overlaps
I didn't do range overlaps because this called itself `overlaps`, I did
range overlaps because `KeyRanges` "allows" it as it never sanitizes its inputs
(if inputs were 100% controlled then I wouldn't do this, but the inputs are
from users that provide `Shard`, so the correctness of this class is 100%
dependent on users). Since I couldn't find any ordering or control of its
inputs, I went with what it "allows" regardless of what its methods assume,
this then drives the statement that I posted, that what is allowed vs what is
expected doesn't match.
> if any. I will add javadoc to explain all of this.
In this case I don't feel a javadoc is best, the input to this is from
users, so without sanitizing to enforce assumptions, this isn't really safe.
Also looking at the single usage (creation) its done once per topology, so
validating assumptions is something we could do on that path and then all the
internal methods can avoid those checks as the assumptions were already handled.
--
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]
