harry-core/src/harry/util/Ranges.java

/*
 *  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 harry.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

// TODO: this is not really an interval tree, just two sorted arrays. However, given that ExhaustiveChecker has
//       to inflate a partition every time we execute the query, we always know all boundaries at any given point in time.
public class Ranges
{
    private List<Range> sortedByMin;

    public Ranges(List<Range> ranges)
    {
        this.sortedByMin = new ArrayList<>(ranges);
        Collections.sort(sortedByMin, Comparator.comparingLong(a -> a.minBound));
    }

    public boolean isShadowed(long cd, long lts)
    {
        return !shadowedBy(cd, lts).isEmpty();
    }

    public List<Range> shadowedBy(long cd, long lts)
    {
        List<Range> shadowedBy = new ArrayList<>();
        for (Range range : sortedByMin)
        {
            if (range.minBound > cd)
                break;

            if (range.contains(cd, lts))
                shadowedBy.add(range);
        }

        return shadowedBy;
    }

    public List<Ranges.Range> newerThan(long ts)
    {
        return sortedByMin.stream().filter((rt) -> {
            return rt.timestamp >= ts;
        }).collect(Collectors.toList());
    }


    private static int toIdx(int idxOrIP)
    {
        if (idxOrIP >= 0)
            return idxOrIP;

        return -1 * (idxOrIP + 1);
    }

    public static class Range
    {
        public final long minBound;
        public final long maxBound;
        public final boolean minInclusive;
        public final boolean maxInclusive;

        public final long timestamp;

        public Range(long minBound, long maxBound, boolean minInclusive, boolean maxInclusive, long timestamp)
        {
            assert (minBound < maxBound) || ((minBound == maxBound) && minInclusive && maxInclusive) :
            String.format("Min bound should be less than max bound, or both bounds have to be inclusive, but was: %s%d,%d%s",
                          minInclusive ? "[" : "(",
                          minBound, maxBound,
                          maxInclusive ? "]" : ")");
            this.minBound = minBound;
            this.maxBound = maxBound;
            this.minInclusive = minInclusive;
            this.maxInclusive = maxInclusive;

            this.timestamp = timestamp;
        }

        public boolean contains(long descriptor)
        {
            if (minInclusive && descriptor == minBound)
                return true;
            if (maxInclusive && descriptor == maxBound)
                return true;

            return (descriptor > minBound) && (descriptor < maxBound);
        }

        public boolean contains(long descriptor, long ts)
        {
            return contains(descriptor) && timestamp >= ts;
        }

        public boolean equals(Object o)
        {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Range range = (Range) o;
            return minBound == range.minBound &&
                   maxBound == range.maxBound &&
                   minInclusive == range.minInclusive &&
                   maxInclusive == range.maxInclusive &&
                   timestamp == range.timestamp;
        }

        public int hashCode()
        {
            return Objects.hash(minBound, maxBound, minInclusive, maxInclusive, timestamp);
        }

        public String toString()
        {
            return "Range{" +
                   "minBound=" + minBound +
                   ", maxBound=" + maxBound +
                   ", minInclusive=" + minInclusive +
                   ", maxInclusive=" + maxInclusive +
                   ", timestamp=" + timestamp +
                   '}';
        }
    }

    public String toString()
    {
        return "Ranges{" +
               "sortedByMin=" + sortedByMin +
               '}';
    }
}