001: //** Copyright Statement ***************************************************
002: //The Salmon Open Framework for Internet Applications (SOFIA)
003: // Copyright (C) 1999 - 2002, Salmon LLC
004: //
005: // This program is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU General Public License version 2
007: // as published by the Free Software Foundation;
008: //
009: // This program is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU General Public License
015: // along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: //
018: // For more information please visit http://www.salmonllc.com
019: //** End Copyright Statement ***************************************************
020: package com.salmonllc.util;
021:
022: /**
023: * This utility class extends a java.util.Vector by implementing a method that can sort the vector. You must subclass it and implement the compare method. The compare method must have specific knowledge of the types of components on the vector and determine if one object is greater then another.
024: */
025: public abstract class VectorSort extends java.util.Vector {
026: /**
027: * Constructs an empty vector.
028: *
029: * @since JDK1.0
030: */
031: public VectorSort() {
032: super ();
033: }
034:
035: /**
036: * Constructs an empty vector with the specified initial capacity.
037: *
038: * @param initialCapacity the initial capacity of the vector.
039: * @since JDK1.0
040: */
041: public VectorSort(int initialCapacity) {
042: super (initialCapacity);
043: }
044:
045: /**
046: * Constructs an empty vector with the specified initial capacity and
047: * capacity increment.
048: *
049: * @param initialCapacity the initial capacity of the vector.
050: * @param capacityIncrement the amount by which the capacity is
051: * increased when the vector overflows.
052: * @since JDK1.0
053: */
054: public VectorSort(int initialCapacity, int capacityIncrement) {
055: super (initialCapacity, capacityIncrement);
056: }
057:
058: /**
059: * The compare method is passed two objects from the vector and must return true if Object2 is greater then Object1 for an ascending sort or true if Object2 is less then Object1 for a descending sort.
060: * @param o1 The first object to compare
061: * @param o2 The second object to compare
062: */
063: public abstract boolean compare(Object o1, Object o2);
064:
065: private int divide(int low, int high) {
066: int i, ptr;
067:
068: Object key = elementAt(low);
069: ptr = low;
070:
071: for (i = low + 1; i <= high; i++) {
072: if (compare(elementAt(i), key))
073: swap(++ptr, i);
074: }
075: swap(low, ptr);
076: return ptr;
077: }
078:
079: /**
080: * Sorts the Vector
081: */
082: public void sort() {
083: sort(0, size() - 1);
084: }
085:
086: private void sort(int low, int high) {
087: int ptr;
088:
089: if (low < high) {
090: ptr = divide(low, high);
091: sort(low, ptr - 1);
092: sort(ptr + 1, high);
093: }
094: }
095:
096: private void swap(int a, int b) {
097: Object tmp = elementAt(a);
098: setElementAt(elementAt(b), a);
099: setElementAt(tmp, b);
100: }
101: }
|