SorterTemplate.java revision 674060f01e9090cd21b3c5656cc3204912ad17a6 
1/*
2 * Copyright 2003 The Apache Software Foundation
3 *
4 *  Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 *  Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package org.mockito.cglib.util;
17
18import java.util.*;
19
20abstract class SorterTemplate {
21    private static final int MERGESORT_THRESHOLD = 12;
22    private static final int QUICKSORT_THRESHOLD = 7;
23
24    abstract protected void swap(int i, int j);
25    abstract protected int compare(int i, int j);
26
27    protected void quickSort(int lo, int hi) {
28        quickSortHelper(lo, hi);
29        insertionSort(lo, hi);
30    }
31
32    private void quickSortHelper(int lo, int hi) {
33        for (;;) {
34            int diff = hi - lo;
35            if (diff <= QUICKSORT_THRESHOLD) {
36                break;
37            }
38            int i = (hi + lo) / 2;
39            if (compare(lo, i) > 0) {
40                swap(lo, i);
41            }
42            if (compare(lo, hi) > 0) {
43                swap(lo, hi);
44            }
45            if (compare(i, hi) > 0) {
46                swap(i, hi);
47            }
48            int j = hi - 1;
49            swap(i, j);
50            i = lo;
51            int v = j;
52            for (;;) {
53                while (compare(++i, v) < 0) {
54                    /* nothing */;
55                }
56                while (compare(--j, v) > 0) {
57                    /* nothing */;
58                }
59                if (j < i) {
60                    break;
61                }
62                swap(i, j);
63            }
64            swap(i, hi - 1);
65            if (j - lo <= hi - i + 1) {
66                quickSortHelper(lo, j);
67                lo = i + 1;
68            } else {
69                quickSortHelper(i + 1, hi);
70                hi = j;
71            }
72        }
73    }
74
75    private void insertionSort(int lo, int hi) {
76        for (int i = lo + 1 ; i <= hi; i++) {
77            for (int j = i; j > lo; j--) {
78                if (compare(j - 1, j) > 0) {
79                    swap(j - 1, j);
80                } else {
81                    break;
82                }
83            }
84        }
85    }
86
87    protected void mergeSort(int lo, int hi) {
88        int diff = hi - lo;
89        if (diff <= MERGESORT_THRESHOLD) {
90            insertionSort(lo, hi);
91            return;
92        }
93        int mid = lo + diff / 2;
94        mergeSort(lo, mid);
95        mergeSort(mid, hi);
96        merge(lo, mid, hi, mid - lo, hi - mid);
97    }
98
99    private void merge(int lo, int pivot, int hi, int len1, int len2) {
100        if (len1 == 0 || len2 == 0) {
101            return;
102        }
103        if (len1 + len2 == 2) {
104            if (compare(pivot, lo) < 0) {
105                swap(pivot, lo);
106            }
107            return;
108        }
109        int first_cut, second_cut;
110        int len11, len22;
111        if (len1 > len2) {
112            len11 = len1 / 2;
113            first_cut = lo + len11;
114            second_cut = lower(pivot, hi, first_cut);
115            len22 = second_cut - pivot;
116        } else {
117            len22 = len2 / 2;
118            second_cut = pivot + len22;
119            first_cut = upper(lo, pivot, second_cut);
120            len11 = first_cut - lo;
121        }
122        rotate(first_cut, pivot, second_cut);
123        int new_mid = first_cut + len22;
124        merge(lo, first_cut, new_mid, len11, len22);
125        merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
126    }
127
128    private void rotate(int lo, int mid, int hi) {
129        int lot = lo;
130        int hit = mid - 1;
131        while (lot < hit) {
132            swap(lot++, hit--);
133        }
134        lot = mid; hit = hi - 1;
135        while (lot < hit) {
136            swap(lot++, hit--);
137        }
138        lot = lo; hit = hi - 1;
139        while (lot < hit) {
140            swap(lot++, hit--);
141        }
142    }
143
144    private int lower(int lo, int hi, int val) {
145        int len = hi - lo;
146        while (len > 0) {
147            int half = len / 2;
148            int mid= lo + half;
149            if (compare(mid, val) < 0) {
150                lo = mid + 1;
151                len = len - half -1;
152            } else {
153                len = half;
154            }
155        }
156        return lo;
157    }
158
159    private int upper(int lo, int hi, int val) {
160        int len = hi - lo;
161        while (len > 0) {
162            int half = len / 2;
163            int mid = lo + half;
164            if (compare(val, mid) < 0) {
165                len = half;
166            } else {
167                lo = mid + 1;
168                len = len - half -1;
169            }
170        }
171        return lo;
172    }
173}
174