Merge pull request #21773 from vespa-engine/jonmv/multi-range-item-2

Jonmv/multi range item 2

4 files changed, 785 insertions, 1 deletions

diff --git a/container-search/abi-spec.json b/container-search/abi-spec.json
index 22be0d32f69..b70a88d09a0 100644
--- a/container-search/abi-spec.json
+++ b/container-search/abi-spec.json
@@ -899,6 +899,57 @@
     ],
     "fields" : [ ]
   },
+  "com.yahoo.prelude.query.MultiRangeItem$Limit": {
+    "superClass": "java.lang.Enum",
+    "interfaces": [],
+    "attributes": [
+      "public",
+      "final",
+      "enum"
+    ],
+    "methods": [
+      "public static com.yahoo.prelude.query.MultiRangeItem$Limit[] values()",
+      "public static com.yahoo.prelude.query.MultiRangeItem$Limit valueOf(java.lang.String)"
+    ],
+    "fields": [
+      "public static final enum com.yahoo.prelude.query.MultiRangeItem$Limit INCLUSIVE",
+      "public static final enum com.yahoo.prelude.query.MultiRangeItem$Limit EXCLUSIVE"
+    ]
+  },
+  "com.yahoo.prelude.query.MultiRangeItem$NumberType" : {
+    "superClass" : "java.lang.Object",
+    "interfaces" : [ ],
+    "attributes" : [
+      "public"
+    ],
+    "methods" : [ ],
+    "fields" : [
+      "public static final com.yahoo.prelude.query.MultiRangeItem$NumberType INTEGER",
+      "public static final com.yahoo.prelude.query.MultiRangeItem$NumberType LONG",
+      "public static final com.yahoo.prelude.query.MultiRangeItem$NumberType DOUBLE"
+    ]
+  },
+  "com.yahoo.prelude.query.MultiRangeItem" : {
+    "superClass" : "com.yahoo.prelude.query.MultiTermItem",
+    "interfaces" : [ ],
+    "attributes" : [
+      "public"
+    ],
+    "methods" : [
+      "public static com.yahoo.prelude.query.MultiRangeItem overRanges(com.yahoo.prelude.query.MultiRangeItem$NumberType, java.lang.String, com.yahoo.prelude.query.MultiRangeItem$Limit, java.lang.String, com.yahoo.prelude.query.MultiRangeItem$Limit)",
+      "public static com.yahoo.prelude.query.MultiRangeItem overPoints(com.yahoo.prelude.query.MultiRangeItem$NumberType, java.lang.String, com.yahoo.prelude.query.MultiRangeItem$Limit, com.yahoo.prelude.query.MultiRangeItem$Limit)",
+      "public com.yahoo.prelude.query.MultiRangeItem addPoint(java.lang.Number)",
+      "public com.yahoo.prelude.query.MultiRangeItem addRange(java.lang.Number, java.lang.Number)",
+      "public void setIndexName(java.lang.String)",
+      "protected void appendBodyString(java.lang.StringBuilder)",
+      "public void disclose(com.yahoo.prelude.query.textualrepresentation.Discloser)",
+      "public com.yahoo.prelude.query.Item clone()",
+      "public boolean equals(java.lang.Object)",
+      "public int hashCode()",
+      "public bridge synthetic java.lang.Object clone()"
+    ],
+    "fields" : [ ]
+  },
   "com.yahoo.prelude.query.NearItem" : {
     "superClass" : "com.yahoo.prelude.query.CompositeItem",
     "interfaces" : [ ],
@@ -8674,4 +8725,4 @@
     ],
     "fields" : [ ]
   }
-}
\ No newline at end of file
+}
diff --git a/container-search/src/main/java/com/yahoo/prelude/query/MultiRangeItem.java b/container-search/src/main/java/com/yahoo/prelude/query/MultiRangeItem.java
new file mode 100644
index 00000000000..7ba7a13936f
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/prelude/query/MultiRangeItem.java
@@ -0,0 +1,351 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.prelude.query;
+
+import com.yahoo.compress.IntegerCompressor;
+import com.yahoo.prelude.query.textualrepresentation.Discloser;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Objects;
+import java.util.function.BiConsumer;
+import java.util.function.Function;
+
+import static java.util.Objects.requireNonNull;
+
+/**
+ * A term which contains a set of numerical ranges; a match with any of these indicates a match.
+ * <p>
+ * This is a stricter version of an {@link OrItem} containing multiple {@link RangeItem}s, where all
+ * ranges must be specified against the same field, or pair of fields, and where all the left boundaries,
+ * and all the right boundaries, share whether they are {@link Limit#INCLUSIVE} or {@link Limit#EXCLUSIVE}.
+ * Furthermore, all overlapping ranges are joined, such that the set of ranges this represents is
+ * guaranteed to be non-overlapping, and thus, sorted order of start and end boundaries is the same,
+ * which allows efficient filtering of document points or ranges by whether they are included in any of
+ * the ranges contained in this term. Note that touching ranges, like [3, 5) and [5, 7), will be joined
+ * unless this item is declared to have exclusive boundaries at both ends, or if one of the items is contained
+ * within the other, e.g., (3, 5) and (5, 5) (see below for explanation of weirdness).
+ * <p>
+ * In the absence of a range type in the schema definition, all ranges (and points) contained in documents
+ * are taken to be inclusive at both ends. However, intersection of range starts from documents and range
+ * ends from the query is inclusive, i.e., matching on equality, iff. both boundaries are inclusive, and
+ * likewise for intersection between range starts from query and range ends from documents. It is therefore
+ * possible to achieve any matching by choosing inclusiveness for the query ranges appropriately.
+ * For the case where document ranges are to be treated as exclusive, and the query has single points, this
+ * becomes weird, since the ranges [1, 1), (1, 1] and (1, 1) are all logically empty, but this still works :)
+ * <p>
+ * Unless ranges are added in ascending start order, the implementation lazily sorts and merges ranges,
+ * when a representation of the item is required. This is typically when the query is serialized and sent
+ * to the backend, or when trace information is written, or {@link #toString()} is called on the item.
+ * Adding ranges in ascending order is much faster than not; ascending order here has the rather lax
+ * requirement that each added interval is not completely before the current last interval.
+ *
+ * @author jonmv
+ */
+public class MultiRangeItem<Type extends Number> extends MultiTermItem {
+
+    public enum Limit {
+        /** Points match the boundaries of ranges which are inclusive. */
+        INCLUSIVE,
+        /** Points do not match the boundaries of ranges which are exclusive. */
+        EXCLUSIVE;
+    }
+
+    /** Type of numbers stored used to describe the ranges stored in a {@link MultiRangeItem}. */
+    public static class NumberType<Type extends Number> {
+
+        public static final NumberType<Integer> INTEGER = new NumberType<>((a, b) -> a < b ? -1 : a > b ? 1 : 0, ranges ->
+                switch (IntegerCompressor.compressionMode(ranges.get(0).start, ranges.get(ranges.size() - 1).end)) {
+                    case NONE -> NumberEncoder.UNIFORM_INTEGER;
+                    case COMPRESSED -> NumberEncoder.COMPRESSED_INTEGER;
+                    case COMPRESSED_POSITIVE -> NumberEncoder.COMPRESSED_POSITIVE_INTEGER;
+                });
+        public static final NumberType<Long>    LONG    = new NumberType<>((a, b) -> a < b ? -1 : a > b ? 1 : 0, __ -> NumberEncoder.UNIFORM_LONG);
+        public static final NumberType<Double>  DOUBLE  = new NumberType<>((a, b) -> a < b ? -1 : a > b ? 1 : 0, __ -> NumberEncoder.UNIFORM_DOUBLE);
+
+        private final Comparator<Type> comparator;
+        private final Function<List<Range<Type>>, NumberEncoder<Type>> encoder;
+
+        private NumberType(Comparator<Type> comparator, Function<List<Range<Type>>, NumberEncoder<Type>> encoder) {
+            this.comparator = comparator;
+            this.encoder = encoder;
+        }
+
+        NumberEncoder<Type> encoderFor(List<Range<Type>> ranges) {
+            return encoder.apply(ranges);
+        }
+
+    }
+
+    static class Range<Type extends Number> {
+
+        final Type start;
+        final Type end;
+
+        Range(Type start, Type end) {
+            this.start = start;
+            this.end = end;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Range<?> range = (Range<?>) o;
+            return start.equals(range.start) && end.equals(range.end);
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(start, end);
+        }
+
+        @Override
+        public String toString() {
+            return "(" + start + ", " + end + ")";
+        }
+
+    }
+
+    private static class NumberEncoder<Type extends Number> {
+
+        static NumberEncoder<Integer> UNIFORM_INTEGER             = new NumberEncoder<>(0, ByteBuffer::putInt);
+        static NumberEncoder<Long>    UNIFORM_LONG                = new NumberEncoder<>(1, ByteBuffer::putLong);
+        static NumberEncoder<Double>  UNIFORM_DOUBLE              = new NumberEncoder<>(2, ByteBuffer::putDouble);
+        static NumberEncoder<Integer> COMPRESSED_INTEGER          = new NumberEncoder<>(3, (b, n) -> IntegerCompressor.putCompressedNumber(n, b));
+        static NumberEncoder<Integer> COMPRESSED_POSITIVE_INTEGER = new NumberEncoder<>(4, (b, n) -> IntegerCompressor.putCompressedPositiveNumber(n, b));
+
+        final byte id; // 5 bits
+        final BiConsumer<ByteBuffer, Type> serializer;
+
+        NumberEncoder(int id, BiConsumer<ByteBuffer, Type> serializer) {
+            this.id = (byte) id;
+            this.serializer = serializer;
+        }
+
+    }
+
+    private final NumberType<Type> type;
+    private final String startIndex;
+    private final String endIndex;
+    private final boolean startInclusive;
+    private final boolean endInclusive;
+    private List<Range<Type>> ranges = new ArrayList<>();
+    private boolean sorted = true;
+    private NumberEncoder<Type> encoder;
+
+    /** A multi range item with ranges to intersect with ranges given by the pair of index names. */
+    private MultiRangeItem(NumberType<Type> type, String startIndex, Limit startInclusive, String endIndex, Limit endInclusive) {
+        if (startIndex.isBlank()) throw new IllegalArgumentException("start index name must be non-blank");
+        if (endIndex.isBlank()) throw new IllegalArgumentException("end index name must be non-blank");
+        this.type = requireNonNull(type);
+        this.startIndex = startIndex;
+        this.endIndex = endIndex;
+        this.startInclusive = startInclusive == requireNonNull(Limit.INCLUSIVE);
+        this.endInclusive = endInclusive == requireNonNull(Limit.INCLUSIVE);
+    }
+
+    /** A multi range item to intersect with the ranges defined by the two given index names. */
+    public static <Type extends Number> MultiRangeItem<Type> overRanges(NumberType<Type> type,
+                                                                        String startIndex, Limit startInclusive,
+                                                                        String endIndex, Limit endInclusive) {
+        return new MultiRangeItem<>(type, startIndex, startInclusive, endIndex, endInclusive);
+    }
+
+    /** A multi range item to contain the points defined by the single given index name. */
+    public static <Type extends Number> MultiRangeItem<Type> overPoints(NumberType<Type> type, String index,
+                                                                        Limit startInclusive, Limit endInclusive) {
+        return overRanges(type, index, startInclusive, index, endInclusive);
+    }
+
+    /** Adds the given point to this item. More efficient when each added point is not completely before the current last one. */
+    public MultiRangeItem<Type> addPoint(Type point) {
+        return addRange(point, point);
+    }
+
+    /** Adds the given range to this item. More efficient when each added range is not completely before the current last one. */
+    public MultiRangeItem<Type> addRange(Type start, Type end) {
+        if (Double.isNaN(start.doubleValue()))
+            throw new IllegalArgumentException("range start cannot be NaN");
+        if (Double.isNaN(end.doubleValue()))
+            throw new IllegalArgumentException("range end cannot be NaN");
+        if (type.comparator.compare(start, end) > 0)
+            throw new IllegalArgumentException("ranges must satisfy start <= end, but got " + start + " > " + end);
+
+        Range<Type> range = new Range<>(start, end);
+        // If the list of ranges is still sorted, we try to keep it sorted.
+        if (sorted && ! ranges.isEmpty()) {
+            // If the new range is not completely before the current last range, we can prune, and keep a sorted list.
+            Range<Type> last = ranges.get(ranges.size() - 1);
+            sorted = overlap(range, last);
+            if (sorted) {
+                // Pop all ranges that overlap with the new range ...
+                Range<Type> popped = range;
+                for (int i = ranges.size(); i-- > 0; )
+                    if (overlap(ranges.get(i), range))
+                        popped = ranges.remove(i);
+                    else
+                        break;
+                // ... then add a new range, possibly with start and end from the popped and last ranges.
+                ranges.add(popped == range ? range : new Range<>(min(popped.start, range.start), max(last.end, range.end)));
+                return this;
+            }
+        }
+        ranges.add(range);
+        return this;
+    }
+
+    /**
+     * Assumption: first.start <= second.start
+     * Then there is overlap if
+     * first.end  > second.start
+     * first.end == second.start AND either of
+     *   ranges are inclusive at either end, OR
+     *   either range is a (logically empty) point (a, a), since this dominated by (or equal to) the other range.
+     */
+    private boolean overlap(Range<Type> first, Range<Type> second) {
+        int comparison = type.comparator.compare(first.end, second.start);
+        return   comparison  > 0
+              || comparison == 0 && (startInclusive || endInclusive || first.start.equals(first.end) || second.start.equals(second.end));
+    }
+
+    private Type min(Type a, Type b) {
+        return type.comparator.compare(a, b) <= 0 ? a : b;
+    }
+
+    private Type max(Type a, Type b) {
+        return type.comparator.compare(a, b) >= 0 ? a : b;
+    }
+
+    List<Range<Type>> sortedRanges() {
+        if (sorted)
+            return ranges;
+
+        ranges.sort((r1, r2) -> type.comparator.compare(r1.start, r2.start));
+
+        List<Range<Type>> pruned = new ArrayList<>();
+        Range<Type> start = ranges.get(0), end = start;
+        for (int i = 1; i < ranges.size(); i++) {
+            Range<Type> range = ranges.get(i);
+            if (overlap(end, range)) {
+                end = type.comparator.compare(end.end, range.end) < 0 ? range : end;
+            }
+            else {
+                pruned.add(start == end ? start : new Range<>(start.start, end.end));
+                start = end = range;
+            }
+        }
+        pruned.add(start == end ? start : new Range<>(start.start, end.end));
+
+        sorted = true;
+        return ranges = pruned;
+    }
+
+    @Override
+    public void setIndexName(String index) {
+        throw new UnsupportedOperationException("index cannot be changed for " + MultiRangeItem.class.getSimpleName());
+    }
+
+    @Override
+    OperatorType operatorType() {
+        return OperatorType.OR;
+    }
+
+    @Override
+    TermType termType() {
+        return TermType.RANGES;
+    }
+
+    @Override
+    int terms() {
+        return sortedRanges().size();
+    }
+
+    @Override
+    void encodeBlueprint(ByteBuffer buffer) {
+        boolean sameIndex = startIndex.equals(endIndex);
+        byte metadata = 0;
+        if (sameIndex)      metadata |= 0b00000001;
+        if (startInclusive) metadata |= 0b00000010;
+        if (endInclusive)   metadata |= 0b00000100;
+
+        encoder = type.encoderFor(sortedRanges());
+        metadata |= encoder.id << 3;
+
+        buffer.put(metadata);
+        putString(startIndex, buffer);
+        if ( ! sameIndex) putString(endIndex, buffer);
+    }
+
+    @Override
+    void encodeTerms(ByteBuffer buffer) {
+        for (Range<Type> range : sortedRanges()) {
+            encoder.serializer.accept(buffer, range.start);
+            encoder.serializer.accept(buffer, range.end);
+        }
+    }
+
+    @Override
+    protected void appendBodyString(StringBuilder buffer) {
+        asCompositeItem().appendBodyString(buffer);
+    }
+
+    @Override
+    public void disclose(Discloser discloser) {
+        asCompositeItem().disclose(discloser);
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public Item clone() {
+        MultiRangeItem<Type> clone = (MultiRangeItem<Type>) super.clone();
+        clone.ranges = new ArrayList<>(ranges);
+        return clone;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        if ( ! super.equals(o)) return false;
+        MultiRangeItem<?> that = (MultiRangeItem<?>) o;
+        return    type == that.type
+               && startInclusive == that.startInclusive
+               && endInclusive == that.endInclusive
+               && startIndex.equals(that.startIndex)
+               && endIndex.equals(that.endIndex)
+               && sortedRanges().equals(that.sortedRanges());
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(super.hashCode(), type, startIndex, endIndex, startInclusive, endInclusive, sortedRanges());
+    }
+
+    @Override
+    Item asCompositeItem() {
+        OrItem root = new OrItem();
+        if (startIndex.equals(endIndex)) {
+            for (Range<Type> range : sortedRanges()) {
+                root.addItem(new IntItem(new com.yahoo.prelude.query.Limit(range.start, startInclusive),
+                                         new com.yahoo.prelude.query.Limit(range.end, endInclusive),
+                                         startIndex));
+            }
+        }
+        else {
+            for (Range<Type> range : sortedRanges()) {
+                AndItem pair = new AndItem();
+                pair.addItem(new IntItem(new com.yahoo.prelude.query.Limit(range.start, startInclusive),
+                                         com.yahoo.prelude.query.Limit.POSITIVE_INFINITY,
+                                         startIndex));
+                pair.addItem(new IntItem(com.yahoo.prelude.query.Limit.NEGATIVE_INFINITY,
+                                         new com.yahoo.prelude.query.Limit(range.end, endInclusive),
+                                         endIndex));
+                root.addItem(pair);
+            }
+        }
+        return root;
+    }
+
+}
diff --git a/container-search/src/main/java/com/yahoo/prelude/query/MultiTermItem.java b/container-search/src/main/java/com/yahoo/prelude/query/MultiTermItem.java
new file mode 100644
index 00000000000..a7ca62d153c
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/prelude/query/MultiTermItem.java
@@ -0,0 +1,84 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.prelude.query;
+
+import java.nio.ByteBuffer;
+
+/**
+ * A term which wraps a set of similar simple terms, all joined with {@code AND} or {@code OR}.
+ * <p>
+ * This class exists to encompass similarities in the serialization of such multi-term constructs.
+ *
+ * @author jonmv
+ */
+abstract class MultiTermItem extends SimpleTaggableItem {
+
+    enum OperatorType {
+
+        AND(0),
+        OR(1);
+
+        private final byte code;
+
+        OperatorType(int code) { this.code = (byte) code; }
+
+    }
+
+    enum TermType {
+
+        RANGES(0);
+
+        private final byte code;
+
+        TermType(int code) { this.code = (byte) code; }
+
+    }
+
+    /** The operator used to join all wrapped terms. */
+    abstract OperatorType operatorType();
+
+    /** The term type of the wrapped terms. */
+    abstract TermType termType();
+
+    /** The number of wrapped terms. */
+    abstract int terms();
+
+    /** Encode term type and common properties to the buffer. */
+    abstract void encodeBlueprint(ByteBuffer buffer);
+
+    /** Encode all wrapped terms to the buffer. */
+    abstract void encodeTerms(ByteBuffer buffer);
+
+    abstract Item asCompositeItem();
+
+    @Override
+    public final ItemType getItemType() {
+        return ItemType.MULTI_TERM;
+    }
+
+    @Override
+    public final String getName() {
+        return getItemType().name();
+    }
+
+    @Override
+    public final int encode(ByteBuffer buffer) {
+        // TODO: Remove once backend support deserialisation of this type.
+        if (getClass() == MultiRangeItem.class) return asCompositeItem().encode(buffer);
+
+        super.encodeThis(buffer);
+        byte metadata = 0;
+        metadata |= (operatorType().code << 5) & 0b11100000;
+        metadata |= (    termType().code     ) & 0b00011111;
+        buffer.put(metadata);
+        buffer.putInt(terms());
+        encodeBlueprint(buffer);
+        encodeTerms(buffer);
+        return 1;
+    }
+
+    @Override
+    public final int getTermCount() {
+        return 1;
+    }
+
+}
diff --git a/container-search/src/test/java/com/yahoo/prelude/query/MultiRangeItemTestCase.java b/container-search/src/test/java/com/yahoo/prelude/query/MultiRangeItemTestCase.java
new file mode 100644
index 00000000000..f71c30af00b
--- /dev/null
+++ b/container-search/src/test/java/com/yahoo/prelude/query/MultiRangeItemTestCase.java
@@ -0,0 +1,298 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.prelude.query;
+
+import com.yahoo.prelude.query.MultiRangeItem.NumberType;
+import com.yahoo.prelude.query.MultiRangeItem.Range;
+import org.junit.jupiter.api.Disabled;
+import org.junit.jupiter.api.Test;
+
+import java.nio.ByteBuffer;
+import java.util.List;
+
+import static com.yahoo.compress.IntegerCompressor.putCompressedNumber;
+import static com.yahoo.prelude.query.MultiRangeItem.Limit.EXCLUSIVE;
+import static com.yahoo.prelude.query.MultiRangeItem.Limit.INCLUSIVE;
+import static java.lang.Double.NEGATIVE_INFINITY;
+import static java.lang.Double.NaN;
+import static java.lang.Double.POSITIVE_INFINITY;
+import static java.nio.charset.StandardCharsets.UTF_8;
+import static java.util.Comparator.comparingInt;
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.fail;
+
+/**
+ * @author jonmv
+ */
+public class MultiRangeItemTestCase {
+
+    // We'll add ranges (0, 0), (0, 2), (2, 2), (3, 4), (5, 8), (6, 6), (7, 9), (9, 9), (1, 8), in that order, and in "random" order.
+    final List<Range<Integer>> ranges = List.of(new Range<>(1, 8), // Make it "unordered", so sorting is delayed.
+                                       new Range<>(0, 0),
+                                       new Range<>(0, 2),
+                                       new Range<>(2, 2),
+                                       new Range<>(3, 4),
+                                       new Range<>(5, 8),
+                                       new Range<>(6, 6),
+                                       new Range<>(9, 9),
+                                       new Range<>(7, 9));
+
+    @Test
+    public void testNanIsDisallowed() {
+        try {
+            MultiRangeItem.overPoints(NumberType.DOUBLE, "i", INCLUSIVE, EXCLUSIVE).addPoint(NaN);
+            fail("NaN should be disallowed");
+        }
+        catch (IllegalArgumentException e) {
+            assertEquals("range start cannot be NaN", e.getMessage());
+        }
+    }
+
+    @Test
+    public void testSpecialValuesWithClosedIntervals() {
+        MultiRangeItem<Double> item = MultiRangeItem.overPoints(NumberType.DOUBLE, "i", INCLUSIVE, INCLUSIVE);
+        item.addPoint(0.0);
+        item.addPoint(-0.0);
+        assertEquals(List.of(new Range<>(0.0, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(NEGATIVE_INFINITY, 0.0);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(0.0, POSITIVE_INFINITY);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, POSITIVE_INFINITY)),
+                     item.sortedRanges());
+
+        try {
+            item.addRange(POSITIVE_INFINITY, NEGATIVE_INFINITY);
+            fail("negative ranges should be disallowed");
+        }
+        catch (IllegalArgumentException e) {
+            assertEquals("ranges must satisfy start <= end, but got Infinity > -Infinity", e.getMessage());
+        }
+    }
+
+    @Test
+    public void testSpecialValuesWithClosedOpenIntervals() {
+        MultiRangeItem<Double> item = MultiRangeItem.overPoints(NumberType.DOUBLE, "i", INCLUSIVE, EXCLUSIVE);
+        item.addPoint( 0.0);
+        item.addPoint(-0.0);
+        assertEquals(List.of(new Range<>(0.0, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(NEGATIVE_INFINITY, 0.0);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(0.0, POSITIVE_INFINITY);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, POSITIVE_INFINITY)),
+                     item.sortedRanges());
+
+        try {
+            item.addRange(POSITIVE_INFINITY, NEGATIVE_INFINITY);
+            fail("negative ranges should be disallowed");
+        }
+        catch (IllegalArgumentException e) {
+            assertEquals("ranges must satisfy start <= end, but got Infinity > -Infinity", e.getMessage());
+        }
+    }
+
+    @Test
+    public void testSpecialValuesWithOpenClosedIntervals() {
+        MultiRangeItem<Double> item = MultiRangeItem.overPoints(NumberType.DOUBLE, "i", EXCLUSIVE, INCLUSIVE);
+        item.addPoint( 0.0);
+        item.addPoint(-0.0);
+        assertEquals(List.of(new Range<>(0.0, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(NEGATIVE_INFINITY, 0.0);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(0.0, POSITIVE_INFINITY);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, POSITIVE_INFINITY)),
+                     item.sortedRanges());
+
+        try {
+            item.addRange(POSITIVE_INFINITY, NEGATIVE_INFINITY);
+            fail("negative ranges should be disallowed");
+        }
+        catch (IllegalArgumentException e) {
+            assertEquals("ranges must satisfy start <= end, but got Infinity > -Infinity", e.getMessage());
+        }
+    }
+
+    @Test
+    public void testSpecialValuesWithOpenIntervals() {
+        MultiRangeItem<Double> item = MultiRangeItem.overPoints(NumberType.DOUBLE, "i", EXCLUSIVE, EXCLUSIVE);
+        item.addPoint( 0.0);
+        item.addPoint(-0.0);
+        assertEquals(List.of(new Range<>(0.0, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(NEGATIVE_INFINITY, 0.0);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, 0.0)),
+                     item.sortedRanges());
+
+        item.addRange(0.0, POSITIVE_INFINITY);
+        assertEquals(List.of(new Range<>(NEGATIVE_INFINITY, 0.0),
+                             new Range<>(0.0, POSITIVE_INFINITY)),
+                     item.sortedRanges());
+
+        try {
+            item.addRange(POSITIVE_INFINITY, NEGATIVE_INFINITY);
+            fail("negative ranges should be disallowed");
+        }
+        catch (IllegalArgumentException e) {
+            assertEquals("ranges must satisfy start <= end, but got Infinity > -Infinity", e.getMessage());
+        }
+    }
+
+    @Test
+    public void testAddingRangesOrderedByStartWithClosedIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", INCLUSIVE, INCLUSIVE);
+        ranges.stream().sorted(comparingInt(range -> range.start))
+              .forEach(range -> item.addRange(range.start, range.end));
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    public void testAddingRangesOrderedByStartWithOpenIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", EXCLUSIVE, EXCLUSIVE);
+        ranges.stream().sorted(comparingInt(range -> range.start))
+              .forEach(range -> item.addRange(range.start, range.end));
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    public void testAddingRangesOrderedByEndWithClosedIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", INCLUSIVE, INCLUSIVE);
+        ranges.stream().sorted(comparingInt(range -> range.end))
+              .forEach(range -> item.addRange(range.start, range.end));
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    public void testAddingRangesOrderedByEndWithOpenIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", EXCLUSIVE, EXCLUSIVE);
+        ranges.stream().sorted(comparingInt(range -> range.end))
+              .forEach(range -> item.addRange(range.start, range.end));
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    public void testAddingRangesUnorderedWithClosedIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", INCLUSIVE, INCLUSIVE);
+        for (Range<Integer> range : ranges)
+            item.addRange(range.start, range.end);
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    public void testAddingRangesUnorderedWithOpenIntervals() {
+        MultiRangeItem<Integer> item = MultiRangeItem.overPoints(NumberType.INTEGER, "i", EXCLUSIVE, EXCLUSIVE);
+        for (Range<Integer> range : ranges)
+            item.addRange(range.start, range.end);
+
+        assertEquals(List.of(new Range<>(0, 9)),
+                     item.sortedRanges());
+    }
+
+    @Test
+    @Disabled
+    public void testDoublePointsSerialization() {
+        ByteBuffer pointsBuffer = ByteBuffer.allocate(25);
+        MultiRangeItem<Double> pointsItem = MultiRangeItem.overPoints(NumberType.DOUBLE, "i", EXCLUSIVE, INCLUSIVE)
+                                                          .addRange(NEGATIVE_INFINITY, POSITIVE_INFINITY);
+        pointsItem.encode(pointsBuffer);
+
+        ByteBuffer expected = ByteBuffer.allocate(25);
+        expected.put((byte) 0b00000111); // ItemType.MULTI_TERM
+        expected.put((byte) 0b00100000); // OR << 5, RANGES
+        expected.putInt(1);              // term count
+        expected.put((byte) 0b00010101); // UNIFORM_DOUBLE << 3, end inclusive, same index
+        expected.put((byte) 1);          // index name length
+        expected.put((byte) 'i');        // index name bytes
+        expected.putDouble(NEGATIVE_INFINITY);
+        expected.putDouble(POSITIVE_INFINITY);
+
+        pointsBuffer.flip();
+        expected.flip();
+        assertArrayEquals(expected.array(), pointsBuffer.array());
+        assertEquals(expected, pointsBuffer);
+    }
+
+    @Test
+    @Disabled
+    public void testDoubleRangesSerialization() {
+        ByteBuffer rangesBuffer = ByteBuffer.allocate(59);
+        MultiRangeItem<Double> rangesItem = MultiRangeItem.overRanges(NumberType.DOUBLE, "i", INCLUSIVE, "j", EXCLUSIVE)
+                                                          .addPoint(      -0.0)
+                                                          .addRange( 1.0,  2.0)
+                                                          .addRange(-1.0, -0.5);
+        rangesItem.encode(rangesBuffer);
+
+        ByteBuffer expected = ByteBuffer.allocate(59);
+        expected.put((byte) 0b00000111); // ItemType.MULTI_TERM
+        expected.put((byte) 0b00100000); // OR << 5, RANGES
+        expected.putInt(3);              // term count
+        expected.put((byte) 0b00010010); // UNIFORM_DOUBLE, start inclusive, two indexes
+        expected.put((byte) 1);          // index name length
+        expected.put((byte) 'i');        // index name bytes
+        expected.put((byte) 1);          // index name length
+        expected.put((byte) 'j');        // index name bytes
+        expected.putDouble(-1.0);
+        expected.putDouble(-0.5);
+        expected.putDouble(-0.0);
+        expected.putDouble(-0.0);
+        expected.putDouble( 1.0);
+        expected.putDouble( 2.0);
+
+        rangesBuffer.flip();
+        expected.flip();
+        assertArrayEquals(expected.array(), rangesBuffer.array());
+        assertEquals(expected, rangesBuffer);
+    }
+
+    @Test
+    @Disabled
+    public void testIntegerRangesSerialization() {
+        ByteBuffer rangesBuffer = ByteBuffer.allocate(24);
+        MultiRangeItem<Integer> rangesItem = MultiRangeItem.overRanges(NumberType.INTEGER, "start", INCLUSIVE, "end", EXCLUSIVE)
+                                                          .addPoint(                0)
+                                                          .addRange( 1, (1 << 29) - 1)
+                                                          .addRange(-1,            -0);
+        rangesItem.encode(rangesBuffer);
+
+        ByteBuffer expected = ByteBuffer.allocate(24);
+        expected.put((byte) 0b00000111);              // ItemType.MULTI_TERM
+        expected.put((byte) 0b00100000);              // OR << 5, RANGES
+        expected.putInt(2);                           // term count
+        expected.put((byte) 0b00011010);              // COMPRESSED_INTEGER << 3, start inclusive, two indexes
+        expected.put((byte) 5);                       // index name length
+        expected.put("start".getBytes(UTF_8));        // index name bytes
+        expected.put((byte) 3);                       // index name length
+        expected.put("end".getBytes(UTF_8));          // index name bytes
+        putCompressedNumber(-1, expected);            // 1 byte
+        putCompressedNumber(0, expected);             // 1 byte
+        putCompressedNumber(1, expected);             // 1 byte
+        putCompressedNumber((1 << 29) - 1, expected); // 4 bytes
+
+        rangesBuffer.flip();
+        expected.flip();
+        assertArrayEquals(expected.array(), rangesBuffer.array());
+        assertEquals(expected, rangesBuffer);
+    }
+
+}