Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright 2003 The Apache Software Foundation
   *
   *  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 org.mockito.cglib.util;
 
 import java.util.*;
 
 abstract class SorterTemplate {
     private static final int MERGESORT_THRESHOLD = 12;
     private static final int QUICKSORT_THRESHOLD = 7;
 
     abstract protected void swap(int iint j);
     abstract protected int compare(int iint j);
 
     protected void quickSort(int loint hi) {
         quickSortHelper(lohi);
         insertionSort(lohi);
     }
 
     private void quickSortHelper(int loint hi) {
         for (;;) {
             int diff = hi - lo;
             if (diff <= ) {
                 break;
             }
             int i = (hi + lo) / 2;
             if (compare(loi) > 0) {
                 swap(loi);
             }
             if (compare(lohi) > 0) {
                 swap(lohi);
             }
             if (compare(ihi) > 0) {
                 swap(ihi);
             }
             int j = hi - 1;
             swap(ij);
             i = lo;
             int v = j;
             for (;;) {
                 while (compare(++iv) < 0) {
                     /* nothing */;
                 }
                 while (compare(--jv) > 0) {
                     /* nothing */;
                 }
                 if (j < i) {
                     break;
                 }
                 swap(ij);
             }
             swap(ihi - 1);
             if (j - lo <= hi - i + 1) {
                 quickSortHelper(loj);
                 lo = i + 1;
             } else {
                 quickSortHelper(i + 1, hi);
                 hi = j;
             }
         }
     }
     
     private void insertionSort(int loint hi) {
         for (int i = lo + 1 ; i <= hii++) {
             for (int j = ij > loj--) {
                 if (compare(j - 1, j) > 0) {
                     swap(j - 1, j);
                 } else {
                     break;
                 }
             }
         }
     }
 
     protected void mergeSort(int loint hi) {
         int diff = hi - lo;
         if (diff <= ) {
             insertionSort(lohi);
             return;
         }
         int mid = lo + diff / 2;
         mergeSort(lomid);
         mergeSort(midhi);
         merge(lomidhimid - lohi - mid);
     }
 
     private void merge(int loint pivotint hiint len1int len2) {
        if (len1 == 0 || len2 == 0) {
            return;
        }
        if (len1 + len2 == 2) {
            if (compare(pivotlo) < 0) {
                swap(pivotlo);
            }
            return;
        }
        int first_cutsecond_cut;
        int len11len22;
        if (len1 > len2) {
            len11 = len1 / 2;
            first_cut = lo + len11;
            second_cut = lower(pivothifirst_cut);
            len22 = second_cut - pivot;
        } else {
            len22 = len2 / 2;
            second_cut = pivot + len22;
            first_cut = upper(lopivotsecond_cut);
            len11 = first_cut - lo;
        }
        rotate(first_cutpivotsecond_cut);
        int new_mid = first_cut + len22;
        merge(lofirst_cutnew_midlen11len22);
        merge(new_midsecond_cuthilen1 - len11len2 - len22);
    }
    private void rotate(int loint midint hi) {
        int lot = lo;
        int hit = mid - 1;
        while (lot < hit) {
            swap(lot++, hit--);
        }
        lot = midhit = hi - 1;
        while (lot < hit) {
            swap(lot++, hit--);
        }
        lot = lohit = hi - 1;
        while (lot < hit) {
            swap(lot++, hit--);
        }
    }
    private int lower(int loint hiint val) {
        int len = hi - lo;
        while (len > 0) {
            int half = len / 2;
            int midlo + half;
            if (compare(midval) < 0) {
                lo = mid + 1;
                len = len - half -1;
            } else {
                len = half;
            }
        }
        return lo;
    }
    private int upper(int loint hiint val) {
        int len = hi - lo;
        while (len > 0) {
            int half = len / 2;
            int mid = lo + half;
            if (compare(valmid) < 0) {
                len = half;
            } else {
                lo = mid + 1;
                len = len - half -1;
            }
        }
        return lo;
    }
New to GrepCode? Check out our FAQ X