// Example solution to programming assignment 5.
// CS 509, Spring 2002.

#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>

typedef std::pair<int, int> int_pair;

//
// This code needs to keep track of the indices of the pairs selected for the
// subset.  One way to do this is to add the index to the pair, creating a
// triple.  As the triple gets moved around, so does the index.
//

struct triple {
  int first, second;
  unsigned indx;
  triple(int f, int s, unsigned i = 0) : first(f), second(s), indx(i) { }
  };

typedef std::vector<triple> itrio_vec;

//
// Given a vector of pairs, this code needs to create a vector of triples.
// This can be done with the STL generic algorithm transform(), in conjunction
// with the functor p2t that turns a pair into a triple.  The indicies are
// assigned to pairs in left to right order (that is from begin() to end()).
//

struct p2t {
  unsigned indx;
  p2t() : indx(0) { }
  triple operator () (int_pair p) {
    return triple(p.first, p.second, indx++);
    }
  };

//
// Deja vu, c++ style.
//

static unsigned difference_sum(const itrio_vec &);
static int first_sum(const itrio_vec &);
static bool operator > (const itrio_vec &, const itrio_vec &);
static triple trio_sum(const itrio_vec &);
static int second_sum(const itrio_vec &);
static void select(itrio_vec, itrio_vec &, itrio_vec, unsigned);
static int total_sum(const itrio_vec &);
static unsigned get_index(const triple &);

//
// The actual code to find an acceptable subset is stupid: it's a brute force
// search through all possible subsets.
//

std::vector<unsigned>
pick_pairs(const std::vector<int_pair> & pairs, unsigned n) {

  // If the subset size is larger than the input set size, die with an error
  // message.

     if (pairs.size() < n) {
       std::cerr << "The subset size " << n << " is larger than the pair set "
		 << "size " << pairs.size() << ".\n";
       exit(EXIT_FAILURE);
       }

  // Turn the pairs into triples, using the pair index as the third element.

     itrio_vec trios;
     std::transform(
       pairs.begin(), pairs.end(), std::back_inserter(trios), p2t());

  // select() needs a best subset so it has something to compare the current
  // subset against.  Arbitrarily select the first n elements of the input set
  // as the best subset.

     itrio_vec current_subset, best_subset;
     std::copy(trios.begin(), trios.begin() + n,
	       std::back_inserter(best_subset));

  // If the subset size is less then the input set size, generate all possible
  // n-element subests of the input set and compare each one against the best
  // n-element subset found so far.

     if (pairs.size() > n)
       select(current_subset, best_subset, trios, n);

  // Having been compared against all possible n-element subsets, best_subset
  // now really does contain the best possible subset (or among the best).
  // Copy the indices from the triples to a vector and return the vector.

     std::vector<unsigned> indxs;

     std::transform(best_subset.begin(), best_subset.end(),
		    std::back_inserter(indxs), get_index);

     return indxs;
  }

//
// This is the usual recursive algorithm for generating subsets.  
//

static void 
select(
  itrio_vec current_subset, itrio_vec & best_subset, itrio_vec set, unsigned n) {

  // If the current subset has the proper number of elements, compare it
  // against the best subset and take it as the new best subset if it's better.
  // In any case, return immediately because the current subset can't grow any
  // larger and still be a valid answer.

     if (current_subset.size() == n) {
       if (current_subset > best_subset)
	 best_subset = current_subset;
       return;
       }

  // The current subset has less than n elements.  If the input set is empty,
  // there's nothing left to do.

     if (set.empty())
       return;

  // Otherwise, pick an arbitrary element t of the input set as a candidate
  // element for the current subset.

     triple t = set.back();
     set.pop_back();

  // The element t either is or is not part of the best subset for this
  // problem.  Because we don't know which one, we have to check both
  // possibilities, first without and then with.

     select(current_subset, best_subset, set, n);
     current_subset.push_back(t);
     select(current_subset, best_subset, set, n);

  }

//
// Return the difference sum of the triples in the input vector.
//

static unsigned
difference_sum(const itrio_vec & tv) {
  const int d = first_sum(tv) - second_sum(tv);
  return d < 0 ? -d : d;
  }

//
// Return the sum of the first elements of the triples in the input vector.
//

static int
first_sum(const itrio_vec & tv) {
  return trio_sum(tv).first;
  }

//
// Return the index part of the input triple.
//

static unsigned
get_index(const triple & t) {
  return t.indx;
  }

//
// Return true if and only if triple vector tv1 is a better subset than triple
// vector tv2, where "better" is defined in the assignment.  This code assumes
// the input vectors are properly sized.

static bool
operator > (const itrio_vec & tv1, const itrio_vec & tv2) {
  return (difference_sum(tv1) < difference_sum(tv2)) or
         ((difference_sum(tv1) == difference_sum(tv2)) and
	  (total_sum(tv1) > total_sum(tv2)));
  }

//
// Return the sum of triples it1 and it2; the indices of the triples don't
// matter.
//

static triple
operator + (const triple & it1, const triple & it2) {
  return triple(it1.first + it2.first, it1.second + it2.second);
  }

// 
// Return the sum of the triples in the input vector.
//

static triple
trio_sum(const itrio_vec & tv) {
  return std::accumulate(tv.begin(), tv.end(), triple(0, 0), operator +);
  }

// 
// Sum the triples in the input vector and return the second component of the
// sum.
//

static int
second_sum(const itrio_vec & tv) {
  return trio_sum(tv).second;
  }

//
// Return the total sum of the input vector.
//

static int
total_sum(const itrio_vec & tv) {
  return first_sum(tv) + second_sum(tv);
  }

// $Log: pp.cc,v $
// Revision 1.4  2002/04/18 17:17:53  rclayton
// Do the documentation thing.
//
// Revision 1.3  2002/03/26 19:33:29  rclayton
// Generate the best subset as n past begin(), not n past end().
//
// Revision 1.2  2002/03/26 16:34:41  rclayton
// Rewrote to use the subset generating solution.
//