/*
 * 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 __SGI_STL_VALARRAY_H
#define __SGI_STL_VALARRAY_H

#ifndef __STLPORT_CMATH
#include <cmath>
#endif
#ifndef __STLPORT_NEW
#include <new>
#endif
#ifndef __SGI_STL_INTERNAL_ALGO_H
#include <stl_algo.h>
#endif
#ifndef __SGI_STL_INTERNAL_NUMERIC_H
#include <stl_numeric.h>
#endif
#ifndef __STLPORT_LIMITS_H
#include <stl_limits.h>
#endif


__STL_BEGIN_NAMESPACE

class slice;
class gslice;

template <class _Tp> class valarray;
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(__STL_NO_BAD_ALLOC) && defined(__STL_USE_EXCEPTIONS)
      if (_M_first == 0) {
        _M_size = 0;
        throw __STLPORT_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>() {}
  valarray(size_t __n) : _Valarray_base<_Tp>(__n)
    { uninitialized_fill_n(this->_M_first, this->_M_size, 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() { destroy(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(__true_type) {}
  void _M_initialize(__false_type)
    { uninitialized_fill_n(this->_M_first, this->_M_size, value_type()); }

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) {
    if (this != &__x)
      copy(__x._M_first, __x._M_first + __x._M_size, this->_M_first);
    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[](gslice) const;
  gslice_array<_Tp>   operator[](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 {
    valarray<bool> __tmp(this->size(), valarray<bool>::_NoInit());
    for (size_t __i = 0; __i < this->size(); ++__i)
      __tmp[__i] = !(*this)[__i];
    return __tmp;
  }

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, 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, this->_M_first + this->_M_size, __tmp._M_first,
              __f);
    return __tmp;
  }
  
  void resize(size_t __n, value_type __x = value_type()) {
    destroy(this->_M_first, this->_M_first + this->_M_size);
    this->_Valarray_base<_Tp>::_M_deallocate();
    this->_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> 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> 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> 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> 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> 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> 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> 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>