001: /*
002: * Copyright 2003 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package net.sf.cglib.util;
017:
018: import java.util.*;
019:
020: abstract class SorterTemplate {
021: private static final int MERGESORT_THRESHOLD = 12;
022: private static final int QUICKSORT_THRESHOLD = 7;
023:
024: abstract protected void swap(int i, int j);
025:
026: abstract protected int compare(int i, int j);
027:
028: protected void quickSort(int lo, int hi) {
029: quickSortHelper(lo, hi);
030: insertionSort(lo, hi);
031: }
032:
033: private void quickSortHelper(int lo, int hi) {
034: for (;;) {
035: int diff = hi - lo;
036: if (diff <= QUICKSORT_THRESHOLD) {
037: break;
038: }
039: int i = (hi + lo) / 2;
040: if (compare(lo, i) > 0) {
041: swap(lo, i);
042: }
043: if (compare(lo, hi) > 0) {
044: swap(lo, hi);
045: }
046: if (compare(i, hi) > 0) {
047: swap(i, hi);
048: }
049: int j = hi - 1;
050: swap(i, j);
051: i = lo;
052: int v = j;
053: for (;;) {
054: while (compare(++i, v) < 0) {
055: /* nothing */;
056: }
057: while (compare(--j, v) > 0) {
058: /* nothing */;
059: }
060: if (j < i) {
061: break;
062: }
063: swap(i, j);
064: }
065: swap(i, hi - 1);
066: if (j - lo <= hi - i + 1) {
067: quickSortHelper(lo, j);
068: lo = i + 1;
069: } else {
070: quickSortHelper(i + 1, hi);
071: hi = j;
072: }
073: }
074: }
075:
076: private void insertionSort(int lo, int hi) {
077: for (int i = lo + 1; i <= hi; i++) {
078: for (int j = i; j > lo; j--) {
079: if (compare(j - 1, j) > 0) {
080: swap(j - 1, j);
081: } else {
082: break;
083: }
084: }
085: }
086: }
087:
088: protected void mergeSort(int lo, int hi) {
089: int diff = hi - lo;
090: if (diff <= MERGESORT_THRESHOLD) {
091: insertionSort(lo, hi);
092: return;
093: }
094: int mid = lo + diff / 2;
095: mergeSort(lo, mid);
096: mergeSort(mid, hi);
097: merge(lo, mid, hi, mid - lo, hi - mid);
098: }
099:
100: private void merge(int lo, int pivot, int hi, int len1, int len2) {
101: if (len1 == 0 || len2 == 0) {
102: return;
103: }
104: if (len1 + len2 == 2) {
105: if (compare(pivot, lo) < 0) {
106: swap(pivot, lo);
107: }
108: return;
109: }
110: int first_cut, second_cut;
111: int len11, len22;
112: if (len1 > len2) {
113: len11 = len1 / 2;
114: first_cut = lo + len11;
115: second_cut = lower(pivot, hi, first_cut);
116: len22 = second_cut - pivot;
117: } else {
118: len22 = len2 / 2;
119: second_cut = pivot + len22;
120: first_cut = upper(lo, pivot, second_cut);
121: len11 = first_cut - lo;
122: }
123: rotate(first_cut, pivot, second_cut);
124: int new_mid = first_cut + len22;
125: merge(lo, first_cut, new_mid, len11, len22);
126: merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
127: }
128:
129: private void rotate(int lo, int mid, int hi) {
130: int lot = lo;
131: int hit = mid - 1;
132: while (lot < hit) {
133: swap(lot++, hit--);
134: }
135: lot = mid;
136: hit = hi - 1;
137: while (lot < hit) {
138: swap(lot++, hit--);
139: }
140: lot = lo;
141: hit = hi - 1;
142: while (lot < hit) {
143: swap(lot++, hit--);
144: }
145: }
146:
147: private int lower(int lo, int hi, int val) {
148: int len = hi - lo;
149: while (len > 0) {
150: int half = len / 2;
151: int mid = lo + half;
152: if (compare(mid, val) < 0) {
153: lo = mid + 1;
154: len = len - half - 1;
155: } else {
156: len = half;
157: }
158: }
159: return lo;
160: }
161:
162: private int upper(int lo, int hi, int val) {
163: int len = hi - lo;
164: while (len > 0) {
165: int half = len / 2;
166: int mid = lo + half;
167: if (compare(val, mid) < 0) {
168: len = half;
169: } else {
170: lo = mid + 1;
171: len = len - half - 1;
172: }
173: }
174: return lo;
175: }
176: }
|