Heterogeneous arrays and how to sort them
by Charles Kelemen
Under construction. Extremely crude at present. Check back
in a week.
Here is our challange.
Suppose we are asked to help a college with a small part of its
data processing needs. The college has a file containing
records on students, staff, and faculty. Each record has
fields as follows:
- student fields: name, ID number, graduation year, advisor, dorm
- staff fields: name, ID number, months employed at college
- faculty fields: name, ID number, department, phone extension
Here is a small portion of the file:
<![CDATA[
stu William 183 1999 Kelemen Mertz
stf Don 640 12
stf Bill 643 12
stu Gabriel 180 2002 Kelemen Parrish
fac Kelemen 520 CS 8123
stu Brandon 176 2000 Kelemen ML
]]>
Each record in the file begins with a 3 letter code indicating
whether it is a student(stu), staff(stf), or faculty(fac) record.
The file is in no particular order.
We would like to be able to sort these records in different ways.
For example, we might want them all in ascending order by name for
a phone directory. we might want them in ascending order by
ID number for some other purpose.
We have developed a sort Sort.inssort that can sort
any array of Sortable objects. So our task will be to make our
collection of Student, Faculty, and Staff objects into an
array of Sortable objects with an appropriate precedes methods for
the ordering we desire. We can redefine precedes for different orderings.
Please click on Inheritance in small steps to
develop the use of inheritance in a liesurely manner.
Inheritance in small steps.
You should not proceed until you have worked through the
material on Inheritance in small steps.
Here is the raw file of people we will use. It is called students.txt
even though it contains faculty and staff in addition to students.
<![CDATA[
thyme.cs.swarthmore.edu% less students.txt
29
stu Nii 66 2002 smith Hollowell
fac Pete 567 English 8888
stu Laura 34 2000 Meeden Dana
fac Sue 535 Math 8887
stu Aaron 36 2001 Marshall Wharton
stu Bjorn 41 2001 Kelemen Palmer
stu Kellen 28 2002 Kelemen Pitt
stf Jeff 651 9
stu Timothy 101 2000 Kelemen Palmer
stu Jimmy 103 2001 Kelemen Parrish
stu Joshua 106 2000 Meeden ML
stu YingJie 108 2001 Meeden Parrish
fac Marshall 501 CS 8765
stu Will 113 2000 Kelemen Mertz
stu Benjamin 116 2002 Meeden ML
stu Benjamin 119 2001 Marshall Parrish
stu William 183 1999 Kelemen Mertz
stf Don 640 12
stf Bill 643 12
stu Gabriel 180 2002 Kelemen Parrish
fac Kelemen 520 CS 8123
stu Brandon 176 2000 Kelemen ML
stu Thomas 173 2002 Kelemen Parrish
stu Eugene 170 2001 Meeden Willets
stu Stephanie 168 2002 Marshall ML
stu Jeffrey 165 2001 Kelemen Mertz
stf Joan 677 9
stu Yuhai 164 2001 Kelemen Mertz
fac Meeden 530 CS 8333
]]>
Here are a set of files that let us use our old friend Sort.inssort to
sort the whole database in alphabetical order by name. Person
is the superclass for Student, Staff, and Faculty.
<![CDATA[
thyme.cs.swarthmore.edu% less Person.java
//
// by cfk
//
import java.io.*;
class Person implements Sortable
{
// private data members....
protected String name;
protected int idnum;
// contructors
public Person() {name=""; idnum=0;}
public Person(String n, int id) {
name=new String(n);
idnum=id;}
// public MEMBER FUNCTIONS ...
//comparison
public boolean precedes(Object other) {
return(this.name.compareTo( ((Person) other).name) < 0);
}
// display
public void display() {
System.out.print(" Name: " + name + " ");
System.out.println(" Id: " + idnum);
}
// file input
public void file_in(StreamTokenizer inf) throws IOException {
inf.nextToken(); name = inf.sval;
inf.nextToken(); idnum=(int)inf.nval;
}
}
]]>
Here are the subclasses Student, Staff, and Faculty. They do
not need their own preceds method because for a straight
alphabetical sort by name, the precedes that they inherit
from Person is adequate.
<![CDATA[
thyme.cs.swarthmore.edu% less Student.java
//
// by cfk
import java.io.*;
class Student extends Person
{
// private data members....
private String advisor, dorm;
private int gradyear;
// contructors
public Student() {name=""; gradyear=0;idnum=0;advisor="";dorm="";}
// public MEMBER FUNCTIONS ...
// display
public void display() {
System.out.print(" Name: " + name);
System.out.print(" Id: " + idnum);
System.out.print(" Grad year: " + gradyear);
System.out.print(" Advisor: " + advisor);
System.out.println(" Dorm: " + dorm);
}
// file input
public void file_in(StreamTokenizer inf) throws IOException {
inf.nextToken(); name = inf.sval;
inf.nextToken(); idnum=(int)inf.nval;
inf.nextToken(); gradyear=(int)inf.nval;
inf.nextToken(); advisor = inf.sval;
inf.nextToken(); dorm = inf.sval;
}
}
]]>
<![CDATA[
thyme.cs.swarthmore.edu% less Staff.java
//
// by cfk
import java.io.*;
class Staff extends Person
{
// private data members....
private int months;
// contructors
public Staff() {name=""; idnum=0; months=0;}
// public MEMBER FUNCTIONS ...
// display
public void display() {
System.out.print(" Name: " + name);
System.out.print(" Id: " + idnum);
System.out.println(" Months: " + months);
}
// file input
public void file_in(StreamTokenizer inf) throws IOException {
inf.nextToken(); name = inf.sval;
inf.nextToken(); idnum=(int)inf.nval;
inf.nextToken(); months = (int)inf.nval;
}
}
]]>
<![CDATA[
thyme.cs.swarthmore.edu% less Faculty.java
//
// by cfk
import java.io.*;
class Faculty extends Person
{
// private data members....
private String dept;
private int phone;
// contructors
public Faculty() {name=""; idnum=0; dept=""; phone=0;}
// public MEMBER FUNCTIONS ...
// display
public void display() {
System.out.print(" Name: " + name);
System.out.print(" Id: " + idnum);
System.out.print(" Dept: " + dept);
System.out.println(" Phone: " + phone);
}
// file input
public void file_in(StreamTokenizer inf) throws IOException {
inf.nextToken(); name = inf.sval;
inf.nextToken(); idnum=(int)inf.nval;
inf.nextToken(); dept=inf.sval;
inf.nextToken(); phone= (int)inf.nval;
}
}
]]>
Sort.java and Sortable.java are unchanged from when we sorted MyInts.
Our testing program is Trysubcl.java:
<![CDATA[
thyme.cs.swarthmore.edu% less Trysubcl.java
// A program to help illustrate subclasses
// by cfk
import java.io.*;
class Trysubcl {
public static void main(String argv[]) throws IOException {
FileReader infi=new FileReader("students.txt");
StreamTokenizer infitok = new StreamTokenizer(infi);
infitok.eolIsSignificant(false);
int gyear, numofpeople;
String nm, kindofperson;
Person stu[]; //declare array of objects of class Student2
System.out.println("starting: ");
infitok.nextToken(); numofpeople=(int)infitok.nval;
stu = new Person[numofpeople]; //instantiate array of references
for (int i=0; i<numofpeople; i++) {
infitok.nextToken(); kindofperson=infitok.sval;
if ( kindofperson.equalsIgnoreCase("stu") ) {
stu[i]=new Student();
stu[i].file_in(infitok); // use objects file_in method to initi
alize
}
else if ( kindofperson.equalsIgnoreCase("fac") ) {
stu[i]=new Faculty();
stu[i].file_in(infitok); // use objects file_in method to initi
alize
}
if ( kindofperson.equalsIgnoreCase("stf") ) {
stu[i]=new Staff();
stu[i].file_in(infitok); // use objects file_in method to initi
alize
}
}
System.out.println("have read in people");
for (int k=0; k<numofpeople; k++) stu[k].display();
Sort.inssort(stu, numofpeople); // call class sort method of Person
System.out.println("after sorting people");
for (int k=0; k<numofpeople; k++) stu[k].display();
}
}
]]>
Putting these files in the same directory with students.txt and
compiling and running Trysubcl.java leads to:
<![CDATA[
thyme.cs.swarthmore.edu% java Trysubcl
starting:
have read in people
Name: Nii Id: 66 Grad year: 2002 Advisor: smith Dorm: Hollowell
Name: Pete Id: 567 Dept: English Phone: 8888
Name: Laura Id: 34 Grad year: 2000 Advisor: Meeden Dorm: Dana
Name: Sue Id: 535 Dept: Math Phone: 8887
Name: Aaron Id: 36 Grad year: 2001 Advisor: Marshall Dorm: Wharton
Name: Bjorn Id: 41 Grad year: 2001 Advisor: Kelemen Dorm: Palmer
Name: Kellen Id: 28 Grad year: 2002 Advisor: Kelemen Dorm: Pitt
Name: Jeff Id: 651 Months: 9
Name: Timothy Id: 101 Grad year: 2000 Advisor: Kelemen Dorm: Palmer
Name: Jimmy Id: 103 Grad year: 2001 Advisor: Kelemen Dorm: Parrish
Name: Joshua Id: 106 Grad year: 2000 Advisor: Meeden Dorm: ML
Name: YingJie Id: 108 Grad year: 2001 Advisor: Meeden Dorm: Parrish
Name: Marshall Id: 501 Dept: CS Phone: 8765
Name: Will Id: 113 Grad year: 2000 Advisor: Kelemen Dorm: Mertz
Name: Benjamin Id: 116 Grad year: 2002 Advisor: Meeden Dorm: ML
Name: Benjamin Id: 119 Grad year: 2001 Advisor: Marshall Dorm: Parrish
Name: William Id: 183 Grad year: 1999 Advisor: Kelemen Dorm: Mertz
Name: Don Id: 640 Months: 12
Name: Bill Id: 643 Months: 12
Name: Gabriel Id: 180 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Kelemen Id: 520 Dept: CS Phone: 8123
Name: Brandon Id: 176 Grad year: 2000 Advisor: Kelemen Dorm: ML
Name: Thomas Id: 173 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Eugene Id: 170 Grad year: 2001 Advisor: Meeden Dorm: Willets
Name: Stephanie Id: 168 Grad year: 2002 Advisor: Marshall Dorm: ML
Name: Jeffrey Id: 165 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Joan Id: 677 Months: 9
Name: Yuhai Id: 164 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Meeden Id: 530 Dept: CS Phone: 8333
after sorting people
Name: Aaron Id: 36 Grad year: 2001 Advisor: Marshall Dorm: Wharton
Name: Benjamin Id: 116 Grad year: 2002 Advisor: Meeden Dorm: ML
Name: Benjamin Id: 119 Grad year: 2001 Advisor: Marshall Dorm: Parrish
Name: Bill Id: 643 Months: 12
Name: Bjorn Id: 41 Grad year: 2001 Advisor: Kelemen Dorm: Palmer
Name: Brandon Id: 176 Grad year: 2000 Advisor: Kelemen Dorm: ML
Name: Don Id: 640 Months: 12
Name: Eugene Id: 170 Grad year: 2001 Advisor: Meeden Dorm: Willets
Name: Gabriel Id: 180 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Jeff Id: 651 Months: 9
Name: Jeffrey Id: 165 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Jimmy Id: 103 Grad year: 2001 Advisor: Kelemen Dorm: Parrish
Name: Joan Id: 677 Months: 9
Name: Joshua Id: 106 Grad year: 2000 Advisor: Meeden Dorm: ML
Name: Kelemen Id: 520 Dept: CS Phone: 8123
Name: Kellen Id: 28 Grad year: 2002 Advisor: Kelemen Dorm: Pitt
Name: Laura Id: 34 Grad year: 2000 Advisor: Meeden Dorm: Dana
Name: Marshall Id: 501 Dept: CS Phone: 8765
Name: Meeden Id: 530 Dept: CS Phone: 8333
Name: Nii Id: 66 Grad year: 2002 Advisor: smith Dorm: Hollowell
Name: Pete Id: 567 Dept: English Phone: 8888
Name: Stephanie Id: 168 Grad year: 2002 Advisor: Marshall Dorm: ML
Name: Sue Id: 535 Dept: Math Phone: 8887
Name: Thomas Id: 173 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Timothy Id: 101 Grad year: 2000 Advisor: Kelemen Dorm: Palmer
Name: Will Id: 113 Grad year: 2000 Advisor: Kelemen Dorm: Mertz
Name: William Id: 183 Grad year: 1999 Advisor: Kelemen Dorm: Mertz
Name: YingJie Id: 108 Grad year: 2001 Advisor: Meeden Dorm: Parrish
Name: Yuhai Id: 164 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
thyme.cs.swarthmore.edu%
]]>
Here is an example of an ordering achieved without any changes to the
sort program. By clever definition of precedes, this puts all staff
first (ordered alphbetically by name within Staff). Students come
next. Within students, they are ordered by graduation year, and
with in graduation year, students are ordered by name. Faculty
come last (alas) order by name.
<![CDATA[
starting:
have read in people
Name: Nii Id: 66 Grad year: 2002 Advisor: smith Dorm: Hollowell
Name: Pete Id: 567 Dept: English Phone: 8888
Name: Laura Id: 34 Grad year: 2000 Advisor: Meeden Dorm: Dana
Name: Sue Id: 535 Dept: Math Phone: 8887
Name: Aaron Id: 36 Grad year: 2001 Advisor: Marshall Dorm: Wharton
Name: Bjorn Id: 41 Grad year: 2001 Advisor: Kelemen Dorm: Palmer
Name: Kellen Id: 28 Grad year: 2002 Advisor: Kelemen Dorm: Pitt
Name: Jeff Id: 651 Months: 9
Name: Timothy Id: 101 Grad year: 2000 Advisor: Kelemen Dorm: Palmer
Name: Jimmy Id: 103 Grad year: 2001 Advisor: Kelemen Dorm: Parrish
Name: Joshua Id: 106 Grad year: 2000 Advisor: Meeden Dorm: ML
Name: YingJie Id: 108 Grad year: 2001 Advisor: Meeden Dorm: Parrish
Name: Marshall Id: 501 Dept: CS Phone: 8765
Name: Will Id: 113 Grad year: 2000 Advisor: Kelemen Dorm: Mertz
Name: Benjamin Id: 116 Grad year: 2002 Advisor: Meeden Dorm: ML
Name: Benjamin Id: 119 Grad year: 2001 Advisor: Marshall Dorm: Parrish
Name: William Id: 183 Grad year: 1999 Advisor: Kelemen Dorm: Mertz
Name: Don Id: 640 Months: 12
Name: Bill Id: 643 Months: 12
Name: Gabriel Id: 180 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Kelemen Id: 520 Dept: CS Phone: 8123
Name: Brandon Id: 176 Grad year: 2000 Advisor: Kelemen Dorm: ML
Name: Thomas Id: 173 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Eugene Id: 170 Grad year: 2001 Advisor: Meeden Dorm: Willets
Name: Stephanie Id: 168 Grad year: 2002 Advisor: Marshall Dorm: ML
Name: Jeffrey Id: 165 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Joan Id: 677 Months: 9
Name: Yuhai Id: 164 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Meeden Id: 530 Dept: CS Phone: 8333
after sorting people
Name: Bill Id: 643 Months: 12
Name: Don Id: 640 Months: 12
Name: Jeff Id: 651 Months: 9
Name: Joan Id: 677 Months: 9
Name: William Id: 183 Grad year: 1999 Advisor: Kelemen Dorm: Mertz
Name: Brandon Id: 176 Grad year: 2000 Advisor: Kelemen Dorm: ML
Name: Joshua Id: 106 Grad year: 2000 Advisor: Meeden Dorm: ML
Name: Laura Id: 34 Grad year: 2000 Advisor: Meeden Dorm: Dana
Name: Timothy Id: 101 Grad year: 2000 Advisor: Kelemen Dorm: Palmer
Name: Will Id: 113 Grad year: 2000 Advisor: Kelemen Dorm: Mertz
Name: Aaron Id: 36 Grad year: 2001 Advisor: Marshall Dorm: Wharton
Name: Benjamin Id: 119 Grad year: 2001 Advisor: Marshall Dorm: Parrish
Name: Bjorn Id: 41 Grad year: 2001 Advisor: Kelemen Dorm: Palmer
Name: Eugene Id: 170 Grad year: 2001 Advisor: Meeden Dorm: Willets
Name: Jeffrey Id: 165 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Jimmy Id: 103 Grad year: 2001 Advisor: Kelemen Dorm: Parrish
Name: YingJie Id: 108 Grad year: 2001 Advisor: Meeden Dorm: Parrish
Name: Yuhai Id: 164 Grad year: 2001 Advisor: Kelemen Dorm: Mertz
Name: Benjamin Id: 116 Grad year: 2002 Advisor: Meeden Dorm: ML
Name: Gabriel Id: 180 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Kellen Id: 28 Grad year: 2002 Advisor: Kelemen Dorm: Pitt
Name: Nii Id: 66 Grad year: 2002 Advisor: smith Dorm: Hollowell
Name: Stephanie Id: 168 Grad year: 2002 Advisor: Marshall Dorm: ML
Name: Thomas Id: 173 Grad year: 2002 Advisor: Kelemen Dorm: Parrish
Name: Kelemen Id: 520 Dept: CS Phone: 8123
Name: Marshall Id: 501 Dept: CS Phone: 8765
Name: Meeden Id: 530 Dept: CS Phone: 8333
Name: Pete Id: 567 Dept: English Phone: 8888
Name: Sue Id: 535 Dept: Math Phone: 8887
thyme.cs.swarthmore.edu%
]]>