report.tex

% Created 2021-11-21 Sun 23:24
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\author{Josh W. Brook}
\date{\today}
\title{\textbf{Assignment 2: MySongPlayer}}
\hypersetup{
 pdfauthor={Josh W. Brook},
 pdftitle={\textbf{Assignment 2: MySongPlayer}},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 26.3 (Org mode 9.1.9)}, 
 pdflang={English}}
\begin{document}

\maketitle

\section{Data Structures}
\label{sec:org179905e}

\subsection{MySong}
\label{sec:orgdbdd6a5}

Firstly, I implemented a new struct to store a song, which can hold both a song \emph{tune} and an int \emph{played}.
The \emph{song} struct is defined in the playlist.h interface, and contains an int \emph{id}, a char* \emph{title}, and a float \emph{duration}.
Since we are working with interfaces, I cannot alter the orginal song structure definition, but I need to add a new integer value (0 or 1), to record whether a song has been played yet.
As such, my playlist stores an array of \emph{mysong} rather than the original \emph{song}.

\subsection{Playlist}
\label{sec:org7dc4e0b}

I defined another struct to store the playlist of songs, as well as some other values to keep track of the playlist functions.
I chose to implement the playlist as a queue-style dynamic array, as items within it can be efficiently added and accessed. 
More specifically, these operations can be performed in constant time O(1).
This is far better than using a linked list, which has O(n) complexity for adding and searching.
The one downside of using a dynamic array is that it must be infrequently copied, doubling in size, to make space for more items.
Copying runs in linear time, O(n), but since we assume that the playlist should be very static, this is not a big issue.
The structure contains a dynamic array of \emph{mysong}, Q, as well as two integers to store the positions of the \emph{first} and \emph{last} elements.
Since we are not removing from the playlist, \emph{first} is generally unused.
The playlist struct also contains integers to store the \emph{size} of the allocated array, the position of the \emph{next} song to be played, and the \emph{mode} that the playlist should play in.
This \emph{mode} can be adjusted with the function \texttt{skipAllPlayedSongs} and dictates whether the paylist will automatically skip previously played songs.

\section{Implementation of Functions}
\label{sec:org9179c6b}

\subsection{PlaySong}
\label{sec:org6bbe317}

The function \textbf{playSong} takes a playlist as input and returns the id of the next song to be played.
If \texttt{p->mode == 0}, the function sets the \emph{played} variable attached to the specific \emph{mysong} to 1, showing that the song has been played. 
It then runs \texttt{findnext(p)}, which either increments \texttt{p->next} or sets it back to 0 if the end of the playlist is reached.
I decided to find the next song at this stage since the playlist should be very static, meaning that most songs will be added at the start of the program.
This means that if the last song is played and then another is added, the playlist will still play from the beginning.
If \texttt{p->mode == 1}, and \texttt{p->next} hasn't been \emph{played}, \textbf{playSong} runs as before, outputting the id of the next song to be played.
If \texttt{p->next} has already been played, the function loops through the rest of the playlist, returning the id of the next unplayed song or -1 if all the songs have been played.
When the playlist is in mode 0, this function should have constant complexity O(1), as the array can be accessed directly.
When in mode 1, the worst case complexity is O(n), as the function may have to search through the entire array linearly before it can say there are no songs left to be played.
Unfortunately, this can't be improved upon wthout drastic structure changes, as the playlist isn't sorted so binary search cannot be implemented.

\subsection{PlayFrom}
\label{sec:orgc2230d7}

The function \textbf{playFrom} takes the playlist \emph{p} and an integer \emph{i}, representing the position to play from.
If \texttt{i-1 <= p->last}, the function sets \texttt{p->next} to \emph{i - 1}, meaning \emph{i - 1} will be played next.
I check \emph{i - 1} rather than \emph{i} as the playlist indexes from 0, but the input integer counts from 1, as a human normally would.
Since the playlist is very static and I defined the variable \emph{next} within the playlist struct, playing from any given position is relatively simple.
This function has constant complexity O(1), as the size of the playlist does not affect the runtime.
\end{document}