Java example source code file (SortedLists.java)

This example Java source code file (SortedLists.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

annotation, beta, comparable, comparator, first_after, first_present, function, keyabsentbehavior, keypresentbehavior, list, nullable, override, sortedlists, util

The SortedLists.java Java example source code

/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed 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 com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.RandomAccess;

import javax.annotation.Nullable;

/**
 * Static methods pertaining to sorted {@link List} instances.
 *
 * In this documentation, the terms <i>greatest, greater, least, and
 * <i>lesser are considered to refer to the comparator on the elements, and the terms
 * <i>first and last are considered to refer to the elements' ordering in a
 * list.
 *
 * @author Louis Wasserman
 */
@GwtCompatible
@Beta final class SortedLists {
  private SortedLists() {}

  /**
   * A specification for which index to return if the list contains at least one element that
   * compares as equal to the key.
   */
  public enum KeyPresentBehavior {
    /**
     * Return the index of any list element that compares as equal to the key. No guarantees are
     * made as to which index is returned, if more than one element compares as equal to the key.
     */
    ANY_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List list, int foundIndex) {
        return foundIndex;
      }
    },
    /**
     * Return the index of the last list element that compares as equal to the key.
     */
    LAST_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List list, int foundIndex) {
        // Of course, we have to use binary search to find the precise
        // breakpoint...
        int lower = foundIndex;
        int upper = list.size() - 1;
        // Everything between lower and upper inclusive compares at >= 0.
        while (lower < upper) {
          int middle = (lower + upper + 1) >>> 1;
          int c = comparator.compare(list.get(middle), key);
          if (c > 0) {
            upper = middle - 1;
          } else { // c == 0
            lower = middle;
          }
        }
        return lower;
      }
    },
    /**
     * Return the index of the first list element that compares as equal to the key.
     */
    FIRST_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List list, int foundIndex) {
        // Of course, we have to use binary search to find the precise
        // breakpoint...
        int lower = 0;
        int upper = foundIndex;
        // Of course, we have to use binary search to find the precise breakpoint...
        // Everything between lower and upper inclusive compares at <= 0.
        while (lower < upper) {
          int middle = (lower + upper) >>> 1;
          int c = comparator.compare(list.get(middle), key);
          if (c < 0) {
            lower = middle + 1;
          } else { // c == 0
            upper = middle;
          }
        }
        return lower;
      }
    },
    /**
     * Return the index of the first list element that compares as greater than the key, or {@code
     * list.size()} if there is no such element.
     */
    FIRST_AFTER {
      @Override
      public <E> int resultIndex(
          Comparator<? super E> comparator, E key, List list, int foundIndex) {
        return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
      }
    },
    /**
     * Return the index of the last list element that compares as less than the key, or {@code -1}
     * if there is no such element.
     */
    LAST_BEFORE {
      @Override
      public <E> int resultIndex(
          Comparator<? super E> comparator, E key, List list, int foundIndex) {
        return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
      }
    };

    abstract <E> int resultIndex(
        Comparator<? super E> comparator, E key, List list, int foundIndex);
  }

  /**
   * A specification for which index to return if the list contains no elements that compare as
   * equal to the key.
   */
  public enum KeyAbsentBehavior {
    /**
     * Return the index of the next lower element in the list, or {@code -1} if there is no such
     * element.
     */
    NEXT_LOWER {
      @Override
      int resultIndex(int higherIndex) {
        return higherIndex - 1;
      }
    },
    /**
     * Return the index of the next higher element in the list, or {@code list.size()} if there is
     * no such element.
     */
    NEXT_HIGHER {
      @Override
      public int resultIndex(int higherIndex) {
        return higherIndex;
      }
    },
    /**
     * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at
     * which the key would be inserted into the list: the index of the next higher element in the
     * list, or {@code list.size()} if there is no such element.
     *
     * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
     * list that compares as equal to the key.
     *
     * <p>This is equivalent to the behavior of
     * {@link java.util.Collections#binarySearch(List, Object)} when the key isn't present, since
     * {@code ~insertionIndex} is equal to {@code -1 - insertionIndex}.
     */
    INVERTED_INSERTION_INDEX {
      @Override
      public int resultIndex(int higherIndex) {
        return ~higherIndex;
      }
    };

    abstract int resultIndex(int higherIndex);
  }

  /**
   * Searches the specified naturally ordered list for the specified object using the binary search
   * algorithm.
   *
   * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
   * KeyAbsentBehavior)} using {@link Ordering#natural}.
   */
  public static <E extends Comparable> int binarySearch(
      List<? extends E> list,
      E e,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    checkNotNull(e);
    return binarySearch(list, e, Ordering.natural(), presentBehavior, absentBehavior);
  }

  /**
   * Binary searches the list for the specified key, using the specified key function.
   *
   * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
   * KeyAbsentBehavior)} using {@link Ordering#natural}.
   */
  public static <E, K extends Comparable> int binarySearch(
      List<E> list,
      Function<? super E, K> keyFunction,
      @Nullable K key,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    return binarySearch(
        list, keyFunction, key, Ordering.natural(), presentBehavior, absentBehavior);
  }

  /**
   * Binary searches the list for the specified key, using the specified key function.
   *
   * <p>Equivalent to
   * {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)} using
   * {@link Lists#transform(List, Function) Lists.transform(list, keyFunction)}.
   */
  public static <E, K> int binarySearch(
      List<E> list,
      Function<? super E, K> keyFunction,
      @Nullable K key,
      Comparator<? super K> keyComparator,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    return binarySearch(
        Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
  }

  /**
   * Searches the specified list for the specified object using the binary search algorithm. The
   * list must be sorted into ascending order according to the specified comparator (as by the
   * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior
   * to making this call. If it is not sorted, the results are undefined.
   *
   * <p>If there are elements in the list which compare as equal to the key, the choice of
   * {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to
   * the key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
   *
   * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
   * access to each list element.
   *
   * @param list the list to be searched.
   * @param key the value to be searched for.
   * @param comparator the comparator by which the list is ordered.
   * @param presentBehavior the specification for what to do if at least one element of the list
   *        compares as equal to the key.
   * @param absentBehavior the specification for what to do if no elements of the list compare as
   *        equal to the key.
   * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
   *         otherwise the index determined by the {@code KeyAbsentBehavior}.
   */
  public static <E> int binarySearch(
      List<? extends E> list,
      @Nullable E key,
      Comparator<? super E> comparator,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    checkNotNull(comparator);
    checkNotNull(list);
    checkNotNull(presentBehavior);
    checkNotNull(absentBehavior);
    if (!(list instanceof RandomAccess)) {
      list = Lists.newArrayList(list);
    }
    // TODO(lowasser): benchmark when it's best to do a linear search

    int lower = 0;
    int upper = list.size() - 1;

    while (lower <= upper) {
      int middle = (lower + upper) >>> 1;
      int c = comparator.compare(key, list.get(middle));
      if (c < 0) {
        upper = middle - 1;
      } else if (c > 0) {
        lower = middle + 1;
      } else {
        return lower
            + presentBehavior.resultIndex(
                comparator, key, list.subList(lower, upper + 1), middle - lower);
      }
    }
    return absentBehavior.resultIndex(lower);
  }
}