As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/

Comparable interfaces! Merge sort! NULL POINTER EXCEPTION!?!? (Java)

Shazkar ShadowstormShazkar Shadowstorm Registered User regular
edited April 2007 in Help / Advice Forum
Hey, so yeah, I'm doing some project with Comparable interfaces and the sorting of various objects... and I decided, hey, we just half learned merge sort in class, why don't I figure out the rest of it and use it here. Of course, me trying to figure it out on my own seems to have led to some problems.
I have not used the Comparable interface before either, since we are just learning it, so perhaps I have that wrong as well...

Well, let me see...
Here is my sorting class:
public class Sorter {
    //---------------------------------
    // Sorts an array using merge sort.
    //---------------------------------
    public static void mergeSort(Comparable[] objArray, int left, int right) {
       int mid = -1;
        if (left < right){
           // Finds the middle: 
           mid = (int) (left + right)/2;
           
           // Calls mergeSort twice:
           mergeSort(objArray, left, mid); // Sorts first half.
           mergeSort(objArray, mid+1, right);  // Sorts second half.
           
           // Calls merge (sorts 2 sorted subarrays and makes into one array)
           merge(objArray, left, mid, right);
            
        }
    }
    
    
    //----------------------------------
    // Merges two sorted subarrays into
    // one sorted array.
    //----------------------------------
    private static void merge(Comparable[] objArray, int left, int mid, 
            int right){
        
        int length1 = mid - left + 1; // Length of first subarray.
        int length2 = right - mid; // Length of second subarray.
        
        // Counters for merging.
        int count1 = 0;
        int count2 = 0;
        int sortedCount = 0;
        int i = 0;
        
        // New merged sorted array:
        Comparable[] sortedArray = new Comparable[length1+length2];
        
        while ((count1<length1) && (count2<length2)){
            //If obj in subarray1 is less than obj in subarray2:
            if (objArray[left+count1].compareTo(objArray[mid+count2+1])<0){
                sortedArray[sortedCount]=objArray[left+count1];
                count1++;
            }
            else {
                sortedArray[sortedCount]=objArray[mid+count2+1];
                count2++;
            }
            sortedCount++;
        }
        
        // If one subarray is done being merged, apped the remainder of the
        // other array to the sorted array:
        while (count1<length1){
            sortedArray[sortedCount]=objArray[left+count1];
            sortedCount++;
            count1++;
        }
        
        while (count2<length2){
            sortedArray[sortedCount]=objArray[mid+count2+1];
            sortedCount++;
            count2++;
        }
        
        // Put sortedArray back into original array.
        for (i = 0; i < length1+length2; i++)
            objArray[left+i] = sortedArray[i];

        
        
        
    }
}


Right, and then we're supposed to take an older class for cards from a previous project, and make it use the comparable interface so we can sort it...
So I put the following lines into the code:
public class Card implements Comparable {
and
    public int compareTo(Object otherObject){
        Card other = (Card) otherObject;
        int answer = 0;
        if (this.rank > other.rank)
            answer = 1;
        if (this.rank < other.rank)
            answer = -1;
        return answer;        
    }
so that's that...

Then, just to test it, in my driver I made an array of cards and put it into Sorter.mergeSort(); and tried to print the results. When I compiled and ran I got:
Exception in thread "main" java.lang.NullPointerException
on several different lines. Any idea why that might be?

Also, what we're actually supposed to be sorting isn't just an array of cards but a deck object from last project... the deck is an array of cards though. Can I just instantiate a deck, and plug it into merge sort, and it should work?

I'm still working on some other things as this is going on. We also need to be able to sort BankAccounts.

Also, I was wondering how one could make it sort by two different things, rank and suit, this way... would I need to change the compareTo method in my card class? I figured out how to sort by rank and suit using a method I had put into the Deck class, but we need to use a general sorting static method.

Oh boys.
Not asking for anyone to do my HW of course though, just trying to learn and figure out what I am doing wrong with what I already have.

poo
Shazkar Shadowstorm on

Posts

  • Bob SappBob Sapp Registered User regular
    edited March 2007
    General tip: Throw some trace statements in and try to narrow the problem down. (Or use a debugger).

    Edit: Also, NullPointerException means you're trying to access an object that isn't created. For example:
    StringBuilder s;
    s.append("t"); <-- NullPointerException (you didn't use new)
    

    Bob Sapp on
    fizzatar.jpg
  • SpackleSpackle Registered User regular
    edited March 2007
    Have you tried just doing a very simple sorting problem like a large array of just ints?

    Spackle on
    Taco Bell does win the franchise war according to the tome of knowledge that is Demolition Man. However, I've watched Demolition Man more then a few times and never once did I see WoW. In conclusion Taco Bell has more lasting power then WoW.
    D&D Metal Thread: HERE
  • Shazkar ShadowstormShazkar Shadowstorm Registered User regular
    edited March 2007
    Well, I took your advice for testing on an array of ints... I changed Comparable[] to int[] and plugged in an unsorted array and it did sort it properly. So at least my merge sort is right. I guess it's the interface/Comparable stuff that's the problem.

    Shazkar Shadowstorm on
    poo
  • SenjutsuSenjutsu thot enthusiast Registered User regular
    edited March 2007
    You've got at least one uninitialized object in there.

    If you're submitting this for marks you've got a couple of stylistic problems that could cost you some points. Some pointless type casts and redundant variables in various spots where you could express what you're doing much more cleanly.

    And I've had profs that would fail you for the way you're commenting things; always use comments to tell someone why you're doing something, not what you're doing. Sticking a comment on a function call that consists of "calls function" or an "is x less than y" comment on an if statement isn't just poor style, it actively distracts from the actual code which already documents precisely what it's doing. Tell your readers why you're call function, or why you're checking to see if x is less than y.

    Senjutsu on
  • iudeltaiudelta Registered User new member
    edited March 2007
    The Comparable stuff looks fine. I tried using Sorter with an array of String objects and it worked, so that's likely not the problem. You're trying to sort a Card[] right? I'm guessing some of the objects in the Card[] are null (print the contents of the array to be sure). If your Deck object contains a Card[], then you'll want send the Card[] to your Sorter, not the Deck object.

    iudelta on
  • Shazkar ShadowstormShazkar Shadowstorm Registered User regular
    edited March 2007
    Thanks for the advice re: comments. I guess the TAs are being easy on me, or maybe I wasn't so silly on the other projects. Good to learn these things before I move on. This is my first semester doing programming, so better to know things now rather than form bad habits which will screw me later.

    Cleared up the redundant casting... when you say some variables are redundant, do you mean things like sortedCount, which I realized I could just have as count1 + count2?

    Shazkar Shadowstorm on
    poo
  • Shazkar ShadowstormShazkar Shadowstorm Registered User regular
    edited March 2007
    Dumb question... I don't have to create a temporary array Comparable[] to store the object in Deck to, sort that, and then put it back in Deck, do I?

    EDIT: Yay, I made it work. It sorts my deck of cards. However, perhaps this is a roundabout way of doing it....

    Here is part of my code:
    // Sort by suit first:
            tempCards = theDeck.getDeckArray();
            Sorter.mergeSort(tempCards, 0, 51);
            
            // Change what is compared with all Cards' compareTo,
            // so the deck can be sorted by rank:
            for(int i=0; i<52;i++){
                tempCards[i].setCompareBy(1);
            }
            
            // Sort 4 subarrays (1 for each suit) of length 13:
            Sorter.mergeSort(tempCards, 0, 12);
            Sorter.mergeSort(tempCards, 13, 25);
            Sorter.mergeSort(tempCards, 26, 38);
            Sorter.mergeSort(tempCards, 39, 51);
            
            theDeck.setDeckArray(tempCards);
    

    Shazkar Shadowstorm on
    poo
  • SenjutsuSenjutsu thot enthusiast Registered User regular
    edited March 2007
    Thanks for the advice re: comments. I guess the TAs are being easy on me, or maybe I wasn't so silly on the other projects. Good to learn these things before I move on. This is my first semester doing programming, so better to know things now rather than form bad habits which will screw me later.

    Cleared up the redundant casting... when you say some variables are redundant, do you mean things like sortedCount, which I realized I could just have as count1 + count2?
    I wouldn't normally rewrite code for you, but I'm not actually fixing any bugs (there aren't any in this part), so as an example:

    public int compareTo(Object otherObject){
            Card other = (Card) otherObject;
            int answer = 0;
            if (this.rank > other.rank)
                answer = 1;
            if (this.rank < other.rank)
                answer = -1;
            return answer;        
        }
    

    could be expressed as
    public int compareTo(Object other){
            Card other = (Card) otherObject;
            if (this.rank > other.rank)
                return 1;
            else if (this.rank < other.rank)
               return -1;
            else
               return 0;
        }
    
    The advantages here are the lack of an variable and the fact that by returning immediately out of the if statement rather than at the end of the function the effect of the if statements is immediately clear. Even if you wanted to keep around the additional variable to store the value you want to return, you'd be better off sticking an else clause in, like:
    public int compareTo(Object otherObject){
            Card other = (Card) otherObject;
            int answer = 0;
            if (this.rank > other.rank)
                answer = 1;
            else if (this.rank < other.rank)
                answer = -1;
            return answer;        
        }
    
    Without that else in there, even after finding out that this.rank really is greater than other.rank, you're performing the second test anyways, which is redundant. I think this is less clean than eliminating the answer variable, though, because the fact that it returns 0 if both the greater than and lesser than tests fail is less immediately explicit to the reader.

    The redundant cast was simply "mid = (int) (left + right)/2". mid is an int, so the conversion to an int was guaranteed even without the cast.

    Senjutsu on
  • BamaBama Registered User regular
    edited March 2007
    To offer another perspective on the compareTo function, I prefer return a variable that can be modified to having several return statements in a function. In a small function like that there isn't really a risk of losing track of the different returns, but I don't think it's a good practice to get into. Tracing control flow is much easier when a function always exits at the same line. Similarly, I prefer to have multiple conditionals in a loop control if it means I can do away with break statements.

    Bama on
  • dsplaisteddsplaisted Registered User regular
    edited March 2007
    To compare both rank and suite, I would do the compareTo() something like this:
    if (this.suite < other.suite)
        return -1;
    else if (this.suite > other.suite)
        return 1;
    else if (this.rank < other.rank)
        return -1;
    else if (this.rank > other.rank)
        return 1;
    else
        return 0;
    

    dsplaisted on
    2850-1.png
  • Mr.FragBaitMr.FragBait Registered User regular
    edited March 2007
    dsplaisted wrote: »
    To compare both rank and suite, I would do the compareTo() something like this:

    When comparing multiple values, I try to avoid multiple else if statements. Plus, this way is slightly more efficient, which is important if you're comparing hundreds of values.

            /*
    	 * (non-Javadoc)
    	 * 
    	 * @see java.lang.Comparable#compareTo(java.lang.Object)
    	 * 
    	 */
    	public int compareTo(Object o) {
                    Card other = (Card) o;
    
    		int compare = this.suite - other.suite;
                    
                    if(compare != 0)
                           return compare;
                      
                     return this.rank - other.rank;
    	}
    
    
    

    And don't forget, compareTo doesn't return ONLY 1,0, -1. As stated in the javadoc

    "Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."

    This is important for figuring out relative differences in two comparable Objects without looking at them. So try to avoid the habit of only using 1,0,-1.

    Mr.FragBait on
  • dsplaisteddsplaisted Registered User regular
    edited April 2007
    dsplaisted wrote: »
    To compare both rank and suite, I would do the compareTo() something like this:

    When comparing multiple values, I try to avoid multiple else if statements. Plus, this way is slightly more efficient, which is important if you're comparing hundreds of values.

            /*
    	 * (non-Javadoc)
    	 * 
    	 * @see java.lang.Comparable#compareTo(java.lang.Object)
    	 * 
    	 */
    	public int compareTo(Object o) {
                    Card other = (Card) o;
    
    		int compare = this.suite - other.suite;
                    
                    if(compare != 0)
                           return compare;
                      
                     return this.rank - other.rank;
    	}
    
    
    

    And don't forget, compareTo doesn't return ONLY 1,0, -1. As stated in the javadoc

    "Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."

    This is important for figuring out relative differences in two comparable Objects without looking at them. So try to avoid the habit of only using 1,0,-1.

    Well, the problem with using subtraction is that you can have an overflow. For example, a signed byte can have values from -128 to +127. If you try to subtract +127 from -128, you will either get +1 or some sort of overflow exception. In a lot of situations it may not matter, but it's something to keep in mind.

    dsplaisted on
    2850-1.png
  • Mr.FragBaitMr.FragBait Registered User regular
    edited April 2007
    dsplaisted wrote: »

    Well, the problem with using subtraction is that you can have an overflow. For example, a signed byte can have values from -128 to +127. If you try to subtract +127 from -128, you will either get +1 or some sort of overflow exception. In a lot of situations it may not matter, but it's something to keep in mind.

    Admittedly, thats an issue. But I was under the assumption that his suit and rank wouldn't be from negative integer max value to positive max value. Though I wont deny there isn't much difference when we're comparing two primitives.

    Plus this shorter way of writing compareTo works well for general Objects that are comparable, which is generally when you use mergeSort and the like. For example, for a Pair Class that contains comparables:
    (Ignoring Generics)
    int compare = this.pair.first.compareTo(other.pair.first);
                    
    if(compare != 0)
            return compare;
                      
    return this.pair.second.compareTo(other.pair.second);
    

    is more efficient than:
    if (this.pair.first.compareTo(other.pair.first) < 0)
        return -1;
    else if (this.pair.first.compareTo(other.pair.first) > 0)
        return 1;
    else if (this.pair.second.compareTo(other.pair.second) < 0)
        return -1;
    else if (this.pair.second.compareTo(other.pair.second) > 0)
        return 1;
    else
        return 0;
    

    My point is that not to pick up bad habits like using multiple compares when you might not need to. Sometimes people pick up bad habits when they first start coding. The difference in efficiency is especially true when what your comparing might take a while to finish comparing. If the OP is learning sorts, he should be learning about coding efficiency and Big O. ( Yes, I know both ways are O(n). But one is O(2n) and O(4n). It makes a difference to a CprE. )

    Mr.FragBait on
Sign In or Register to comment.