#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

void print_song_titles( const map< string, int >& m, bool show )
{
  map< string, int>::const_iterator i;
  for ( i = m.begin() ; i != m.end() ; i++ ) {
    cout << i->first;
    if ( show ) {
      cout << " (" << i->second << " seconds)";
    }
    cout << '\n';
  }
}

// using an iterator, print song titles in reverse order
// -- print "<empty>" if the list is empty
// -- print song durations only if the show variable is true
void
print_song_titles_reverse( const map< string, int >& m, bool show )
{
  if ( m.size() == 0 ) {
    cout << "<empty>\n";
  } else {
    map< string, int >::const_iterator i;
    i = m.end();  // BEYOND the last element in the map
//    i--;
//    for ( ; i != m.begin() ; i-- ) { .... }
    do {
      i--;
      cout << i->first;
      if ( show ) {
        cout << " (" << i->second << " seconds)";
      }
      cout << '\n';
    } while ( i != m.begin() );
  }
}

// Add the song referred to by the map iterator to the playlist
// -- be sure to add both the song title and duration
// -- if the song title already exists, replace it (i.e. remove it)
// -- regardless of whether added or replaced, the song should
//    be added to the end of the playlist
void
add_to_playlist( const map< string, int >::const_iterator& i,
                 vector< pair< string, int > >& playlist )
{
  bool found = false;
  unsigned int loc = 0;
  while ( !found && loc < playlist.size() )
  {
    found =  ( playlist[loc].first == i->first );
    if ( !found ) {
      loc++;
    }
  }

#if 0
// another approach using an iterator on the vector
  vector< pair< string, int > >::iterator j;
  for ( j = playlist.begin() ; !found && j != playlist.end() ; j++ ) {
    found =  ( j->first == i->first );
  }
#endif

  if ( found ) {
    // remove old occurrence
    playlist.erase( playlist.begin() + loc ); // vector iterator arithmetic
//  playlist.erase( j );
  }

  playlist.push_back( *i );
}

// using an iterator, print the given playlist
// -- format the output to match the print_song_titles() function
void
print_playlist( vector< pair< string, int > >& playlist )
{
  vector< pair< string, int > >::iterator j = playlist.begin();
  while ( j != playlist.end() )
  {
    cout << j->first << " (" << j->second << " seconds)\n";
//    playlist[loc].first
    j++;
  }
}

int main()
{
  // maps song titles to their
  //   duration (in seconds)
  map< string, int > durations;

  durations[ "Cold Day" ] = 191;
  durations[ "Tinted Glass" ] = 256;
  durations[ "Borderline" ] = 189;
  durations[ "Robin in the Snow" ] = 300;

  print_song_titles( durations, true );
  print_song_titles_reverse( durations, true );

  string song_title = "Robin in the Snow";
  int x = durations[ song_title ] + 3 + durations[ "Cold Day" ];
  cout << "x is: " << x << '\n';

  x += 3 + durations[ "Fly Away" ];
  cout << "x is: " << x << '\n';

  print_song_titles( durations, true );
  print_song_titles_reverse( durations, true );

  vector< pair< string, int > > playlist;
  map< string, int >::iterator i;
  for ( i = durations.begin() ; i != durations.end() ; i++ ) {
    add_to_playlist( i, playlist );
  }

  cout << "\nPLAYLIST:\n";
  print_playlist( playlist );

  i = durations.find( "Fly Away" );
  i->second = 246;
  add_to_playlist( i, playlist );

  cout << "\nNEW PLAYLIST:\n";
  print_playlist( playlist );

  return 0;
}