// An example solution to Programming Assignment 3.
//
// CS 306, Computer Algorithms II, Fall 2007


#include <iostream>
#include <cstdlib>
#include <vector>
#include <sstream>


struct guest_name
  std::string first_name, last_name


static const unsigned guest_list_size = 9


typedef std::vector<guest_name> seating_list
typedef seating_list::const_iterator seats_citer


typedef std::vector<std::string> string_list


struct guest
  guest_name name
  string_list interests
  string_list acquaintences


typedef std::vector<guest> guest_list


// Deja vu c++ style.

   static guest_list read_guests(std::istream &)
   static void output_seating(std::ostream &, const seating_list &)
   static seating_list seat_guests(const guest_list &)
   static bool read_next_nonblank_line(std::istream &, std::string &)
   static void oops(const std::string &)
   static string_list read_words(std::istream &)
   static bool member(const std::string &, const string_list &)
   static bool nonempty_intersection(const string_list &, const string_list &)


static bool
compatible(const guest & g1, const guest & g2)

  // Return true iff the given guests are compatible.

  return 
    nonempty_intersection(g1.interests, g2.interests) and 
    member(g1.name.last_name, g2.acquaintences) and
    member(g2.name.last_name, g1.acquaintences)


static bool
compatible_seating(const guest_list & guests)
  
  // Return true iff the given seating list is compatible.

  const unsigned n = guests.size()

  for unsigned i = 0; i < n; i++
    if not compatible(guests[i], guests[(i + 1) % n])
      return false

  return true


static bool
is_blank_line(const std::string & str)

  // Return true iff the given string is blank.

  return str.find_first_not_of(" \t\n") == std::string::npos


int 
main()

  guest_list guests = read_guests(std::cin)

  if guests.size() != guest_list_size
    std::ostringstream oss
    oss << "A guest list of size " << guest_list_size << " expected, "
	<< "a guest list of size " << guests.size() << " entered"
    oops(oss.str())

  output_seating(std::cout, seat_guests(guests))


static bool
member(const std::string & str, const string_list & strings)

  // Return true iff the given string is in the given string list.

  for unsigned i = 0; i < strings.size(); i++
    if strings[i] == str
      return true

  return false


static bool
nonempty_intersection(const string_list & strs1, const string_list & strs2)

  // Return true iff the given string lists have an string in common.

  for unsigned i = 0; i < strs1.size(); i++
    if member(strs1[i], strs2)
      return true

  return false


static void
oops(const std::string & emsg)

  // print the given error message to std::err and and die.

  std::cerr << "! " << emsg << ".\n"
  exit(EXIT_FAILURE)


static void
output_seating(std::ostream & os, const seating_list & seats)

  // Output to the given output stream the given seating list.

  for seats_citer i = seats.begin(); i != seats.end(); i++
    os << i→first_name << " " << i→last_name << "\n"


static guest
read_guest(const std::string & str)

  // Read a guest from the given string; return the guest read.  Die with an
  // error if anything untoward happens.

  const size_t comma = str.find(',')
  if std::string::npos == comma
    oops("Guest missing a comma between interests and acquaintences")

  std::istringstream iss(str.substr(0, comma))
  guest g

  if not (iss >> g.name.first_name)
    oops("A guest has no name")
  if not (iss >> g.name.last_name)
    oops("A guest has only one name")

  g.interests = read_words(iss)

  iss.clear()
  iss.str(str.substr(comma + 1))
  g.acquaintences = read_words(iss)

  return g


static guest_list
read_guests(std::istream & is)

  // Read a guest list from the given input stream; return the list.  Die with
  // an error message if anything untoward happens.

  guest_list guests
  std::string str

  while read_next_nonblank_line(is, str)
    guests.push_back(read_guest(str))
  
  return guests


static bool
read_next_nonblank_line(std::istream & is, std::string & str)

  // Read the next non-blank line from the given input stream; store the string
  // read in the given reference and return true.  If there are no more
  // non-blank strings to read, return false.

  do
    if not std::getline(is, str)
      return false
  while is_blank_line(str)

  return true


static string_list
read_words(std::istream & is)

  // Read words from the given input stream; return the words read in a string
  // list.

  string_list words
  std::string word

  while is >> word
    words.push_back(word)

  return words


static bool
seat_guests(guest_list guests, unsigned i, seating_list & seats)

  // Permute the elements in guests[i..guests.size()-1] into a compatible
  // seating arrangement.  If successful, store the seating arrangment in the
  // given seating list and return true; otherwise return false (in which case
  // the contents of seats is undefined).

  if guests.size() - 1 == i
    seats.at(i) = guests.at(i).name
    return compatible_seating(guests)

  for unsigned j = i + 1; j < guests.size(); j++
    if seat_guests(guests, i + 1, seats)
      seats.at(i) = guests.at(i).name
      return true
    std::swap(guests[i], guests[j])

  return false


static seating_list
seat_guests(const guest_list & guests)

  // Find an acceptable seating list for the guests in the given list; return
  // the seating list found.  If no acceptable seating list exists, the
  // returned seating list will be empty.

  seating_list seats(guest_list_size)

  return seat_guests(guests, 0, seats) ? seats : seating_list()


// $Log:$