Sorter


1   /*******************************************************************************
2    * Copyright (c) 2000, 2004 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials 
4    * are made available under the terms of the Common Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/cpl-v10.html
7    * 
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.team.internal.core;
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 is 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      public abstract boolean compare(Object   elementOne, Object   elementTwo);
28      /**
29       * Sort the objects in sorted collection and return that collection.
30       */
31      private Object  [] quickSort(Object  [] sortedCollection, int left, int right) {
32          int originalLeft = left;
33          int originalRight = right;
34          Object   mid = sortedCollection[ (left + right) / 2];
35          do {
36              while (compare(sortedCollection[left], mid))
37                  left++;
38              while (compare(mid, sortedCollection[right]))
39                  right--;
40              if (left <= right) {
41                  Object   tmp = sortedCollection[left];
42                  sortedCollection[left] = sortedCollection[right];
43                  sortedCollection[right] = tmp;
44                  left++;
45                  right--;
46              }
47          } while (left <= right);
48          if (originalLeft < right)
49              sortedCollection = quickSort(sortedCollection, originalLeft, right);
50          if (left < originalRight)
51              sortedCollection = quickSort(sortedCollection, left, originalRight);
52          return sortedCollection;
53      }
54      /**
55       * Return a new sorted collection from this unsorted collection.
56       * Sort using quick sort.
57       */
58      public Object  [] sort(Object  [] unSortedCollection) {
59          int size = unSortedCollection.length;
60          Object  [] sortedCollection = new Object  [size];
61          //copy the array so can return a new sorted collection  
62          System.arraycopy(unSortedCollection, 0, sortedCollection, 0, size);
63          if (size > 1)
64              quickSort(sortedCollection, 0, size - 1);
65          return sortedCollection;
66      }
67  }
68
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags