code: # Created by Pearu Peterson, September 2002
  
  from __future__ import division, print_function, absolute_import
  
  __usage__ = """
  Build fftpack:
    python setup_fftpack.py build
  Run tests if scipy is installed:
    python -c 'import scipy;scipy.fftpack.test()'
  Run tests if fftpack is not installed:
    python tests/test_basic.py
  """
  
  from numpy.testing import (assert_, assert_equal, assert_array_almost_equal,
                             assert_array_almost_equal_nulp, assert_array_less)
  import pytest
  from pytest import raises as assert_raises
  from scipy.fftpack import ifft, fft, fftn, ifftn, rfft, irfft, fft2
  from scipy.fftpack import _fftpack as fftpack
  from scipy.fftpack.basic import _is_safe_size
  
  from numpy import (arange, add, array, asarray, zeros, dot, exp, pi,
                     swapaxes, double, cdouble)
  import numpy as np
  import numpy.fft
  from numpy.random import rand
  
  # "large" composite numbers supported by FFTPACK
  LARGE_COMPOSITE_SIZES = [
      2**13,
      2**5 * 3**5,
      2**3 * 3**3 * 5**2,
  ]
  SMALL_COMPOSITE_SIZES = [
      2,
      2*3*5,
      2*2*3*3,
  ]
  # prime
  LARGE_PRIME_SIZES = [
      2011
  ]
  SMALL_PRIME_SIZES = [
      29
  ]
  
  
  def _assert_close_in_norm(x, y, rtol, size, rdt):
      # helper function for testing
      err_msg = "size: %s  rdt: %s" % (size, rdt)
      assert_array_less(np.linalg.norm(x - y), rtol*np.linalg.norm(x), err_msg)
  
  
  def random(size):
      return rand(*size)
  
  
  def get_mat(n):
      data = arange(n)
      data = add.outer(data, data)
      return data
  
  
  def direct_dft(x):
      x = asarray(x)
      n = len(x)
      y = zeros(n, dtype=cdouble)
      w = -arange(n)*(2j*pi/n)
      for i in range(n):
          y[i] = dot(exp(i*w), x)
      return y
  
  
  def direct_idft(x):
      x = asarray(x)
      n = len(x)
      y = zeros(n, dtype=cdouble)
      w = arange(n)*(2j*pi/n)
      for i in range(n):
          y[i] = dot(exp(i*w), x)/n
      return y
  
  
  def direct_dftn(x):
      x = asarray(x)
      for axis in range(len(x.shape)):
          x = fft(x, axis=axis)
      return x
  
  
  def direct_idftn(x):
      x = asarray(x)
      for axis in range(len(x.shape)):
          x = ifft(x, axis=axis)
      return x
  
  
  def direct_rdft(x):
      x = asarray(x)
      n = len(x)
      w = -arange(n)*(2j*pi/n)
      r = zeros(n, dtype=double)
      for i in range(n//2+1):
          y = dot(exp(i*w), x)
          if i:
              r[2*i-1] = y.real
              if 2*i < n:
                  r[2*i] = y.imag
          else:
              r[0] = y.real
      return r
  
  
  def direct_irdft(x):
      x = asarray(x)
      n = len(x)
      x1 = zeros(n, dtype=cdouble)
      for i in range(n//2+1):
          if i:
              if 2*i < n:
                  x1[i] = x[2*i-1] + 1j*x[2*i]
                  x1[n-i] = x[2*i-1] - 1j*x[2*i]
              else:
                  x1[i] = x[2*i-1]
          else:
              x1[0] = x[0]
      return direct_idft(x1).real
  
  
  class _TestFFTBase(object):
      def setup_method(self):
          self.cdt = None
          self.rdt = None
          np.random.seed(1234)
  
      def test_definition(self):
          x = np.array([1,2,3,4+1j,1,2,3,4+2j], dtype=self.cdt)
          y = fft(x)
          assert_equal(y.dtype, self.cdt)
          y1 = direct_dft(x)
          assert_array_almost_equal(y,y1)
          x = np.array([1,2,3,4+0j,5], dtype=self.cdt)
          assert_array_almost_equal(fft(x),direct_dft(x))
  
      def test_n_argument_real(self):
          x1 = np.array([1,2,3,4], dtype=self.rdt)
          x2 = np.array([1,2,3,4], dtype=self.rdt)
          y = fft([x1,x2],n=4)
          assert_equal(y.dtype, self.cdt)
          assert_equal(y.shape,(2,4))
          assert_array_almost_equal(y[0],direct_dft(x1))
          assert_array_almost_equal(y[1],direct_dft(x2))
  
      def _test_n_argument_complex(self):
          x1 = np.array([1,2,3,4+1j], dtype=self.cdt)
          x2 = np.array([1,2,3,4+1j], dtype=self.cdt)
          y = fft([x1,x2],n=4)
          assert_equal(y.dtype, self.cdt)
          assert_equal(y.shape,(2,4))
          assert_array_almost_equal(y[0],direct_dft(x1))
          assert_array_almost_equal(y[1],direct_dft(x2))
  
      def test_djbfft(self):
          for i in range(2,14):
              n = 2**i
              x = list(range(n))
              y = fftpack.zfft(x)
              y2 = numpy.fft.fft(x)
              assert_array_almost_equal(y,y2)
              y = fftpack.zrfft(x)
              assert_array_almost_equal(y,y2)
  
      def test_invalid_sizes(self):
          assert_raises(ValueError, fft, [])
          assert_raises(ValueError, fft, [[1,1],[2,2]], -5)
  
      def test__is_safe_size(self):
          vals = [(0, True), (1, True), (2, True), (3, True), (4, True), (5, True), (6, True), (7, False),
                  (15, True), (16, True), (17, False), (18, True), (21, False), (25, True), (50, True),
                  (120, True), (210, False)]
          for n, is_safe in vals:
              assert_equal(_is_safe_size(n), is_safe)
  
  
  class TestDoubleFFT(_TestFFTBase):
      def setup_method(self):
          self.cdt = np.cdouble
          self.rdt = np.double
  
  
  class TestSingleFFT(_TestFFTBase):
      def setup_method(self):
          self.cdt = np.complex64
          self.rdt = np.float32
  
      @pytest.mark.xfail(run=False, reason="single-precision FFT implementation is partially disabled, until accuracy issues with large prime powers are resolved")
      def test_notice(self):
          pass
  
  
  class TestFloat16FFT(object):
  
      def test_1_argument_real(self):
          x1 = np.array([1, 2, 3, 4], dtype=np.float16)
          y = fft(x1, n=4)
          assert_equal(y.dtype, np.complex64)
          assert_equal(y.shape, (4, ))
          assert_array_almost_equal(y, direct_dft(x1.astype(np.float32)))
  
      def test_n_argument_real(self):
          x1 = np.array([1, 2, 3, 4], dtype=np.float16)
          x2 = np.array([1, 2, 3, 4], dtype=np.float16)
          y = fft([x1, x2], n=4)
          assert_equal(y.dtype, np.complex64)
          assert_equal(y.shape, (2, 4))
          assert_array_almost_equal(y[0], direct_dft(x1.astype(np.float32)))
          assert_array_almost_equal(y[1], direct_dft(x2.astype(np.float32)))
  
  
  class _TestIFFTBase(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_definition(self):
          x = np.array([1,2,3,4+1j,1,2,3,4+2j], self.cdt)
          y = ifft(x)
          y1 = direct_idft(x)
          assert_equal(y.dtype, self.cdt)
          assert_array_almost_equal(y,y1)
  
          x = np.array([1,2,3,4+0j,5], self.cdt)
          assert_array_almost_equal(ifft(x),direct_idft(x))
  
      def test_definition_real(self):
          x = np.array([1,2,3,4,1,2,3,4], self.rdt)
          y = ifft(x)
          assert_equal(y.dtype, self.cdt)
          y1 = direct_idft(x)
          assert_array_almost_equal(y,y1)
  
          x = np.array([1,2,3,4,5], dtype=self.rdt)
          assert_equal(y.dtype, self.cdt)
          assert_array_almost_equal(ifft(x),direct_idft(x))
  
      def test_djbfft(self):
          for i in range(2,14):
              n = 2**i
              x = list(range(n))
              y = fftpack.zfft(x,direction=-1)
              y2 = numpy.fft.ifft(x)
              assert_array_almost_equal(y,y2)
              y = fftpack.zrfft(x,direction=-1)
              assert_array_almost_equal(y,y2)
  
      def test_random_complex(self):
          for size in [1,51,111,100,200,64,128,256,1024]:
              x = random([size]).astype(self.cdt)
              x = random([size]).astype(self.cdt) + 1j*x
              y1 = ifft(fft(x))
              y2 = fft(ifft(x))
              assert_equal(y1.dtype, self.cdt)
              assert_equal(y2.dtype, self.cdt)
              assert_array_almost_equal(y1, x)
              assert_array_almost_equal(y2, x)
  
      def test_random_real(self):
          for size in [1,51,111,100,200,64,128,256,1024]:
              x = random([size]).astype(self.rdt)
              y1 = ifft(fft(x))
              y2 = fft(ifft(x))
              assert_equal(y1.dtype, self.cdt)
              assert_equal(y2.dtype, self.cdt)
              assert_array_almost_equal(y1, x)
              assert_array_almost_equal(y2, x)
  
      def test_size_accuracy(self):
          # Sanity check for the accuracy for prime and non-prime sized inputs
          if self.rdt == np.float32:
              rtol = 1e-5
          elif self.rdt == np.float64:
              rtol = 1e-10
  
          for size in LARGE_COMPOSITE_SIZES + LARGE_PRIME_SIZES:
              np.random.seed(1234)
              x = np.random.rand(size).astype(self.rdt)
              y = ifft(fft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
              y = fft(ifft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
  
              x = (x + 1j*np.random.rand(size)).astype(self.cdt)
              y = ifft(fft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
              y = fft(ifft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
  
      def test_invalid_sizes(self):
          assert_raises(ValueError, ifft, [])
          assert_raises(ValueError, ifft, [[1,1],[2,2]], -5)
  
  
  class TestDoubleIFFT(_TestIFFTBase):
      def setup_method(self):
          self.cdt = np.cdouble
          self.rdt = np.double
  
  
  class TestSingleIFFT(_TestIFFTBase):
      def setup_method(self):
          self.cdt = np.complex64
          self.rdt = np.float32
  
  
  class _TestRFFTBase(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_definition(self):
          for t in [[1, 2, 3, 4, 1, 2, 3, 4], [1, 2, 3, 4, 1, 2, 3, 4, 5]]:
              x = np.array(t, dtype=self.rdt)
              y = rfft(x)
              y1 = direct_rdft(x)
              assert_array_almost_equal(y,y1)
              assert_equal(y.dtype, self.rdt)
  
      def test_djbfft(self):
          from numpy.fft import fft as numpy_fft
          for i in range(2,14):
              n = 2**i
              x = list(range(n))
              y2 = numpy_fft(x)
              y1 = zeros((n,),dtype=double)
              y1[0] = y2[0].real
              y1[-1] = y2[n//2].real
              for k in range(1, n//2):
                  y1[2*k-1] = y2[k].real
                  y1[2*k] = y2[k].imag
              y = fftpack.drfft(x)
              assert_array_almost_equal(y,y1)
  
      def test_invalid_sizes(self):
          assert_raises(ValueError, rfft, [])
          assert_raises(ValueError, rfft, [[1,1],[2,2]], -5)
  
      # See gh-5790
      class MockSeries(object):
          def __init__(self, data):
              self.data = np.asarray(data)
  
          def __getattr__(self, item):
              try:
                  return getattr(self.data, item)
              except AttributeError:
                  raise AttributeError(("'MockSeries' object "
                                        "has no attribute '{attr}'".
                                        format(attr=item)))
  
      def test_non_ndarray_with_dtype(self):
          x = np.array([1., 2., 3., 4., 5.])
          xs = _TestRFFTBase.MockSeries(x)
  
          expected = [1, 2, 3, 4, 5]
          out = rfft(xs)
  
          # Data should not have been overwritten
          assert_equal(x, expected)
          assert_equal(xs.data, expected)
  
  class TestRFFTDouble(_TestRFFTBase):
      def setup_method(self):
          self.cdt = np.cdouble
          self.rdt = np.double
  
  
  class TestRFFTSingle(_TestRFFTBase):
      def setup_method(self):
          self.cdt = np.complex64
          self.rdt = np.float32
  
  
  class _TestIRFFTBase(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_definition(self):
          x1 = [1,2,3,4,1,2,3,4]
          x1_1 = [1,2+3j,4+1j,2+3j,4,2-3j,4-1j,2-3j]
          x2 = [1,2,3,4,1,2,3,4,5]
          x2_1 = [1,2+3j,4+1j,2+3j,4+5j,4-5j,2-3j,4-1j,2-3j]
  
          def _test(x, xr):
              y = irfft(np.array(x, dtype=self.rdt))
              y1 = direct_irdft(x)
              assert_equal(y.dtype, self.rdt)
              assert_array_almost_equal(y,y1, decimal=self.ndec)
              assert_array_almost_equal(y,ifft(xr), decimal=self.ndec)
  
          _test(x1, x1_1)
          _test(x2, x2_1)
  
      def test_djbfft(self):
          from numpy.fft import ifft as numpy_ifft
          for i in range(2,14):
              n = 2**i
              x = list(range(n))
              x1 = zeros((n,),dtype=cdouble)
              x1[0] = x[0]
              for k in range(1, n//2):
                  x1[k] = x[2*k-1]+1j*x[2*k]
                  x1[n-k] = x[2*k-1]-1j*x[2*k]
              x1[n//2] = x[-1]
              y1 = numpy_ifft(x1)
              y = fftpack.drfft(x,direction=-1)
              assert_array_almost_equal(y,y1)
  
      def test_random_real(self):
          for size in [1,51,111,100,200,64,128,256,1024]:
              x = random([size]).astype(self.rdt)
              y1 = irfft(rfft(x))
              y2 = rfft(irfft(x))
              assert_equal(y1.dtype, self.rdt)
              assert_equal(y2.dtype, self.rdt)
              assert_array_almost_equal(y1, x, decimal=self.ndec,
                                         err_msg="size=%d" % size)
              assert_array_almost_equal(y2, x, decimal=self.ndec,
                                         err_msg="size=%d" % size)
  
      def test_size_accuracy(self):
          # Sanity check for the accuracy for prime and non-prime sized inputs
          if self.rdt == np.float32:
              rtol = 1e-5
          elif self.rdt == np.float64:
              rtol = 1e-10
  
          for size in LARGE_COMPOSITE_SIZES + LARGE_PRIME_SIZES:
              np.random.seed(1234)
              x = np.random.rand(size).astype(self.rdt)
              y = irfft(rfft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
              y = rfft(irfft(x))
              _assert_close_in_norm(x, y, rtol, size, self.rdt)
  
      def test_invalid_sizes(self):
          assert_raises(ValueError, irfft, [])
          assert_raises(ValueError, irfft, [[1,1],[2,2]], -5)
  
  
  # self.ndec is bogus; we should have a assert_array_approx_equal for number of
  # significant digits
  
  class TestIRFFTDouble(_TestIRFFTBase):
      def setup_method(self):
          self.cdt = np.cdouble
          self.rdt = np.double
          self.ndec = 14
  
  
  class TestIRFFTSingle(_TestIRFFTBase):
      def setup_method(self):
          self.cdt = np.complex64
          self.rdt = np.float32
          self.ndec = 5
  
  
  class Testfft2(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_regression_244(self):
          """FFT returns wrong result with axes parameter."""
          # fftn (and hence fft2) used to break when both axes and shape were
          # used
          x = numpy.ones((4, 4, 2))
          y = fft2(x, shape=(8, 8), axes=(-3, -2))
          y_r = numpy.fft.fftn(x, s=(8, 8), axes=(-3, -2))
          assert_array_almost_equal(y, y_r)
  
      def test_invalid_sizes(self):
          assert_raises(ValueError, fft2, [[]])
          assert_raises(ValueError, fft2, [[1, 1], [2, 2]], (4, -3))
  
  
  class TestFftnSingle(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_definition(self):
          x = [[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9]]
          y = fftn(np.array(x, np.float32))
          assert_(y.dtype == np.complex64,
                  msg="double precision output with single precision")
  
          y_r = np.array(fftn(x), np.complex64)
          assert_array_almost_equal_nulp(y, y_r)
  
      @pytest.mark.parametrize('size', SMALL_COMPOSITE_SIZES + SMALL_PRIME_SIZES)
      def test_size_accuracy_small(self, size):
          x = np.random.rand(size, size) + 1j*np.random.rand(size, size)
          y1 = fftn(x.real.astype(np.float32))
          y2 = fftn(x.real.astype(np.float64)).astype(np.complex64)
  
          assert_equal(y1.dtype, np.complex64)
          assert_array_almost_equal_nulp(y1, y2, 2000)
  
      @pytest.mark.parametrize('size', LARGE_COMPOSITE_SIZES + LARGE_PRIME_SIZES)
      def test_size_accuracy_large(self, size):
          x = np.random.rand(size, 3) + 1j*np.random.rand(size, 3)
          y1 = fftn(x.real.astype(np.float32))
          y2 = fftn(x.real.astype(np.float64)).astype(np.complex64)
  
          assert_equal(y1.dtype, np.complex64)
          assert_array_almost_equal_nulp(y1, y2, 2000)
  
      def test_definition_float16(self):
          x = [[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9]]
          y = fftn(np.array(x, np.float16))
          assert_equal(y.dtype, np.complex64)
          y_r = np.array(fftn(x), np.complex64)
          assert_array_almost_equal_nulp(y, y_r)
  
      @pytest.mark.parametrize('size', SMALL_COMPOSITE_SIZES + SMALL_PRIME_SIZES)
      def test_float16_input_small(self, size):
          x = np.random.rand(size, size) + 1j*np.random.rand(size, size)
          y1 = fftn(x.real.astype(np.float16))
          y2 = fftn(x.real.astype(np.float64)).astype(np.complex64)
  
          assert_equal(y1.dtype, np.complex64)
          assert_array_almost_equal_nulp(y1, y2, 5e5)
  
      @pytest.mark.parametrize('size', LARGE_COMPOSITE_SIZES + LARGE_PRIME_SIZES)
      def test_float16_input_large(self, size):
          x = np.random.rand(size, 3) + 1j*np.random.rand(size, 3)
          y1 = fftn(x.real.astype(np.float16))
          y2 = fftn(x.real.astype(np.float64)).astype(np.complex64)
  
          assert_equal(y1.dtype, np.complex64)
          assert_array_almost_equal_nulp(y1, y2, 2e6)
  
  
  class TestFftn(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_definition(self):
          x = [[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9]]
          y = fftn(x)
          assert_array_almost_equal(y, direct_dftn(x))
  
          x = random((20, 26))
          assert_array_almost_equal(fftn(x), direct_dftn(x))
  
          x = random((5, 4, 3, 20))
          assert_array_almost_equal(fftn(x), direct_dftn(x))
  
      def test_axes_argument(self):
          # plane == ji_plane, x== kji_space
          plane1 = [[1, 2, 3],
                    [4, 5, 6],
                    [7, 8, 9]]
          plane2 = [[10, 11, 12],
                    [13, 14, 15],
                    [16, 17, 18]]
          plane3 = [[19, 20, 21],
                    [22, 23, 24],
                    [25, 26, 27]]
          ki_plane1 = [[1, 2, 3],
                       [10, 11, 12],
                       [19, 20, 21]]
          ki_plane2 = [[4, 5, 6],
                       [13, 14, 15],
                       [22, 23, 24]]
          ki_plane3 = [[7, 8, 9],
                       [16, 17, 18],
                       [25, 26, 27]]
          jk_plane1 = [[1, 10, 19],
                       [4, 13, 22],
                       [7, 16, 25]]
          jk_plane2 = [[2, 11, 20],
                       [5, 14, 23],
                       [8, 17, 26]]
          jk_plane3 = [[3, 12, 21],
                       [6, 15, 24],
                       [9, 18, 27]]
          kj_plane1 = [[1, 4, 7],
                       [10, 13, 16], [19, 22, 25]]
          kj_plane2 = [[2, 5, 8],
                       [11, 14, 17], [20, 23, 26]]
          kj_plane3 = [[3, 6, 9],
                       [12, 15, 18], [21, 24, 27]]
          ij_plane1 = [[1, 4, 7],
                       [2, 5, 8],
                       [3, 6, 9]]
          ij_plane2 = [[10, 13, 16],
                       [11, 14, 17],
                       [12, 15, 18]]
          ij_plane3 = [[19, 22, 25],
                       [20, 23, 26],
                       [21, 24, 27]]
          ik_plane1 = [[1, 10, 19],
                       [2, 11, 20],
                       [3, 12, 21]]
          ik_plane2 = [[4, 13, 22],
                       [5, 14, 23],
                       [6, 15, 24]]
          ik_plane3 = [[7, 16, 25],
                       [8, 17, 26],
                       [9, 18, 27]]
          ijk_space = [jk_plane1, jk_plane2, jk_plane3]
          ikj_space = [kj_plane1, kj_plane2, kj_plane3]
          jik_space = [ik_plane1, ik_plane2, ik_plane3]
          jki_space = [ki_plane1, ki_plane2, ki_plane3]
          kij_space = [ij_plane1, ij_plane2, ij_plane3]
          x = array([plane1, plane2, plane3])
  
          assert_array_almost_equal(fftn(x),
                                    fftn(x, axes=(-3, -2, -1)))  # kji_space
          assert_array_almost_equal(fftn(x), fftn(x, axes=(0, 1, 2)))
          assert_array_almost_equal(fftn(x, axes=(0, 2)), fftn(x, axes=(0, -1)))
          y = fftn(x, axes=(2, 1, 0))  # ijk_space
          assert_array_almost_equal(swapaxes(y, -1, -3), fftn(ijk_space))
          y = fftn(x, axes=(2, 0, 1))  # ikj_space
          assert_array_almost_equal(swapaxes(swapaxes(y, -1, -3), -1, -2),
                                    fftn(ikj_space))
          y = fftn(x, axes=(1, 2, 0))  # jik_space
          assert_array_almost_equal(swapaxes(swapaxes(y, -1, -3), -3, -2),
                                    fftn(jik_space))
          y = fftn(x, axes=(1, 0, 2))  # jki_space
          assert_array_almost_equal(swapaxes(y, -2, -3), fftn(jki_space))
          y = fftn(x, axes=(0, 2, 1))  # kij_space
          assert_array_almost_equal(swapaxes(y, -2, -1), fftn(kij_space))
  
          y = fftn(x, axes=(-2, -1))  # ji_plane
          assert_array_almost_equal(fftn(plane1), y[0])
          assert_array_almost_equal(fftn(plane2), y[1])
          assert_array_almost_equal(fftn(plane3), y[2])
  
          y = fftn(x, axes=(1, 2))  # ji_plane
          assert_array_almost_equal(fftn(plane1), y[0])
          assert_array_almost_equal(fftn(plane2), y[1])
          assert_array_almost_equal(fftn(plane3), y[2])
  
          y = fftn(x, axes=(-3, -2))  # kj_plane
          assert_array_almost_equal(fftn(x[:, :, 0]), y[:, :, 0])
          assert_array_almost_equal(fftn(x[:, :, 1]), y[:, :, 1])
          assert_array_almost_equal(fftn(x[:, :, 2]), y[:, :, 2])
  
          y = fftn(x, axes=(-3, -1))  # ki_plane
          assert_array_almost_equal(fftn(x[:, 0, :]), y[:, 0, :])
          assert_array_almost_equal(fftn(x[:, 1, :]), y[:, 1, :])
          assert_array_almost_equal(fftn(x[:, 2, :]), y[:, 2, :])
  
          y = fftn(x, axes=(-1, -2))  # ij_plane
          assert_array_almost_equal(fftn(ij_plane1), swapaxes(y[0], -2, -1))
          assert_array_almost_equal(fftn(ij_plane2), swapaxes(y[1], -2, -1))
          assert_array_almost_equal(fftn(ij_plane3), swapaxes(y[2], -2, -1))
  
          y = fftn(x, axes=(-1, -3))  # ik_plane
          assert_array_almost_equal(fftn(ik_plane1),
                                    swapaxes(y[:, 0, :], -1, -2))
          assert_array_almost_equal(fftn(ik_plane2),
                                    swapaxes(y[:, 1, :], -1, -2))
          assert_array_almost_equal(fftn(ik_plane3),
                                    swapaxes(y[:, 2, :], -1, -2))
  
          y = fftn(x, axes=(-2, -3))  # jk_plane
          assert_array_almost_equal(fftn(jk_plane1),
                                    swapaxes(y[:, :, 0], -1, -2))
          assert_array_almost_equal(fftn(jk_plane2),
                                    swapaxes(y[:, :, 1], -1, -2))
          assert_array_almost_equal(fftn(jk_plane3),
                                    swapaxes(y[:, :, 2], -1, -2))
  
          y = fftn(x, axes=(-1,))  # i_line
          for i in range(3):
              for j in range(3):
                  assert_array_almost_equal(fft(x[i, j, :]), y[i, j, :])
          y = fftn(x, axes=(-2,))  # j_line
          for i in range(3):
              for j in range(3):
                  assert_array_almost_equal(fft(x[i, :, j]), y[i, :, j])
          y = fftn(x, axes=(0,))  # k_line
          for i in range(3):
              for j in range(3):
                  assert_array_almost_equal(fft(x[:, i, j]), y[:, i, j])
  
          y = fftn(x, axes=())  # point
          assert_array_almost_equal(y, x)
  
      def test_shape_argument(self):
          small_x = [[1, 2, 3],
                     [4, 5, 6]]
          large_x1 = [[1, 2, 3, 0],
                      [4, 5, 6, 0],
                      [0, 0, 0, 0],
                      [0, 0, 0, 0]]
  
          y = fftn(small_x, shape=(4, 4))
          assert_array_almost_equal(y, fftn(large_x1))
  
          y = fftn(small_x, shape=(3, 4))
          assert_array_almost_equal(y, fftn(large_x1[:-1]))
  
      def test_shape_axes_argument(self):
          small_x = [[1, 2, 3],
                     [4, 5, 6],
                     [7, 8, 9]]
          large_x1 = array([[1, 2, 3, 0],
                            [4, 5, 6, 0],
                            [7, 8, 9, 0],
                            [0, 0, 0, 0]])
          y = fftn(small_x, shape=(4, 4), axes=(-2, -1))
          assert_array_almost_equal(y, fftn(large_x1))
          y = fftn(small_x, shape=(4, 4), axes=(-1, -2))
  
          assert_array_almost_equal(y, swapaxes(
              fftn(swapaxes(large_x1, -1, -2)), -1, -2))
  
      def test_shape_axes_argument2(self):
          # Change shape of the last axis
          x = numpy.random.random((10, 5, 3, 7))
          y = fftn(x, axes=(-1,), shape=(8,))
          assert_array_almost_equal(y, fft(x, axis=-1, n=8))
  
          # Change shape of an arbitrary axis which is not the last one
          x = numpy.random.random((10, 5, 3, 7))
          y = fftn(x, axes=(-2,), shape=(8,))
          assert_array_almost_equal(y, fft(x, axis=-2, n=8))
  
          # Change shape of axes: cf #244, where shape and axes were mixed up
          x = numpy.random.random((4, 4, 2))
          y = fftn(x, axes=(-3, -2), shape=(8, 8))
          assert_array_almost_equal(y,
                                    numpy.fft.fftn(x, axes=(-3, -2), s=(8, 8)))
  
      def test_shape_argument_more(self):
          x = zeros((4, 4, 2))
          with assert_raises(ValueError,
                             match="when given, axes and shape arguments"
                             " have to be of the same length"):
              fftn(x, shape=(8, 8, 2, 1))
  
      def test_invalid_sizes(self):
          with assert_raises(ValueError,
                             match="invalid number of data points"
                             r" \(\[1 0\]\) specified"):
              fftn([[]])
  
          with assert_raises(ValueError,
                             match="invalid number of data points"
                             r" \(\[ 4 -3\]\) specified"):
              fftn([[1, 1], [2, 2]], (4, -3))
  
  
  class TestIfftn(object):
      dtype = None
      cdtype = None
  
      def setup_method(self):
          np.random.seed(1234)
  
      @pytest.mark.parametrize('dtype,cdtype,maxnlp',
                               [(np.float64, np.complex128, 2000),
                                (np.float32, np.complex64, 3500)])
      def test_definition(self, dtype, cdtype, maxnlp):
          x = np.array([[1, 2, 3],
                        [4, 5, 6],
                        [7, 8, 9]], dtype=dtype)
          y = ifftn(x)
          assert_equal(y.dtype, cdtype)
          assert_array_almost_equal_nulp(y, direct_idftn(x), maxnlp)
  
          x = random((20, 26))
          assert_array_almost_equal_nulp(ifftn(x), direct_idftn(x), maxnlp)
  
          x = random((5, 4, 3, 20))
          assert_array_almost_equal_nulp(ifftn(x), direct_idftn(x), maxnlp)
  
      @pytest.mark.parametrize('maxnlp', [2000, 3500])
      @pytest.mark.parametrize('size', [1, 2, 51, 32, 64, 92])
      def test_random_complex(self, maxnlp, size):
          x = random([size, size]) + 1j*random([size, size])
          assert_array_almost_equal_nulp(ifftn(fftn(x)), x, maxnlp)
          assert_array_almost_equal_nulp(fftn(ifftn(x)), x, maxnlp)
  
      def test_invalid_sizes(self):
          with assert_raises(ValueError,
                             match="invalid number of data points"
                             r" \(\[1 0\]\) specified"):
              ifftn([[]])
  
          with assert_raises(ValueError,
                             match="invalid number of data points"
                             r" \(\[ 4 -3\]\) specified"):
              ifftn([[1, 1], [2, 2]], (4, -3))
  
  
  class TestLongDoubleFailure(object):
      def setup_method(self):
          np.random.seed(1234)
  
      def test_complex(self):
          if np.dtype(np.longcomplex).itemsize == np.dtype(complex).itemsize:
              # longdouble == double; so fft is supported
              return
  
          x = np.random.randn(10).astype(np.longdouble) + \
                  1j * np.random.randn(10).astype(np.longdouble)
  
          for f in [fft, ifft]:
              try:
                  f(x)
                  raise AssertionError("Type {0} not supported but does not fail" %
                                       np.longcomplex)
              except ValueError:
                  pass
  
      def test_real(self):
          if np.dtype(np.longdouble).itemsize == np.dtype(np.double).itemsize:
              # longdouble == double; so fft is supported
              return
  
          x = np.random.randn(10).astype(np.longcomplex)
  
          for f in [fft, ifft]:
              try:
                  f(x)
                  raise AssertionError("Type %r not supported but does not fail" %
                                       np.longcomplex)
              except ValueError:
                  pass
  
  
  class FakeArray(object):
      def __init__(self, data):
          self._data = data
          self.__array_interface__ = data.__array_interface__
  
  
  class FakeArray2(object):
      def __init__(self, data):
          self._data = data
  
      def __array__(self):
          return self._data
  
  
  class TestOverwrite(object):
      """Check input overwrite behavior of the FFT functions."""
  
      real_dtypes = [np.float32, np.float64]
      dtypes = real_dtypes + [np.complex64, np.complex128]
      fftsizes = [8, 16, 32]
  
      def _check(self, x, routine, fftsize, axis, overwrite_x, should_overwrite):
          x2 = x.copy()
          for fake in [lambda x: x, FakeArray, FakeArray2]:
              routine(fake(x2), fftsize, axis, overwrite_x=overwrite_x)
  
              sig = "%s(%s%r, %r, axis=%r, overwrite_x=%r)" % (
                  routine.__name__, x.dtype, x.shape, fftsize, axis, overwrite_x)
              if not should_overwrite:
                  assert_equal(x2, x, err_msg="spurious overwrite in %s" % sig)
  
      def _check_1d(self, routine, dtype, shape, axis, overwritable_dtypes,
                    fftsize, overwrite_x):
          np.random.seed(1234)
          if np.issubdtype(dtype, np.complexfloating):
              data = np.random.randn(*shape) + 1j*np.random.randn(*shape)
          else:
              data = np.random.randn(*shape)
          data = data.astype(dtype)
  
          should_overwrite = (overwrite_x
                              and dtype in overwritable_dtypes
                              and fftsize <= shape[axis]
                              and (len(shape) == 1 or
                                   (axis % len(shape) == len(shape)-1
                                    and fftsize == shape[axis])))
          self._check(data, routine, fftsize, axis,
                      overwrite_x=overwrite_x,
                      should_overwrite=should_overwrite)
  
      @pytest.mark.parametrize('dtype', dtypes)
      @pytest.mark.parametrize('fftsize', fftsizes)
      @pytest.mark.parametrize('overwrite_x', [True, False])
      @pytest.mark.parametrize('shape,axes', [((16,), -1),
                                              ((16, 2), 0),
                                              ((2, 16), 1)])
      def test_fft_ifft(self, dtype, fftsize, overwrite_x, shape, axes):
          overwritable = (np.complex128, np.complex64)
          self._check_1d(fft, dtype, shape, axes, overwritable,
                         fftsize, overwrite_x)
          self._check_1d(ifft, dtype, shape, axes, overwritable,
                         fftsize, overwrite_x)
  
      @pytest.mark.parametrize('dtype', real_dtypes)
      @pytest.mark.parametrize('fftsize', fftsizes)
      @pytest.mark.parametrize('overwrite_x', [True, False])
      @pytest.mark.parametrize('shape,axes', [((16,), -1),
                                              ((16, 2), 0),
                                              ((2, 16), 1)])
      def test_rfft_irfft(self, dtype, fftsize, overwrite_x, shape, axes):
          overwritable = self.real_dtypes
          self._check_1d(irfft, dtype, shape, axes, overwritable,
                         fftsize, overwrite_x)
          self._check_1d(rfft, dtype, shape, axes, overwritable,
                         fftsize, overwrite_x)
  
      def _check_nd_one(self, routine, dtype, shape, axes, overwritable_dtypes,
                        overwrite_x):
          np.random.seed(1234)
          if np.issubdtype(dtype, np.complexfloating):
              data = np.random.randn(*shape) + 1j*np.random.randn(*shape)
          else:
              data = np.random.randn(*shape)
          data = data.astype(dtype)
  
          def fftshape_iter(shp):
              if len(shp) <= 0:
                  yield ()
              else:
                  for j in (shp[0]//2, shp[0], shp[0]*2):
                      for rest in fftshape_iter(shp[1:]):
                          yield (j,) + rest
  
          if axes is None:
              part_shape = shape
          else:
              part_shape = tuple(np.take(shape, axes))
  
          for fftshape in fftshape_iter(part_shape):
              should_overwrite = (overwrite_x
                                  and data.ndim == 1
                                  and np.all([x < y for x, y in zip(fftshape,
                                                                    part_shape)])
                                  and dtype in overwritable_dtypes)
              self._check(data, routine, fftshape, axes,
                          overwrite_x=overwrite_x,
                          should_overwrite=should_overwrite)
              if data.ndim > 1:
                  # check fortran order: it never overwrites
                  self._check(data.T, routine, fftshape, axes,
                              overwrite_x=overwrite_x,
                              should_overwrite=False)
  
      @pytest.mark.parametrize('dtype', dtypes)
      @pytest.mark.parametrize('overwrite_x', [True, False])
      @pytest.mark.parametrize('shape,axes', [((16,), None),
                                              ((16,), (0,)),
                                              ((16, 2), (0,)),
                                              ((2, 16), (1,)),
                                              ((8, 16), None),
                                              ((8, 16), (0, 1)),
                                              ((8, 16, 2), (0, 1)),
                                              ((8, 16, 2), (1, 2)),
                                              ((8, 16, 2), (0,)),
                                              ((8, 16, 2), (1,)),
                                              ((8, 16, 2), (2,)),
                                              ((8, 16, 2), None),
                                              ((8, 16, 2), (0, 1, 2))])
      def test_fftn_ifftn(self, dtype, overwrite_x, shape, axes):
          overwritable = (np.complex128, np.complex64)
          self._check_nd_one(fftn, dtype, shape, axes, overwritable,
                             overwrite_x)
          self._check_nd_one(ifftn, dtype, shape, axes, overwritable,
                             overwrite_x)
   from __future__ import division, absolute_import, print_function
  
  import sys
  import warnings
  import functools
  import operator
  import pytest
  
  import numpy as np
  from numpy.core._multiarray_tests import array_indexing
  from itertools import product
  from numpy.testing import (
      assert_, assert_equal, assert_raises, assert_array_equal, assert_warns,
      HAS_REFCOUNT, suppress_warnings,
      )
  
  
  class TestIndexing(object):
      def test_index_no_floats(self):
          a = np.array([[[5]]])
  
          assert_raises(IndexError, lambda: a[0.0])
          assert_raises(IndexError, lambda: a[0, 0.0])
          assert_raises(IndexError, lambda: a[0.0, 0])
          assert_raises(IndexError, lambda: a[0.0,:])
          assert_raises(IndexError, lambda: a[:, 0.0])
          assert_raises(IndexError, lambda: a[:, 0.0,:])
          assert_raises(IndexError, lambda: a[0.0,:,:])
          assert_raises(IndexError, lambda: a[0, 0, 0.0])
          assert_raises(IndexError, lambda: a[0.0, 0, 0])
          assert_raises(IndexError, lambda: a[0, 0.0, 0])
          assert_raises(IndexError, lambda: a[-1.4])
          assert_raises(IndexError, lambda: a[0, -1.4])
          assert_raises(IndexError, lambda: a[-1.4, 0])
          assert_raises(IndexError, lambda: a[-1.4,:])
          assert_raises(IndexError, lambda: a[:, -1.4])
          assert_raises(IndexError, lambda: a[:, -1.4,:])
          assert_raises(IndexError, lambda: a[-1.4,:,:])
          assert_raises(IndexError, lambda: a[0, 0, -1.4])
          assert_raises(IndexError, lambda: a[-1.4, 0, 0])
          assert_raises(IndexError, lambda: a[0, -1.4, 0])
          assert_raises(IndexError, lambda: a[0.0:, 0.0])
          assert_raises(IndexError, lambda: a[0.0:, 0.0,:])
  
      def test_slicing_no_floats(self):
          a = np.array([[5]])
  
          # start as float.
          assert_raises(TypeError, lambda: a[0.0:])
          assert_raises(TypeError, lambda: a[0:, 0.0:2])
          assert_raises(TypeError, lambda: a[0.0::2, :0])
          assert_raises(TypeError, lambda: a[0.0:1:2,:])
          assert_raises(TypeError, lambda: a[:, 0.0:])
          # stop as float.
          assert_raises(TypeError, lambda: a[:0.0])
          assert_raises(TypeError, lambda: a[:0, 1:2.0])
          assert_raises(TypeError, lambda: a[:0.0:2, :0])
          assert_raises(TypeError, lambda: a[:0.0,:])
          assert_raises(TypeError, lambda: a[:, 0:4.0:2])
          # step as float.
          assert_raises(TypeError, lambda: a[::1.0])
          assert_raises(TypeError, lambda: a[0:, :2:2.0])
          assert_raises(TypeError, lambda: a[1::4.0, :0])
          assert_raises(TypeError, lambda: a[::5.0,:])
          assert_raises(TypeError, lambda: a[:, 0:4:2.0])
          # mixed.
          assert_raises(TypeError, lambda: a[1.0:2:2.0])
          assert_raises(TypeError, lambda: a[1.0::2.0])
          assert_raises(TypeError, lambda: a[0:, :2.0:2.0])
          assert_raises(TypeError, lambda: a[1.0:1:4.0, :0])
          assert_raises(TypeError, lambda: a[1.0:5.0:5.0,:])
          assert_raises(TypeError, lambda: a[:, 0.4:4.0:2.0])
          # should still get the DeprecationWarning if step = 0.
          assert_raises(TypeError, lambda: a[::0.0])
  
      def test_index_no_array_to_index(self):
          # No non-scalar arrays.
          a = np.array([[[1]]])
  
          assert_raises(TypeError, lambda: a[a:a:a])
  
      def test_none_index(self):
          # `None` index adds newaxis
          a = np.array([1, 2, 3])
          assert_equal(a[None], a[np.newaxis])
          assert_equal(a[None].ndim, a.ndim + 1)
  
      def test_empty_tuple_index(self):
          # Empty tuple index creates a view
          a = np.array([1, 2, 3])
          assert_equal(a[()], a)
          assert_(a[()].base is a)
          a = np.array(0)
          assert_(isinstance(a[()], np.int_))
  
      def test_void_scalar_empty_tuple(self):
          s = np.zeros((), dtype='V4')
          assert_equal(s[()].dtype, s.dtype)
          assert_equal(s[()], s)
          assert_equal(type(s[...]), np.ndarray)
  
      def test_same_kind_index_casting(self):
          # Indexes should be cast with same-kind and not safe, even if that
          # is somewhat unsafe. So test various different code paths.
          index = np.arange(5)
          u_index = index.astype(np.uintp)
          arr = np.arange(10)
  
          assert_array_equal(arr[index], arr[u_index])
          arr[u_index] = np.arange(5)
          assert_array_equal(arr, np.arange(10))
  
          arr = np.arange(10).reshape(5, 2)
          assert_array_equal(arr[index], arr[u_index])
  
          arr[u_index] = np.arange(5)[:,None]
          assert_array_equal(arr, np.arange(5)[:,None].repeat(2, axis=1))
  
          arr = np.arange(25).reshape(5, 5)
          assert_array_equal(arr[u_index, u_index], arr[index, index])
  
      def test_empty_fancy_index(self):
          # Empty list index creates an empty array
          # with the same dtype (but with weird shape)
          a = np.array([1, 2, 3])
          assert_equal(a[[]], [])
          assert_equal(a[[]].dtype, a.dtype)
  
          b = np.array([], dtype=np.intp)
          assert_equal(a[[]], [])
          assert_equal(a[[]].dtype, a.dtype)
  
          b = np.array([])
          assert_raises(IndexError, a.__getitem__, b)
  
      def test_ellipsis_index(self):
          a = np.array([[1, 2, 3],
                        [4, 5, 6],
                        [7, 8, 9]])
          assert_(a[...] is not a)
          assert_equal(a[...], a)
          # `a[...]` was `a` in numpy <1.9.
          assert_(a[...].base is a)
  
          # Slicing with ellipsis can skip an
          # arbitrary number of dimensions
          assert_equal(a[0, ...], a[0])
          assert_equal(a[0, ...], a[0,:])
          assert_equal(a[..., 0], a[:, 0])
  
          # Slicing with ellipsis always results
          # in an array, not a scalar
          assert_equal(a[0, ..., 1], np.array(2))
  
          # Assignment with `(Ellipsis,)` on 0-d arrays
          b = np.array(1)
          b[(Ellipsis,)] = 2
          assert_equal(b, 2)
  
      def test_single_int_index(self):
          # Single integer index selects one row
          a = np.array([[1, 2, 3],
                        [4, 5, 6],
                        [7, 8, 9]])
  
          assert_equal(a[0], [1, 2, 3])
          assert_equal(a[-1], [7, 8, 9])
  
          # Index out of bounds produces IndexError
          assert_raises(IndexError, a.__getitem__, 1 << 30)
          # Index overflow produces IndexError
          assert_raises(IndexError, a.__getitem__, 1 << 64)
  
      def test_single_bool_index(self):
          # Single boolean index
          a = np.array([[1, 2, 3],
                        [4, 5, 6],
                        [7, 8, 9]])
  
          assert_equal(a[np.array(True)], a[None])
          assert_equal(a[np.array(False)], a[None][0:0])
  
      def test_boolean_shape_mismatch(self):
          arr = np.ones((5, 4, 3))
  
          index = np.array([True])
          assert_raises(IndexError, arr.__getitem__, index)
  
          index = np.array([False] * 6)
          assert_raises(IndexError, arr.__getitem__, index)
  
          index = np.zeros((4, 4), dtype=bool)
          assert_raises(IndexError, arr.__getitem__, index)
  
          assert_raises(IndexError, arr.__getitem__, (slice(None), index))
  
      def test_boolean_indexing_onedim(self):
          # Indexing a 2-dimensional array with
          # boolean array of length one
          a = np.array([[ 0.,  0.,  0.]])
          b = np.array([ True], dtype=bool)
          assert_equal(a[b], a)
          # boolean assignment
          a[b] = 1.
          assert_equal(a, [[1., 1., 1.]])
  
      def test_boolean_assignment_value_mismatch(self):
          # A boolean assignment should fail when the shape of the values
          # cannot be broadcast to the subscription. (see also gh-3458)
          a = np.arange(4)
  
          def f(a, v):
              a[a > -1] = v
  
          assert_raises(ValueError, f, a, [])
          assert_raises(ValueError, f, a, [1, 2, 3])
          assert_raises(ValueError, f, a[:1], [1, 2, 3])
  
      def test_boolean_assignment_needs_api(self):
          # See also gh-7666
          # This caused a segfault on Python 2 due to the GIL not being
          # held when the iterator does not need it, but the transfer function
          # does
          arr = np.zeros(1000)
          indx = np.zeros(1000, dtype=bool)
          indx[:100] = True
          arr[indx] = np.ones(100, dtype=object)
  
          expected = np.zeros(1000)
          expected[:100] = 1
          assert_array_equal(arr, expected)
  
      def test_boolean_indexing_twodim(self):
          # Indexing a 2-dimensional array with
          # 2-dimensional boolean array
          a = np.array([[1, 2, 3],
                        [4, 5, 6],
                        [7, 8, 9]])
          b = np.array([[ True, False,  True],
                        [False,  True, False],
                        [ True, False,  True]])
          assert_equal(a[b], [1, 3, 5, 7, 9])
          assert_equal(a[b[1]], [[4, 5, 6]])
          assert_equal(a[b[0]], a[b[2]])
  
          # boolean assignment
          a[b] = 0
          assert_equal(a, [[0, 2, 0],
                           [4, 0, 6],
                           [0, 8, 0]])
  
      def test_boolean_indexing_list(self):
          # Regression test for #13715. It's a use-after-free bug which the
          # test won't directly catch, but it will show up in valgrind.
          a = np.array([1, 2, 3])
          b = [True, False, True]
          # Two variants of the test because the first takes a fast path
          assert_equal(a[b], [1, 3])
          assert_equal(a[None, b], [[1, 3]])
  
      def test_reverse_strides_and_subspace_bufferinit(self):
          # This tests that the strides are not reversed for simple and
          # subspace fancy indexing.
          a = np.ones(5)
          b = np.zeros(5, dtype=np.intp)[::-1]
          c = np.arange(5)[::-1]
  
          a[b] = c
          # If the strides are not reversed, the 0 in the arange comes last.
          assert_equal(a[0], 0)
  
          # This also tests that the subspace buffer is initialized:
          a = np.ones((5, 2))
          c = np.arange(10).reshape(5, 2)[::-1]
          a[b, :] = c
          assert_equal(a[0], [0, 1])
  
      def test_reversed_strides_result_allocation(self):
          # Test a bug when calculating the output strides for a result array
          # when the subspace size was 1 (and test other cases as well)
          a = np.arange(10)[:, None]
          i = np.arange(10)[::-1]
          assert_array_equal(a[i], a[i.copy('C')])
  
          a = np.arange(20).reshape(-1, 2)
  
      def test_uncontiguous_subspace_assignment(self):
          # During development there was a bug activating a skip logic
          # based on ndim instead of size.
          a = np.full((3, 4, 2), -1)
          b = np.full((3, 4, 2), -1)
  
          a[[0, 1]] = np.arange(2 * 4 * 2).reshape(2, 4, 2).T
          b[[0, 1]] = np.arange(2 * 4 * 2).reshape(2, 4, 2).T.copy()
  
          assert_equal(a, b)
  
      def test_too_many_fancy_indices_special_case(self):
          # Just documents behaviour, this is a small limitation.
          a = np.ones((1,) * 32)  # 32 is NPY_MAXDIMS
          assert_raises(IndexError, a.__getitem__, (np.array([0]),) * 32)
  
      def test_scalar_array_bool(self):
          # NumPy bools can be used as boolean index (python ones as of yet not)
          a = np.array(1)
          assert_equal(a[np.bool_(True)], a[np.array(True)])
          assert_equal(a[np.bool_(False)], a[np.array(False)])
  
          # After deprecating bools as integers:
          #a = np.array([0,1,2])
          #assert_equal(a[True, :], a[None, :])
          #assert_equal(a[:, True], a[:, None])
          #
          #assert_(not np.may_share_memory(a, a[True, :]))
  
      def test_everything_returns_views(self):
          # Before `...` would return a itself.
          a = np.arange(5)
  
          assert_(a is not a[()])
          assert_(a is not a[...])
          assert_(a is not a[:])
  
      def test_broaderrors_indexing(self):
          a = np.zeros((5, 5))
          assert_raises(IndexError, a.__getitem__, ([0, 1], [0, 1, 2]))
          assert_raises(IndexError, a.__setitem__, ([0, 1], [0, 1, 2]), 0)
  
      def test_trivial_fancy_out_of_bounds(self):
          a = np.zeros(5)
          ind = np.ones(20, dtype=np.intp)
          ind[-1] = 10
          assert_raises(IndexError, a.__getitem__, ind)
          assert_raises(IndexError, a.__setitem__, ind, 0)
          ind = np.ones(20, dtype=np.intp)
          ind[0] = 11
          assert_raises(IndexError, a.__getitem__, ind)
          assert_raises(IndexError, a.__setitem__, ind, 0)
  
      def test_trivial_fancy_not_possible(self):
          # Test that the fast path for trivial assignment is not incorrectly
          # used when the index is not contiguous or 1D, see also gh-11467.
          a = np.arange(6)
          idx = np.arange(6, dtype=np.intp).reshape(2, 1, 3)[:, :, 0]
          assert_array_equal(a[idx], idx)
  
          # this case must not go into the fast path, note that idx is
          # a non-contiuguous none 1D array here.
          a[idx] = -1
          res = np.arange(6)
          res[0] = -1
          res[3] = -1
          assert_array_equal(a, res)
  
      def test_nonbaseclass_values(self):
          class SubClass(np.ndarray):
              def __array_finalize__(self, old):
                  # Have array finalize do funny things
                  self.fill(99)
  
          a = np.zeros((5, 5))
          s = a.copy().view(type=SubClass)
          s.fill(1)
  
          a[[0, 1, 2, 3, 4], :] = s
          assert_((a == 1).all())
  
          # Subspace is last, so transposing might want to finalize
          a[:, [0, 1, 2, 3, 4]] = s
          assert_((a == 1).all())
  
          a.fill(0)
          a[...] = s
          assert_((a == 1).all())
  
      def test_subclass_writeable(self):
          d = np.rec.array([('NGC1001', 11), ('NGC1002', 1.), ('NGC1003', 1.)],
                           dtype=[('target', 'S20'), ('V_mag', '>f4')])
          ind = np.array([False,  True,  True], dtype=bool)
          assert_(d[ind].flags.writeable)
          ind = np.array([0, 1])
          assert_(d[ind].flags.writeable)
          assert_(d[...].flags.writeable)
          assert_(d[0].flags.writeable)
  
      def test_memory_order(self):
          # This is not necessary to preserve. Memory layouts for
          # more complex indices are not as simple.
          a = np.arange(10)
          b = np.arange(10).reshape(5,2).T
          assert_(a[b].flags.f_contiguous)
  
          # Takes a different implementation branch:
          a = a.reshape(-1, 1)
          assert_(a[b, 0].flags.f_contiguous)
  
      def test_scalar_return_type(self):
          # Full scalar indices should return scalars and object
          # arrays should not call PyArray_Return on their items
          class Zero(object):
              # The most basic valid indexing
              def __index__(self):
                  return 0
  
          z = Zero()
  
          class ArrayLike(object):
              # Simple array, should behave like the array
              def __array__(self):
                  return np.array(0)
  
          a = np.zeros(())
          assert_(isinstance(a[()], np.float_))
          a = np.zeros(1)
          assert_(isinstance(a[z], np.float_))
          a = np.zeros((1, 1))
          assert_(isinstance(a[z, np.array(0)], np.float_))
          assert_(isinstance(a[z, ArrayLike()], np.float_))
  
          # And object arrays do not call it too often:
          b = np.array(0)
          a = np.array(0, dtype=object)
          a[()] = b
          assert_(isinstance(a[()], np.ndarray))
          a = np.array([b, None])
          assert_(isinstance(a[z], np.ndarray))
          a = np.array([[b, None]])
          assert_(isinstance(a[z, np.array(0)], np.ndarray))
          assert_(isinstance(a[z, ArrayLike()], np.ndarray))
  
      def test_small_regressions(self):
          # Reference count of intp for index checks
          a = np.array([0])
          if HAS_REFCOUNT:
              refcount = sys.getrefcount(np.dtype(np.intp))
          # item setting always checks indices in separate function:
          a[np.array([0], dtype=np.intp)] = 1
          a[np.array([0], dtype=np.uint8)] = 1
          assert_raises(IndexError, a.__setitem__,
                        np.array([1], dtype=np.intp), 1)
          assert_raises(IndexError, a.__setitem__,
                        np.array([1], dtype=np.uint8), 1)
  
          if HAS_REFCOUNT:
              assert_equal(sys.getrefcount(np.dtype(np.intp)), refcount)
  
      def test_unaligned(self):
          v = (np.zeros(64, dtype=np.int8) + ord('a'))[1:-7]
          d = v.view(np.dtype("S8"))
          # unaligned source
          x = (np.zeros(16, dtype=np.int8) + ord('a'))[1:-7]
          x = x.view(np.dtype("S8"))
          x[...] = np.array("b" * 8, dtype="S")
          b = np.arange(d.size)
          #trivial
          assert_equal(d[b], d)
          d[b] = x
          # nontrivial
          # unaligned index array
          b = np.zeros(d.size + 1).view(np.int8)[1:-(np.intp(0).itemsize - 1)]
          b = b.view(np.intp)[:d.size]
          b[...] = np.arange(d.size)
          assert_equal(d[b.astype(np.int16)], d)
          d[b.astype(np.int16)] = x
          # boolean
          d[b % 2 == 0]
          d[b % 2 == 0] = x[::2]
  
      def test_tuple_subclass(self):
          arr = np.ones((5, 5))
  
          # A tuple subclass should also be an nd-index
          class TupleSubclass(tuple):
              pass
          index = ([1], [1])
          index = TupleSubclass(index)
          assert_(arr[index].shape == (1,))
          # Unlike the non nd-index:
          assert_(arr[index,].shape != (1,))
  
      def test_broken_sequence_not_nd_index(self):
          # See gh-5063:
          # If we have an object which claims to be a sequence, but fails
          # on item getting, this should not be converted to an nd-index (tuple)
          # If this object happens to be a valid index otherwise, it should work
          # This object here is very dubious and probably bad though:
          class SequenceLike(object):
              def __index__(self):
                  return 0
  
              def __len__(self):
                  return 1
  
              def __getitem__(self, item):
                  raise IndexError('Not possible')
  
          arr = np.arange(10)
          assert_array_equal(arr[SequenceLike()], arr[SequenceLike(),])
  
          # also test that field indexing does not segfault
          # for a similar reason, by indexing a structured array
          arr = np.zeros((1,), dtype=[('f1', 'i8'), ('f2', 'i8')])
          assert_array_equal(arr[SequenceLike()], arr[SequenceLike(),])
  
      def test_indexing_array_weird_strides(self):
          # See also gh-6221
          # the shapes used here come from the issue and create the correct
          # size for the iterator buffering size.
          x = np.ones(10)
          x2 = np.ones((10, 2))
          ind = np.arange(10)[:, None, None, None]
          ind = np.broadcast_to(ind, (10, 55, 4, 4))
  
          # single advanced index case
          assert_array_equal(x[ind], x[ind.copy()])
          # higher dimensional advanced index
          zind = np.zeros(4, dtype=np.intp)
          assert_array_equal(x2[ind, zind], x2[ind.copy(), zind])
  
      def test_indexing_array_negative_strides(self):
          # From gh-8264,
          # core dumps if negative strides are used in iteration
          arro = np.zeros((4, 4))
          arr = arro[::-1, ::-1]
  
          slices = (slice(None), [0, 1, 2, 3])
          arr[slices] = 10
          assert_array_equal(arr, 10.)
  
  class TestFieldIndexing(object):
      def test_scalar_return_type(self):
          # Field access on an array should return an array, even if it
          # is 0-d.
          a = np.zeros((), [('a','f8')])
          assert_(isinstance(a['a'], np.ndarray))
          assert_(isinstance(a[['a']], np.ndarray))
  
  
  class TestBroadcastedAssignments(object):
      def assign(self, a, ind, val):
          a[ind] = val
          return a
  
      def test_prepending_ones(self):
          a = np.zeros((3, 2))
  
          a[...] = np.ones((1, 3, 2))
          # Fancy with subspace with and without transpose
          a[[0, 1, 2], :] = np.ones((1, 3, 2))
          a[:, [0, 1]] = np.ones((1, 3, 2))
          # Fancy without subspace (with broadcasting)
          a[[[0], [1], [2]], [0, 1]] = np.ones((1, 3, 2))
  
      def test_prepend_not_one(self):
          assign = self.assign
          s_ = np.s_
          a = np.zeros(5)
  
          # Too large and not only ones.
          assert_raises(ValueError, assign, a, s_[...],  np.ones((2, 1)))
          assert_raises(ValueError, assign, a, s_[[1, 2, 3],], np.ones((2, 1)))
          assert_raises(ValueError, assign, a, s_[[[1], [2]],], np.ones((2,2,1)))
  
      def test_simple_broadcasting_errors(self):
          assign = self.assign
          s_ = np.s_
          a = np.zeros((5, 1))
  
          assert_raises(ValueError, assign, a, s_[...], np.zeros((5, 2)))
          assert_raises(ValueError, assign, a, s_[...], np.zeros((5, 0)))
          assert_raises(ValueError, assign, a, s_[:, [0]], np.zeros((5, 2)))
          assert_raises(ValueError, assign, a, s_[:, [0]], np.zeros((5, 0)))
          assert_raises(ValueError, assign, a, s_[[0], :], np.zeros((2, 1)))
  
      def test_index_is_larger(self):
          # Simple case of fancy index broadcasting of the index.
          a = np.zeros((5, 5))
          a[[[0], [1], [2]], [0, 1, 2]] = [2, 3, 4]
  
          assert_((a[:3, :3] == [2, 3, 4]).all())
  
      def test_broadcast_subspace(self):
          a = np.zeros((100, 100))
          v = np.arange(100)[:,None]
          b = np.arange(100)[::-1]
          a[b] = v
          assert_((a[::-1] == v).all())
  
  
  class TestSubclasses(object):
      def test_basic(self):
          # Test that indexing in various ways produces SubClass instances,
          # and that the base is set up correctly: the original subclass
          # instance for views, and a new ndarray for advanced/boolean indexing
          # where a copy was made (latter a regression test for gh-11983).
          class SubClass(np.ndarray):
              pass
  
          a = np.arange(5)
          s = a.view(SubClass)
          s_slice = s[:3]
          assert_(type(s_slice) is SubClass)
          assert_(s_slice.base is s)
          assert_array_equal(s_slice, a[:3])
  
          s_fancy = s[[0, 1, 2]]
          assert_(type(s_fancy) is SubClass)
          assert_(s_fancy.base is not s)
          assert_(type(s_fancy.base) is np.ndarray)
          assert_array_equal(s_fancy, a[[0, 1, 2]])
          assert_array_equal(s_fancy.base, a[[0, 1, 2]])
  
          s_bool = s[s > 0]
          assert_(type(s_bool) is SubClass)
          assert_(s_bool.base is not s)
          assert_(type(s_bool.base) is np.ndarray)
          assert_array_equal(s_bool, a[a > 0])
          assert_array_equal(s_bool.base, a[a > 0])
  
      def test_finalize_gets_full_info(self):
          # Array finalize should be called on the filled array.
          class SubClass(np.ndarray):
              def __array_finalize__(self, old):
                  self.finalize_status = np.array(self)
                  self.old = old
  
          s = np.arange(10).view(SubClass)
          new_s = s[:3]
          assert_array_equal(new_s.finalize_status, new_s)
          assert_array_equal(new_s.old, s)
  
          new_s = s[[0,1,2,3]]
          assert_array_equal(new_s.finalize_status, new_s)
          assert_array_equal(new_s.old, s)
  
          new_s = s[s > 0]
          assert_array_equal(new_s.finalize_status, new_s)
          assert_array_equal(new_s.old, s)
  
      @pytest.mark.skipif(not HAS_REFCOUNT, reason="Python lacks refcounts")
      def test_slice_decref_getsetslice(self):
          # See gh-10066, a temporary slice object should be discarted.
          # This test is only really interesting on Python 2 since
          # it goes through `__set/getslice__` here and can probably be
          # removed. Use 0:7 to make sure it is never None:7.
          class KeepIndexObject(np.ndarray):
              def __getitem__(self, indx):
                  self.indx = indx
                  if indx == slice(0, 7):
                      raise ValueError
  
              def __setitem__(self, indx, val):
                  self.indx = indx
                  if indx == slice(0, 4):
                      raise ValueError
  
          k = np.array([1]).view(KeepIndexObject)
          k[0:5]
          assert_equal(k.indx, slice(0, 5))
          assert_equal(sys.getrefcount(k.indx), 2)
          try:
              k[0:7]
              raise AssertionError
          except ValueError:
              # The exception holds a reference to the slice so clear on Py2
              if hasattr(sys, 'exc_clear'):
                  with suppress_warnings() as sup:
                      sup.filter(DeprecationWarning)
                      sys.exc_clear()
          assert_equal(k.indx, slice(0, 7))
          assert_equal(sys.getrefcount(k.indx), 2)
  
          k[0:3] = 6
          assert_equal(k.indx, slice(0, 3))
          assert_equal(sys.getrefcount(k.indx), 2)
          try:
              k[0:4] = 2
              raise AssertionError
          except ValueError:
              # The exception holds a reference to the slice so clear on Py2
              if hasattr(sys, 'exc_clear'):
                  with suppress_warnings() as sup:
                      sup.filter(DeprecationWarning)
                      sys.exc_clear()
          assert_equal(k.indx, slice(0, 4))
          assert_equal(sys.getrefcount(k.indx), 2)
  
  
  class TestFancyIndexingCast(object):
      def test_boolean_index_cast_assign(self):
          # Setup the boolean index and float arrays.
          shape = (8, 63)
          bool_index = np.zeros(shape).astype(bool)
          bool_index[0, 1] = True
          zero_array = np.zeros(shape)
  
          # Assigning float is fine.
          zero_array[bool_index] = np.array([1])
          assert_equal(zero_array[0, 1], 1)
  
          # Fancy indexing works, although we get a cast warning.
          assert_warns(np.ComplexWarning,
                       zero_array.__setitem__, ([0], [1]), np.array([2 + 1j]))
          assert_equal(zero_array[0, 1], 2)  # No complex part
  
          # Cast complex to float, throwing away the imaginary portion.
          assert_warns(np.ComplexWarning,
                       zero_array.__setitem__, bool_index, np.array([1j]))
          assert_equal(zero_array[0, 1], 0)
  
  class TestFancyIndexingEquivalence(object):
      def test_object_assign(self):
          # Check that the field and object special case using copyto is active.
          # The right hand side cannot be converted to an array here.
          a = np.arange(5, dtype=object)
          b = a.copy()
          a[:3] = [1, (1,2), 3]
          b[[0, 1, 2]] = [1, (1,2), 3]
          assert_array_equal(a, b)
  
          # test same for subspace fancy indexing
          b = np.arange(5, dtype=object)[None, :]
          b[[0], :3] = [[1, (1,2), 3]]
          assert_array_equal(a, b[0])
  
          # Check that swapping of axes works.
          # There was a bug that made the later assignment throw a ValueError
          # do to an incorrectly transposed temporary right hand side (gh-5714)
          b = b.T
          b[:3, [0]] = [[1], [(1,2)], [3]]
          assert_array_equal(a, b[:, 0])
  
          # Another test for the memory order of the subspace
          arr = np.ones((3, 4, 5), dtype=object)
          # Equivalent slicing assignment for comparison
          cmp_arr = arr.copy()
          cmp_arr[:1, ...] = [[[1], [2], [3], [4]]]
          arr[[0], ...] = [[[1], [2], [3], [4]]]
          assert_array_equal(arr, cmp_arr)
          arr = arr.copy('F')
          arr[[0], ...] = [[[1], [2], [3], [4]]]
          assert_array_equal(arr, cmp_arr)
  
      def test_cast_equivalence(self):
          # Yes, normal slicing uses unsafe casting.
          a = np.arange(5)
          b = a.copy()
  
          a[:3] = np.array(['2', '-3', '-1'])
          b[[0, 2, 1]] = np.array(['2', '-1', '-3'])
          assert_array_equal(a, b)
  
          # test the same for subspace fancy indexing
          b = np.arange(5)[None, :]
          b[[0], :3] = np.array([['2', '-3', '-1']])
          assert_array_equal(a, b[0])
  
  
  class TestMultiIndexingAutomated(object):
      """
      These tests use code to mimic the C-Code indexing for selection.
  
      NOTE:
  
          * This still lacks tests for complex item setting.
          * If you change behavior of indexing, you might want to modify
            these tests to try more combinations.
          * Behavior was written to match numpy version 1.8. (though a
            first version matched 1.7.)
          * Only tuple indices are supported by the mimicking code.
            (and tested as of writing this)
          * Error types should match most of the time as long as there
            is only one error. For multiple errors, what gets raised
            will usually not be the same one. They are *not* tested.
  
      Update 2016-11-30: It is probably not worth maintaining this test
      indefinitely and it can be dropped if maintenance becomes a burden.
  
      """
  
      def setup(self):
          self.a = np.arange(np.prod([3, 1, 5, 6])).reshape(3, 1, 5, 6)
          self.b = np.empty((3, 0, 5, 6))
          self.complex_indices = ['skip', Ellipsis,
              0,
              # Boolean indices, up to 3-d for some special cases of eating up
              # dimensions, also need to test all False
              np.array([True, False, False]),
              np.array([[True, False], [False, True]]),
              np.array([[[False, False], [False, False]]]),
              # Some slices:
              slice(-5, 5, 2),
              slice(1, 1, 100),
              slice(4, -1, -2),
              slice(None, None, -3),
              # Some Fancy indexes:
              np.empty((0, 1, 1), dtype=np.intp),  # empty and can be broadcast
              np.array([0, 1, -2]),
              np.array([[2], [0], [1]]),
              np.array([[0, -1], [0, 1]], dtype=np.dtype('intp').newbyteorder()),
              np.array([2, -1], dtype=np.int8),
              np.zeros([1]*31, dtype=int),  # trigger too large array.
              np.array([0., 1.])]  # invalid datatype
          # Some simpler indices that still cover a bit more
          self.simple_indices = [Ellipsis, None, -1, [1], np.array([True]),
                                 'skip']
          # Very simple ones to fill the rest:
          self.fill_indices = [slice(None, None), 0]
  
      def _get_multi_index(self, arr, indices):
          """Mimic multi dimensional indexing.
  
          Parameters
          ----------
          arr : ndarray
              Array to be indexed.
          indices : tuple of index objects
  
          Returns
          -------
          out : ndarray
              An array equivalent to the indexing operation (but always a copy).
              `arr[indices]` should be identical.
          no_copy : bool
              Whether the indexing operation requires a copy. If this is `True`,
              `np.may_share_memory(arr, arr[indices])` should be `True` (with
              some exceptions for scalars and possibly 0-d arrays).
  
          Notes
          -----
          While the function may mostly match the errors of normal indexing this
          is generally not the case.
          """
          in_indices = list(indices)
          indices = []
          # if False, this is a fancy or boolean index
          no_copy = True
          # number of fancy/scalar indexes that are not consecutive
          num_fancy = 0
          # number of dimensions indexed by a "fancy" index
          fancy_dim = 0
          # NOTE: This is a funny twist (and probably OK to change).
          # The boolean array has illegal indexes, but this is
          # allowed if the broadcast fancy-indices are 0-sized.
          # This variable is to catch that case.
          error_unless_broadcast_to_empty = False
  
          # We need to handle Ellipsis and make arrays from indices, also
          # check if this is fancy indexing (set no_copy).
          ndim = 0
          ellipsis_pos = None  # define here mostly to replace all but first.
          for i, indx in enumerate(in_indices):
              if indx is None:
                  continue
              if isinstance(indx, np.ndarray) and indx.dtype == bool:
                  no_copy = False
                  if indx.ndim == 0:
                      raise IndexError
                  # boolean indices can have higher dimensions
                  ndim += indx.ndim
                  fancy_dim += indx.ndim
                  continue
              if indx is Ellipsis:
                  if ellipsis_pos is None:
                      ellipsis_pos = i
                      continue  # do not increment ndim counter
                  raise IndexError
              if isinstance(indx, slice):
                  ndim += 1
                  continue
              if not isinstance(indx, np.ndarray):
                  # This could be open for changes in numpy.
                  # numpy should maybe raise an error if casting to intp
                  # is not safe. It rejects np.array([1., 2.]) but not
                  # [1., 2.] as index (same for ie. np.take).
                  # (Note the importance of empty lists if changing this here)
                  try:
                      indx = np.array(indx, dtype=np.intp)
                  except ValueError:
                      raise IndexError
                  in_indices[i] = indx
              elif indx.dtype.kind != 'b' and indx.dtype.kind != 'i':
                  raise IndexError('arrays used as indices must be of '
                                   'integer (or boolean) type')
              if indx.ndim != 0:
                  no_copy = False
              ndim += 1
              fancy_dim += 1
  
          if arr.ndim - ndim < 0:
              # we can't take more dimensions then we have, not even for 0-d
              # arrays.  since a[()] makes sense, but not a[(),]. We will
              # raise an error later on, unless a broadcasting error occurs
              # first.
              raise IndexError
  
          if ndim == 0 and None not in in_indices:
              # Well we have no indexes or one Ellipsis. This is legal.
              return arr.copy(), no_copy
  
          if ellipsis_pos is not None:
              in_indices[ellipsis_pos:ellipsis_pos+1] = ([slice(None, None)] *
                                                         (arr.ndim - ndim))
  
          for ax, indx in enumerate(in_indices):
              if isinstance(indx, slice):
                  # convert to an index array
                  indx = np.arange(*indx.indices(arr.shape[ax]))
                  indices.append(['s', indx])
                  continue
              elif indx is None:
                  # this is like taking a slice with one element from a new axis:
                  indices.append(['n', np.array([0], dtype=np.intp)])
                  arr = arr.reshape((arr.shape[:ax] + (1,) + arr.shape[ax:]))
                  continue
              if isinstance(indx, np.ndarray) and indx.dtype == bool:
                  if indx.shape != arr.shape[ax:ax+indx.ndim]:
                      raise IndexError
  
                  try:
                      flat_indx = np.ravel_multi_index(np.nonzero(indx),
                                      arr.shape[ax:ax+indx.ndim], mode='raise')
                  except Exception:
                      error_unless_broadcast_to_empty = True
                      # fill with 0s instead, and raise error later
                      flat_indx = np.array([0]*indx.sum(), dtype=np.intp)
                  # concatenate axis into a single one:
                  if indx.ndim != 0:
                      arr = arr.reshape((arr.shape[:ax]
                                    + (np.prod(arr.shape[ax:ax+indx.ndim]),)
                                    + arr.shape[ax+indx.ndim:]))
                      indx = flat_indx
                  else:
                      # This could be changed, a 0-d boolean index can
                      # make sense (even outside the 0-d indexed array case)
                      # Note that originally this is could be interpreted as
                      # integer in the full integer special case.
                      raise IndexError
              else:
                  # If the index is a singleton, the bounds check is done
                  # before the broadcasting. This used to be different in <1.9
                  if indx.ndim == 0:
                      if indx >= arr.shape[ax] or indx < -arr.shape[ax]:
                          raise IndexError
              if indx.ndim == 0:
                  # The index is a scalar. This used to be two fold, but if
                  # fancy indexing was active, the check was done later,
                  # possibly after broadcasting it away (1.7. or earlier).
                  # Now it is always done.
                  if indx >= arr.shape[ax] or indx < - arr.shape[ax]:
                      raise IndexError
              if (len(indices) > 0 and
                      indices[-1][0] == 'f' and
                      ax != ellipsis_pos):
                  # NOTE: There could still have been a 0-sized Ellipsis
                  # between them. Checked that with ellipsis_pos.
                  indices[-1].append(indx)
              else:
                  # We have a fancy index that is not after an existing one.
                  # NOTE: A 0-d array triggers this as well, while one may
                  # expect it to not trigger it, since a scalar would not be
                  # considered fancy indexing.
                  num_fancy += 1
                  indices.append(['f', indx])
  
          if num_fancy > 1 and not no_copy:
              # We have to flush the fancy indexes left
              new_indices = indices[:]
              axes = list(range(arr.ndim))
              fancy_axes = []
              new_indices.insert(0, ['f'])
              ni = 0
              ai = 0
              for indx in indices:
                  ni += 1
                  if indx[0] == 'f':
                      new_indices[0].extend(indx[1:])
                      del new_indices[ni]
                      ni -= 1
                      for ax in range(ai, ai + len(indx[1:])):
                          fancy_axes.append(ax)
                          axes.remove(ax)
                  ai += len(indx) - 1  # axis we are at
              indices = new_indices
              # and now we need to transpose arr:
              arr = arr.transpose(*(fancy_axes + axes))
  
          # We only have one 'f' index now and arr is transposed accordingly.
          # Now handle newaxis by reshaping...
          ax = 0
          for indx in indices:
              if indx[0] == 'f':
                  if len(indx) == 1:
                      continue
                  # First of all, reshape arr to combine fancy axes into one:
                  orig_shape = arr.shape
                  orig_slice = orig_shape[ax:ax + len(indx[1:])]
                  arr = arr.reshape((arr.shape[:ax]
                                      + (np.prod(orig_slice).astype(int),)
                                      + arr.shape[ax + len(indx[1:]):]))
  
                  # Check if broadcasting works
                  res = np.broadcast(*indx[1:])
                  # unfortunately the indices might be out of bounds. So check
                  # that first, and use mode='wrap' then. However only if
                  # there are any indices...
                  if res.size != 0:
                      if error_unless_broadcast_to_empty:
                          raise IndexError
                      for _indx, _size in zip(indx[1:], orig_slice):
                          if _indx.size == 0:
                              continue
                          if np.any(_indx >= _size) or np.any(_indx < -_size):
                                  raise IndexError
                  if len(indx[1:]) == len(orig_slice):
                      if np.product(orig_slice) == 0:
                          # Work around for a crash or IndexError with 'wrap'
                          # in some 0-sized cases.
                          try:
                              mi = np.ravel_multi_index(indx[1:], orig_slice,
                                                        mode='raise')
                          except Exception:
                              # This happens with 0-sized orig_slice (sometimes?)
                              # here it is a ValueError, but indexing gives a:
                              raise IndexError('invalid index into 0-sized')
                      else:
                          mi = np.ravel_multi_index(indx[1:], orig_slice,
                                                    mode='wrap')
                  else:
                      # Maybe never happens...
                      raise ValueError
                  arr = arr.take(mi.ravel(), axis=ax)
                  try:
                      arr = arr.reshape((arr.shape[:ax]
                                          + mi.shape
                                          + arr.shape[ax+1:]))
                  except ValueError:
                      # too many dimensions, probably
                      raise IndexError
                  ax += mi.ndim
                  continue
  
              # If we are here, we have a 1D array for take:
              arr = arr.take(indx[1], axis=ax)
              ax += 1
  
          return arr, no_copy
  
      def _check_multi_index(self, arr, index):
          """Check a multi index item getting and simple setting.
  
          Parameters
          ----------
          arr : ndarray
              Array to be indexed, must be a reshaped arange.
          index : tuple of indexing objects
              Index being tested.
          """
          # Test item getting
          try:
              mimic_get, no_copy = self._get_multi_index(arr, index)
          except Exception as e:
              if HAS_REFCOUNT:
                  prev_refcount = sys.getrefcount(arr)
              assert_raises(type(e), arr.__getitem__, index)
              assert_raises(type(e), arr.__setitem__, index, 0)
              if HAS_REFCOUNT:
                  assert_equal(prev_refcount, sys.getrefcount(arr))
              return
  
          self._compare_index_result(arr, index, mimic_get, no_copy)
  
      def _check_single_index(self, arr, index):
          """Check a single index item getting and simple setting.
  
          Parameters
          ----------
          arr : ndarray
              Array to be indexed, must be an arange.
          index : indexing object
              Index being tested. Must be a single index and not a tuple
              of indexing objects (see also `_check_multi_index`).
          """
          try:
              mimic_get, no_copy = self._get_multi_index(arr, (index,))
          except Exception as e:
              if HAS_REFCOUNT:
                  prev_refcount = sys.getrefcount(arr)
              assert_raises(type(e), arr.__getitem__, index)
              assert_raises(type(e), arr.__setitem__, index, 0)
              if HAS_REFCOUNT:
                  assert_equal(prev_refcount, sys.getrefcount(arr))
              return
  
          self._compare_index_result(arr, index, mimic_get, no_copy)
  
      def _compare_index_result(self, arr, index, mimic_get, no_copy):
          """Compare mimicked result to indexing result.
          """
          arr = arr.copy()
          indexed_arr = arr[index]
          assert_array_equal(indexed_arr, mimic_get)
          # Check if we got a view, unless its a 0-sized or 0-d array.
          # (then its not a view, and that does not matter)
          if indexed_arr.size != 0 and indexed_arr.ndim != 0:
              assert_(np.may_share_memory(indexed_arr, arr) == no_copy)
              # Check reference count of the original array
              if HAS_REFCOUNT:
                  if no_copy:
                      # refcount increases by one:
                      assert_equal(sys.getrefcount(arr), 3)
                  else:
                      assert_equal(sys.getrefcount(arr), 2)
  
          # Test non-broadcast setitem:
          b = arr.copy()
          b[index] = mimic_get + 1000
          if b.size == 0:
              return  # nothing to compare here...
          if no_copy and indexed_arr.ndim != 0:
              # change indexed_arr in-place to manipulate original:
              indexed_arr += 1000
              assert_array_equal(arr, b)
              return
          # Use the fact that the array is originally an arange:
          arr.flat[indexed_arr.ravel()] += 1000
          assert_array_equal(arr, b)
  
      def test_boolean(self):
          a = np.array(5)
          assert_equal(a[np.array(True)], 5)
          a[np.array(True)] = 1
          assert_equal(a, 1)
          # NOTE: This is different from normal broadcasting, as
          # arr[boolean_array] works like in a multi index. Which means
          # it is aligned to the left. This is probably correct for
          # consistency with arr[boolean_array,] also no broadcasting
          # is done at all
          self._check_multi_index(
              self.a, (np.zeros_like(self.a, dtype=bool),))
          self._check_multi_index(
              self.a, (np.zeros_like(self.a, dtype=bool)[..., 0],))
          self._check_multi_index(
              self.a, (np.zeros_like(self.a, dtype=bool)[None, ...],))
  
      def test_multidim(self):
          # Automatically test combinations with complex indexes on 2nd (or 1st)
          # spot and the simple ones in one other spot.
          with warnings.catch_warnings():
              # This is so that np.array(True) is not accepted in a full integer
              # index, when running the file separately.
              warnings.filterwarnings('error', '', DeprecationWarning)
              warnings.filterwarnings('error', '', np.VisibleDeprecationWarning)
  
              def isskip(idx):
                  return isinstance(idx, str) and idx == "skip"
  
              for simple_pos in [0, 2, 3]:
                  tocheck = [self.fill_indices, self.complex_indices,
                             self.fill_indices, self.fill_indices]
                  tocheck[simple_pos] = self.simple_indices
                  for index in product(*tocheck):
                      index = tuple(i for i in index if not isskip(i))
                      self._check_multi_index(self.a, index)
                      self._check_multi_index(self.b, index)
  
          # Check very simple item getting:
          self._check_multi_index(self.a, (0, 0, 0, 0))
          self._check_multi_index(self.b, (0, 0, 0, 0))
          # Also check (simple cases of) too many indices:
          assert_raises(IndexError, self.a.__getitem__, (0, 0, 0, 0, 0))
          assert_raises(IndexError, self.a.__setitem__, (0, 0, 0, 0, 0), 0)
          assert_raises(IndexError, self.a.__getitem__, (0, 0, [1], 0, 0))
          assert_raises(IndexError, self.a.__setitem__, (0, 0, [1], 0, 0), 0)
  
      def test_1d(self):
          a = np.arange(10)
          for index in self.complex_indices:
              self._check_single_index(a, index)
  
  class TestFloatNonIntegerArgument(object):
      """
      These test that ``TypeError`` is raised when you try to use
      non-integers as arguments to for indexing and slicing e.g. ``a[0.0:5]``
      and ``a[0.5]``, or other functions like ``array.reshape(1., -1)``.
  
      """
      def test_valid_indexing(self):
          # These should raise no errors.
          a = np.array([[[5]]])
  
          a[np.array([0])]
          a[[0, 0]]
          a[:, [0, 0]]
          a[:, 0,:]
          a[:,:,:]
  
      def test_valid_slicing(self):
          # These should raise no errors.
          a = np.array([[[5]]])
  
          a[::]
          a[0:]
          a[:2]
          a[0:2]
          a[::2]
          a[1::2]
          a[:2:2]
          a[1:2:2]
  
      def test_non_integer_argument_errors(self):
          a = np.array([[5]])
  
          assert_raises(TypeError, np.reshape, a, (1., 1., -1))
          assert_raises(TypeError, np.reshape, a, (np.array(1.), -1))
          assert_raises(TypeError, np.take, a, [0], 1.)
          assert_raises(TypeError, np.take, a, [0], np.float64(1.))
  
      def test_non_integer_sequence_multiplication(self):
          # NumPy scalar sequence multiply should not work with non-integers
          def mult(a, b):
              return a * b
  
          assert_raises(TypeError, mult, [1], np.float_(3))
          # following should be OK
          mult([1], np.int_(3))
  
      def test_reduce_axis_float_index(self):
          d = np.zeros((3,3,3))
          assert_raises(TypeError, np.min, d, 0.5)
          assert_raises(TypeError, np.min, d, (0.5, 1))
          assert_raises(TypeError, np.min, d, (1, 2.2))
          assert_raises(TypeError, np.min, d, (.2, 1.2))
  
  
  class TestBooleanIndexing(object):
      # Using a boolean as integer argument/indexing is an error.
      def test_bool_as_int_argument_errors(self):
          a = np.array([[[1]]])
  
          assert_raises(TypeError, np.reshape, a, (True, -1))
          assert_raises(TypeError, np.reshape, a, (np.bool_(True), -1))
          # Note that operator.index(np.array(True)) does not work, a boolean
          # array is thus also deprecated, but not with the same message:
          assert_raises(TypeError, operator.index, np.array(True))
          assert_warns(DeprecationWarning, operator.index, np.True_)
          assert_raises(TypeError, np.take, args=(a, [0], False))
  
      def test_boolean_indexing_weirdness(self):
          # Weird boolean indexing things
          a = np.ones((2, 3, 4))
          a[False, True, ...].shape == (0, 2, 3, 4)
          a[True, [0, 1], True, True, [1], [[2]]] == (1, 2)
          assert_raises(IndexError, lambda: a[False, [0, 1], ...])
  
  
  class TestArrayToIndexDeprecation(object):
      """Creating an an index from array not 0-D is an error.
  
      """
      def test_array_to_index_error(self):
          # so no exception is expected. The raising is effectively tested above.
          a = np.array([[[1]]])
  
          assert_raises(TypeError, operator.index, np.array([1]))
          assert_raises(TypeError, np.reshape, a, (a, -1))
          assert_raises(TypeError, np.take, a, [0], a)
  
  
  class TestNonIntegerArrayLike(object):
      """Tests that array_likes only valid if can safely cast to integer.
  
      For instance, lists give IndexError when they cannot be safely cast to
      an integer.
  
      """
      def test_basic(self):
          a = np.arange(10)
  
          assert_raises(IndexError, a.__getitem__, [0.5, 1.5])
          assert_raises(IndexError, a.__getitem__, (['1', '2'],))
  
          # The following is valid
          a.__getitem__([])
  
  
  class TestMultipleEllipsisError(object):
      """An index can only have a single ellipsis.
  
      """
      def test_basic(self):
          a = np.arange(10)
          assert_raises(IndexError, lambda: a[..., ...])
          assert_raises(IndexError, a.__getitem__, ((Ellipsis,) * 2,))
          assert_raises(IndexError, a.__getitem__, ((Ellipsis,) * 3,))
  
  
  class TestCApiAccess(object):
      def test_getitem(self):
          subscript = functools.partial(array_indexing, 0)
  
          # 0-d arrays don't work:
          assert_raises(IndexError, subscript, np.ones(()), 0)
          # Out of bound values:
          assert_raises(IndexError, subscript, np.ones(10), 11)
          assert_raises(IndexError, subscript, np.ones(10), -11)
          assert_raises(IndexError, subscript, np.ones((10, 10)), 11)
          assert_raises(IndexError, subscript, np.ones((10, 10)), -11)
  
          a = np.arange(10)
          assert_array_equal(a[4], subscript(a, 4))
          a = a.reshape(5, 2)
          assert_array_equal(a[-4], subscript(a, -4))
  
      def test_setitem(self):
          assign = functools.partial(array_indexing, 1)
  
          # Deletion is impossible:
          assert_raises(ValueError, assign, np.ones(10), 0)
          # 0-d arrays don't work:
          assert_raises(IndexError, assign, np.ones(()), 0, 0)
          # Out of bound values:
          assert_raises(IndexError, assign, np.ones(10), 11, 0)
          assert_raises(IndexError, assign, np.ones(10), -11, 0)
          assert_raises(IndexError, assign, np.ones((10, 10)), 11, 0)
          assert_raises(IndexError, assign, np.ones((10, 10)), -11, 0)
  
          a = np.arange(10)
          assign(a, 4, 10)
          assert_(a[4] == 10)
  
          a = a.reshape(5, 2)
          assign(a, 4, 10)
          assert_array_equal(a[-1], [10, 10])
  
apis: numpy.take numpy.testing.assert_equal numpy.dtype scipy.fftpack.basic._is_safe_size numpy.issubdtype numpy.random.seed numpy.asarray numpy.add.outer scipy.fftpack.ifftn scipy.fftpack._fftpack.drfft scipy.fftpack.fft2 numpy.random.rand scipy.fftpack.rfft scipy.fftpack.ifft numpy.zeros scipy.fftpack.fftn scipy.fftpack.irfft numpy.arange numpy.testing.assert_array_almost_equal_nulp numpy.testing.assert_array_almost_equal numpy.linalg.norm numpy.fft.fft scipy.fftpack._fftpack.zfft scipy.fftpack.fft scipy.fftpack._fftpack.zrfft numpy.swapaxes numpy.random.randn numpy.exp numpy.fft.ifft numpy.array numpy.testing.assert_
apis: numpy.ones numpy.ravel_multi_index numpy.testing.assert_equal numpy.dtype numpy.any numpy.int_ numpy.testing.assert_warns numpy.float64 numpy.testing.assert_array_equal numpy.bool_ numpy.broadcast numpy.nonzero numpy.float_ numpy.zeros numpy.testing.suppress_warnings numpy.arange numpy.may_share_memory numpy.prod numpy.broadcast_to numpy.intp numpy.testing.assert_raises numpy.zeros_like numpy.empty numpy.product numpy.array numpy.full numpy.rec.array numpy.testing.assert_