Sorter


1   /**
2   * The XMOJO Project 5
3   * Copyright � 2003 XMOJO.org. All rights reserved.
4   
5   * NO WARRANTY
6   
7   * BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR
8   * THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
9   * OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
10  * PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
11  * OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
13  * TO THE QUALITY AND PERFORMANCE OF THE LIBRARY IS WITH YOU. SHOULD THE
14  * LIBRARY PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
15  * REPAIR OR CORRECTION.
16  
17  * IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL
18  * ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE
19  * THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY
20  * GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
21  * USE OR INABILITY TO USE THE LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF
22  * DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD
23  * PARTIES OR A FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE),
24  * EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
25  * SUCH DAMAGES.
26  **/
27  
28  package com.adventnet.jmx.utils;
29  
30  /**
31   * This is a utility class which sorts a objectID array using
32   * quick sort mechanism .By default the compareTo method compares
33   * two strings str1 & str2 considering it to be a OID string. API
34   * users may override this method inorder to have their own compareTo
35   * method incase of different type of string.
36   * <p>
37   * Usage is :
38   * <li>sorter = new Sorter();
39   * <li>toSort = new String[2]{".1.3.6.1.3.2", ".1.3.6.1.3.12",};
40   * <li>sorter.sort(toSort, null);
41   */
42  public class Sorter implements java.io.Serializable  
43  {
44  
45  
46     /** This is a generic version of C.A.R Hoare's Quick Sort
47      * algorithm.  This will handle arrays that are already
48      * sorted, and arrays with duplicate keys.<BR>
49      *
50      * If you think of a one dimensional array as going from
51      * the lowest index on the left to the highest index on the right
52      * then the parameters to this function are lowest index or
53      * left and highest index or right.  The first time you call
54      * this function it will be with the parameters 0, a.length - 1.
55      *
56      * @param a       an integer array
57      * @param lo0     left boundary of array partition
58      * @param hi0     right boundary of array partition
59      */
60     public void QuickSort(String   a[], int lo0, int hi0) throws Exception  
61     {
62        int lo = lo0;
63        int hi = hi0;
64        String   mid;
65  
66        if ( hi0 > lo0)
67        {
68  
69           /* Arbitrarily establishing partition element as the midpoint of
70            * the array.
71            */
72           mid = a[ ( lo0 + hi0 ) / 2 ];
73  
74           // loop through the array until indices cross
75           while( lo <= hi )
76           {
77              /* find the first element that is greater than or equal to
78               * the partition element starting from the left Index.
79               */
80           while( ( lo < hi0 ) && (compareTo(a[lo], mid) < 0))
81           ++lo;
82  
83              /* find an element that is smaller than or equal to
84               * the partition element starting from the right Index.
85               */
86           while( ( hi > lo0 ) && (compareTo(a[hi], mid) > 0))
87           --hi;
88  
89              // if the indexes have not crossed, swap
90              if( lo <= hi )
91              {
92                 swap(a, lo, hi);
93                 ++lo;
94                 --hi;
95              }
96           }
97  
98           /* If the right index has not reached the left side of array
99            * must now sort the left partition.
100           */
101          if( lo0 < hi )
102             QuickSort( a, lo0, hi );
103 
104          /* If the left index has not reached the right side of array
105           * must now sort the right partition.
106           */
107          if( lo < hi0 )
108             QuickSort( a, lo, hi0 );
109 
110       }
111    }
112 
113    /**
114     * This method compares two string considering it be
115     * OID string. API users may override this method incase
116     * if they want to have different compareTo method.
117     */
118 
119     private int compareTo(String   str1, String   str2)
120     {
121         int ret = str1.compareTo(str2);
122 
123         if(ret > 0)
124             return 1;
125         if(ret < 0)
126             return -1;
127         return 0;
128     }
129 
130    private void swap(String   a[], int i, int j)
131    {
132       Object   T;
133       T = a[i];
134       a[i] = a[j];
135       a[j] = (String  )T;
136 
137       if(obj != null)
138       {
139 
140         int max = obj.length;
141 
142         for( int pos = 0; pos < max; pos++)
143         {
144             Object  [] b = obj[pos];
145             T = b[i];
146             b[i] = b[j];
147             b[j] = T;
148         }
149       }
150 
151 
152    }
153 
154    Object  [][] obj = null;
155 
156    /**
157     * This method sorts the OID string array in ascending order.
158     * Also it sorts multi array objects in "obj" according to the key
159     * OID string array "a".
160     * @param a the key string array to be sorted.
161     * @param obj the multiarray objects which are sorted according to the
162     * key oid.
163     */
164    public void sort(String   a[], Object  [][] obj) throws Exception  
165    {
166       this.obj = obj;
167       QuickSort(a, 0, a.length - 1);
168    }
169 
170 
171    /** This is a generic version of C.A.R Hoare's Quick Sort
172     * algorithm.  This will handle arrays that are already
173     * sorted, and arrays with duplicate keys.<BR>
174     *
175     * If you think of a one dimensional array as going from
176     * the lowest index on the left to the highest index on the right
177     * then the parameters to this function are lowest index or
178     * left and highest index or right.  The first time you call
179     * this function it will be with the parameters 0, a.length - 1.
180     *
181     * @param a       an integer array
182     * @param lo0     left boundary of array partition
183     * @param hi0     right boundary of array partition
184     */
185    public void QuickSort(int a[], int lo0, int hi0) throws Exception  
186    {
187        int lo = lo0;
188        int hi = hi0;
189        int mid;
190 
191        if ( hi0 > lo0)
192        {
193 
194        /* Arbitrarily establishing partition element as the midpoint of
195        * the array.
196            */
197            mid = a[ ( lo0 + hi0 ) / 2 ];
198 
199            // loop through the array until indices cross
200            while( lo <= hi )
201            {
202            /* find the first element that is greater than or equal to
203            * the partition element starting from the left Index.
204                */
205                while( ( lo < hi0 ) &&  ( a[lo] < mid ))
206                    ++lo;
207 
208                    /* find an element that is smaller than or equal to
209                    * the partition element starting from the right Index.
210                */
211                while( ( hi > lo0 ) &&  ( a[hi] > mid ))
212                    --hi;
213 
214                // if the indexes have not crossed, swap
215                if( lo <= hi )
216                {
217                    swap(a, lo, hi);
218                    ++lo;
219                    --hi;
220                }
221            }
222 
223            /* If the right index has not reached the left side of array
224            * must now sort the left partition.
225            */
226            if( lo0 < hi )
227                QuickSort( a, lo0, hi );
228 
229                /* If the left index has not reached the right side of array
230                * must now sort the right partition.
231            */
232            if( lo < hi0 )
233                QuickSort( a, lo, hi0 );
234 
235        }
236    }
237 
238    private void swap(int a[], int i, int j)
239    {
240        int T;
241        T = a[i];
242        a[i] = a[j];
243        a[j] = T;
244 
245    }
246 
247    public void sort(int a[]) throws Exception  
248    {
249        QuickSort(a, 0, a.length - 1);
250    }
251 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags