KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > lucene > util > Arrays


1 package org.apache.lucene.util;
2
3 /* ====================================================================
4  * The Apache Software License, Version 1.1
5  *
6  * Copyright (c) 2001 The Apache Software Foundation. All rights
7  * reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in
18  * the documentation and/or other materials provided with the
19  * distribution.
20  *
21  * 3. The end-user documentation included with the redistribution,
22  * if any, must include the following acknowledgment:
23  * "This product includes software developed by the
24  * Apache Software Foundation (http://www.apache.org/)."
25  * Alternately, this acknowledgment may appear in the software itself,
26  * if and wherever such third-party acknowledgments normally appear.
27  *
28  * 4. The names "Apache" and "Apache Software Foundation" and
29  * "Apache Lucene" must not be used to endorse or promote products
30  * derived from this software without prior written permission. For
31  * written permission, please contact apache@apache.org.
32  *
33  * 5. Products derived from this software may not be called "Apache",
34  * "Apache Lucene", nor may "Apache" appear in their name, without
35  * prior written permission of the Apache Software Foundation.
36  *
37  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
44  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
45  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
46  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
47  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
48  * SUCH DAMAGE.
49  * ====================================================================
50  *
51  * This software consists of voluntary contributions made by many
52  * individuals on behalf of the Apache Software Foundation. For more
53  * information on the Apache Software Foundation, please see
54  * <http://www.apache.org/>.
55  */
56
57 // copied from jdk 1.2b3 sources, so that we can use it in java 1.1
58
59 /**
60  * This class contains various methods for manipulating arrays (such as
61  * sorting and searching). It also contains a static factory that allows
62  * arrays to be viewed as Lists.
63  *
64  * @author Josh Bloch
65  * @version 1.17 03/18/98
66  * @since JDK1.2
67  */
68
69 public class Arrays {
70     /**
71      * Sorts the specified array of objects into ascending order, according
72      * to the <i>natural comparison method</i> of its elements. All
73      * elements in the array must implement the Comparable interface.
74      * Furthermore, all elements in the array must be <i>mutually
75      * comparable</i> (that is, e1.compareTo(e2) must not throw a
76      * typeMismatchException for any elements e1 and e2 in the array).
77      * <p>
78      * This sort is guaranteed to be <em>stable</em>: equal elements will
79      * not be reordered as a result of the sort.
80      * <p>
81      * The sorting algorithm is a modified mergesort (in which the merge is
82      * omitted if the highest element in the low sublist is less than the
83      * lowest element in the high sublist). This algorithm offers guaranteed
84      * n*log(n) performance, and can approach linear performance on nearly
85      * sorted lists.
86      *
87      * @param a the array to be sorted.
88      * @exception ClassCastException array contains elements that are not
89      * <i>mutually comparable</i> (for example, Strings and
90      * Integers).
91      * @see Comparable
92      */
93     public static void sort(String JavaDoc[] a) {
94         String JavaDoc aux[] = (String JavaDoc[])a.clone();
95         mergeSort(aux, a, 0, a.length);
96     }
97
98     private static void mergeSort(String JavaDoc src[], String JavaDoc dest[],
99                                   int low, int high) {
100     int length = high - low;
101
102     // Insertion sort on smallest arrays
103 if (length < 7) {
104         for (int i=low; i<high; i++)
105         for (int j=i; j>low && (dest[j-1]).compareTo(dest[j])>0; j--)
106             swap(dest, j, j-1);
107         return;
108     }
109
110         // Recursively sort halves of dest into src
111 int mid = (low + high)/2;
112         mergeSort(dest, src, low, mid);
113         mergeSort(dest, src, mid, high);
114
115         // If list is already sorted, just copy from src to dest. This is an
116 // optimization that results in faster sorts for nearly ordered lists.
117 if ((src[mid-1]).compareTo(src[mid]) <= 0) {
118            System.arraycopy(src, low, dest, low, length);
119            return;
120         }
121
122         // Merge sorted halves (now in src) into dest
123 for(int i = low, p = low, q = mid; i < high; i++) {
124             if (q>=high || p<mid && (src[p]).compareTo(src[q])<=0)
125                 dest[i] = src[p++];
126             else
127                 dest[i] = src[q++];
128         }
129     }
130
131     /**
132      * Swaps x[a] with x[b].
133      */
134     private static void swap(String JavaDoc x[], int a, int b) {
135     String JavaDoc t = x[a];
136     x[a] = x[b];
137     x[b] = t;
138     }
139 }
140
141
142
143
144
145
146
147
148
149
150
151
Popular Tags