• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to implement Collections.binarySearch() method on ArrayList of custom objects ?  RSS feed

 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm doubted regarding the implementation of Collections.binarySearch() method on an ArrayList of objects of a custom class Movie.

Here is the movie class :





Now, I have another class to manipulate the Movie objects as :




The sort/binarySearch in searchByMovieName function is done with natural sorting (and Comparable Interface in Movie class). I mean no comparators involved here. And the comparator that I used for sorting/binarySearching on Movies Director attribute in searchByMovieDirector function is :


.......................

But I was not able to implement binarySearch ?? Could anyone please help me out in how to implement the binarySearch here. I have google to see only binarySearch working on Arrays or probably ArrayList of String only, but not on ArrayList of custom objects. Thanks so much in advance.
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or isn't it possible to implement binarySearch for ArrayList of custom objects ? Am I on the wrong track ?
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh I got my mistake. Actually here I sent the wrong second argument on the binarySearch method:
moviesList : ArrayList of movie objects
searchKeyword : String keyword to search for in the ArrayList. I should have passed Movie Object as the second argument instead of searchKeyword string, right ? But, how to pass a Movie object when my intention is to just send a search keyword. So, I think this model doesn't works with binarySearch method. Instead, I should iterate the ArrayList and check each Movie object's name against the search Keyword using some equals method or something. Is there any other efficient methods possible ? As I'm very new to Java I haven't been exposed to such situations. I hope to learn much from the kind repliers on this topic. Thanks !

public int searchByMovieName(ArrayList<Movie> moviesList,
String searchKeyword) {
// sorting before searching
Collections.sort(moviesList);
// binary search
return Collections.binarySearch(moviesList, searchKeyword);
}
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You will need to check the details of the binary search method in the API. You find there are overloaded versions which take a Comparable as the argument or which take a Comparator. You might have to design a Comparator to sort the list, and pass the same Comparator to the binary search method.
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks so much Campbell Ritchie for the reply and API link, but I couldn't figure out the issue because I had the Movie class implementing Comparable interface, and compareTo method as quoted below which compares the movieName attribute between different Movie objects. What I just need is to do binarySearch upon ArrayList of Movie objects where the search keyword would be movie name.



But when I write the following function searchByMovieName in another class named MovieInfoManipulator, where I have the binarySearch as
return Collections.binarySearch(moviesList, searchKeyword); : it gives the following compilation error "The method binarySearch(List<? extends Comparable<? super T>>, T) in the type Collections is not applicable for the arguments (ArrayList<Movie>, String)".

I think the reason is type mismatch between the ArrayList (list of Movie objects) and searchKeyword(which is of type String). But, then how do I pass the keyword ?? Please help me out in this. Very much pleased if I get to know the reason or if I can see a working example with similar case or atleast link to some other sites where I see a sample of similar case.. Thanks again.



public class MovieInfoManipulator {
ArrayList<Movie> moviesList;

public int searchByMovieName(ArrayList<Movie> moviesList,
String searchKeyword) {
// sorting before searching
Collections.sort(moviesList);
// binary search
return Collections.binarySearch(moviesList, searchKeyword);
}
 
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're trying to put a movie name into the binary search (a String), but the method expect something comparable to the Movie class, that is another Movie instance. In other words, this function can help you find a movie that is already in the list somewhere.

you should probably use a map (Map<String, Movie>) and put all movies into this map using the movie name as a key.
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Martin Vajsar. You really gave me an insight to the issue, but then I thought If I have multiple options to search such as search movies by Director, genre, rating etc. then I would have to create different maps for each movie property with that property as map's key right. I thought Comparator class could help here like the following :


etc ..

May be all the Comparator classes could be made also as inner classes to My MovieInfoManipulator Class. Any idea to implement such a model through Comparator though I don't know whether this model is good in performance than making a Map as you told ( for each Movie property - name, genre, rating...). What is your kind opinion ? Thanks for all the inputs that you all give me.
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are really many, many possibilities how to implement this kind of functionality.

You might create a separate map for each of the search criteria, and probably put lists of movies into these maps (obviously, there will be many movies of a given genre, and all movies of one genre could be included in a single list that would then be put into a map, using the genre as a key. (You might also consider using enums for genres, but that's another, unrelated issue.)

You will certainly not be able to make this using a single list and binary search. The binary search needs the items to be sorted by the criteria you use to perform the search, and with different comparators, these orders would be different. Maybe several lists of the same instances, each sorted by given comparator could do. But you still need to use an instance of the Movie to perform the search on first, and that complicates the thing a bit. It is doable, but given that you'd need several lists anyway, I'd vote for maps.

Another approach (depending on number of movies and exact requirements) could be to keep all movies in a single collection (a list perhaps) and implement a "filter" over this list, which would select only items matching certain criteria. This filter might be an Iterator<Movie> perhaps, this would allow you to iterate over a subset of the movies that match given criteria, and you could also use Comparator<Movie> to specify these criteria.

It is certainly a good idea to hide these details in your MovieInfoManipulator class, and just provide methods such as findMoviesByGenre(String genre) which will return an Iterator<Movie> or perhaps a List<Movie>. You might start with a single list as a backing store and if it was not adequate for performance reasons, add maps to speed up the lookups.

The Collections framework allows many clever uses. I really like playing with these a lot.
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Martin for taking time to make such long explanations and advices. I liked the idea of Maps, it could easily deal with this situation but I would like to know further with the ArrayList case just only because I'm in a learning stage now. Please reply to my comments below :

Martin Vajsar wrote:
You will certainly not be able to make this using a single list and binary search. The binary search needs the items to be sorted by the criteria you use to perform the search, and with different comparators, these orders would be different.


In my implementation I do sorting with corresponding Comparator before performing binarySearch with the same Comparator for each of my search functions in the class MovieInfoManipulator. So there won't be the issue of orders getting different and resulting in wrong output. For example the search function searchByMovieName below does sorting first with movieNameComparator before performing binarySearch with same Comparator.



But, still I was wondering how to send String searchKeyword as second argument to binarySearch method when it expects movie object ? I think that is not practically doable right ? Probably binarySearch could be preferred only if I have ArrayList of Strings and then I have a searchKeyword string ??

Regarding filters that you mentioned, you mean to make a custom filter function isn't (Or is there any Core Java Classes supporting filtering this kind ) ? The custom filter function is supposed to search through the list of objects through a for loop and finds all objects that contains the searched value in each object's field values right ?.
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, using the list the way you've described (that is, sorting it by using the given comparator and then using binary search with the same comparator) is possible, and it is reasonable to implement it for learning purposes. It is only inefficient. Since sorting is quite expensive, you'd have always better response if you simply iterated through the unsorted list and returned first record which would match given value using the comparator.

Jo Jake wrote:But, still I was wondering how to send String searchKeyword as second argument to binarySearch method when it expects movie object ? I think that is not practically doable right ? Probably binarySearch could be preferred only if I have ArrayList of Strings and then I have a searchKeyword string ??

Well, it is doable, and in more than one way:

1) Your current code seems to be creating a new instance of Movie and only filling in the movie name, and using this instance in the binary search. You might create the instance in the searchByMovieName method, therefore hiding its existence from the outside world. This is fraught with problems, however. If the Movie class has many attributes, you would have to leave the others uninitialized or even provide some bogus values of them. And if such a Movie instance slipped outside of the place it was intended to be used, it could cause errors and exceptions in methods which expect all of the attributes to contain some meaningful value. So while this is doable, it is not a good thing to do.

2) You could create a comparator which would be able to compare a String to a Movie. The comparator is not obliged to only compare objects of the same class. You could inspect the class of the objects passed to the comaprator (probably using the instanceof operator) and if one of them was String and the other Movie, you could compare the movie name to the value of the string. Such comparator could be then used to binary search a movie by name given in a String.

Of course, there are downsides. Firstly, such comparator cannot be cleanly declared using generics. There is no way to express that a comparator can accept Movie instances or String instances, so you'd have to declare it as a comparator over the common parent of these two classes, which is Object. Therefore we lose type safety. This indicates the design is problematic from the OOP point of view.

Secondly, this construct is very unusual and it would give headaches to anyone who would happen to deal with your code (including yourself a year from now), since he (you) would struggle to understand what's going on. Even if it was well documented, it is still something which is not usual and it would be easy to make a mistake or overlook an undesired side effect of this solution. You should strive to write code that is maintainable in the long run; code which advertises "I'm clever" usually fails the former criterion.

I'm describing this only to help you understand that the binarySearch methods don't care what the comparator does and what types it operates on. As long as it provides a well-defined order over all objects that will be feed to the comparator, it can be successfully used in the binary search. And we can actually improve the idea a bit:

3) Create an interface called eg. MovieNameProvider with a single method String getMovieName(). Have Movie implement this interface (easy, huh?). Create a comparator declared as MovieNameComparator implements Comparator<MovieNameProvider> which will compare instances according to the movie name. Now, when doing a binary search, we can do this:


(Note we had to declare the movieName parameter as final; this is useful trick to learn when using anonymous or local classes.)

You would create similar interfaces and comparators for other attributes of the Movie class which you want to sort/search by. And you'd have a code which does practically the same thing as the first case I've described, but it is type safe and employs interfaces and comparators whose purpose is simple, clear and focused.

Jo Jake wrote:Regarding filters that you mentioned, you mean to make a custom filter function isn't (Or is there any Core Java Classes supporting filtering this kind ) ? The custom filter function is supposed to search through the list of objects through a for loop and finds all objects that contains the searched value in each object's field values right ?.

No, the Collections framework does not have built-in support for this kind of filtering. But it is quite easy to write your own generic classes and methods to this end. For example, I've created a simple interface:

and then wrote methods which allow me to copy only items matched by a filter from one collection to another, or create a filtered iterator which takes another iterator and a filter and skips over items not matched by given filter.

I'm pretty sure there are third party libraries there which provide functionality similar to this filtering (or otherwise suitable to your needs), such as the Google Guava libraries. You might try to have a look at them after you learn the Java's own Collections framework.
 
Jo Jake
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks very much Martin. You have helped me in learning many things. And your example on Comparator with anonymous inner class and final String variable was so much helpful for me because I didn't knew before these points.
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!