{-# LANGUAGE ScopedTypeVariables #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  Data.PlanarGraph.Core
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- Data type for representing connected planar graphs
--------------------------------------------------------------------------------
module Data.PlanarGraph.Core where


import           Control.DeepSeq
import           Control.Lens               hiding ((.=))
import           Control.Monad.State.Strict
import           Data.Aeson
import qualified Data.Foldable              as F
import           Data.Permutation
import           Data.PlanarGraph.Dart
import           Data.Type.Equality         (gcastWith)
import qualified Data.Vector                as V
import qualified Data.Vector.Mutable        as MV
import           GHC.Generics               (Generic)
import           Unsafe.Coerce              (unsafeCoerce)

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------
-- $setup
-- >>> :{
-- let dart i s = Dart (Arc i) (read s)
--     (aA:aB:aC:aD:aE:aG:_) = take 6 [Arc 0..]
--     myGraph :: PlanarGraph () Primal () String ()
--     myGraph = planarGraph [ [ (Dart aA Negative, "a-")
--                             , (Dart aC Positive, "c+")
--                             , (Dart aB Positive, "b+")
--                             , (Dart aA Positive, "a+")
--                             ]
--                           , [ (Dart aE Negative, "e-")
--                             , (Dart aB Negative, "b-")
--                             , (Dart aD Negative, "d-")
--                             , (Dart aG Positive, "g+")
--                             ]
--                           , [ (Dart aE Positive, "e+")
--                             , (Dart aD Positive, "d+")
--                             , (Dart aC Negative, "c-")
--                             ]
--                           , [ (Dart aG Negative, "g-")
--                             ]
--                           ]
-- :}
--
--
-- This represents the following graph. Note that the graph is undirected, the
-- arrows are just to indicate what the Positive direction of the darts is.
--
-- ![myGraph](docs/Data/PlanarGraph/testG.png)

--------------------------------------------------------------------------------
-- * Representing The World

-- | The world in which the graph lives
data World = Primal | Dual deriving (Int -> World -> ShowS
[World] -> ShowS
World -> String
(Int -> World -> ShowS)
-> (World -> String) -> ([World] -> ShowS) -> Show World
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [World] -> ShowS
$cshowList :: [World] -> ShowS
show :: World -> String
$cshow :: World -> String
showsPrec :: Int -> World -> ShowS
$cshowsPrec :: Int -> World -> ShowS
Show,World -> World -> Bool
(World -> World -> Bool) -> (World -> World -> Bool) -> Eq World
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: World -> World -> Bool
$c/= :: World -> World -> Bool
== :: World -> World -> Bool
$c== :: World -> World -> Bool
Eq)

-- | We can take the dual of a world. For the Primal this gives us the Dual,
-- for the Dual this gives us the Primal.
type family DualOf (sp :: World) where
  DualOf Primal = Dual
  DualOf Dual   = Primal

-- | The Dual of the Dual is the Primal.
dualDualIdentity :: forall w. DualOf (DualOf w) :~: w
dualDualIdentity :: DualOf (DualOf w) :~: w
dualDualIdentity = (Any :~: Any) -> DualOf (DualOf w) :~: w
forall a b. a -> b
unsafeCoerce Any :~: Any
forall k (a :: k). a :~: a
Refl
          -- manual proof:
          --    DualOf (DualOf Primal) = Primal
          --    DualOf (DualOf Dual)   = Dual


--------------------------------------------------------------------------------
-- * VertexId's

-- | A vertex in a planar graph. A vertex is tied to a particular planar graph
-- by the phantom type s, and to a particular world w.
newtype VertexId s (w :: World) = VertexId { VertexId s w -> Int
_unVertexId :: Int }
                                deriving (VertexId s w -> VertexId s w -> Bool
(VertexId s w -> VertexId s w -> Bool)
-> (VertexId s w -> VertexId s w -> Bool) -> Eq (VertexId s w)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
/= :: VertexId s w -> VertexId s w -> Bool
$c/= :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
== :: VertexId s w -> VertexId s w -> Bool
$c== :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
Eq,Eq (VertexId s w)
Eq (VertexId s w)
-> (VertexId s w -> VertexId s w -> Ordering)
-> (VertexId s w -> VertexId s w -> Bool)
-> (VertexId s w -> VertexId s w -> Bool)
-> (VertexId s w -> VertexId s w -> Bool)
-> (VertexId s w -> VertexId s w -> Bool)
-> (VertexId s w -> VertexId s w -> VertexId s w)
-> (VertexId s w -> VertexId s w -> VertexId s w)
-> Ord (VertexId s w)
VertexId s w -> VertexId s w -> Bool
VertexId s w -> VertexId s w -> Ordering
VertexId s w -> VertexId s w -> VertexId s w
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k (s :: k) (w :: World). Eq (VertexId s w)
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Ordering
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> VertexId s w
min :: VertexId s w -> VertexId s w -> VertexId s w
$cmin :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> VertexId s w
max :: VertexId s w -> VertexId s w -> VertexId s w
$cmax :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> VertexId s w
>= :: VertexId s w -> VertexId s w -> Bool
$c>= :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
> :: VertexId s w -> VertexId s w -> Bool
$c> :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
<= :: VertexId s w -> VertexId s w -> Bool
$c<= :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
< :: VertexId s w -> VertexId s w -> Bool
$c< :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Bool
compare :: VertexId s w -> VertexId s w -> Ordering
$ccompare :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> Ordering
$cp1Ord :: forall k (s :: k) (w :: World). Eq (VertexId s w)
Ord,Int -> VertexId s w
VertexId s w -> Int
VertexId s w -> [VertexId s w]
VertexId s w -> VertexId s w
VertexId s w -> VertexId s w -> [VertexId s w]
VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w]
(VertexId s w -> VertexId s w)
-> (VertexId s w -> VertexId s w)
-> (Int -> VertexId s w)
-> (VertexId s w -> Int)
-> (VertexId s w -> [VertexId s w])
-> (VertexId s w -> VertexId s w -> [VertexId s w])
-> (VertexId s w -> VertexId s w -> [VertexId s w])
-> (VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w])
-> Enum (VertexId s w)
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
forall k (s :: k) (w :: World). Int -> VertexId s w
forall k (s :: k) (w :: World). VertexId s w -> Int
forall k (s :: k) (w :: World). VertexId s w -> [VertexId s w]
forall k (s :: k) (w :: World). VertexId s w -> VertexId s w
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> [VertexId s w]
forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w]
enumFromThenTo :: VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w]
$cenumFromThenTo :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w]
enumFromTo :: VertexId s w -> VertexId s w -> [VertexId s w]
$cenumFromTo :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> [VertexId s w]
enumFromThen :: VertexId s w -> VertexId s w -> [VertexId s w]
$cenumFromThen :: forall k (s :: k) (w :: World).
VertexId s w -> VertexId s w -> [VertexId s w]
enumFrom :: VertexId s w -> [VertexId s w]
$cenumFrom :: forall k (s :: k) (w :: World). VertexId s w -> [VertexId s w]
fromEnum :: VertexId s w -> Int
$cfromEnum :: forall k (s :: k) (w :: World). VertexId s w -> Int
toEnum :: Int -> VertexId s w
$ctoEnum :: forall k (s :: k) (w :: World). Int -> VertexId s w
pred :: VertexId s w -> VertexId s w
$cpred :: forall k (s :: k) (w :: World). VertexId s w -> VertexId s w
succ :: VertexId s w -> VertexId s w
$csucc :: forall k (s :: k) (w :: World). VertexId s w -> VertexId s w
Enum,[VertexId s w] -> Encoding
[VertexId s w] -> Value
VertexId s w -> Encoding
VertexId s w -> Value
(VertexId s w -> Value)
-> (VertexId s w -> Encoding)
-> ([VertexId s w] -> Value)
-> ([VertexId s w] -> Encoding)
-> ToJSON (VertexId s w)
forall a.
(a -> Value)
-> (a -> Encoding)
-> ([a] -> Value)
-> ([a] -> Encoding)
-> ToJSON a
forall k (s :: k) (w :: World). [VertexId s w] -> Encoding
forall k (s :: k) (w :: World). [VertexId s w] -> Value
forall k (s :: k) (w :: World). VertexId s w -> Encoding
forall k (s :: k) (w :: World). VertexId s w -> Value
toEncodingList :: [VertexId s w] -> Encoding
$ctoEncodingList :: forall k (s :: k) (w :: World). [VertexId s w] -> Encoding
toJSONList :: [VertexId s w] -> Value
$ctoJSONList :: forall k (s :: k) (w :: World). [VertexId s w] -> Value
toEncoding :: VertexId s w -> Encoding
$ctoEncoding :: forall k (s :: k) (w :: World). VertexId s w -> Encoding
toJSON :: VertexId s w -> Value
$ctoJSON :: forall k (s :: k) (w :: World). VertexId s w -> Value
ToJSON,Value -> Parser [VertexId s w]
Value -> Parser (VertexId s w)
(Value -> Parser (VertexId s w))
-> (Value -> Parser [VertexId s w]) -> FromJSON (VertexId s w)
forall a.
(Value -> Parser a) -> (Value -> Parser [a]) -> FromJSON a
forall k (s :: k) (w :: World). Value -> Parser [VertexId s w]
forall k (s :: k) (w :: World). Value -> Parser (VertexId s w)
parseJSONList :: Value -> Parser [VertexId s w]
$cparseJSONList :: forall k (s :: k) (w :: World). Value -> Parser [VertexId s w]
parseJSON :: Value -> Parser (VertexId s w)
$cparseJSON :: forall k (s :: k) (w :: World). Value -> Parser (VertexId s w)
FromJSON,(forall x. VertexId s w -> Rep (VertexId s w) x)
-> (forall x. Rep (VertexId s w) x -> VertexId s w)
-> Generic (VertexId s w)
forall x. Rep (VertexId s w) x -> VertexId s w
forall x. VertexId s w -> Rep (VertexId s w) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (s :: k) (w :: World) x.
Rep (VertexId s w) x -> VertexId s w
forall k (s :: k) (w :: World) x.
VertexId s w -> Rep (VertexId s w) x
$cto :: forall k (s :: k) (w :: World) x.
Rep (VertexId s w) x -> VertexId s w
$cfrom :: forall k (s :: k) (w :: World) x.
VertexId s w -> Rep (VertexId s w) x
Generic,VertexId s w -> ()
(VertexId s w -> ()) -> NFData (VertexId s w)
forall a. (a -> ()) -> NFData a
forall k (s :: k) (w :: World). VertexId s w -> ()
rnf :: VertexId s w -> ()
$crnf :: forall k (s :: k) (w :: World). VertexId s w -> ()
NFData)
-- VertexId's are in the range 0...|orbits|-1

-- | Shorthand for vertices in the primal.
type VertexId' s = VertexId s Primal

-- | Getter for a VertexId's unique number.
unVertexId :: Getter (VertexId s w) Int
unVertexId :: (Int -> f Int) -> VertexId s w -> f (VertexId s w)
unVertexId = (VertexId s w -> Int)
-> (Int -> f Int) -> VertexId s w -> f (VertexId s w)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to VertexId s w -> Int
forall k (s :: k) (w :: World). VertexId s w -> Int
_unVertexId

instance Show (VertexId s w) where
  show :: VertexId s w -> String
show (VertexId Int
i) = String
"VertexId " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
i

--------------------------------------------------------------------------------
-- * FaceId's

-- | The type to represent FaceId's
newtype FaceId s w = FaceId { FaceId s w -> VertexId s (DualOf w)
_unFaceId :: VertexId s (DualOf w) }
                   deriving (FaceId s w -> FaceId s w -> Bool
(FaceId s w -> FaceId s w -> Bool)
-> (FaceId s w -> FaceId s w -> Bool) -> Eq (FaceId s w)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
/= :: FaceId s w -> FaceId s w -> Bool
$c/= :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
== :: FaceId s w -> FaceId s w -> Bool
$c== :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
Eq,Eq (FaceId s w)
Eq (FaceId s w)
-> (FaceId s w -> FaceId s w -> Ordering)
-> (FaceId s w -> FaceId s w -> Bool)
-> (FaceId s w -> FaceId s w -> Bool)
-> (FaceId s w -> FaceId s w -> Bool)
-> (FaceId s w -> FaceId s w -> Bool)
-> (FaceId s w -> FaceId s w -> FaceId s w)
-> (FaceId s w -> FaceId s w -> FaceId s w)
-> Ord (FaceId s w)
FaceId s w -> FaceId s w -> Bool
FaceId s w -> FaceId s w -> Ordering
FaceId s w -> FaceId s w -> FaceId s w
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k (s :: k) (w :: World). Eq (FaceId s w)
forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> Ordering
forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> FaceId s w
min :: FaceId s w -> FaceId s w -> FaceId s w
$cmin :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> FaceId s w
max :: FaceId s w -> FaceId s w -> FaceId s w
$cmax :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> FaceId s w
>= :: FaceId s w -> FaceId s w -> Bool
$c>= :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
> :: FaceId s w -> FaceId s w -> Bool
$c> :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
<= :: FaceId s w -> FaceId s w -> Bool
$c<= :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
< :: FaceId s w -> FaceId s w -> Bool
$c< :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w -> Bool
compare :: FaceId s w -> FaceId s w -> Ordering
$ccompare :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> Ordering
$cp1Ord :: forall k (s :: k) (w :: World). Eq (FaceId s w)
Ord,Int -> FaceId s w
FaceId s w -> Int
FaceId s w -> [FaceId s w]
FaceId s w -> FaceId s w
FaceId s w -> FaceId s w -> [FaceId s w]
FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w]
(FaceId s w -> FaceId s w)
-> (FaceId s w -> FaceId s w)
-> (Int -> FaceId s w)
-> (FaceId s w -> Int)
-> (FaceId s w -> [FaceId s w])
-> (FaceId s w -> FaceId s w -> [FaceId s w])
-> (FaceId s w -> FaceId s w -> [FaceId s w])
-> (FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w])
-> Enum (FaceId s w)
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
forall k (s :: k) (w :: World). Int -> FaceId s w
forall k (s :: k) (w :: World). FaceId s w -> Int
forall k (s :: k) (w :: World). FaceId s w -> [FaceId s w]
forall k (s :: k) (w :: World). FaceId s w -> FaceId s w
forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> [FaceId s w]
forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w]
enumFromThenTo :: FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w]
$cenumFromThenTo :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w]
enumFromTo :: FaceId s w -> FaceId s w -> [FaceId s w]
$cenumFromTo :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> [FaceId s w]
enumFromThen :: FaceId s w -> FaceId s w -> [FaceId s w]
$cenumFromThen :: forall k (s :: k) (w :: World).
FaceId s w -> FaceId s w -> [FaceId s w]
enumFrom :: FaceId s w -> [FaceId s w]
$cenumFrom :: forall k (s :: k) (w :: World). FaceId s w -> [FaceId s w]
fromEnum :: FaceId s w -> Int
$cfromEnum :: forall k (s :: k) (w :: World). FaceId s w -> Int
toEnum :: Int -> FaceId s w
$ctoEnum :: forall k (s :: k) (w :: World). Int -> FaceId s w
pred :: FaceId s w -> FaceId s w
$cpred :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w
succ :: FaceId s w -> FaceId s w
$csucc :: forall k (s :: k) (w :: World). FaceId s w -> FaceId s w
Enum,[FaceId s w] -> Encoding
[FaceId s w] -> Value
FaceId s w -> Encoding
FaceId s w -> Value
(FaceId s w -> Value)
-> (FaceId s w -> Encoding)
-> ([FaceId s w] -> Value)
-> ([FaceId s w] -> Encoding)
-> ToJSON (FaceId s w)
forall a.
(a -> Value)
-> (a -> Encoding)
-> ([a] -> Value)
-> ([a] -> Encoding)
-> ToJSON a
forall k (s :: k) (w :: World). [FaceId s w] -> Encoding
forall k (s :: k) (w :: World). [FaceId s w] -> Value
forall k (s :: k) (w :: World). FaceId s w -> Encoding
forall k (s :: k) (w :: World). FaceId s w -> Value
toEncodingList :: [FaceId s w] -> Encoding
$ctoEncodingList :: forall k (s :: k) (w :: World). [FaceId s w] -> Encoding
toJSONList :: [FaceId s w] -> Value
$ctoJSONList :: forall k (s :: k) (w :: World). [FaceId s w] -> Value
toEncoding :: FaceId s w -> Encoding
$ctoEncoding :: forall k (s :: k) (w :: World). FaceId s w -> Encoding
toJSON :: FaceId s w -> Value
$ctoJSON :: forall k (s :: k) (w :: World). FaceId s w -> Value
ToJSON,Value -> Parser [FaceId s w]
Value -> Parser (FaceId s w)
(Value -> Parser (FaceId s w))
-> (Value -> Parser [FaceId s w]) -> FromJSON (FaceId s w)
forall a.
(Value -> Parser a) -> (Value -> Parser [a]) -> FromJSON a
forall k (s :: k) (w :: World). Value -> Parser [FaceId s w]
forall k (s :: k) (w :: World). Value -> Parser (FaceId s w)
parseJSONList :: Value -> Parser [FaceId s w]
$cparseJSONList :: forall k (s :: k) (w :: World). Value -> Parser [FaceId s w]
parseJSON :: Value -> Parser (FaceId s w)
$cparseJSON :: forall k (s :: k) (w :: World). Value -> Parser (FaceId s w)
FromJSON)

-- | Shorthand for FaceId's in the primal.
type FaceId' s = FaceId s Primal

instance Show (FaceId s w) where
  show :: FaceId s w -> String
show (FaceId (VertexId Int
i)) = String
"FaceId " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
i


--------------------------------------------------------------------------------
-- * The graph type itself

-- | A *connected* Planar graph with bidirected edges. I.e. the edges (darts) are
-- directed, however, for every directed edge, the edge in the oposite
-- direction is also in the graph.
--
-- The types v, e, and f are the are the types of the data associated with the
-- vertices, edges, and faces, respectively.
--
-- The orbits in the embedding are assumed to be in counterclockwise
-- order. Therefore, every dart directly bounds the face to its right.
data PlanarGraph s (w :: World) v e f = PlanarGraph { PlanarGraph s w v e f -> Permutation (Dart s)
_embedding   :: Permutation (Dart s)
                                                    , PlanarGraph s w v e f -> Vector v
_vertexData  :: V.Vector v
                                                    , PlanarGraph s w v e f -> Vector e
_rawDartData :: V.Vector e
                                                    , PlanarGraph s w v e f -> Vector f
_faceData    :: V.Vector f
                                                    , PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
_dual        :: PlanarGraph s (DualOf w) f e v
                                                    } deriving ((forall x. PlanarGraph s w v e f -> Rep (PlanarGraph s w v e f) x)
-> (forall x.
    Rep (PlanarGraph s w v e f) x -> PlanarGraph s w v e f)
-> Generic (PlanarGraph s w v e f)
forall x. Rep (PlanarGraph s w v e f) x -> PlanarGraph s w v e f
forall x. PlanarGraph s w v e f -> Rep (PlanarGraph s w v e f) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (s :: k) (w :: World) v e f x.
Rep (PlanarGraph s w v e f) x -> PlanarGraph s w v e f
forall k (s :: k) (w :: World) v e f x.
PlanarGraph s w v e f -> Rep (PlanarGraph s w v e f) x
$cto :: forall k (s :: k) (w :: World) v e f x.
Rep (PlanarGraph s w v e f) x -> PlanarGraph s w v e f
$cfrom :: forall k (s :: k) (w :: World) v e f x.
PlanarGraph s w v e f -> Rep (PlanarGraph s w v e f) x
Generic)

instance (Show v, Show e, Show f) => Show (PlanarGraph s w v e f) where
  show :: PlanarGraph s w v e f -> String
show (PlanarGraph Permutation (Dart s)
e Vector v
v Vector e
r Vector f
f PlanarGraph s (DualOf w) f e v
_) = [String] -> String
unwords [ String
"PlanarGraph"
                                         , String
"embedding =", Permutation (Dart s) -> String
forall a. Show a => a -> String
show Permutation (Dart s)
e
                                         , String
", vertexData =", Vector v -> String
forall a. Show a => a -> String
show Vector v
v
                                         , String
", rawDartData =", Vector e -> String
forall a. Show a => a -> String
show Vector e
r
                                         , String
", faceData =", Vector f -> String
forall a. Show a => a -> String
show Vector f
f
                                         ]

instance (Eq v, Eq e, Eq f) => Eq (PlanarGraph s w v e f) where
  (PlanarGraph Permutation (Dart s)
e Vector v
v Vector e
r Vector f
f PlanarGraph s (DualOf w) f e v
_) == :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool
== (PlanarGraph Permutation (Dart s)
e' Vector v
v' Vector e
r' Vector f
f' PlanarGraph s (DualOf w) f e v
_) =  Permutation (Dart s)
e Permutation (Dart s) -> Permutation (Dart s) -> Bool
forall a. Eq a => a -> a -> Bool
== Permutation (Dart s)
e' Bool -> Bool -> Bool
&& Vector v
v Vector v -> Vector v -> Bool
forall a. Eq a => a -> a -> Bool
== Vector v
v'
                                                         Bool -> Bool -> Bool
&& Vector e
r Vector e -> Vector e -> Bool
forall a. Eq a => a -> a -> Bool
== Vector e
r' Bool -> Bool -> Bool
&& Vector f
f Vector f -> Vector f -> Bool
forall a. Eq a => a -> a -> Bool
== Vector f
f'



-- ** lenses and getters

-- | Get the embedding, represented as a permutation of the darts, of this
-- graph.
embedding :: Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding :: (Permutation (Dart s) -> f (Permutation (Dart s)))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f)
embedding = (PlanarGraph s w v e f -> Permutation (Dart s))
-> (Permutation (Dart s) -> f (Permutation (Dart s)))
-> PlanarGraph s w v e f
-> f (PlanarGraph s w v e f)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to PlanarGraph s w v e f -> Permutation (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Permutation (Dart s)
_embedding

-- | O\(1\) access, \( O(n) \) update.
vertexData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v' e f)
                   (V.Vector v) (V.Vector v')
vertexData :: (Vector v -> f (Vector v'))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v' e f)
vertexData = (PlanarGraph s w v e f -> Vector v)
-> (PlanarGraph s w v e f -> Vector v' -> PlanarGraph s w v' e f)
-> Lens
     (PlanarGraph s w v e f)
     (PlanarGraph s w v' e f)
     (Vector v)
     (Vector v')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarGraph s w v e f -> Vector v
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector v
_vertexData (\PlanarGraph s w v e f
g Vector v'
vD -> (Vector v -> Vector v')
-> (Vector e -> Vector e)
-> (Vector f -> Vector f)
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e f
forall k (s :: k) (w :: World) v e f v' e' f'.
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData (Vector v' -> Vector v -> Vector v'
forall a b. a -> b -> a
const Vector v'
vD) Vector e -> Vector e
forall a. a -> a
id Vector f -> Vector f
forall a. a -> a
id PlanarGraph s w v e f
g)

-- | O\(1\) access, \( O(n) \) update.
rawDartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f)
                    (V.Vector e) (V.Vector e')
rawDartData :: (Vector e -> f (Vector e'))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e' f)
rawDartData = (PlanarGraph s w v e f -> Vector e)
-> (PlanarGraph s w v e f -> Vector e' -> PlanarGraph s w v e' f)
-> Lens
     (PlanarGraph s w v e f)
     (PlanarGraph s w v e' f)
     (Vector e)
     (Vector e')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarGraph s w v e f -> Vector e
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector e
_rawDartData (\PlanarGraph s w v e f
g Vector e'
dD -> (Vector v -> Vector v)
-> (Vector e -> Vector e')
-> (Vector f -> Vector f)
-> PlanarGraph s w v e f
-> PlanarGraph s w v e' f
forall k (s :: k) (w :: World) v e f v' e' f'.
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData Vector v -> Vector v
forall a. a -> a
id (Vector e' -> Vector e -> Vector e'
forall a b. a -> b -> a
const Vector e'
dD) Vector f -> Vector f
forall a. a -> a
id PlanarGraph s w v e f
g)

-- | O\(1\) access, \( O(n) \) update.
faceData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e f')
                 (V.Vector f) (V.Vector f')
faceData :: (Vector f -> f (Vector f'))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f')
faceData = (PlanarGraph s w v e f -> Vector f)
-> (PlanarGraph s w v e f -> Vector f' -> PlanarGraph s w v e f')
-> Lens
     (PlanarGraph s w v e f)
     (PlanarGraph s w v e f')
     (Vector f)
     (Vector f')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarGraph s w v e f -> Vector f
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector f
_faceData (\PlanarGraph s w v e f
g Vector f'
fD -> (Vector v -> Vector v)
-> (Vector e -> Vector e)
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v e f'
forall k (s :: k) (w :: World) v e f v' e' f'.
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData Vector v -> Vector v
forall a. a -> a
id Vector e -> Vector e
forall a. a -> a
id (Vector f' -> Vector f -> Vector f'
forall a b. a -> b -> a
const Vector f'
fD) PlanarGraph s w v e f
g)

-- | Get the dual graph of this graph.
dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v)
dual :: (PlanarGraph s (DualOf w) f e v
 -> f (PlanarGraph s (DualOf w) f e v))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f)
dual = (PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v)
-> (PlanarGraph s (DualOf w) f e v
    -> f (PlanarGraph s (DualOf w) f e v))
-> PlanarGraph s w v e f
-> f (PlanarGraph s w v e f)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
_dual


-- FIXME: So I guess the two darts associated with an edge can store different
-- data. This is useful. Make sure that works as expected.

-- | lens to access the Dart Data
--
--
dartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f)
                 (V.Vector (Dart s, e))  (V.Vector (Dart s, e'))
dartData :: (Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e' f)
dartData = (PlanarGraph s w v e f -> Vector (Dart s, e))
-> (PlanarGraph s w v e f
    -> Vector (Dart s, e') -> PlanarGraph s w v e' f)
-> Lens
     (PlanarGraph s w v e f)
     (PlanarGraph s w v e' f)
     (Vector (Dart s, e))
     (Vector (Dart s, e'))
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarGraph s w v e f -> Vector (Dart s, e)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s, e)
darts (\PlanarGraph s w v e f
g Vector (Dart s, e')
dD -> (Vector v -> Vector v)
-> (Vector e -> Vector e')
-> (Vector f -> Vector f)
-> PlanarGraph s w v e f
-> PlanarGraph s w v e' f
forall k (s :: k) (w :: World) v e f v' e' f'.
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData Vector v -> Vector v
forall a. a -> a
id (Vector e' -> Vector e -> Vector e'
forall a b. a -> b -> a
const (Vector e' -> Vector e -> Vector e')
-> Vector e' -> Vector e -> Vector e'
forall a b. (a -> b) -> a -> b
$ Vector (Dart s, e') -> Vector e'
forall k (f :: * -> *) (s :: k) e.
Foldable f =>
f (Dart s, e) -> Vector e
reorderEdgeData Vector (Dart s, e')
dD) Vector f -> Vector f
forall a. a -> a
id PlanarGraph s w v e f
g)

-- | edgeData is just an alias for 'dartData'
edgeData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f)
                 (V.Vector (Dart s, e)) (V.Vector (Dart s, e'))
edgeData :: (Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e' f)
edgeData = (Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e' f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector (Dart s, e))
  (Vector (Dart s, e'))
dartData

-- | Helper function to update the data in a planar graph. Takes care to update
-- both the data in the original graph as well as in the dual.
updateData :: forall s w v e f v' e' f'
           .  (V.Vector v -> V.Vector v')
           -> (V.Vector e -> V.Vector e')
           -> (V.Vector f -> V.Vector f')
           -> PlanarGraph s w v  e  f
           -> PlanarGraph s w v' e' f'
updateData :: (Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData = (DualOf (DualOf w) :~: w)
-> ((DualOf (DualOf w) ~ w) =>
    (Vector v -> Vector v')
    -> (Vector e -> Vector e')
    -> (Vector f -> Vector f')
    -> PlanarGraph s w v e f
    -> PlanarGraph s w v' e' f')
-> (Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
gcastWith DualOf (DualOf w) :~: w
proof (DualOf (DualOf w) ~ w) =>
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
forall k (w :: World) v v' e e' f f' (s :: k).
(DualOf (DualOf w) ~ w) =>
(Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData'
  where
    proof :: DualOf (DualOf w) :~: w
    proof :: DualOf (DualOf w) :~: w
proof = DualOf (DualOf w) :~: w
forall (w :: World). DualOf (DualOf w) :~: w
dualDualIdentity

-- | The function that does the actual work for 'updateData'
updateData'  :: (DualOf (DualOf w) ~ w)
             => (V.Vector v -> V.Vector v')
             -> (V.Vector e -> V.Vector e')
             -> (V.Vector f -> V.Vector f')
             -> PlanarGraph s w v  e  f
             -> PlanarGraph s w v' e' f'
updateData' :: (Vector v -> Vector v')
-> (Vector e -> Vector e')
-> (Vector f -> Vector f')
-> PlanarGraph s w v e f
-> PlanarGraph s w v' e' f'
updateData' Vector v -> Vector v'
fv Vector e -> Vector e'
fe Vector f -> Vector f'
ff (PlanarGraph Permutation (Dart s)
em Vector v
vtxData Vector e
dData Vector f
fData PlanarGraph s (DualOf w) f e v
dg) = PlanarGraph s w v' e' f'
g'
  where
    vtxData' :: Vector v'
vtxData' = Vector v -> Vector v'
fv Vector v
vtxData
    dData' :: Vector e'
dData'   = Vector e -> Vector e'
fe Vector e
dData
    fData' :: Vector f'
fData'   = Vector f -> Vector f'
ff Vector f
fData

    g' :: PlanarGraph s w v' e' f'
g'       = Permutation (Dart s)
-> Vector v'
-> Vector e'
-> Vector f'
-> PlanarGraph s (DualOf w) f' e' v'
-> PlanarGraph s w v' e' f'
forall k (s :: k) (w :: World) v e f.
Permutation (Dart s)
-> Vector v
-> Vector e
-> Vector f
-> PlanarGraph s (DualOf w) f e v
-> PlanarGraph s w v e f
PlanarGraph Permutation (Dart s)
em              Vector v'
vtxData' Vector e'
dData' Vector f'
fData'   PlanarGraph s (DualOf w) f' e' v'
dg'
    dg' :: PlanarGraph s (DualOf w) f' e' v'
dg'      = Permutation (Dart s)
-> Vector f'
-> Vector e'
-> Vector v'
-> PlanarGraph s (DualOf (DualOf w)) v' e' f'
-> PlanarGraph s (DualOf w) f' e' v'
forall k (s :: k) (w :: World) v e f.
Permutation (Dart s)
-> Vector v
-> Vector e
-> Vector f
-> PlanarGraph s (DualOf w) f e v
-> PlanarGraph s w v e f
PlanarGraph (PlanarGraph s (DualOf w) f e v
dgPlanarGraph s (DualOf w) f e v
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s (DualOf w) f e v)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s (DualOf w) f e v)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding) Vector f'
fData'   Vector e'
dData' Vector v'
vtxData' PlanarGraph s w v' e' f'
PlanarGraph s (DualOf (DualOf w)) v' e' f'
g'


-- | Reorders the edge data to be in the right order to set edgeData
reorderEdgeData    :: Foldable f => f (Dart s, e) -> V.Vector e
reorderEdgeData :: f (Dart s, e) -> Vector e
reorderEdgeData f (Dart s, e)
ds = (forall s. ST s (MVector s e)) -> Vector e
forall a. (forall s. ST s (MVector s a)) -> Vector a
V.create ((forall s. ST s (MVector s e)) -> Vector e)
-> (forall s. ST s (MVector s e)) -> Vector e
forall a b. (a -> b) -> a -> b
$ do
                                  MVector s e
v <- Int -> ST s (MVector (PrimState (ST s)) e)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> m (MVector (PrimState m) a)
MV.new (f (Dart s, e) -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
F.length f (Dart s, e)
ds)
                                  [(Dart s, e)] -> ((Dart s, e) -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ (f (Dart s, e) -> [(Dart s, e)]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList f (Dart s, e)
ds) (((Dart s, e) -> ST s ()) -> ST s ())
-> ((Dart s, e) -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \(Dart s
d,e
x) ->
                                    MVector (PrimState (ST s)) e -> Int -> e -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
MV.write MVector s e
MVector (PrimState (ST s)) e
v (Dart s -> Int
forall a. Enum a => a -> Int
fromEnum Dart s
d) e
x
                                  MVector s e -> ST s (MVector s e)
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s e
v

-- | Traverse the vertices
--
-- >>> (^.vertexData) <$> traverseVertices (\i x -> Just (i,x)) myGraph
-- Just [(VertexId 0,()),(VertexId 1,()),(VertexId 2,()),(VertexId 3,())]
-- >>> traverseVertices (\i x -> print (i,x)) myGraph >> pure ()
-- (VertexId 0,())
-- (VertexId 1,())
-- (VertexId 2,())
-- (VertexId 3,())
traverseVertices   :: Applicative m
                   => (VertexId s w -> v -> m v')
                   -> PlanarGraph s w v e f
                   -> m (PlanarGraph s w v' e f)
traverseVertices :: (VertexId s w -> v -> m v')
-> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f)
traverseVertices VertexId s w -> v -> m v'
f = (Indexed Int v (m v')
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f))
-> (Int -> v -> m v')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v' e f)
forall i a (f :: * -> *) b s t.
(Indexed i a (f b) -> s -> f t) -> (i -> a -> f b) -> s -> f t
itraverseOf ((Vector v -> m (Vector v'))
-> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
vertexData((Vector v -> m (Vector v'))
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f))
-> (Indexed Int v (m v') -> Vector v -> m (Vector v'))
-> Indexed Int v (m v')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v' e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Indexed Int v (m v') -> Vector v -> m (Vector v')
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
itraversed) (VertexId s w -> v -> m v'
f (VertexId s w -> v -> m v')
-> (Int -> VertexId s w) -> Int -> v -> m v'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId s w
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId)

-- | Traverses the darts
--
-- >>> traverseDarts (\d x -> print (d,x)) myGraph >> pure ()
-- (Dart (Arc 0) +1,"a+")
-- (Dart (Arc 0) -1,"a-")
-- (Dart (Arc 1) +1,"b+")
-- (Dart (Arc 1) -1,"b-")
-- (Dart (Arc 2) +1,"c+")
-- (Dart (Arc 2) -1,"c-")
-- (Dart (Arc 3) +1,"d+")
-- (Dart (Arc 3) -1,"d-")
-- (Dart (Arc 4) +1,"e+")
-- (Dart (Arc 4) -1,"e-")
-- (Dart (Arc 5) +1,"g+")
-- (Dart (Arc 5) -1,"g-")
traverseDarts   :: Applicative m
                => (Dart s -> e -> m e')
                -> PlanarGraph s w v e f
                -> m (PlanarGraph s w v e' f)
traverseDarts :: (Dart s -> e -> m e')
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f)
traverseDarts Dart s -> e -> m e'
f = (Indexed Int e (m e')
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f))
-> (Int -> e -> m e')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v e' f)
forall i a (f :: * -> *) b s t.
(Indexed i a (f b) -> s -> f t) -> (i -> a -> f b) -> s -> f t
itraverseOf ((Vector e -> m (Vector e'))
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector e)
  (Vector e')
rawDartData((Vector e -> m (Vector e'))
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f))
-> (Indexed Int e (m e') -> Vector e -> m (Vector e'))
-> Indexed Int e (m e')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v e' f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Indexed Int e (m e') -> Vector e -> m (Vector e')
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
itraversed) (Dart s -> e -> m e'
f (Dart s -> e -> m e') -> (Int -> Dart s) -> Int -> e -> m e'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Dart s
forall a. Enum a => Int -> a
toEnum)

-- | Traverses the faces
--
-- >>> traverseFaces (\i x -> print (i,x)) myGraph >> pure ()
-- (FaceId 0,())
-- (FaceId 1,())
-- (FaceId 2,())
-- (FaceId 3,())
traverseFaces   :: Applicative m
                => (FaceId s w -> f -> m f')
                -> PlanarGraph s w v e f
                -> m (PlanarGraph s w v e f')
traverseFaces :: (FaceId s w -> f -> m f')
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e f')
traverseFaces FaceId s w -> f -> m f'
f = (Indexed Int f (m f')
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v e f'))
-> (Int -> f -> m f')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v e f')
forall i a (f :: * -> *) b s t.
(Indexed i a (f b) -> s -> f t) -> (i -> a -> f b) -> s -> f t
itraverseOf ((Vector f -> m (Vector f'))
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e f')
forall k (s :: k) (w :: World) v e f f'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e f')
  (Vector f)
  (Vector f')
faceData((Vector f -> m (Vector f'))
 -> PlanarGraph s w v e f -> m (PlanarGraph s w v e f'))
-> (Indexed Int f (m f') -> Vector f -> m (Vector f'))
-> Indexed Int f (m f')
-> PlanarGraph s w v e f
-> m (PlanarGraph s w v e f')
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Indexed Int f (m f') -> Vector f -> m (Vector f')
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
itraversed) (\Int
i -> FaceId s w -> f -> m f'
f (VertexId s (DualOf w) -> FaceId s w
forall k (s :: k) (w :: World). VertexId s (DualOf w) -> FaceId s w
FaceId (VertexId s (DualOf w) -> FaceId s w)
-> VertexId s (DualOf w) -> FaceId s w
forall a b. (a -> b) -> a -> b
$ Int -> VertexId s (DualOf w)
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId Int
i))

--------------------------------------------------------------------------------
-- ** Constructing a Planar graph

-- | Construct a planar graph
--
-- running time: \(O(n)\).
planarGraph'      :: Permutation (Dart s) -> PlanarGraph s w () () ()
planarGraph' :: Permutation (Dart s) -> PlanarGraph s w () () ()
planarGraph' Permutation (Dart s)
perm = PlanarGraph s w () () ()
pg
  where
    pg :: PlanarGraph s w () () ()
pg = Permutation (Dart s)
-> Vector ()
-> Vector ()
-> Vector ()
-> PlanarGraph s (DualOf w) () () ()
-> PlanarGraph s w () () ()
forall k (s :: k) (w :: World) v e f.
Permutation (Dart s)
-> Vector v
-> Vector e
-> Vector f
-> PlanarGraph s (DualOf w) f e v
-> PlanarGraph s w v e f
PlanarGraph Permutation (Dart s)
perm Vector ()
vData Vector ()
eData Vector ()
fData (PlanarGraph s w () () () -> PlanarGraph s (DualOf w) () () ()
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual PlanarGraph s w () () ()
pg)
        -- note the lazy calculation of computeDual that refers to pg itself
    d :: Int
d  = Permutation (Dart s) -> Int
forall a. Permutation a -> Int
size Permutation (Dart s)
perm
    e :: Int
e  = Int
d Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
    v :: Int
v  = Vector (Orbit (Dart s)) -> Int
forall a. Vector a -> Int
V.length (Permutation (Dart s)
permPermutation (Dart s)
-> Getting
     (Vector (Orbit (Dart s)))
     (Permutation (Dart s))
     (Vector (Orbit (Dart s)))
-> Vector (Orbit (Dart s))
forall s a. s -> Getting a s a -> a
^.Getting
  (Vector (Orbit (Dart s)))
  (Permutation (Dart s))
  (Vector (Orbit (Dart s)))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits)
    f :: Int
f  = Int
e Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
v Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2

    vData :: Vector ()
vData  = Int -> () -> Vector ()
forall a. Int -> a -> Vector a
V.replicate Int
v ()
    eData :: Vector ()
eData  = Int -> () -> Vector ()
forall a. Int -> a -> Vector a
V.replicate Int
d ()
    fData :: Vector ()
fData  = Int -> () -> Vector ()
forall a. Int -> a -> Vector a
V.replicate Int
f ()

-- | Construct a planar graph, given the darts in cyclic order around each
-- vertex.
--
-- running time: \(O(n)\).
planarGraph    :: [[(Dart s,e)]] -> PlanarGraph s Primal () e ()
planarGraph :: [[(Dart s, e)]] -> PlanarGraph s 'Primal () e ()
planarGraph [[(Dart s, e)]]
ds = Permutation (Dart s) -> PlanarGraph s 'Primal () () ()
forall k (s :: k) (w :: World).
Permutation (Dart s) -> PlanarGraph s w () () ()
planarGraph' Permutation (Dart s)
perm PlanarGraph s 'Primal () () ()
-> (PlanarGraph s 'Primal () () ()
    -> PlanarGraph s 'Primal () e ())
-> PlanarGraph s 'Primal () e ()
forall a b. a -> (a -> b) -> b
& (Vector (Dart s, ()) -> Identity (Vector (Dart s, e)))
-> PlanarGraph s 'Primal () () ()
-> Identity (PlanarGraph s 'Primal () e ())
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector (Dart s, e))
  (Vector (Dart s, e'))
dartData ((Vector (Dart s, ()) -> Identity (Vector (Dart s, e)))
 -> PlanarGraph s 'Primal () () ()
 -> Identity (PlanarGraph s 'Primal () e ()))
-> Vector (Dart s, e)
-> PlanarGraph s 'Primal () () ()
-> PlanarGraph s 'Primal () e ()
forall s t a b. ASetter s t a b -> b -> s -> t
.~ ([(Dart s, e)] -> Vector (Dart s, e)
forall a. [a] -> Vector a
V.fromList ([(Dart s, e)] -> Vector (Dart s, e))
-> ([[(Dart s, e)]] -> [(Dart s, e)])
-> [[(Dart s, e)]]
-> Vector (Dart s, e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[(Dart s, e)]] -> [(Dart s, e)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[(Dart s, e)]] -> Vector (Dart s, e))
-> [[(Dart s, e)]] -> Vector (Dart s, e)
forall a b. (a -> b) -> a -> b
$ [[(Dart s, e)]]
ds)
  where
    n :: Int
n     = [Int] -> Int
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int)
-> ([[(Dart s, e)]] -> [Int]) -> [[(Dart s, e)]] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([(Dart s, e)] -> Int) -> [[(Dart s, e)]] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map [(Dart s, e)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([[(Dart s, e)]] -> Int) -> [[(Dart s, e)]] -> Int
forall a b. (a -> b) -> a -> b
$ [[(Dart s, e)]]
ds
    perm :: Permutation (Dart s)
perm  = Int -> [[Dart s]] -> Permutation (Dart s)
forall a. Enum a => Int -> [[a]] -> Permutation a
toCycleRep Int
n ([[Dart s]] -> Permutation (Dart s))
-> [[Dart s]] -> Permutation (Dart s)
forall a b. (a -> b) -> a -> b
$ ([(Dart s, e)] -> [Dart s]) -> [[(Dart s, e)]] -> [[Dart s]]
forall a b. (a -> b) -> [a] -> [b]
map (((Dart s, e) -> Dart s) -> [(Dart s, e)] -> [Dart s]
forall a b. (a -> b) -> [a] -> [b]
map (Dart s, e) -> Dart s
forall a b. (a, b) -> a
fst) [[(Dart s, e)]]
ds




-- | Produces the adjacencylists for all vertices in the graph. For every vertex, the
-- adjacent vertices are given in counter clockwise order.
--
-- Note that in case a vertex u as a self loop, we have that this vertexId occurs
-- twice in the list of neighbours, i.e.: u : [...,u,..,u,...]. Similarly, if there are
-- multiple darts between a pair of edges they occur multiple times.
--
-- running time: \(O(n)\)
toAdjacencyLists    :: PlanarGraph s w v e f -> [(VertexId s w, V.Vector (VertexId s w))]
toAdjacencyLists :: PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))]
toAdjacencyLists PlanarGraph s w v e f
pg = (VertexId s w -> (VertexId s w, Vector (VertexId s w)))
-> [VertexId s w] -> [(VertexId s w, Vector (VertexId s w))]
forall a b. (a -> b) -> [a] -> [b]
map (\VertexId s w
u -> (VertexId s w
u,VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)
neighboursOf VertexId s w
u PlanarGraph s w v e f
pg)) ([VertexId s w] -> [(VertexId s w, Vector (VertexId s w))])
-> (PlanarGraph s w v e f -> [VertexId s w])
-> PlanarGraph s w v e f
-> [(VertexId s w, Vector (VertexId s w))]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (VertexId s w) -> [VertexId s w]
forall a. Vector a -> [a]
V.toList (Vector (VertexId s w) -> [VertexId s w])
-> (PlanarGraph s w v e f -> Vector (VertexId s w))
-> PlanarGraph s w v e f
-> [VertexId s w]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarGraph s w v e f -> Vector (VertexId s w)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (VertexId s w)
vertices' (PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))])
-> PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))]
forall a b. (a -> b) -> a -> b
$ PlanarGraph s w v e f
pg
-- TODO: something weird happens when we have self-loops here.


--------------------------------------------------------------------------------
-- ** Convenience functions

-- | Get the number of vertices
--
-- >>> numVertices myGraph
-- 4
numVertices :: PlanarGraph s w v e f -> Int
numVertices :: PlanarGraph s w v e f -> Int
numVertices PlanarGraph s w v e f
g = Vector (Orbit (Dart s)) -> Int
forall a. Vector a -> Int
V.length (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Vector (Orbit (Dart s)))
     (PlanarGraph s w v e f)
     (Vector (Orbit (Dart s)))
-> Vector (Orbit (Dart s))
forall s a. s -> Getting a s a -> a
^.(Permutation (Dart s)
 -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
-> PlanarGraph s w v e f
-> Const (Vector (Orbit (Dart s))) (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding((Permutation (Dart s)
  -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
 -> PlanarGraph s w v e f
 -> Const (Vector (Orbit (Dart s))) (PlanarGraph s w v e f))
-> ((Vector (Orbit (Dart s))
     -> Const (Vector (Orbit (Dart s))) (Vector (Orbit (Dart s))))
    -> Permutation (Dart s)
    -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
-> Getting
     (Vector (Orbit (Dart s)))
     (PlanarGraph s w v e f)
     (Vector (Orbit (Dart s)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Orbit (Dart s))
 -> Const (Vector (Orbit (Dart s))) (Vector (Orbit (Dart s))))
-> Permutation (Dart s)
-> Const (Vector (Orbit (Dart s))) (Permutation (Dart s))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits)

-- | Get the number of Darts
--
-- >>> numDarts myGraph
-- 12
numDarts :: PlanarGraph s w v e f -> Int
numDarts :: PlanarGraph s w v e f -> Int
numDarts PlanarGraph s w v e f
g = Permutation (Dart s) -> Int
forall a. Permutation a -> Int
size (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s w v e f)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s w v e f)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding)

-- | Get the number of Edges
--
-- >>> numEdges myGraph
-- 6
numEdges :: PlanarGraph s w v e f -> Int
numEdges :: PlanarGraph s w v e f -> Int
numEdges PlanarGraph s w v e f
g = PlanarGraph s w v e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
numDarts PlanarGraph s w v e f
g Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2

-- | Get the number of faces
--
-- >>> numFaces myGraph
-- 4
numFaces   :: PlanarGraph s w v e f -> Int
numFaces :: PlanarGraph s w v e f -> Int
numFaces PlanarGraph s w v e f
g = PlanarGraph s w v e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
numEdges PlanarGraph s w v e f
g Int -> Int -> Int
forall a. Num a => a -> a -> a
- PlanarGraph s w v e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
numVertices PlanarGraph s w v e f
g Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2


-- | Enumerate all vertices
--
-- >>> vertices' myGraph
-- [VertexId 0,VertexId 1,VertexId 2,VertexId 3]
vertices'   :: PlanarGraph s w v e f -> V.Vector (VertexId s w)
vertices' :: PlanarGraph s w v e f -> Vector (VertexId s w)
vertices' PlanarGraph s w v e f
g = Int -> VertexId s w
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId (Int -> VertexId s w) -> Vector Int -> Vector (VertexId s w)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> Vector Int
forall a. Num a => a -> Int -> Vector a
V.enumFromN Int
0 (Vector (Orbit (Dart s)) -> Int
forall a. Vector a -> Int
V.length (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Vector (Orbit (Dart s)))
     (PlanarGraph s w v e f)
     (Vector (Orbit (Dart s)))
-> Vector (Orbit (Dart s))
forall s a. s -> Getting a s a -> a
^.(Permutation (Dart s)
 -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
-> PlanarGraph s w v e f
-> Const (Vector (Orbit (Dart s))) (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding((Permutation (Dart s)
  -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
 -> PlanarGraph s w v e f
 -> Const (Vector (Orbit (Dart s))) (PlanarGraph s w v e f))
-> ((Vector (Orbit (Dart s))
     -> Const (Vector (Orbit (Dart s))) (Vector (Orbit (Dart s))))
    -> Permutation (Dart s)
    -> Const (Vector (Orbit (Dart s))) (Permutation (Dart s)))
-> Getting
     (Vector (Orbit (Dart s)))
     (PlanarGraph s w v e f)
     (Vector (Orbit (Dart s)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Orbit (Dart s))
 -> Const (Vector (Orbit (Dart s))) (Vector (Orbit (Dart s))))
-> Permutation (Dart s)
-> Const (Vector (Orbit (Dart s))) (Permutation (Dart s))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits))

-- | Enumerate all vertices, together with their vertex data

-- >>> vertices myGraph
-- [(VertexId 0,()),(VertexId 1,()),(VertexId 2,()),(VertexId 3,())]
vertices   :: PlanarGraph s w v e f -> V.Vector (VertexId s w, v)
vertices :: PlanarGraph s w v e f -> Vector (VertexId s w, v)
vertices PlanarGraph s w v e f
g = Vector (VertexId s w) -> Vector v -> Vector (VertexId s w, v)
forall a b. Vector a -> Vector b -> Vector (a, b)
V.zip (PlanarGraph s w v e f -> Vector (VertexId s w)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (VertexId s w)
vertices' PlanarGraph s w v e f
g) (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting (Vector v) (PlanarGraph s w v e f) (Vector v)
-> Vector v
forall s a. s -> Getting a s a -> a
^.Getting (Vector v) (PlanarGraph s w v e f) (Vector v)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
vertexData)



-- | Enumerate all darts
darts' :: PlanarGraph s w v e f -> V.Vector (Dart s)
darts' :: PlanarGraph s w v e f -> Vector (Dart s)
darts' = Permutation (Dart s) -> Vector (Dart s)
forall a. Permutation a -> Vector a
elems (Permutation (Dart s) -> Vector (Dart s))
-> (PlanarGraph s w v e f -> Permutation (Dart s))
-> PlanarGraph s w v e f
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarGraph s w v e f -> Permutation (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Permutation (Dart s)
_embedding

-- | Get all darts together with their data
--
-- >>> mapM_ print $ darts myGraph
-- (Dart (Arc 0) -1,"a-")
-- (Dart (Arc 2) +1,"c+")
-- (Dart (Arc 1) +1,"b+")
-- (Dart (Arc 0) +1,"a+")
-- (Dart (Arc 4) -1,"e-")
-- (Dart (Arc 1) -1,"b-")
-- (Dart (Arc 3) -1,"d-")
-- (Dart (Arc 5) +1,"g+")
-- (Dart (Arc 4) +1,"e+")
-- (Dart (Arc 3) +1,"d+")
-- (Dart (Arc 2) -1,"c-")
-- (Dart (Arc 5) -1,"g-")
darts   :: PlanarGraph s w v e f -> V.Vector (Dart s, e)
darts :: PlanarGraph s w v e f -> Vector (Dart s, e)
darts PlanarGraph s w v e f
g = (\Dart s
d -> (Dart s
d,PlanarGraph s w v e f
gPlanarGraph s w v e f -> Getting e (PlanarGraph s w v e f) e -> e
forall s a. s -> Getting a s a -> a
^.Dart s
-> Lens'
     (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart s
d)) (Dart s -> (Dart s, e)) -> Vector (Dart s) -> Vector (Dart s, e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarGraph s w v e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s)
darts' PlanarGraph s w v e f
g

-- | Enumerate all edges. We report only the Positive darts
edges' :: PlanarGraph s w v e f -> V.Vector (Dart s)
edges' :: PlanarGraph s w v e f -> Vector (Dart s)
edges' = (Dart s -> Bool) -> Vector (Dart s) -> Vector (Dart s)
forall a. (a -> Bool) -> Vector a -> Vector a
V.filter Dart s -> Bool
forall k (s :: k). Dart s -> Bool
isPositive (Vector (Dart s) -> Vector (Dart s))
-> (PlanarGraph s w v e f -> Vector (Dart s))
-> PlanarGraph s w v e f
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarGraph s w v e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s)
darts'

-- | Enumerate all edges with their edge data. We report only the Positive
-- darts.
--
-- >>> mapM_ print $ edges myGraph
-- (Dart (Arc 2) +1,"c+")
-- (Dart (Arc 1) +1,"b+")
-- (Dart (Arc 0) +1,"a+")
-- (Dart (Arc 5) +1,"g+")
-- (Dart (Arc 4) +1,"e+")
-- (Dart (Arc 3) +1,"d+")
edges :: PlanarGraph s w v e f -> V.Vector (Dart s, e)
edges :: PlanarGraph s w v e f -> Vector (Dart s, e)
edges = ((Dart s, e) -> Bool) -> Vector (Dart s, e) -> Vector (Dart s, e)
forall a. (a -> Bool) -> Vector a -> Vector a
V.filter (Dart s -> Bool
forall k (s :: k). Dart s -> Bool
isPositive (Dart s -> Bool) -> ((Dart s, e) -> Dart s) -> (Dart s, e) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Dart s, e) -> Dart s
forall a b. (a, b) -> a
fst) (Vector (Dart s, e) -> Vector (Dart s, e))
-> (PlanarGraph s w v e f -> Vector (Dart s, e))
-> PlanarGraph s w v e f
-> Vector (Dart s, e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarGraph s w v e f -> Vector (Dart s, e)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s, e)
darts


-- | The tail of a dart, i.e. the vertex this dart is leaving from
--
-- running time: \(O(1)\)
tailOf     :: Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf Dart s
d PlanarGraph s w v e f
g = Int -> VertexId s w
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId (Int -> VertexId s w)
-> ((Int, Int) -> Int) -> (Int, Int) -> VertexId s w
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Int
forall a b. (a, b) -> a
fst ((Int, Int) -> VertexId s w) -> (Int, Int) -> VertexId s w
forall a b. (a -> b) -> a -> b
$ Permutation (Dart s) -> Dart s -> (Int, Int)
forall a. Enum a => Permutation a -> a -> (Int, Int)
lookupIdx (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s w v e f)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s w v e f)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding) Dart s
d

-- | The vertex this dart is heading in to
--
-- running time: \(O(1)\)
headOf   :: Dart s -> PlanarGraph s w v e f -> VertexId s w
headOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w
headOf Dart s
d = Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf (Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d)

-- | endPoints d g = (tailOf d g, headOf d g)
--
-- running time: \(O(1)\)
endPoints :: Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)
endPoints :: Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)
endPoints Dart s
d PlanarGraph s w v e f
g = (Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf Dart s
d PlanarGraph s w v e f
g, Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
headOf Dart s
d PlanarGraph s w v e f
g)


-- | All edges incident to vertex v, in counterclockwise order around v.
--
--
--
-- running time: \(O(k)\), where \(k\) is the output size
incidentEdges                :: VertexId s w -> PlanarGraph s w v e f
                             -> V.Vector (Dart s)
incidentEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
incidentEdges (VertexId Int
v) PlanarGraph s w v e f
g = PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Endo (Vector (Dart s))) (PlanarGraph s w v e f) (Vector (Dart s))
-> Vector (Dart s)
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Permutation (Dart s)
 -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
-> PlanarGraph s w v e f
-> Const (Endo (Vector (Dart s))) (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding((Permutation (Dart s)
  -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
 -> PlanarGraph s w v e f
 -> Const (Endo (Vector (Dart s))) (PlanarGraph s w v e f))
-> ((Vector (Dart s)
     -> Const (Endo (Vector (Dart s))) (Vector (Dart s)))
    -> Permutation (Dart s)
    -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
-> Getting
     (Endo (Vector (Dart s))) (PlanarGraph s w v e f) (Vector (Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Vector (Dart s))
 -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> Permutation (Dart s)
-> Const (Endo (Vector (Dart s))) (Permutation (Dart s))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits((Vector (Vector (Dart s))
  -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
 -> Permutation (Dart s)
 -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
-> ((Vector (Dart s)
     -> Const (Endo (Vector (Dart s))) (Vector (Dart s)))
    -> Vector (Vector (Dart s))
    -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> (Vector (Dart s)
    -> Const (Endo (Vector (Dart s))) (Vector (Dart s)))
-> Permutation (Dart s)
-> Const (Endo (Vector (Dart s))) (Permutation (Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Vector (Dart s)))
-> Traversal'
     (Vector (Vector (Dart s))) (IxValue (Vector (Vector (Dart s))))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Vector (Dart s)))
v
  -- TODO: The Delaunay triang. stuff seems to produce these in clockwise order instead

-- | All edges incident to vertex v in incoming direction
-- (i.e. pointing into v) in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k) is the total number of incident edges of v
incomingEdges     :: VertexId s w -> PlanarGraph s w v e f -> V.Vector (Dart s)
incomingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
incomingEdges VertexId s w
v PlanarGraph s w v e f
g = Dart s -> Dart s
orient (Dart s -> Dart s) -> Vector (Dart s) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
incidentEdges VertexId s w
v PlanarGraph s w v e f
g
  where
    orient :: Dart s -> Dart s
orient Dart s
d = if Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
headOf Dart s
d PlanarGraph s w v e f
g VertexId s w -> VertexId s w -> Bool
forall a. Eq a => a -> a -> Bool
== VertexId s w
v then Dart s
d else Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d

-- | All edges incident to vertex v in outgoing direction
-- (i.e. pointing away from v) in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k) is the total number of incident edges of v
outgoingEdges     :: VertexId s w -> PlanarGraph s w v e f -> V.Vector (Dart s)
outgoingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
outgoingEdges VertexId s w
v PlanarGraph s w v e f
g = Dart s -> Dart s
orient (Dart s -> Dart s) -> Vector (Dart s) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
incidentEdges VertexId s w
v PlanarGraph s w v e f
g
  where
    orient :: Dart s -> Dart s
orient Dart s
d = if Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf Dart s
d PlanarGraph s w v e f
g VertexId s w -> VertexId s w -> Bool
forall a. Eq a => a -> a -> Bool
== VertexId s w
v then Dart s
d else Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d


-- | Gets the neighbours of a particular vertex, in counterclockwise order
-- around the vertex.
--
-- running time: \(O(k)\), where \(k\) is the output size
neighboursOf     :: VertexId s w -> PlanarGraph s w v e f -> V.Vector (VertexId s w)
neighboursOf :: VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)
neighboursOf VertexId s w
v PlanarGraph s w v e f
g = (Dart s -> PlanarGraph s w v e f -> VertexId s w)
-> PlanarGraph s w v e f -> Dart s -> VertexId s w
forall a b c. (a -> b -> c) -> b -> a -> c
flip Dart s -> PlanarGraph s w v e f -> VertexId s w
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
tailOf PlanarGraph s w v e f
g (Dart s -> VertexId s w)
-> Vector (Dart s) -> Vector (VertexId s w)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
incomingEdges VertexId s w
v PlanarGraph s w v e f
g

-- | Given a dart d that points into some vertex v, report the next dart in the
-- cyclic order around v.
--
-- running time: \(O(1)\)
nextIncidentEdge     :: Dart s -> PlanarGraph s w v e f -> Dart s
nextIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s
nextIncidentEdge Dart s
d PlanarGraph s w v e f
g = let perm :: Permutation (Dart s)
perm  = PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s w v e f)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s w v e f)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding
                           (Int
i,Int
j) = Permutation (Dart s) -> Dart s -> (Int, Int)
forall a. Enum a => Permutation a -> a -> (Int, Int)
lookupIdx Permutation (Dart s)
perm Dart s
d
                       in Vector (Dart s) -> Int -> Dart s
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
next (Permutation (Dart s)
permPermutation (Dart s)
-> Getting
     (Endo (Vector (Dart s))) (Permutation (Dart s)) (Vector (Dart s))
-> Vector (Dart s)
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Vector (Dart s))
 -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> Permutation (Dart s)
-> Const (Endo (Vector (Dart s))) (Permutation (Dart s))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits((Vector (Vector (Dart s))
  -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
 -> Permutation (Dart s)
 -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
-> ((Vector (Dart s)
     -> Const (Endo (Vector (Dart s))) (Vector (Dart s)))
    -> Vector (Vector (Dart s))
    -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> Getting
     (Endo (Vector (Dart s))) (Permutation (Dart s)) (Vector (Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Vector (Dart s)))
-> Traversal'
     (Vector (Vector (Dart s))) (IxValue (Vector (Vector (Dart s))))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Vector (Dart s)))
i) Int
j


-- | Given a dart d that points into some vertex v, report the next dart in the
-- cyclic order around v.
--
-- running time: \(O(1)\)
prevIncidentEdge     :: Dart s -> PlanarGraph s w v e f -> Dart s
prevIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s
prevIncidentEdge Dart s
d PlanarGraph s w v e f
g = let perm :: Permutation (Dart s)
perm  = PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s w v e f)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s w v e f)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding
                           (Int
i,Int
j) = Permutation (Dart s) -> Dart s -> (Int, Int)
forall a. Enum a => Permutation a -> a -> (Int, Int)
lookupIdx Permutation (Dart s)
perm Dart s
d
                       in Vector (Dart s) -> Int -> Dart s
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
previous (Permutation (Dart s)
permPermutation (Dart s)
-> Getting
     (Endo (Vector (Dart s))) (Permutation (Dart s)) (Vector (Dart s))
-> Vector (Dart s)
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Vector (Dart s))
 -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> Permutation (Dart s)
-> Const (Endo (Vector (Dart s))) (Permutation (Dart s))
forall a1 a2.
Lens
  (Permutation a1)
  (Permutation a2)
  (Vector (Orbit a1))
  (Vector (Orbit a2))
orbits((Vector (Vector (Dart s))
  -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
 -> Permutation (Dart s)
 -> Const (Endo (Vector (Dart s))) (Permutation (Dart s)))
-> ((Vector (Dart s)
     -> Const (Endo (Vector (Dart s))) (Vector (Dart s)))
    -> Vector (Vector (Dart s))
    -> Const (Endo (Vector (Dart s))) (Vector (Vector (Dart s))))
-> Getting
     (Endo (Vector (Dart s))) (Permutation (Dart s)) (Vector (Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Vector (Dart s)))
-> Traversal'
     (Vector (Vector (Dart s))) (IxValue (Vector (Vector (Dart s))))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Vector (Dart s)))
i) Int
j


--------------------------------------------------------------------------------
-- * Access data

-- | General interface to accessing vertex data, dart data, and face data.
class HasDataOf g i where
  type DataOf g i
  -- | get the data associated with the value i.
  --
  -- running time: \(O(1)\) to read the data, \(O(n)\) to write it.
  dataOf :: i -> Lens' g (DataOf g i)

instance HasDataOf (PlanarGraph s w v e f) (VertexId s w) where
  type DataOf (PlanarGraph s w v e f) (VertexId s w) = v
  dataOf :: VertexId s w
-> Lens'
     (PlanarGraph s w v e f)
     (DataOf (PlanarGraph s w v e f) (VertexId s w))
dataOf (VertexId Int
i) = (Vector v -> f (Vector v))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
vertexData((Vector v -> f (Vector v))
 -> PlanarGraph s w v e f -> f (PlanarGraph s w v e f))
-> ((v -> f v) -> Vector v -> f (Vector v))
-> (v -> f v)
-> PlanarGraph s w v e f
-> f (PlanarGraph s w v e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Traversing (->) f (Vector v) (Vector v) v v
-> (v -> f v) -> Vector v -> f (Vector v)
forall (p :: * -> * -> *) (f :: * -> *) s t a.
(HasCallStack, Conjoined p, Functor f) =>
Traversing p f s t a a -> Over p f s t a a
singular (Index (Vector v) -> Traversal' (Vector v) (IxValue (Vector v))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector v)
i)

instance HasDataOf (PlanarGraph s w v e f) (Dart s) where
  type DataOf (PlanarGraph s w v e f) (Dart s) = e
  dataOf :: Dart s
-> Lens'
     (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s))
dataOf Dart s
d = (Vector e -> f (Vector e))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector e)
  (Vector e')
rawDartData((Vector e -> f (Vector e))
 -> PlanarGraph s w v e f -> f (PlanarGraph s w v e f))
-> ((e -> f e) -> Vector e -> f (Vector e))
-> (e -> f e)
-> PlanarGraph s w v e f
-> f (PlanarGraph s w v e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Traversing (->) f (Vector e) (Vector e) e e
-> (e -> f e) -> Vector e -> f (Vector e)
forall (p :: * -> * -> *) (f :: * -> *) s t a.
(HasCallStack, Conjoined p, Functor f) =>
Traversing p f s t a a -> Over p f s t a a
singular (Index (Vector e) -> Traversal' (Vector e) (IxValue (Vector e))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Index (Vector e) -> Traversal' (Vector e) (IxValue (Vector e)))
-> Index (Vector e) -> Traversal' (Vector e) (IxValue (Vector e))
forall a b. (a -> b) -> a -> b
$ Dart s -> Int
forall a. Enum a => a -> Int
fromEnum Dart s
d)

instance HasDataOf (PlanarGraph s w v e f) (FaceId s w) where
  type DataOf (PlanarGraph s w v e f) (FaceId s w) = f
  dataOf :: FaceId s w
-> Lens'
     (PlanarGraph s w v e f)
     (DataOf (PlanarGraph s w v e f) (FaceId s w))
dataOf (FaceId (VertexId Int
i)) = (Vector f -> f (Vector f))
-> PlanarGraph s w v e f -> f (PlanarGraph s w v e f)
forall k (s :: k) (w :: World) v e f f'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e f')
  (Vector f)
  (Vector f')
faceData((Vector f -> f (Vector f))
 -> PlanarGraph s w v e f -> f (PlanarGraph s w v e f))
-> ((f -> f f) -> Vector f -> f (Vector f))
-> (f -> f f)
-> PlanarGraph s w v e f
-> f (PlanarGraph s w v e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Traversing (->) f (Vector f) (Vector f) f f
-> (f -> f f) -> Vector f -> f (Vector f)
forall (p :: * -> * -> *) (f :: * -> *) s t a.
(HasCallStack, Conjoined p, Functor f) =>
Traversing p f s t a a -> Over p f s t a a
singular (Index (Vector f) -> Traversal' (Vector f) (IxValue (Vector f))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector f)
i)


-- | Data corresponding to the endpoints of the dart
endPointDataOf   :: Dart s -> Getter (PlanarGraph s w v e f) (v,v)
endPointDataOf :: Dart s -> Getter (PlanarGraph s w v e f) (v, v)
endPointDataOf Dart s
d = (PlanarGraph s w v e f -> (v, v))
-> Optic' (->) f (PlanarGraph s w v e f) (v, v)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to ((PlanarGraph s w v e f -> (v, v))
 -> Optic' (->) f (PlanarGraph s w v e f) (v, v))
-> (PlanarGraph s w v e f -> (v, v))
-> Optic' (->) f (PlanarGraph s w v e f) (v, v)
forall a b. (a -> b) -> a -> b
$ Dart s -> PlanarGraph s w v e f -> (v, v)
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> (v, v)
endPointData Dart s
d


-- | Data corresponding to the endpoints of the dart
--
-- running time: \(O(1)\)
endPointData     :: Dart s -> PlanarGraph s w v e f -> (v,v)
endPointData :: Dart s -> PlanarGraph s w v e f -> (v, v)
endPointData Dart s
d PlanarGraph s w v e f
g = let (VertexId s w
u,VertexId s w
v) = Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)
endPoints Dart s
d PlanarGraph s w v e f
g in (PlanarGraph s w v e f
gPlanarGraph s w v e f -> Getting v (PlanarGraph s w v e f) v -> v
forall s a. s -> Getting a s a -> a
^.VertexId s w
-> Lens'
     (PlanarGraph s w v e f)
     (DataOf (PlanarGraph s w v e f) (VertexId s w))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf VertexId s w
u, PlanarGraph s w v e f
gPlanarGraph s w v e f -> Getting v (PlanarGraph s w v e f) v -> v
forall s a. s -> Getting a s a -> a
^.VertexId s w
-> Lens'
     (PlanarGraph s w v e f)
     (DataOf (PlanarGraph s w v e f) (VertexId s w))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf VertexId s w
v)


--------------------------------------------------------------------------------
-- * The Dual graph

-- | The dual of this graph
--
-- >>> :{
--  let fromList = V.fromList
--      answer = fromList [ fromList [dart 0 "-1"]
--                        , fromList [dart 2 "+1",dart 4 "+1",dart 1 "-1",dart 0 "+1"]
--                        , fromList [dart 1 "+1",dart 3 "-1",dart 2 "-1"]
--                        , fromList [dart 4 "-1",dart 3 "+1",dart 5 "+1",dart 5 "-1"]
--                        ]
--  in (computeDual myGraph)^.embedding.orbits == answer
-- :}
-- True
--
-- running time: \(O(n)\).
computeDual :: forall s w v e f. PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual :: PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual = (DualOf (DualOf w) :~: w)
-> ((DualOf (DualOf w) ~ w) =>
    PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v)
-> PlanarGraph s w v e f
-> PlanarGraph s (DualOf w) f e v
forall k (a :: k) (b :: k) r. (a :~: b) -> ((a ~ b) => r) -> r
gcastWith DualOf (DualOf w) :~: w
proof (DualOf (DualOf w) ~ w) =>
PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
forall k (w :: World) (s :: k) v e f.
(DualOf (DualOf w) ~ w) =>
PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual'
  where
    proof :: DualOf (DualOf w) :~: w
    proof :: DualOf (DualOf w) :~: w
proof = DualOf (DualOf w) :~: w
forall (w :: World). DualOf (DualOf w) :~: w
dualDualIdentity

-- | Does the actual work for dualGraph
computeDual'   :: (DualOf (DualOf w) ~ w)
               => PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual' :: PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
computeDual' PlanarGraph s w v e f
g = PlanarGraph s (DualOf w) f e v
dualG
  where
    perm :: Permutation (Dart s)
perm  = PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting
     (Permutation (Dart s))
     (PlanarGraph s w v e f)
     (Permutation (Dart s))
-> Permutation (Dart s)
forall s a. s -> Getting a s a -> a
^.Getting
  (Permutation (Dart s))
  (PlanarGraph s w v e f)
  (Permutation (Dart s))
forall k (s :: k) (w :: World) v e f.
Getter (PlanarGraph s w v e f) (Permutation (Dart s))
embedding
    dualG :: PlanarGraph s (DualOf w) f e v
dualG = Permutation (Dart s)
-> Vector f
-> Vector e
-> Vector v
-> PlanarGraph s (DualOf (DualOf w)) v e f
-> PlanarGraph s (DualOf w) f e v
forall k (s :: k) (w :: World) v e f.
Permutation (Dart s)
-> Vector v
-> Vector e
-> Vector f
-> PlanarGraph s (DualOf w) f e v
-> PlanarGraph s w v e f
PlanarGraph (Vector (Dart s) -> (Dart s -> Dart s) -> Permutation (Dart s)
forall (v :: * -> *) a.
(Vector v a, Enum a, Eq a) =>
v a -> (a -> a) -> Permutation a
cycleRep (Permutation (Dart s) -> Vector (Dart s)
forall a. Permutation a -> Vector a
elems Permutation (Dart s)
perm) (Permutation (Dart s) -> Dart s -> Dart s
forall a. Enum a => Permutation a -> a -> a
apply Permutation (Dart s)
perm (Dart s -> Dart s) -> (Dart s -> Dart s) -> Dart s -> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin))
                        (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting (Vector f) (PlanarGraph s w v e f) (Vector f)
-> Vector f
forall s a. s -> Getting a s a -> a
^.Getting (Vector f) (PlanarGraph s w v e f) (Vector f)
forall k (s :: k) (w :: World) v e f f'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e f')
  (Vector f)
  (Vector f')
faceData)
                        (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting (Vector e) (PlanarGraph s w v e f) (Vector e)
-> Vector e
forall s a. s -> Getting a s a -> a
^.Getting (Vector e) (PlanarGraph s w v e f) (Vector e)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector e)
  (Vector e')
rawDartData)
                        (PlanarGraph s w v e f
gPlanarGraph s w v e f
-> Getting (Vector v) (PlanarGraph s w v e f) (Vector v)
-> Vector v
forall s a. s -> Getting a s a -> a
^.Getting (Vector v) (PlanarGraph s w v e f) (Vector v)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
vertexData)
                        PlanarGraph s w v e f
PlanarGraph s (DualOf (DualOf w)) v e f
g