src/java/org/apache/cassandra/utils/AsymmetricOrdering.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 org.apache.cassandra.utils;

import java.util.List;

import com.google.common.collect.Ordering;

import net.nicoulaj.compilecommand.annotations.Inline;

public abstract class AsymmetricOrdering<T1, T2> extends Ordering<T1>
{

    public abstract int compareAsymmetric(T1 left, T2 right);

    public static enum Op
    {
        // maximum index < key; -1 if no such key. == CEIL - 1
        LOWER,

        // maximum index <= key; -1 if no such key. == HIGHER + 1
        FLOOR,

        // minimum index >= key; size() if no such key.  == LOWER + 1
        CEIL,

        // minimum index > key; size() if no such key. == FLOOR - 1
        HIGHER
    }

    /**
     * @param searchIn sorted list to look in
     * @param searchFor key to find
     */
    public int binarySearchAsymmetric(List<? extends T1> searchIn, T2 searchFor, Op op)
    {
        final int strictnessOfLessThan = strictnessOfLessThan(op);
        int lb = -1;
        int ub = searchIn.size();
        // a[-1]            ^= -infinity
        // a[search.size()] ^= +infinity

        while (lb + 1 < ub)
        {
            int m = (lb + ub) / 2;
            int c = compareAsymmetric(searchIn.get(m), searchFor);

            if (c < strictnessOfLessThan) lb = m;
            else ub = m;
        }

        return selectBoundary(op, lb, ub);
    }

    @Inline
    // this value, used as the right operand to a less than operator for the result
    // of a compare() makes its behaviour either strict (<) or not strict (<=).
    // a value of 1 is not strict, whereas 0 is strict
    private static int strictnessOfLessThan(Op op)
    {
        switch (op)
        {
            case FLOOR: case HIGHER:

            // { a[lb] <= v ^ a[ub] > v }
            return 1;

            // { a[m] >  v   ==>   a[ub] >  v   ==>   a[lb] <= v ^ a[ub] > v }
            // { a[m] <= v   ==>   a[lb] <= v   ==>   a[lb] <= v ^ a[ub] > v }

            case CEIL: case LOWER:

            // { a[lb] < v ^ a[ub] >= v }

            return 0;

            // { a[m] >= v   ==>   a[ub] >= v   ==>   a[lb] < v ^ a[ub] >= v }
            // { a[m] <  v   ==>   a[lb] <  v   ==>   a[lb] < v ^ a[ub] >= v }
        }
        throw new IllegalStateException();
    }

    @Inline
    private static int selectBoundary(Op op, int lb, int ub)
    {
        switch (op)
        {
            case CEIL:
                // { a[lb] < v ^ a[ub] >= v }
            case HIGHER:
                // { a[lb] <= v ^ a[ub] > v }
                return ub;
            case FLOOR:
                // { a[lb] <= v ^ a[ub] > v }
            case LOWER:
                // { a[lb] < v ^ a[ub] >= v }
                return lb;
        }
        throw new IllegalStateException();
    }

    private class Reversed extends AsymmetricOrdering<T1, T2>
    {
        public int compareAsymmetric(T1 left, T2 right)
        {
            return -AsymmetricOrdering.this.compareAsymmetric(left, right);
        }

        public int compare(T1 left, T1 right)
        {
            return AsymmetricOrdering.this.compare(right, left);
        }

        public AsymmetricOrdering<T1, T2> reverse()
        {
            return AsymmetricOrdering.this;
        }
    }

    public AsymmetricOrdering<T1, T2> reverse()
    {
        return new Reversed();
    }
}