import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableRangeSet;
import com.google.common.primitives.UnsignedLong;
+import java.util.NavigableSet;
import java.util.TreeSet;
import org.eclipse.jdt.annotation.NonNull;
import org.opendaylight.yangtools.concepts.Mutable;
return new MutableUnsignedLongSet(new TreeSet<>());
}
+ public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
+ final var ret = MutableUnsignedLongSet.of();
+ for (long longBits : ulongs) {
+ ret.add(longBits);
+ }
+ return ret;
+ }
+
@Override
public ImmutableUnsignedLongSet immutableCopy() {
return ImmutableUnsignedLongSet.copyOf(this);
}
public void add(final long longBits) {
+ addOne(trustedRanges(), Entry.of(longBits), longBits);
+ }
+
+ public void addAll(final UnsignedLongSet other) {
final var ranges = trustedRanges();
- final var range = Entry.of(longBits);
+ for (var range : other.trustedRanges()) {
+ if (range.lowerBits == range.upperBits) {
+ addOne(ranges, range, range.lowerBits);
+ } else {
+ addRange(ranges, range);
+ }
+ }
+ }
+ private static void addOne(final NavigableSet<Entry> ranges, final Entry range, final long longBits) {
// We need Iterator.remove() to perform efficient merge below
final var headIt = ranges.headSet(range, true).descendingIterator();
if (headIt.hasNext()) {
ranges.add(range);
}
+ private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
+ // If the start of the range is already covered by an existing range, we can expand that
+ final var lower = ranges.floor(range);
+ if (lower != null && Long.compareUnsigned(lower.upperBits + 1, range.lowerBits) >= 0) {
+ expandLower(ranges, lower, range.upperBits);
+ return;
+ }
+
+ // If the end of the range is already covered by an existing range, we can expand that
+ final var upper = ranges.floor(Entry.of(range.upperBits));
+ if (upper != null && Long.compareUnsigned(upper.lowerBits - 1, range.upperBits) <= 0) {
+ // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
+ // case upper needs to become the first entry
+ if (lower == null) {
+ ranges.headSet(upper, false).clear();
+ }
+
+ expandUpper(ranges, upper, range.lowerBits, range.upperBits);
+ return;
+ }
+
+ // No luck, insert
+ ranges.add(range);
+ }
+
+ private static void expandLower(final NavigableSet<Entry> ranges, final Entry entry, final long upperBits) {
+ if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+ // Already contained, this is a no-op
+ return;
+ }
+
+ // Acquire any ranges after floor and clean them up
+ final var tailIt = ranges.tailSet(entry, false).iterator();
+ final long nextLower = upperBits + 1;
+ while (tailIt.hasNext()) {
+ final var tail = tailIt.next();
+ if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
+ // There is gap, nothing more to cleanup
+ break;
+ }
+
+ // We can merge this entry into floor...
+ tailIt.remove();
+
+ if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
+ // ... but we need to expand floor accordingly and after that we are done
+ entry.upperBits = tail.upperBits;
+ return;
+ }
+ }
+
+ // Expand floor to include this range and we are done
+ entry.upperBits = upperBits;
+ }
+
+ private static void expandUpper(final NavigableSet<Entry> ranges, final Entry entry, final long lowerBits,
+ final long upperBits) {
+ if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+ // Upper end is already covered
+ entry.lowerBits = lowerBits;
+ return;
+ }
+
+ // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
+ long newUpper = upperBits;
+ final var tailIt = ranges.tailSet(entry, false).iterator();
+ if (tailIt.hasNext()) {
+ final var tail = tailIt.next();
+ if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
+ tailIt.remove();
+ newUpper = tail.upperBits;
+ }
+ }
+
+ entry.lowerBits = lowerBits;
+ entry.upperBits = newUpper;
+ }
+
public ImmutableRangeSet<UnsignedLong> toRangeSet() {
return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
}
set.add(0);
assertTrue(set.contains(0));
- assertEquals("MutableUnsignedLongSet{span=[0..0], size=1}", set.toString());
+ assertRanges("[[0..0]]", set);
set.add(1);
assertTrue(set.contains(1));
- assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
+ assertRanges("[[0..1]]", set);
set.add(1);
- assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
+ assertRanges("[[0..1]]", set);
set.add(4);
- assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
+ assertRanges("[[0..1], [4..4]]", set);
set.add(3);
- assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
+ assertRanges("[[0..1], [3..4]]", set);
set.add(2);
- assertEquals("MutableUnsignedLongSet{span=[0..4], size=1}", set.toString());
+ assertRanges("[[0..4]]", set);
assertTrue(set.contains(2));
assertTrue(set.contains(3));
assertTrue(set.contains(4));
+
+ set.add(8);
+ assertRanges("[[0..4], [8..8]]", set);
+ set.add(6);
+ assertRanges("[[0..4], [6..6], [8..8]]", set);
+ set.add(7);
+ assertRanges("[[0..4], [6..8]]", set);
+ set.add(5);
+ assertRanges("[[0..8]]", set);
+
+ set.add(11);
+ assertRanges("[[0..8], [11..11]]", set);
+ set.add(9);
+ assertRanges("[[0..9], [11..11]]", set);
}
@Test
public void testSerialization() throws IOException {
- final var tmp = MutableUnsignedLongSet.of();
- tmp.add(0);
- tmp.add(1);
- tmp.add(4);
- tmp.add(3);
- final var set = tmp.immutableCopy();
+ final var set = MutableUnsignedLongSet.of(0, 1, 4, 3).immutableCopy();
final var bos = new ByteArrayOutputStream();
try (var out = new DataOutputStream(bos)) {
@Test
public void testToRangeSet() {
- final var set = MutableUnsignedLongSet.of();
- set.add(0);
- set.add(1);
- set.add(4);
- set.add(3);
+ final var set = MutableUnsignedLongSet.of(0, 1, 4, 3);
assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
}
() -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1));
assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
}
+
+ @Test
+ public void testAddRange() {
+ var set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(1, 2));
+ assertRanges("[[1..2], [5..6], [9..10], [13..14]]", set);
+ set.addAll(MutableUnsignedLongSet.of(3, 4));
+ assertRanges("[[1..6], [9..10], [13..14]]", set);
+ set.addAll(MutableUnsignedLongSet.of(4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
+ assertRanges("[[1..15]]", set);
+
+ set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(2, 3, 4, 5));
+ assertRanges("[[1..6], [9..10], [13..14]]", set);
+
+ set.addAll(MutableUnsignedLongSet.of(6, 7));
+ assertRanges("[[1..7], [9..10], [13..14]]", set);
+
+ set.addAll(MutableUnsignedLongSet.of(8));
+ assertRanges("[[1..10], [13..14]]", set);
+
+ set = MutableUnsignedLongSet.of();
+ set.addAll(MutableUnsignedLongSet.of(1, 2));
+ assertRanges("[[1..2]]", set);
+
+ set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(4, 5));
+ assertRanges("[[1..2], [4..6], [9..10], [13..14]]", set);
+
+ set.addAll(MutableUnsignedLongSet.of(12, 13, 14, 15));
+ assertRanges("[[1..2], [4..6], [9..10], [12..15]]", set);
+
+ set.addAll(MutableUnsignedLongSet.of(8, 9, 10, 11));
+ assertRanges("[[1..2], [4..6], [8..15]]", set);
+
+ set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
+ assertRanges("[[0..16]]", set);
+
+ set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3));
+ assertRanges("[[0..3], [5..6], [9..10], [13..14]]", set);
+
+ set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8));
+ assertRanges("[[0..10], [13..14]]", set);
+
+ set = sparseSet();
+ set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
+ assertRanges("[[0..10], [13..14]]", set);
+ }
+
+ private static MutableUnsignedLongSet sparseSet() {
+ final var ret = MutableUnsignedLongSet.of(1, 2, 5, 6, 9, 10, 13, 14);
+ assertRanges("[[1..2], [5..6], [9..10], [13..14]]", ret);
+ return ret;
+ }
+
+ private static void assertRanges(final String expected, final UnsignedLongSet set) {
+ assertEquals(expected, set.ranges().toString());
+ }
}
Code Review / controller.git / commitdiff