//=================================================================================================
/*!
//  \file blaze/math/dense/RQ.h
//  \brief Header file for the dense matrix in-place RQ decomposition
//
//  Copyright (C) 2013 Klaus Iglberger - All Rights Reserved
//
//  This file is part of the Blaze library. You can redistribute it and/or modify it under
//  the terms of the New (Revised) BSD License. Redistribution and use in source and binary
//  forms, with or without modification, are permitted provided that the following conditions
//  are met:
//
//  1. Redistributions of source code must retain the above copyright notice, this list of
//     conditions and the following disclaimer.
//  2. Redistributions in binary form must reproduce the above copyright notice, this list
//     of conditions and the following disclaimer in the documentation and/or other materials
//     provided with the distribution.
//  3. Neither the names of the Blaze development group nor the names of its contributors
//     may be used to endorse or promote products derived from this software without specific
//     prior written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
//  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
//  SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
//  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
//  TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
//  BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
//  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
//  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
//  DAMAGE.
*/
//=================================================================================================

#ifndef _BLAZE_MATH_DENSE_RQ_H_
#define _BLAZE_MATH_DENSE_RQ_H_


//*************************************************************************************************
// Includes
//*************************************************************************************************

#include <blaze/math/constraints/Adaptor.h>
#include <blaze/math/constraints/BlasCompatible.h>
#include <blaze/math/constraints/Hermitian.h>
#include <blaze/math/constraints/Lower.h>
#include <blaze/math/constraints/StorageOrder.h>
#include <blaze/math/constraints/StrictlyTriangular.h>
#include <blaze/math/constraints/Symmetric.h>
#include <blaze/math/constraints/UniTriangular.h>
#include <blaze/math/constraints/Upper.h>
#include <blaze/math/expressions/DenseMatrix.h>
#include <blaze/math/Functions.h>
#include <blaze/math/lapack/gerqf.h>
#include <blaze/math/lapack/orgrq.h>
#include <blaze/math/lapack/ungrq.h>
#include <blaze/math/traits/DerestrictTrait.h>
#include <blaze/math/typetraits/IsResizable.h>
#include <blaze/math/typetraits/IsRowMajorMatrix.h>
#include <blaze/math/typetraits/IsSquare.h>
#include <blaze/math/typetraits/RemoveAdaptor.h>
#include <blaze/math/views/DenseSubmatrix.h>
#include <blaze/math/views/Submatrix.h>
#include <blaze/util/constraints/SameType.h>
#include <blaze/util/Exception.h>
#include <blaze/util/mpl/If.h>


namespace blaze {

//=================================================================================================
//
//  RQ DECOMPOSITION FUNCTIONS
//
//=================================================================================================

//*************************************************************************************************
/*!\name RQ decomposition functions */
//@{
template< typename MT1, bool SO1, typename MT2, bool SO2, typename MT3, bool SO3 >
void rq( const DenseMatrix<MT1,SO1>& A, DenseMatrix<MT2,SO2>& R, DenseMatrix<MT3,SO3>& Q );
//@}
//*************************************************************************************************


//*************************************************************************************************
/*! \cond BLAZE_INTERNAL */
/*!\brief Auxiliary function for the RQ decomposition.
// \ingroup dense_matrix
//
// \param A The RQ decomposed column-major matrix.
// \param tau Array for the scalar factors of the elementary reflectors.
// \return void
//
// This function is an auxiliary helper for the dense matrix RQ decomposition. It performs the
// reconstruction of the \c Q matrix from the RQ decomposition.
*/
template< typename MT1 >  // Type of matrix A
inline typename EnableIf< IsBuiltin< typename MT1::ElementType > >::Type
   rq_backend( MT1& A, const typename MT1::ElementType* tau )
{
   BLAZE_CONSTRAINT_MUST_BE_COLUMN_MAJOR_MATRIX_TYPE( MT1 );

   orgrq( A, tau );
}
/*! \endcond */
//*************************************************************************************************


//*************************************************************************************************
/*! \cond BLAZE_INTERNAL */
/*!\brief Auxiliary function for the RQ decomposition.
// \ingroup dense_matrix
//
// \param A The RQ decomposed column-major matrix.
// \param tau Array for the scalar factors of the elementary reflectors.
// \return void
//
// This function is an auxiliary helper for the dense matrix RQ decomposition. It performs the
// reconstruction of the \c Q matrix from the RQ decomposition.
*/
template< typename MT1 >  // Type of matrix A
inline typename EnableIf< IsComplex< typename MT1::ElementType > >::Type
   rq_backend( MT1& A, const typename MT1::ElementType* tau )
{
   BLAZE_CONSTRAINT_MUST_BE_COLUMN_MAJOR_MATRIX_TYPE( MT1 );

   ungrq( A, tau );
}
/*! \endcond */
//*************************************************************************************************


//*************************************************************************************************
/*!\brief RQ decomposition of the given dense matrix.
// \ingroup dense_matrix
//
// \param A The matrix to be decomposed.
// \param R The resulting \c R matrix.
// \param Q The resulting \c Q matrix.
// \return void
// \exception std::invalid_argument Dimensions of fixed size matrix do not match.
// \exception std::invalid_argument Square matrix cannot be resized to \a m-by-\a n.
//
// This function performs the dense matrix RQ decomposition of a general \a m-by-\a n matrix.
// The resulting decomposition has the form

                              \f[ A = R \cdot Q, \f]

// where \c R is an upper trapezoidal \a m-by-min(\a m,\a n) matrix and \c Q is a general
// min(\a m,\a n)-by-\a n matrix. The decomposition is written to the two distinct matrices
// \c R and \c Q, which are resized to the correct dimensions (if possible and necessary).
//
// The function fails if ...
//
//  - ... either \a R or \a Q are fixed size matrices and the dimensions don't match;
//  - ... \a R is a compile time square matrix, but is required to be non-square.
//
// In all failure cases a \a std::invalid_argument exception is thrown.
//
// Example:

   \code
   blaze::DynamicMatrix<double,blaze::columnMajor> A( 32, 16 );
   // ... Initialization of A

   blaze::DynamicMatrix<double,blaze::columnMajor> R( 32, 16 );
   blaze::DynamicMatrix<double,blaze::columnMajor> Q( 16, 16 );


   rq( A, R, Q );

   assert( A == R * Q );
   \endcode

// \note This function only works for matrices with \c float, \c double, \c complex<float>, or
// \c complex<double> element type. The attempt to call the function with matrices of any other
// element type results in a compile time error!
//
// \note This function can only be used if the fitting LAPACK library is available and linked to
// the executable. Otherwise a call to this function will result in a linker error.
*/
template< typename MT1  // Type of matrix A
        , bool SO1      // Storage order of matrix A
        , typename MT2  // Type of matrix R
        , bool SO2      // Storage order of matrix R
        , typename MT3  // Type of matrix Q
        , bool SO3 >    // Storage order of matrix Q
void rq( const DenseMatrix<MT1,SO1>& A, DenseMatrix<MT2,SO2>& R, DenseMatrix<MT3,SO3>& Q )
{
   BLAZE_CONSTRAINT_MUST_NOT_BE_STRICTLY_TRIANGULAR_MATRIX_TYPE( MT1 );
   BLAZE_CONSTRAINT_MUST_BE_BLAS_COMPATIBLE_TYPE( typename MT1::ElementType );

   BLAZE_CONSTRAINT_MUST_NOT_BE_SYMMETRIC_MATRIX_TYPE( MT2 );
   BLAZE_CONSTRAINT_MUST_NOT_BE_HERMITIAN_MATRIX_TYPE( MT2 );
   BLAZE_CONSTRAINT_MUST_NOT_BE_UNITRIANGULAR_MATRIX_TYPE( MT2 );
   BLAZE_CONSTRAINT_MUST_NOT_BE_STRICTLY_TRIANGULAR_MATRIX_TYPE( MT2 );
   BLAZE_CONSTRAINT_MUST_NOT_BE_LOWER_MATRIX_TYPE( MT2 );
   BLAZE_CONSTRAINT_MUST_BE_BLAS_COMPATIBLE_TYPE( typename MT2::ElementType );

   BLAZE_CONSTRAINT_MUST_NOT_BE_ADAPTOR_TYPE( MT3 );
   BLAZE_CONSTRAINT_MUST_BE_BLAS_COMPATIBLE_TYPE( typename MT3::ElementType );

   typedef typename RemoveAdaptor<MT1>::Type  UMT1;
   typedef typename If< IsRowMajorMatrix<UMT1>, typename UMT1::OppositeType, UMT1 >::Type  Tmp;
   typedef typename MT1::ElementType  ET1;

   BLAZE_CONSTRAINT_MUST_BE_COLUMN_MAJOR_MATRIX_TYPE( Tmp );
   BLAZE_CONSTRAINT_MUST_BE_SAME_TYPE( ET1, typename Tmp::ElementType );

   const size_t m( (~A).rows() );
   const size_t n( (~A).columns() );
   const size_t mindim( min( m, n ) );

   if( ( !IsResizable<MT2>::value && ( (~R).rows() != m || (~R).columns() != mindim ) ) ||
       ( !IsResizable<MT3>::value && ( (~Q).rows() != mindim || (~Q).columns() != n ) ) ) {
      BLAZE_THROW_INVALID_ARGUMENT( "Dimensions of fixed size matrix do not match" );
   }

   if( IsSquare<MT2>::value && m != mindim ) {
      BLAZE_THROW_INVALID_ARGUMENT( "Square matrix cannot be resized to m-by-min(m,n)" );
   }

   Tmp tmp( ~A );
   UniqueArray<ET1> tau( new ET1[mindim] );

   gerqf( tmp, tau.get() );

   typename DerestrictTrait<MT2>::Type r( derestrict( ~R ) );
   resize( ~R, m, mindim );
   reset( r );

   const size_t ioffset( ( m > n )?( m-n ):( 0UL ) );
   const size_t joffset( ( m < n )?( n-m ):( 0UL ) );

   for( size_t i=0UL; i<ioffset; ++i ) {
      for( size_t j=0UL; j<mindim; ++j ) {
         r(i,j) = tmp(i,j);
      }
   }

   for( size_t i=ioffset; i<m; ++i ) {
      for( size_t j=i-ioffset; j<mindim; ++j ) {
         r(i,j) = tmp(i,j+joffset);
      }
   }

   rq_backend( tmp, tau.get() );

   (~Q) = submatrix( tmp, ioffset, 0UL, min( m, n ), n );
}
//*************************************************************************************************

} // namespace blaze

#endif
