{-# LANGUAGE CPP                        #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE UndecidableInstances       #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Diagrams.Core.Envelope
-- Copyright   :  (c) 2011 diagrams-core team (see LICENSE)
-- License     :  BSD-style (see LICENSE)
-- Maintainer  :  diagrams-discuss@googlegroups.com
--
-- diagrams-core defines the core library of primitives forming the
-- basis of an embedded domain-specific language for describing and
-- rendering diagrams.
--
-- The @Diagrams.Core.Envelope@ module defines a data type and type class for
-- \"envelopes\", aka functional bounding regions.
--
-----------------------------------------------------------------------------

module Diagrams.Core.Envelope
       ( -- * Envelopes
         Envelope(..)

       , appEnvelope
       , onEnvelope
       , mkEnvelope
       , pointEnvelope

       , Enveloped(..)

         -- * Utility functions
       , diameter
       , radius
       , extent
       , size
       , envelopeVMay
       , envelopeV
       , envelopePMay
       , envelopeP
       , envelopeSMay
       , envelopeS

         -- * Miscellaneous
       , OrderedField
       ) where

#if __GLASGOW_HASKELL__ < 710
import           Control.Applicative     ((<$>))
#endif
import           Control.Lens            (Rewrapped, Wrapped (..), iso, mapped,
                                          op, over, (&), (.~), _Wrapping')
import           Data.Functor.Rep
import qualified Data.Map                as M
import           Data.Maybe              (fromMaybe)
import           Data.Semigroup
import qualified Data.Set                as S

import           Diagrams.Core.HasOrigin
import           Diagrams.Core.Points
import           Diagrams.Core.Transform
import           Diagrams.Core.V

import           Linear.Metric
import           Linear.Vector


------------------------------------------------------------
--  Envelopes  ---------------------------------------------
------------------------------------------------------------

-- | Every diagram comes equipped with an /envelope/.  What is an envelope?
--
--   Consider first the idea of a /bounding box/. A bounding box
--   expresses the distance to a bounding plane in every direction
--   parallel to an axis.  That is, a bounding box can be thought of
--   as the intersection of a collection of half-planes, two
--   perpendicular to each axis.
--
--   More generally, the intersection of half-planes in /every/
--   direction would give a tight \"bounding region\", or convex hull.
--   However, representing such a thing intensionally would be
--   impossible; hence bounding boxes are often used as an
--   approximation.
--
--   An envelope is an /extensional/ representation of such a
--   \"bounding region\".  Instead of storing some sort of direct
--   representation, we store a /function/ which takes a direction as
--   input and gives a distance to a bounding half-plane as output.
--   The important point is that envelopes can be composed, and
--   transformed by any affine transformation.
--
--   Formally, given a vector @v@, the envelope computes a scalar @s@ such
--   that
--
--     * for every point @u@ inside the diagram,
--       if the projection of @(u - origin)@ onto @v@ is @s' *^ v@, then @s' <= s@.
--
--     * @s@ is the smallest such scalar.
--
--   There is also a special \"empty envelope\".
--
--   The idea for envelopes came from
--   Sebastian Setzer; see
--   <http://byorgey.wordpress.com/2009/10/28/collecting-attributes/#comment-2030>.  See also Brent Yorgey, /Monoids: Theme and Variations/, published in the 2012 Haskell Symposium: <http://ozark.hendrix.edu/~yorgey/pub/monoid-pearl.pdf>; video: <http://www.youtube.com/watch?v=X-8NCkD2vOw>.
newtype Envelope v n = Envelope (Option (v n -> Max n))

instance Wrapped (Envelope v n) where
  type Unwrapped (Envelope v n) = Option (v n -> Max n)
  _Wrapped' = iso (\(Envelope e) -> e) Envelope

instance Rewrapped (Envelope v n) (Envelope v' n')

-- | \"Apply\" an envelope by turning it into a function.  @Nothing@
--   is returned iff the envelope is empty.
appEnvelope :: Envelope v n -> Maybe (v n -> n)
appEnvelope (Envelope (Option e)) = (getMax .) <$> e

-- | A convenient way to transform an envelope, by specifying a
--   transformation on the underlying @v n -> n@ function.  The empty
--   envelope is unaffected.
onEnvelope :: ((v n -> n) -> v n -> n) -> Envelope v n -> Envelope v n
onEnvelope t = over (_Wrapping' Envelope . mapped) ((Max .) . t . (getMax .))

-- | Create an envelope from a @v n -> n@ function.
mkEnvelope :: (v n -> n) -> Envelope v n
mkEnvelope = Envelope . Option . Just . (Max .)

-- | Create a point envelope for the given point.  A point envelope
--   has distance zero to a bounding hyperplane in every direction.
--   Note this is /not/ the same as the empty envelope.
pointEnvelope :: (Fractional n, Metric v) => Point v n -> Envelope v n
pointEnvelope p = moveTo p (mkEnvelope $ const 0)

-- | Envelopes form a semigroup with pointwise maximum as composition.
--   Hence, if @e1@ is the envelope for diagram @d1@, and
--   @e2@ is the envelope for @d2@, then @e1 \`mappend\` e2@
--   is the envelope for @d1 \`atop\` d2@.
deriving instance Ord n => Semigroup (Envelope v n)

-- | The special empty envelope is the identity for the
--   'Monoid' instance.
deriving instance Ord n => Monoid (Envelope v n)

type instance V (Envelope v n) = v
type instance N (Envelope v n) = n

instance Show (Envelope v n) where
  show _ = "<envelope>"

------------------------------------------------------------
--  Transforming envelopes  --------------------------------
------------------------------------------------------------

-- | The local origin of an envelope is the point with respect to
--   which bounding queries are made, /i.e./ the point from which the
--   input vectors are taken to originate.
instance (Metric v, Fractional n) => HasOrigin (Envelope v n) where
  moveOriginTo (P u) = onEnvelope $ \oldEnv v -> oldEnv v - ((u ^/ (v `dot` v)) `dot` v)
  -- For a detailed explanation of this code, see note
  -- [Transforming Envelopes] below.

instance (Metric v, Floating n) => Transformable (Envelope v n) where
  transform t = moveOriginTo (P . negated . transl $ t) . onEnvelope g
    where

      -- For a detailed explanation of this code, see note
      -- [Transforming Envelopes] below.
      g f v = f v' / (v' `dot` vi)
        where
          v' = signorm $ lapp (transp t) v
          vi = apply (inv t) v

{-

Note [Transforming Envelopes]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

We are given an envelope for some object, and want to apply an affine
transformation, such that the new envelope will be the envelope for
the transformed object.  The HasOrigin instance handles the
translational component; the rest of the code in the Transformable
instance handles the linear component.

See <<diagrams/EnvHasOrigin.png>>.

To implement moveOriginTo, we need to move the "base point" from which
envelope queries are made.  We are given the old envelope @oldEnv@ (a
function from vectors to scalars), a vector @u@ from the old origin to
the new origin, and a query vector @v@ which we imagine to emanate
from the new origin.  If we query the old envelope with v, it will
find the correct perpendicular hyperplane, but the reported distance
may be wrong (it will only be correct if the origin was moved in a
direction perpendicular to v).  The part that needs to be subtracted
is just the projection of u onto v, which is given by (u.v)/(v.v) *^
v.  In fact envelopes return not a distance or vector, but a scalar
which is taken to be a multiple of the query vector, so the scalar we
need to subtract is just (u.v)/(v.v).

We now consider how to apply a linear transformation to an envelope.
Recall that an envelope is a function that takes a vector and returns
a scaling factor s such that scaling the vector by s will produce a
vector to the minimum separating hyperplane.  (So if given a unit
vector as input, the output will be simply the distance to the minimum
separating hyperplane.)

We are given a linear transformation t and must produce a new envelope
function.  Given an input vector v, the "obvious" thing to do is to
transform v back into the original coordinate system using the inverse
of t, apply the original envelope, and then adjust the resulting
scalar according to how much the transformation scales v.

However, this does not work, since linear transformations do not
preserve angles.  Thus, in particular, given the query vector v and
the perpendicular separating hyperplane H which we wish to find, t^-1
v and t^-1 H are not necessarily perpendicular anymore.  So if we
query the envelope with t^-1 v we will get information about the
distance to some separating hyperplane, which when mapped forward
through t will no longer be perpendicular to v.

However, it turns out that if v and w are perpendicular, then t^-1 v
will be perpendicular to t^T w, that is, the *transpose* of t (when
considered as a matrix) applied to w.  The proof is simple. Recall
that v and w are perpendicular if and only if v . w = v^T w = 0.  Thus,

  (t^-1 v) . (t^T w) = (t^-1 v)^T (t^T w) = v^T t^-T t^T w = v^T w = 0.

Now to explain this code:

      g f v = f v' / (v' `dot` vi)
        where
          v' = signorm $ lapp (transp t) v
          vi = apply (inv t) v

In our case, our new envelope function (transformed by t) will be
given a query vector v, and we suppose v is perpendicular to the
separating hyperplane H.  Instead of querying the old envelope
function f with t^-1 v, we query it with t^T v (after normalizing),
since that vector will be perpendicular to t^-1 H.

Finally, to scale the resulting value correctly, we divide by (t^T v
. t^-1 v); I forget why.  Perhaps I will come back later and complete
this explanation.

-}

------------------------------------------------------------
--  Enveloped class
------------------------------------------------------------

-- | When dealing with envelopes we often want scalars to be an
--   ordered field (i.e. support all four arithmetic operations and be
--   totally ordered) so we introduce this class as a convenient
--   shorthand.
class (Floating s, Ord s) => OrderedField s
instance (Floating s, Ord s) => OrderedField s

-- | @Enveloped@ abstracts over things which have an envelope.
class (Metric (V a), OrderedField (N a)) => Enveloped a where

  -- | Compute the envelope of an object.  For types with an intrinsic
  --   notion of \"local origin\", the envelope will be based there.
  --   Other types (e.g. 'Trail') may have some other default
  --   reference point at which the envelope will be based; their
  --   instances should document what it is.
  getEnvelope :: a -> Envelope (V a) (N a)

instance (Metric v, OrderedField n) => Enveloped (Envelope v n) where
  getEnvelope = id

instance (OrderedField n, Metric v) => Enveloped (Point v n) where
  getEnvelope p = moveTo p . mkEnvelope $ const 0

instance Enveloped t => Enveloped (TransInv t) where
  getEnvelope = getEnvelope . op TransInv

instance (Enveloped a, Enveloped b, V a ~ V b, N a ~ N b) => Enveloped (a,b) where
  getEnvelope (x,y) = getEnvelope x <> getEnvelope y

instance Enveloped b => Enveloped [b] where
  getEnvelope = mconcat . map getEnvelope

instance Enveloped b => Enveloped (M.Map k b) where
  getEnvelope = mconcat . map getEnvelope . M.elems

instance Enveloped b => Enveloped (S.Set b) where
  getEnvelope = mconcat . map getEnvelope . S.elems

------------------------------------------------------------
--  Computing with envelopes
------------------------------------------------------------

-- | Compute the vector from the local origin to a separating
--   hyperplane in the given direction, or @Nothing@ for the empty
--   envelope.
envelopeVMay :: Enveloped a => Vn a -> a -> Maybe (Vn a)
envelopeVMay v = fmap ((*^ v) . ($ v)) . appEnvelope . getEnvelope

-- | Compute the vector from the local origin to a separating
--   hyperplane in the given direction.  Returns the zero vector for
--   the empty envelope.
envelopeV :: Enveloped a => Vn a -> a -> Vn a
envelopeV v = fromMaybe zero . envelopeVMay v

-- | Compute the point on a separating hyperplane in the given
--   direction, or @Nothing@ for the empty envelope.
envelopePMay :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> Maybe (Point v n)
envelopePMay v = fmap P . envelopeVMay v

-- | Compute the point on a separating hyperplane in the given
--   direction.  Returns the origin for the empty envelope.
envelopeP :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> Point v n
envelopeP v = P . envelopeV v

-- | Equivalent to the norm of 'envelopeVMay':
--
--   @ envelopeSMay v x == fmap norm (envelopeVMay v x) @
--
--   (other than differences in rounding error)
--
--   Note that the 'envelopeVMay' / 'envelopePMay' functions above should be
--   preferred, as this requires a call to norm.  However, it is more
--   efficient than calling norm on the results of those functions.
envelopeSMay :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> Maybe n
envelopeSMay v = fmap ((* norm v) . ($ v)) . appEnvelope . getEnvelope

-- | Equivalent to the norm of 'envelopeV':
--
--   @ envelopeS v x == norm (envelopeV v x) @
--
--   (other than differences in rounding error)
--
--   Note that the 'envelopeV' / 'envelopeP' functions above should be
--   preferred, as this requires a call to norm. However, it is more
--   efficient than calling norm on the results of those functions.
envelopeS :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> n
envelopeS v = fromMaybe 0 . envelopeSMay v

-- | Compute the diameter of a enveloped object along a particular
--   vector.  Returns zero for the empty envelope.
diameter :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> n
diameter v a = maybe 0 (\(lo,hi) -> (hi - lo) * norm v) (extent v a)

-- | Compute the \"radius\" (1\/2 the diameter) of an enveloped object
--   along a particular vector.
radius :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> n
radius v = (0.5*) . diameter v

-- | Compute the range of an enveloped object along a certain
--   direction.  Returns a pair of scalars @(lo,hi)@ such that the
--   object extends from @(lo *^ v)@ to @(hi *^ v)@. Returns @Nothing@
--   for objects with an empty envelope.
extent :: (V a ~ v, N a ~ n, Enveloped a) => v n -> a -> Maybe (n, n)
extent v a = (\f -> (-f (negated v), f v)) <$> (appEnvelope . getEnvelope $ a)

-- | The smallest positive /axis-parallel/ vector that bounds the
--   envelope of an object.
size :: (V a ~ v, N a ~ n, Enveloped a, HasBasis v) => a -> v n
size d = tabulate $ \(E l) -> diameter (zero & l .~ 1) d