src/java/org/apache/cassandra/utils/IntegerInterval.java

package org.apache.cassandra.utils;

import java.util.*;
import java.util.concurrent.atomic.AtomicLongFieldUpdater;
import java.util.stream.Collectors;

import com.google.common.collect.Lists;
import com.google.common.primitives.Longs;

/**
 * Mutable integer interval class, thread-safe.
 * Represents the interval [lower,upper].
 */
public class IntegerInterval
{
    volatile long interval;
    private static AtomicLongFieldUpdater<IntegerInterval> intervalUpdater =
            AtomicLongFieldUpdater.newUpdater(IntegerInterval.class, "interval");

    private IntegerInterval(long interval)
    {
        this.interval = interval;
    }

    public IntegerInterval(int lower, int upper)
    {
        this(make(lower, upper));
    }

    public IntegerInterval(IntegerInterval src)
    {
        this(src.interval);
    }

    public int lower()
    {
        return lower(interval);
    }

    public int upper()
    {
        return upper(interval);
    }

    /**
     * Expands the interval to cover the given value by extending one of its sides if necessary.
     * Mutates this. Thread-safe.
     */
    public void expandToCover(int value)
    {
        long prev;
        int lower;
        int upper;
        do
        {
            prev = interval;
            upper = upper(prev);
            lower = lower(prev);
            if (value > upper) // common case
                upper = value;
            else if (value < lower)
                lower = value;
        }
        while (!intervalUpdater.compareAndSet(this, prev, make(lower, upper)));
    }

    @Override
    public int hashCode()
    {
        return Long.hashCode(interval);
    }

    @Override
    public boolean equals(Object obj)
    {
        if (getClass() != obj.getClass())
            return false;
        IntegerInterval other = (IntegerInterval) obj;
        return interval == other.interval;
    }

    public String toString()
    {
        long interval = this.interval;
        return "[" + lower(interval) + "," + upper(interval) + "]";
    }

    private static long make(int lower, int upper)
    {
        assert lower <= upper;
        return ((lower & 0xFFFFFFFFL) << 32) | upper & 0xFFFFFFFFL;
    }

    private static int lower(long interval)
    {
        return (int) (interval >>> 32);
    }

    private static int upper(long interval)
    {
        return (int) interval;
    }


    /**
     * A mutable set of closed integer intervals, stored in normalized form (i.e. where overlapping intervals are
     * converted to a single interval covering both). Thread-safe.
     */
    public static class Set
    {
        static long[] EMPTY = new long[0];

        private volatile long[] ranges = EMPTY;

        /**
         * Adds an interval to the set, performing the necessary normalization.
         */
        public synchronized void add(int start, int end)
        {
            assert start <= end;
            long[] ranges, newRanges;
            {
                ranges = this.ranges; // take local copy to avoid risk of it changing in the midst of operation

                // extend ourselves to cover any ranges we overlap
                // record directly preceding our end may extend past us, so take the max of our end and its
                int rpos = Arrays.binarySearch(ranges, ((end & 0xFFFFFFFFL) << 32) | 0xFFFFFFFFL); // floor (i.e. greatest <=) of the end position
                if (rpos < 0)
                    rpos = (-1 - rpos) - 1;
                if (rpos >= 0)
                {
                    int extend = upper(ranges[rpos]);
                    if (extend > end)
                        end = extend;
                }
    
                // record directly preceding our start may extend into us; if it does, we take it as our start
                int lpos = Arrays.binarySearch(ranges, ((start & 0xFFFFFFFFL) << 32) | 0); // lower (i.e. greatest <) of the start position
                if (lpos < 0)
                    lpos = -1 - lpos;
                lpos -= 1;
                if (lpos >= 0)
                {
                    if (upper(ranges[lpos]) >= start)
                    {
                        start = lower(ranges[lpos]);
                        --lpos;
                    }
                }
    
                newRanges = new long[ranges.length - (rpos - lpos) + 1];
                int dest = 0;
                for (int i = 0; i <= lpos; ++i)
                    newRanges[dest++] = ranges[i];
                newRanges[dest++] = make(start, end);
                for (int i = rpos + 1; i < ranges.length; ++i)
                    newRanges[dest++] = ranges[i];
            }
            this.ranges = newRanges;
        }

        /**
         * Returns true if the set completely covers the given interval.
         */
        public boolean covers(IntegerInterval iv)
        {
            long l = iv.interval;
            return covers(lower(l), upper(l));
        }

        /**
         * Returns true if the set completely covers the given interval.
         */
        public boolean covers(int start, int end)
        {
            long[] ranges = this.ranges; // take local copy to avoid risk of it changing in the midst of operation
            int rpos = Arrays.binarySearch(ranges, ((start & 0xFFFFFFFFL) << 32) | 0xFFFFFFFFL);        // floor (i.e. greatest <=) of the end position
            if (rpos < 0)
                rpos = (-1 - rpos) - 1;
            if (rpos == -1)
                return false;
            return upper(ranges[rpos]) >= end;
        }

        /**
         * Returns a lower bound for the whole set. Will throw if set is not empty.
         */
        public int lowerBound()
        {
            return lower(ranges[0]);
        }

        /**
         * Returns an upper bound for the whole set. Will throw if set is not empty.
         */
        public int upperBound()
        {
            long[] ranges = this.ranges; // take local copy to avoid risk of it changing in the midst of operation
            return upper(ranges[ranges.length - 1]);
        }

        public Collection<IntegerInterval> intervals()
        {
            return Lists.transform(Longs.asList(ranges), iv -> new IntegerInterval(iv));
        }

        @Override
        public int hashCode()
        {
            return Arrays.hashCode(ranges);
        }

        @Override
        public boolean equals(Object obj)
        {
            if (getClass() != obj.getClass())
                return false;
            Set other = (Set) obj;
            return Arrays.equals(ranges, other.ranges);
        }

        public String toString()
        {
            return "[" + intervals().stream().map(IntegerInterval::toString).collect(Collectors.joining(", ")) + "]";
        }
    }
}