Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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.facebook.presto.operator;
 
 import static com.google.common.base.Preconditions.checkNotNull;
 
 public class PagesIndexOrdering
 {
     private static final int SMALL = 7;
     private static final int MEDIUM = 40;
 
     private final PagesIndexComparator comparator;
 
     public PagesIndexOrdering(PagesIndexComparator comparator)
     {
         this. = checkNotNull(comparator"comparator is null");
     }
 
     {
         return ;
     }
 
     public void sort(PagesIndex pagesIndex)
     {
         quickSort(pagesIndex, 0, pagesIndex.getPositionCount());
     }

    
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified comparator using quickSort.

The sorting algorithm is a tuned quickSort adapted from Jon L. Bentley and M. Douglas McIlroy, “Engineering a Sort Function”, Software: Practice and Experience, 23(11), pages 1249−1265, 1993.

Parameters:
from the index of the first element (inclusive) to be sorted.
to the index of the last element (exclusive) to be sorted.
 
     // note this code was forked from Fastutils
     private void quickSort(PagesIndex pagesIndexint fromint to)
     {
         int len = to - from;
         // Insertion sort on smallest arrays
         if (len < ) {
             for (int i = fromi < toi++) {
                 for (int j = ij > from && (.compareTo(pagesIndexj - 1, j) > 0); j--) {
                     pagesIndex.swap(jj - 1);
                 }
             }
             return;
         }
 
         // Choose a partition element, v
         int m = from + len / 2; // Small arrays, middle element
         if (len > ) {
             int l = from;
             int n = to - 1;
             if (len > ) { // Big arrays, pseudomedian of 9
                 int s = len / 8;
                 l = median3(pagesIndexll + sl + 2 * s);
                 m = median3(pagesIndexm - smm + s);
                 n = median3(pagesIndexn - 2 * sn - sn);
             }
             m = median3(pagesIndexlmn); // Mid-size, med of 3
         }
         // int v = x[m];
 
         int a = from;
         int b = a;
         int c = to - 1;
         // Establish Invariant: v* (<v)* (>v)* v*
         int d = c;
         while (true) {
             int comparison;
             while (b <= c && ((comparison = .compareTo(pagesIndexbm)) <= 0)) {
                 if (comparison == 0) {
                     if (a == m) {
                         m = b// moving target; DELTA to JDK !!!
                     }
                     else if (b == m) {
                         m = a// moving target; DELTA to JDK !!!
                     }
                     pagesIndex.swap(a++, b);
                 }
                 b++;
             }
             while (c >= b && ((comparison = .compareTo(pagesIndexcm)) >= 0)) {
                if (comparison == 0) {
                    if (c == m) {
                        m = d// moving target; DELTA to JDK !!!
                    }
                    else if (d == m) {
                        m = c// moving target; DELTA to JDK !!!
                    }
                    pagesIndex.swap(cd--);
                }
                c--;
            }
            if (b > c) {
                break;
            }
            if (b == m) {
                m = d// moving target; DELTA to JDK !!!
            }
            else if (c == m) {
                m = c// moving target; DELTA to JDK !!!
            }
            pagesIndex.swap(b++, c--);
        }
        // Swap partition elements back to middle
        int s;
        int n = to;
        s = Math.min(a - fromb - a);
        vectorSwap(pagesIndexfromb - ss);
        s = Math.min(d - cn - d - 1);
        vectorSwap(pagesIndexbn - ss);
        // Recursively sort non-partition-elements
        if ((s = b - a) > 1) {
            quickSort(pagesIndexfromfrom + s);
        }
        if ((s = d - c) > 1) {
            quickSort(pagesIndexn - sn);
        }
    }

    
Returns the index of the median of the three positions.
    private int median3(PagesIndex pagesIndexint aint bint c)
    {
        int ab = .compareTo(pagesIndexab);
        int ac = .compareTo(pagesIndexac);
        int bc = .compareTo(pagesIndexbc);
        return (ab < 0 ?
                (bc < 0 ? b : ac < 0 ? c : a) :
                (bc > 0 ? b : ac > 0 ? c : a));
    }

    
Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
    private void vectorSwap(PagesIndex pagesIndexint fromint lint s)
    {
        for (int i = 0; i < si++, from++, l++) {
            pagesIndex.swap(froml);
        }
    }
New to GrepCode? Check out our FAQ X