Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do i find if its a repeating playlist?

Tags:

c#

class

I need to find if the playlist is repeating. From my below code pls help to suggest a solution. A playlist is considered a repeating playlist if any of the songs contain a reference to a previous song in the playlist. Otherwise, the playlist will end with the last song which points to null.

using System;

public class Song
{
    private string name;
    public Song NextSong { get; set; }

    public Song(string name)
    {
        this.name = name;
    }

    public bool IsRepeatingPlaylist()
    {
        if(this.name == NextSong.name)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void Main(string[] args)
    {
        Song first = new Song("Hello");
        Song second = new Song("Eye of the tiger");

        first.NextSong = second;
        second.NextSong = first;

        Console.WriteLine(first.IsRepeatingPlaylist());
    }
}
like image 774
cloudySky Avatar asked Mar 04 '23 16:03

cloudySky


1 Answers

This would appear to be equivalent to checking for cycles in a linked-list, so we can simply use Floyd's "Tortoise and Hare" cycle detection algorithm:

public bool IsRepeatingPlaylist()
{
    var tortoise = this;
    var hare     = NextSong;

    while (tortoise is not null && hare is not null)
    {
        if (ReferenceEquals(tortoise, hare))
            return true;

        tortoise = tortoise.NextSong;
        hare     = hare.NextSong?.NextSong; // Twice as fast.
    }

    return false;
}

Here's some code that tests a playlist where the end of the play list loops back to a song about halfway through the playlist:

static void Main()
{
    Song start = new Song("1");
    Song curr  = start;

    Song halfway = null;

    for (int i = 2; i < 100; ++i)
    {
        curr.NextSong = new Song(i.ToString());
        curr = curr.NextSong;

        if (i == 50)
            halfway = curr;
    }

    curr.NextSong = halfway;
    Console.WriteLine(start.IsRepeatingPlaylist());
}
like image 93
Matthew Watson Avatar answered Mar 16 '23 02:03

Matthew Watson