Sorter


1   /*******************************************************************************
2    * Copyright (c) 2002, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.ui.internal.cheatsheets.registry;
12  
13  /**
14   *  The SortOperation takes a collection of objects and returns
15   *  a sorted collection of these objects.  Concrete instances of this
16   *  class provide the criteria for the sorting of the objects based on
17   *  the type of the objects.
18   */
19  public abstract class Sorter {
20      /**
21       *  Returns true if elementTwo is 'greater than' elementOne
22       *  This is the 'ordering' method of the sort operation.
23       *  Each subclass overides this method with the particular
24       *  implementation of the 'greater than' concept for the 
25       *  objects being sorted.
26       */
27      /*package*/ abstract boolean compare(Object   elementOne, Object   elementTwo);
28  
29      /**
30       *  Sort the objects in sorted collection and return that collection.
31       */
32      private Object  [] quickSort(Object  [] sortedCollection, int left, int right) {
33          int originalLeft = left;
34          int originalRight = right;
35          Object   mid = sortedCollection[(left + right) / 2];
36  
37          do {
38              while (compare(sortedCollection[left], mid))
39                  left++;
40              while (compare(mid, sortedCollection[right]))
41                  right--;
42              if (left <= right) {
43                  Object   tmp = sortedCollection[left];
44                  sortedCollection[left] = sortedCollection[right];
45                  sortedCollection[right] = tmp;
46                  left++;
47                  right--;
48              }
49          }
50          while (left <= right);
51  
52          if (originalLeft < right)
53              sortedCollection = quickSort(sortedCollection, originalLeft, right);
54          if (left < originalRight)
55              sortedCollection = quickSort(sortedCollection, left, originalRight);
56  
57          return sortedCollection;
58      }
59  
60      /**
61       *  Return a new sorted collection from this unsorted collection.
62       *  Sort using quick sort.
63       */
64      /*package*/ Object  [] sort(Object  [] unSortedCollection) {
65          int size = unSortedCollection.length;
66          Object  [] sortedCollection = new Object  [size];
67  
68          //copy the array so can return a new sorted collection  
69          System.arraycopy(unSortedCollection, 0, sortedCollection, 0, size);
70          if (size > 1)
71              quickSort(sortedCollection, 0, size - 1);
72  
73          return sortedCollection;
74      }
75  }
76
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags