KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > versant > core > common > SortableBase


1
2 /*
3  * Copyright (c) 1998 - 2005 Versant Corporation
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License v1.0
6  * which accompanies this distribution, and is available at
7  * http://www.eclipse.org/legal/epl-v10.html
8  *
9  * Contributors:
10  * Versant Corporation - initial API and implementation
11  */
12 package com.versant.core.common;
13
14 /**
15  * Base class for containers that need to be able to sort themselves using
16  * the quicksort algorithm. Subclasses just need to implement compare
17  * and swap to make themselves sortable. The size field must be set to
18  * the number of entries in the container when sort is called.
19  *
20  * @see #compare
21  * @see #swap
22  * @see #sort
23  * @see #size
24  *
25  */
26 public abstract class SortableBase {
27
28     /**
29      * The number of entries in the container.
30      */
31     protected int size;
32
33     /**
34      * Sort the entries.
35      */
36     public void sort() {
37         quicksort(0, size - 1);
38     }
39
40     public void sort(int min, int max){
41         quicksort(min,max);
42     }
43     /**
44      * Compare entries at and a and b. Return 0 if equal, less than 0
45      * if a is less than b or greater than 0 if a is greater than b.
46      */
47     protected abstract int compare(int a, int b);
48
49     /**
50      * Swap entries.
51      */
52     protected abstract void swap(int index1, int index2);
53
54     private final void quicksort(final int left,final int right) {
55         final int size = right - left + 1;
56         if (size <= 3) {
57             manualSort(left, right, size);
58         } else {
59             final int median = median(left, right);
60             final int partition = partition(left, right, median);
61             quicksort(left, partition - 1);
62             quicksort(partition + 1, right);
63         }
64     }
65
66     /**
67      * This will sort up to 3 entries.
68      */
69     private final void manualSort(final int left, final int right,final int size) {
70         if (size <= 1) return;
71         if (size == 2) {
72             if (compare(left, right) > 0) swap(left, right);
73         } else {
74             if (compare(left, right - 1) > 0) swap(left, right - 1);
75             if (compare(left, right) > 0) swap(left, right);
76             if (compare(left + 1, right) > 0) swap(left + 1, right);
77         }
78
79     }
80
81     private final int median(final int left,final int right) {
82         final int center = (left + right) / 2;
83         if (compare(left, center) > 0) swap(left, center);
84         if (compare(left, right) > 0) swap(left, right);
85         if (compare(center, right) > 0) swap(center, right);
86         swap(center, right - 1);
87         return right - 1;
88     }
89
90     private final int partition(final int left,final int right,final int pivotIndex) {
91         int leftIndex = left;
92         int rightIndex = right - 1;
93         while (true) {
94             while (compare(++leftIndex, pivotIndex) < 0);
95             while (compare(--rightIndex, pivotIndex) > 0);
96             if (leftIndex >= rightIndex) {
97                 break; // pointers cross so partition done
98 } else {
99                 swap(leftIndex, rightIndex);
100             }
101         }
102         swap(leftIndex, right - 1); // restore pivot
103 return leftIndex; // return pivot location
104 }
105
106 }
107
108
Popular Tags