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


#include <iostream>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cctype>


// Both the portfolio and the current share prices can be represented by the
// same data structure.


   struct triple {
     double x, y, z;
     triple() : x(0), y(0), z(0) { }
     triple(double x, double y, double z) : x(x), y(y), z(z) { }
     };


// One problem with using double values (floating-point values in general) is
// they are inexact, and it is frequently difficult to determine both when and
// how the values are inexact.  One pratical consiquence of these difficulties
// is that direct comparisons between double values usually don't work as
// expected.  The following comparison routines get around this problem by
// assuming that two double values that are within a penny of each other are
// close enough.


   static bool equal(double a, double b) {
     const double d = a - b;
     return (-0.01 < d) && (d < 0.01);
     }

   static bool greater(double a, double b) {
     return 0.01 < (a - b);
     }

   static double min(double a, double b) {
     return greater(a, b) ? b : a;
     }


// Return the value of a portfolio given a set of share prices.

   static double portfolio_value(const triple & portfolio, const triple & prices) {
     return portfolio.x*prices.x + portfolio.y*prices.y + portfolio.z*prices.z;
     }


// Given a portfolio and a set of share prices, return a new portfilio
// containing the old portfolio plus the monthly amount worth of shares bought
// according to strategy s.


   static triple strategy_s(
     double monthly_amount,
     const triple & percentages,
     const triple & prices, 
     const triple & portfolio) {

     triple p;

     p.x = portfolio.x + (monthly_amount*percentages.x)/prices.x;
     p.y = portfolio.y + (monthly_amount*percentages.y)/prices.y;
     p.z = portfolio.z + (monthly_amount*percentages.z)/prices.z;

     return p;
     }


// Strategy c repeatedly reduces the largest difference in actual-ideal value
// percentages until there are either no more differences or no more money.
//
// The code implementing stragegy c follows the description: loop until there's
// no more money.  In each loop, find the largest percentage difference, spend
// as much money as possible to eliminate it, and add the shares to the
// portfolio.  If there are no differences - that is, the actual value
// percentages are ideal - use stragegy s to spend the rest of the money (which
// must be there, otherwise the loop wouldn't be iterating).  When the loop
// terminates, return the new portfolio.
//
// The trick is in the differences - not computing them, but using them.  The
// percentage difference for X, for example, can be computed as
//
//   Dx = Ix - Vx/Vp
//
// where Dx is the percentage difference for x,
//       Ix is the ideal percentage for x,
//       Vx is the dollar value of X in the current portfolio, and
//       Px is the dollar value of the total current portfolio.
//
// Unfortunatley, you can't use Dx*Vp to determine the dollar amount of X
// shares to buy because Dx is a percentage relative to the current portfolio
// value and we need a percentage relative to the expected portfolio value
// after the shares have been bought.
//
// To understand why Dx doesn't work, consider a simple example where Vx = $0
// and Vp = $100.00.  Dx is 0.5 - 0/100.00 = 0.5, which means buy $100.00*0.5 =
// $50.00 worth of X.  But if we add $50 shares of X to the portfolio, the new
// value for Dx is 0.5 - 50.00/150.00 = 0.5 - 0.33 = 0.23, not quite what we
// wanted.
//
// What we need to know is not the percentage of the total portfolio value
// before we buy the stocks, but the percentage of the total portfolio value
// after we buy the stocks; that is, find Bx in
//
//   (Vx + Bx)/(Vp + Bx) = Ix
//
// where Bx is the dollar value of X shares to buy.  This can be rearranged to
//
//   Bx = (Ix*Vp - Vx)/(1 - Ix)


   static triple strategy_c2(
     double monthly_amount,
     const triple & percentages,
     const triple & prices, 
     triple portfolio) {

     while (!equal(monthly_amount, 0)) {

       const double total = portfolio_value(portfolio, prices);

       double max_difference = (0.5*total - portfolio.x*prices.x)/(1.0 - 0.5);
       char max = 'x';

       double d = (0.3*total - portfolio.y*prices.y)/(1.0 - 0.3);
       if (greater(d, max_difference)) {
	 max_difference = d;
	 max = 'y';
	 }

       d = (0.2*total - portfolio.z*prices.z)/(1.0 - 0.2);
       if (greater(d, max_difference)) {
	 max_difference = d;
	 max = 'z';
	 }

       if (equal(max_difference, 0))
	 return strategy_s(monthly_amount, percentages, prices, portfolio);
       else {
	 const double amt = min(monthly_amount, max_difference);
	 monthly_amount -= amt;

	 if (max == 'x')
	   portfolio.x += amt/prices.x;
	 else if (max == 'y')
	   portfolio.y += amt/prices.y;
	 else 
	   portfolio.z += amt/prices.z;
	 }
       }

     return portfolio;
     }


// That was pretty ugly: lots of iterations, calculations, and testing - all in
// all, it's complex.  You should learn to complexity as an indicator that
// something's wrong: either you don't understand the problem, or the design is
// lacking, or the implementation is using the wrong tools.
//
// In this case, code complexity means the design is lacking.  There are two
// problems with basing a solution on calculating Bi.  First, Bi doesn't get us
// where we want to be; rather than completely eliminating the difference
// between the two actual and ideal value percentages, it reduces it.  Second,
// Bi is based on the current portfolio value; every time that changes, the Bi
// values need to be recalculated.  Not surprisingly, code based on using Bi is
// going to require a lot of calculations and a lot of iterations.
//
// Is there a better way?  One way to look a solution based on Bi is that it
// starts at the beginning and stops at the end; that is, c2() starts with the
// current portfolio value and stops when the current monthly amount has been
// added to the portfolio.  One obvious alternative is to go in the other
// direction: start with the current portfolio value that includes the monthly
// amount.
//
// One immediate advantage provided by the alternative is a constant portfolio
// value: portfolio value is going to increase by the monthly amount no matter
// how the stocks are bought, which should cut down on a lot of recalculation
// caused by changing protfolio values.
//
// How many shares of each stock to buy?  Again, starting at where we'd like to
// end up, the value of X shares should be
//
//   Vx = Ix(Vp + M)
//
// where Vx is the final value of X shares in the protfolio, Vp is the current
// portfilio value, and M is the monthly amount.  To make that be true we need
// to buy shares of X equal to
//
//   Vx - Sx*Px
//
// where Sx is the number of shares of X in the current portfolio and Px is the
// current X share price.


   static triple strategy_c(
     double monthly_amount,
     const triple & percentages,
     const triple & prices, 
     const triple & portfolio) {

     triple p = portfolio;
     const double total = portfolio_value(p, prices) + monthly_amount;

     while (!equal(monthly_amount, 0)) {

       double max_difference = total*percentages.x - p.x*prices.x;
       char max = 'x';

       double d = total*percentages.y - p.y*prices.y;
       if (greater(d, max_difference)) {
	 max_difference = d;
	 max = 'y';
	 }

       d = total*percentages.z - p.z*prices.z;
       if (greater(d, max_difference)) {
	 max_difference = d;
	 max = 'z';
	 }

       if (equal(max_difference, 0)) {
	 p = strategy_s(monthly_amount, percentages, prices, p);
	 break;
	 }
       else {
	 const double amt = min(monthly_amount, max_difference);
	 monthly_amount -= amt;

	 if (max == 'x')
	   p.x += amt/prices.x;
	 else if (max == 'y')
	   p.y += amt/prices.y;
	 else 
	   p.z += amt/prices.z;
	 }
       }

     return p;
     }


// Input, as usual, is a pain not because it's difficult, but becuase there's a
// lot of little details to keep straight.  However, the pain of writing a
// correct input routine can be minimized by dividing the routine into smaller,
// well-defined pieces that follow the structure of the input problem.
//
// Assume for the moment we have available for use a procedure
//
   static bool read_price(std::istream &, double &);
//
// that reads a double from an input stream and a procedure
//
   static bool skip_space(std::istream &);
//
// that eats space characters from an input stream.  Using these procedures
// makes reading a triple of prices on a line in an input stream is relatively
// striaghtforward:


   static bool read_prices(std::istream & is, triple & prices) {

     if (!read_price(is, prices.x)) {
       if (is.eof()) return false;
       std::cerr << "Input error while reading X price.\n";
       exit(EXIT_FAILURE);
       }

     if (!read_price(is, prices.y)) {
       std::cerr << "Input error while reading Y price.\n";
       exit(EXIT_FAILURE);
       }

     if (!read_price(is, prices.z)) {
       std::cerr << "Input error while reading Z price.\n";
       exit(EXIT_FAILURE);
       }

     if (!skip_space(is) && !is.eof()) {
       std::cerr << "Junk at end of input line.\n";
       exit(EXIT_FAILURE);
       }

     return true;
     }


// If a price is missing, the input is incorrect - except when the first price
// is missing due to eof, which is fine because input must end sometime.  In
// all other cases, a missing price - even due to eof - is an error.
//
// In addition, there should no non-space characters between the third price
// and the end of the line; if there is, it's another input error.
// 
// The way these routines deal with input errors is not very good - programs
// that give up and die on the first error are not considered reliable or
// pleasant to use.  However, correctly recovering from errors is not easy to
// do and it adds much complexity to the code.  Because there's only a finite
// amount of time avaialble to work on these assignments, it is better to make
// sure errors get caught, and then spend the time making sure the program
// works correctly when the input is correct.

// Read into price the next double value from the text line in the input stream
// ins.  Return true if a double was read, false otherwise.


   static bool read_price(std::istream & is, double & price) {

     if (skip_space(is) || is.eof())
       return false;

     is >> price;
     if (!is.good()) {
       std::cerr << "Input error while reading a price.\n";
       exit(EXIT_FAILURE);
       }

     return true;
     }


// And finaly, read and eat space characters from the text line in the input
// stream ins until either a newline is read and eaten, the next character from
// ins would be a non-space character, or ins has no more characters.  Return
// true if a newline was eaten, false otherwise.


   static bool skip_space(std::istream & ins) {

     while (true) {
       const char ch = ins.peek();
       if (ins.eof() || !isspace(ch)) return false;
       (void) ins.get();
       if (ch == '\n') return true;
       }
     }


// More complexity, this time in the number of procedures necessary.  What's
// wrong now?  The input needed is simple, so it's unlikely we don't understand
// that.  The design doesn't have any obvious (to me) flaws:  there's a lot of
// parts involved, but each part is simple, as is the relation among the parts.
// That leaves the implementation tools.
//
// The standard C++ libraries include <sstream>, a facility to do stream io to
// and from strings.  Using <sstream> eliminates the auxiliary routines needed
// above, but only reduces the complexity of the remaining routine.
//
// For the record, here's the <sstream> implementation of price input:

#  include <sstream>
#  include <string>

   static bool read_prices2(std::istream & ins, triple & prices) {

     std::string s;
     if (!std::getline(ins, s)) return false;

     std::istringstream sin(s);

     if (!(sin >> prices.x)) {
       std::cerr << "Input error while reading X price.\n";
       exit(EXIT_FAILURE);
       }

     if (!(sin >> prices.y)) {
       std::cerr << "Input error while reading Y price.\n";
       exit(EXIT_FAILURE);
       }

     if (!(sin >> prices.z)) {
       std::cerr << "Input error while reading Z price.\n";
       exit(EXIT_FAILURE);
       }

     char c;
     if (sin >> c) {
       std::cerr << "Junk at end of input line.\n";
       exit(EXIT_FAILURE);
       }

     return true;
     }


// The last test takes advantage of the space-eating behavior of i-o stream
// input.


// Output is straightforward, except for two potential problems when computing
// precentages.  First, if the portfolio is empty, there's no percentages to
// compute; this can be dealt with by a test for zero portfolio value.  Second,
// the percentages have to sum to 100, which means the code has to keep track
// of the round-off error to make sure it doesn't accumulate.  Fortunately,
// this is not as complicated to do as it sounds because each integer
// percentage already contains the round-off error (the round-off error is what
// makes it an integer).  Not only does this handle the round-off error
// properly (subtracting the overages and adding the underages) but it makes it
// clear that the three percentages sum to 100.
// 
// A third problem, with which this code doesn't deal, is formatting the output
// nicely.  Doing so would involve the ridiculusly complicated i-o stream
// manipulators, and it just isn't worth the effort.  However, to avoid
// excessive precision, the portfolio value is rounded to the nearest penny.


   static int pct(double n, double d) {
     return equal(d, 0) ? 0 : static_cast<int>((n/d + 0.005)*100);
     }

   static void print_portfolio(
     std::ostream & os,
     const char type[],
     const triple & portfolio,
     const triple & prices) {

     const double total = portfolio_value(portfolio, prices);

     const int xpct = pct(portfolio.x*prices.x, total);
     const int ypct = pct(portfolio.y*prices.y, total);

     os << type 
	<< " " << xpct 
	<< " " << ypct
	<< " " << (equal(total, 0) ? 0 : 100 - (xpct + ypct))
	<< " " << static_cast<double>(static_cast<int>((total*100) + 0.5))/100 
	<< "\n";
     }


// And that's it.


   int main() {

     const triple percentages(0.5, 0.3, 0.2);
     const double monthly_amount = 2500.00;

     triple prices,
	    portfolio_s,
	    portfolio_c;

     while (read_prices2(std::cin, prices)) {
       portfolio_s = strategy_s(monthly_amount, percentages, prices, portfolio_s);
       portfolio_c = strategy_c(monthly_amount, percentages, prices, portfolio_c);
       }

     print_portfolio(std::cout, "c", portfolio_c, prices);
     print_portfolio(std::cout, "s", portfolio_s, prices);
     }