    {-# LANGUAGE TypeOperators, FlexibleInstances, ScopedTypeVariables #-}

    -- | Index types.
    module Data.Array.Repa.Index
            (
            -- * Index types
              Z     (..)
            , (:.)  (..)

            -- * Common dimensions.
            , DIM0, DIM1, DIM2, DIM3, DIM4, DIM5
            ,       ix1,  ix2,  ix3,  ix4,  ix5)
    where
    import Data.Array.Repa.Shape
    import GHC.Base                 (quotInt, remInt)

    stage   = "Data.Array.Repa.Index"

    -- | An index of dimension zero
    data Z  = Z
            deriving (Show, Read, Eq, Ord)

    -- | Our index type, used for both shapes and indices.
    infixl 3 :.
    data tail :. head
            = !tail :. !head
            deriving (Show, Read, Eq, Ord)

    -- Common dimensions
    type DIM0       = Z
    type DIM1       = DIM0 :. Int
    type DIM2       = DIM1 :. Int
    type DIM3       = DIM2 :. Int
    type DIM4       = DIM3 :. Int
    type DIM5       = DIM4 :. Int

    -- | Helper for index construction.
    --
    --   Use this instead of explicit constructors like @(Z :. (x :: Int))@.
    --   The this is sometimes needed to ensure that 'x' is constrained to
    --   be in @Int@.
    ix1 :: Int -> DIM1
    ix1 x = Z :. x
    {-# INLINE ix1 #-}

    ix2 :: Int -> Int -> DIM2
    ix2 y x = Z :. y :. x
    {-# INLINE ix2 #-}

    ix3 :: Int -> Int -> Int -> DIM3
    ix3 z y x = Z :. z :. y :. x
    {-# INLINE ix3 #-}

    ix4 :: Int -> Int -> Int -> Int -> DIM4
    ix4 a z y x = Z :. a :. z :. y :. x
    {-# INLINE ix4 #-}

    ix5 :: Int -> Int -> Int -> Int -> Int -> DIM5
    ix5 b a z y x = Z :. b :. a :. z :. y :. x
    {-# INLINE ix5 #-}

    -- Shape ----------------------------------------------------------------------
    instance Shape Z where
            {-# INLINE [1] rank #-}
            rank _                  = 0

            {-# INLINE [1] zeroDim #-}
            zeroDim                 = Z

            {-# INLINE [1] unitDim #-}
            unitDim                 = Z

            {-# INLINE [1] intersectDim #-}
            intersectDim _ _        = Z

            {-# INLINE [1] addDim #-}
            addDim _ _              = Z

            {-# INLINE [1] size #-}
            size _                  = 1

            {-# INLINE [1] sizeIsValid #-}
            sizeIsValid _           = True

            {-# INLINE [1] toIndex #-}
            toIndex _ _             = 0

            {-# INLINE [1] fromIndex #-}
            fromIndex _ _           = Z

            {-# INLINE [1] inShapeRange #-}
            inShapeRange Z Z Z      = True

            {-# NOINLINE listOfShape #-}
            listOfShape _           = []

            {-# NOINLINE shapeOfList #-}
            shapeOfList []          = Z
            shapeOfList _           = error $ stage ++ ".fromList: non-empty list when converting to Z."

            {-# INLINE deepSeq #-}
            deepSeq Z x             = x

    instance Shape sh => Shape (sh :. Int) where
            {-# INLINE [1] rank #-}
            rank   (sh  :. _)
                    = rank sh + 1

            {-# INLINE [1] zeroDim #-}
            zeroDim = zeroDim :. 0

            {-# INLINE [1] unitDim #-}
            unitDim = unitDim :. 1

            {-# INLINE [1] intersectDim #-}
            intersectDim (sh1 :. n1) (sh2 :. n2)
                    = (intersectDim sh1 sh2 :. (min n1 n2))

            {-# INLINE [1] addDim #-}
            addDim (sh1 :. n1) (sh2 :. n2)
                    = addDim sh1 sh2 :. (n1 + n2)

            {-# INLINE [1] size #-}
            size  (sh1 :. n)
                    = size sh1 * n

            {-# INLINE [1] sizeIsValid #-}
            sizeIsValid (sh1 :. n)
                    | size sh1 > 0
                    = n <= maxBound `div` size sh1

                    | otherwise
                    = False

            {-# INLINE [1] toIndex #-}
            toIndex (sh1 :. sh2) (sh1' :. sh2')
                    = toIndex sh1 sh1' * sh2 + sh2'

            {-# INLINE [1] fromIndex #-}
            fromIndex (ds :. d) n
                    = fromIndex ds (n `quotInt` d) :. r
                    where
                    -- If we assume that the index is in range, there is no point
                    -- in computing the remainder for the highest dimension since
                    -- n < d must hold. This saves one remInt per element access which
                    -- is quite a big deal.
                    r       | rank ds == 0  = n
                            | otherwise     = n `remInt` d

            {-# INLINE [1] inShapeRange #-}
            inShapeRange (zs :. z) (sh1 :. n1) (sh2 :. n2)
                    = (n2 >= z) && (n2 < n1) && (inShapeRange zs sh1 sh2)

            {-# NOINLINE listOfShape #-}
            listOfShape (sh :. n)
             = n : listOfShape sh

            {-# NOINLINE shapeOfList #-}
            shapeOfList xx
             = case xx of
                    []      -> error $ stage ++ ".toList: empty list when converting to  (_ :. Int)"
                    x:xs    -> shapeOfList xs :. x

            {-# INLINE deepSeq #-}
            deepSeq (sh :. n) x = deepSeq sh (n `seq` x)