KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > logicalcobwebs > cglib > util > SorterTemplate


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 org.logicalcobwebs.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 }
212
Popular Tags