[416] in java-interest
SortedVector class
daemon@ATHENA.MIT.EDU (Shaun Terry)
Tue Jun 20 18:28:56 1995
Date: Tue, 20 Jun 95 18:04:07 EDT
From: shaun@calcdev.ml.com (Shaun Terry)
To: java-interest@java.Eng.Sun.COM
Here's a sorted vector class I wrote which some may find handy since I didn't
come across anything in the current packages which did sorting.
SPT
import java.util.Vector;
import java.util.Enumeration;
import java.lang.Exception;
public interface Sortable {
/**
* Compare value of object to s
* @return a number less than zero if the value of the object is
* less than s, 0 if equal or a number greater
* than 0 if greater than s
*/
int compareTo(Sortable s);
}
public class ObjectNotSortable extends Exception {
ObjectNotSortable() { super(); }
}
/**
* An extension of the Vector class which maintains its members in sorted
* order. Members of the vector must implement the Sortable interface.
*
* Example:
* <pre>
* class Val implements Sortable {
* public int v;
* public Val(int x) { v = x; }
* public int compareTo(Sortable s) {
* if (v < ((Val) s).v) return (-1);
* else if (v > ((Val) s).v) return 1;
* else return 0;
* }
* }
*
* Vector v = new Vector();
* v.addElement(new Val(9));
* v.addElement(new Val(7));
* v.addElement(new Val(2));
* SortedVector sv = new SortedVector(v);
* for (int i=0; i < sv.size(); ++i) {
* System.out.println(((Val) sv.elementAt(i)).v);
* }
*
* prints 2
* 7
* 9
* </pre>
*
* @author Shaun Terry
*/
public class SortedVector extends Vector {
// Your basic quicksort
void sort(int l, int r) {
int i, j;
Sortable v;
if (r > l) {
v = (Sortable) elementAt(r);
i = l-1; j = r;
while (true) {
while (i<r && ((Sortable) elementAt(++i)).compareTo(v) < 0);
while (j>l && ((Sortable) elementAt(--j)).compareTo(v) > 0);
if (i >= j) break;
Object T = elementAt(i);
setElementAt(elementAt(j), i);
setElementAt(T, j);
}
Object T = elementAt(i);
setElementAt(elementAt(r), i);
setElementAt(T, r);
sort(l, i-1);
sort(i+1, r);
}
}
/**
* Sort the existing vector. Items added through this class's methods
* should always be in sort order, however, the vector will need to be
* explicitly sorted if items are added through the parent class's methods.
* Being able to add items in unsorted order can be useful if you want to
* add a lot of them at once, saving the sorting for last.
*/
public synchronized void sort() { sort(0, size()-1); }
/** Copy (deep) a vector and sort it */
public SortedVector(Vector v) {
for (Enumeration e = v.elements(); e.hasMoreElements();) {
Object o = e.nextElement();
if (!(o instanceof Sortable)) throw new ObjectNotSortable();
addElement(e.nextElement());
}
sort();
}
/** Add an element to the vector and re-sort */
public void newElement(Sortable s) {
addElement(s);
sort();
}
}
-
Note to Sun employees: this is an EXTERNAL mailing list!
Info: send 'help' to java-interest-request@java.sun.com
