dcapwell commented on code in PR #50:
URL: https://github.com/apache/cassandra-accord/pull/50#discussion_r1240157341
##########
accord-core/src/main/java/accord/primitives/AbstractRanges.java:
##########
@@ -561,10 +635,26 @@ static <RS extends AbstractRanges<?>> RS
of(Function<Range[], RS> constructor, R
if (ranges.length == 0)
return constructor.apply(NO_RANGES);
- return sortAndDeoverlap(constructor, ranges, ranges.length);
+ return sortAndDeoverlap(constructor, ranges, ranges.length,
UnionMode.MERGE_OVERLAPPING);
+ }
+
+ static <RS extends AbstractRanges<?>> RS
sortAndDeoverlap(Function<Range[], RS> constructor, Range[] ranges, int count,
UnionMode mode)
+ {
+ if (count > 1 && !isSorted(ranges, Range::compareTo))
+ {
+ ranges = ranges.clone();
+ Arrays.sort(ranges, 0, count, Range::compare);
+ }
+
+ return deoverlapSorted(constructor, ranges, count, mode, false);
+ }
+
+ static <RS extends AbstractRanges<?>> RS deoverlapSorted(Function<Range[],
RS> constructor, Range[] ranges, int count, UnionMode mode)
+ {
+ return deoverlapSorted(constructor, ranges, count, mode, true);
}
- static <RS extends AbstractRanges<?>> RS
sortAndDeoverlap(Function<Range[], RS> constructor, Range[] ranges, int count)
+ private static <RS extends AbstractRanges<?>> RS
deoverlapSorted(Function<Range[], RS> constructor, Range[] ranges, int count,
UnionMode mode, boolean copyOnWrite)
Review Comment:
`copyOnWrite` is not used
##########
accord-core/src/main/java/accord/primitives/RangeDeps.java:
##########
@@ -229,11 +254,76 @@ public void forEach(Ranges ranges, Consumer<TxnId>
forEach)
/**
* The same TxnId may be provided as a parameter multiple times
*/
- public <P> void forEach(Ranges ranges, IndexedConsumer<P> forEach, P param)
+ public <P> void forEach(Unseekables<?> unseekables, P param,
IndexedConsumer<P> forEach)
+ {
+ forEach(unseekables, null, 0, unseekables.size(), param, forEach);
+ }
+
+ /**
+ * The same TxnId may be provided as a parameter multiple times
+ * @param slice is only useful in case unseekables is a Ranges, in which
case we only visit the intersection of the slice and the ranges we walk
+ * for keys it is expected that the caller has already sliced
in this manner
+ */
+ public <P> void forEach(Unseekables<?> unseekables, @Nullable Range slice,
int from, int to, P param, IndexedConsumer<P> forEach)
+ {
+ switch (unseekables.domain())
+ {
+ default: throw new AssertionError();
Review Comment:
```suggestion
default: throw new AssertionError("Unknown domain: " +
unseekables.domain());
```
##########
accord-core/src/main/java/accord/primitives/RoutingKeys.java:
##########
@@ -55,12 +55,23 @@ public static RoutingKeys ofSortedUnique(RoutingKey ...
keys)
}
@Override
- public Unseekables<RoutingKey, ?> with(Unseekables<RoutingKey, ?> with)
+ public RoutingKeys with(Unseekables<RoutingKey> with)
{
- AbstractKeys<RoutingKey, ?> that = (AbstractKeys<RoutingKey, ?>) with;
- return wrap(SortedArrays.linearUnion(keys, that.keys,
cachedRoutingKeys()), that);
+ return with((AbstractKeys<RoutingKey>) with);
}
+ @Override
+ public RoutingKeys with(Participants<RoutingKey> with)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public RoutingKeys with(Participants<RoutingKey> with)
```
##########
accord-core/src/main/java/accord/primitives/SyncPoint.java:
##########
@@ -30,13 +33,21 @@ public class SyncPoint
{
public final TxnId syncId;
public final Deps waitFor;
- public final Route<?> route;
+ public final Ranges ranges;
+ public final RoutingKey homeKey;
- public SyncPoint(TxnId syncId, Deps waitFor, Route<?> route)
+ public SyncPoint(TxnId syncId, Deps waitFor, Ranges ranges, FullRangeRoute
route)
{
+ Invariants.checkArgument(ranges.toRoute(route.homeKey).equals(route));
Review Comment:
```suggestion
Invariants.checkArgument(ranges.toRoute(route.homeKey).equals(route), "Expected
homeKey from route %s to be in ranges %s", route, ranges);
```
##########
accord-core/src/main/java/accord/utils/Timestamped.java:
##########
@@ -35,14 +35,34 @@ public Timestamped(Timestamp timestamp, T data)
public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b)
{
- return a.timestamp.compareTo(b.timestamp) >= 0 ? a : b;
+ return a.timestamp.compareTo(b.timestamp) < 0 ? b : a;
}
- public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testEquality)
+ public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testPrefix, BiPredicate<T, T> testEquality)
{
int c = a.timestamp.compareTo(b.timestamp);
- if (c == 0) Invariants.checkArgument(testEquality.test(a.data,
b.data));
- return c >= 0 ? a : b;
+ if (c == 0)
+ {
+ Invariants.checkArgument(testEquality.test(a.data, b.data));
Review Comment:
```suggestion
Invariants.checkArgument(testEquality.test(a.data, b.data), "%s
!= %s", a, b);
```
##########
accord-core/src/main/java/accord/impl/CommandTimeseries.java:
##########
@@ -103,6 +102,10 @@ public Timestamp maxTimestamp()
{
return commands.isEmpty() ? Timestamp.NONE : commands.keySet().last();
}
+ public Timestamp minTimestamp()
Review Comment:
can you add a space between this and `maxTimestamp`
##########
accord-core/src/main/java/accord/primitives/AbstractRanges.java:
##########
@@ -28,11 +28,15 @@
import java.util.*;
import java.util.function.Function;
+import static accord.primitives.Ranges.EMPTY;
+import static accord.primitives.Ranges.ofSortedAndDeoverlappedUnchecked;
import static accord.utils.ArrayBuffers.cachedRanges;
+import static accord.utils.SortedArrays.Search.CEIL;
import static accord.utils.SortedArrays.Search.FAST;
+import static accord.utils.SortedArrays.isSorted;
import static accord.utils.SortedArrays.swapHighLow32b;
-public abstract class AbstractRanges<RS extends Routables<Range, ?>>
implements Iterable<Range>, Routables<Range, RS>
+public abstract class AbstractRanges<RS extends Routables<Range>> implements
Iterable<Range>, Routables<Range>
Review Comment:
`RS` is now dead code as its not used in `Routables<Range, RS>` anymore
##########
accord-core/src/main/java/accord/primitives/Deps.java:
##########
@@ -138,6 +139,21 @@ public int txnIdCount()
return keyDeps.txnIdCount() + rangeDeps.txnIdCount();
}
+ public int indexOf(TxnId txnId)
+ {
+ switch (txnId.domain())
+ {
+ default: throw new AssertionError();
Review Comment:
```suggestion
default: throw new AssertionError("Unknown domain: " +
txnId.domain());
```
##########
accord-core/src/main/java/accord/primitives/KeyRoute.java:
##########
@@ -27,48 +29,98 @@
import static accord.utils.ArrayBuffers.cachedRoutingKeys;
-public abstract class KeyRoute extends
AbstractUnseekableKeys<Route<RoutingKey>> implements Route<RoutingKey>
+public abstract class KeyRoute extends AbstractUnseekableKeys implements
Route<RoutingKey>
{
public final RoutingKey homeKey;
+ public final boolean isParticipatingHomeKey;
- KeyRoute(@Nonnull RoutingKey homeKey, RoutingKey[] keys)
+ KeyRoute(@Nonnull RoutingKey homeKey, boolean isParticipatingHomeKey,
RoutingKey[] keys)
{
super(keys);
this.homeKey = Invariants.nonNull(homeKey);
+ this.isParticipatingHomeKey = isParticipatingHomeKey;
+ }
+
+ @Override
+ public boolean participatesIn(Ranges ranges)
+ {
+ if (isParticipatingHomeKey())
+ return intersects(ranges);
+
+ long ij = findNextIntersection(0, ranges, 0);
+ if (ij < 0)
+ return false;
+
+ int i = (int)ij;
+ if (!get(i).equals(homeKey))
+ return true;
+
+ int j = (int)(ij >>> 32);
+ return findNextIntersection(i + 1, ranges, j) >= 0;
}
@Override
- public Unseekables<RoutingKey, ?> toMaximalUnseekables()
+ public Unseekables<RoutingKey> with(Unseekables<RoutingKey> with)
{
- return new RoutingKeys(SortedArrays.insert(keys, homeKey,
RoutingKey[]::new));
+ AbstractKeys<RoutingKey> that = (AbstractKeys<RoutingKey>) with;
+ return wrap(SortedArrays.linearUnion(keys, that.keys,
cachedRoutingKeys()), that);
}
@Override
- public Unseekables<RoutingKey, ?> with(Unseekables<RoutingKey, ?> with)
+ public Participants<RoutingKey> with(Participants<RoutingKey> with)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public Participants<RoutingKey> with(Participants<RoutingKey> with)
```
##########
accord-core/src/main/java/accord/primitives/KeyRoute.java:
##########
@@ -27,48 +29,98 @@
import static accord.utils.ArrayBuffers.cachedRoutingKeys;
-public abstract class KeyRoute extends
AbstractUnseekableKeys<Route<RoutingKey>> implements Route<RoutingKey>
+public abstract class KeyRoute extends AbstractUnseekableKeys implements
Route<RoutingKey>
{
public final RoutingKey homeKey;
+ public final boolean isParticipatingHomeKey;
- KeyRoute(@Nonnull RoutingKey homeKey, RoutingKey[] keys)
+ KeyRoute(@Nonnull RoutingKey homeKey, boolean isParticipatingHomeKey,
RoutingKey[] keys)
{
super(keys);
this.homeKey = Invariants.nonNull(homeKey);
+ this.isParticipatingHomeKey = isParticipatingHomeKey;
+ }
+
+ @Override
+ public boolean participatesIn(Ranges ranges)
+ {
+ if (isParticipatingHomeKey())
+ return intersects(ranges);
+
+ long ij = findNextIntersection(0, ranges, 0);
+ if (ij < 0)
+ return false;
+
+ int i = (int)ij;
+ if (!get(i).equals(homeKey))
+ return true;
+
+ int j = (int)(ij >>> 32);
+ return findNextIntersection(i + 1, ranges, j) >= 0;
}
@Override
- public Unseekables<RoutingKey, ?> toMaximalUnseekables()
+ public Unseekables<RoutingKey> with(Unseekables<RoutingKey> with)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public Unseekables<RoutingKey> with(Unseekables<RoutingKey> with)
```
##########
accord-core/src/main/java/accord/primitives/AbstractKeys.java:
##########
@@ -229,42 +233,61 @@ public final long foldl(IndexedFoldToLong<? super K>
fold, long param, long init
public final FullKeyRoute toRoute(RoutingKey homeKey)
{
if (isEmpty())
- return new FullKeyRoute(homeKey, new RoutingKey[] { homeKey });
+ return new FullKeyRoute(homeKey, false, new RoutingKey[] { homeKey
});
RoutingKey[] result = toRoutingKeysArray(homeKey);
int pos = Arrays.binarySearch(result, homeKey);
- return new FullKeyRoute(result[pos], result);
+ return new FullKeyRoute(result[pos], contains(homeKey), result);
}
protected RoutingKey[] toRoutingKeysArray(RoutingKey withKey)
Review Comment:
```suggestion
@SuppressWarnings("SuspiciousSystemArraycopy")
protected RoutingKey[] toRoutingKeysArray(RoutingKey withKey)
```
##########
accord-core/src/main/java/accord/primitives/Routables.java:
##########
@@ -48,21 +48,21 @@ enum Slice
boolean isEmpty();
boolean intersects(AbstractRanges<?> ranges);
- boolean intersects(AbstractKeys<?, ?> keys);
- default boolean intersects(Routables<?, ?> routables)
+ boolean intersects(AbstractKeys<?> keys);
+ default boolean intersects(Routables<?> routables)
{
switch (routables.domain())
{
default: throw new AssertionError();
- case Key: return intersects((AbstractKeys<?, ?>) routables);
+ case Key: return intersects((AbstractKeys<?>) routables);
case Range: return intersects((AbstractRanges<?>) routables);
}
}
boolean contains(RoutableKey key);
- boolean containsAll(Routables<?, ?> keysOrRanges);
+ boolean containsAll(Routables<?> keysOrRanges);
- U slice(Ranges ranges);
- Routables<K, ?> slice(Ranges ranges, Slice slice);
+ Routables slice(Ranges ranges);
Review Comment:
```suggestion
Routables<?> slice(Ranges ranges);
```
the `<?>` is to avoid a compiler warning... all subtypes override and define
a more specific type
##########
accord-core/src/main/java/accord/primitives/Route.java:
##########
@@ -22,9 +22,18 @@
import javax.annotation.Nullable;
-public interface Route<K extends Unseekable> extends Unseekables<K, Route<K>>
+public interface Route<K extends Unseekable> extends Unseekables<K>
{
+ enum Participation
Review Comment:
this is dead code
##########
accord-core/src/main/java/accord/primitives/KeyDeps.java:
##########
@@ -485,24 +502,12 @@ public List<TxnId> txnIds(Range range)
return txnIds(ids, 0, count);
}
- private List<TxnId> txnIds(int[] ids, int start, int size)
+ private SortedRelationList<TxnId> txnIds(int[] ids, int start, int end)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
private SortedRelationList<TxnId> txnIds(int[] ids, int start, int end)
```
##########
accord-core/src/main/java/accord/primitives/Route.java:
##########
@@ -22,9 +22,18 @@
import javax.annotation.Nullable;
-public interface Route<K extends Unseekable> extends Unseekables<K, Route<K>>
+public interface Route<K extends Unseekable> extends Unseekables<K>
{
+ enum Participation
+ {
+ PARTICIPANT,
+ HOME_KEY_ONLY
+ }
+
RoutingKey homeKey();
+ // true iff homeKey() is not involved in the transaction, only in its
coordination (i.e. !txn.keys().contains(homeKey())
Review Comment:
```suggestion
/**
* @return true iff {@link #homeKey()} is not involved in the
transaction, only in its coordination (i.e. {@code
!txn.keys().contains(homeKey()})
*/
```
##########
accord-core/src/main/java/accord/primitives/KeyDeps.java:
##########
@@ -428,13 +439,18 @@ public List<TxnId> txnIds(Key key)
if (keyIndex < 0)
return Collections.emptyList();
+ return txnIdsForKeyIndex(keyIndex);
+ }
+
+ public SortedRelationList<TxnId> txnIdsForKeyIndex(int keyIndex)
+ {
+ int[] keysToTxnIds = keysToTxnIds();
int start = startOffset(keyIndex);
int end = endOffset(keyIndex);
- int size = end - start;
- return txnIds(keysToTxnIds, start, size);
+ return txnIds(keysToTxnIds, start, end);
}
- public List<TxnId> txnIds(Range range)
+ public SortedRelationList<TxnId> txnIds(Range range)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public SortedRelationList<TxnId> txnIds(Range range)
```
This is needed due to `SortedRelationList.EMPTY;`... if you create a
`empty()` method you can push this suppress warning there and avoid 3 compiler
warnings
##########
accord-core/src/main/java/accord/primitives/RoutingKeys.java:
##########
@@ -69,6 +80,18 @@ public RoutingKeys with(RoutingKey with)
return wrap(toRoutingKeysArray(with));
}
+ public RoutingKeys without(RoutingKey without)
Review Comment:
not used within this patch, but also doesn't work, see comment below
##########
accord-core/src/main/java/accord/primitives/RoutingKeys.java:
##########
@@ -55,12 +55,23 @@ public static RoutingKeys ofSortedUnique(RoutingKey ...
keys)
}
@Override
- public Unseekables<RoutingKey, ?> with(Unseekables<RoutingKey, ?> with)
+ public RoutingKeys with(Unseekables<RoutingKey> with)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public RoutingKeys with(Unseekables<RoutingKey> with)
```
##########
accord-core/src/main/java/accord/primitives/Timestamp.java:
##########
@@ -277,6 +277,11 @@ public static <T extends Timestamp> T nonNullOrMax(T a, T
b)
return a == null ? b : b == null ? a : max(a, b);
}
+ public static <T extends Timestamp> T nonNullOrMin(T a, T b)
Review Comment:
`nonNull` doesn't feel like a correct name, as `nonNullOrMin(null, null)`
returns `null`... this does match `nonNullOrMax` so guess its at least
consistent with this class... but maybe `nullableMin`?
##########
accord-core/src/main/java/accord/primitives/RoutingKeys.java:
##########
@@ -69,6 +80,18 @@ public RoutingKeys with(RoutingKey with)
return wrap(toRoutingKeysArray(with));
}
+ public RoutingKeys without(RoutingKey without)
+ {
+ int index = indexOf(without);
+ if (index < 0)
+ return this;
+
+ RoutingKey[] keys = new RoutingKey[size() - 1];
+ System.arraycopy(keys, 0, keys, 0, index);
+ System.arraycopy(keys, index + 1, keys, index, size() - (1 + index));
Review Comment:
believe you mean `this.keys`, right now we are copying from an empty array
to the same empty array...
##########
accord-core/src/main/java/accord/topology/Topology.java:
##########
@@ -326,24 +291,19 @@ private <P1> int[] subsetFor(Unseekables<?, ?> select,
IndexedPredicate<P1> pred
return cachedInts.completeAndDiscard(newSubset, count);
}
- public <P1> void visitNodeForKeysOnceOrMore(Unseekables<?, ?> select,
OnUnknown onUnknown, Consumer<Id> nodes)
- {
- visitNodeForKeysOnceOrMore(select, onUnknown, (i1, i2) -> true, null,
nodes);
- }
-
- public <P1> void visitNodeForKeysOnceOrMore(Unseekables<?, ?> select,
OnUnknown onUnknown, IndexedPredicate<P1> predicate, P1 param, Consumer<Id>
nodes)
+ public <P1> void visitNodeForKeysOnceOrMore(Unseekables<?> select,
Consumer<Id> nodes)
Review Comment:
```suggestion
public void visitNodeForKeysOnceOrMore(Unseekables<?> select,
Consumer<Id> nodes)
```
##########
accord-core/src/main/java/accord/utils/SortedArrays.java:
##########
@@ -66,6 +66,11 @@ public int findNext(int i, Comparable<? super T> find)
return exponentialSearch(array, i, array.length, find);
}
+ public int find(Comparable<? super T> find)
Review Comment:
```suggestion
@Override
public int find(Comparable<? super T> find)
```
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -130,101 +148,121 @@ private boolean contains(int idx, K key)
if (idx < 0 || idx > size())
Review Comment:
GH won't let me comment on the method... `contains` is private and dead
code, we can remove
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -44,34 +45,39 @@ public class ReducingIntervalMap<K extends Comparable<?
super K>, V>
// for simplicity at construction, we permit this to be overridden by the
first insertion
final boolean inclusiveEnds;
- final K[] ends;
+ // starts is 1 longer than values, so that starts[0] == start of values[0]
+ final K[] starts;
final V[] values;
- public ReducingIntervalMap(V value)
+ public ReducingIntervalMap()
{
- this(false, value);
+ this(false);
}
- public ReducingIntervalMap(boolean inclusiveEnds, V value)
+ public ReducingIntervalMap(boolean inclusiveEnds)
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
public ReducingIntervalMap(boolean inclusiveEnds)
```
##########
accord-core/src/main/java/accord/utils/ReducingRangeMap.java:
##########
@@ -182,14 +191,15 @@ public static <V> ReducingRangeMap<V>
merge(ReducingRangeMap<V> historyLeft, Red
static class Builder<V> extends ReducingIntervalMap.Builder<RoutingKey, V,
ReducingRangeMap<V>>
{
- Builder(boolean inclusiveEnds, int capacity)
+ protected Builder(boolean inclusiveEnds, int capacity)
{
super(inclusiveEnds, capacity);
}
- ReducingRangeMap<V> buildInternal()
+ @Override
+ protected ReducingRangeMap<V> buildInternal()
Review Comment:
```suggestion
@SuppressWarnings("unchecked")
protected ReducingRangeMap<V> buildInternal()
```
##########
accord-core/src/main/java/accord/utils/Timestamped.java:
##########
@@ -35,14 +35,34 @@ public Timestamped(Timestamp timestamp, T data)
public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b)
{
- return a.timestamp.compareTo(b.timestamp) >= 0 ? a : b;
+ return a.timestamp.compareTo(b.timestamp) < 0 ? b : a;
}
- public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testEquality)
+ public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testPrefix, BiPredicate<T, T> testEquality)
{
int c = a.timestamp.compareTo(b.timestamp);
- if (c == 0) Invariants.checkArgument(testEquality.test(a.data,
b.data));
- return c >= 0 ? a : b;
+ if (c == 0)
+ {
+ Invariants.checkArgument(testEquality.test(a.data, b.data));
+ return a;
+ }
+ else if (c < 0)
+ {
+ Invariants.checkArgument(testPrefix.test(a.data, b.data));
+ return b;
+ }
+ else
+ {
+ Invariants.checkArgument(testPrefix.test(b.data, a.data));
+ return a;
+ }
+ }
+
+ public static <T> Timestamped<T> mergeEqual(Timestamped<T> a,
Timestamped<T> b, BiPredicate<T, T> testEquality)
+ {
+ int c = a.timestamp.compareTo(b.timestamp);
+ Invariants.checkState(c == 0 && testEquality.test(a.data, b.data));
Review Comment:
```suggestion
Invariants.checkState(c == 0 && testEquality.test(a.data, b.data),
"%s != %s", a, b);
```
##########
accord-core/src/main/java/accord/utils/Timestamped.java:
##########
@@ -35,14 +35,34 @@ public Timestamped(Timestamp timestamp, T data)
public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b)
{
- return a.timestamp.compareTo(b.timestamp) >= 0 ? a : b;
+ return a.timestamp.compareTo(b.timestamp) < 0 ? b : a;
}
- public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testEquality)
+ public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testPrefix, BiPredicate<T, T> testEquality)
{
int c = a.timestamp.compareTo(b.timestamp);
- if (c == 0) Invariants.checkArgument(testEquality.test(a.data,
b.data));
- return c >= 0 ? a : b;
+ if (c == 0)
+ {
+ Invariants.checkArgument(testEquality.test(a.data, b.data));
+ return a;
+ }
+ else if (c < 0)
+ {
+ Invariants.checkArgument(testPrefix.test(a.data, b.data));
Review Comment:
```suggestion
Invariants.checkArgument(testPrefix.test(a.data, b.data), "%s >=
%s", a, b);
```
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils;
+
+import java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
Review Comment:
```
BitSet set = ...
BitSet copy = BitSet.valueOf(set.toLongArray())
```
##########
accord-core/src/main/java/accord/utils/Timestamped.java:
##########
@@ -35,14 +35,34 @@ public Timestamped(Timestamp timestamp, T data)
public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b)
{
- return a.timestamp.compareTo(b.timestamp) >= 0 ? a : b;
+ return a.timestamp.compareTo(b.timestamp) < 0 ? b : a;
}
- public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testEquality)
+ public static <T> Timestamped<T> merge(Timestamped<T> a, Timestamped<T> b,
BiPredicate<T, T> testPrefix, BiPredicate<T, T> testEquality)
{
int c = a.timestamp.compareTo(b.timestamp);
- if (c == 0) Invariants.checkArgument(testEquality.test(a.data,
b.data));
- return c >= 0 ? a : b;
+ if (c == 0)
+ {
+ Invariants.checkArgument(testEquality.test(a.data, b.data));
+ return a;
+ }
+ else if (c < 0)
+ {
+ Invariants.checkArgument(testPrefix.test(a.data, b.data));
+ return b;
+ }
+ else
+ {
+ Invariants.checkArgument(testPrefix.test(b.data, a.data));
Review Comment:
```suggestion
Invariants.checkArgument(testPrefix.test(b.data, a.data), "%s <=
%s", a, b);
```
##########
accord-core/src/main/java/accord/utils/ReducingIntervalMap.java:
##########
@@ -93,35 +99,47 @@ public boolean equals(Object o)
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ReducingIntervalMap that = (ReducingIntervalMap) o;
- return Arrays.equals(ends, that.ends) && Arrays.equals(values,
that.values);
+ return Arrays.equals(starts, that.starts) && Arrays.equals(values,
that.values);
}
public int hashCode()
{
return Arrays.hashCode(values);
Review Comment:
> so it would be a more serious bug if we're ever comparing things where
they don't match
In C* we are consistent, but in accord its a library, so a different
implementation might mix, so worth detecting
> Also, hashCode() does not need to include everything
agree, this would only ever impact stuff like hash map/set but wouldn't
impact correctness
##########
accord-core/src/main/java/accord/utils/SimpleBitSet.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils;
+
+import java.util.Arrays;
+
+import static java.lang.Long.highestOneBit;
+import static java.lang.Long.lowestOneBit;
+import static java.lang.Long.numberOfTrailingZeros;
+
+public class SimpleBitSet
+{
+ public static class SerializationSupport
+ {
+ public static long[] getArray(SimpleBitSet bs)
+ {
+ return bs.bits;
+ }
+
+ public static SimpleBitSet construct(long[] bits)
+ {
+ return new SimpleBitSet(bits);
+ }
+ }
+
+ final long[] bits;
+ int count;
+
+ public SimpleBitSet(int size)
+ {
+ bits = new long[(size + 63)/64];
+ }
+
+ public SimpleBitSet(int size, boolean set)
+ {
+ this(size);
+ if (set)
+ {
+ Arrays.fill(bits, 0, size / 64, -1L);
+ if ((size & 63) != 0)
+ bits[indexOf(size - 1)] = -1L >>> (64 - (size & 63));
+ count = size;
+ }
+ }
+
+ public SimpleBitSet(SimpleBitSet copy)
+ {
+ bits = copy.bits.clone();
+ count = copy.count;
+ }
+
+ SimpleBitSet(long[] bits)
+ {
+ this.bits = bits;
+ for (long v : bits)
+ count += Long.bitCount(v);
+ }
+
+ public boolean set(int i)
+ {
+ int index = indexOf(i);
+ long bit = bit(i);
+ if (0 != (bits[index] & bit))
+ return false;
+ bits[index] |= bit;
+ ++count;
+ return true;
+ }
+
+ public void setRange(int from, int to)
+ {
+ if (to <= from)
+ {
+ Invariants.checkArgument(to >= from, "to < from (%s < %s)", to,
from);
Review Comment:
> any >= would be a bug
you point out that `==` is a no-op and supported case, so `>=` being a bug
isn't true, its only true in the context of the if check above, which makes you
have to undo the logic in your head (making it more complex)...
The following is simpler and very clear IMO
```
Invariants.checkArgument(from <= to, "to < from (%s < %s)", to, from);
```
> We don’t currently perform the check unless we’ve already tested <, so you
can pre-apply this and reduce the test to =
2 checks when we can perform in 1?
> The modified check is also prone to being disarmed by refactoring. So I
think it is strictly worse, but minimally so.
I don't follow this argument... we need a if check that adds more
complication to this check become a refactor in the future might change things?
##########
accord-core/src/main/java/accord/topology/Topology.java:
##########
@@ -236,16 +226,14 @@ private Topology forSubset(int[] newSubset,
Collection<Id> nodes)
return new Topology(epoch, shards, ranges, nodeLookup, rangeSubset,
newSubset);
}
- public enum OnUnknown { REJECT, IGNORE }
-
- private <P1> int[] subsetFor(Unseekables<?, ?> select,
IndexedPredicate<P1> predicate, P1 param, OnUnknown onUnknown)
+ private int[] subsetFor(Unseekables<?> select)
Review Comment:
TODO for me: double check `TopologyManager` handles this, was added due to
that class
--
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]
