#include "../DeadLockAvoid.hpp"
#include "../ContainerOperation.hpp"
#include <boost/functional.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>
#include <boost/numeric/ublas/matrix_proxy.hpp>
#include <boost/utility.hpp>


namespace DLA = DeadlockAvoidance;


template<typename T>
bool operator<=(const boost::numeric::ublas::matrix_row< boost::numeric::ublas::matrix<T> >& A,
                const boost::numeric::ublas::matrix_row< boost::numeric::ublas::matrix<T> >& B)
{
    typedef typename boost::numeric::ublas::matrix_row<boost::numeric::ublas::matrix<T> >::size_type TDS;
    for (TDS i(0); i < A.size(); ++i)
    {
       if (!(A(i) <= B(i)))
          return false;
    }
    return true;
}

template <typename T,
         template <typename ELEM, typename = std::allocator<ELEM> >
         class CONT
>
bool DLA::isSafe(boost::numeric::ublas::matrix<T> Alloc,
               boost::numeric::ublas::matrix<T> Need,
               boost::numeric::ublas::matrix<T> Available)
{
    BOOST_STATIC_ASSERT(boost::is_arithmetic<T>::value);
    typedef boost::numeric::ublas::matrix<T> matr;
    typedef boost::numeric::ublas::matrix_row<matr> mat_row;
    typedef typename matr::size_type TDS;
    CONT<bool> Finish(Alloc.size1(), false);
    mat_row Work(Available, 0);
    TDS index(0);
    const TDS size(Finish.size());
    typedef typename CONT<bool>::iterator ContIter;
    ContIter iter;
    bool found(true);
	while ((iter = std::find(Finish.begin(), Finish.end(), false)) != Finish.end() && found)
    {
             found = false;
             for (index =  std::distance(Finish.begin(), iter); index < size; ++index)
             {
                 mat_row myNeed(Need, index);
                 mat_row myAlloc(Alloc, index);
                 iter = boost::next(Finish.begin(), index);
                 if (*iter == false
                     &&
                     myNeed <= Work)
                 {
                    *iter = true;
                    Work += myAlloc;
                    #ifndef NODEBUG
                            std::cout << "isSafe: p[" << index << "]\n";
                    #endif
                    found = true;
                 }
             }
    }
    return (std::binary_search(Finish.begin(), Finish.end(), false))
          ? false : true;
}

/*************************************************************
 * For each request  in Request                              *
 * if request[i] <= Need[i], raise an error                  *
 * Wait if request[i] > available                            *
 * otherwise:                                                *
 * Available = Available - Request[i];                       *
 * Allocation[i] = Allocation[i] + Request[i]                *
 * Need[i] = Need[i] - Request[i]                            *
 ************************************************************/
template <typename T,
           template <
                     typename ELEM,
                     typename = std::allocator<ELEM>
           >
           class CONT
>
CONT<RequestResult> DLA::isRequest(
               boost::numeric::ublas::matrix<T> Alloc,
               boost::numeric::ublas::matrix<T> Need,
               boost::numeric::ublas::matrix<T>  Available,
               boost::numeric::ublas::matrix<T> Request)
{
    BOOST_STATIC_ASSERT(boost::is_arithmetic<T>::value);
    typedef boost::numeric::ublas::matrix<T> matr;
    typedef boost::numeric::ublas::matrix_row<matr> mat_row;
    typedef typename matr::size_type TDS;
    const TDS outer_sz(Alloc.size1());
    CONT<bool> Finish(outer_sz, false);
    mat_row Work(Available, 0);
    CONT<RequestResult> req_res;    // results of request
    for (TDS i(0); i < outer_sz; ++i)
    {
        mat_row myRequest(Request, i);
        mat_row myNeed(Need, i);
        mat_row myAlloc(Alloc, i);
        assert(myRequest <= myNeed);
        if (myRequest <= Work)
        {
            Work -= myRequest;
            myAlloc += myRequest;
            myNeed -= myRequest;
            (DLA::isSafe<long,CONT>(Alloc, Need, Available)) ?
        req_res.push_back(RequestResult(SAFE)) : req_res.push_back(RequestResult(NOT_SAFE));
        }
        else
        {
            req_res.push_back(RequestResult(WAIT));
        }
    }
    return req_res;
}

template <typename T,
           template <
                     typename ELEM,
                     typename = std::allocator<ELEM>
           >
           class CONT
   >
CONT<bool> DLA::DeadLockDetect(
           boost::numeric::ublas::matrix<T> Alloc,
           boost::numeric::ublas::matrix<T> Available,
           boost::numeric::ublas::matrix<T> Request)
{
    BOOST_STATIC_ASSERT(boost::is_arithmetic<T>::value);
    typedef boost::numeric::ublas::matrix<T> matr;
    typedef boost::numeric::ublas::matrix_row<matr> mat_row;
    typedef typename matr::size_type TDS;
    typedef typename CONT<bool>::size_type size_type;
    CONT<bool> Finish(Available.size2(), false);
    mat_row Work(Available, 0);
    typedef typename CONT<bool>::iterator ContIter;
    ContIter iter;
    bool found(true);
    while ((iter = std::find(Finish.begin(), Finish.end(), false)) != Finish.end() && found)
    {
         found = false;
         for (size_type  i = distance(Finish.begin(), iter); i < Finish.size(); ++i)
         {
              iter = boost::next(Finish.begin(), i);
              mat_row myRequest(Request, i);
              mat_row myAlloc(Alloc, i);
              #ifndef NODEBUG
                      std::cout << myRequest << "\t" << myAlloc << "\t"
                                << Work << "\n";
              #endif
              if (*iter == false && myRequest <= Work)
              {
                 found = true;
                 *iter = true;
                 Work += myAlloc;
                 #ifndef NODEBUG
                         std::cout << "DeadLockDetect: p[" << i << "]\n";
                 #endif
              }
          }
    }
    return Finish;
}