001: /*
002: * Copyright 2001-2007 Geert Bevin <gbevin[remove] at uwyn dot com>
003: * Distributed under the terms of either:
004: * - the common development and distribution license (CDDL), v1.0; or
005: * - the GNU Lesser General Public License, v2.1 or later
006: * $Id: Sort.java 3634 2007-01-08 21:42:24Z gbevin $
007: */
008: package com.uwyn.rife.tools;
009:
010: /**
011: * Generic class that implements the quicksort algorithm. Extending classes
012: * have to implement the abstract methods so that the sorting algorithm can
013: * perform the appropriate modifications to the extending class's
014: * datastructure.
015: *
016: * @author Geert Bevin (gbevin[remove] at uwyn dot com)
017: * @version $Revision: 3634 $
018: * @since 1.0
019: */
020: public abstract class Sort {
021: /**
022: * Starts the sorting of the provided datastructure.
023: *
024: * @param dataToSort An <code>Object</code> instance that points to the
025: * datastructure that has to be sorted. The extending class should know how
026: * to manipulate this particular datastructure.
027: * @param lastElementPosition An integer that specifies the position of the
028: * last element in the provided datastructure.
029: * @param ascending true of the data has to be sorted in an ascending
030: * fashion and false otherwise
031: *
032: * @since 1.0
033: */
034: public final void sort(Object dataToSort, int lastElementPosition,
035: boolean ascending) {
036: if (null == dataToSort)
037: throw new IllegalArgumentException(
038: "dataToSort can't be null");
039: if (lastElementPosition < 0)
040: throw new IllegalArgumentException(
041: "lastElementPosition has to be bigger than 0.");
042:
043: quickSort(dataToSort, 0, lastElementPosition, ascending);
044: }
045:
046: /**
047: * This method contains the actual sorting algorithm.
048: *
049: * @param dataToSort An <code>Object</code> instance that points to the
050: * datastructure that has to be sorted.
051: * @param lo0 An integer indicating the bottom boundary of the range that
052: * will be sorted.
053: * @param hi0 An integer indicating the upper boundary of the range that
054: * will be sorted.
055: * @param ascending true of the data has to be sorted in an ascending
056: * fashion and false otherwise
057: *
058: * @since 1.0
059: */
060: protected final void quickSort(Object dataToSort, int lo0, int hi0,
061: boolean ascending) {
062: int lo = lo0;
063: int hi = hi0;
064:
065: if (hi0 > lo0) {
066: Object mid_element = elementAt(dataToSort, (lo0 + hi0) / 2);
067:
068: while (lo <= hi) {
069: if (ascending) {
070: while ((lo < hi0)
071: && compare(elementAt(dataToSort, lo),
072: mid_element) < 0) {
073: lo++;
074: }
075: while ((hi > lo0)
076: && compare(elementAt(dataToSort, hi),
077: mid_element) > 0) {
078: hi--;
079: }
080: } else {
081: while ((lo < hi0)
082: && compare(elementAt(dataToSort, lo),
083: mid_element) > 0) {
084: lo++;
085: }
086: while ((hi > lo0)
087: && compare(elementAt(dataToSort, hi),
088: mid_element) < 0) {
089: hi--;
090: }
091: }
092:
093: if (lo <= hi) {
094: swap(dataToSort, lo, hi);
095: lo++;
096: hi--;
097: }
098: }
099:
100: if (lo0 < hi) {
101: quickSort(dataToSort, lo0, hi, ascending);
102: }
103:
104: if (lo < hi0) {
105: quickSort(dataToSort, lo, hi0, ascending);
106: }
107: }
108: }
109:
110: /**
111: * Swaps the position of two entries in the provided datastructure. This is
112: * an abstract method that needs to be implemented by every extending class.
113: *
114: * @param dataToSort An <code>Object</code> instance that points to the
115: * datastructure in which the entries have to be swapped.
116: * @param position1 An integer with the position of the first entry.
117: * @param position2 An integer with the position of the second entry.
118: *
119: * @since 1.0
120: */
121: protected abstract void swap(Object dataToSort, int position1,
122: int position2);
123:
124: /**
125: * Retrieves an entry from a certain position within the specified
126: * datastructure.
127: *
128: * @param dataToSort An <code>Object</code> instance that points to the
129: * datastructure from where the entry has to be retrieved.
130: * @param position An integer with the position of the entry that has to be
131: * retrieved.
132: *
133: * @return An <code>Object</code> instace containing the entry at the
134: * specified position.
135: *
136: * @since 1.0
137: */
138: protected abstract Object elementAt(Object dataToSort, int position);
139:
140: /**
141: * Compares the entries, determining which one comes before the other.
142: *
143: * @param element1 An <code>Object</code> instance containing the first
144: * entry.
145: * @param element2 An <code>Object</code> instance containing the second
146: * entry.
147: *
148: * @return <code>0</code> if the two entries are equals; or
149: * <p>
150: * an integer <code><0</code> if the first entry comes before the second
151: * one; or
152: * <p>
153: * an integer <code>>0</code> if the first entry comes after the second
154: * one
155: *
156: * @since 1.0
157: */
158: protected abstract int compare(Object element1, Object element2);
159: }
|