def rw(X,w,step=1):
    """Make sliding-window view of vector array X.
    Input array X has to be C_CONTIGUOUS otherwise a copy is made.
    C-contiguous arrays do do not require any additional memory or 
    time for array copy.
    
    Example:
    >> X = arange(10)
    >> rw(X,4,1)
    array([[0, 1, 2, 3],
       [1, 2, 3, 4],
       [2, 3, 4, 5],
       [3, 4, 5, 6],
       [4, 5, 6, 7],
       [5, 6, 7, 8],
       [6, 7, 8, 9]])

    >> rw(X,3,3)
    array([[0, 1, 2],
       [3, 4, 5],
       [6, 7, 8]])
    """
    from numpy.lib.stride_tricks import as_strided as ast
    if not X.flags['C_CONTIGUOUS']:
        X = X.copy()
    if hasattr(X,'mask'):
        return ma.array(ast(X.data,((X.shape[0]-w)//step+1,w),((step*X.dtype.itemsize),X.dtype.itemsize)),
                        mask = ast(X.mask,((X.shape[0]-w)//step+1,w), ((step*X.mask.dtype.itemsize),X.mask.dtype.itemsize)))
    else:
        return ast(X, ((X.shape[0]-w)//step+1,w), ((step*X.dtype.itemsize),X.dtype.itemsize))

def patchify(A, step=(1,1), block= (8, 8)):
    """Make a Ndata by (flattened) patch, 2D array"""
    shape   = ((A.shape[0] - block[0])/step[0] + 1,
               (A.shape[1] - block[1])/step[1] + 1) + block
    strides = (A.strides[0]*step[0],A.strides[1]*step[1]) + A.strides
    blocks = ast(A, shape= shape, strides= strides)
    blocks = blocks.flatten()
    shape = (shape[0]*shape[1],block[0]*block[1])
    strides = (blocks.itemsize*block[0]*block[1],blocks.itemsize)
    return ast(blocks, shape= shape, strides= strides)

def rw(x, w, step=1):
    from numpy.lib.stride_tricks import as_strided as ast

    if not x.flags["C_CONTIGUOUS"]:
        x = x.copy()
    if hasattr(x, "mask"):
        return ma.array(
            ast(x.data, ((x.shape[0] - w) // step + 1, w), ((step * x.dtype.itemsize), x.dtype.itemsize)),
            mask=ast(
                x.mask, ((x.shape[0] - w) // step + 1, w), ((step * x.mask.dtype.itemsize), x.mask.dtype.itemsize)
            ),
        )
    else:
        return ast(x, ((x.shape[0] - w) // step + 1, w), ((step * x.dtype.itemsize), x.dtype.itemsize))

def sliding_window(a,ws,ss = None,flatten = True):
    '''
    Return a sliding window over a in any number of dimensions
     
    Parameters:
        a  - an n-dimensional numpy array
        ws - an int (a is 1D) or tuple (a is 2D or greater) representing the size 
             of each dimension of the window
        ss - an int (a is 1D) or tuple (a is 2D or greater) representing the 
             amount to slide the window in each dimension. If not specified, it
             defaults to ws.
        flatten - if True, all slices are flattened, otherwise, there is an 
                  extra dimension for each dimension of the input.
     
    Returns
        an array containing each n-dimensional window from a
    '''
     
    if None is ss:
        # ss was not provided. the windows will not overlap in any direction.
        ss = ws
    ws = norm_shape(ws)
    ss = norm_shape(ss)
     
    # convert ws, ss, and a.shape to numpy arrays so that we can do math in every 
    # dimension at once.
    ws = np.array(ws)
    ss = np.array(ss)
    shape = np.array(a.shape)
     
     
    # ensure that ws, ss, and a.shape all have the same number of dimensions
    ls = [len(shape),len(ws),len(ss)]
    if 1 != len(set(ls)):
        raise ValueError('a.shape, ws and ss must all have the same length. They were %s' % str(ls))
     
    # ensure that ws is smaller than a in every dimension
    if np.any(ws > shape):
        raise ValueError('ws cannot be larger than a in any dimension.a.shape was %s and ws was %s' % (str(a.shape),str(ws)))
     
    # how many slices will there be in each dimension?
    newshape = norm_shape(((shape - ws) // ss) + 1)
    # the shape of the strided array will be the number of slices in each dimension
    # plus the shape of the window (tuple addition)
    newshape += norm_shape(ws)
    # the strides tuple will be the array's strides multiplied by step size, plus
    # the array's strides (tuple addition)
    newstrides = norm_shape(np.array(a.strides) * ss) + a.strides
    strided = ast(a,shape = newshape,strides = newstrides)
    if not flatten:
        return strided
     
    # Collapse strided so that it has one more dimension than the window.  I.e.,
    # the new array is a flat list of slices.
    meat = len(ws) if ws.shape else 0
    firstdim = (np.product(newshape[:-meat]),) if ws.shape else ()
    dim = firstdim + (newshape[-meat:])
    # remove any dimensions with size 1
    dim = filter(lambda i : i != 1,dim)
    return strided.reshape(dim)

    def patchify(self, D):
        """
        Make a Ndata by (flattened) pshape, 2D array
        """
        step    = self.step
        pshape  = self.pshape   

        shape   = ((D.shape[0] - pshape[0])/step[0] + 1,
                   (D.shape[1] - pshape[1])/step[1] + 1) + pshape
        strides = (D.strides[0]*step[0],D.strides[1]*step[1]) + D.strides
        blocks  = ast(D, shape= shape, strides= strides)
        blocks  = blocks.ravel()
        shape   = (shape[0]*shape[1],pshape[0]*pshape[1])
        strides = (blocks.itemsize*pshape[0]*pshape[1],blocks.itemsize)

        return ast(blocks, shape= shape, strides= strides)

def overlap_data_stream(data, chunk=256, overlap_percentage=.75):
    chunk_count = len(data)/chunk
    overlap_samples = int(chunk*overlap_percentage)+1
    extended_length = (chunk_count+1)*(chunk-overlap_samples)
    data = np.hstack((np.asarray(data),np.asarray([0]*(extended_length-len(data)))))
    shape = (len(data)/(chunk-overlap_samples),chunk)
    strides = (data.itemsize*(chunk-overlap_samples), data.itemsize)
    return ast(data, shape=shape, strides=strides)

def AR_striding(data, nlags):
    data = np.asarray(data)
    if not data.flags.c_contiguous:
        data = data.copy(order="C")
    if data.ndim == 1:
        data = np.reshape(data, (-1, 1))
    sz = data.dtype.itemsize
    return ast(data, shape=(data.shape[0] - nlags, data.shape[1] * (nlags + 1)), strides=(data.shape[1] * sz, sz))

def block_view(A, block= (3, 3)):
	"""Provide a 2D block view to 2D array. No error checking made.
	Therefore meaningful (as implemented) only for blocks strictly
	compatible with the shape of A."""

	shape= (A.shape[0]/ block[0], A.shape[1]/ block[1])+ block
	strides= (block[0]* A.strides[0], block[1]* A.strides[1])+ A.strides
	return ast(A, shape= shape, strides= strides)

def block_view(A, block= (3, 3)):
    """Provide a 2D block view to 2D array. No error checking made.
    Therefore meaningful (as implemented) only for blocks strictly
    compatible with the shape of A."""
    # simple shape and strides computations may seem at first strange
    # unless one is able to recognize the 'tuple additions' involved ;-)
    shape= (A.shape[0]/ block[0], A.shape[1]/ block[1])+ block
    strides= (block[0]* A.strides[0], block[1]* A.strides[1])+ A.strides
    return ast(A, shape= shape, strides= strides)

def sliding_window_sliced(a,density, ws,ss = None,flatten = True):
   '''
   Return a sliding window over a in any number of dimensions
   '''
   if None is ss:
      # ss was not provided. the windows will not overlap in any direction.
      ss = ws
   ws = norm_shape(ws)
   ss = norm_shape(ss)
   # convert ws, ss, and a.shape to numpy arrays
   ws = np.array(ws)
   ss = np.array(ss)

   r = np.arange(1,ws[0]-1,density, dtype=np.int)

   shap = np.array(a.shape)

   # ensure that ws, ss, and a.shape all have the same number of dimensions
   ls = [len(shap),len(ws),len(ss)]
   if 1 != len(set(ls)):
      raise ValueError(\
      'a.shape, ws and ss must all have the same length. They were %s' % str(ls))

   # ensure that ws is smaller than a in every dimension
   if np.any(ws > shap):
      raise ValueError(\
      'ws cannot be larger than a in any dimension.\
 a.shape was %s and ws was %s' % (str(a.shape),str(ws)))

   # how many slices will there be in each dimension?
   newshape = norm_shape(((shap - ws) // ss) + 1)
   # the shape of the strided array will be the number of slices in each dimension
   # plus the shape of the window (tuple addition)
   newshape += norm_shape(ws)
   # the strides tuple will be the array's strides multiplied by step size, plus

   # the array's strides (tuple addition)
   newstrides = norm_shape(np.array(a.strides) * ss) + a.strides
   a = ast(a,shape = newshape,strides = newstrides)[:,:,:,r]
   if not flatten:
      return a
   # Collapse strided so that it has one more dimension than the window.  I.e.,
   # the new array is a flat list of slices.
   meat = len(ws) if ws.shape else 0
   firstdim = (int(np.product(newshape[:-meat])),) if ws.shape else ()
   dim = firstdim + (newshape[-meat:])

   dim = list(dim)
   dim[-1] = len(r)
   ## remove any dimensions with size 1
   dim = filter(lambda i : i != 1,dim)
   dim = tuple(dim)

   newshape = np.shape(a)

   return a.reshape(dim), newshape

def striding(data, lens, stride):
    from numpy.lib.stride_tricks import as_strided as ast
    itemsize = data.itemsize
    t, chan = data.shape
    n = np.floor((t-lens)/stride) + 1
    if data.flags.c_contiguous:
        strides = tuple(itemsize*i for i in (chan*stride, 1, chan))
    else:
        strides = tuple(itemsize*i for i in (stride, t, 1))
    return ast(data, shape=(n, chan, lens), strides=strides)

def block_view(arr, block_shape):
    
    assert arr.ndim == len(block_shape), \
            "ndim mismatch; arr.ndim(=%s) and len(block_shape(=%s) should be equal" % (arr.ndim, len(block_shape))
    assert all([i % j == 0 for i, j in zip(arr.shape, block_shape)]), \
            "block_view requires arr.shape[i] to be a multiple of block_shape[i]"
    
    shape= tuple(i // j for i, j in zip(arr.shape, block_shape)) + block_shape
    strides = tuple(i * j for i, j in zip(arr.strides, block_shape)) + arr.strides
    return ast(arr, shape=shape, strides=strides)

 def sliding_window(self, xr):
   """
   :type xr: numpy.ndarray
   :rtype: numpy.ndarray
   """
   from numpy.lib.stride_tricks import as_strided as ast
   x = numpy.concatenate([self.zpad, xr, self.zpad])
   return ast(x,
              shape=(x.shape[0] - self.window + 1, 1, self.window, self.num_inputs),
              strides=(x.strides[0], x.strides[1] * self.num_inputs) + x.strides
              ).reshape((xr.shape[0], self.num_inputs * self.window))

def AR_striding(data,nlags):
    # I had some trouble with views and as_strided, so copy if not contiguous
    data = np.asarray(data)
    if not data.flags.c_contiguous:
        data = data.copy(order='C')
    if data.ndim == 1:
        data = np.reshape(data,(-1,1))
    sz = data.dtype.itemsize
    return ast(
            data,
            shape=(data.shape[0]-nlags,data.shape[1]*(nlags+1)),
            strides=(data.shape[1]*sz,sz))

def sliding_window(a, ws, ss=None):
    '''
    Return a sliding window over a in any number of dimensions

    Parameters:
        a  - an n-dimensional numpy array
        ws - an int (a is 1D) or tuple (a is 2D or greater) representing the size
             of each dimension of the window
        ss - an int (a is 1D) or tuple (a is 2D or greater) representing the
             amount to slide the window in each dimension. If not specified, it
             defaults to ws.

    Returns
        an array containing each n-dimensional window from a
    '''

    if None is ss:
        # ss was not provided. the windows will not overlap in any direction.
        ss = ws
    ws = norm_shape(ws)
    ss = norm_shape(ss)

    # convert ws, ss, and a.shape to numpy arrays so that we can do math in every
    # dimension at once.
    ws = np.array(ws)
    ss = np.array(ss)
    shape = np.array(a.shape)


    # ensure that ws, ss, and a.shape all have the same number of dimensions
    ls = [len(shape),len(ws),len(ss)]
    if 1 != len(set(ls)):
        raise ValueError(\
        'a.shape, ws and ss must all have the same length. They were %s' % str(ls))

    # ensure that ws is smaller than a in every dimension
    if np.any(ws > shape):
        raise ValueError(\
        'ws cannot be larger than a in any dimension.\
 a.shape was %s and ws was %s' % (str(a.shape),str(ws)))

    # how many slices will there be in each dimension?
    newshape = norm_shape(((shape - ws) // ss) + 1)
    # the shape of the strided array will be the number of slices in each dimension
    # plus the shape of the window (tuple addition)
    newshape += norm_shape(ws)
    # the strides tuple will be the array's strides multiplied by step size, plus
    # the array's strides (tuple addition)
    newstrides = norm_shape(np.array(a.strides) * ss) + a.strides
    strided = ast(a,shape = newshape, strides = newstrides)
    return strided

def binning(arr, br, bc):
    """Return a binned view if 'arr'"""
    nr, nc = arr.shape

    if nr % br != 0 or nc % bc != 0:
        raise ValueError("'bin' must be an integer multiple of size")

    bnr = nr // br
    bnc = nc // bc
    m = arr.dtype.itemsize
    newshape = bnr, bnc, br, bc
    newstrides = nc*br*m, bc*m, nc*m, m
    binned = ast(arr, shape=newshape, strides=newstrides)
    return binned

def block_view(orig, block):
    """Provide a 2D block view to 2D array. No error checking made.
    Therefore meaningful (as implemented) only for blocks strictly
    compatible with the shape of A.

    Note the tuple addition happening!
    """
    if orig.shape[1] == block[1]:
        shape = (orig.shape[0] / block[0],) + block
        strides = (block[0] * orig.strides[0],) + orig.strides
    else:
        shape = (orig.shape[0] / block[0], orig.shape[1] / block[1]) + block
        strides = (block[0] * orig.strides[0],
                   block[1] * orig.strides[1]) + orig.strides
    return ast(orig, shape=shape, strides=strides)

def _row_block_view(rx, x_shape, block, block_shape, func=lambda x:x):
    '''
    2D case
    single row block view, return the row form of it
    and with func apply to each block
    _block_shape_.shape must have a strictly matching with _rx_.shape
    that means, each dimension of _rx_ could be divisible by
    corresponding dim of _block_shape_
    '''
    x = rx.reshape(x_shape)
    shape = (x.shape[0]/block_shape[0], x.shape[1]/block_shape[1]) + block_shape
    strides= (block_shape[0]*x.strides[0], block_shape[1]*x.strides[1]) + x.strides
    block_x = ast(x, shape=shape, strides=strides)
    l = []
    for i in xrange(block[0]):
        for j in xrange(block[1]):
            l.append(func(block_x[i][j]).ravel())
            # block_rx = np.concatenate((block_rx, func(block_x[i][j]).ravel()), axis=1)
    return np.concatenate(l, axis=1).reshape(1, -1)

def sliding_window(a,ws,ss=1):
    """Generate sliding window version of an array

    Parameters
    ----------
    a (np.ndarray): input array
    ws (int): window size
    ss (int): step size

    Returns
    -------
    Array in which iteration along the 0th dimension provides requested data windows
    """
    # sliding window along 0'th axis of a, using stride tricks
    # ws: window size
    # ss: step size
    l = a.shape[0]
    n_slices = ((l - ws) // ss) + 1
    newshape = (n_slices,ws) + a.shape[1:] 
    newstrides = (a.strides[0]*ss,) + a.strides
    strided = ast(a,shape = newshape,strides = newstrides)
    return strided

def block_view(A, block= (32, 32)):
    # simple shape and strides computations may seem at first strange
    # unless one is able to recognize the 'tuple additions' involved ;-)
    shape= (A.shape[0]/ block[0], A.shape[1]/ block[1])+ block
    strides= (block[0]* A.strides[0], block[1]* A.strides[1])+ A.strides
    return ast(A, shape= shape, strides= strides)