Homework4

[Homework 4 is due on Jul 26 (Tue) at 11:59pm]

Problem: Song Playlist Manager

Please use the starter files here and read the directions below.

As we have learned in class, splay trees are a self-adjusting binary search tree that allows one to achieve fundamental operations with an average complexity of O(log n).

Here is a hypothetical scenario for your consideration. You have been hired as an engineer to improve the iTunes music search.  Previously, the iTunes library used a binary search tree, but it was not self-balancing, which lead to performance spikes in the search.

Help Apple defeat Microsoft’s Windows Media Player by building a splay tree that will allow the software to incrementally search for music in log(n) time by implementing the splay tree.

Part 1: File I/O [Already given]

The following sample input file contains a list of musicians and some of their songs.

music.txt

You will be performing the following basic operations:

• Read the file.

• Parse each line of the file.

• Store each of artist and their associated songs in a node structure.

• Close the loaded file

Input File (music.txt) format:

• The artist and the song are separated by a dash

• Artist names can have alphanumeric characters

Part 2: Managing the Splay tree updates [Your responsibility]

Your splay tree supports the following operations:

  • Insert a new musician (and a song that is associated with that node). If the musician already exists, add the song to the list of songs associated with the musician.
  • Delete a musician.
  • Search for a musician: If the musician exists, return the exact match. Otherwise, return the closest result. Hint: The closest match is the last node you traversed before reaching NULL, or another node nearby.
  • Output the playlist of songs in the sorted order of musicians.
  • The intermediate splay trees are dumped in the GraphViz format. This will allow you to visualize the balancing operations. You will be evaluated based on how the splay operations get reflected in these intermediate dumps.

You are responsible for implementing the splay() operations.


 

Expected Outputs:

Note the generation of splay_tree*.dot files, which track the result of splay operations. You have been given a small music list (music1.txt) and a reasonably large music list (music.txt) to test your program.


 

With test input music1.txt:

Command: ./songmanager music1.txt

Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
4
Sorted List:
christina aguilera: beautiful
crystals: then he kissed me
good charlotte: anthem | anthem 2
hootie and the blowfish: let her cry
kc & jojo: all my life
natasha bedingfield: pocket full of sunshine
owl city: fireflies
rehab: bartender
sugar ray: falls apart
Done.
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): kc
Approximate matches:
Artist: hootie and the blowfish
Songs: let her cry
Artist: kc & jojo
Songs: all my life
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
3
Remove what (Enter artist name): good charlotte
Done.
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
4
Sorted List:
christina aguilera: beautiful
crystals: then he kissed me
hootie and the blowfish: let her cry
kc & jojo: all my life
natasha bedingfield: pocket full of sunshine
owl city: fireflies
rehab: bartender
sugar ray: falls apart
Done.
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): crystals
Accurately matched!
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
0
Exiting…

Expected Result: The intermediate files (output of splaying after every operation) must match the files here.


 

With test input music.txt:

Command: ./songmanager music.txt

Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): christina
Approximate matches:
Artist: chris isaak
Songs: wicked game
Artist: christina aguilera
Songs: beautiful | genie in a bottle
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
3
Remove what (Enter artist name): christina aguilera
Done.
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): christina aguilera
Approximate matches:
Artist: chris isaak
Songs: wicked game
Artist: chumbawumba
Songs: beautiful | genie in a bottle
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
1
Artist: enya
Music: a day without rain
Done.
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): enya
Accurately matched!
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): en
Approximate matches:
Artist: elvis presley
Songs: hound dog | jailhouse rock | suspicious minds
Artist: enrique iglesias
Songs: be with you | bailamos | i like it | hero
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
2
Find what (Enter artist name): eny
Approximate matches:
Artist: enrique iglesias
Songs: be with you | bailamos | i like it | hero
Artist: enya
Songs: a day without rain
Input choices:
* Insert (1)
* Find (2)
* Remove (3)
* Print sorted (4)
* Exit(0)
0
Exiting…

Expected Result: The intermediate files (output of splaying after every operation) must match the files here.


 

Hints:

  • You can derive SplayTree from BST and then do the needful in the SplayTree. For example,  SplayTree::find() could be written as follows:
 // Find a node in the BST containing the given key
  BSTNode* SplayTree::find(int aKey)
  {
    BSTNode* node = BST::find(aKey);
    if (node != NULL) {
      // Splay the node that is found or the node where the search ended
      splay(node);
    }
    return node;
  }
  • If you are confused about how to implement the Splay tree, here are some sample functions from the SplayTree class:
  /// Zig rotation -- left to right
  /// Scenario: aNode is a left child of root
  void SplayTree::zigLR(BSTNode* aNode, BSTNode* aParent)
  {
    BSTNode* rightChild = aNode->right();
    aNode->setRight(aParent);
    aParent->setParent(aNode);
    aParent->setLeft(rightChild);
    if (rightChild != NULL) {
      rightChild->setParent(aParent);
    }
    // Set the new root
    if (root() == aParent) {
      setRoot(aNode);
      aNode->setParent(NULL);
    }
  }

  /// Zigzag rotation --
  /// around parent from left to right
  /// around grandparent from right to left
  /// Scenario: aNode is a left child of a right child
  void SplayTree::zigLRzagRL(BSTNode* aNode, BSTNode* aParent, BSTNode* aGrandParent)
  {
    BSTNode* ggParent = aGrandParent->parent();
    SplayTree::Orientation orient = SplayTree::NONE;
    if (ggParent != NULL) {
      if (ggParent->left() == aGrandParent) {
        orient = SplayTree::LEFT;
      } else {
        orient = SplayTree::RIGHT;
      }
    }
    // Rotate around the parent from left to right
    zigLR(aNode, aParent);
    // Rotate around the grandparent from right to left
    zigRL(aNode, aGrandParent);
    if (orient == SplayTree::LEFT) {
      ggParent->setLeft(aNode);
      aNode->setParent(ggParent);
    } else if (orient == SplayTree::RIGHT) {
      ggParent->setRight(aNode);
      aNode->setParent(ggParent);
    }
  }

  /// Splay operation
  void SplayTree::splay(BSTNode* aNode)
  {
    BSTNode* parent = aNode->parent();
    if (parent == NULL) {
      return;
    }
    BSTNode* grandParent = parent->parent();
    while (parent != NULL &&
           grandParent != NULL) {
      // All zigzag and zigzig operations go here      
      ...
      // Evaluate new parent and grandparent after rotations
      parent = aNode->parent();
      if (parent == NULL) {
        break;
      }
      grandParent = parent->parent();
      if (grandParent == NULL) {
        break;
      }
    }
    // Zig operation is done only as a last pass
    // after Zigzig and/or Zigzag operations
    if (grandParent == NULL) {
      // Parent is the root -- Zig operation
      if (parent->left() == aNode) {
        // aNode is a left child of root
        // Zig operation
        zigLR(aNode, parent);
      } else {
        // aNode is a right child of root
        // Zig operation
        zigRL(aNode, parent);
      }
    }
  }