Playlist

Fig. 26 A playlist of a music player.
CC BY-SA 3.0. By Thewob. Source: Wikimedia Commons

Imagine you want to manage a playlist which supports adding and removing tracks. The playlist should be able to manage thousands of tracks.

Activity 61 (Array or not to array?)

1. How would you implement this with an array? In particular, how do you add, remove tracks and how do you list the tracks?

2. Do you see any disadvantages of arrays? If yes, do you have any improvement ideas?

Requirements

1. Use the template below and only provide code in YOUR CODE HERE blocks.

2. Document your project, but you don’t have to provide a flowchart.

3. Content in playlist.txt should be transformed and written to playlist-out.txt, so that you get the following output. This modification is caused by highlighted lines in main.c.

4. Optional: augment your code with an interactive command line interface on terminal or even a mouse-interface using raylib.

playlist.txt:

Bad Guy – Billie Eilish 👽
Bohemian Rhapsody - Queen 🎤
Billie Jean – Michael Jackson 🕺
Rolling in the Deep – Adele 🌊
Smells Like Teen Spirit – Nirvana 🤘

playlist-out.txt:

Bad Guy – Billie Eilish 👽
Bohemian Rhapsody - Queen 🎤
Billie Jean – Michael Jackson 🕺
Tarkan – Şımarık 💋
Rolling in the Deep – Adele 🌊

Template

main.c

#include "singly_linked_list.h"
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRACK_TITLE_SIZE 60

#define PLAYLIST_IN_PATH "playlist.txt"
#define PLAYLIST_OUT_PATH "playlist-out.txt"
// To avoid unnecessary complexity, we fix the filenames instead of getting them
// through runtime parameters.

typedef char Data[TRACK_TITLE_SIZE];
Node *playlist;

/// Removes trailing newline from the line, if it exists.
/// Note: Some lines may not have a newline, e.g., last line in a file,
/// therefore we have to check for presence.
char *remove_newline_if_exists(char *line) {
  // YOUR CODE HERE
  return line;
}

/// Reads lines from at `filename`, creates a node for each line and inserts
/// nodes to `list`.
Node **load_file(const char *filename, Node **list) {
  // Open the file and assign to stream `f`
  // YOUR CODE HERE
  if (!f) {
    perror(PLAYLIST_IN_PATH);
    exit(EXIT_FAILURE);
  }
  char line[TRACK_TITLE_SIZE];

  while (
      // Read one line from the stream
      // YOUR CODE HERE
  ) {
    remove_newline_if_exists(line);

    auto new_node = (Node *)malloc(sizeof(Node));
    new_node->next = nullptr;
    auto data = (Data *)malloc(sizeof(Data));
    new_node->data = data;

    // Copy line to `new_node` and append `new_node` to `list`
    // YOUR CODE HERE
  }
  fclose(f);
  return list;
}

/// Saves `list` contents to the file at `filename`.
void save_file(const char *filename, Node *list) {
  // Open file
  // YOUR CODE HERE

  // Move through the list and save the tracks to the file
  // Note: You have to cast the data to print the track to the file as follows:
  // (char *)current->data
  // Because current->data is a pointer to everything (void*).
  auto current = playlist;
  // YOUR CODE HERE

  fclose(f);
  //// END SOLUTION
}

void print_tracks(const Node *const playlist) {
  auto current = playlist;
  for (size_t i = 1; current; i++, current = current->next)
    printf("%2ld: %s\n", i, (char *)current->data);
}

int main() {
  load_file(PLAYLIST_IN_PATH, &playlist);
  print_tracks(playlist);

  // Deletion
  size_t node_index_to_del = 4;
  free(delete_at(&playlist, node_index_to_del));

  // Insertion
  Node node = {.data = "Tarkan – Şımarık 💋", .next = nullptr};
  insert_at(&playlist, 3, &node);

  save_file(PLAYLIST_OUT_PATH, playlist);
}

singly_linked_list.h

#pragma once
#include <stddef.h>

/**
 * Node of the single list
 * @note Thanks to the `void` pointer the linked list can store any datatype.
 */
typedef struct Node {
  void *data;
  struct Node *next;
} Node;

/**
 * Inserts `node` at the 0-indexed position `n` on the list with the start
 * node`head`.
 * @return `Node *` that has been inserted.
 * @note `head` is a pointer to a pointer, because we need to be
able to modify the head of the provided linked list.
 */
Node *insert_at(Node **head, size_t n, Node *node);

/**
 * @return size of the list
 */
size_t list_len(Node *head);

/**
 * @return node at the index `n`
 */
Node *node_at(Node *head, size_t n);

/**
 * Deletes and deallocates node at index `n`.
 * @return node data
 * @note Data of the node has to be deallocated manually.
 */
void *delete_at(Node **head, size_t n);

/**
 * Deletes and deallocates node at index `n`.
 * @return the node at the tail of the list.
 * @note Can return `nullptr` if the list is empty.
 */
Node *tail(Node *head);

singly_linked_list.c

#include "singly_linked_list.h"
#include <stddef.h>
#include <stdlib.h>

static Node *prev_node_at(Node *head, size_t n) {
  auto current = head;
  Node *prev = nullptr;

  if (current) {
    size_t i = 0;
    while (i != n && current) {
      prev = current;
      current = current->next;
      ++i;
    }
    if (i != n)
      return nullptr;
    else
      return prev;
  }
  return prev;
}

Node *insert_at(Node **head, size_t n, Node *node) {
  if (!n) {
    node->next = *head;
    *head = node;
    return node;
  }
  auto prev_node = prev_node_at(*head, n);
  auto next_node = prev_node->next;
  prev_node->next = node;
  node->next = next_node;
  return node;
}

size_t list_len(Node *head) {
  auto current = head;

  if (current) {
    size_t len = 1;
    while ((current = current->next)) {
      ++len;
    }
    return len;
  }
  return 0;
}

Node *node_at(Node *head, size_t n) {
  auto current = head;

  for (size_t i = 0; i < n;) {
    if (current) {
      current = current->next;
      ++i;
    } else
      return nullptr;
  }
  return current;
}
// Node *node_idx(Node *head, size_t n);

void *delete_at(Node **head, size_t n) {
  auto current = *head;
  if (!n) {
    if ((*head)->next)
      *head = current->next;
    else
      *head = nullptr;

    return nullptr;
  } else {
    auto prev = prev_node_at(*head, n);
    auto node_to_be_deleted = prev->next;
    prev->next = node_to_be_deleted->next;

    auto data = node_to_be_deleted->data;
    free(node_to_be_deleted);
    return data;
  }
}

Node *tail(Node *head) {
  auto current = head;
  if (current) {
    auto next = current->next;
    while (next) {
      current = current->next;
      next = current->next;
    }
    return current;
  }
  return current;
}