Class Partition


  • public class Partition
    extends java.lang.Object
    TODO
    • Constructor Summary

      Constructors 
      Constructor Description
      Partition()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static int partitionSubList​(int i, int j, byte[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, char[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, double[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, float[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, int[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, long[] values)
      Partition a subarray of values.
      static int partitionSubList​(int i, int j, short[] values)
      Partition a subarray of values.
      static <T extends java.lang.Comparable<T>>
      int
      partitionSubList​(int i, int j, java.util.List<T> values)
      Partition a sublist of values.
      static <T extends java.lang.Comparable<T>>
      int
      partitionSubList​(int i, int j, java.util.List<T> values, int[] permutation)
      Partition a sublist of values.
      static <T> int partitionSubList​(int i, int j, java.util.List<T> values, int[] permutation, java.util.Comparator<? super T> compare)
      Partition a sublist of values.
      static <T> int partitionSubList​(int i, int j, java.util.List<T> values, java.util.Comparator<? super T> compare)
      Partition a sublist of values.
      static <T extends java.lang.Comparable<T>>
      void
      partitionSubList​(java.util.ListIterator<T> i, java.util.ListIterator<T> j)
      Partition a sublist.
      static <T extends java.lang.Comparable<T>>
      void
      partitionSubList​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int[] permutation)
      Partition a sublist.
      static <T> void partitionSubList​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int[] permutation, java.util.Comparator<? super T> compare)
      Partition a sublist.
      static <T> void partitionSubList​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, java.util.Comparator<? super T> compare)
      Partition a sublist.
      • Methods inherited from class java.lang.Object

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

      • Partition

        public Partition()
    • Method Detail

      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           byte[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           short[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           int[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           long[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           float[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           double[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static int partitionSubList​(int i,
                                           int j,
                                           char[] values)
        Partition a subarray of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        values - array
        Returns:
        index of pivot element
      • partitionSubList

        public static <T> int partitionSubList​(int i,
                                               int j,
                                               java.util.List<T> values,
                                               java.util.Comparator<? super T> compare)
        Partition a sublist of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of the sublist
        j - index of last element of the sublist
        values - the list
        compare - ordering function on T
        Returns:
        index of pivot element
      • partitionSubList

        public static <T extends java.lang.Comparable<T>> int partitionSubList​(int i,
                                                                               int j,
                                                                               java.util.List<T> values)
        Partition a sublist of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.
        Parameters:
        i - index of first element of the sublist
        j - index of last element of the sublist
        values - the list
        Returns:
        index of pivot element
      • partitionSubList

        public static <T> void partitionSubList​(java.util.ListIterator<T> i,
                                                java.util.ListIterator<T> j,
                                                java.util.Comparator<? super T> compare)
        Partition a sublist. The element at j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        After the function returns, the iterator i is on the pivot element. That is, i.next() gives the element after the pivot.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        compare - ordering function on T
      • partitionSubList

        public static <T extends java.lang.Comparable<T>> void partitionSubList​(java.util.ListIterator<T> i,
                                                                                java.util.ListIterator<T> j)
        Partition a sublist. The element at j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller, and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        After the function returns, the iterator i is on the pivot element. That is, i.next() gives the element after the pivot.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
      • partitionSubList

        public static <T> int partitionSubList​(int i,
                                               int j,
                                               java.util.List<T> values,
                                               int[] permutation,
                                               java.util.Comparator<? super T> compare)
        Partition a sublist of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use partitionSubList to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - index of first element of the sublist
        j - index of last element of the sublist
        values - the list
        permutation - elements of this array are permuted in the same way as the elements in the values list
        compare - ordering function on T
        Returns:
        index of pivot element
      • partitionSubList

        public static <T extends java.lang.Comparable<T>> int partitionSubList​(int i,
                                                                               int j,
                                                                               java.util.List<T> values,
                                                                               int[] permutation)
        Partition a sublist of values. The element at index j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use partitionSubList to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - index of first element of the sublist
        j - index of last element of the sublist
        values - the list
        permutation - elements of this array are permuted in the same way as the elements in the values list
        Returns:
        index of pivot element
      • partitionSubList

        public static <T> void partitionSubList​(java.util.ListIterator<T> i,
                                                java.util.ListIterator<T> j,
                                                int[] permutation,
                                                java.util.Comparator<? super T> compare)
        Partition a sublist. The element at j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        After the function returns, the iterator i is on the pivot element. That is, i.next() gives the element after the pivot.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use partitionSubList to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        permutation - elements of this array are permuted in the same way as the elements in the values list
        compare - ordering function on T
      • partitionSubList

        public static <T extends java.lang.Comparable<T>> void partitionSubList​(java.util.ListIterator<T> i,
                                                                                java.util.ListIterator<T> j,
                                                                                int[] permutation)
        Partition a sublist. The element at j is taken as the pivot value. The elements [i,j] are reordered, such that all elements before the pivot are smaller, and all elements after the pivot are equal or larger than the pivot. The index of the pivot element is returned.

        After the function returns, the iterator i is on the pivot element. That is, i.next() gives the element after the pivot.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        permutation - elements of this array are permuted in the same way as the elements in the values list