1 /*

     2  * CDDL HEADER START

     3  *

     4  * The contents of this file are subject to the terms of the

     5  * Common Development and Distribution License (the "License").

     6  * You may not use this file except in compliance with the License.

     7  *

     8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

     9  * or http://www.opensolaris.org/os/licensing.

    10  * See the License for the specific language governing permissions

    11  * and limitations under the License.

    12  *

    13  * When distributing Covered Code, include this CDDL HEADER in each

    14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.

    15  * If applicable, add the following below this CDDL HEADER, with the

    16  * fields enclosed by brackets "[]" replaced with your own identifying

    17  * information: Portions Copyright [yyyy] [name of copyright owner]

    18  *

    19  * CDDL HEADER END

    20  */

    21 

    22 /*

    23  * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved.

    24  */

    25 

    26 

    27 /**

    28  * SMC code adapted for Visual Panels

    29  *

    30  * Sort: a class that uses the quicksort algorithm to sort an

    31  *         array of objects.

    32  */

    33 

    34 package com.oracle.solaris.vp.panels.usermgr.client.swing;

    35 

    36 import java.util.Vector;

    37 import java.util.Random;

    38 import java.lang.Math;

    39 

    40 @SuppressWarnings("unchecked")

    41 public class Sort {

    42 

    43     private static Random rn = null;

    44 

    45     private static int MAX_ELEMENTS_FOR_COPY = 15000;

    46 

    47     static final int ASCENDING_SORT = 0;

    48     static final int DESCENDING_SORT = 0;

    49 

    50     private static void swap(Object arr[], int i, int j) {

    51         Object tmp;

    52 

    53         tmp = arr[i];

    54         arr[i] = arr[j];

    55         arr[j] = tmp;

    56     }

    57 

    58     /**

    59      * quicksort the array of objects.

    60      *

    61      * @param arr[] - an array of objects

    62      * @param left - the start index - from where to begin sorting

    63      * @param right - the last index

    64      * @param comp - object that implemnts the Compare interface

    65      */

    66     private static void quicksort(Object arr[], int left, int right,

    67 	Compare comp) {

    68 

    69         int i, last;

    70 

    71         if (left >= right) { /* do nothing if array contains fewer than two */

    72 	    return;    /* two elements */

    73         }

    74 

    75         swap(arr, left, left+(Math.abs(rn.nextInt())%(right-left)+1));

    76         last = left;

    77         for (i = left+1; i <= right; i++) {

    78             if (comp.doCompare(arr[i], arr[left]) < 0) {

    79                 swap(arr, ++last, i);

    80             }

    81         }

    82         swap(arr, left, last);

    83 

    84         quicksort(arr, left, last-1, comp);

    85         quicksort(arr, last+1, right, comp);

    86     }

    87 

    88     /**

    89      * quicksort the array of strings.

    90      *

    91      * @param arr[] - an array of strings

    92      * @param left - the start index - from where to begin sorting

    93      * @param right - the last index.

    94      * @param order - ASCENDING_SORT or DESCENDING_SORT

    95      */

    96     private static void quicksort(String arr[], int left, int right,

    97 	int order) {

    98 

    99         int i, last;

   100 

   101         if (left >= right) { /* do nothing if array contains fewer than two */

   102 	    return;	/* two elements */

   103         }

   104         swap(arr, left, left+(Math.abs(rn.nextInt())%(right-left)+1));

   105         last = left;

   106         for (i = left+1; i <= right; i++) {

   107             if (order == ASCENDING_SORT) {

   108                 if (arr[i].compareTo(arr[left]) < 0) {

   109                     swap(arr, ++last, i);

   110                 }

   111             } else {

   112                 if (arr[i].compareTo(arr[left]) > 0) {

   113                     swap(arr, ++last, i);

   114                 }

   115             }

   116         }

   117         swap(arr, left, last);

   118         quicksort(arr, left, last-1, order);

   119         quicksort(arr, last+1, right, order);

   120     }

   121 

   122     private static void swap(Vector vec, int i, int j) {

   123         Object tmp;

   124 

   125         tmp = vec.elementAt(i);

   126         vec.setElementAt(vec.elementAt(j), i);

   127         vec.setElementAt(tmp, j);

   128     }

   129 

   130     /**

   131      * quicksort the vector of objects.

   132      *

   133      * @param vec - a vector of objects

   134      * @param left - the start index - from where to begin sorting

   135      * @param right - the last index

   136      * @param comp - object that implements the Compare interface

   137      */

   138     private static void quicksort(Vector vec, int left, int right,

   139 	Compare comp) {

   140 

   141         int i, last;

   142 

   143         if (left >= right) { /* do nothing if vector contains fewer than two */

   144 	    return;	/* two elements */

   145         }

   146         swap(vec, left, left+(Math.abs(rn.nextInt())%(right-left)+1));

   147         last = left;

   148         for (i = left+1; i <= right; i++) {

   149             if (comp.doCompare(vec.elementAt(i), vec.elementAt(left)) < 0) {

   150                 swap(vec, ++last, i);

   151             }

   152         }

   153         swap(vec, left, last);

   154         quicksort(vec, left, last-1, comp);

   155         quicksort(vec, last+1, right, comp);

   156     }

   157 

   158     /**

   159      * quicksort the vector of strings.

   160      *

   161      * @param vec - a vector of strings

   162      * @param left - the start index - from where to begin sorting

   163      * @param right - the last index.

   164      * @param order - ASCENDING_SORT or DESCENDING_SORT

   165      */

   166     private static void quicksort(Vector vec, int left, int right, int order) {

   167         int i, last;

   168 

   169         if (left >= right) { /* do nothing if vector contains fewer than two */

   170 	    return;		/* two elements */

   171         }

   172         swap(vec, left, left+(Math.abs(rn.nextInt())%(right-left)+1));

   173         last = left;

   174         for (i = left+1; i <= right; i++) {

   175             if (order == ASCENDING_SORT) {

   176                if (((String)(vec.elementAt(i))).compareTo(

   177 				(String)vec.elementAt(left)) < 0) {

   178                    swap(vec, ++last, i);

   179                }

   180             } else {

   181                if (((String)(vec.elementAt(i))).compareTo(

   182 				(String)vec.elementAt(left)) > 0) {

   183                    swap(vec, ++last, i);

   184                }

   185             }

   186         }

   187         swap(vec, left, last);

   188         quicksort(vec, left, last-1, order);

   189         quicksort(vec, last+1, right, order);

   190     }

   191 

   192     /**

   193      * quicksort the vector of objects.

   194      *

   195      * @param vec - a vector of objects

   196      * @param left - the start index - from where to begin sorting

   197      * @param right - the last index

   198      * @param comp - object that implemnts the Compare interface

   199      */

   200     private static void quicksort(QuickVector vec, int left, int right,

   201 	Compare comp) {

   202 

   203         int i, last;

   204 

   205         if (left >= right) { /* do nothing if vector contains fewer than two */

   206 	    return;		/* two elements */

   207         }

   208         vec.quickSwapElementsAt(left,

   209 				left+(Math.abs(rn.nextInt())%(right-left)+1));

   210         last = left;

   211         for (i = left+1; i <= right; i++) {

   212             if (comp.doCompare(vec.quickElementAt(i),

   213 				vec.quickElementAt(left)) < 0) {

   214                 vec.quickSwapElementsAt(++last, i);

   215             }

   216         }

   217         vec.quickSwapElementsAt(left, last);

   218         quicksort(vec, left, last-1, comp);

   219         quicksort(vec, last+1, right, comp);

   220     }

   221 

   222     /**

   223      * quicksort the vector of strings.

   224      *

   225      * @param vec - a vector of strings

   226      * @param left - the start index - from where to begin sorting

   227      * @param right - the last index.

   228      * @param order - ASCENDING_SORT or DESCENDING_SORT

   229      */

   230     private static void quicksort(QuickVector vec, int left, int right,

   231 	int order) {

   232 

   233         int i, last;

   234 

   235         if (left >= right) { /* do nothing if vector contains fewer than two */

   236 	    return;		/* two elements */

   237         }

   238         vec.quickSwapElementsAt(left,

   239 				left+(Math.abs(rn.nextInt())%(right-left)+1));

   240         last = left;

   241         for (i = left+1; i <= right; i++) {

   242             if (order == ASCENDING_SORT) {

   243                if (((String)(vec.quickElementAt(i))).compareTo(

   244 				(String)vec.quickElementAt(left)) < 0) {

   245                    vec.quickSwapElementsAt(++last, i);

   246                }

   247             } else {

   248                if (((String)(vec.quickElementAt(i))).compareTo(

   249 				(String)vec.quickElementAt(left)) > 0) {

   250                    vec.quickSwapElementsAt(++last, i);

   251                }

   252             }

   253         }

   254         vec.quickSwapElementsAt(left, last);

   255         quicksort(vec, left, last-1, order);

   256         quicksort(vec, last+1, right, order);

   257     }

   258 

   259     /**

   260      * sort the array of objects.

   261      *

   262      * @param arr - a array of objects

   263      * @param comp - object that implemnts the Compare interface

   264      */

   265     public static void sort(Object arr[], Compare comp) {

   266         if (rn == null)

   267             rn = new Random();

   268         quicksort(arr, 0, arr.length-1, comp);

   269     }

   270 

   271     /**

   272      * sort the array of strings.

   273      *

   274      * @param arr - an array of strings

   275      * @param order - ASCENDING_SORT or DESCENDING_SORT

   276      */

   277     public static void sort(String arr[], int order) {

   278         if (rn == null)

   279             rn = new Random();

   280         quicksort(arr, 0, arr.length-1, order);

   281     }

   282 

   283     /**

   284      * sort the array of strings in ascending order

   285      *

   286      * @param arr - an array of strings

   287      */

   288     public static void sort(String arr[]) {

   289         sort(arr, ASCENDING_SORT);

   290     }

   291 

   292     /**

   293      * sort the vector of objects.

   294      *

   295      * @param vec - a vector of objects

   296      * @param comp - object that implemnts the Compare interface

   297      */

   298     public static void sort(Vector vec, Compare comp) {

   299         if (rn == null)

   300             rn = new Random();

   301         if (vec.size() > MAX_ELEMENTS_FOR_COPY) {

   302             // Would use up too much memory, so have to do an in place sort

   303             quicksort(vec, 0, vec.size()-1, comp);

   304         } else {

   305             // For small vector, optimize the sort by copying to an array

   306             // first

   307             Object[] arr = new Object[vec.size()];

   308             vec.copyInto(arr);

   309             quicksort(arr, 0, arr.length-1, comp);

   310             for (int i = 0; i < arr.length; i++) {

   311                 vec.setElementAt(arr[i], i);

   312             }

   313         }

   314     }

   315 

   316     /**

   317      * sort the vector of strings.

   318      *

   319      * @param vec - a vector of strings

   320      * @param order - ASCENDING_SORT or DESCENDING_SORT

   321      */

   322     public static void sort(Vector vec, int order) {

   323         if (rn == null)

   324             rn = new Random();

   325         if (vec.size() > MAX_ELEMENTS_FOR_COPY) {

   326             // Would use up too much memory, so have to do an in place sort

   327             quicksort(vec, 0, vec.size()-1, order);

   328         } else {

   329             // For small vector, we can optimize the sort by copying to an array

   330             // first

   331             String[] arr = new String[vec.size()];

   332             vec.copyInto(arr);

   333             vec.removeAllElements();

   334             quicksort(arr, 0, arr.length-1, order);

   335             vec.setSize(arr.length);

   336             for (int i = 0; i < arr.length; i++) {

   337                 vec.setElementAt(arr[i], i);

   338             }

   339         }

   340     }

   341 

   342     /**

   343      * sort the vector of strings in ascending order

   344      *

   345      * @param vec - a vector of strings

   346      */

   347     public static void sort(Vector vec) {

   348         sort(vec, ASCENDING_SORT);

   349     }

   350 

   351     /**

   352      * sort the vector of objects.

   353      *

   354      * @param vec - a vector of objects

   355      * @param comp - object that implemnts the Compare interface

   356      */

   357     public static void sort(QuickVector vec, Compare comp) {

   358         if (rn == null)

   359             rn = new Random();

   360         quicksort(vec, 0, vec.size()-1, comp);

   361     }

   362 

   363     /**

   364      * sort the vector of strings.

   365      *

   366      * @param vec - a vector of strings

   367      * @param order - ASCENDING_SORT or DESCENDING_SORT

   368      */

   369     public static void sort(QuickVector vec, int order) {

   370         if (rn == null)

   371             rn = new Random();

   372         quicksort(vec, 0, vec.size()-1, order);

   373     }

   374 

   375     /**

   376      * sort the vector of strings in ascending order

   377      *

   378      * @param vec - a vector of strings

   379      */

   380     public static void sort(QuickVector vec) {

   381         sort(vec, ASCENDING_SORT);

   382     }

   383 

   384 }