{-# LANGUAGE RecordWildCards #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  Data.PlanarGraph.Immutable
-- Copyright   :  (C) David Himmelstrup
-- License     :  see the LICENSE file
-- Maintainer  :  David Himmelstrup
--
-- A graph is planar if it can be drawn on a flat piece of
-- paper without any crossing edges. More theory is explained on wikipedia:
-- <https://en.wikipedia.org/wiki/Planar_graph>
--
-- This module describes the connectivity of planar graphs without knowing
-- the 2D coordinates of each vertex. Algorithms that require the vertex
-- positions (such as planar point locators or mesh smoothers) have to store
-- that information somewhere else. Vertices are identified by dense, consecutive
-- integers and can be efficiently used with arrays or finite maps.
-- 
-- A planar graph consists of directed edges (also called half-edges or darts),
-- vertices, and faces. If a face lies on the outside of a set of vertices, this
-- face is called a boundary.
--
-- The simplest planar graph has just three vertices and three edges:
--
-- @'pgFromFaces' [[0,1,2]]@
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- The above pictures shows three vertices (named @'0'@, @'1'@, and @'2'@), a single face
-- (named @'0'@ with an underscore), and 6 half-edges (named @'0'@ through @'5'@).
-- Vertices, faces, and half-edges can be efficiently queried and traversed.
--
-- >>> let pg = pgFromFaces [[0,1,2]]
-- >>> pgFaces pg
-- [Face 0]
-- >>> faceBoundary (Face 0) pg
-- [Vertex 1,Vertex 2,Vertex 0]
--
--
-- == Planar graph examples:
--
-- Faces in planar graphs do not have to be triangular:
--
-- @'pgFromFaces' [[0,1,2,3]]@
--
-- <<docs/Data/PlanarGraph/planargraph-2506803680640023584.svg>>
--
-- Vertices may be interior or lie on a boundary:
--
-- @'pgFromFaces' [[0,1,2,3],[4,3,2,1]]@
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
-- >>> pgFaces pg
-- [Face 0,Face 1]
-- >>> vertexIsBoundary (Vertex 0) pg
-- True
-- >>> vertexIsBoundary (Vertex 2) pg
-- False
--
-- Planar graphs may have multiple boundaries. Notice how the area between vertices
-- @'1'@, @'2'@ and @'3'@ does not have a face ID:
--
-- @'pgFromFaces' [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]@
--
-- <<docs/Data/PlanarGraph/planargraph-2635031442529484236.compact.svg>>
--
-- >>> let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
-- >>> pgFaces pg
-- [Face 0,Face 1,Face 2,Face 3,Face 4,Face 5]
-- >>> pgBoundaries pg
-- [Boundary 0,Boundary 1]
-- >>> faceBoundary (Boundary 0) pg {- Outer boundary -}
-- [Vertex 0,Vertex 4,Vertex 5]
-- >>> faceBoundary (Boundary 1) pg {- Inner boundary -}
-- [Vertex 1,Vertex 2,Vertex 3]
--
-- Planar graphs may also have multiple unconnected components but they cannot be
-- automatically rendered:
--
-- >>> let pg = pgFromFaces [[0,1,2], [3,4,5]]
-- >>> pgFaces pg
-- [Face 0,Face 1]
-- >>> pgBoundaries pg
-- [Boundary 0,Boundary 1]
-- >>> faceBoundary (Boundary 0) pg
-- [Vertex 0,Vertex 1,Vertex 2]
-- >>> faceBoundary (Boundary 1) pg
-- [Vertex 3,Vertex 4,Vertex 5]
--
-- == Big-O Notation
--
-- When describing runtime complexity, @n@ refers to the size of the graph
-- (vertices, half-edges, faces, etcs). Some functions are output-sensitive
-- and use @k@ to indicate the amount of data consumed. For example,
-- 'vertexNeighbours' runs in \( O(k) \) and taking the first neighbour is therefore
-- an \( O(1) \) operation (because k=1).
--------------------------------------------------------------------------------
module Data.PlanarGraph.Immutable
  ( -- * Planar graphs
    PlanarGraph
  , pgFromFaces   -- :: [[VertexId]] -> PlanarGraph
  , pgFromFacesCV -- :: [CircularVector VertexId] -> PlanarGraph
  , pgVertices    -- :: PlanarGraph -> [Vertex]
  , pgEdges       -- :: PlanarGraph -> [Edge]
  , pgHalfEdges   -- :: PlanarGraph -> [HalfEdge]
  , pgFaces       -- :: PlanarGraph -> [Face]
  , pgBoundaries  -- :: PlanarGraph -> [Face]

    -- * Elements
    -- ** Vertices
  , Vertex(..)
  , vertexHalfEdge              -- :: Vertex -> PlanarGraph -> HalfEdge
  , vertexIsInterior            -- :: Vertex -> PlanarGraph -> Bool
  , vertexIsBoundary            -- :: Vertex -> PlanarGraph -> Bool
  , vertexOutgoingHalfEdges     -- :: Vertex -> PlanarGraph -> [HalfEdge]
  , vertexIncomingHalfEdges     -- :: Vertex -> PlanarGraph -> [HalfEdge]
  , vertexNeighbours            -- :: Vertex -> PlanarGraph -> [Vertex]

    -- ** Edges
  , Edge(..)
  , edgeHalfEdges        -- :: Edge -> (HalfEdge, HalfEdge)

    -- ** Half-edges
  , HalfEdge(..)
  , halfEdgeNext         -- :: HalfEdge -> PlanarGraph -> HalfEdge
  , halfEdgePrev         -- :: HalfEdge -> PlanarGraph -> HalfEdge
  , halfEdgeTwin         -- :: HalfEdge -> HalfEdge
  , halfEdgeNextOutgoing -- :: HalfEdge -> PlanarGraph -> HalfEdge
  , halfEdgeNextIncoming -- :: HalfEdge -> PlanarGraph -> HalfEdge
  , halfEdgeVertex       -- :: HalfEdge -> PlanarGraph -> Vertex
  , halfEdgeTailVertex   -- :: HalfEdge -> PlanarGraph -> Vertex
  , halfEdgeTipVertex    -- :: HalfEdge -> PlanarGraph -> Vertex
  , halfEdgeFace         -- :: HalfEdge -> PlanarGraph -> Face
  , halfEdgeIsInterior   -- :: HalfEdge -> PlanarGraph -> Bool
  , halfEdgeIsBoundary   -- :: HalfEdge -> PlanarGraph -> Bool

    -- ** Faces
  , Face(..), FaceId
  , faceMember     -- :: Face -> PlanarGraph -> Bool
  , faceId         -- :: Face -> FaceId
  , faceHalfEdge   -- :: Face -> PlanarGraph -> HalfEdge
  , faceIsInterior -- :: Face -> Bool
  , faceIsBoundary -- :: Face -> Bool
  , faceHalfEdges  -- :: Face -> PlanarGraph -> CircularVector HalfEdge
  , faceBoundary   -- :: Face -> PlanarGraph -> CircularVector Vertex

    -- * Mutation
  , pgMutate       -- :: PlanarGraph -> (forall s. Mut.PlanarGraph s -> ST s ()) -> PlanarGraph
  , pgCreate       -- :: (forall s. ST s (Mut.PlanarGraph s)) -> PlanarGraph
  , pgThaw         -- :: PlanarGraph -> ST s (Mut.PlanarGraph s)
  , pgFreeze       -- :: Mut.PlanarGraph s -> ST s PlanarGraph
  , pgUnsafeThaw   -- :: PlanarGraph -> ST s (Mut.PlanarGraph s)
  , pgUnsafeFreeze -- :: Mut.PlanarGraph s -> ST s PlanarGraph

    -- * Misc
  , tutteEmbedding -- :: PlanarGraph -> Vector.Vector (V2 Double)
  )
  where

import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Coerce
import           Data.Hashable
import           Data.PlanarGraph.Internal (FaceId, HalfEdgeId, VertexId)
import qualified Data.PlanarGraph.Internal as Mut
import qualified Data.PlanarGraph.Mutable  as Mut
import           Data.Proxy
import           Data.STRef
import           Data.Vector               (Vector)
import qualified Data.Vector               as Vector
import           Data.Vector.Circular      (CircularVector)
import qualified Data.Vector.Circular      as CV
import qualified Data.Vector.Mutable       as V
import           GHC.Exts
import           Linear.Matrix             (luSolve)
import           Linear.V
import           Linear.V2

-- import Debug.Trace

-------------------------------------------------------------------------------
-- Elements: Half-edges, vertices, faces.


-- | Half-edges are directed edges between vertices. All Half-edge have a twin
--   in the opposite direction. Half-edges have individual identity but are always
--   created in pairs.
newtype HalfEdge = HalfEdge {HalfEdge -> Int
halfEdgeId :: Int}
  deriving (HalfEdge -> HalfEdge -> Bool
(HalfEdge -> HalfEdge -> Bool)
-> (HalfEdge -> HalfEdge -> Bool) -> Eq HalfEdge
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: HalfEdge -> HalfEdge -> Bool
$c/= :: HalfEdge -> HalfEdge -> Bool
== :: HalfEdge -> HalfEdge -> Bool
$c== :: HalfEdge -> HalfEdge -> Bool
Eq, Int -> HalfEdge -> Int
HalfEdge -> Int
(Int -> HalfEdge -> Int) -> (HalfEdge -> Int) -> Hashable HalfEdge
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: HalfEdge -> Int
$chash :: HalfEdge -> Int
hashWithSalt :: Int -> HalfEdge -> Int
$chashWithSalt :: Int -> HalfEdge -> Int
Hashable)

instance Show HalfEdge where
  showsPrec :: Int -> HalfEdge -> ShowS
showsPrec Int
d (HalfEdge Int
v) = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"HalfEdge " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ShowS
forall a. Show a => a -> ShowS
shows Int
v

instance Read HalfEdge where
  readsPrec :: Int -> ReadS HalfEdge
readsPrec Int
d = Bool -> ReadS HalfEdge -> ReadS HalfEdge
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
app_prec) (ReadS HalfEdge -> ReadS HalfEdge)
-> ReadS HalfEdge -> ReadS HalfEdge
forall a b. (a -> b) -> a -> b
$ \String
r ->
      [ (Int -> HalfEdge
HalfEdge Int
v, String
t)
      | (String
"HalfEdge", String
s) <- ReadS String
lex String
r, (Int
v, String
t) <- ReadS Int
forall a. Read a => ReadS a
reads String
s ]
    where app_prec :: Int
app_prec = Int
10

-- | Edges are bidirectional and connect two vertices. No two edges are allowed
-- to cross.
newtype Edge = Edge {Edge -> Int
edgeId :: Int}
  deriving (Edge -> Edge -> Bool
(Edge -> Edge -> Bool) -> (Edge -> Edge -> Bool) -> Eq Edge
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Edge -> Edge -> Bool
$c/= :: Edge -> Edge -> Bool
== :: Edge -> Edge -> Bool
$c== :: Edge -> Edge -> Bool
Eq, Int -> Edge -> Int
Edge -> Int
(Int -> Edge -> Int) -> (Edge -> Int) -> Hashable Edge
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: Edge -> Int
$chash :: Edge -> Int
hashWithSalt :: Int -> Edge -> Int
$chashWithSalt :: Int -> Edge -> Int
Hashable)

instance Show Edge where
  showsPrec :: Int -> Edge -> ShowS
showsPrec Int
d (Edge Int
v) = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"Edge " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ShowS
forall a. Show a => a -> ShowS
shows Int
v

instance Read Edge where
  readsPrec :: Int -> ReadS Edge
readsPrec Int
d = Bool -> ReadS Edge -> ReadS Edge
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
app_prec) (ReadS Edge -> ReadS Edge) -> ReadS Edge -> ReadS Edge
forall a b. (a -> b) -> a -> b
$ \String
r ->
      [ (Int -> Edge
Edge Int
v, String
t)
      | (String
"Edge", String
s) <- ReadS String
lex String
r, (Int
v, String
t) <- ReadS Int
forall a. Read a => ReadS a
reads String
s ]
    where app_prec :: Int
app_prec = Int
10

-- | Graph vertices. For best performance, make sure to use consecutive numbers.
newtype Vertex = Vertex {Vertex -> Int
vertexId :: Int}
  deriving (Vertex -> Vertex -> Bool
(Vertex -> Vertex -> Bool)
-> (Vertex -> Vertex -> Bool) -> Eq Vertex
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Vertex -> Vertex -> Bool
$c/= :: Vertex -> Vertex -> Bool
== :: Vertex -> Vertex -> Bool
$c== :: Vertex -> Vertex -> Bool
Eq, Int -> Vertex -> Int
Vertex -> Int
(Int -> Vertex -> Int) -> (Vertex -> Int) -> Hashable Vertex
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
hash :: Vertex -> Int
$chash :: Vertex -> Int
hashWithSalt :: Int -> Vertex -> Int
$chashWithSalt :: Int -> Vertex -> Int
Hashable)

instance Show Vertex where
  showsPrec :: Int -> Vertex -> ShowS
showsPrec Int
d (Vertex Int
v) = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"Vertex " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ShowS
forall a. Show a => a -> ShowS
shows Int
v

instance Read Vertex where
  readsPrec :: Int -> ReadS Vertex
readsPrec Int
d = Bool -> ReadS Vertex -> ReadS Vertex
forall a. Bool -> ReadS a -> ReadS a
readParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
app_prec) (ReadS Vertex -> ReadS Vertex) -> ReadS Vertex -> ReadS Vertex
forall a b. (a -> b) -> a -> b
$ \String
r ->
      [ (Int -> Vertex
Vertex Int
v, String
t)
      | (String
"Vertex", String
s) <- ReadS String
lex String
r, (Int
v, String
t) <- ReadS Int
forall a. Read a => ReadS a
reads String
s ]
    where app_prec :: Int
app_prec = Int
10

-- | Faces are the areas divided by edges. If a face is not surrounded by a set of vertices,
--   it is called a boundary.
data Face = Face FaceId | Boundary FaceId
  deriving (Face -> Face -> Bool
(Face -> Face -> Bool) -> (Face -> Face -> Bool) -> Eq Face
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Face -> Face -> Bool
$c/= :: Face -> Face -> Bool
== :: Face -> Face -> Bool
$c== :: Face -> Face -> Bool
Eq, ReadPrec [Face]
ReadPrec Face
Int -> ReadS Face
ReadS [Face]
(Int -> ReadS Face)
-> ReadS [Face] -> ReadPrec Face -> ReadPrec [Face] -> Read Face
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Face]
$creadListPrec :: ReadPrec [Face]
readPrec :: ReadPrec Face
$creadPrec :: ReadPrec Face
readList :: ReadS [Face]
$creadList :: ReadS [Face]
readsPrec :: Int -> ReadS Face
$creadsPrec :: Int -> ReadS Face
Read, Int -> Face -> ShowS
[Face] -> ShowS
Face -> String
(Int -> Face -> ShowS)
-> (Face -> String) -> ([Face] -> ShowS) -> Show Face
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Face] -> ShowS
$cshowList :: [Face] -> ShowS
show :: Face -> String
$cshow :: Face -> String
showsPrec :: Int -> Face -> ShowS
$cshowsPrec :: Int -> Face -> ShowS
Show)

-------------------------------------------------------------------------------
-- Planar graph

-- PlanarGraphs have vertices, edges, and faces.
-- Invariant: The half-edge of a boundary vertex is interior, twin is exterior.

-- FIXME: Use STRefU ?
-- PlanarGraph with 0 vertices: No edges, no vertices, no faces.
-- PlanarGraph with 1 vertex: No edges, no interior faces.
-- PlanarGraph with 2 vertices: One edge, no interior faces.
-- PlanarGraph with 3+ vertices: Usual properties hold.
-- | Immutable planar graph.
data PlanarGraph = PlanarGraph
  { PlanarGraph -> Vector Int
pgHalfEdgeNext   :: !(Vector HalfEdgeId) -- HalfEdge indexed
  , PlanarGraph -> Vector Int
pgHalfEdgePrev   :: !(Vector HalfEdgeId) -- HalfEdge indexed
  , PlanarGraph -> Vector Int
pgHalfEdgeVertex :: !(Vector VertexId)   -- HalfEdge indexed
  , PlanarGraph -> Vector Int
pgHalfEdgeFace   :: !(Vector FaceId)     -- HalfEdge indexed
  , PlanarGraph -> Vector Int
pgVertexEdges    :: !(Vector HalfEdgeId) -- Vertex indexed
  , PlanarGraph -> Vector Int
pgFaceEdges      :: !(Vector HalfEdgeId) -- Face indexed
  , PlanarGraph -> Vector Int
pgBoundaryEdges  :: !(Vector HalfEdgeId) -- Boundary faces
  } deriving PlanarGraph -> PlanarGraph -> Bool
(PlanarGraph -> PlanarGraph -> Bool)
-> (PlanarGraph -> PlanarGraph -> Bool) -> Eq PlanarGraph
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PlanarGraph -> PlanarGraph -> Bool
$c/= :: PlanarGraph -> PlanarGraph -> Bool
== :: PlanarGraph -> PlanarGraph -> Bool
$c== :: PlanarGraph -> PlanarGraph -> Bool
Eq

panic :: String -> String -> a
panic :: String -> String -> a
panic String
tag String
msg = String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
"Data.PlanarGraph.Immutable." String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
tag String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
": " String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
msg


-- $setup
--
-- >>> hash $ pgFromFaces [[0,1,2]]
-- 2959979592048325618
-- >>> hash $ pgFromFaces [[1,2,3]]
-- 2486673127436488352
-- >>> hash $ pgFromFaces [[0,1,2,3]]
-- 2506803680640023584
-- >>> hash $ pgFromFaces [[0,1,2,3],[4,3,2,1]]
-- 1711135548958680232
--

-- | \( O(n \log n) \)
--
--   Construct a planar graph from a list of faces. Vertices are assumed to be dense
--   (ie without gaps) but this only affects performance, not correctness. Memory
--   usage is defined by the largest vertex ID. That means @'pgFromFaces' [[0,1,2]]@
--   has the same connectivity as @'pgFromFaces' [[7,8,9]]@ but uses three times less
--   memory.
--
-- ==== __Examples:__
-- @
-- 'pgFromFaces' [[0,1,2]]
-- @
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- @
-- 'pgFromFaces' [[0,1,2,3]]
-- @
-- <<docs/Data/PlanarGraph/planargraph-2506803680640023584.svg>>
--
-- @
-- 'pgFromFaces' [[1,2,3]]
-- @
-- <<docs/Data/PlanarGraph/planargraph-2486673127436488352.svg>>
--
-- @since 0.12.0.0
pgFromFaces :: [[VertexId]] -> PlanarGraph
pgFromFaces :: [[Int]] -> PlanarGraph
pgFromFaces = [CircularVector Int] -> PlanarGraph
pgFromFacesCV ([CircularVector Int] -> PlanarGraph)
-> ([[Int]] -> [CircularVector Int]) -> [[Int]] -> PlanarGraph
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Int] -> CircularVector Int) -> [[Int]] -> [CircularVector Int]
forall a b. (a -> b) -> [a] -> [b]
map [Int] -> CircularVector Int
forall a. [a] -> CircularVector a
CV.unsafeFromList

-- | \( O(n \log n) \)
--
--   Construct a planar graph from a list of faces. This is a slightly more
--   efficient version of 'pgFromFacesCV'.
-- 
-- @since 0.12.0.0
pgFromFacesCV :: [CircularVector VertexId] -> PlanarGraph
pgFromFacesCV :: [CircularVector Int] -> PlanarGraph
pgFromFacesCV [CircularVector Int]
faces = (forall s. ST s (PlanarGraph s)) -> PlanarGraph
pgCreate ((forall s. ST s (PlanarGraph s)) -> PlanarGraph)
-> (forall s. ST s (PlanarGraph s)) -> PlanarGraph
forall a b. (a -> b) -> a -> b
$ [CircularVector Int] -> ST s (PlanarGraph s)
forall s. [CircularVector Int] -> ST s (PlanarGraph s)
Mut.pgFromFacesCV [CircularVector Int]
faces

-- fromFaces' :: Int -> Int -> Int -> [CircularVector VertexId] -> ST s (PlanarGraph)
-- fromFaces' nFaces nHalfEdges maxVertexId faces = do
--   undefined

-- dualTree :: Face -> ST s (Tree Face)
-- dualTree = undefined

instance Hashable PlanarGraph where
  hashWithSalt :: Int -> PlanarGraph -> Int
hashWithSalt Int
salt = Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (Int -> Int) -> (PlanarGraph -> Int) -> PlanarGraph -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarGraph -> Int
pgHash
  hash :: PlanarGraph -> Int
hash = PlanarGraph -> Int
pgHash

-- | O(n)
-- 
-- @since 0.12.0.0
pgHash :: PlanarGraph -> Int
pgHash :: PlanarGraph -> Int
pgHash PlanarGraph
pg =
  let loop :: [Int] -> Int -> Int
loop [] Int
salt = Int
salt
      loop (Int
edgeId:[Int]
rest) Int
salt =
        let he :: HalfEdge
he = Int -> HalfEdge
HalfEdge (Int
edgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2)
            vTail :: Vertex
vTail = HalfEdge -> PlanarGraph -> Vertex
halfEdgeTailVertex HalfEdge
he PlanarGraph
pg
            vTip :: Vertex
vTip = HalfEdge -> PlanarGraph -> Vertex
halfEdgeTipVertex HalfEdge
he PlanarGraph
pg
        in [Int] -> Int -> Int
loop [Int]
rest (Int -> (Vertex, Vertex) -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (Vertex
vTail, Vertex
vTip))
  in Int -> Int
forall a. Num a => a -> a
abs (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ [Int] -> Int -> Int
loop [Int
0..Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg)Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div`Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] Int
0

-------------------------------------------------------------------------------
-- Vertices

-- | O(1)
vertexCheck :: String -> Vertex -> PlanarGraph -> a -> a
vertexCheck :: String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
tag (Vertex Int
vId) PlanarGraph
pg a
_val
  | Int
vId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg) Bool -> Bool -> Bool
|| Int
vId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Out-of-bounds vertex access: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
vId)
  | Bool -> Bool
not (HalfEdge -> Bool
halfEdgeIsValid (Int -> HalfEdge
HalfEdge (PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
vId))) =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Tried to access deleted vertex: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
vId)
vertexCheck String
_tag Vertex
_face PlanarGraph
_pg a
val = a
val

-- | \( O(k) \)
--   
--   List all vertices in a graph.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> pgVertices pg
-- [Vertex 0,Vertex 1,Vertex 2]
--
-- @since 0.12.0.0
pgVertices :: PlanarGraph -> [Vertex]
pgVertices :: PlanarGraph -> [Vertex]
pgVertices PlanarGraph
pg =
  [ Int -> Vertex
Vertex Int
v
  | Int
v <- [Int
0 .. Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg)Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 ]
  , HalfEdge -> Bool
halfEdgeIsValid (Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
v)
  ]

-- -- | \( O(1) \)
-- vertexFromId :: VertexId -> Vertex
-- vertexFromId vId = Vertex vId

-- -- | \( O(1) \)
-- vertexId :: Vertex -> VertexId
-- vertexId (Vertex vId) = vId

-- $hidden
--
-- >>> hash $ pgFromFaces [[0,1,2]]
-- 2959979592048325618

-- | \( O(1) \)
--
--   Each vertex has an assigned half-edge with the following properties:
--
--   @'halfEdgeVertex' ('vertexHalfEdge' vertex pg) pg = vertex@
--
--   @'faceIsInterior' ('halfEdgeFace' ('vertexHalfEdge' vertex pg) pg) = True@
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> vertexHalfEdge (Vertex 0) pg
-- HalfEdge 4
--
-- >>> vertexHalfEdge (Vertex 1) pg
-- HalfEdge 0
--
-- >>> vertexHalfEdge (Vertex 6) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: 6
-- ...
--
-- >>> vertexHalfEdge (Vertex (-10)) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: -10
-- ...
--
-- >>> halfEdgeVertex (vertexHalfEdge (Vertex 2) pg) pg
-- Vertex 2
--
-- >>> halfEdgeFace (vertexHalfEdge (Vertex 0) pg) pg
-- Face 0
--
-- @since 0.12.0.0
vertexHalfEdge :: Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge :: Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexHalfEdge" Vertex
vertex PlanarGraph
pg Bool
False = HalfEdge
forall a. HasCallStack => a
undefined
vertexHalfEdge (Vertex Int
vId) PlanarGraph
pg = Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
vId


-- $hidden
--
-- >>> hash $ pgFromFaces [[0,1,2,3],[4,3,2,1]]
-- 1711135548958680232

-- | \( O(1) \)
--
--   Returns @True@ iff the vertex lies on a boundary.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> vertexIsBoundary (Vertex 0) pg
-- True
--
-- >>> vertexIsBoundary (Vertex 2) pg
-- False
--
-- >>> vertexIsBoundary (Vertex 4) pg
-- True
--
-- >>> vertexIsBoundary (Vertex 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexIsBoundary: Out-of-bounds vertex access: 12
-- ...
--
-- @since 0.12.0.0
vertexIsBoundary :: Vertex -> PlanarGraph -> Bool
vertexIsBoundary :: Vertex -> PlanarGraph -> Bool
vertexIsBoundary Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexIsBoundary" Vertex
vertex PlanarGraph
pg Bool
False = Bool
forall a. HasCallStack => a
undefined
vertexIsBoundary Vertex
vertex PlanarGraph
pg =
    Face -> Bool
faceIsBoundary (Face -> Bool) -> Face -> Bool
forall a b. (a -> b) -> a -> b
$ HalfEdge -> PlanarGraph -> Face
halfEdgeFace (HalfEdge -> HalfEdge
halfEdgeTwin (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge Vertex
vertex PlanarGraph
pg) PlanarGraph
pg

-- | \( O(1) \)
--
--   Returns @True@ iff the vertex is interior, ie. does not lie on a boundary.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> vertexIsInterior (Vertex 0) pg
-- False
--
-- >>> vertexIsInterior (Vertex 2) pg
-- True
--
-- >>> vertexIsInterior (Vertex 4) pg
-- False
--
-- >>> vertexIsInterior (Vertex 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexIsInterior: Out-of-bounds vertex access: 12
-- ...
--
-- @since 0.12.0.0
vertexIsInterior :: Vertex -> PlanarGraph -> Bool
vertexIsInterior :: Vertex -> PlanarGraph -> Bool
vertexIsInterior Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexIsInterior" Vertex
vertex PlanarGraph
pg Bool
False = Bool
forall a. HasCallStack => a
undefined
vertexIsInterior Vertex
vertex PlanarGraph
pg = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> Bool
vertexIsBoundary Vertex
vertex PlanarGraph
pg

-- | \( O(k) \)
--
--   Query outgoing half-edges from a given vertex in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> vertexOutgoingHalfEdges (Vertex 1) pg
-- [HalfEdge 0,HalfEdge 11,HalfEdge 3]
--
-- Each half-edge will point out from the origin vertex:
--
-- >>> map (`halfEdgeVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg
-- [Vertex 1,Vertex 1,Vertex 1]
--
-- >>> map (`halfEdgeTipVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg
-- [Vertex 0,Vertex 4,Vertex 2]
--
-- >>> vertexOutgoingHalfEdges (Vertex 2) pg
-- [HalfEdge 2,HalfEdge 5]
--
-- >>> vertexOutgoingHalfEdges (Vertex 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexOutgoingHalfEdges: Out-of-bounds vertex access: 12
-- ...
--
-- @since 0.12.0.0
vertexOutgoingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]
vertexOutgoingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]
vertexOutgoingHalfEdges Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexOutgoingHalfEdges" Vertex
vertex PlanarGraph
pg Bool
False = [HalfEdge]
forall a. HasCallStack => a
undefined
vertexOutgoingHalfEdges Vertex
vertex PlanarGraph
pg = HalfEdge
first HalfEdge -> [HalfEdge] -> [HalfEdge]
forall a. a -> [a] -> [a]
: (forall b. (HalfEdge -> b -> b) -> b -> b) -> [HalfEdge]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (HalfEdge -> (HalfEdge -> b -> b) -> b -> b
forall b. HalfEdge -> (HalfEdge -> b -> b) -> b -> b
g (HalfEdge -> HalfEdge
advance HalfEdge
first))
  where
    advance :: HalfEdge -> HalfEdge
advance HalfEdge
he = HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext (HalfEdge -> HalfEdge
halfEdgeTwin HalfEdge
he) PlanarGraph
pg
    first :: HalfEdge
first = Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge Vertex
vertex PlanarGraph
pg
    g :: HalfEdge -> (HalfEdge -> b -> b) -> b -> b
    g :: HalfEdge -> (HalfEdge -> b -> b) -> b -> b
g HalfEdge
he HalfEdge -> b -> b
cons b
nil
      | HalfEdge
he HalfEdge -> HalfEdge -> Bool
forall a. Eq a => a -> a -> Bool
== HalfEdge
first = b
nil
      | Bool
otherwise   = HalfEdge -> b -> b
cons HalfEdge
he (HalfEdge -> (HalfEdge -> b -> b) -> b -> b
forall b. HalfEdge -> (HalfEdge -> b -> b) -> b -> b
g (HalfEdge -> HalfEdge
advance HalfEdge
he) HalfEdge -> b -> b
cons b
nil)

-- $hidden
--
-- >>> hash $ pgFromFaces [[0,1,2,3],[4,3,2,1]]
-- 1711135548958680232

-- | \( O(k) \)
--
--   Query incoming half-edges from a given vertex in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> vertexIncomingHalfEdges (Vertex 1) pg
-- [HalfEdge 1,HalfEdge 10,HalfEdge 2]
--
-- >>> map (`halfEdgeVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg
-- [Vertex 0,Vertex 4,Vertex 2]
--
-- >>> map (`halfEdgeTipVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg
-- [Vertex 1,Vertex 1,Vertex 1]
--
-- >>> vertexIncomingHalfEdges (Vertex 2) pg
-- [HalfEdge 3,HalfEdge 4]
--
-- >>> vertexIncomingHalfEdges (Vertex 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexIncomingHalfEdges: Out-of-bounds vertex access: 12
-- ...
--
-- @since 0.12.0.0
vertexIncomingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]
vertexIncomingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]
vertexIncomingHalfEdges Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexIncomingHalfEdges" Vertex
vertex PlanarGraph
pg Bool
False = [HalfEdge]
forall a. HasCallStack => a
undefined
vertexIncomingHalfEdges Vertex
vertex PlanarGraph
pg = (HalfEdge -> HalfEdge) -> [HalfEdge] -> [HalfEdge]
forall a b. (a -> b) -> [a] -> [b]
map HalfEdge -> HalfEdge
halfEdgeTwin ([HalfEdge] -> [HalfEdge]) -> [HalfEdge] -> [HalfEdge]
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> [HalfEdge]
vertexOutgoingHalfEdges Vertex
vertex PlanarGraph
pg

-- | \( O(k) \)
--
--   Query vertex neighbours in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> vertexNeighbours (Vertex 0) pg
-- [Vertex 3,Vertex 1]
--
-- >>> vertexNeighbours (Vertex 1) pg
-- [Vertex 0,Vertex 4,Vertex 2]
--
-- >>> vertexNeighbours (Vertex 2) pg
-- [Vertex 1,Vertex 3]
--
-- >>> vertexNeighbours (Vertex 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.vertexNeighbours: Out-of-bounds vertex access: 12
-- ...
--
-- @since 0.12.0.0
vertexNeighbours :: Vertex -> PlanarGraph -> [Vertex]
vertexNeighbours :: Vertex -> PlanarGraph -> [Vertex]
vertexNeighbours Vertex
vertex PlanarGraph
pg | String -> Vertex -> PlanarGraph -> Bool -> Bool
forall a. String -> Vertex -> PlanarGraph -> a -> a
vertexCheck String
"vertexNeighbours" Vertex
vertex PlanarGraph
pg Bool
False = [Vertex]
forall a. HasCallStack => a
undefined
vertexNeighbours Vertex
vertex PlanarGraph
pg = (HalfEdge -> Vertex) -> [HalfEdge] -> [Vertex]
forall a b. (a -> b) -> [a] -> [b]
map (HalfEdge -> PlanarGraph -> Vertex
`halfEdgeVertex` PlanarGraph
pg) ([HalfEdge] -> [Vertex]) -> [HalfEdge] -> [Vertex]
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> [HalfEdge]
vertexIncomingHalfEdges Vertex
vertex PlanarGraph
pg

-- vertexAdjacentVertices :: Vertex -> PlanarGraph -> [Vertex]
-- vertexAdjacentFaces :: Vertex -> PlanarGraph -> [Face]

-------------------------------------------------------------------------------
-- Edges

-- | \( O(k) \)
--   
--   List all edges in a graph.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> pgEdges pg
-- [Edge 0,Edge 1,Edge 2]
--
-- >>> map edgeHalfEdges $ pgEdges pg
-- [(HalfEdge 0,HalfEdge 1),(HalfEdge 2,HalfEdge 3),(HalfEdge 4,HalfEdge 5)]
--
-- @since 0.12.0.0
pgEdges :: PlanarGraph -> [Edge]
pgEdges :: PlanarGraph -> [Edge]
pgEdges PlanarGraph
pg =
  [ Int -> Edge
Edge Int
e
  | Int
e <- [Int
0 .. Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]
  , let he :: Int
he = Int
eInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2
  , HalfEdge -> Bool
halfEdgeIsValid (Int -> HalfEdge
HalfEdge Int
he)
  ]

-- | \( O(1) \)
--
--   Split a bidirectional edge into directed half-edges.
--
-- @since 0.12.0.0
edgeHalfEdges :: Edge -> (HalfEdge, HalfEdge)
edgeHalfEdges :: Edge -> (HalfEdge, HalfEdge)
edgeHalfEdges (Edge Int
e) = (Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ Int
eInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2, Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ Int
eInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)

-------------------------------------------------------------------------------
-- Half-edges

-- | O(1)
halfEdgeCheck :: String -> HalfEdgeId -> PlanarGraph -> a -> a
halfEdgeCheck :: String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
tag Int
eId PlanarGraph
pg a
_val
  | Int
eId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgHalfEdgeVertex PlanarGraph
pg) Bool -> Bool -> Bool
|| Int
eId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Out-of-bounds half-edge access: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
eId)
  | PlanarGraph -> Vector Int
pgHalfEdgeVertex PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
eId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Tried to access deleted half-edge: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
eId)
halfEdgeCheck String
_tag Int
_face PlanarGraph
_pg a
val = a
val

-- | \( O(k) \)
--   
--   List all half-edges in a graph.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> pgHalfEdges pg
-- [HalfEdge 0,HalfEdge 1,HalfEdge 2,HalfEdge 3,HalfEdge 4,HalfEdge 5]
--
-- @since 0.12.0.0
pgHalfEdges :: PlanarGraph -> [HalfEdge]
pgHalfEdges :: PlanarGraph -> [HalfEdge]
pgHalfEdges PlanarGraph
pg =
  [ HalfEdge
he
  | HalfEdge
he <- (Int -> HalfEdge) -> [Int] -> [HalfEdge]
forall a b. (a -> b) -> [a] -> [b]
map Int -> HalfEdge
HalfEdge [Int
0 .. Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg)Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 ]
  , HalfEdge -> Bool
halfEdgeIsValid HalfEdge
he
  ]


-- | O(1)
--
-- @since 0.12.0.0
halfEdgeIsValid :: HalfEdge -> Bool
halfEdgeIsValid :: HalfEdge -> Bool
halfEdgeIsValid (HalfEdge Int
eId) = Int
eId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0

-- -- | O(1)
-- halfEdgeFromId :: HalfEdgeId -> HalfEdge
-- halfEdgeFromId eId = HalfEdge eId

-- -- | O(1)
-- halfEdgeId :: HalfEdge -> HalfEdgeId
-- halfEdgeId (HalfEdge eId) = eId

-- $hidden
--
-- >>> hash $ pgFromFaces [[0,1,2,3],[4,3,2,1]]
-- 1711135548958680232

-- | \( O(1) \)
--
--   Query the half-edge in the pointed direction. Internal half-edges
--   are arranged clockwise and external half-edges go counter-clockwise.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> halfEdgeNext (HalfEdge 4) pg {- clockwise -}
-- HalfEdge 2
--
-- >>> halfEdgeNext (HalfEdge 3) pg {- clockwise -}
-- HalfEdge 5
--
-- >>> halfEdgeNext (HalfEdge 1) pg {- counter-clockwise -}
-- HalfEdge 11
--
-- >>> halfEdgeNext (HalfEdge 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeNext: Out-of-bounds half-edge access: 12
-- ...
--
-- @since 0.12.0.0
halfEdgeNext :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext (HalfEdge Int
eId) PlanarGraph
pg = String -> Int -> PlanarGraph -> HalfEdge -> HalfEdge
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeNext" Int
eId PlanarGraph
pg (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$
  Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
eId

-- | \( O(1) \)
--
--   Query the half-edge opposite the pointed direction. This means counter-clockwise
--   for internal half-edges and clockwise for external half-edges.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> halfEdgePrev (HalfEdge 4) pg {- counter-clockwise -}
-- HalfEdge 6
--
-- >>> halfEdgePrev (HalfEdge 3) pg {- counter-clockwise -}
-- HalfEdge 10
--
-- >>> halfEdgePrev (HalfEdge 1) pg {- clockwise -}
-- HalfEdge 7
--
-- >>> halfEdgePrev (HalfEdge 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgePrev: Out-of-bounds half-edge access: 12
-- ...
--
-- @since 0.12.0.0
halfEdgePrev :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgePrev :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgePrev (HalfEdge Int
eId) PlanarGraph
pg = String -> Int -> PlanarGraph -> HalfEdge -> HalfEdge
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgePrev" Int
eId PlanarGraph
pg (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$
  Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgePrev PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
eId

-- | \( O(1) \)
--
--   Next half-edge with the same vertex in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- @HalfEdge 0@ is poiting out from @Vertex 1@. Moving counter-clockwise
-- around @Vertex 1@ yields @HalfEdge 11@ and @HalfEdge 3@.
--
-- >>> halfEdgeNextOutgoing (HalfEdge 0) pg
-- HalfEdge 11
--
-- >>> halfEdgeNextOutgoing (HalfEdge 11) pg
-- HalfEdge 3
--
-- >>> halfEdgeNextOutgoing (HalfEdge 3) pg
-- HalfEdge 0
--
-- >>> halfEdgeNextOutgoing (HalfEdge 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeNextOutgoing: Out-of-bounds half-edge access: 12
-- ...
--
-- @since 0.12.0.0
halfEdgeNextOutgoing :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNextOutgoing :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNextOutgoing HalfEdge
e PlanarGraph
pg = String -> Int -> PlanarGraph -> HalfEdge -> HalfEdge
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeNextOutgoing" (HalfEdge -> Int
halfEdgeId HalfEdge
e) PlanarGraph
pg (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$
  HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext (HalfEdge -> HalfEdge
halfEdgeTwin HalfEdge
e) PlanarGraph
pg

-- | \( O(1) \)
--
--   Next half-edge with the same vertex in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- @HalfEdge 6@ is poiting towards @Vertex 3@. Moving clockwise
-- around @Vertex 3@ yields @HalfEdge 11@ and @HalfEdge 3@.
--
-- >>> halfEdgeNextIncoming (HalfEdge 6) pg
-- HalfEdge 5
--
-- >>> halfEdgeNextIncoming (HalfEdge 5) pg
-- HalfEdge 9
--
-- >>> halfEdgeNextIncoming (HalfEdge 9) pg
-- HalfEdge 6
--
-- >>> halfEdgeNextIncoming (HalfEdge 12) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeNextIncoming: Out-of-bounds half-edge access: 12
-- ...
--
-- @since 0.12.0.0
halfEdgeNextIncoming :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNextIncoming :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNextIncoming HalfEdge
e PlanarGraph
pg = String -> Int -> PlanarGraph -> HalfEdge -> HalfEdge
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeNextIncoming" (HalfEdge -> Int
halfEdgeId HalfEdge
e) PlanarGraph
pg (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$
  HalfEdge -> HalfEdge
halfEdgeTwin (HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext HalfEdge
e PlanarGraph
pg)

-- | \( O(1) \)
--
-- @
-- 'halfEdgeTwin' . 'halfEdgeTwin' == id
-- @
--
-- @since 0.12.0.0
halfEdgeTwin :: HalfEdge -> HalfEdge
halfEdgeTwin :: HalfEdge -> HalfEdge
halfEdgeTwin (HalfEdge Int
idx) = Int -> HalfEdge
HalfEdge (Int
idx Int -> Int -> Int
forall a. Bits a => a -> a -> a
`xor` Int
1)


-- | \( O(1) \)
--
--   Tail-end of a half-edge. Synonym of 'halfEdgeTailVertex'.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeVertex (HalfEdge 1) pg
-- Vertex 0
--
-- >>> halfEdgeVertex (HalfEdge 2) pg
-- Vertex 2
--
-- >>> halfEdgeVertex (HalfEdge 6) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeVertex: Out-of-bounds half-edge access: 6
-- ...
--
-- @since 0.12.0.0
halfEdgeVertex :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeVertex :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeVertex (HalfEdge Int
idx) PlanarGraph
pg = String -> Int -> PlanarGraph -> Vertex -> Vertex
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeVertex" Int
idx PlanarGraph
pg (Vertex -> Vertex) -> Vertex -> Vertex
forall a b. (a -> b) -> a -> b
$
  Int -> Vertex
Vertex (Int -> Vertex) -> Int -> Vertex
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeVertex PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
idx

-- | O(1)
--
--   Tail-end of a half-edge. Synonym of 'halfEdgeVertex'.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeTailVertex (HalfEdge 1) pg
-- Vertex 0
--
-- >>> halfEdgeTailVertex (HalfEdge 2) pg
-- Vertex 2
--
-- @since 0.12.0.0
halfEdgeTailVertex :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeTailVertex :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeTailVertex HalfEdge
e PlanarGraph
pg = HalfEdge -> PlanarGraph -> Vertex
halfEdgeVertex HalfEdge
e PlanarGraph
pg

-- | O(1)
--
--   Tip-end of a half-edge. This is the tail-end vertex of the twin half-edge.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeTipVertex (HalfEdge 1) pg
-- Vertex 1
--
-- >>> halfEdgeTipVertex (HalfEdge 5) pg
-- Vertex 0
--
-- @since 0.12.0.0
halfEdgeTipVertex  :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeTipVertex :: HalfEdge -> PlanarGraph -> Vertex
halfEdgeTipVertex HalfEdge
e PlanarGraph
pg = HalfEdge -> PlanarGraph -> Vertex
halfEdgeVertex (HalfEdge -> HalfEdge
halfEdgeTwin HalfEdge
e) PlanarGraph
pg

-- $hidden
--
-- >>> hash $ pgFromFaces [[0,1,2]]
-- 2959979592048325618

-- | \( O(1) \)
--
--   Query the face of a half-edge.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeFace (HalfEdge 0) pg
-- Face 0
--
-- >>> halfEdgeFace (HalfEdge 1) pg
-- Boundary 0
--
-- >>> halfEdgeFace (HalfEdge 6) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeFace: Out-of-bounds half-edge access: 6
-- ...
--
-- @since 0.12.0.0
halfEdgeFace       :: HalfEdge -> PlanarGraph -> Face
halfEdgeFace :: HalfEdge -> PlanarGraph -> Face
halfEdgeFace (HalfEdge Int
eId) PlanarGraph
pg = String -> Int -> PlanarGraph -> Face -> Face
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeFace" Int
eId PlanarGraph
pg (Face -> Face) -> Face -> Face
forall a b. (a -> b) -> a -> b
$
  Int -> Face
faceFromId (Int -> Face) -> Int -> Face
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeFace PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
eId

-- | \( O(1) \)
--
--   Check if a half-edge's face is on a boundary.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeIsBoundary (HalfEdge 0) pg
-- False
--
-- >>> halfEdgeIsBoundary (HalfEdge 1) pg
-- True
--
-- >>> halfEdgeIsBoundary (HalfEdge 2) pg
-- False
--
-- >>> halfEdgeIsBoundary (HalfEdge 3) pg
-- True
--
-- >>> halfEdgeIsBoundary (HalfEdge 6) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeIsBoundary: Out-of-bounds half-edge access: 6
-- ...
--
-- @since 0.12.0.0
halfEdgeIsBoundary :: HalfEdge -> PlanarGraph -> Bool
halfEdgeIsBoundary :: HalfEdge -> PlanarGraph -> Bool
halfEdgeIsBoundary HalfEdge
edge PlanarGraph
pg = String -> Int -> PlanarGraph -> Bool -> Bool
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeIsBoundary" (HalfEdge -> Int
halfEdgeId HalfEdge
edge) PlanarGraph
pg (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$
  Face -> Bool
faceIsBoundary (Face -> Bool) -> Face -> Bool
forall a b. (a -> b) -> a -> b
$ HalfEdge -> PlanarGraph -> Face
halfEdgeFace HalfEdge
edge PlanarGraph
pg

-- | \( O(1) \)
--
--   Check if a half-edge's face is interior.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> halfEdgeIsInterior (HalfEdge 0) pg
-- True
--
-- >>> halfEdgeIsInterior (HalfEdge 1) pg
-- False
--
-- >>> halfEdgeIsInterior (HalfEdge 2) pg
-- True
--
-- >>> halfEdgeIsInterior (HalfEdge 3) pg
-- False
--
-- >>> halfEdgeIsInterior (HalfEdge 6) pg
-- ... Exception: Data.PlanarGraph.Immutable.halfEdgeIsInterior: Out-of-bounds half-edge access: 6
-- ...
--
-- @since 0.12.0.0
halfEdgeIsInterior :: HalfEdge -> PlanarGraph -> Bool
halfEdgeIsInterior :: HalfEdge -> PlanarGraph -> Bool
halfEdgeIsInterior HalfEdge
edge PlanarGraph
pg = String -> Int -> PlanarGraph -> Bool -> Bool
forall a. String -> Int -> PlanarGraph -> a -> a
halfEdgeCheck String
"halfEdgeIsInterior" (HalfEdge -> Int
halfEdgeId HalfEdge
edge) PlanarGraph
pg (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$
  Face -> Bool
faceIsInterior (Face -> Bool) -> Face -> Bool
forall a b. (a -> b) -> a -> b
$ HalfEdge -> PlanarGraph -> Face
halfEdgeFace HalfEdge
edge PlanarGraph
pg

-------------------------------------------------------------------------------
-- Faces

-- | \( O(k) \)
--   
--   List all faces in a graph.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--
-- <<docs/Data/PlanarGraph/planargraph-2635031442529484236.compact.svg>>
--
-- >>> pgFaces pg
-- [Face 0,Face 1,Face 2,Face 3,Face 4,Face 5]
--
-- @since 0.12.0.0
pgFaces :: PlanarGraph -> [Face]
pgFaces :: PlanarGraph -> [Face]
pgFaces PlanarGraph
pg =
  [ Int -> Face
Face Int
fId
  | Int
fId <- [Int
0 .. Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg)Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 ]
  , HalfEdge -> Bool
halfEdgeIsValid (Face -> PlanarGraph -> HalfEdge
faceHalfEdge (Int -> Face
Face Int
fId) PlanarGraph
pg)
  ]

-- | \( O(k) \)
--   
--   List all boundaries (ie external faces) in a graph. There may be
--   multiple boundaries and they may or may not be reachable from each other.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--
-- <<docs/Data/PlanarGraph/planargraph-2635031442529484236.compact.svg>>
--
-- >>> pgBoundaries pg
-- [Boundary 0,Boundary 1]
--
-- >>> faceBoundary (Boundary 0) pg
-- [Vertex 0,Vertex 4,Vertex 5]
--
-- >>> faceBoundary (Boundary 1) pg
-- [Vertex 1,Vertex 2,Vertex 3]
--
-- @since 0.12.0.0
pgBoundaries :: PlanarGraph -> [Face]
pgBoundaries :: PlanarGraph -> [Face]
pgBoundaries PlanarGraph
pg =
  [ Int -> Face
Boundary Int
fId
  | Int
fId <- [Int
0 .. Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg)Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 ]
  , HalfEdge -> Bool
halfEdgeIsValid (Face -> PlanarGraph -> HalfEdge
faceHalfEdge (Int -> Face
Boundary Int
fId) PlanarGraph
pg)
  ]

-- | O(1)
faceCheck :: String -> Face -> PlanarGraph -> a -> a
faceCheck :: String -> Face -> PlanarGraph -> a -> a
faceCheck String
tag (Face Int
fId) PlanarGraph
pg a
_val
  | Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg) Bool -> Bool -> Bool
|| Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Out-of-bounds face access: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
fId)
  | PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Tried to access deleted face: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
fId)
faceCheck String
tag (Boundary Int
fId) PlanarGraph
pg a
_val
  | Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg) Bool -> Bool -> Bool
|| Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Out-of-bounds boundary access: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
fId)
  | PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 =
    String -> String -> a
forall a. String -> String -> a
panic String
tag (String
"Tried to access deleted boundary: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
fId)
faceCheck String
_tag Face
_face PlanarGraph
_pg a
val = a
val

-- | \( O(1) \)
--
--   Returns @True@ iff a face or boundary is part of the planar graph.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2]]
--
-- <<docs/Data/PlanarGraph/planargraph-2959979592048325618.svg>>
--
-- >>> faceMember (Face 0) pg
-- True
--
-- >>> faceMember (Face 1) pg
-- False
--
-- >>> faceMember (Face 100) pg
-- False
--
-- >>> faceMember (Face (-100)) pg
-- False
--
-- >>> faceMember (Boundary 0) pg
-- True
--
-- >>> faceMember (Boundary 1) pg
-- False
--
-- @since 0.12.0.0
faceMember :: Face -> PlanarGraph -> Bool
faceMember :: Face -> PlanarGraph -> Bool
faceMember face :: Face
face@(Face Int
fId) PlanarGraph
pg =
  Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg) Bool -> Bool -> Bool
&&
  Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&&
  HalfEdge -> Bool
halfEdgeIsValid (Face -> PlanarGraph -> HalfEdge
faceHalfEdge Face
face PlanarGraph
pg)
faceMember face :: Face
face@(Boundary Int
fId) PlanarGraph
pg =
  Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg) Bool -> Bool -> Bool
&&
  Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&&
  HalfEdge -> Bool
halfEdgeIsValid (Face -> PlanarGraph -> HalfEdge
faceHalfEdge Face
face PlanarGraph
pg)


-- -- | O(1)
-- faceInvalid :: Face
-- faceInvalid = faceFromId maxBound

-- -- | O(1)
-- faceIsValid :: Face -> Bool
-- faceIsValid = not . faceIsInvalid

-- -- | O(1)
-- faceIsInvalid :: Face -> Bool
-- faceIsInvalid (Face fId)     = fId == maxBound
-- faceIsInvalid (Boundary fId) = fId == maxBound

-- | O(1)
--
-- @since 0.12.0.0
faceFromId :: FaceId -> Face
faceFromId :: Int -> Face
faceFromId Int
fId | Int
fId Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = Int -> Face
Boundary (Int -> Int
forall a. Num a => a -> a
negate Int
fId Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
faceFromId Int
fId = Int -> Face
Face Int
fId

-- | \( O(1) \)
--
--   Maps interior faces to positive integers and boundary faces to negative integers.
--
-- ==== __Examples:__
--
-- >>> faceId (Face 0)
-- 0
--
-- >>> faceId (Face 10)
-- 10
--
-- >>> faceId (Boundary 0)
-- -1
--
-- >>> faceId (Boundary 10)
-- -11
--
-- @since 0.12.0.0
faceId :: Face -> FaceId
faceId :: Face -> Int
faceId (Face Int
fId)     = Int
fId
faceId (Boundary Int
fId) = Int -> Int
forall a. Num a => a -> a
negate Int
fId Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1


-- | \( O(1) \)
--
--   Query the half-edge associated with a face or boundary.
--
-- ==== __Examples:__
--
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> faceHalfEdge (Face 0) pg
-- HalfEdge 0
--
-- >>> faceHalfEdge (Face 1) pg
-- HalfEdge 8
--
-- >>> faceHalfEdge (Boundary 0) pg
-- HalfEdge 1
--
-- >>> faceHalfEdge (Face 10) pg {- Invalid face -}
-- ... Exception: Data.PlanarGraph.Immutable.faceHalfEdge: Out-of-bounds face access: 10
-- ...
--
-- @since 0.12.0.0
faceHalfEdge :: Face -> PlanarGraph -> HalfEdge
faceHalfEdge :: Face -> PlanarGraph -> HalfEdge
faceHalfEdge Face
face PlanarGraph
pg = String -> Face -> PlanarGraph -> HalfEdge -> HalfEdge
forall a. String -> Face -> PlanarGraph -> a -> a
faceCheck String
"faceHalfEdge" Face
face PlanarGraph
pg (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$
  case Face
face of
    Face Int
fId     -> Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
fId
    Boundary Int
fId -> Int -> HalfEdge
HalfEdge (Int -> HalfEdge) -> Int -> HalfEdge
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg Vector Int -> Int -> Int
forall a. Vector a -> Int -> a
Vector.! Int
fId

-- | \( O(1) \)
--
--   Returns @True@ iff a face is interior. Does not check if the face actually exists.
--
-- ==== __Examples:__
--
-- >>> faceIsInterior (Face 0)
-- True
--
-- >>> faceIsInterior (Face 10000)
-- True
--
-- >>> faceIsInterior (Boundary 0)
-- False
--
-- @since 0.12.0.0
faceIsInterior :: Face -> Bool
faceIsInterior :: Face -> Bool
faceIsInterior = Bool -> Bool
not (Bool -> Bool) -> (Face -> Bool) -> Face -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Face -> Bool
faceIsBoundary

-- | \( O(1) \)
--
--   Returns @True@ iff a face is a boundary. Does not check if the face actually exists.
--
-- ==== __Examples:__
--
-- >>> faceIsBoundary (Face 0)
-- False
--
-- >>> faceIsBoundary (Face 10000)
-- False
--
-- >>> faceIsBoundary (Boundary 0)
-- True
--
-- @since 0.12.0.0
faceIsBoundary :: Face -> Bool
faceIsBoundary :: Face -> Bool
faceIsBoundary Face{}     = Bool
False
faceIsBoundary Boundary{} = Bool
True

-- faceVertices         :: Face -> ST s (CircularVector Vertex)

-- | \( O(k) \)
--
--   Query the half-edges around a face in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> faceHalfEdges (Face 0) pg
-- [HalfEdge 0,HalfEdge 2,HalfEdge 4,HalfEdge 6]
--
-- >>> faceHalfEdges (Face 1) pg
-- [HalfEdge 8,HalfEdge 5,HalfEdge 3,HalfEdge 10]
--
-- >>> faceHalfEdges (Boundary 0) pg
-- [HalfEdge 1,HalfEdge 11,HalfEdge 9,HalfEdge 7]
--
-- >>> faceHalfEdges (Face 10) pg
-- ... Exception: Data.PlanarGraph.Immutable.faceHalfEdges: Out-of-bounds face access: 10
-- ...
--
-- @since 0.12.0.0
faceHalfEdges        :: Face -> PlanarGraph -> [HalfEdge]
faceHalfEdges :: Face -> PlanarGraph -> [HalfEdge]
faceHalfEdges Face
face PlanarGraph
pg | String -> Face -> PlanarGraph -> Bool -> Bool
forall a. String -> Face -> PlanarGraph -> a -> a
faceCheck String
"faceHalfEdges" Face
face PlanarGraph
pg Bool
False = [HalfEdge]
forall a. HasCallStack => a
undefined
faceHalfEdges Face
face PlanarGraph
pg
  | Face -> Bool
faceIsBoundary Face
face = HalfEdge
first HalfEdge -> [HalfEdge] -> [HalfEdge]
forall a. a -> [a] -> [a]
: (forall b. (HalfEdge -> b -> b) -> b -> b) -> [HalfEdge]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build ((HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
forall b.
(HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
worker HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext (HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNext HalfEdge
first PlanarGraph
pg))
  | Bool
otherwise           = HalfEdge
first HalfEdge -> [HalfEdge] -> [HalfEdge]
forall a. a -> [a] -> [a]
: (forall b. (HalfEdge -> b -> b) -> b -> b) -> [HalfEdge]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build ((HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
forall b.
(HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
worker HalfEdge -> PlanarGraph -> HalfEdge
halfEdgePrev (HalfEdge -> PlanarGraph -> HalfEdge
halfEdgePrev HalfEdge
first PlanarGraph
pg))
  where
    first :: HalfEdge
first = Face -> PlanarGraph -> HalfEdge
faceHalfEdge Face
face PlanarGraph
pg
    worker :: (HalfEdge -> PlanarGraph -> HalfEdge) -> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
    worker :: (HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
worker HalfEdge -> PlanarGraph -> HalfEdge
advance HalfEdge
he HalfEdge -> b -> b
cons b
nil
      | HalfEdge
he HalfEdge -> HalfEdge -> Bool
forall a. Eq a => a -> a -> Bool
== HalfEdge
first = b
nil
      | Bool
otherwise   = HalfEdge -> b -> b
cons HalfEdge
he ((HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
forall b.
(HalfEdge -> PlanarGraph -> HalfEdge)
-> HalfEdge -> (HalfEdge -> b -> b) -> b -> b
worker HalfEdge -> PlanarGraph -> HalfEdge
advance (HalfEdge -> PlanarGraph -> HalfEdge
advance HalfEdge
he PlanarGraph
pg) HalfEdge -> b -> b
cons b
nil)

-- | \( O(k) \)
--
--   Query the vertices of a face in counter-clockwise order.
--
-- ==== __Examples:__
-- >>> let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--
-- <<docs/Data/PlanarGraph/planargraph-1711135548958680232.svg>>
--
-- >>> faceBoundary (Face 0) pg
-- [Vertex 1,Vertex 2,Vertex 3,Vertex 0]
--
-- >>> faceBoundary (Face 1) pg
-- [Vertex 3,Vertex 2,Vertex 1,Vertex 4]
--
-- >>> faceBoundary (Boundary 0) pg
-- [Vertex 0,Vertex 1,Vertex 4,Vertex 3]
--
-- >>> faceBoundary (Face 10) pg
-- ... Exception: Data.PlanarGraph.Immutable.faceBoundary: Out-of-bounds face access: 10
-- ...
--
-- @since 0.12.0.0
faceBoundary :: Face -> PlanarGraph -> [Vertex]
faceBoundary :: Face -> PlanarGraph -> [Vertex]
faceBoundary Face
face PlanarGraph
pg = String -> Face -> PlanarGraph -> [Vertex] -> [Vertex]
forall a. String -> Face -> PlanarGraph -> a -> a
faceCheck String
"faceBoundary" Face
face PlanarGraph
pg ([Vertex] -> [Vertex]) -> [Vertex] -> [Vertex]
forall a b. (a -> b) -> a -> b
$
  (HalfEdge -> Vertex) -> [HalfEdge] -> [Vertex]
forall a b. (a -> b) -> [a] -> [b]
map (HalfEdge -> PlanarGraph -> Vertex
`halfEdgeVertex` PlanarGraph
pg) ([HalfEdge] -> [Vertex]) -> [HalfEdge] -> [Vertex]
forall a b. (a -> b) -> a -> b
$ Face -> PlanarGraph -> [HalfEdge]
faceHalfEdges Face
face PlanarGraph
pg

-- faceAdjacentFaces    :: Face -> ST s (CircularVector Face)

-------------------------------------------------------------------------------
-- Mutation

-- | \( O(n) \)
--
-- @since 0.12.0.0
pgMutate :: PlanarGraph -> (forall s. Mut.PlanarGraph s -> ST s ()) -> PlanarGraph
pgMutate :: PlanarGraph -> (forall s. PlanarGraph s -> ST s ()) -> PlanarGraph
pgMutate PlanarGraph
pg forall s. PlanarGraph s -> ST s ()
action = (forall s. ST s PlanarGraph) -> PlanarGraph
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s PlanarGraph) -> PlanarGraph)
-> (forall s. ST s PlanarGraph) -> PlanarGraph
forall a b. (a -> b) -> a -> b
$ do
  PlanarGraph s
mutPG <- PlanarGraph -> ST s (PlanarGraph s)
forall s. PlanarGraph -> ST s (PlanarGraph s)
pgThaw PlanarGraph
pg
  PlanarGraph s -> ST s ()
forall s. PlanarGraph s -> ST s ()
action PlanarGraph s
mutPG
  PlanarGraph s -> ST s PlanarGraph
forall s. PlanarGraph s -> ST s PlanarGraph
pgUnsafeFreeze PlanarGraph s
mutPG

-- | \( O(1) \)
--
-- @since 0.12.0.0
pgCreate :: (forall s. ST s (Mut.PlanarGraph s)) -> PlanarGraph
pgCreate :: (forall s. ST s (PlanarGraph s)) -> PlanarGraph
pgCreate forall s. ST s (PlanarGraph s)
action = (forall s. ST s PlanarGraph) -> PlanarGraph
forall a. (forall s. ST s a) -> a
runST (ST s (PlanarGraph s)
forall s. ST s (PlanarGraph s)
action ST s (PlanarGraph s)
-> (PlanarGraph s -> ST s PlanarGraph) -> ST s PlanarGraph
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= PlanarGraph s -> ST s PlanarGraph
forall s. PlanarGraph s -> ST s PlanarGraph
pgUnsafeFreeze)

-- | \( O(n) \)
--
-- @since 0.12.0.0
pgThaw :: PlanarGraph -> ST s (Mut.PlanarGraph s)
pgThaw :: PlanarGraph -> ST s (PlanarGraph s)
pgThaw PlanarGraph
pg = do
  STRef s Int
pgNextHalfEdgeId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
  STRef s Int
pgNextVertexId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg
  STRef s Int
pgNextFaceId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg
  STRef s Int
pgNextBoundaryId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg

  GrowVector s Int
pgHalfEdgeNext   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg
  GrowVector s Int
pgHalfEdgePrev   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgePrev PlanarGraph
pg
  GrowVector s Int
pgHalfEdgeFace   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeFace PlanarGraph
pg
  GrowVector s Int
pgHalfEdgeVertex <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeVertex PlanarGraph
pg
  GrowVector s Int
pgVertexEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg
  GrowVector s Int
pgFaceEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg
  GrowVector s Int
pgBoundaryEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.thawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg
  PlanarGraph s -> ST s (PlanarGraph s)
forall (f :: * -> *) a. Applicative f => a -> f a
pure PlanarGraph :: forall s.
STRef s Int
-> STRef s Int
-> STRef s Int
-> STRef s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> PlanarGraph s
Mut.PlanarGraph {STRef s Int
GrowVector s Int
pgBoundaryEdges :: GrowVector s Int
pgFaceEdges :: GrowVector s Int
pgVertexEdges :: GrowVector s Int
pgHalfEdgeFace :: GrowVector s Int
pgHalfEdgeVertex :: GrowVector s Int
pgHalfEdgePrev :: GrowVector s Int
pgHalfEdgeNext :: GrowVector s Int
pgNextBoundaryId :: STRef s Int
pgNextFaceId :: STRef s Int
pgNextVertexId :: STRef s Int
pgNextHalfEdgeId :: STRef s Int
pgBoundaryEdges :: GrowVector s Int
pgFaceEdges :: GrowVector s Int
pgVertexEdges :: GrowVector s Int
pgHalfEdgeVertex :: GrowVector s Int
pgHalfEdgeFace :: GrowVector s Int
pgHalfEdgePrev :: GrowVector s Int
pgHalfEdgeNext :: GrowVector s Int
pgNextBoundaryId :: STRef s Int
pgNextFaceId :: STRef s Int
pgNextVertexId :: STRef s Int
pgNextHalfEdgeId :: STRef s Int
..}

-- | \( O(1) \)
--
-- @since 0.12.0.0
pgUnsafeThaw :: PlanarGraph -> ST s (Mut.PlanarGraph s)
pgUnsafeThaw :: PlanarGraph -> ST s (PlanarGraph s)
pgUnsafeThaw PlanarGraph
pg = do
  STRef s Int
pgNextHalfEdgeId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg
  STRef s Int
pgNextVertexId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg
  STRef s Int
pgNextFaceId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg
  STRef s Int
pgNextBoundaryId <- Int -> ST s (STRef s Int)
forall a s. a -> ST s (STRef s a)
newSTRef (Int -> ST s (STRef s Int)) -> Int -> ST s (STRef s Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Vector a -> Int
Vector.length (Vector Int -> Int) -> Vector Int -> Int
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg

  GrowVector s Int
pgHalfEdgeNext   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeNext PlanarGraph
pg
  GrowVector s Int
pgHalfEdgePrev   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgePrev PlanarGraph
pg
  GrowVector s Int
pgHalfEdgeFace   <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeFace PlanarGraph
pg
  GrowVector s Int
pgHalfEdgeVertex <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgHalfEdgeVertex PlanarGraph
pg
  GrowVector s Int
pgVertexEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg
  GrowVector s Int
pgFaceEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgFaceEdges PlanarGraph
pg
  GrowVector s Int
pgBoundaryEdges <- Vector Int -> ST s (GrowVector s Int)
forall v s. Vector v -> ST s (GrowVector s v)
Mut.unsafeThawVector (Vector Int -> ST s (GrowVector s Int))
-> Vector Int -> ST s (GrowVector s Int)
forall a b. (a -> b) -> a -> b
$ PlanarGraph -> Vector Int
pgBoundaryEdges PlanarGraph
pg
  PlanarGraph s -> ST s (PlanarGraph s)
forall (f :: * -> *) a. Applicative f => a -> f a
pure PlanarGraph :: forall s.
STRef s Int
-> STRef s Int
-> STRef s Int
-> STRef s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> GrowVector s Int
-> PlanarGraph s
Mut.PlanarGraph {STRef s Int
GrowVector s Int
pgBoundaryEdges :: GrowVector s Int
pgFaceEdges :: GrowVector s Int
pgVertexEdges :: GrowVector s Int
pgHalfEdgeVertex :: GrowVector s Int
pgHalfEdgeFace :: GrowVector s Int
pgHalfEdgePrev :: GrowVector s Int
pgHalfEdgeNext :: GrowVector s Int
pgNextBoundaryId :: STRef s Int
pgNextFaceId :: STRef s Int
pgNextVertexId :: STRef s Int
pgNextHalfEdgeId :: STRef s Int
pgBoundaryEdges :: GrowVector s Int
pgFaceEdges :: GrowVector s Int
pgVertexEdges :: GrowVector s Int
pgHalfEdgeFace :: GrowVector s Int
pgHalfEdgeVertex :: GrowVector s Int
pgHalfEdgePrev :: GrowVector s Int
pgHalfEdgeNext :: GrowVector s Int
pgNextBoundaryId :: STRef s Int
pgNextFaceId :: STRef s Int
pgNextVertexId :: STRef s Int
pgNextHalfEdgeId :: STRef s Int
..}

-- | \( O(n) \)
--
-- @since 0.12.0.0
pgFreeze :: Mut.PlanarGraph s -> ST s PlanarGraph
pgFreeze :: PlanarGraph s -> ST s PlanarGraph
pgFreeze PlanarGraph s
pg = do
  Int
maxEdgeId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextHalfEdgeId PlanarGraph s
pg)
  Int
maxVertexId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextVertexId PlanarGraph s
pg)
  Int
maxFaceId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextFaceId PlanarGraph s
pg)
  Int
maxBoundaryId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextBoundaryId PlanarGraph s
pg)

  Vector Int
pgHalfEdgeNext   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeNext PlanarGraph s
pg)
  Vector Int
pgHalfEdgePrev   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgePrev PlanarGraph s
pg)
  Vector Int
pgHalfEdgeFace   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeFace PlanarGraph s
pg)
  Vector Int
pgHalfEdgeVertex <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeVertex PlanarGraph s
pg)
  Vector Int
pgVertexEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxVertexId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgVertexEdges PlanarGraph s
pg)
  Vector Int
pgFaceEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxFaceId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgFaceEdges PlanarGraph s
pg)
  Vector Int
pgBoundaryEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxBoundaryId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.freezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgBoundaryEdges PlanarGraph s
pg)
  PlanarGraph -> ST s PlanarGraph
forall (f :: * -> *) a. Applicative f => a -> f a
pure PlanarGraph :: Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> PlanarGraph
PlanarGraph { Vector Int
pgBoundaryEdges :: Vector Int
pgFaceEdges :: Vector Int
pgVertexEdges :: Vector Int
pgHalfEdgeVertex :: Vector Int
pgHalfEdgeFace :: Vector Int
pgHalfEdgePrev :: Vector Int
pgHalfEdgeNext :: Vector Int
pgBoundaryEdges :: Vector Int
pgFaceEdges :: Vector Int
pgVertexEdges :: Vector Int
pgHalfEdgeFace :: Vector Int
pgHalfEdgeVertex :: Vector Int
pgHalfEdgePrev :: Vector Int
pgHalfEdgeNext :: Vector Int
.. }

-- | \( O(1) \)
--
-- @since 0.12.0.0
pgUnsafeFreeze :: Mut.PlanarGraph s -> ST s PlanarGraph
pgUnsafeFreeze :: PlanarGraph s -> ST s PlanarGraph
pgUnsafeFreeze PlanarGraph s
pg = do
  Int
maxEdgeId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextHalfEdgeId PlanarGraph s
pg)
  Int
maxVertexId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextVertexId PlanarGraph s
pg)
  Int
maxFaceId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextFaceId PlanarGraph s
pg)
  Int
maxBoundaryId <- STRef s Int -> ST s Int
forall s a. STRef s a -> ST s a
readSTRef (PlanarGraph s -> STRef s Int
forall s. PlanarGraph s -> STRef s Int
Mut.pgNextBoundaryId PlanarGraph s
pg)

  Vector Int
pgHalfEdgeNext   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeNext PlanarGraph s
pg)
  Vector Int
pgHalfEdgePrev   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgePrev PlanarGraph s
pg)
  Vector Int
pgHalfEdgeFace   <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeFace PlanarGraph s
pg)
  Vector Int
pgHalfEdgeVertex <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take (Int
maxEdgeIdInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2) (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgHalfEdgeVertex PlanarGraph s
pg)
  Vector Int
pgVertexEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxVertexId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgVertexEdges PlanarGraph s
pg)
  Vector Int
pgFaceEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxFaceId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgFaceEdges PlanarGraph s
pg)
  Vector Int
pgBoundaryEdges <- Int -> Vector Int -> Vector Int
forall a. Int -> Vector a -> Vector a
Vector.take Int
maxBoundaryId (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> GrowVector s Int -> ST s (Vector Int)
forall s v. GrowVector s v -> ST s (Vector v)
Mut.unsafeFreezeVector (PlanarGraph s -> GrowVector s Int
forall s. PlanarGraph s -> GrowVector s Int
Mut.pgBoundaryEdges PlanarGraph s
pg)
  PlanarGraph -> ST s PlanarGraph
forall (f :: * -> *) a. Applicative f => a -> f a
pure PlanarGraph :: Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> Vector Int
-> PlanarGraph
PlanarGraph { Vector Int
pgBoundaryEdges :: Vector Int
pgFaceEdges :: Vector Int
pgVertexEdges :: Vector Int
pgHalfEdgeVertex :: Vector Int
pgHalfEdgeFace :: Vector Int
pgHalfEdgePrev :: Vector Int
pgHalfEdgeNext :: Vector Int
pgBoundaryEdges :: Vector Int
pgFaceEdges :: Vector Int
pgVertexEdges :: Vector Int
pgHalfEdgeFace :: Vector Int
pgHalfEdgeVertex :: Vector Int
pgHalfEdgePrev :: Vector Int
pgHalfEdgeNext :: Vector Int
.. }

-------------------------------------------------------------------------------
-- Tutte embedding

-- | \( O(n^3) \)
--
-- @since 0.12.0.0
tutteEmbedding :: PlanarGraph -> Vector.Vector (V2 Double)
tutteEmbedding :: PlanarGraph -> Vector (V2 Double)
tutteEmbedding PlanarGraph
pg = (forall s. ST s (Vector (V2 Double))) -> Vector (V2 Double)
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Vector (V2 Double))) -> Vector (V2 Double))
-> (forall s. ST s (Vector (V2 Double))) -> Vector (V2 Double)
forall a b. (a -> b) -> a -> b
$ do
  let nVertices :: Int
nVertices = Vector Int -> Int
forall a. Vector a -> Int
Vector.length (PlanarGraph -> Vector Int
pgVertexEdges PlanarGraph
pg)
  -- trace ("nVertices: " ++ show nVertices) $ return ()
  Vector (MVector s Double)
m <- Int -> ST s (MVector s Double) -> ST s (Vector (MVector s Double))
forall (m :: * -> *) a. Monad m => Int -> m a -> m (Vector a)
Vector.replicateM Int
nVertices (Int -> Double -> ST s (MVector (PrimState (ST s)) Double)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MVector (PrimState m) a)
V.replicate Int
nVertices Double
0)
  MVector s Double
vx <- Int -> Double -> ST s (MVector (PrimState (ST s)) Double)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MVector (PrimState m) a)
V.replicate Int
nVertices Double
0
  MVector s Double
vy <- Int -> Double -> ST s (MVector (PrimState (ST s)) Double)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MVector (PrimState m) a)
V.replicate Int
nVertices Double
0

  let boundary :: [Vertex]
boundary = Face -> PlanarGraph -> [Vertex]
faceBoundary (Int -> Face
Boundary Int
0) PlanarGraph
pg
  let nBoundary :: Int
nBoundary = [Vertex] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Vertex]
boundary
  -- trace ("Vectors: " ++ show boundary) $
  [(Vertex, (Double, Double))]
-> ((Vertex, (Double, Double)) -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ ([Vertex] -> [(Double, Double)] -> [(Vertex, (Double, Double))]
forall a b. [a] -> [b] -> [(a, b)]
zip [Vertex]
boundary (Int -> [(Double, Double)]
regularPolygon Int
nBoundary)) (((Vertex, (Double, Double)) -> ST s ()) -> ST s ())
-> ((Vertex, (Double, Double)) -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \(Vertex
vertex,(Double
x,Double
y)) -> do
    let valid :: Bool
valid = HalfEdge -> Bool
halfEdgeIsValid (HalfEdge -> Bool) -> HalfEdge -> Bool
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge Vertex
vertex PlanarGraph
pg
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
valid (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
      MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write (Vector (MVector s Double)
m Vector (MVector s Double) -> Int -> MVector s Double
forall a. Vector a -> Int -> a
Vector.! Vertex -> Int
vertexId Vertex
vertex) (Vertex -> Int
vertexId Vertex
vertex) (Double
1::Double)
      MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write MVector s Double
MVector (PrimState (ST s)) Double
vx (Vertex -> Int
vertexId Vertex
vertex) Double
x
      MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write MVector s Double
MVector (PrimState (ST s)) Double
vy (Vertex -> Int
vertexId Vertex
vertex) Double
y

  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0..Int
nVerticesInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
vId -> -- trace ("Vertex: " ++ show vId) $
    do
      let valid :: Bool
valid = HalfEdge -> Bool
halfEdgeIsValid (HalfEdge -> Bool) -> HalfEdge -> Bool
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge (Int -> Vertex
Vertex Int
vId) PlanarGraph
pg
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless Bool
valid (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write (Vector (MVector s Double)
m Vector (MVector s Double) -> Int -> MVector s Double
forall a. Vector a -> Int -> a
Vector.! Int
vId) Int
vId (Double
1::Double)
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
valid (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        let onOuterBoundary :: Bool
onOuterBoundary =
              Int -> Face
Boundary Int
0 Face -> Face -> Bool
forall a. Eq a => a -> a -> Bool
== HalfEdge -> PlanarGraph -> Face
halfEdgeFace (HalfEdge -> HalfEdge
halfEdgeTwin (HalfEdge -> HalfEdge) -> HalfEdge -> HalfEdge
forall a b. (a -> b) -> a -> b
$ Vertex -> PlanarGraph -> HalfEdge
vertexHalfEdge (Int -> Vertex
Vertex Int
vId) PlanarGraph
pg) PlanarGraph
pg
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless Bool
onOuterBoundary (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
          let vertex :: Vertex
vertex = Int -> Vertex
Vertex Int
vId
          let neighbours :: [Vertex]
neighbours = Vertex -> PlanarGraph -> [Vertex]
vertexNeighbours Vertex
vertex PlanarGraph
pg
          [Vertex] -> (Vertex -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Vertex]
neighbours ((Vertex -> ST s ()) -> ST s ()) -> (Vertex -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Vertex
neighbour ->
            MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write (Vector (MVector s Double)
m Vector (MVector s Double) -> Int -> MVector s Double
forall a. Vector a -> Int -> a
Vector.! Int
vId) (Vertex -> Int
vertexId Vertex
neighbour) (Double
1::Double)
          MVector (PrimState (ST s)) Double -> Int -> Double -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
V.write (Vector (MVector s Double)
m Vector (MVector s Double) -> Int -> MVector s Double
forall a. Vector a -> Int -> a
Vector.! Int
vId) Int
vId (Double -> Double
forall a. Num a => a -> a
negate (Double -> Double) -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Double) -> Int -> Double
forall a b. (a -> b) -> a -> b
$ [Vertex] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Vertex]
neighbours)

  Vector (Vector Double)
mi <- (MVector s Double -> ST s (Vector Double))
-> Vector (MVector s Double) -> ST s (Vector (Vector Double))
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM MVector s Double -> ST s (Vector Double)
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> m (Vector a)
Vector.freeze Vector (MVector s Double)
m
  Vector Double
vxi <- MVector (PrimState (ST s)) Double -> ST s (Vector Double)
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> m (Vector a)
Vector.freeze MVector s Double
MVector (PrimState (ST s)) Double
vx
  Vector Double
vyi <- MVector (PrimState (ST s)) Double -> ST s (Vector Double)
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> m (Vector a)
Vector.freeze MVector s Double
MVector (PrimState (ST s)) Double
vy

  let xPos :: Vector Double
xPos = Vector (Vector Double)
-> Vector Double
-> (forall n.
    Dim n =>
    V n (V n Double) -> V n Double -> V n Double)
-> Vector Double
forall a.
Vector (Vector a)
-> Vector a
-> (forall n. Dim n => V n (V n a) -> V n a -> V n a)
-> Vector a
reifyMatrix Vector (Vector Double)
mi Vector Double
vxi forall n. Dim n => V n (V n Double) -> V n Double -> V n Double
forall a (m :: * -> *) i.
(Num a, Fractional a, Foldable m, Traversable m, Applicative m,
 Additive m, Ixed (m a), Ixed (m (m a)), i ~ Index (m a),
 i ~ Index (m (m a)), Eq i, Integral i, a ~ IxValue (m a),
 m a ~ IxValue (m (m a)), Num (m a)) =>
m (m a) -> m a -> m a
luSolve
      yPos :: Vector Double
yPos = Vector (Vector Double)
-> Vector Double
-> (forall n.
    Dim n =>
    V n (V n Double) -> V n Double -> V n Double)
-> Vector Double
forall a.
Vector (Vector a)
-> Vector a
-> (forall n. Dim n => V n (V n a) -> V n a -> V n a)
-> Vector a
reifyMatrix Vector (Vector Double)
mi Vector Double
vyi forall n. Dim n => V n (V n Double) -> V n Double -> V n Double
forall a (m :: * -> *) i.
(Num a, Fractional a, Foldable m, Traversable m, Applicative m,
 Additive m, Ixed (m a), Ixed (m (m a)), i ~ Index (m a),
 i ~ Index (m (m a)), Eq i, Integral i, a ~ IxValue (m a),
 m a ~ IxValue (m (m a)), Num (m a)) =>
m (m a) -> m a -> m a
luSolve

  Vector (V2 Double) -> ST s (Vector (V2 Double))
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Vector (V2 Double) -> ST s (Vector (V2 Double)))
-> Vector (V2 Double) -> ST s (Vector (V2 Double))
forall a b. (a -> b) -> a -> b
$ (Double -> Double -> V2 Double)
-> Vector Double -> Vector Double -> Vector (V2 Double)
forall a b c. (a -> b -> c) -> Vector a -> Vector b -> Vector c
Vector.zipWith Double -> Double -> V2 Double
forall a. a -> a -> V2 a
V2 Vector Double
xPos Vector Double
yPos

reifyMatrix :: forall a. Vector.Vector (Vector.Vector a) ->
  Vector.Vector a ->
  (forall (n :: *). Dim n => V n (V n a) -> V n a -> V n a) ->
  Vector.Vector a
reifyMatrix :: Vector (Vector a)
-> Vector a
-> (forall n. Dim n => V n (V n a) -> V n a -> V n a)
-> Vector a
reifyMatrix Vector (Vector a)
m Vector a
v forall n. Dim n => V n (V n a) -> V n a -> V n a
f = Int -> (forall n. Dim n => Proxy n -> Vector a) -> Vector a
forall r. Int -> (forall n. Dim n => Proxy n -> r) -> r
reifyDim (Vector (Vector a) -> Int
forall a. Vector a -> Int
Vector.length Vector (Vector a)
m) ((forall n. Dim n => Proxy n -> Vector a) -> Vector a)
-> (forall n. Dim n => Proxy n -> Vector a) -> Vector a
forall a b. (a -> b) -> a -> b
$ \(Proxy n
Proxy :: Proxy n) ->
  V n a -> Vector a
forall k (n :: k) a. V n a -> Vector a
toVector (V n (V n a) -> V n a -> V n a
forall n. Dim n => V n (V n a) -> V n a -> V n a
f (Vector (Vector a) -> V n (V n a)
coerce Vector (Vector a)
m :: (V n (V n a))) (Vector a -> V n a
coerce Vector a
v))

regularPolygon :: Int -> [(Double, Double)]
regularPolygon :: Int -> [(Double, Double)]
regularPolygon Int
n =
    [ (Double -> Double
forall a. Floating a => a -> a
cos Double
ang, Double -> Double
forall a. Floating a => a -> a
sin Double
ang)
    | Int
i <- [Int
0 .. Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]
    , let ang :: Double
ang = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
frac Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
forall a. Floating a => a
piDouble -> Double -> Double
forall a. Fractional a => a -> a -> a
/Double
2]
  where
    frac :: Double
frac = Double
2Double -> Double -> Double
forall a. Num a => a -> a -> a
*Double
forall a. Floating a => a
pi Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n