// SAMPLE CODE ILLUSTRATING ONE METHOD FOR TEMPORARY-ELIMINATION IN EXPRESSIONS
// USING USER-DEFINED CLASSES


#include <iostream.h>

// DIFFERENTIATE LazyOps (DEFINED BELOW) AND OTHER TYPES

template <class Type> int isLazy(const Type&) { return '\000'; }

// IS SIMPLE OBJECT expr A REFERENCE TO OBJECT result???
// NEED TO KNOW THIS IN evaluateInto() IN ORDER TO INJECT A TEMPORARY
// WHEN A LazyOp REFERS TO THE result OBJECT
// IE: a = a * b WILL (USUALLY) REQUIRE A TEMPORARY COPY OF a
//     SO THAT PARTS OF a AREN'T REASSIGNED (ON THE LEFT) BEFORE 
//     THEY'RE EVALUATED (ON THE RIGHT) %-)

template <class Type>
bool references(const Type& expr, const Type& result) { return &expr==&result; }


// LAZY OPERATION CLASS

template <class Arg1, class Op, class Arg2>
class LazyOp
{
public:
	typedef Arg1	   Arg1Type;
	typedef Arg2	   Arg2Type;
	typedef Op  	   OpType;
	typedef Op::Result ResultType;

	LazyOp(const Arg1& a1, const Arg2& a2) : arg1(a1), arg2(a2) {}

// CONVERSION TO RESULT TYPE ALLOWS LazyOp TO BE USED
// WHEREVER ORIGINAL OP WAS AN rvalue

	operator ResultType (void) const
	{ ResultType result; evaluateInto(*this,result); return result; }

// STORE THE TWO OPERANDS (SINCE THE OPERATOR IS PRESUMED TO
// BE STATE-FREE, IT NEED NOT BE STORED)

	const Arg1& arg1;
	const Arg2& arg2;

// LazyOps ARE LAZY

	friend isLazy(const LazyOp&) { return '\001'; }

// CHECK THE TWO ARGUMENTS TO SEE IF EITHER REFERENCES THE result

	friend bool references(const LazyOp& expr, const ResultType& result)
	{ return references(expr.arg1,result) || references(expr.arg2,result); }
};

// SHORT CIRCUIT evalaute FOR NON-LAZY EXPRESSIONS

template <class Type>
inline const Type& evaluate(const Type& expr, Type*) { return expr; }

// INLINED evaluate REDUCES THE NUMBER OF LOCAL VARS REQUIRED IN evaluateInto

template <class Arg1, class Op, class Arg2, class ResultType>
inline ResultType evaluate(const LazyOp<Arg1,Op,Arg2>& expr, ResultType*)
{ ResultType result; evaluateInto(expr,result); return result; }


// EVALUATION OF A LazyOP INTO A WAITING OBJECT (result)

template <class Arg1, class Op, class Arg2, class ResultType>
void evaluateInto(const LazyOp<Arg1,Op,Arg2>& expr, ResultType& result)
{
// IF THE LAZY EXPRESSION REFERENCES THE result OBJECT, PLAY IT
// SAFE AND INJECT AN INTERMEDIATE TEMPORARY AT THE TOP LEVEL

	if (references(expr,result)) { result = evaluate(expr,(ResultType*)0); }

// OTHERWISE PASS THE EVALUATED VALUES OF EACH ARGUMENT TO THE OPERATOR

	else switch ((isLazy(expr.arg1)<<1)|isLazy(expr.arg2))
	{
	    case '\003': Op::evaluateInto(evaluate(expr.arg1,(Op::Arg1Type*)0),
			                  evaluate(expr.arg2,(Op::Arg2Type*)0),
				          result);
			 break;

	    case '\002': Op::evaluateInto(expr.arg1,
				          evaluate(expr.arg2,(Op::Arg2Type*)0),
				          result);
			 break;

	    case '\001': Op::evaluateInto(evaluate(expr.arg1,(Op::Arg1Type*)0),
				          expr.arg2,
				          result);
			 break;

	    case '\000': Op::evaluateInto(expr.arg1,expr.arg2,result);
	}
}


// (PARTIAL IMPLEMENTATION OF) MATRIX CLASS WITH LAZY OPERATIONS

#define  foreach(i,j)	for (int i=0;i<4;i++) for (int j=0;j<4;j++)

class Matrix
{
	int elem[4][4];

public:
	Matrix(void) { foreach (i,j) elem[i][j] = 0; }

	Matrix(int v00, int v10, int v20, int v30,	//       i
	       int v01, int v11, int v21, int v31,	//     +--->
	       int v02, int v12, int v22, int v32,	//   j |
	       int v03, int v13, int v23, int v33)	//     V
	{
		#define init(i,j)  elem[i][j] = v##i##j
		init(0,0); init(1,0); init(2,0); init(3,0);
		init(0,1); init(1,1); init(2,1); init(3,1);
		init(0,2); init(1,2); init(2,2); init(3,2);
		init(0,3); init(1,3); init(2,3); init(3,3);
	}

// OUTPUT OPERATOR WILL ALSO HANDLE LAZY OPS BECAUSE OF
// LazyOp::operator ResultType()

friend	ostream& operator<<(ostream& os, const Matrix& m)
	{
		for (int j=0;j<4;j++)
		{
			for (int i=0;i<4;i++) os << m.elem[i][j] << " ";
			os << endl;
		}
		return os;
	}


// STRUCTURE REPRESENTING Matrix ADDITION OPERATOR

	struct Add
	{

// NEED TO DEFINE THESE TO ASSIST TYPE UNIFICATION OF evaluate()

		typedef Matrix Arg1Type;
		typedef Matrix Arg2Type;
		typedef Matrix Result;

// THIS FUNCTION CALLED WHEN THE OPERATOR ACTUALLY NEEDS TO BE EVALUATED

		static void
		evaluateInto(const Matrix& m1, const Matrix& m2, Result& result)
		{
			cout << "called Matrix::Add::evaluate" << endl;
			foreach(i,j)
			{
				result.elem[i][j] = m1.elem[i][j] + m2.elem[i][j];
			}
		}
	};

// STRUCTURE REPRESENTING Matrix MULTIPLICATION OPERATOR

	struct Mul
	{
		typedef Matrix Arg1Type;
		typedef Matrix Arg2Type;
		typedef Matrix Result;

		static void
		evaluateInto(const Matrix& m1, const Matrix& m2, Result& result)
		{
		    foreach(i,j)
		    {
		        result.elem[i][j] = 0;
			for (int k=0;k<4;k++)
			    result.elem[i][j] += m1.elem[k][j] * m2.elem[i][k];
		    }
		}
	};

	typedef LazyOp<Matrix,Add,Matrix>  LazyAdd;
	typedef LazyOp<Matrix,Mul,Matrix>  LazyMul;
	typedef LazyOp<LazyMul,Add,Matrix> LazyMulAdd;

// NORMAL ASSIGNMENT OF MATRICES

	Matrix& operator=(const Matrix& m)
	{ foreach(i,j) elem[i][j] = m.elem[i][j]; return *this; }

// LAZY ADDITION, MULTIPLICATION AND
// (COMPOSITE) MULTIPLY-THEN-ADD OF MATRICES

friend	LazyAdd operator+(const Matrix& m1, const Matrix& m2)
	{ return LazyAdd(m1,m2); }

friend	LazyMul operator*(const Matrix& m1, const Matrix& m2)
	{ return LazyMul(m1,m2); }

friend	LazyMulAdd operator+(const LazyMul& m1, const Matrix& m2)
	{ return LazyMulAdd(m1,m2); }


// THESE OVERLOADINGS ARE NOT ESSENTIAL, BUT THEY ELIMINATE
// TWO Matrix TEMPORARIES WHEN ASSIGNING LAZY OPS.
// NOTE THAT FOR COMPILERS WHICH DON"T SUPPORT TEMPLATE MEMBERS, A SEPARATE
// OVERLOADED OPERATOR FOR EACH RELEVANT LazyOp SPECIALIZATION WOULD BE REQUIRED

	template <class LazyOp>
	Matrix& operator=(const LazyOp& lazyop)
	{ evaluateInto(lazyop,*this); return *this; }

// THIS FUNCTION IS NOT ESSENTIAL BUT IT ELIMINATES _ALL_ Matrix
// TEMPORARIES WHEN DOING COMPOSITE MULTIPLY-THEN-ADDS (SEE main BELOW)

friend	void evaluateInto(const LazyMulAdd& expr, Matrix& result)
	{
		foreach(i,j)
		{
		    result.elem[i][j] = expr.arg2.elem[i][j];
		    for (int k=0;k<4;k++)
		    {
			result.elem[i][j] += expr.arg1.arg1.elem[k][j]
					   * expr.arg1.arg2.elem[i][k];
		    }
		}
	}
};

// TRY IT ALL OUT...

Matrix m1 (1,2,3,4, 0,2,0,0, 0,0,3,0, 0,0,0,4);
Matrix m2 (1,0,0,0, 2,2,0,0, 3,0,3,0, 4,0,0,4);
Matrix m3 (1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1);
Matrix m4;

main()
{
// NOTES: 1. FOR THE FOLLOWING EACH * OR + COSTS 1 LazyOp TEMPORARY
//           HOWEVER, SINCE EACH sizeof(LazyOp) IS (THEORETICALLY)
//	     ONLY 2*sizeof(A REFERENCE) AND SINCE THE LazyOp CTOR SIMPLY
//	     BINDS 2 REFERENCES, THIS OVERHEAD IS NEGLIGIBLE FOR OPERATIONS
//	     ON NON-TRIVIAL CLASS TYPES
//
//	  2. IN THE FOLLOWING ANALYSES, A Matrix TEMPORARY IS CONSIDERED
//	     TO HAVE BEEN INCURRED IF EITHER A TEMPORARY COPY OF A Matrix
//	     OR A LOCAL Matrix VARIABLE IS USED. HENCE THE NUMBER OF Matrix
//	     "TEMPORARIES" IS THE NUMBER OF CTOR CALLS INCURRED IN EVALUATING
//	     THE RHS EXPRESSION. 
//	
//	  3. ALL "TEMPORARIES" COSTS ARE MULTIPLES OF 2, REFLECTING THE
//	     CONSISTENT IDIOM OF CREATING A LOCAL VARIABLE (1 "TEMPORARY") AND
//	     RETURNING A COPY OF IT BY VALUE (A SECOND "TEMPORARY"). AGGRESSIVE
//	     OPTIMIZATION (SUCH AS THE USE OF THE g++ NAMED RETURN VALUES)
//	     WOULD TYPICALLY HALVE THESE COSTS.

// THESE EACH COST _ZERO_ Matrix TEMPORARIES (ASSUMING THE APPROPRIATE
// Matrix::operator=(const Matrix::LazyOp&) IS DEFINED),
// OR 2 Matrix TEMPORARIES OTHERWISE.
// (EQUIVALENT NON-LAZY VERSIONS WOULD COST 2 TEMPORARIES EACH)

	m4 = m1 + m2;
	m4 = m2 * m1;

// BECAUSE m1 IS REFERENCED ON BOTH SIDES OF THE ASSIGNMENT,
// THESE EACH COST 2 Matrix TEMPORARIES (WHETHER OR NOT THE APPROPRIATE
// Matrix::operator=(const Matrix::LazyOp&) IS DEFINED)
// (EQUIVALENT NON-LAZY VERSIONS WOULD COST ALSO 2 TEMPORARIES EACH)

	m1 = m1 + m2;
	m1 = m2 * m1;

// THESE EACH COST 2 Matrix TEMPORARIES 
// (A NON-LAZY VERSION OF EACH WOULD ALSO COST 2 TEMPORARIES)

	cout << m1 + m2 << endl;
	cout << m2 * m1 << endl;

// THIS COSTS _ZERO_ Matrix TEMPORARIES IF
// Matrix::operator=(const Matrix::LazyMulAdd&) AND
// evaluateInto(const Matrix::LazyMulAdd&, Matrix&) ARE DEFINED
// COST IS 2 TEMPORARIES IF operator= IS NOT DEFINED
// OR 2 TEMPORARIES IF evaluateInto(const LazyMulAdd&, Matrix&) IS NOT DEFINED
// OR 4 TEMPORARIES IF NEITHER IS DEFINED
// (A NON-LAZY VERSION WOULD COST 4 TEMPORARIES)

	m4 = m1 * m2 + m3;
}

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]