1 /*
2 * The Apache Software License, Version 1.1
3 *
4 * Copyright (c) 2003 The Apache Software Foundation. All rights
5 * reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 * if any, must include the following acknowledgment:
21 * "This product includes software developed by the
22 * Apache Software Foundation (http://www.apache.org/)."
23 * Alternately, this acknowledgment may appear in the software itself,
24 * if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "Apache" and "Apache Software Foundation" must
27 * not be used to endorse or promote products derived from this
28 * software without prior written permission. For written
29 * permission, please contact apache@apache.org.
30 *
31 * 5. Products derived from this software may not be called "Apache",
32 * nor may "Apache" appear in their name, without prior written
33 * permission of the Apache Software Foundation.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46 * SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Apache Software Foundation. For more
51 * information on the Apache Software Foundation, please see
52 * <http://www.apache.org/>;.
53 */
54 package net.sf.cglib.util;
55
56 import java.util.*;
57
58 abstract class SorterTemplate {
59 private static final int MERGESORT_THRESHOLD = 12;
60 private static final int QUICKSORT_THRESHOLD = 7;
61
62 abstract protected void swap(int i, int j);
63 abstract protected int compare(int i, int j);
64
65 protected void quickSort(int lo, int hi) {
66 quickSortHelper(lo, hi);
67 insertionSort(lo, hi);
68 }
69
70 private void quickSortHelper(int lo, int hi) {
71 for (;;) {
72 int diff = hi - lo;
73 if (diff <= QUICKSORT_THRESHOLD) {
74 break;
75 }
76 int i = (hi + lo) / 2;
77 if (compare(lo, i) > 0) {
78 swap(lo, i);
79 }
80 if (compare(lo, hi) > 0) {
81 swap(lo, hi);
82 }
83 if (compare(i, hi) > 0) {
84 swap(i, hi);
85 }
86 int j = hi - 1;
87 swap(i, j);
88 i = lo;
89 int v = j;
90 for (;;) {
91 while (compare(++i, v) < 0) {
92 /* nothing */;
93 }
94 while (compare(--j, v) > 0) {
95 /* nothing */;
96 }
97 if (j < i) {
98 break;
99 }
100 swap(i, j);
101 }
102 swap(i, hi - 1);
103 if (j - lo <= hi - i + 1) {
104 quickSortHelper(lo, j);
105 lo = i + 1;
106 } else {
107 quickSortHelper(i + 1, hi);
108 hi = j;
109 }
110 }
111 }
112
113 private void insertionSort(int lo, int hi) {
114 for (int i = lo + 1 ; i <= hi; i++) {
115 for (int j = i; j > lo; j--) {
116 if (compare(j - 1, j) > 0) {
117 swap(j - 1, j);
118 } else {
119 break;
120 }
121 }
122 }
123 }
124
125 protected void mergeSort(int lo, int hi) {
126 int diff = hi - lo;
127 if (diff <= MERGESORT_THRESHOLD) {
128 insertionSort(lo, hi);
129 return;
130 }
131 int mid = lo + diff / 2;
132 mergeSort(lo, mid);
133 mergeSort(mid, hi);
134 merge(lo, mid, hi, mid - lo, hi - mid);
135 }
136
137 private void merge(int lo, int pivot, int hi, int len1, int len2) {
138 if (len1 == 0 || len2 == 0) {
139 return;
140 }
141 if (len1 + len2 == 2) {
142 if (compare(pivot, lo) < 0) {
143 swap(pivot, lo);
144 }
145 return;
146 }
147 int first_cut, second_cut;
148 int len11, len22;
149 if (len1 > len2) {
150 len11 = len1 / 2;
151 first_cut = lo + len11;
152 second_cut = lower(pivot, hi, first_cut);
153 len22 = second_cut - pivot;
154 } else {
155 len22 = len2 / 2;
156 second_cut = pivot + len22;
157 first_cut = upper(lo, pivot, second_cut);
158 len11 = first_cut - lo;
159 }
160 rotate(first_cut, pivot, second_cut);
161 int new_mid = first_cut + len22;
162 merge(lo, first_cut, new_mid, len11, len22);
163 merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
164 }
165
166 private void rotate(int lo, int mid, int hi) {
167 int lot = lo;
168 int hit = mid - 1;
169 while (lot < hit) {
170 swap(lot++, hit--);
171 }
172 lot = mid; hit = hi - 1;
173 while (lot < hit) {
174 swap(lot++, hit--);
175 }
176 lot = lo; hit = hi - 1;
177 while (lot < hit) {
178 swap(lot++, hit--);
179 }
180 }
181
182 private int lower(int lo, int hi, int val) {
183 int len = hi - lo;
184 while (len > 0) {
185 int half = len / 2;
186 int mid= lo + half;
187 if (compare(mid, val) < 0) {
188 lo = mid + 1;
189 len = len - half -1;
190 } else {
191 len = half;
192 }
193 }
194 return lo;
195 }
196
197 private int upper(int lo, int hi, int val) {
198 int len = hi - lo;
199 while (len > 0) {
200 int half = len / 2;
201 int mid = lo + half;
202 if (compare(val, mid) < 0) {
203 len = half;
204 } else {
205 lo = mid + 1;
206 len = len - half -1;
207 }
208 }
209 return lo;
210 }
211 }
This page was automatically generated by Maven