vector.cpp

Go to the documentation of this file.

/*****************************************************************************
    
    vector.cpp -- Îïèñàíèå ñì. â ôàéëå vector.hpp.

    Ýòîò ôàéë ÿâëÿåòñÿ ÷àñòüþ áèáëèîòåêè Arageli.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Sergey S. Lyalin, 2005
    University of Nizhni Novgorod, Russia

*****************************************************************************/

#include "config.hpp"

#if !defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE) || \
    defined(ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_VECTOR)

#include <sstream>
#include <vector>
#include <string>
#include <sstream>
#include <list>
#include <numeric>

#include "vector.hpp"
#include "_utility.hpp"


namespace Arageli
{


template <typename T, bool REFCNT>
void vector<T, REFCNT>::assign_fromstr (const char* s)
{
    std::istringstream buf(s);
    // WARNING. It is valid if there are no virtual function.
    static_cast<std::istream&>(buf) >> *this;
    if(!buf && !buf.eof())
        throw incorrect_string(s);
}


template <typename T, bool REFCNT>
bool vector<T, REFCNT>::is_null () const
{
    for(size_type i = 0; i < size(); ++i)
        if(!Arageli::is_null(rep(i)))return false;
    return true;
}


template <typename T, bool REFCNT>
bool vector<T, REFCNT>::is_unit () const
{
    if(is_empty())return false;
    for(size_type i = 0; i < size(); ++i)
        if(!Arageli::is_unit(rep(i)))return false;
    return true;
}


template <typename T, bool REFCNT>
bool vector<T, REFCNT>::is_opposite_unit () const
{
    if(is_empty())return false;
    for(size_type i = 0; i < size(); ++i)
        if(!Arageli::is_opposite_unit(rep(i)))return false;
    return true;
}


template <typename T, bool REFCNT>
vector<T, REFCNT>& vector<T, REFCNT>::inverse ()
{
    unique();
    for(size_type i = 0; i < size(); ++i)
        Arageli::inverse(&rep(i));
    return *this;
}


template <typename T, bool REFCNT>
vector<T, REFCNT>& vector<T, REFCNT>::bitwise_not ()
{
    unique();
    for(size_type i = 0; i < size(); ++i)
        Arageli::assign_bitwise_not(rep(i));
    return *this;
}

template <typename T, bool REFCNT>
vector<T, REFCNT>& vector<T, REFCNT>::logical_not ()
{
    unique();
    for(size_type i = 0; i < size(); ++i)
        Arageli::assign_logical_not(rep(i));
    return *this;
}

//template <typename T, bool REFCNT>
//bool vector<T, REFCNT>::operator! () const
//{
//  vector<bool> res(size());
//
//  for(size_type i = 0; i < size(); ++i)
//      res[i] = blogical_not(rep(i));
//  return *this;
//}
//

//#define _ARAGELI_VECTOR_OPERATOR_ASSIGN_1(OPER, MNEM)                 \
//  template <typename T1, bool REFCNT1>                                \
//  template <typename T2>                                              \
//  vector<T1, REFCNT1>& vector<T1, REFCNT1>::MNEM##_scalar             \
//  (const T2& x)                                                       \
//  {                                                                   \
//      if(is_empty())return *this;                                     \
//      /*unique();*/                                                   \
//                                                                      \
//      iterator i = begin(), iend = end();                             \
//      for(; i < iend; ++i)                                            \
//          *i OPER x;                                                  \
//                                                                      \
//      return *this;                                                   \
//  }                                                                   \
//                                                                      \
//  template <typename T1, bool REFCNT1>                                \
//  template <typename T2>                                              \
//  vector<T1, REFCNT1>& vector<T1, REFCNT1>::MNEM##_vector             \
//  (const T2& x)                                                       \
//  {                                                                   \
//      ARAGELI_ASSERT_0(x.size() == size());                           \
//      if(is_empty())return *this;                                     \
//      /*unique();*/                                                   \
//                                                                      \
//      iterator i1 = begin(), i1end = end();                           \
//      typename T2::const_iterator i2 = x.begin();                     \
//      for(; i1 < i1end; ++i1, ++i2)                                   \
//          *i1 OPER *i2;                                               \
//                                                                      \
//      return *this;                                                   \
//  }
//
//
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(+=, add)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(-=, sub)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(*=, mul)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(/=, div);
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(%=, mod);
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(&=, bitand)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(|=, bitor)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(^=, bitxor)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(<<=, shl)
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_1(>>=, shr)


//#define _ARAGELI_VECTOR_OPERATOR_ASSIGN_2(OPER, MNEM)                 \
//  template <typename T1, bool REFCNT1>                                \
//  template <typename T2>                                              \
//  vector<T1, REFCNT1>& vector<T1, REFCNT1>::MNEM##_scalar             \
//  (const T2& x)                                                       \
//  {                                                                   \
//      ARAGELI_ASSERT_0(!is_null(x));                                  \
//      if(is_empty())return *this;                                     \
//      /*unique();*/                                                   \
//                                                                      \
//      iterator i = begin(), iend = end();                             \
//      for(; i < iend; ++i)                                            \
//          *i OPER x;                                                  \
//                                                                      \
//      return *this;                                                   \
//  }                                                                   \
//                                                                      \
//  template <typename T1, bool REFCNT1>                                \
//  template <typename T2>                                              \
//  vector<T1, REFCNT1>& vector<T1, REFCNT1>::MNEM##_vector             \
//  (const T2& x)                                                       \
//  {                                                                   \
//      ARAGELI_ASSERT_0(x.size() == size());                           \
//      if(is_empty())return *this;                                     \
//      unique();                                                       \
//                                                                      \
//      iterator i1 = begin(), i1end = end();                           \
//      typename T2::const_iterator i2 = x.begin();                     \
//      for(; i1 < i1end; ++i1, ++i2)                                   \
//      {                                                               \
//          ARAGELI_ASSERT_0(!is_null(*i2]));                           \
//          *i1 OPER *i2;                                               \
//      }                                                               \
//                                                                      \
//      return *this;                                                   \
//  }
//
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_2(/=, div);
//_ARAGELI_VECTOR_OPERATOR_ASSIGN_2(%=, mod);

#undef _ARAGELI_VECTOR_OPERATOR_ASSIGN_1
//#undef _ARAGELI_VECTOR_OPERATOR_ASSIGN_2


//template <typename T1, bool REFCNT1>
//template <typename T2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator+=
//(const T2& x)
//{
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr = rep();
//  for(size_type i = 0; i < size(); ++i)
//      repr[i] += x;
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator-=
//(const T2& x)
//{
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr = rep();
//  for(size_type i = 0; i < size(); ++i)
//      repr[i] -= x;
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator*=
//(const T2& x)
//{
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr = rep();
//  for(size_type i = 0; i < size(); ++i)
//      repr[i] *= x;
//
//  return *this;
//}


//template <typename T1, bool REFCNT1>
//template <typename T2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator/=
//(const T2& x)
//{
//  ARAGELI_ASSERT_0(!type_traits<T2>::is_null(x));
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr = rep();
//  for(size_type i = 0; i < size(); ++i)
//      repr[i] /= x;
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator%=
//(const T2& x)
//{
//  ARAGELI_ASSERT_0(!type_traits<T2>::is_null(x));
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr = rep();
//  for(size_type i = 0; i < size(); ++i)
//      repr[i] %= x;
//
//  return *this;
//}


//template <typename T1, bool REFCNT1>
//template <typename T2, bool REFCNT2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator+=
//(const vector<T2, REFCNT2>& x)
//{
//  ARAGELI_ASSERT_0(x.size() == size());
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr1 = rep();
//  const typename vector<T2, REFCNT2>::Rep& repr2 = x.rep();
//  for(size_type i = 0; i < repr1.size(); ++i)
//      repr1[i] += repr2[i];
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2, bool REFCNT2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator-=
//(const vector<T2, REFCNT2>& x)
//{
//  ARAGELI_ASSERT_0(x.size() == size());
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr1 = rep();
//  const typename vector<T2, REFCNT2>::Rep& repr2 = x.rep();
//  for(size_type i = 0; i < repr1.size(); ++i)
//      repr1[i] -= repr2[i];
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2, bool REFCNT2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator*=
//(const vector<T2, REFCNT2>& x)
//{
//  ARAGELI_ASSERT_0(x.size() == size());
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr1 = rep();
//  const typename vector<T2, REFCNT2>::Rep& repr2 = x.rep();
//  for(size_type i = 0; i < repr1.size(); ++i)
//      repr1[i] *= repr2[i];
//
//  return *this;
//}


//template <typename T1, bool REFCNT1>
//template <typename T2, bool REFCNT2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator/=
//(const vector<T2, REFCNT2>& x)
//{
//  ARAGELI_ASSERT_0(x.size() == size());
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr1 = rep();
//  const typename vector<T2, REFCNT2>::Rep& repr2 = x.rep();
//  for(size_type i = 0; i < repr1.size(); ++i)
//  {
//      ARAGELI_ASSERT_0(!TT2::is_null(repr2[i]));
//      repr1[i] /= repr2[i];
//  }
//
//  return *this;
//}
//
//
//template <typename T1, bool REFCNT1>
//template <typename T2, bool REFCNT2>
//vector<T1, REFCNT1>& vector<T1, REFCNT1>::operator%=
//(const vector<T2, REFCNT2>& x)
//{
//  ARAGELI_ASSERT_0(x.size() == size());
//  if(is_empty())return *this;
//  unique();
//
//  Rep& repr1 = rep();
//  const typename vector<T2, REFCNT2>::Rep& repr2 = x.rep();
//  for(size_type i = 0; i < repr1.size(); ++i)
//  {
//      ARAGELI_ASSERT_0(!TT2::is_null(repr2[i]));
//      repr1[i] %= repr2[i];
//  }
//
//  return *this;
//}


template <typename T1, bool REFCNT1>
vector<T1, REFCNT1>& vector<T1, REFCNT1>::opposite ()
{
    if(is_empty())return *this;
    unique();

    Rep& repr1 = rep();
    for(size_type i = 0; i < size(); ++i)
        Arageli::opposite(&repr1[i]);

    return *this;
}


template <typename T, bool REFCNT>
bool vector<T, REFCNT>::do_pack ()
{
    ARAGELI_ASSERT_1(size() < capacity());

    unique();
    Rep trep = rep();
    trep.swap(rep());
}


template <typename T, bool REFCNT>
template <typename SV, typename V>
V& vector<T, REFCNT>::copy_subvector (const SV& sv, V& res) const
{
    size_type sz = sv.size();
    res.resize(sz);
    const_iterator thisvec = begin();
    typename V::iterator iv = res.begin();

    for
    (
        typename SV::const_iterator i = sv.begin(), svend = sv.end();
        i != svend;
        ++i, ++iv
    )
    {
        ARAGELI_ASSERT_0(*i < size());
        *iv = thisvec[*i];
    }

    return res;
}


template <typename T, bool REFCNT>
template <typename SV>
void vector<T, REFCNT>::erase_subvector (const SV& sv)
{
    // WARNING! Slow implementation!!!
    // O(sv.size() * log(sv.size()) + this->size())

    //std::cout << "\n*** sv = " << sv << " ***\n";

    if(sv.is_empty())return;

    SV svt = sv;    // copy because need sorting and uniquelization
    typedef typename SV::iterator SViter;
    std::sort(svt.begin(), svt.end());
    
    SViter
        svti = svt.begin(),
        svtend = std::unique(svti, svt.end());

    size_type curerased = *svti;

    //if(*(svtend-1) >= size())
    //{
    //  std::cout << "\nsv = " << sv << ", *(svtend-1) = " << *(svtend-1) << ", size() = " << size();
    //}
    
    ARAGELI_ASSERT_0(*(svtend-1) < size());
    ARAGELI_ASSERT_0(curerased < size());
    
    iterator
        thisdst = begin() + curerased,
        thissrc = thisdst + 1,
        thisend = end();

    for(;;)
    {
        ++svti;

        if(svti != svtend && *svti == curerased+1)
        {
            ++curerased;
            ++svti;
            ARAGELI_ASSERT_0(thissrc != thisend);
            ++thissrc;
        }

        ARAGELI_ASSERT_1(thissrc != thisend || svti == svtend);

        iterator tend =     // end of current copied part of vector
            svti == svtend ?
            thisend : thissrc + (*svti - curerased - 1);

        thisdst = std::copy(thissrc, tend, thisdst);

        if(tend == thisend)
            break;

        thissrc = tend + 1;
        ARAGELI_ASSERT_1(svti != svtend);
        curerased = *svti;
    }

    ARAGELI_ASSERT_1(svti == svtend);
    ARAGELI_ASSERT_1(thisdst + (svtend - svt.begin()) == thisend);
    erase(thisdst, thisend);
}




template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2,
    typename T1_factory
>
T1 dotprod
(
    const vector<T1, REFCNT1>& a,
    const vector<T2, REFCNT2>& b,
    const T1_factory& t1fctr
)
{
    ARAGELI_ASSERT_0(a.size() == b.size());

    T1 res = a.is_empty() ? t1fctr.null() : t1fctr.null(a[0]);
    typename vector<T1, REFCNT1>::size_type size = a.size();
    
    for(std::size_t i = 0; i < size; ++i)
        res += a[i]*b[i];

    return res;
}


template <typename T, bool REFCNT, typename T2, typename T2_factory>
T2& product (const vector<T, REFCNT>& x, T2& res, const T2_factory& t2fctr)
{
    if(x.is_empty())return res = t2fctr.unit();
    res = x[0];
    for(std::size_t i = 1; i < x.size(); ++i)
        res *= x[i];
    return res;
}


template <typename T, bool REFCNT, typename T2, typename T2_factory>
T2& sum (const vector<T, REFCNT>& x, T2& res, const T2_factory& t2fctr)
{
    if(x.is_empty())return res = t2fctr.null();
    res = x[0];
    for(std::size_t i = 1; i < x.size(); ++i)
        res += x[i];
    return res;
}


template <typename In, typename T, bool REFCNT>
In& input_list
(
    In& in,
    vector<T, REFCNT>& x,
    const char* first_bracket,
    const char* second_bracket,
    const char* separator,
    const char* range
)
{
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(first_bracket));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(second_bracket));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(separator));
    ARAGELI_ASSERT_0(_Internal::is_not_contains_spaces(range));

    if(_Internal::is_bad_read_literal(in, first_bracket))return in;

    // (second_bracket == "") is special case
    // in this case vector must be terminated by the some invalid character

    if(*second_bracket && _Internal::read_literal(in, second_bracket))
    { // empty vector
        x.resize(0);
        return in;
    }

    std::list<T> buf;   // a temporary buffer for values

    T t;
    
    for(;;)
    {
        in >> t;
    
        if(_Internal::is_bad_input(in))return in;
        else if(_Internal::read_literal(in, separator))
        { // "t,"
            buf.push_back(t);
            continue;
        }
        else if(_Internal::read_literal(in, range))
        { // "t:"
            T t1;
            in >> t1;
            
            if(_Internal::is_bad_input(in))return in;
            else if(_Internal::read_literal(in, separator))
            { // "t:t1,"
                generate_range_helper(t, t1, std::back_inserter(buf));
                continue;
            }
            else if(_Internal::read_literal(in, range))
            { // "t:t1:"
                T t2;
                in >> t2;

                if(_Internal::is_bad_input(in))return in;
                else if(_Internal::read_literal(in, separator))
                { // "t:t1:t2,"
                    generate_range_helper(t, t1, t2, std::back_inserter(buf));
                    continue;
                }
                else if
                (
                    *second_bracket == 0 ||
                    _Internal::read_literal(in, second_bracket)
                )
                { // "t:t1:t2)"
                    generate_range_helper(t, t1, t2, std::back_inserter(buf));
                    break;
                }
            }
            else if(*second_bracket == 0 || _Internal::read_literal(in, second_bracket))
            { // "t:t1)"
                generate_range_helper(t, t1, std::back_inserter(buf));
                break;
            }
        }
        else if(*second_bracket == 0 || _Internal::read_literal(in, second_bracket))
        { // "t)"
            buf.push_back(t);
            break;
        }
        
        in.clear(std::ios_base::badbit);
        return in;
    }

    // WARNING! Inefficient!
    //std::copy(buf.begin(), buf.end(), std::ostream_iterator<T>(std::cerr, ", "));
    x.resize(buf.size());
    std::copy(buf.begin(), buf.end(), x.begin());
    return in;
}


template <typename T, bool REFCNT>
std::ostream& output_aligned
(
    std::ostream& out,
    const vector<T, REFCNT>& x,
    const char* left_col,
    const char* right_col
)
{
    if(x.is_empty())return out;
    
    std::vector<std::string> buf(x.size());
    std::size_t maxlen = 0;

    for(std::size_t i = 0; i < x.size(); ++i)
    {
        std::ostringstream strbuf;
        strbuf.copyfmt(out);
        strbuf << x[i];
        buf[i] = strbuf.str();

        if(buf[i].length() > maxlen)
            maxlen = buf[i].length();
    }

    for(std::size_t i = 0; i < x.size(); ++i)
    {
        std::size_t numspace = maxlen - buf[i].length();
        
        out
            << left_col << std::string(numspace/2, ' ')
            << buf[i] << std::string(numspace - numspace/2, ' ')
            << right_col << '\n';
    }

    return out;
}


template <typename T, bool REFCNT>
std::istream& input_polynom_internal
(std::istream& in, vector<T, REFCNT>& x)
{
    char ch = 0;
    in >> ch;
    if(!in && !in.eof() || ch != '+' && ch != '-')return in;
    vector<T, REFCNT> res;
    in >> res;
    if(!in && !in.eof())return in;
    if(ch == '-')res.opposite();
    x = res;
    return in;
}


#define ARAGELI_VECTOR_MATH_FUNCS1_IMPL(NAME)           \
    template <typename T, bool REFCNT>                  \
    vector<T, true> NAME                                \
    (const vector<T, REFCNT>& x)                        \
    {                                                   \
        std::size_t size = x.size();                            \
        vector<T, true> res(size);                      \
                                                        \
        typename vector<T, REFCNT>::const_iterator      \
            xbeg = x.begin();                           \
        typename vector<T, true>::iterator              \
            resbeg = res.begin();                       \
                                                        \
        for(std::size_t i = 0; i < size; ++i)               \
            resbeg[i] = NAME(xbeg[i]);                  \
                                                        \
        return res;                                     \
    }


ARAGELI_VECTOR_MATH_FUNCS1_IMPL(sin)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(cos)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(tan)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(sinh)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(cosh)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(tanh)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(asin)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(acos)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(atan)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(abs)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(exp)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(floor)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(ceil)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(log)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(log10)
ARAGELI_VECTOR_MATH_FUNCS1_IMPL(sqrt)


#undef ARAGELI_VECTOR_MATH_FUNCS1_IMPL

    
template
<
    typename T1, bool REFCNT1,
    typename T2, bool REFCNT2
>
vector<T1, REFCNT1> pow
(
    const vector<T1, REFCNT1>& a,
    const vector<T2, REFCNT2>& b
)
{
    ARAGELI_ASSERT_0(a.size() == b.size());
    std::size_t size = a.size();
    vector<T1, REFCNT1> res(size);
    for(std::size_t i = 0; i < size; ++i)
        res[i] = pow(a[i], b[i]);

    return res;
}


template
<
    typename T, bool REFCNT,
    typename P
>
vector<T, REFCNT> pow
(const vector<T, REFCNT>& a, const P& b)
{
    std::size_t size = a.size();
    vector<T, REFCNT> res(size);
    for(std::size_t i = 0; i < size; ++i)
        res[i] = pow(a[i], b);
}

} // namespace Arageli


namespace std
{



}

#endif // #ifndef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE

---