CODEWITHSUNDEEP
javainfinite-loop
Zetland
Zetland

Reputation: 577

Why is my code causing an infinite loop?

I'm currently working on a method which creates a playlist from a music library. The idea is that it asks for a minimum rating for songs and a minimum runtime for the playlist and then produces a random list of songs which fit those criteria. If there are not enough songs of the minimum rating, it reduces the rating by 1 and then looks for songs which meet that requirement. (So if you specified that the playlist should have 60 mins of 5 star songs, but you don't have enough, it tries to fill the rest of the time with 4 star songs instead.)

However, if my library contains no 5 star songs, an infinite loop is caused in my code. (Or I assume so, anyway, the test program doesn't stop running) Why could this be?

public Playlist createPlaylist(int minRating, int minDuration) {
        minDuration = minDuration * 60;              
        ArrayList<Track> shuffledList = trackList;
        Playlist playlist = new Playlist();
        Collections.shuffle(shuffledList);
        int playlistDuration = 0;
        while (playlistDuration <= minDuration) {
            for (Track track : shuffledList) {
                if (track.getRating() >= minRating && !playlist.contains(track)) 
                {
                    playlist.add(track);
                    playlistDuration += track.getLength();
                }
                if (playlistDuration >= minDuration) {
                    break;
                }
            }
            minRating--;
        }
        playlist.randomise();
        return playlist;

Upvotes: 2

Views: 165

Answers (6)

phil_20686
phil_20686

Reputation: 4080

There are several problems

(1) If the total duration of the songs is too small, it will never exit. You need an exit condition based on min rating. Since the iterator over the shuffled list is always finite, this will guarantee that the code exits.

(2) The equalities don't seem to match up. If its min duration == playlist duration, it continues iterating even though it doesnt add any tracks, which is wasteful. Change the while loop to strictly less than.

(3) It would be much more efficient if you sorted the list by rating using a treeSet with a custom comparator. then you would only have to iterate over the list of tracks once.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727047

Since playlistDuration is updated conditionally, there could be many reasons for the loop to become infinite. For example, if shuffledList is empty, your playlistDuration would remain zero, so the outer loop would be infinite.

You can avoid this if you adjust minDuration to the total duration of shuffledList before entering the loop:

minDuration = Math.Min(minDuration, shuffledList.Sum(t => t.getLength()));

In plain English this means "I cannot ask for a minimum duration of more than the total duration of shuffledList".

You should also change the condition of your while loop to strict "less than", because otherwise the infinite loop would remain when shuffledList is empty.

while (playlistDuration < minDuration) {
    ...
}

Upvotes: 4

ToYonos
ToYonos

Reputation: 16833

Change your loop like this, exit the loop when all tracks have been browsed and rating == -1

while (playlistDuration <= minDuration) {
    for (Track track : shuffledList) {
        if (track.getRating() >= minRating && !playlist.contains(track)) 
        {
            playlist.add(track);
            playlistDuration += track.getLength();
        }
        if (playlistDuration > minDuration) {
            break;
        }
    }
    minRating--;
    if (minRating == -1) break;
}

Upvotes: 1

bytepusher
bytepusher

Reputation: 1578

what happens when there are not enough tracks to get playlistDuration > minDuration?

My guess is:

while( playListDuration <= minDuration )

trudges on.

Thus, you might want to check for that in your while, one option would be to add condition that tracks exist

PS: wow. While typing a couple of lines, 3 answers posted, downvote, upvote. Sheesh.

Upvotes: 0

Lawrence Aiello
Lawrence Aiello

Reputation: 4658

If you aren't finding any 5-star songs, you don't update playlistDuration, so your while loop goes on forever.

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49920

Because it is possible to go through the body of the while loop without changing playlistDuration; in particular, when you don't add any tracks.

Upvotes: 1

Related Questions