Thread: Every Input File I Use Returns "Unsorted"

1. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0

Java Code:
public int compareTo(Polynomial arg) {

if (coef.length != arg.coef.length) {
return arg.coef.length - coef.length;
}

for (int i = coef.length - 1; i >= 0; i--) {
if (coef[i] != arg.coef[i]) {
return arg.coef[i] - coef[i];
}
}

return 0;

}
.

Obviously something is screwy. I threw some println's in the compareTo() method and got the following returns:

Java Code:
Polynomial constructor using: 7 0
coef array set to [7]
deg set to 0
p2 set to 7
(using line=7 0)
Polynomial constructor using: 4 1
coef array set to [0, 4]
deg set to 1
p2 set to 4x
(using line=4 1)
Comparing 7
to 4x
Coef length is: 1
Arg coef length is: 2
p1.compareTo(p2)> 0 is true
Coef length is: 1
Arg coef length is: 2
File is not sorted.
I believe the problem has something to do with the lengths of the two arrays since both of them remain the same values throughout the iterations. Is this the correct line of thinking?
Last edited by Cod; 02-27-2011 at 04:41 AM.

2. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
So I changed the the statements that had "!=" to ">" and got all the way down the line...I think. Here's the output:

Java Code:
Polynomial constructor using: 7 0
coef array set to [7]
deg set to 0
p2 set to 7
(using line=7 0)
Polynomial constructor using: 4 1
coef array set to [0, 4]
deg set to 1
p2 set to 4x
(using line=4 1)
Comparing 7
to 4x
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 1 6 5 2 6 1
coef array set to [0, 6, 5, 0, 0, 0, 1]
deg set to 6
p2 set to 1x^6 + 5x^2 + 6x
(using line=1 6 5 2 6 1)
Comparing 4x
to 1x^6 + 5x^2 + 6x
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 1 6 5 2 6 1 4 0
coef array set to [4, 6, 5, 0, 0, 0, 1]
deg set to 6
p2 set to 1x^6 + 5x^2 + 6x + 4
(using line=1 6 5 2 6 1 4 0)
Comparing 1x^6 + 5x^2 + 6x
to 1x^6 + 5x^2 + 6x + 4
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 5 1 2 0
coef array set to [2, 5]
deg set to 1
p2 set to 5x
(using line=5 1 2 0)
Polynomial constructor using: 2 3 3 1
coef array set to [0, 3, 0, 2]
deg set to 3
p2 set to 2x^3 + 3x
(using line=2 3 3 1)
Comparing 5x
to 2x^3 + 3x
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 3 3 1 2 2 0
coef array set to [2, 0, 1, 3]
deg set to 3
p2 set to 3x^3 + 1x^2 + 2
(using line=3 3 1 2 2 0)
Comparing 2x^3 + 3x
to 3x^3 + 1x^2 + 2
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 1 6 5 2 6 1
coef array set to [0, 6, 5, 0, 0, 0, 1]
deg set to 6
p2 set to 1x^6 + 5x^2 + 6x
(using line=1 6 5 2 6 1)
Comparing 3x^3 + 1x^2 + 2
to 1x^6 + 5x^2 + 6x
p1.compareTo(p2)> 0 is false
Polynomial constructor using: 3 8 1 4 1 2
coef array set to [0, 0, 1, 0, 1, 0, 0, 0, 3]
deg set to 8
p2 set to 3x^8 + 1x^4 + 1x^2
(using line=3 8 1 4 1 2)
Comparing 1x^6 + 5x^2 + 6x
to 3x^8 + 1x^4 + 1x^2
p1.compareTo(p2)> 0 is false
Last edited by Cod; 02-27-2011 at 04:46 AM.

3. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
It seems I'm 98% of the way done, a lot of thanks to you pbrockway2.

The only issue is, I'm getting no ouput when I remove the debugging lines and no output to a file. Where would I implement these lines? In the main method? Also, I'm not sure hat method to call in order to print the output and write to a file.
Last edited by Cod; 02-27-2011 at 04:53 AM.

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Seeing what the array lengths were was exactly the right thing to do.

The array lengths are different (1 and 2). So won't the return value come from this bit

Java Code:
if (coef.length != arg.coef.length) {
return arg.coef.length - coef.length;
}

Now you are comparing 7 to 4x. (note the order!) and you want the result "smaller" ie you should be returning a negative number as per the API docs. But the way you have the subtraction set up you will returning 2-1=1. You should be returning 1-2=-1. That's what I meant about the subtraction being backwards.

Check the other subtraction as well.

5. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
So I changed the the statements that had "!=" to ">" and got all the way down the line...

No! Don't change things at random to see what happens or you'll be the mercy of your data files.

If the degrees are different (ie use !=) you want the one with the bigger degree to be bigger: so do the subtraction the right way round to ensure that.

6. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
I didn't change at random. Based on how I understand the link you gave, I realized it should be ">".

I've come across another issue though. How do I ensure the polynomials come out in order? As it stands, the program outputs this:

Java Code:
7
4x
1x^6 + 5x^2 + 6x
1x^6 + 5x^2 + 6x + 4
5x
2x^3 + 3x
3x^3 + 1x^2 + 2
1x^6 + 5x^2 + 6x
3x^8 + 1x^4 + 1x^2

7. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
I didn't change at random. Based on how I understand the link you gave, I realized it should be ">".

Fair enough.

How do I ensure the polynomials come out in order?

I don't see where you are outputting the polynomials.

If it were me I would add them to a collection (say an ArrayList) as I was checking them for being ordered.

Java Code:
public class Project1 {
[b]private static List<Polynomial> fullList = new ArrayList<Polynomial>();[/b]

[i]// main() etc as before[/i]

Polynomial p1 = null;
Polynomial p2 = null;
String line = null;

while ((line = fileName.readLine()) != null) {
p2 = new Polynomial(line);

if (p1 != null) {
[i]// etc[/i]

Then at the end of main() it would be very easy to say

Java Code:
Collections.sort(fullList);
for(Polynomial p :fullList) {
System.out.println(p);
}

(you have to import Collections List and ArrayList of course)

The beauty of this is that your compareTo() - which you're sure is correct - is made to all the hard work of sorting.

It may be that using the collection classes is not allowed if this is homework. In that case you will have to sort them "by hand" bearing in mind that they are already in two groups each individually sorted. Think of two piles of plates going from small (at the top) to bottom and consider how you would efficiently combine them into one stack.
Last edited by pbrockway2; 02-27-2011 at 05:16 AM.

8. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
I can't seem to get the list to print correctly. I tried your method and what I thought was correct; however, the IDE keeps telling me "cannot find symbol" for variable orderedList.

9. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Well the compiler won't lie! If orderedList cannot be found it either hasn't been declared or has been declared in the wrong place. Post the Project1 class (I'm guessing the variable was used somewjere in there).

10. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
Java Code:
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Project1 {

public static void main(final String[] args) throws FileUnsorted, IOException {

Scanner scanner = new Scanner(System.in);
String inputFile1;
String inputFile2;

System.out.println("Enter the first file name: ");
inputFile1 = scanner.nextLine();

System.out.println("Enter second file name: ");
inputFile2 = scanner.nextLine();

try {

checkSorted(file1);
checkSorted(file2);
}

catch (FileUnsorted ex) {
System.exit(1);
}

Collections.sort(orderedList);
for (Polynomial p : orderedList) {
System.out.println(p);
}

}

Polynomial p1 = null;
Polynomial p2 = null;
String line = null;
ArrayList orderedList = new ArrayList();

while ((line = fileName.readLine()) != null) {
p2 = new Polynomial(line);

if (p1 != null) {
if (p1.compareTo(p2) > 0) {
throw new FileUnsorted();
}
}
p1 = p2;

}
}

}
I'm pretty sure you're right, I probably screwed up. I've tried a number of different avenues to call the variable from the checkSorted method, but to no avail.

11. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
You didn't declare orderedList anywhere. It has to be a static member because you populate it in one method and sort and print it in another.

Java Code:
[i]// imports here[/i]
public class Project1 {
[b]private static ArrayList<Polynomial> orderedList = new ArrayList<Polynomial>();[/b]

public static void main(final String[] args) throws FileUnsorted, IOException {
[i]// etc[/i]

12. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
Well, I implemented the static declaration; however, the sort doesn't seem to be working correctly. I'm getting the same output as before. The first file in order then the second file in order. They won't merge for some reason.

13. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Oh! I see. Remove this bit

Java Code:
ArrayList orderedList = new ArrayList();

from the checkSorted() method.

This is another case where the local declaraton of a variable is hiding the class variable of the same name. Similar to what we saw in the constructor where the Polynomial's deg was staying at zero because the constructor had its own deg thereby screwing up the toString().

In this case (as I think I said above somewhere) we want orderedList to be a static variable because it is populated in one place and sorted and printed in another.

As a general rule try to keep variable names distinct. (Exceptions exist, of course. It would be a pain if we couldn't reuse "count" for counts, "ndx" for indices etc. But for the "important" ones like orderedList just declare it once.)

14. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
And ask if you can't decode the meaning of all the bits of the proper declaration:

Java Code:
private static ArrayList<Polynomial> orderedList = new ArrayList<Polynomial>();

All 9(?) of them... ;)

15. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
And another thing: as you had it before the printing at the end of main() would have produced no output. So check that you are seeing output from the right place.

16. Member
Join Date
Nov 2009
Location
Honolulu, HI
Posts
59
Rep Power
0
I've adjusted everything and I'm still getting the output of the first file sorted then the second file sorted. I feel like collections.sort() is sorted the first file when its ran through the checkSorted() method then it moves on to the second file. What gives? My thinking was, from reading the Oracle page, collections.sort() should have waited until the array was completely "built" then sorted.
Last edited by Cod; 02-27-2011 at 06:53 AM.

17. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
sort() sorts at the time you call it.

Are you sure you are seeing one file sorted and then the other? And not

Java Code:
7
1x^6 + 5x^2 + 6x + 4
1x^6 + 5x^2 + 6x
5x + 2               <-- from file 2
4x + 0               <-- from file 1
3x^3 + 1x^2 + 2
2x^3 + 3x
1x^6 + 5x^2 + 6x
3x^8 + 1x^4 + 1x^2

Here's a little example that takes the data from the files and adds the polynomials to a list which is sorted and printed:

Java Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Polynomial implements Comparable<Polynomial> {

private int[] coef;
private int deg;

public Polynomial(String polynomial) {
Scanner line = new Scanner(polynomial);

int coefficient = line.nextInt();
int exp = line.nextInt();

coef = new int[exp + 1];
coef[exp] = coefficient;
deg = degree();

while (line.hasNextInt()) {
coefficient = line.nextInt();
exp = line.nextInt();
coef[exp] = coefficient;
}
}

public int degree() {
int d = 0;

for (int i = 0; i < coef.length; i++) {
if (coef[i] != 0)
d = i;
}
return d;
}

public String toString() {
if (deg == 0) {
return "" + coef[0];
} else if (deg == 1) {
return coef[1] + "x + " + coef[0];
}

String s = coef[deg] + "x^" + deg;

for (int i = deg - 1; i >= 0; i--) {
if (coef[i] == 0) {
continue;
} else if (coef[i] > 0) {
s = s + " + " + (coef[i]);
} else if (coef[i] < 0) {
s = s + " + " + (-coef[i]);
}
if (i == 1) {
s = s + "x";
} else if (i > 1) {
s = s + "x^" + i;
}
}
return s;
}

public int compareTo(Polynomial arg) {
if (coef.length > arg.coef.length) {
return arg.coef.length - coef.length;
}
for (int i = coef.length - 1; i >= 0; i--) {
if (coef[i] != arg.coef[i]) {
return arg.coef[i] - coef[i];
}
}
*/
if (coef.length != arg.coef.length) {
return coef.length - arg.coef.length;
}
for (int i = coef.length - 1; i >= 0; i--) {
if (coef[i] != arg.coef[i]) {
return coef[i] - arg.coef[i];
}
}
return 0;
}

public static void main(String[] args) {
String[] data = new String[] {
"7 0", "4 1", "1 6 5 2 6 1", "1 6 5 2 6 1 4 0",
"5 1 2 0", "2 3 3 1", "3 3 1 2 2 0", "1 6 5 2 6 1", "3 8 1 4 1 2"
};
ArrayList<Polynomial> orderedList = new ArrayList<Polynomial>();

for(String line :data) {
Polynomial p = new Polynomial(line);
}
Collections.sort(orderedList);
System.out.println("The sorted output...");
for(Polynomial p :orderedList) {
System.out.println(p);
}

}
}

with output:

Java Code:
Adding 1x^6 + 5x^2 + 6x
Adding 1x^6 + 5x^2 + 6x + 4
Adding 3x^3 + 1x^2 + 2
Adding 1x^6 + 5x^2 + 6x
Adding 3x^8 + 1x^4 + 1x^2
The sorted output...
7
4x + 0
5x + 2
2x^3 + 3x
3x^3 + 1x^2 + 2
1x^6 + 5x^2 + 6x
1x^6 + 5x^2 + 6x
1x^6 + 5x^2 + 6x + 4
3x^8 + 1x^4 + 1x^2

Beautifully sorted!
Last edited by pbrockway2; 02-27-2011 at 07:46 AM.

Page 2 of 2 First 12

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•