1674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen/* 2674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * Copyright 2003 The Apache Software Foundation 3674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * 4674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * Licensed under the Apache License, Version 2.0 (the "License"); 5674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * you may not use this file except in compliance with the License. 6674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * You may obtain a copy of the License at 7674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * 8674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * http://www.apache.org/licenses/LICENSE-2.0 9674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * 10674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * Unless required by applicable law or agreed to in writing, software 11674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * distributed under the License is distributed on an "AS IS" BASIS, 12674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * See the License for the specific language governing permissions and 14674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen * limitations under the License. 15674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen */ 16674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenpackage org.mockito.cglib.util; 17674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 18674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenimport java.util.*; 19674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 20674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenabstract class SorterTemplate { 21674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private static final int MERGESORT_THRESHOLD = 12; 22674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private static final int QUICKSORT_THRESHOLD = 7; 23674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 24674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen abstract protected void swap(int i, int j); 25674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen abstract protected int compare(int i, int j); 26674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 27674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen protected void quickSort(int lo, int hi) { 28674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen quickSortHelper(lo, hi); 29674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen insertionSort(lo, hi); 30674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 31674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 32674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private void quickSortHelper(int lo, int hi) { 33674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (;;) { 34674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int diff = hi - lo; 35674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (diff <= QUICKSORT_THRESHOLD) { 36674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen break; 37674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 38674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int i = (hi + lo) / 2; 39674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(lo, i) > 0) { 40674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(lo, i); 41674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 42674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(lo, hi) > 0) { 43674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(lo, hi); 44674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 45674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(i, hi) > 0) { 46674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(i, hi); 47674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 48674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int j = hi - 1; 49674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(i, j); 50674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen i = lo; 51674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int v = j; 52674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (;;) { 53674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (compare(++i, v) < 0) { 54674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen /* nothing */; 55674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 56674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (compare(--j, v) > 0) { 57674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen /* nothing */; 58674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 59674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (j < i) { 60674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen break; 61674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 62674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(i, j); 63674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 64674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(i, hi - 1); 65674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (j - lo <= hi - i + 1) { 66674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen quickSortHelper(lo, j); 67674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen lo = i + 1; 68674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } else { 69674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen quickSortHelper(i + 1, hi); 70674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen hi = j; 71674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 72674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 73674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 74674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 75674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private void insertionSort(int lo, int hi) { 76674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (int i = lo + 1 ; i <= hi; i++) { 77674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (int j = i; j > lo; j--) { 78674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(j - 1, j) > 0) { 79674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(j - 1, j); 80674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } else { 81674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen break; 82674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 83674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 84674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 85674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 86674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 87674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen protected void mergeSort(int lo, int hi) { 88674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int diff = hi - lo; 89674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (diff <= MERGESORT_THRESHOLD) { 90674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen insertionSort(lo, hi); 91674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return; 92674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 93674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int mid = lo + diff / 2; 94674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen mergeSort(lo, mid); 95674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen mergeSort(mid, hi); 96674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen merge(lo, mid, hi, mid - lo, hi - mid); 97674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 98674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 99674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private void merge(int lo, int pivot, int hi, int len1, int len2) { 100674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (len1 == 0 || len2 == 0) { 101674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return; 102674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 103674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (len1 + len2 == 2) { 104674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(pivot, lo) < 0) { 105674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(pivot, lo); 106674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 107674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return; 108674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 109674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int first_cut, second_cut; 110674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int len11, len22; 111674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (len1 > len2) { 112674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len11 = len1 / 2; 113674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen first_cut = lo + len11; 114674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen second_cut = lower(pivot, hi, first_cut); 115674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len22 = second_cut - pivot; 116674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } else { 117674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len22 = len2 / 2; 118674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen second_cut = pivot + len22; 119674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen first_cut = upper(lo, pivot, second_cut); 120674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len11 = first_cut - lo; 121674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 122674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen rotate(first_cut, pivot, second_cut); 123674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int new_mid = first_cut + len22; 124674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen merge(lo, first_cut, new_mid, len11, len22); 125674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen merge(new_mid, second_cut, hi, len1 - len11, len2 - len22); 126674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 127674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 128674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private void rotate(int lo, int mid, int hi) { 129674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int lot = lo; 130674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int hit = mid - 1; 131674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (lot < hit) { 132674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(lot++, hit--); 133674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 134674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen lot = mid; hit = hi - 1; 135674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (lot < hit) { 136674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(lot++, hit--); 137674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 138674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen lot = lo; hit = hi - 1; 139674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (lot < hit) { 140674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen swap(lot++, hit--); 141674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 142674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 143674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 144674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private int lower(int lo, int hi, int val) { 145674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int len = hi - lo; 146674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (len > 0) { 147674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int half = len / 2; 148674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int mid= lo + half; 149674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(mid, val) < 0) { 150674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen lo = mid + 1; 151674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len = len - half -1; 152674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } else { 153674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len = half; 154674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 155674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 156674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return lo; 157674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 158674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 159674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen private int upper(int lo, int hi, int val) { 160674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int len = hi - lo; 161674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen while (len > 0) { 162674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int half = len / 2; 163674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen int mid = lo + half; 164674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (compare(val, mid) < 0) { 165674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len = half; 166674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } else { 167674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen lo = mid + 1; 168674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen len = len - half -1; 169674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 170674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 171674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return lo; 172674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 173674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 174