/*
* 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
    }

    
Params:
  • searchIn – sorted list to look in
  • searchFor – key to find
/** * @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(); } }