Class SortedLists


  • public class SortedLists
    extends java.lang.Object
    Static methods pertaining to sorted List instances. In this documentation, the terms greatest, greater, least, and lesser are considered to refer to the comparator on the elements, and the terms first and last are considered to refer to the elements' ordering in a list.
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  SortedLists.KeyAbsentBehavior
      A specification for which index to return if the list contains no elements that compare as equal to the key.
      static class  SortedLists.KeyPresentBehavior
      A specification for which index to return if the list contains at least one element that compares as equal to the key.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private SortedLists()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <E> int binarySearch​(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
      Searches the specified list for the specified object using the binary search algorithm.
      static <E> int binarySearchAdd​(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator)
      Return the index of the first list element that compares as greater than the key, or list.size() if there is no such element.
      static <E> int binarySearchGet​(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator)
      Return the index of the first list element that compares as equal to the key.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • SortedLists

        private SortedLists()
    • Method Detail

      • binarySearch

        public static <E> int binarySearch​(java.util.List<? extends E> list,
                                           E key,
                                           java.util.Comparator<? super E> comparator,
                                           SortedLists.KeyPresentBehavior presentBehavior,
                                           SortedLists.KeyAbsentBehavior 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 Collections.sort(List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined.

        If there are elements in the list which compare as equal to the key, the choice of SortedLists.KeyPresentBehavior decides which index is returned. If no elements compare as equal to the key, the choice of SortedLists.KeyAbsentBehavior decides which index is returned.

        This method runs in log(n) time on random-access lists, which offer near-constant-time access to each list element.

        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        comparator - the comparator by which the list is ordered.
        presentBehavior - the specification for what to do if at least one element of the list compares as equal to the key.
        absentBehavior - the specification for what to do if no elements of the list compare as equal to the key.
        Returns:
        the index determined by the KeyPresentBehavior, if the key is in the list; otherwise the index determined by the KeyAbsentBehavior.
      • binarySearchAdd

        public static <E> int binarySearchAdd​(java.util.List<? extends E> list,
                                              E key,
                                              java.util.Comparator<? super E> comparator)
        Return the index of the first list element that compares as greater than the key, or list.size() if there is no such element.
      • binarySearchGet

        public static <E> int binarySearchGet​(java.util.List<? extends E> list,
                                              E key,
                                              java.util.Comparator<? super E> comparator)
        Return the index of the first list element that compares as equal to the key.