PDA

View Full Version : java: what is wrong with my sorting algorithms / comparator / compareTO?




macman2790
Mar 29, 2007, 07:46 PM
I'm having trouble sorting an array of scholarship applicants which are scholar objects in my program. I think my compareTo() is ok, but my comparator, im not so sure about that. The printAllApplicantsByScore() method sorts the scholars by the highest scores, using the compareTo() method which calls getScore() which works when comparing two objects because i already tested it. The printAllApplicantsByName() method prints them out in alphabetical order using the compare method from the Comparator interface and i am very sketchy with my comparator, never really used it until now. Here are my two classes which are scholar and scholarship. The scholarship class contains an array of scholar objects applying for a scholarship. here are the exceptions i get when running the printAllApplicantsByName(), and the printAllApplicantsByScore() methods:


Exception in thread "main" java.lang.NullPointerException
at project2.Scholarship.printAllApplicantsByScore(Scholarship.java:104)
at project2.ScholarShipTester.main(ScholarShipTester.java:37)
Java Result: 1

Exception in thread "main" java.lang.NullPointerException
at project2.Scholarship.compare(Scholarship.java:120)
at project2.Scholarship.printAllApplicantsByName(Scholarship.java:142)
at project2.ScholarShipTester.main(ScholarShipTester.java:36)
Java Result: 1
Heres the scholar class:

package project2;
import java.util.*;
import java.text.DecimalFormat;
/**
*
* @author Kevin
*/
public class Scholar implements Comparable {
// private variables
private String fullName;
private double gradePointAverage;
private int essayScore;
private int creditHours;
private boolean scienceMajor;
private boolean selected;
private double totalScore;
private DecimalFormat fmt;

// constructor for a Scholar object
public Scholar(String myFullName, double myGradePointAverage, int myEssayScore,
int myCreditHours, boolean isScienceMajor){
this.fullName = myFullName;
this.gradePointAverage = myGradePointAverage;
this.essayScore = myEssayScore;
this.creditHours = myCreditHours;
this.scienceMajor = isScienceMajor;

selected = false; // in case selected for a Scholar object is already set to true.

}
// returns a Scholar object's fullname
public String getFullName(){
return fullName;
}
// returns a Scholar object's gpa
public double getGradePointAverage(){
return gradePointAverage;
}
// returns a Scholar object's essay score
public int getEssayScore(){
return essayScore;
}
/// returns a Scholar object's credit hours
public int getCreditHours(){
return creditHours;
}
// retruns if a Scholar object is a science major or not
public boolean getScienceMajor(){
return scienceMajor;
}
// sets a Scholar object's full name
public String setFullName(String fullName){
return fullName;
}
// sets a Scholar object's gpa
public double setGradePointAverage(double a){
gradePointAverage = a;
return gradePointAverage;
}
// sets a Scholar object's gpa
public int setEssayScore(int a){
essayScore = a;
return essayScore;
}
// sets a Scholar object's credit hours
public int setCreditHours(int a){
creditHours = a;
return creditHours;
}
// sets a Scholar's major to a science major or not a science major
public boolean setScienceMajor(boolean a){
scienceMajor = a;
return scienceMajor;
}

// calculates a Scholar object's score
public double getScore(){
totalScore = (gradePointAverage*5) + essayScore;
if (scienceMajor == true)
totalScore += .5;
if (creditHours >= 60 && creditHours <90)
totalScore += .5;
else if (creditHours >= 90)
totalScore += .75;
return totalScore;
}
public String reverseFullName(){
int num = 0;
for (int i = 0; i < fullName.length(); i++){
if (fullName.charAt(i) == ' ')
num = i + 1;
}

String temp;
String temp2;
temp = fullName.substring(0, num);
temp2 = fullName.substring(num);
String fullName2 = (temp2 + ", " + temp);
return fullName2;
}
// compares two scholar objects.
public int compareTo(Object obj){
Scholar otherObj = (Scholar)obj;
double result = getScore() - otherObj.getScore();
if (result > 0)
return 1;
else if (result < 0)
return -1;
return 0;
}
/* public int compareTo(Scholar s){// dont know
String otherReverseFullName = s.getFullName();
if(otherReverseFullName.equals())

}
*/
// returns the highest scoring of two Scholar objects
public static Scholar max(Scholar s1, Scholar s2){
if (s1.getScore() > s2.getScore())
System.out.println(s1.getFullName() + " scored higher than " +
s2.getFullName() + ".\n");
else
System.out.println(s2.getFullName() + " scored higher than " +
s1.getFullName() + ".\n");
return null;
}
// returns the highest of 3 student objects
public static Scholar max(Scholar s1, Scholar s2, Scholar s3){
if (s1.getScore() > s2.getScore() && s1.getScore() > s3.getScore())
System.out.println(s1.getFullName() + " scored the highest" +
" out of all three students.");
else if (s2.getScore() > s1.getScore() && s2.getScore() > s3.getScore())
System.out.println(s2.getFullName() + " scored the highest" +
" out of all three students.");
else if (s3.getScore() > s2.getScore() && s3.getScore() > s1.getScore())
System.out.println(s3.getFullName() + " scored the highest" +
" out of the three students.");
return null;
}
public void setSelection(boolean f){// dont know
selected = f;
}
public boolean isSelected(){
return selected;
}


// toString method for a Scholar object
public String toString(){
// new decimal format used to change the format of the double gradePointAverage.
DecimalFormat fmt = new DecimalFormat("0.###");
return "Student name: " + reverseFullName() + "-" + " Grade Point Average: "
+ fmt.format(gradePointAverage) + ". " + "Essay Score: " + essayScore + "."
+ " Credit Hours: " + creditHours + ". " + " Science major: " +
scienceMajor + ". ";//Scholarship Selection: " + selected + ".";

}

}


Here is the scholarship class:

/*
* Scholarship.java
*
* Created on March 20, 2007, 20071:40 AM
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/

package project2;
import java.util.*;

/**
*
* @author Kevin
*/
public class Scholarship implements Comparator {
private String scholarship;
private double amount;
private int intendedNumberAwarded;
private int actualNumberAwarded;
private Scholar [] scholar;
private int numberApplicants;
public static final int MAX_DEFAULT = 5;

/** Creates a new instance of Scholarship */
public Scholarship(String scholarship, double amount, int number) {
this.scholarship = scholarship;
this.amount = amount;
this.intendedNumberAwarded = number;
this.actualNumberAwarded = 0;

scholar = new Scholar[MAX_DEFAULT];

}

public String getScholarShipName(){
return scholarship;
}
public String getNumApplicants(){// why is this not an int
return String.valueOf(numberApplicants);
}
public double getSingleScholarshipAmount(){
return amount;
}
public int getNumberWinners(){
for(int i = 0; i < scholar.length; i ++){
if(scholar[i]instanceof Scholar && scholar[i].isSelected()==true)
actualNumberAwarded++;
}
actualNumberAwarded -= 1;

return actualNumberAwarded;
}
public double getAmountAwarded(){
amount = amount/getNumberWinners();
/*for(int i = 0; i < scholar.length; i ++){
getNumberWinners();

}
*/
return amount;
}
public boolean addApplicant(Scholar s){

boolean f = false;
for(int i = 0; i < scholar.length; i++){
// or if(scholar[i]!=null]
if(scholar[i] instanceof Scholar) {}
else {
f = true;
scholar[i] = s;

break;
}
}

if(!f){
Scholar[] temp = new Scholar[scholar.length * 2];
int x = 0;
for (int j = 0; j < scholar.length; j++) {
temp[j] = scholar[j];
x = j;
}
temp[x] = s;
scholar = temp;
}

return true;
}
public void printAllApplicantsByScore(){
StringBuffer buf2 = new StringBuffer(
"\nScholarship = " + scholarship +
//" Amount that will be awarded among winners = " + getSingleScholarshipAmount() +
". Number of intended winners = " + intendedNumberAwarded);

buf2.append("\n------------------------------\n");
int min;
Scholar temp;
for (int index =0 ; index < scholar.length; index++)
{
min = index;
for(int scan = index + 1; scan < scholar.length; scan++)
if(scholar[scan].compareTo(scholar[min]) == 0.0)
min = scan;
// swap
temp = scholar[min];
scholar[min] = scholar[index];
scholar[index] = temp;
//if(scholar[index]!=null)

buf2.append ("[" + (index+1) + "]:" + scholar[index] + "\n");
}
System.out.println(buf2);
}
public int compare(Object o1, Object o2) {
Scholar s1 = (Scholar)o1;
Scholar s2 = (Scholar)o2;
int i = 0;
int name = s1.reverseFullName().compareTo(s2.reverseFullName());
return ((name == 0) ? s1.reverseFullName().compareTo(
s2.reverseFullName()) : name);

}



public void printAllApplicantsByName(){
StringBuffer buf2 = new StringBuffer(
"\nScholarship = " + scholarship +
//" Amount that will be awarded among winners = " + getSingleScholarshipAmount() +
". Number of intended winners = " + intendedNumberAwarded);

buf2.append("\n------------------------------\n");

int min;
Scholar temp;
for (int index =0 ; index < scholar.length; index++)
{
min = index;
for(int scan = index + 1; scan < scholar.length; scan++)
if(compare(scholar[scan], scholar[min]) == 0)
min = scan;
// swap
temp = scholar[min];
scholar[min] = scholar[index];
scholar[index] = temp;
//if(scholar[index]!=null)

buf2.append ("[" + (index+1) + "]:" + scholar[index] + "\n");
}
System.out.println(buf2);
}


public String toString(){
amount = amount/getNumberWinners();
System.out.println("The winners are:");
StringBuffer buf = new StringBuffer(
"\nScholarship = " + scholarship + ". Amount Awarded = " + getAmountAwarded() +
". Number of Winners = " + (getNumberWinners() - 1));

buf.append("\n------------------------------\n");
for (int i =0 ; i < scholar.length; i ++)
{
if(scholar[i]!=null && scholar[i].isSelected())
buf.append ("[" + (i+1) + "]:" + scholar[i] + "\n");
}
return buf.toString();
}

}



Sorry for the very long and boring thread, this is just bugging me and i have no idea how i can fix this.

If anyone needs me to clear anything up, i'll be happy to clear things up.

Thanks in advance.



kpua
Mar 30, 2007, 01:04 AM
This should be very easy to fix because Java tells you exactly what's wrong. You've got a null pointer exception which means you're trying to use a "null" value in a way that it's not supposed to. Usually, this is a result of making the false assumption that some parameter or array value or so on will never be null and never checking for it (or preventing it from happening).

This would have been made clear to you by referencing the Java API documentation for the NullPointerException class. It lists practically every situation that may cause a NullPointerException.

cppnerd
Mar 30, 2007, 02:16 AM
I only briefly looked at your code, but you are trying to compare a null object to a Scholar. See your compare method-- You are casting it to a Scholar object without any typechecking. This would've been easier to debug with a simple:
if (!(o1 instanceof Scholar))
[...error..]

and the same for o2. I made a sample file to test and had o1 as my null object.

This takes us to printAllApplicantsByName.
This means that scholar[scan] (line 142) is out of bounds. A quick glance at it appears you should be breaking on scan = scholar.length-2 in my example. I sent it three students. You have a preset size of 5. scholar.length is 5 based on your initializations on lines 24 and 33.

What should you do?
include another class variable:
int numFilled = 0;
When you add an applicant (addApplicant(Scholar s)), end it as

...
}
numFilled++;
return true;
}

Then when you walk through the Scholar[] array, simply walk from your starting point to scholars[numFilled]. This might look like:
(Line 138 in name printing, 103 in score printing)

for (int scan = index+1; scan < numFilled; scan++)

To recap:
- You probably should check before typecasting - your own errors messages can be far more easily traced.

- Your error is coming because scholars.length is the length of an array. Arrays, once initialized, have a set block of memory. This size does not change, regardless of the status of each element. This means since you are allowing up to 5 for your array, scholars.length is 5 no matter what. This code is only valid if you always have all 5 slots (scholars[0] through scholars[4]) initialized with valid Scholar objects. Maintaining another variable is the easiest way to keep track of where you actually WANT to end your search at.

It's late; I hope this makes sense. If not, I'll try to check back to help with any other problems. (And I really hope I typed my code bits correctly!)

Good luck,
Scott

macman2790
Mar 30, 2007, 11:07 PM
I only briefly looked at your code, but you are trying to compare a null object to a Scholar. See your compare method-- You are casting it to a Scholar object without any typechecking. This would've been easier to debug with a simple:
if (!(o1 instanceof Scholar))
[...error..]

and the same for o2. I made a sample file to test and had o1 as my null object.

This takes us to printAllApplicantsByName.
This means that scholar[scan] (line 142) is out of bounds. A quick glance at it appears you should be breaking on scan = scholar.length-2 in my example. I sent it three students. You have a preset size of 5. scholar.length is 5 based on your initializations on lines 24 and 33.

What should you do?
include another class variable:
int numFilled = 0;
When you add an applicant (addApplicant(Scholar s)), end it as

...
}
numFilled++;
return true;
}

Then when you walk through the Scholar[] array, simply walk from your starting point to scholars[numFilled]. This might look like:
(Line 138 in name printing, 103 in score printing)

for (int scan = index+1; scan < numFilled; scan++)

To recap:
- You probably should check before typecasting - your own errors messages can be far more easily traced.

- Your error is coming because scholars.length is the length of an array. Arrays, once initialized, have a set block of memory. This size does not change, regardless of the status of each element. This means since you are allowing up to 5 for your array, scholars.length is 5 no matter what. This code is only valid if you always have all 5 slots (scholars[0] through scholars[4]) initialized with valid Scholar objects. Maintaining another variable is the easiest way to keep track of where you actually WANT to end your search at.

It's late; I hope this makes sense. If not, I'll try to check back to help with any other problems. (And I really hope I typed my code bits correctly!)

Good luck,
Scott
No, it made perfect sense but i still get a nullpointerexception, numfilled i beleive didnt help, i can make an array of more than 5 objects with no problem. I just have trouble sorting them, there has to be something wrong with my algorithms or the compare/compareto method, i also dont know what you meant with the if statement for the compare method. Did you mean do nothing if that happens? Thanks for the help though, im glad someone gave me a good analysis and understanding.

toddburch
Mar 31, 2007, 09:47 AM
Where's ScholarShipTester?

macman2790
Mar 31, 2007, 02:49 PM
Where's ScholarShipTester?

i'll go ahead and post it, thanks for asking.



/*
* ScholarShipTester.java
*
* Created on March 20, 2007, 1:46 AM
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/

package project2;

public class ScholarShipTester {

public static void main(String [] args){

Scholar a = new Scholar("Jane Doe", 2.1, 3, 34, false);
boolean f = true;
boolean b = true;
Scholar john = new Scholar("John Doe", 3.67, 4, 43, b);
System.out.println(kevin.isSelected());// remove
john.setSelection(true);
a.setSelection(true);
System.out.println(john.isSelected());// remove;
//a.setSelection(true);
//john.setSelection(b);
//System.out.println(a);
//System.out.println(a.getScore());
Scholarship s1 = new Scholarship("Presidential", 500.00, 2);
s1.addApplicant(john);
s1.addApplicant(a);
System.out.println(s1);
s1.printAllApplicantsByName();
//s1.printAllApplicantsByScore();
}
}

macman2790
Mar 31, 2007, 05:39 PM
does the nullPointer exception that im getting have to do with the array being set to MAX_DEFAULT, as its default size and the array isnt yet full? How could i get around this problem since its for one of my classes, and it says explicitly by default that the array have that size, so theres real way to get rid of MAX_DEFAULT?

macman2790
Mar 31, 2007, 08:31 PM
heres my new and improved printAllApplicantsByScore() method, finally got it:


public void printAllApplicantsByScore(){
StringBuffer buf2 = new StringBuffer(
"\nScholarship = " + scholarship +
//" Amount that will be awarded among winners = " + getSingleScholarshipAmount() +
". Number of intended winners = " + intendedNumberAwarded);
//Arrays.sort(scholar, Comparator c);
buf2.append("\n------------------------------\n");


//scholar = insertionSort(scholar);
Scholar nullScholar = new Scholar("Jon Smith", 0.0, 0, 0, false);
int min;
Scholar temp;
for (int index =0 ; index < scholar.length; index++)
{
min = index;

for(int scan = index + 1; scan < scholar.length; scan++){
if(scholar[index] == null || scholar[min] == null || scholar[scan] == null)
//scholar[index] = nullScholar;
scholar[scan] = nullScholar;
if(scholar[scan].compareTo(scholar[min]) > 0)
min = scan;
}

// swap
temp = scholar[min];
scholar[min] = scholar[index];
scholar[index] = temp;

if(scholar[index] != nullScholar)
buf2.append ("[" + (index+1) + "]:" + scholar[index].getFullName() +
" scored " + scholar[index].getScore() + "\n");
}
System.out.println(buf2);
}

toddburch
Mar 31, 2007, 11:02 PM
Glad you got it worked out. I'm just now getting to it.

This code is not done yet. The error is if no scholar is ever selected, it will return a negative number. The more times it is called with no scholars selected, the more negative the value will get.

public int getNumberWinners() {
for (int i = 0; i < scholar.length; i++) {
if (scholar[i]instanceof Scholar && scholar[i].isSelected()==true) {
actualNumberAwarded++;
}
}
actualNumberAwarded -= 1;
return actualNumberAwarded;
}


This code is not finished either:

// returns a Scholar object's fullname
public String getFullName(){
return fullName;
}


On your set... methods, it seems illogical to me to return the value you set.
I would use get... for getting the value.

Your Scholorship.toString method is flawed with this logic:

public String toString(){
amount = amount/getNumberWinners();

If you have no winners, you'll get a divide by zero exception, here, and in any method that calls getNumberWinners().

I've review more later.

Todd