// The SongList class that represents a circular linked list of Song nodes
// Your name here

public class SongList {
    // instance variables
    private Song m_last;
    private int m_numElements;

    // constructor
    // Do not make any changes to this method!
    public SongList() {
        m_last = null;
        m_numElements = 0;
    }

    // check whether the list is empty
    // Do not make any changes to this method!
    boolean isEmpty() {
        if (m_last == null)
            return true;
        else
            return false;
    }

    // return the size of the list (# of Song nodes)
    // Do not make any changes to this method!
    public int size() {
        return m_numElements;
    }

    // add a new Song to the circular linked list with the given artist and
    // title, keeping the list sorted by *song title*.
    public void add(String artist, String title) {
        Song to_add = new Song(artist, title);
        if (m_last == null) {
            m_last = to_add;
            m_last.setLink(m_last);
        }
        else if (m_last.getTitle().compareTo(title) <= 0) {
            to_add.setLink(m_last.getLink());
            m_last.setLink(to_add);
            m_last = to_add;
        }
        else {
            // start from last song
            Song current = m_last;
            while (title.compareTo(current.getLink().getTitle()) >= 0) {
                current = current.getLink();
            }
            to_add.setLink(current.getLink());
            current.setLink(to_add);
        }
        m_numElements += 1;
    }

    // remove a Song associated with the given artist and title from the list,
    // keeping the list sorted by *song title*.
    public boolean remove(String artist, String title) {
        Song current = m_last;
        if (current == null)
            return false;

        while ((current.getLink().getTitle().compareTo(title) != 0) && (current.getLink().getArtist().compareTo(artist) != 0) && (current.getLink() != m_last)) {
            current = current.getLink();
        }
        if (current.getLink() == m_last) {
            if ((m_last.getTitle().compareTo(title) == 0) && (m_last.getArtist().compareTo(artist) == 0)) {
                current.setLink(m_last.getLink());
                if (current.getTitle().compareTo(current.getLink().getTitle()) >= 0)
                    m_last = current;
                else
                    m_last = current.getLink();
            }
            else
                return false;
        }
        else {
            current.setLink(current.getLink().getLink());
        }
        m_numElements -= 1;
        return true;
    }

    // build and return a circular linked list that contains all songs from the
    // given artist
    public SongList buildList(String artist) {
        SongList new_list = new SongList();
        Song current = m_last;
        if (size() == 1) {
            if (current.getArtist().compareTo(artist) == 0)
                new_list.add(artist, current.getTitle());
            return new_list;
        }
        for (int i = 0; i < size(); i++) {
            if (current.getArtist().compareTo(artist) == 0)
                new_list.add(artist, current.getTitle());
            current = current.getLink();
        }
        return new_list;
    }

    // return a string representation of the list
    // Do not make any changes to this method!
    public String toString() {
        String listContent = "";
        Song current = m_last;
        if (m_last != null)
            do {
                current = current.getLink();
                listContent += "  [" + current.getArtist() + " - " + current.getTitle() + "]\n";
            } while (current != m_last);
        return listContent;
    }
}