File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Binary search to add elements into array throws null pointer exception Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Reply locked New topic
Author

Binary search to add elements into array throws null pointer exception

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Daniel Perera wrote:


You're still doing the exact same thing--shifting elements down.





+ means it's already there, -means it's not. By dealing with +/- AFTER the above logic, you're going to have a serious problem if it's already there. Think about what your * -1 logic will do.

What do you WANT to do if it's already there? Whatever that is, you have to make that decision BEFORE you execute the insert logic.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Jeff Verdegan wrote:
You're still doing the exact same thing--shifting elements down.


+ means it's already there, -means it's not. By dealing with +/- AFTER the above logic, you're going to have a serious problem if it's already there. Think about what your * -1 logic will do.

What do you WANT to do if it's already there? Whatever that is, you have to make that decision BEFORE you execute the insert logic.

Right. So, here's what I've got now. I'm hoping it makes a little more sense now? If the entry is already there, I would obviously not want it to add a duplicate. I've changed the code to the following, but I am still not dealing with the nulls and thus getting the NPE. Does the following seem reasonable? If yes, could you please hint at how I can deal with the nulls? If the following is still wrong, what am I doing wrong?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

What does size represent? The number of elements currently in the array?

Look closely at this bit:



It looks like you're calling binarySearch() for the new size, before you add the new element.

Do you see why that would be a problem?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Jeff Verdegan wrote:What does size represent? The number of elements currently in the array?

Look closely at this bit:



It looks like you're calling binarySearch() for the new size, before you add the new element.

Do you see why that would be a problem?

I think so - I'm increasing the number of elements in the array before physically adding a new element to the array itself. Is moving size++; to the following bit the right course of action?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Daniel Perera wrote:
I think so - I'm increasing the number of elements in the array before physically adding a new element to the array itself. Is moving size++; to the following bit the right course of action?


At a quick scan it looks right, but since you're so close now, the best way to find out is to test it, and if needed, and println() statements to see what's going on step by step.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Jeff Verdegan wrote:

At a quick scan it looks right, but since you're so close now, the best way to find out is to test it, and if needed, and println() statements to see what's going on step by step.

Jeff, I've actually run the debugger and it seems like it adds the first entry into index 0 without any problem, and then overwrites the second entry into index 0. After that, it does some funny things with the shifting.

Here's a basic outline of what appears to be happening:

First, the first entry to be added to the directoryArray, A SMITH, is placed into index position 0. For the next element, the binary search is ran and returns -1. The program therefore converts -1 into 1, and thus places the second entry, B JOHNSON into position directoryArray[placeEntry-1], i.e. index 0, thus overwriting the current 0th element, A SMITH. I created a for loop which is supposed to do the shifting, but I'm guessing there is a problem to do with the value of size at this point being 0:

After this point, the third entry C WILLIAMS is placed in the position AFTER B JOHNSON which seems to be correct. However, after this, the fourth element D JONES overwrites C WILLIAMS, and after that what happens is that the next 3 spaces in the array that were null are filled with D JONES as well, so the array looks like this:

[B JOHNSON, D JONES, D JONES, D JONES, D JONES, null, null, null......]

Before the program encounters the null pointer exception, several other entries are added in the correct positions but overwrite some of the previous entries, it really is a mess, but it's good to see that at times the sorting does seem to work. The final look of the array before the NPE is this:

[E BROWN, F DAVIS, D JONES, D JONES, D JONES, G MILLER, I MOORE, null, null...] - the NPE then shows up. As you can see some entries such as B JOHNSON, A SMITH, C WILLIAMS etc have been completely overwritten and D JONES duplicated several times, and the entries after a certain point cause a NPE.

I'm sorry if I've not been able to explain what is going on very well, but without screenshots or any real output it really is a little challenging, especially for me. Looking at the latest code and the info I've tried to provide above, I'm hoping you may be able to see what is happening, what's wrong with the code that is causing the above to happen and help me fix it.


Thank you,
Daniel
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

I can see 2 mistakes in your code:

First : What does size represent? The number of elements in the array. Right? So, after inserting the first element, the size should be 1, not 0, then 2 and so on. Initialize size to 0, not -1, in the constructor.

Second : Think carefully that exactly where would you be placing the new entry in the directoryArray. Simply multiplying the placeEntry by -1 is not the insertPostion. Remember that the way we are using binarySearch() here, it will always return a -ve value as the entry is not present in the array. And what does that returned value represent? It is not the insertion point of the entry but equal to (-(I.P) -1). Therefore, insertionPoint needs to be calculated as:

Hence, insertionIndex = placeEntry-1

So, if your binarySearch() returns -2, it means the actual insertPosition would be -(-2) -1 = 1. Are you with me?

Whenever placeValue is negative, it means that the actual insertion point needs to be calculated by you using the -(I.P) - 1 formula. See the documentation of the method. So, I.P would become -1*(placeEntry) -1). So, what your method will partly look like is :






~ Mansukh
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:I can see 2 mistakes in your code:

First : What does size represent? The number of elements in the array. Right? So, after inserting the first element, the size should be 1, not 0, then 2 and so on. Initialize size to 0, not -1, in the constructor.

Second : Think carefully that exactly where would you be placing the new entry in the directoryArray. Simply multiplying the placeEntry by -1 is not the insertPostion. Remember that the way we are using binarySearch() here, it will always return a -ve value as the entry is not present in the array. And what does that returned value represent? It is not the insertion point of the entry but equal to (-(I.P) -1). Therefore, insertionPoint needs to be calculated as:

Hence, insertionIndex = placeEntry-1

So, if your binarySearch() returns -2, it means the actual insertPosition would be -(-2) -1 = 1. Are you with me?

Whenever placeValue is negative, it means that the actual insertion point needs to be calculated by you using the -(I.P) - 1 formula. See the documentation of the method. So, I.P would become -1*(placeEntry) -1). So, what your method will partly look like is :



Hi again. I've made a few changes but it's still not functioning correctly. The Null Pointer Exception no longer appears to be coming up but the array ends up being something like this:

[BROWN E 0005, DAVIS F 0006, JOHNSON B 0002, JOHNSON B 0002, JOHNSON B 0002, JOHNSON B 0002, ....] so some of the sorting works but there still appears to be a problem with the shifting of the elements and so on. I really don't have a lot of time left for this project and I'm still on part one, starting to worry a little bit, I don't understand why it still doesn't work... Here is the latest code:


What am I doing wrong still? :/

EDIT: After going through the debugger a few times and trying to examine what exactly happens, I'm noticing that the following appears to be happening:

A SMITH added into position 0 as first element in array. B JOHNSON placed before A SMITH (sorting works). C WILLIAMS is then placed into index 2, so the array looks like this: [B JOHNSON, A SMITH, C WILLIAMS] at this point. What then appears to happen is when D JONES needs to be added, it needs to go into index 1, after B JOHNSON, so that the array will look like this: [B JOHSON, D JONES, A SMITH, C WILLIAMS] - what actually happens is the following: A SMITH is shifted from index 1 to 2, and then index 2 is shifted to index 3, so we have the following: [B JOHNSON, A SMITH, A SMITH, A SMITH]. It appears that there is some sort of flaw in the logic where we execute the following code,

Can you see the problem? Any suggestions as to how I can fix this?

EDIT #2 (sorry for the long post!):

Changing the for loop above to the following appears to make it work now! It seemed that with the previous loop, the array would lose elements because it would do directoryArray[i+1] = directoryArray[i] so when an entry e.g. D JONES was to be added between B JOHNSON and A SMITH, A SMITH was copied over to the next position in the array, thus overwriting the next element, C WILLIAMS, before C WILLIAMS had a chance to be copied over to the next position, thus duplicating A SMITH as I stated above in the first edit. The following now seems to work, can you check and confirm that this makes sense?

Thanks
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Yes, that is what I wrote 6 hours ago. Nice work David. Now that you have completed the addEntry(String, String, String) method, functionally at least, lets move on. We will be coming back to refine the methods and add documentation and comments though. Which one do you want to go for next?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Yes, that is what I wrote 6 hours ago. Nice work David. Now that you have completed the addEntry(String, String, String) method, functionally at least, lets move on. We will be coming back to refine the methods and add documentation and comments though. Which one do you want to go for next?

Thanks Mansukh Btw, its Daniel. I actually did the removeEntry method a few days ago. It works for removing an entry by Surname, however I also need it to work for removing an entry by extension. So for instance, I want to be able to do d.removeEntry("Perera") OR d.removeEntry("2013") - at the moment it only works for the surname, and I know why - it's because I haven't made an entry where the paramater is passed on as an extension. I was thinking that I could perhaps use try and catch statements here but I gave it a go and couldn't get it working. If I enter an extension, it throws an ArrayIndexOutOfBoundsException: -1. Here's the current code:

Hints?

Thanks,
Daniel
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Oh yes, Daniel not David. Anyways, let me first confirm the use case. You want to remove an entry from the array if that surname or extension exists in the directory. Am I correct?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Oh yes, Daniel not David. Anyways, let me first confirm the use case. You want to remove an entry from the array if that surname or extension exists in the directory. Am I correct?


Correct The current code works for the surname but not for the extension since I haven't written any code that covers such a case. I was thinking that I could perhaps use try and catch statements here but I gave it a go and couldn't get it working.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Why not pass Entry reference as a parameter to the remove method instead of a surname? Why not have a remove(Entry entry) method? Does you assignment specifically say so? Also, what prompted you to use a try-catch construct?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Mansukhdeep Thind wrote:Also, what prompted you to use a try-catch construct?


Indeed. If you're using try/catch because of NPE or ArrayIndexOutOfBoundsException or any other unchecked exception, you're doing it wrong. RuntimeException and its descendants indicate a bug in your code. Fix the bug, rather than masking it and sidestepping around it by catching those exceptions.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Why not pass Entry reference as a parameter to the remove method instead of a surname? Why not have a remove(Entry entry) method? Does you assignment specifically say so? Also, what prompted you to use a try-catch construct?


The assignment asks for us to be able to do a set of things in the first part, one of which is the following:

2) Delete entries from the directory either by name or number

So I guess the remove(Entry entry) method would be out of question.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Daniel Perera wrote: 2) Delete entries from the directory either by name or number


Do you mean delete the first entry or all the entries that match the surname? There could be more than one person having the same surname. Then what?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:
Daniel Perera wrote: 2) Delete entries from the directory either by name or number


Do you mean delete the first entry or all the entries that match the surname? There could be more than one person having the same surname. Then what?


In such a case I would probably want it to print a line such as: "There are two entries matching this surname, E PERERA 1205 and D PERERA 0222, which would you like to delete?" and then remove the correct one.. Although we were told that there shouldn't be any I/O so I'm not sure if that's a good approach
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

For the time being, let us assume that there are no duplicate surnames. Write down the logic that you will be implementing to search and remove the passed surname. How do you know for sure that your current remove(String) method works correctly without any issues? Did you try and print the list before and after the call to remove(String)?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:For the time being, let us assume that there are no duplicate surnames. Write down the logic that you will be implementing to search and remove the passed surname. How do you know for sure that your current remove(String) method works correctly without any issues? Did you try and print the list before and after the call to remove(String)?


Yes, it wors for the surname. In my test class I did d.printDir(), d.removeEntry("ZUMWALT") and d.printDir() one after the other and in the first print out E ZUMWALT is there, in the second he is not, so the following code works for surnames:
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Show me your printDir() method. Also, think how will you cater for the scenario where one would like to delete an entry based on en extension and not a surname.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Show me your printDir() method. Also, think how will you cater for the scenario where one would like to delete an entry based on en extension and not a surname.


Thats what I'm trying to figure out right now. Initially, I was not using binarySearch() and the following worked well:

However I then read up about binary search and realised it would be more efficient to use binary search than to look through the whole array to find the matching entry. I'm not sure how I can do it for two possibilities though but one thing that I thought of was perhaps if I did something like this:

I'm not sure if making two seperate entries makes sense, and I'm not sure how I'd add another for loop and make it choose the right for loop depending on what info the user passes to the method.

Here is my printDir() method:
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Daniel Perera wrote: However I then read up about binary search and realized it would be more efficient to use binary search than to look through the whole array to find the matching entry. I'm not sure how I can do it for two possibilities though but one thing that I thought of was perhaps if I did something like this:


I'm not sure if making two separate entries makes sense, and I'm not sure how I'd add another for loop and make it choose the right for loop depending on what info the user passes to the method.


Why not check what is being passed right at the beginning of the method? If it is a surname, create the entry for the first type else of the second type. Why to create two entries? Use an if check in the beginning itself. As a thumb rule, try and filter input as much as possible before implementing the actual business logic in any java method.

You do not need to write two for loops either. Once you have the correct entry with you from the if-else construct, go ahead, search for it and remove it. Are you with me? You can't, as you said, choose a for loop depending on the input. With the switch-case construct, you can do selective execution though. But that is not needed here.

Daniel Perera wrote:Here is my printDir() method:


That looks fine. I would like to test it once though.


Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Why not check what is being passed right at the beginning of the method? If it is a surname, create the entry for the first type else of the second type. Why to create two entries? Use an if check in the beginning itself. As a thumb rule, try and filter input as much as possible before implementing the actual business logic in any java method.

You do not need to write two for loops either. Once you have the correct entry with you from the if-else construct, go ahead, search for it and remove it. Are you with me? You can't, as you said, choose a for loop depending on the input. With the switch-case construct, you can do selective execution though. But that is not needed here.

Hey again. Here's what I've tried, but I get an ArrayIndexOutOfBoundsException when I try to delete an entry by extension. I went into the debugger and the binary search returns a negative number so from what I understand it's telling me it can't find an entry with that extension (although it exists) - what might I be doing wrong here?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

What exactly are you searching for Daniel? Is there any entry ("BROWN", "ilove", "csc1022" ) in your directory? How do you expect the binarySearch() to find it? You have to tweak the logic to find the entry only on the basis of a surname or an extension? Getting the idea? Because you only have that part of the information as a passed argument. Think.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:What exactly are you searching for Daniel? Is there any entry ("BROWN", "ilove", "csc1022" ) in your directory? How do you expect the binarySearch() to find it? You have to tweak the logic to find the entry only on the basis of a surname or an extension? Getting the idea? Because you only have that part of the information as a passed argument. Think.

I understand what you mean but in that case how come this works?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

I don't see your size variable changing during a delete operation. When you delete an element, does size remain the same?
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Jeff Verdegan wrote:I don't see your size variable changing during a delete operation. When you delete an element, does size remain the same?


Does that matter? I can do size--; at the end I suppose?
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Daniel Perera wrote:
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.


I have the compareTo() method that compares both surnames and initials. Hence, the exception. Do you intend to keep it that way? If you change the compareTo() later, it might break your code as a lot of the implemented logic is based on searching that uses this method. Also, cater for reducing the size for each entry removed as Jeff rightly said.
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Daniel Perera wrote:
Jeff Verdegan wrote:I don't see your size variable changing during a delete operation. When you delete an element, does size remain the same?


Does that matter? I can do size--; at the end I suppose?


Of course it matters! That is what size represents, right? The number of entries in the array at present.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:
Daniel Perera wrote:
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.


I have the compareTo() method that compares both surnames and initials. Hence, the exception. Do you intend to keep it that way? If you change the compareTo() later, it might break your code as a lot of the implemented logic is based on searching that uses this method. Also, cater for reducing the size for each entry removed as Jeff rightly said.

Alright, fair enough, I must have removed the initial comparison at some point and thus never noticed the problem. I would like it to compare initials IF the surnames are the same. Do I not also need an extension comparison for when I want to delete an entry by extension number? Can I have all three comparisons in the compareTo method and still get it working? If you could give me more than "think" that would be great, I only have a week left to hand in this coursework now and I'm still not done with part 1 (there are three parts)
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:
Daniel Perera wrote:
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.


I have the compareTo() method that compares both surnames and initials. Hence, the exception. Do you intend to keep it that way? If you change the compareTo() later, it might break your code as a lot of the implemented logic is based on searching that uses this method. Also, cater for reducing the size for each entry removed as Jeff rightly said.

Hey again, ok I just spoke with people on my course and re-read the specs and it appears that we should be deleting entries like this: d.removeEntry("PERERA", "D");... So, I changed the removeEntry(String deleteMe) to removeEntry(String deleteSurname, String deleteInitials). Works fine for deleting a name like d.removeEntry("PERERA","D") but if I wanted to delete an entry by extension, a friend of mine said that I can't do it by using binarySearch because it is sorted by surname and not by extension and binarySearch requires the stuff to be sorted properly. So he said I should use a for loop to delete by extensions. However, since I made the removeEntry method take two parameters I don't know how I could also make it work for one parameter - an extension.. Please advise, really need to get this part finished asap
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Daniel Perera wrote:
Jeff Verdegan wrote:I don't see your size variable changing during a delete operation. When you delete an element, does size remain the same?


Does that matter?


You tell me. What is your size variable for, and is it a member or a local? I assumed it was a member, but if it's a local, then no, it doesn't matter if you change it.

If it's a member though, and if you're using it to represent the state of the object--that is the number of elements present, even when not in the middle of a method call--then I would think that it would have to change when you add or delete an element.

(Actually, now that I think about it, if your printouts looked good after adding and deleting, then I guess it must be a local variable, and I probably just threw a red herring in your path. My apologies if that's the case.)
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Daniel Perera wrote:
Mansukhdeep Thind wrote:
Daniel Perera wrote:
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.


I have the compareTo() method that compares both surnames and initials. Hence, the exception. Do you intend to keep it that way? If you change the compareTo() later, it might break your code as a lot of the implemented logic is based on searching that uses this method. Also, cater for reducing the size for each entry removed as Jeff rightly said.

Hey again, ok I just spoke with people on my course and re-read the specs and it appears that we should be deleting entries like this: d.removeEntry("PERERA", "D");... So, I changed the removeEntry(String deleteMe) to removeEntry(String deleteSurname, String deleteInitials). Works fine for deleting a name like d.removeEntry("PERERA","D") but if I wanted to delete an entry by extension, a friend of mine said that I can't do it by using binarySearch because it is sorted by surname and not by extension and binarySearch requires the stuff to be sorted properly. So he said I should use a for loop to delete by extensions. However, since I made the removeEntry method take two parameters I don't know how I could also make it work for one parameter - an extension.. Please advise, really need to get this part finished asap


There is something called varargs in Java which is used for precisely this kind of a use case. Do you know what are varargs Daniel? Instead of remove(String, String) or remove (String), I can say remove (String...). This means that the method can accept a variable number of Strings. Try and see if your problem is solved.
Daniel Perera
Ranch Hand

Joined: Apr 17, 2013
Posts: 47
Mansukhdeep Thind wrote:
Daniel Perera wrote:
Mansukhdeep Thind wrote:
Daniel Perera wrote:
Mansukhdeep Thind wrote:Are you sure it works? I am not so sure though. Check again. You will get an exception on the console.

Checked several times, it works, no exception no nothing, did printDir() before and afterwards as well and the entry is deleted... Provided the Entry class only compares surnames in the compareTo method, it works absolutely fine.


I have the compareTo() method that compares both surnames and initials. Hence, the exception. Do you intend to keep it that way? If you change the compareTo() later, it might break your code as a lot of the implemented logic is based on searching that uses this method. Also, cater for reducing the size for each entry removed as Jeff rightly said.

Hey again, ok I just spoke with people on my course and re-read the specs and it appears that we should be deleting entries like this: d.removeEntry("PERERA", "D");... So, I changed the removeEntry(String deleteMe) to removeEntry(String deleteSurname, String deleteInitials). Works fine for deleting a name like d.removeEntry("PERERA","D") but if I wanted to delete an entry by extension, a friend of mine said that I can't do it by using binarySearch because it is sorted by surname and not by extension and binarySearch requires the stuff to be sorted properly. So he said I should use a for loop to delete by extensions. However, since I made the removeEntry method take two parameters I don't know how I could also make it work for one parameter - an extension.. Please advise, really need to get this part finished asap


There is something called varargs in Java which is used for precisely this kind of a use case. Do you know what are varargs Daniel? Instead of remove(String, String) or remove (String), I can say remove (String...). This means that the method can accept a variable number of Strings. Try and see if your problem is solved.

I didn't know about varargs, looking into it now, however if I did something like

Then it doesn't work, I'm guessing I need to somehow seperate the input, for example if I called the method removeEntry("PERERA", "D") I'm guessing it doesn't know how to seperate them from each other or something? The error I get is on line Entry entry = new Entry(deleteMe, deleteMe, "ilovecsc1022"); and it says The constructor Entry(String[], String[], String) is undefined. How could I make this work?
Andrew Monkhouse
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11476
    
  94

Mansukhdeep Thind wrote:
Daniel Perera wrote:Works fine for deleting a name like d.removeEntry("PERERA","D") but if I wanted to delete an entry by extension, a friend of mine said that I can't do it by using binarySearch because it is sorted by surname and not by extension and binarySearch requires the stuff to be sorted properly. So he said I should use a for loop to delete by extensions. However, since I made the removeEntry method take two parameters I don't know how I could also make it work for one parameter - an extension.. Please advise, really need to get this part finished asap


There is something called varargs in Java which is used for precisely this kind of a use case. Do you know what are varargs Daniel? Instead of remove(String, String) or remove (String), I can say remove (String...). This means that the method can accept a variable number of Strings. Try and see if your problem is solved.


I don't think that varargs are the best option in this case. You seem to have two distinct operations here:
  • Delete by surname and initial, and for this you will use a binary search (in DB terms, you will be searching on an index).
  • Delete by extension, and for this you will look at every single record in your array (in DB terms, you will use a full table scan).


  • Given that these have different parameters and different implementations, I think you are better off setting up two distinct methods for doing the searching, and then have a separate (private) method that does the deletion of the record from the array once found.

    Side notes (feel free to ignore everything from this point onwards) - the reason I mention database terms is that this seems to be a good way to build towards the knowledge needed for creating your own database from scratch.

    You mentioned that you would prefer to do a binary search on the extension number, however binary searches only work on sorted data, so as you have discovered (and your friend pointed out) it will not work with your current data structures.

    I do not recommend this for your assignment, but consider what would happen if you had multiple arrays:
  • the main array containing the complete record (initial, last name, extension) in a completely unsorted order
  • another array containing a sorted list of last names and the record number from the main array
  • another array containing a sorted list of extensions and the record number from the main array


  • If you need to print the phone list in sorted order, you can simply traverse the second array and use it to pull records from the main array - they will be pulled in sorted order.

    If you need to search either the last name or the phone number you can use the sorted lists.

    In DB terms, what we have just done is add another index to the main table.

    Of course, you have not yet got to the point where you do a hashed look up on surname, which will be faster still than the binary search. And there are similar speed lookups you can do for looking up based on extensions. But I am getting way ahead of where we should be.


    The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
    Mansukhdeep Thind
    Ranch Hand

    Joined: Jul 27, 2010
    Posts: 1157

    What's the reason that you say varargs are not the way to go Andrew? Any particular cause?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Mansukhdeep Thind wrote:What's the reason that you say varargs are not the way to go Andrew? Any particular cause?


    Re-read this:
    Mansukhdeep Thind wrote:
    Daniel Perera wrote:
    Hey again, ok I just spoke with people on my course and re-read the specs and it appears that we should be deleting entries like this: d.removeEntry("PERERA", "D");... So, I changed the removeEntry(String deleteMe) to removeEntry(String deleteSurname, String deleteInitials). Works fine for deleting a name like d.removeEntry("PERERA","D") but if I wanted to delete an entry by extension, a friend of mine said that I can't do it by using binarySearch because it is sorted by surname and not by extension and binarySearch requires the stuff to be sorted properly. So he said I should use a for loop to delete by extensions. However, since I made the removeEntry method take two parameters I don't know how I could also make it work for one parameter - an extension.. Please advise, really need to get this part finished asap


    There is something called varargs in Java which is used for precisely this kind of a use case. Do you know what are varargs Daniel? Instead of remove(String, String) or remove (String), I can say remove (String...). This means that the method can accept a variable number of Strings. Try and see if your problem is solved.


    Varargs is most definitely NOT for this kind of use case. Varargs is for when you want to do the same operation on a variable number of arguments, such as printGrades(student1); vs. printGrades(student1, student2, student3); vs. printGrades(studentArray);

    What he's doing here is two completely different things. The fact that they're both removals and that one happens to take one arg and one happens to take two args does not make them even remotely appropriate for varargs.

    You don't want to write a varargs method like:


    A varargs method should look like:
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Binary search to add elements into array throws null pointer exception