/*

 * Copyright (c) 1999

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1999

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

#ifndef _STLP_VALARRAY_H

#define _STLP_VALARRAY_H

#ifndef _STLP_INTERNAL_CMATH

#  include <stl/_cmath.h>

#endif

#ifndef _STLP_INTERNAL_NEW

#  include <stl/_new.h>

#endif

#ifndef _STLP_INTERNAL_ALGO_H

#  include <stl/_algo.h>

#endif

#ifndef _STLP_INTERNAL_NUMERIC_H

#  include <stl/_numeric.h>

#endif

#ifndef _STLP_INTERNAL_LIMITS

#  include <stl/_limits.h>

#endif

/* As we only need the _STLP_ASSERT macro from _debug.h we test it to include _debug.h */

#ifndef _STLP_ASSERT

#  include <stl/debug/_debug.h>

#endif

_STLP_BEGIN_NAMESPACE

class slice;

class gslice;

template <class _Tp> class valarray;

typedef valarray<bool>    _Valarray_bool;

typedef valarray<size_t>  _Valarray_size_t;

template <class _Tp> class slice_array;

template <class _Tp> class gslice_array;

template <class _Tp> class mask_array;

template <class _Tp> class indirect_array;

//----------------------------------------------------------------------

// class valarray

// Base class to handle memory allocation and deallocation.  We can't just

// use vector<>, because vector<bool> would be unsuitable as an internal

// representation for valarray<bool>.

template <class _Tp>

struct _Valarray_base

{

  _Tp*   _M_first;

  size_t _M_size;

  _Valarray_base() : _M_first(0), _M_size(0) {}

  _Valarray_base(size_t __n) : _M_first(0), _M_size(0) { _M_allocate(__n); }

  ~_Valarray_base() { _M_deallocate(); }

  void _M_allocate(size_t __n) {

    if (__n != 0) {

      _M_first = __STATIC_CAST(_Tp*, (malloc(__n * sizeof(_Tp))));

      _M_size  = __n;

#if !defined(_STLP_NO_BAD_ALLOC) && defined(_STLP_USE_EXCEPTIONS)

      if (_M_first == 0) {

        _M_size = 0;

        throw _STLP_STD::bad_alloc();

      }

#endif

    }

    else {

      _M_first = 0;

      _M_size = 0;

    }

  }

  void _M_deallocate() {

    free(_M_first);

    _M_first = 0;

    _M_size = 0;

  }

};

template <class _Tp>

class valarray : private _Valarray_base<_Tp>

{

  friend class gslice;

public:

  typedef _Tp value_type;

  // Basic constructors

  valarray() : _Valarray_base<_Tp>() {}

  explicit valarray(size_t __n) : _Valarray_base<_Tp>(__n)

    { uninitialized_fill_n(this->_M_first, this->_M_size, _STLP_DEFAULT_CONSTRUCTED(value_type)); }

  valarray(const value_type& __x, size_t __n) : _Valarray_base<_Tp>(__n)

    { uninitialized_fill_n(this->_M_first, this->_M_size, __x); }

  valarray(const value_type* __p, size_t __n) : _Valarray_base<_Tp>(__n)

    { uninitialized_copy(__p, __p + __n, this->_M_first); }

  valarray(const valarray<_Tp>& __x) : _Valarray_base<_Tp>(__x._M_size) {

    uninitialized_copy(__x._M_first, __x._M_first + __x._M_size,

                       this->_M_first);

  }

  // Constructors from auxiliary array types

  valarray(const slice_array<_Tp>&);

  valarray(const gslice_array<_Tp>&);

  valarray(const mask_array<_Tp>&);

  valarray(const indirect_array<_Tp>&);

  // Destructor

  ~valarray() { _STLP_STD::_Destroy_Range(this->_M_first, this->_M_first + this->_M_size); }

  // Extension: constructor that doesn't initialize valarray elements to a

  // specific value.  This is faster for types such as int and double.

private:

  void _M_initialize(const __true_type&) {}

  void _M_initialize(const __false_type&)

    { uninitialized_fill_n(this->_M_first, this->_M_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }

public:

  struct _NoInit {};

  valarray(size_t __n, _NoInit) : _Valarray_base<_Tp>(__n) {

    typedef typename __type_traits<_Tp>::has_trivial_default_constructor _Is_Trivial;

    _M_initialize(_Is_Trivial());

  }

public:                         // Assignment

  // Basic assignment.  Note that 'x = y' is undefined if x.size() != y.size()

  valarray<_Tp>& operator=(const valarray<_Tp>& __x) {

    _STLP_ASSERT(__x.size() == this->size())

    if (this != &__x)

	{

#ifdef __SYMBIAN32__

      /* Eventhough the behavior is undefined when the sizes are different,

         copying the data correspoding to the minimum of both the lengths 

         will prevent a crash */ 

      if( this->size() < __x._M_size )

    	  copy(__x._M_first, __x._M_first + this->size(), this->_M_first);

      else

    	  copy(__x._M_first, __x._M_first + __x._M_size, this->_M_first);

#else /* __SYMBIAN32__ */

      copy(__x._M_first, __x._M_first + __x._M_size, this->_M_first);

#endif /* __SYMBIAN32__ */

     }

    return *this;

  }

  // Scalar assignment

  valarray<_Tp>& operator=(const value_type& __x) {

    fill_n(this->_M_first, this->_M_size, __x);

    return *this;

  }

  // Assignment of auxiliary array types

  valarray<_Tp>& operator=(const slice_array<_Tp>&);

  valarray<_Tp>& operator=(const gslice_array<_Tp>&);

  valarray<_Tp>& operator=(const mask_array<_Tp>&);

  valarray<_Tp>& operator=(const indirect_array<_Tp>&);

public:                         // Element access

  value_type  operator[](size_t __n) const { return this->_M_first[__n]; }

  value_type& operator[](size_t __n)       { return this->_M_first[__n]; }

  size_t size() const { return this->_M_size; }

public:                         // Subsetting operations with auxiliary type

  valarray<_Tp>            operator[](slice) const;

  slice_array<_Tp>    operator[](slice);

  valarray<_Tp>            operator[](const gslice&) const;

  gslice_array<_Tp>   operator[](const gslice&);

  valarray<_Tp>            operator[](const _Valarray_bool&) const;

  mask_array<_Tp>     operator[](const _Valarray_bool&);

  valarray<_Tp>            operator[](const _Valarray_size_t&) const;

  indirect_array<_Tp> operator[](const _Valarray_size_t&);

public:                         // Unary operators.

  valarray<_Tp> operator+() const { return *this; }

  valarray<_Tp> operator-() const {

    valarray<_Tp> __tmp(this->size(), _NoInit());

    for (size_t __i = 0; __i < this->size(); ++__i)

      __tmp[__i] = -(*this)[__i];

    return __tmp;

  }

  valarray<_Tp> operator~() const {

    valarray<_Tp> __tmp(this->size(), _NoInit());

    for (size_t __i = 0; __i < this->size(); ++__i)

      __tmp[__i] = ~(*this)[__i];

    return __tmp;

  }

  _Valarray_bool operator!() const;

public:                         // Scalar computed assignment.

  valarray<_Tp>& operator*= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] *= __x;

    return *this;

  }

  valarray<_Tp>& operator/= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] /= __x;

    return *this;

  }

  valarray<_Tp>& operator%= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] %= __x;

    return *this;

  }

  valarray<_Tp>& operator+= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] += __x;

    return *this;

  }

  valarray<_Tp>& operator-= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] -= __x;

    return *this;

  }

  valarray<_Tp>& operator^= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] ^= __x;

    return *this;

  }

  valarray<_Tp>& operator&= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] &= __x;

    return *this;

  }

  valarray<_Tp>& operator|= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] |= __x;

    return *this;

  }

  valarray<_Tp>& operator<<= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] <<= __x;

    return *this;

  }

  valarray<_Tp>& operator>>= (const value_type& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] >>= __x;

    return *this;

  }

public:                         // Array computed assignment.

  valarray<_Tp>& operator*= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] *= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator/= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] /= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator%= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] %= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator+= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] += __x[__i];

    return *this;

  }

  valarray<_Tp>& operator-= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] -= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator^= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] ^= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator&= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] &= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator|= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] |= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator<<= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] <<= __x[__i];

    return *this;

  }

  valarray<_Tp>& operator>>= (const valarray<_Tp>& __x) {

    for (size_t __i = 0; __i < this->size(); ++__i)

      (*this)[__i] >>= __x[__i];

    return *this;

  }

public:                         // Other member functions.

  // The result is undefined for zero-length arrays

  value_type sum() const {

    return accumulate(this->_M_first + 1, this->_M_first + this->_M_size,

                      (*this)[0]);

  }

  // The result is undefined for zero-length arrays

  value_type (min) () const {

    return *min_element(this->_M_first + 0, this->_M_first + this->_M_size);

  }

  value_type (max) () const {

    return *max_element(this->_M_first + 0, this->_M_first + this->_M_size);

  }

  valarray<_Tp> shift(int __n) const;

  valarray<_Tp> cshift(int __n) const;

  valarray<_Tp> apply(value_type __f(value_type)) const {

    valarray<_Tp> __tmp(this->size());

    transform(this->_M_first + 0, this->_M_first + this->_M_size, __tmp._M_first,

              __f);

    return __tmp;

  }

  valarray<_Tp> apply(value_type __f(const value_type&)) const {

    valarray<_Tp> __tmp(this->size());

    transform(this->_M_first + 0, this->_M_first + this->_M_size, __tmp._M_first,

              __f);

    return __tmp;

  }

  void resize(size_t __n, value_type __x = value_type()) {

    _STLP_STD::_Destroy_Range(this->_M_first, this->_M_first + this->_M_size);

    _Valarray_base<_Tp>::_M_deallocate();

    _Valarray_base<_Tp>::_M_allocate(__n);

    uninitialized_fill_n(this->_M_first, this->_M_size, __x);

  }

};

//----------------------------------------------------------------------

// valarray non-member functions.

// Binary arithmetic operations between two arrays.  Behavior is

// undefined if the two arrays do not have the same length.

template <class _Tp>

inline valarray<_Tp>  _STLP_CALL operator*(const valarray<_Tp>& __x,

                                           const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] * __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp>  _STLP_CALL operator/(const valarray<_Tp>& __x,

                                           const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] / __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp>  _STLP_CALL operator%(const valarray<_Tp>& __x,

                                           const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] % __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp>  _STLP_CALL operator+(const valarray<_Tp>& __x,

                                           const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] + __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp>  _STLP_CALL operator-(const valarray<_Tp>& __x,

                                           const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] - __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator^(const valarray<_Tp>& __x,

                               const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] ^ __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator&(const valarray<_Tp>& __x,

                               const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] & __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator|(const valarray<_Tp>& __x,

                               const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] | __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator<<(const valarray<_Tp>& __x,

                               const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] << __y[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator>>(const valarray<_Tp>& __x,

                               const valarray<_Tp>& __y) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i] >> __y[__i];

  return __tmp;

}

// Binary arithmetic operations between an array and a scalar.

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator*(const valarray<_Tp>& __x, const _Tp& __c) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i]  * __c;

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator*(const _Tp& __c, const valarray<_Tp>& __x) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __c * __x[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator/(const valarray<_Tp>& __x, const _Tp& __c) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i]  / __c;

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator/(const _Tp& __c, const valarray<_Tp>& __x) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __c / __x[__i];

  return __tmp;

}

template <class _Tp>

inline valarray<_Tp> _STLP_CALL operator%(const valarray<_Tp>& __x, const _Tp& __c) {

  typedef typename valarray<_Tp>::_NoInit _NoInit;

  valarray<_Tp> __tmp(__x.size(), _NoInit());

  for (size_t __i = 0; __i < __x.size(); ++__i)

    __tmp[__i] = __x[__i]  % __c;