-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Data structures, and Data types.
--   
--   The Non-geometric data types and algorithms used in HGeometry.
@package hgeometry-combinatorial
@version 0.13


module Algorithms.BinarySearch

-- | Given a monotonic predicate p, a lower bound l, and an upper bound u,
--   with: p l = False p u = True l < u.
--   
--   Get the index h such that everything strictly smaller than h has: p i
--   = False, and all i >= h, we have p h = True
--   
--   running time: <math>
binarySearch :: Integral a => (a -> Bool) -> a -> a -> a

-- | Given a value <math>, a monotone predicate <math>, and two
--   values <math> and <math> with:
--   
--   <ul>
--   <li>&lt;math&gt; = False</li>
--   <li>&lt;math&gt; = True</li>
--   <li>&lt;math&gt;</li>
--   </ul>
--   
--   we find a value &lt;math&gt; such that:
--   
--   <ul>
--   <li>&lt;math&gt; = True</li>
--   <li>&lt;math&gt; = False</li>
--   </ul>
--   
--   <pre>
--   &gt;&gt;&gt; binarySearchUntil (0.1) (&gt;= 0.5) 0 (1 :: Double)
--   0.5
--   
--   &gt;&gt;&gt; binarySearchUntil (0.1) (&gt;= 0.51) 0 (1 :: Double)
--   0.5625
--   
--   &gt;&gt;&gt; binarySearchUntil (0.01) (&gt;= 0.51) 0 (1 :: Double)
--   0.515625
--   </pre>
binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r
class BinarySearch v where {
    type family Index v :: *;
    type family Elem v :: *;
}

-- | Given a monotonic predicate p and a data structure v, find the element
--   v[h] such that that
--   
--   for every index i &lt; h we have p v[i] = False, and for every inedx i
--   &gt;= h we have p v[i] = True
--   
--   returns Nothing if no element satisfies p
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the time to execute
--   the predicate.
binarySearchIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Elem v)

-- | Given a monotonic predicate p and a data structure v, find the index h
--   such that that
--   
--   for every index i &lt; h we have p v[i] = False, and for every inedx i
--   &gt;= h we have p v[i] = True
--   
--   returns Nothing if no element satisfies p
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the time to execute
--   the predicate.
binarySearchIdxIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Index v)
instance Algorithms.BinarySearch.BinarySearch (Data.Sequence.Internal.Seq a)
instance Data.Vector.Generic.Base.Vector v a => Algorithms.BinarySearch.BinarySearch (v a)
instance Algorithms.BinarySearch.BinarySearch (Data.Set.Internal.Set a)


module Algorithms.DivideAndConquer

-- | Divide and conquer strategy. See <a>divideAndConquer1</a>.
divideAndConquer :: (Foldable f, Monoid s) => (a -> s) -> f a -> s

-- | Divide and conquer strategy
--   
--   the running time satifies T(n) = 2T(n/2) + M(n),
--   
--   where M(n) is the time corresponding to the semigroup operation of s
--   on n elements.
divideAndConquer1 :: (Foldable1 f, Semigroup s) => (a -> s) -> f a -> s

-- | Divide and conquer strategy
--   
--   the running time satifies T(n) = 2T(n/2) + M(n),
--   
--   where M(n) is the time corresponding to the semigroup operation of s
--   on n elements.
divideAndConquer1With :: Foldable1 f => (s -> s -> s) -> (a -> s) -> f a -> s

-- | Merges two sorted non-Empty lists in linear time.
mergeSorted :: Ord a => NonEmpty a -> NonEmpty a -> NonEmpty a

-- | Merges two sorted lists in linear time.
mergeSortedLists :: Ord a => [a] -> [a] -> [a]

-- | Given an ordering and two nonempty sequences ordered according to that
--   ordering, merge them.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   list, and &lt;math&gt; the time required to compare two elements.
mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a

-- | Given an ordering and two nonempty sequences ordered according to that
--   ordering, merge them
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   list, and &lt;math&gt; the time required to compare two elements.
mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]


-- | Implementation of Floyd-Warshall shortest path algorithm.
--   
--   See Wikipedia article for details:
--   <a>https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a>
module Algorithms.FloydWarshall

-- | Compute the index of an element in a given range.
mkIndex :: Num a => a -> (a, a) -> a

-- | Construct a weighted graph from &lt;math&gt; vertices, a max bound,
--   and a list of weighted edges.
mkGraph :: (Unbox a, Num a) => Int -> a -> [(Int, Int, a)] -> ST s (MVector s (a, Int))

-- | &lt;math&gt;
floydWarshall :: (Unbox a, Fractional a, Ord a) => Int -> MVector s (a, Int) -> ST s ()


module Algorithms.Graph.BFS

-- | Runs a BFS from the first vertex in the graph. The graph is given in
--   adjacency list representation.
--   
--   running time: &lt;math&gt;
bfs :: Foldable f => Int -> Vector (v, f Int) -> Tree v

-- | Runs a BFS from the first vertex in the graph. The graph is given in
--   adjacency list representation.
--   
--   running time: &lt;math&gt;
bfs' :: Foldable f => Int -> Vector (f Int) -> Tree Int


module Algorithms.LogarithmicMethod

-- | Represents an insertion-only data structure built from static data
--   structures.
--   
--   In particular, we maintain &lt;math&gt; static data structures of
--   sizes &lt;math&gt;, for &lt;math&gt;.
newtype InsertionOnly static a
InsertionOnly :: [Maybe (static a)] -> InsertionOnly static a

-- | Builds an empty structure
empty :: InsertionOnly static a
class LogarithmicMethodDS static a

-- | Create a new static data structure storing only one value.
singleton :: LogarithmicMethodDS static a => a -> static a

-- | Given a NonEmpty list of a's build a static a.
build :: LogarithmicMethodDS static a => NonEmpty a -> static a

-- | Merges two structurs of the same size. Has a default implementation
--   via build in case the static structure is Foldable1.
merge :: LogarithmicMethodDS static a => static a -> static a -> static a

-- | Merges two structurs of the same size. Has a default implementation
--   via build in case the static structure is Foldable1.
merge :: (LogarithmicMethodDS static a, Foldable1 static) => static a -> static a -> static a

-- | Inserts an element into the data structure
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the time required to
--   merge two data structures of size &lt;math&gt;.
insert :: LogarithmicMethodDS static a => a -> InsertionOnly static a -> InsertionOnly static a

-- | Given a decomposable query algorithm for the static structure, lift it
--   to a query algorithm on the insertion only structure.
--   
--   pre: (As indicated by the Monoid constraint), the query answer should
--   be decomposable. I.e. we should be able to anser the query on a set
--   &lt;math&gt; by answering the query on &lt;math&gt; and &lt;math&gt;
--   separately, and combining their results.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the query time on
--   the static structure.
queryWith :: Monoid m => (static a -> m) -> InsertionOnly static a -> m
instance forall k (static :: k -> *) (a :: k). GHC.Classes.Ord (static a) => GHC.Classes.Ord (Algorithms.LogarithmicMethod.InsertionOnly static a)
instance forall k (static :: k -> *) (a :: k). GHC.Classes.Eq (static a) => GHC.Classes.Eq (Algorithms.LogarithmicMethod.InsertionOnly static a)
instance forall k (static :: k -> *) (a :: k). GHC.Show.Show (static a) => GHC.Show.Show (Algorithms.LogarithmicMethod.InsertionOnly static a)
instance Algorithms.LogarithmicMethod.LogarithmicMethodDS static a => GHC.Base.Semigroup (Algorithms.LogarithmicMethod.InsertionOnly static a)
instance Algorithms.LogarithmicMethod.LogarithmicMethodDS static a => GHC.Base.Monoid (Algorithms.LogarithmicMethod.InsertionOnly static a)
instance GHC.Base.Functor static => GHC.Base.Functor (Algorithms.LogarithmicMethod.InsertionOnly static)
instance Data.Traversable.Traversable static => Data.Traversable.Traversable (Algorithms.LogarithmicMethod.InsertionOnly static)
instance Data.Foldable.Foldable static => Data.Foldable.Foldable (Algorithms.LogarithmicMethod.InsertionOnly static)


-- | Implementation of Knuth-Morris-Pratt String-searching algorithm. The
--   exposition is based on that of Goodrich and Tamassia in "Data
--   Structures and Algorithms in Java 2nd Edition".
module Algorithms.StringSearch.KMP

-- | Test if the first argument, the pattern p, occurs as a consecutive
--   subsequence in t.
--   
--   running time: &lt;math&gt;, where p has length &lt;math&gt; and t has
--   length &lt;math&gt;.
isSubStringOf :: (Eq a, Foldable p, Foldable t) => p a -> t a -> Maybe Int

-- | Test if the first argument, the pattern p, occurs as a consecutive
--   subsequence in t.
--   
--   running time: &lt;math&gt;, where p has length &lt;math&gt; and t has
--   length &lt;math&gt;.
kmpMatch :: Eq a => Vector a -> Vector a -> Maybe Int

-- | Constructs the failure function.
--   
--   running time: &lt;math&gt;.
buildFailureFunction :: forall a. Eq a => Vector a -> Vector Int


module Control.CanAquire

-- | Run a computation on something that can aquire i's.
runAcquire :: forall t a b. Traversable t => (forall s. CanAquire (I s a) a => t (I s a) -> b) -> t a -> b
class HasIndex i Int => CanAquire i a

-- | A value of type i can obtain something of type <tt>'a'</tt>
aquire :: CanAquire i a => i -> a
class HasIndex t i | t -> i

-- | Types that have an instance of this class can act as indices.
indexOf :: HasIndex t i => t -> i

-- | Replaces every element by an index. Returns the new traversable
--   containing only these indices, as well as a vector with the values.
--   (such that indexing in this value gives the original value).
replaceByIndex :: forall t a. Traversable t => t a -> (Vector a, t Int)

-- | Label each element with its index. Returns the new collection as well
--   as its size.
labelWithIndex :: Traversable t => t a -> (t (Int, a), Int)

-- | A type that can act as an Index.
data I (s :: *) a
instance forall s k (a :: k). GHC.Enum.Enum (Control.CanAquire.I s a)
instance forall s k (a :: k). GHC.Classes.Ord (Control.CanAquire.I s a)
instance forall s k (a :: k). GHC.Classes.Eq (Control.CanAquire.I s a)
instance forall k s (a :: k). GHC.Show.Show (Control.CanAquire.I s a)
instance forall k s (a :: k). Control.CanAquire.HasIndex (Control.CanAquire.I s a) GHC.Types.Int
instance Data.Reflection.Reifies s (Data.Vector.Vector a) => Control.CanAquire.CanAquire (Control.CanAquire.I s a) a


module Control.Monad.State.Persistent

-- | A State monad that can store earlier versions of the state.
data PersistentStateT s m a

-- | A State monad that can store earlier versions of the state.
type PersistentState s = PersistentStateT s Identity

-- | Create a snapshot of the current state and add it to the list of
--   states that we store.
store :: Monad m => PersistentStateT s m ()

-- | Run a persistentStateT, returns a triplet with the value, the last
--   state and a list of all states (including the last one) in
--   chronological order
runPersistentStateT :: Functor m => PersistentStateT s m a -> s -> m (a, s, [s])

-- | Run a persistentStateT, returns a triplet with the value, the last
--   state and a list of all states (including the last one) in
--   chronological order
runPersistentState :: PersistentState s a -> s -> (a, s, [s])
instance GHC.Base.Monad m => GHC.Base.Monad (Control.Monad.State.Persistent.PersistentStateT s m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Monad.State.Persistent.PersistentStateT s m)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Monad.State.Persistent.PersistentStateT s m)
instance GHC.Base.Monad m => Control.Monad.State.Class.MonadState s (Control.Monad.State.Persistent.PersistentStateT s m)


module Data.CircularList.Util

-- | Given a circular list, whose elements are in increasing order, insert
--   the new element into the Circular list in its sorted order.
--   
--   <pre>
--   &gt;&gt;&gt; insertOrd 1 C.empty
--   fromList [1]
--   
--   &gt;&gt;&gt; insertOrd 1 $ C.fromList [2]
--   fromList [2,1]
--   
--   &gt;&gt;&gt; insertOrd 2 $ C.fromList [1,3]
--   fromList [1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 31 ordList
--   fromList [5,6,10,20,30,31,1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 1 ordList
--   fromList [5,6,10,20,30,1,1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 4 ordList
--   fromList [5,6,10,20,30,1,2,3,4]
--   
--   &gt;&gt;&gt; insertOrd 11 ordList
--   fromList [5,6,10,11,20,30,1,2,3]
--   </pre>
insertOrd :: Ord a => a -> CList a -> CList a

-- | Insert an element into an increasingly ordered circular list, with
--   specified compare operator.
insertOrdBy :: (a -> a -> Ordering) -> a -> CList a -> CList a

-- | List version of insertOrdBy; i.e. the list contains the elements in
--   cirulcar order. Again produces a list that has the items in circular
--   order.
insertOrdBy' :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | Given a list of elements that is supposedly a a cyclic-shift of a list
--   of increasing items, find the splitting point. I.e. returns a pair of
--   lists (ys,zs) such that xs = zs ++ ys, and ys ++ zs is (supposedly) in
--   sorted order.
splitIncr :: (a -> a -> Ordering) -> [a] -> ([a], [a])

-- | Test if the circular list is a cyclic shift of the second list.
--   Running time: O(n), where n is the size of the smallest list
isShiftOf :: Eq a => CList a -> CList a -> Bool


module Data.Double.Approximate

-- | Relatively safe double floating-point type with a relative error
--   margin of 10 <a>ULPs</a> and an absolute margin around zero of
--   <tt>10*<a>epsilon</a></tt>.
--   
--   Warning: All numbers within <tt>10*<a>epsilon</a></tt> of zero will be
--   considered zero.
--   
--   <pre>
--   &gt;&gt;&gt; m_epsilon * 10
--   2.220446049250313e-15
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; realToFrac (m_epsilon * 10) == (0::SafeDouble)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; realToFrac (m_epsilon * 9) == (0::SafeDouble)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 1e-20 == (5e-20 :: Double)
--   False
--   
--   &gt;&gt;&gt; 1e-20 == (5e-20 :: SafeDouble)
--   True
--   </pre>
--   
--   <a>pi</a> and <a>sin</a> are approximations:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi
--   1.2246467991473532e-16
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: Double)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: SafeDouble)
--   True
--   </pre>
type SafeDouble = DoubleRelAbs 10 10

-- | Custom double floating-point type with a relative error margin of
--   <tt>rel</tt> number of <a>ULPs</a> and an absolute error margin of
--   <tt>abs</tt> times <a>epsilon</a>.
--   
--   The relative error margin is the primary tool for good numerical
--   robustness and can relatively safely be set to a high number such as
--   100. The absolute error margin is a last ditch attempt at fixing
--   broken algorithms and dramatically limits the resolution around zero.
--   If possible, use a low absolute error margin.
newtype DoubleRelAbs (abs :: Nat) (rel :: Nat)
DoubleRelAbs :: Double -> DoubleRelAbs (abs :: Nat) (rel :: Nat)
instance Control.DeepSeq.NFData (Data.Double.Approximate.DoubleRelAbs abs rel)
instance System.Random.Random (Data.Double.Approximate.DoubleRelAbs abs rel)
instance (GHC.TypeNats.KnownNat abs, GHC.TypeNats.KnownNat rel) => GHC.Real.RealFrac (Data.Double.Approximate.DoubleRelAbs abs rel)
instance (GHC.TypeNats.KnownNat abs, GHC.TypeNats.KnownNat rel) => GHC.Float.RealFloat (Data.Double.Approximate.DoubleRelAbs abs rel)
instance (GHC.TypeNats.KnownNat abs, GHC.TypeNats.KnownNat rel) => GHC.Real.Real (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Real.Fractional (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Float.Floating (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Enum.Enum (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Num.Num (Data.Double.Approximate.DoubleRelAbs abs rel)
instance (GHC.TypeNats.KnownNat abs, GHC.TypeNats.KnownNat rel) => GHC.Classes.Eq (Data.Double.Approximate.DoubleRelAbs abs rel)
instance (GHC.TypeNats.KnownNat abs, GHC.TypeNats.KnownNat rel) => GHC.Classes.Ord (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Show.Show (Data.Double.Approximate.DoubleRelAbs abs rel)
instance GHC.Read.Read (Data.Double.Approximate.DoubleRelAbs abs rel)

module Data.Double.Shaman

-- | Double-precision floating point numbers with error-bounds.
--   
--   Some digits can be represented exactly and have essentially an
--   infinitely number of significant digits:
--   
--   <pre>
--   &gt;&gt;&gt; significativeDigits 1
--   Infinity
--   </pre>
--   
--   Some fractional numbers can also be represented exactly:
--   
--   <pre>
--   &gt;&gt;&gt; significativeDigits 0.5
--   Infinity
--   </pre>
--   
--   Other numbers are merely approximations:
--   
--   <pre>
--   &gt;&gt;&gt; significativeDigits 0.1
--   16.255619765854984
--   </pre>
--   
--   Pi is an irrational number so we can't represent it with infinite
--   precision:
--   
--   <pre>
--   &gt;&gt;&gt; significativeDigits pi
--   15.849679651557175
--   </pre>
--   
--   <tt>sin pi</tt> should theoretically be zero but we cannot do better
--   than saying it is near zero:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi
--   1.2246467991473532e-16
--   </pre>
--   
--   The error margins are greater than value itself so we have no
--   significant digits:
--   
--   <pre>
--   &gt;&gt;&gt; significativeDigits (sin pi)
--   0.0
--   </pre>
--   
--   Since 'near zero' is not zero, the following fails when using Doubles:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: Double)
--   False
--   </pre>
--   
--   Equality testing for Shaman numbers tests whether the two intervals
--   overlap:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: Shaman)
--   True
--   </pre>
data Shaman

-- | Number of significant bits (base 2).
significativeBits :: Shaman -> Double

-- | Number of significant digits (base 10).
significativeDigits :: Shaman -> Double

-- | Double-precision floating point numbers that throw exceptions if the
--   accumulated errors grow large enough to cause unstable branching.
--   
--   If <tt>SDouble n</tt> works without throwing any exceptions, it'll be
--   safe to use <tt>DoubleRelAbs n 0</tt> instead for a sizable
--   performance boost.
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: SDouble 0)
--   *** Exception: Insufficient precision.
--   ...
--   </pre>
--   
--   <tt>SDouble 0</tt> failed so <tt>DoubleRelAbs 0 0</tt> will lead to an
--   unstable branch. In other words, it'll return <tt>False</tt> when it
--   should have returned <tt>True</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: DoubleRelAbs 0 0)
--   False
--   </pre>
--   
--   Comparing to within 1 ULP stabalizes the branch:
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: SDouble 1)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sin pi == (0 :: DoubleRelAbs 1 0)
--   True
--   </pre>
data SDouble (n :: Nat)
instance GHC.TypeNats.KnownNat n => GHC.Float.RealFloat (Data.Double.Shaman.SDouble n)
instance GHC.TypeNats.KnownNat n => GHC.Real.RealFrac (Data.Double.Shaman.SDouble n)
instance GHC.TypeNats.KnownNat n => GHC.Real.Real (Data.Double.Shaman.SDouble n)
instance GHC.Float.Floating (Data.Double.Shaman.SDouble n)
instance GHC.Real.Fractional (Data.Double.Shaman.SDouble n)
instance GHC.Num.Num (Data.Double.Shaman.SDouble n)
instance GHC.Show.Show (Data.Double.Shaman.SDouble n)
instance GHC.Read.Read (Data.Double.Shaman.SDouble n)
instance GHC.TypeNats.KnownNat n => GHC.Classes.Eq (Data.Double.Shaman.SDouble n)
instance GHC.TypeNats.KnownNat n => GHC.Classes.Ord (Data.Double.Shaman.SDouble n)
instance GHC.Show.Show Data.Double.Shaman.Shaman
instance GHC.Read.Read Data.Double.Shaman.Shaman
instance GHC.Num.Num Data.Double.Shaman.Shaman
instance GHC.Real.Fractional Data.Double.Shaman.Shaman
instance GHC.Float.Floating Data.Double.Shaman.Shaman
instance GHC.Real.Real Data.Double.Shaman.Shaman
instance GHC.Real.RealFrac Data.Double.Shaman.Shaman
instance GHC.Float.RealFloat Data.Double.Shaman.Shaman
instance GHC.Classes.Eq Data.Double.Shaman.Shaman
instance GHC.Classes.Ord Data.Double.Shaman.Shaman


module Data.DynamicOrd

-- | Values of type '<tt>a</tt>' in our dynamically constructed <a>Ord</a>
--   instance
newtype O (s :: *) (a :: *)
O :: a -> O (s :: *) (a :: *)
[runO] :: O (s :: *) (a :: *) -> a

-- | An Ord Dictionary
newtype OrdDict a
OrdDict :: (a -> a -> Ordering) -> OrdDict a
[compare_] :: OrdDict a -> a -> a -> Ordering

-- | Run a computation with a given ordering
withOrd :: (a -> a -> Ordering) -> (forall s. Reifies s (OrdDict a) => O s b) -> b

-- | Lifts a container f whose values (of type a) depend on '<tt>s</tt>'
--   into a more general computation in that produces a '<tt>f a</tt>'
--   (depending on s).
--   
--   running time: &lt;math&gt;
extractOrd1 :: f (O s a) -> O s (f a)

-- | Introduce dynamic order in a container '<tt>f</tt>'.
--   
--   running time: &lt;math&gt;
introOrd1 :: f a -> f (O s a)

-- | Lifts a function that works on a container '<tt>f</tt>' of
--   orderable-things into one that works on dynamically ordered ones.
liftOrd1 :: (f (O s a) -> g (O s a)) -> f a -> O s (g a)

-- | Lifts a container f whose keys (of type k) depend on '<tt>s</tt>' into
--   a more general computation in that produces a <tt>`f k v`</tt>
--   (depending on s).
--   
--   running time: &lt;math&gt;
extractOrd2 :: f (O s k) v -> O s (f k v)

-- | Introduce dynamic order in a container '<tt>f</tt>' that has keys of
--   type k.
--   
--   running time: &lt;math&gt;
introOrd2 :: f k v -> f (O s k) v
instance GHC.Show.Show a => GHC.Show.Show (Data.DynamicOrd.O s a)
instance Data.Reflection.Reifies s (Data.DynamicOrd.OrdDict a) => GHC.Classes.Eq (Data.DynamicOrd.O s a)
instance (GHC.Classes.Eq (Data.DynamicOrd.O s a), Data.Reflection.Reifies s (Data.DynamicOrd.OrdDict a)) => GHC.Classes.Ord (Data.DynamicOrd.O s a)


-- | A pair-like data type to represent a <a>core</a> type that has extra
--   information as well.
module Data.Ext

-- | Our Ext type that represents the core datatype core extended with
--   extra information of type <a>extra</a>.
data core :+ extra
(:+) :: core -> extra -> (:+) core extra
infixr 1 :+
infixr 1 :+

-- | Access the core of an extended value.
_core :: (core :+ extra) -> core

-- | Access the extra part of an extended value.
_extra :: (core :+ extra) -> extra

-- | Lens access to the core of an extended value.
core :: Lens (core :+ extra) (core' :+ extra) core core'

-- | Lens access to the extra part of an extended value.
extra :: Lens (core :+ extra) (core :+ extra') extra extra'

-- | Tag a value with the unit type.
ext :: a -> a :+ ()
instance (Control.DeepSeq.NFData core, Control.DeepSeq.NFData extra) => Control.DeepSeq.NFData (core Data.Ext.:+ extra)
instance GHC.Generics.Generic (core Data.Ext.:+ extra)
instance (GHC.Enum.Bounded core, GHC.Enum.Bounded extra) => GHC.Enum.Bounded (core Data.Ext.:+ extra)
instance (GHC.Classes.Ord core, GHC.Classes.Ord extra) => GHC.Classes.Ord (core Data.Ext.:+ extra)
instance (GHC.Classes.Eq core, GHC.Classes.Eq extra) => GHC.Classes.Eq (core Data.Ext.:+ extra)
instance (GHC.Read.Read core, GHC.Read.Read extra) => GHC.Read.Read (core Data.Ext.:+ extra)
instance (GHC.Show.Show core, GHC.Show.Show extra) => GHC.Show.Show (core Data.Ext.:+ extra)
instance Data.Bifunctor.Bifunctor (Data.Ext.:+)
instance Data.Functor.Bind.Class.Biapply (Data.Ext.:+)
instance Data.Biapplicative.Biapplicative (Data.Ext.:+)
instance Data.Bifoldable.Bifoldable (Data.Ext.:+)
instance Data.Bitraversable.Bitraversable (Data.Ext.:+)
instance Data.Semigroup.Foldable.Class.Bifoldable1 (Data.Ext.:+)
instance Data.Semigroup.Traversable.Class.Bitraversable1 (Data.Ext.:+)
instance (GHC.Base.Semigroup core, GHC.Base.Semigroup extra) => GHC.Base.Semigroup (core Data.Ext.:+ extra)
instance (Data.Aeson.Types.ToJSON.ToJSON core, Data.Aeson.Types.ToJSON.ToJSON extra) => Data.Aeson.Types.ToJSON.ToJSON (core Data.Ext.:+ extra)
instance (Data.Aeson.Types.FromJSON.FromJSON core, Data.Aeson.Types.FromJSON.FromJSON extra) => Data.Aeson.Types.FromJSON.FromJSON (core Data.Ext.:+ extra)
instance (Test.QuickCheck.Arbitrary.Arbitrary c, Test.QuickCheck.Arbitrary.Arbitrary e) => Test.QuickCheck.Arbitrary.Arbitrary (c Data.Ext.:+ e)


module Data.CircularSeq

-- | Nonempty circular sequence
data CSeq a

-- | smart constructor that automatically balances the seq
cseq :: Seq a -> a -> Seq a -> CSeq a

-- | <i>O(1)</i> CSeq with exactly one element.
singleton :: a -> CSeq a

-- | builds a CSeq
fromNonEmpty :: NonEmpty a -> CSeq a

-- | <i>O(n)</i> Convert from a list to a CSeq.
--   
--   Warning: the onus is on the user to ensure that their list is not
--   empty, otherwise all bets are off!
fromList :: [a] -> CSeq a

-- | Gets the focus of the CSeq.
--   
--   running time: O(1)
focus :: CSeq a -> a

-- | Access the i^th item (w.r.t the focus; elements numbered in increasing
--   order towards the right) in the CSeq (indices modulo n).
--   
--   running time: &lt;math&gt;
--   
--   <pre>
--   &gt;&gt;&gt; index (fromList [0..5]) 1
--   1
--   
--   &gt;&gt;&gt; index (fromList [0..5]) 2
--   2
--   
--   &gt;&gt;&gt; index (fromList [0..5]) 5
--   5
--   
--   &gt;&gt;&gt; index (fromList [0..5]) 10
--   4
--   
--   &gt;&gt;&gt; index (fromList [0..5]) 6
--   0
--   
--   &gt;&gt;&gt; index (fromList [0..5]) (-1)
--   5
--   
--   &gt;&gt;&gt; index (fromList [0..5]) (-6)
--   0
--   </pre>
index :: CSeq a -> Int -> a

-- | Adjusts the i^th element w.r.t the focus in the CSeq
--   
--   running time: &lt;math&gt;
--   
--   <pre>
--   &gt;&gt;&gt; adjust (const 1000) 2 (fromList [0..5])
--   CSeq [0,1,1000,3,4,5]
--   </pre>
adjust :: (a -> a) -> Int -> CSeq a -> CSeq a

-- | Access the ith item in the CSeq (w.r.t the focus) as a lens
item :: Int -> Lens' (CSeq a) a

-- | rotates the focus to the left
--   
--   running time: O(1) (amortized)
--   
--   <pre>
--   &gt;&gt;&gt; rotateL $ fromList [3,4,5,1,2]
--   CSeq [2,3,4,5,1]
--   
--   &gt;&gt;&gt; mapM_ print . take 5 $ iterate rotateL $ fromList [1..5]
--   CSeq [1,2,3,4,5]
--   CSeq [5,1,2,3,4]
--   CSeq [4,5,1,2,3]
--   CSeq [3,4,5,1,2]
--   CSeq [2,3,4,5,1]
--   </pre>
rotateL :: CSeq a -> CSeq a

-- | rotates one to the right
--   
--   running time: O(1) (amortized)
--   
--   <pre>
--   &gt;&gt;&gt; rotateR $ fromList [3,4,5,1,2]
--   CSeq [4,5,1,2,3]
--   </pre>
rotateR :: CSeq a -> CSeq a

-- | Rotates i elements to the left.
--   
--   pre: 0 &lt;= i &lt; n
--   
--   running time: &lt;math&gt; amoritzed
--   
--   <pre>
--   &gt;&gt;&gt; rotateNL 0 $ fromList [1..5]
--   CSeq [1,2,3,4,5]
--   
--   &gt;&gt;&gt; rotateNL 1 $ fromList [1..5]
--   CSeq [5,1,2,3,4]
--   
--   &gt;&gt;&gt; rotateNL 2 $ fromList [1..5]
--   CSeq [4,5,1,2,3]
--   
--   &gt;&gt;&gt; rotateNL 3 $ fromList [1..5]
--   CSeq [3,4,5,1,2]
--   
--   &gt;&gt;&gt; rotateNL 4 $ fromList [1..5]
--   CSeq [2,3,4,5,1]
--   </pre>
rotateNL :: Int -> CSeq a -> CSeq a

-- | Rotates i elements to the right.
--   
--   pre: 0 &lt;= i &lt; n
--   
--   running time: &lt;math&gt; amortized
--   
--   <pre>
--   &gt;&gt;&gt; rotateNR 0 $ fromList [1..5]
--   CSeq [1,2,3,4,5]
--   
--   &gt;&gt;&gt; rotateNR 1 $ fromList [1..5]
--   CSeq [2,3,4,5,1]
--   
--   &gt;&gt;&gt; rotateNR 4 $ fromList [1..5]
--   CSeq [5,1,2,3,4]
--   </pre>
rotateNR :: Int -> CSeq a -> CSeq a

-- | All elements, starting with the focus, going to the right
rightElements :: CSeq a -> Seq a

-- | All elements, starting with the focus, going to the left
--   
--   <pre>
--   &gt;&gt;&gt; leftElements $ fromList [3,4,5,1,2]
--   fromList [3,2,1,5,4]
--   </pre>
leftElements :: CSeq a -> Seq a

-- | Convert to a single Seq, starting with the focus.
asSeq :: CSeq a -> Seq a

-- | Label the elements with indices.
--   
--   <pre>
--   &gt;&gt;&gt; withIndices $ fromList [0..5]
--   CSeq [0 :+ 0,1 :+ 1,2 :+ 2,3 :+ 3,4 :+ 4,5 :+ 5]
--   </pre>
withIndices :: CSeq a -> CSeq (Int :+ a)

-- | Reverses the direction of the CSeq
--   
--   running time: &lt;math&gt;
--   
--   <pre>
--   &gt;&gt;&gt; reverseDirection $ fromList [1..5]
--   CSeq [1,5,4,3,2]
--   </pre>
reverseDirection :: CSeq a -> CSeq a

-- | All rotations, the input CSeq is the focus.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print . allRotations $ fromList [1..5]
--   CSeq [1,2,3,4,5]
--   CSeq [2,3,4,5,1]
--   CSeq [3,4,5,1,2]
--   CSeq [4,5,1,2,3]
--   CSeq [5,1,2,3,4]
--   </pre>
allRotations :: CSeq a -> CSeq (CSeq a)

-- | Finds an element in the CSeq
--   
--   <pre>
--   &gt;&gt;&gt; findRotateTo (== 3) $ fromList [1..5]
--   Just (CSeq [3,4,5,1,2])
--   
--   &gt;&gt;&gt; findRotateTo (== 7) $ fromList [1..5]
--   Nothing
--   </pre>
findRotateTo :: (a -> Bool) -> CSeq a -> Maybe (CSeq a)

-- | Rotate to a specific element in the CSeq.
rotateTo :: Eq a => a -> CSeq a -> Maybe (CSeq a)

-- | "Left zip": zip the two CLists, pairing up every element in the *left*
--   list with its corresponding element in the right list. If there are
--   more items in the right clist they are discarded.
zipLWith :: (a -> b -> c) -> CSeq a -> CSeq b -> CSeq c

-- | see 'zipLWith
zipL :: CSeq a -> CSeq b -> CSeq (a, b)

-- | same as zipLWith but with three items
zip3LWith :: (a -> b -> c -> d) -> CSeq a -> CSeq b -> CSeq c -> CSeq d

-- | Given a circular seq, whose elements are in increasing order, insert
--   the new element into the Circular seq in its sorted order.
--   
--   <pre>
--   &gt;&gt;&gt; insertOrd 1 $ fromList [2]
--   CSeq [2,1]
--   
--   &gt;&gt;&gt; insertOrd 2 $ fromList [1,3]
--   CSeq [1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 31 ordList
--   CSeq [5,6,10,20,30,31,1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 1 ordList
--   CSeq [5,6,10,20,30,1,1,2,3]
--   
--   &gt;&gt;&gt; insertOrd 4 ordList
--   CSeq [5,6,10,20,30,1,2,3,4]
--   
--   &gt;&gt;&gt; insertOrd 11 ordList
--   CSeq [5,6,10,11,20,30,1,2,3]
--   </pre>
--   
--   running time: &lt;math&gt;
insertOrd :: Ord a => a -> CSeq a -> CSeq a

-- | Insert an element into an increasingly ordered circular list, with
--   specified compare operator.
--   
--   running time: &lt;math&gt;
insertOrdBy :: (a -> a -> Ordering) -> a -> CSeq a -> CSeq a

-- | Test if the circular list is a cyclic shift of the second list. We
--   have that
--   
--   <pre>
--   (xs `isShiftOf` ys) == (xs `elem` allRotations (ys :: CSeq Int))
--   </pre>
--   
--   Running time: &lt;math&gt;, where &lt;math&gt; and &lt;math&gt; are
--   the sizes of the lists.
isShiftOf :: Eq a => CSeq a -> CSeq a -> Bool
instance GHC.Generics.Generic (Data.CircularSeq.CSeq a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.CircularSeq.CSeq a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CircularSeq.CSeq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.CircularSeq.CSeq a)
instance GHC.Read.Read a => GHC.Read.Read (Data.CircularSeq.CSeq a)
instance Data.Traversable.Traversable Data.CircularSeq.CSeq
instance Data.Semigroup.Foldable.Class.Foldable1 Data.CircularSeq.CSeq
instance Data.Foldable.Foldable Data.CircularSeq.CSeq
instance GHC.Base.Functor Data.CircularSeq.CSeq
instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.CircularSeq.CSeq a)


-- | Defines a data type for representing intersections. Mostly useful for
--   the more geometric types.
module Data.Intersection

-- | A simple data type expressing that there are no intersections
data NoIntersection
NoIntersection :: NoIntersection

-- | The result of interesecting two geometries is a CoRec,
type Intersection g h = CoRec Identity (IntersectionOf g h)

-- | The type family specifying the list of possible result types of an
--   intersection.
type family IntersectionOf g h :: [*]

-- | Helper to produce a corec
coRec :: a ∈ as => a -> CoRec Identity as
class HasIntersectionWith g h

-- | g <a>intersects</a> h <a>=</a> The intersection of g and h is
--   non-empty.
--   
--   The default implementation computes the intersection of g and h, and
--   uses nonEmptyIntersection to determine if the intersection is
--   non-empty.
intersects :: HasIntersectionWith g h => g -> h -> Bool

-- | g <a>intersects</a> h <a>=</a> The intersection of g and h is
--   non-empty.
--   
--   The default implementation computes the intersection of g and h, and
--   uses nonEmptyIntersection to determine if the intersection is
--   non-empty.
intersects :: (HasIntersectionWith g h, IsIntersectableWith g h) => g -> h -> Bool

-- | Class relationship between intersectable geometric objects.
class HasIntersectionWith g h => IsIntersectableWith g h
intersect :: IsIntersectableWith g h => g -> h -> Intersection g h

-- | Helper to implement <a>intersects</a>.
nonEmptyIntersection :: IsIntersectableWith g h => proxy g -> proxy h -> Intersection g h -> Bool

-- | Helper to implement <a>intersects</a>.
nonEmptyIntersection :: (IsIntersectableWith g h, NoIntersection ∈ IntersectionOf g h, RecApplicative (IntersectionOf g h)) => proxy g -> proxy h -> Intersection g h -> Bool

-- | When using IntersectionOf we may need some constraints that are always
--   true anyway.
type AlwaysTrueIntersection g h = RecApplicative (IntersectionOf g h)

-- | Returns True iff the result is *not* a NoIntersection
defaultNonEmptyIntersection :: forall g h proxy. (NoIntersection ∈ IntersectionOf g h, RecApplicative (IntersectionOf g h)) => proxy g -> proxy h -> Intersection g h -> Bool
instance GHC.Classes.Ord Data.Intersection.NoIntersection
instance GHC.Classes.Eq Data.Intersection.NoIntersection
instance GHC.Read.Read Data.Intersection.NoIntersection
instance GHC.Show.Show Data.Intersection.NoIntersection


module Data.LSeq

-- | LSeq n a certifies that the sequence has *at least* n items
data LSeq (n :: Nat) a

-- | The empty sequence.
pattern EmptyL :: LSeq n a

-- | A bidirectional pattern synonym viewing the front of a non-empty
--   sequence.
pattern (:<|) :: a -> LSeq n a -> LSeq (1 + n) a

-- | A unidirectional pattern synonym viewing the front of a non-empty
--   sequence.
pattern (:<<) :: a -> LSeq 0 a -> LSeq n a

-- | A bidirectional pattern synonym viewing the rear of a non-empty
--   sequence.
pattern (:|>) :: forall n a. LSeq n a -> a -> LSeq (1 + n) a
infixr 5 :<|
infixr 5 :<<
infixl 5 :|>

-- | &lt;math&gt; Convert to a sequence by dropping the type-level size.
toSeq :: LSeq n a -> Seq a

-- | &lt;math&gt; The empty sequence.
empty :: LSeq 0 a

-- | &lt;math&gt;. Create an l-sequence from a finite list of elements.
fromList :: Foldable f => f a -> LSeq 0 a

-- | &lt;math&gt;. Create an l-sequence from a non-empty list.
fromNonEmpty :: NonEmpty a -> LSeq 1 a

-- | &lt;math&gt;. Create an l-sequence from a sequence of elements.
fromSeq :: Seq a -> LSeq 0 a

-- | &lt;math&gt; Add an element to the left end of a sequence. Mnemonic: a
--   triangle with the single element at the pointy end.
(<|) :: a -> LSeq n a -> LSeq (1 + n) a
infixr 5 <|

-- | &lt;math&gt; Add an element to the right end of a sequence. Mnemonic:
--   a triangle with the single element at the pointy end.
(|>) :: LSeq n a -> a -> LSeq (1 + n) a
infixl 5 |>

-- | &lt;math&gt; Concatenate two sequences.
(><) :: LSeq n a -> LSeq m a -> LSeq (n + m) a
infix 5 ><

-- | &lt;math&gt; Prove a sequence has at least <tt>n</tt> elements.
--   
--   <pre>
--   &gt;&gt;&gt; eval @3 (fromList [1,2,3])
--   Just (LSeq (fromList [1,2,3]))
--   
--   &gt;&gt;&gt; eval @3 (fromList [1,2])
--   Nothing
--   
--   &gt;&gt;&gt; eval @3 (fromList [1..10])
--   Just (LSeq (fromList [1,2,3,4,5,6,7,8,9,10]))
--   </pre>
eval :: forall n m a. KnownNat n => LSeq m a -> Maybe (LSeq n a)

-- | Implementatio nof eval' that takes an explicit proxy.
eval' :: forall proxy n m a. KnownNat n => proxy n -> LSeq m a -> Maybe (LSeq n a)

-- | &lt;math&gt; Get the element with index i, counting from the left and
--   starting at 0.
index :: LSeq n a -> Int -> a

-- | &lt;math&gt; Update the element at the specified position. If the
--   position is out of range, the original sequence is returned. adjust
--   can lead to poor performance and even memory leaks, because it does
--   not force the new value before installing it in the sequence. adjust'
--   should usually be preferred.
adjust :: (a -> a) -> Int -> LSeq n a -> LSeq n a

-- | &lt;math&gt; The partition function takes a predicate p and a sequence
--   xs and returns sequences of those elements which do and do not satisfy
--   the predicate.
partition :: (a -> Bool) -> LSeq n a -> (LSeq 0 a, LSeq 0 a)

-- | A generalization of <a>fmap</a>, <a>mapWithIndex</a> takes a mapping
--   function that also depends on the element's index, and applies it to
--   every element in the sequence.
mapWithIndex :: (Int -> a -> b) -> LSeq n a -> LSeq n b

-- | &lt;math&gt;. The first <tt>i</tt> elements of a sequence. If
--   <tt>i</tt> is negative, <tt><a>take</a> i s</tt> yields the empty
--   sequence. If the sequence contains fewer than <tt>i</tt> elements, the
--   whole sequence is returned.
take :: Int -> LSeq n a -> LSeq 0 a

-- | &lt;math&gt;. Elements of a sequence after the first <tt>i</tt>. If
--   <tt>i</tt> is negative, <tt><a>drop</a> i s</tt> yields the whole
--   sequence. If the sequence contains fewer than <tt>i</tt> elements, the
--   empty sequence is returned.
drop :: Int -> LSeq n a -> LSeq 0 a

-- | &lt;math&gt;. <a>unstableSort</a> sorts the specified <a>LSeq</a> by
--   the natural ordering of its elements, but the sort is not stable. This
--   algorithm is frequently faster and uses less memory than <a>sort</a>.
unstableSort :: Ord a => LSeq n a -> LSeq n a

-- | &lt;math&gt;. A generalization of <a>unstableSort</a>,
--   <a>unstableSortBy</a> takes an arbitrary comparator and sorts the
--   specified sequence. The sort is not stable. This algorithm is
--   frequently faster and uses less memory than <a>sortBy</a>.
unstableSortBy :: (a -> a -> Ordering) -> LSeq n a -> LSeq n a

-- | Gets the first element of the LSeq
--   
--   <pre>
--   &gt;&gt;&gt; head $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]
--   1
--   </pre>
head :: LSeq (1 + n) a -> a

-- | Get the LSeq without its first element -- &gt;&gt;&gt; head $
--   forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3] LSeq (fromList [2,3])
tail :: LSeq (1 + n) a -> LSeq n a

-- | Get the last element of the LSeq
--   
--   <pre>
--   &gt;&gt;&gt; last $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]
--   3
--   </pre>
last :: LSeq (1 + n) a -> a

-- | The sequence without its last element
--   
--   <pre>
--   &gt;&gt;&gt; init $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]
--   LSeq (fromList [1,2])
--   </pre>
init :: LSeq (1 + n) a -> LSeq n a

-- | appends two sequences.
append :: LSeq n a -> LSeq m a -> LSeq (n + m) a

-- | Reverses the sequence.
reverse :: LSeq n a -> LSeq n a

-- | View of the left end of a sequence.
data ViewL n a
[:<] :: a -> LSeq n a -> ViewL (1 + n) a
infixr 5 :<

-- | ( O(1) ). Analyse the left end of a sequence.
viewl :: LSeq (1 + n) a -> ViewL (1 + n) a

-- | View of the right end of a sequence.
data ViewR n a
[:>] :: LSeq n a -> a -> ViewR (1 + n) a
infixl 5 :>

-- | &lt;math&gt;. Analyse the right end of a sequence.
viewr :: LSeq (1 + n) a -> ViewR (1 + n) a

-- | Zips two equal length LSeqs
zipWith :: (a -> b -> c) -> LSeq n a -> LSeq n b -> LSeq n c

-- | Promises that the length of this LSeq is actually n. This is not
--   checked.
--   
--   This function should be a noop
promise :: forall n m a. LSeq m a -> LSeq n a

-- | Forces the first n elements of the LSeq
forceLSeq :: KnownNat n => proxy n -> LSeq m a -> LSeq n a
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.LSeq.LSeq n a)
instance GHC.Generics.Generic (Data.LSeq.LSeq n a)
instance Data.Traversable.Traversable (Data.LSeq.LSeq n)
instance GHC.Base.Functor (Data.LSeq.LSeq n)
instance Data.Foldable.Foldable (Data.LSeq.LSeq n)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.LSeq.LSeq n a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.LSeq.LSeq n a)
instance GHC.Read.Read a => GHC.Read.Read (Data.LSeq.LSeq n a)
instance GHC.Show.Show a => GHC.Show.Show (Data.LSeq.LSeq n a)
instance GHC.Show.Show a => GHC.Show.Show (Data.LSeq.ViewL n a)
instance GHC.Show.Show a => GHC.Show.Show (Data.LSeq.ViewR n a)
instance GHC.Base.Semigroup (Data.LSeq.ViewR n a)
instance GHC.Base.Functor (Data.LSeq.ViewR n)
instance Data.Foldable.Foldable (Data.LSeq.ViewR n)
instance Data.Traversable.Traversable (Data.LSeq.ViewR n)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.LSeq.ViewR n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.LSeq.ViewR n a)
instance GHC.Base.Semigroup (Data.LSeq.ViewL n a)
instance GHC.Base.Functor (Data.LSeq.ViewL n)
instance Data.Foldable.Foldable (Data.LSeq.ViewL n)
instance Data.Traversable.Traversable (Data.LSeq.ViewL n)
instance (1 GHC.TypeNats.<= n) => Data.Semigroup.Foldable.Class.Foldable1 (Data.LSeq.ViewL n)
instance (1 GHC.TypeNats.<= n) => Data.Semigroup.Traversable.Class.Traversable1 (Data.LSeq.ViewL n)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.LSeq.ViewL n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.LSeq.ViewL n a)
instance GHC.Base.Semigroup (Data.LSeq.LSeq n a)
instance GHC.Base.Monoid (Data.LSeq.LSeq 0 a)
instance (GHC.TypeNats.KnownNat n, Test.QuickCheck.Arbitrary.Arbitrary a) => Test.QuickCheck.Arbitrary.Arbitrary (Data.LSeq.LSeq n a)
instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.LSeq.LSeq n a)
instance Data.Aeson.Types.FromJSON.FromJSON a => Data.Aeson.Types.FromJSON.FromJSON (Data.LSeq.LSeq n a)
instance Control.Lens.At.Ixed (Data.LSeq.LSeq n a)
instance (1 GHC.TypeNats.<= n) => Data.Semigroup.Foldable.Class.Foldable1 (Data.LSeq.LSeq n)
instance (1 GHC.TypeNats.<= n) => Data.Semigroup.Traversable.Class.Traversable1 (Data.LSeq.LSeq n)


module Data.List.Alternating

-- | A (non-empty) alternating list of <tt>a</tt>'s and <tt>b</tt>'s
data Alternating a b
Alternating :: a -> [b :+ a] -> Alternating a b

-- | Computes a b with all its neighbours
--   
--   <pre>
--   &gt;&gt;&gt; withNeighbours (Alternating 0 ['a' :+ 1, 'b' :+ 2, 'c' :+ 3])
--   [(0,'a' :+ 1),(1,'b' :+ 2),(2,'c' :+ 3)]
--   </pre>
withNeighbours :: Alternating a b -> [(a, b :+ a)]

-- | Generic merging scheme that merges two Alternatings and applies the
--   function '<tt>f</tt>', with the current/new value at every event. So
--   note that if the alternating consists of 'Alternating a0 [t1 :+ a1]'
--   then the function is applied to a1, not to a0 (i.e. every value ai is
--   considered alive on the interval [ti,t(i+1))
--   
--   <pre>
--   &gt;&gt;&gt; let odds  = Alternating "a" [3 :+ "c", 5 :+ "e", 7 :+ "g"]
--   
--   &gt;&gt;&gt; let evens = Alternating "b" [4 :+ "d", 6 :+ "f", 8 :+ "h"]
--   
--   &gt;&gt;&gt; mergeAlternating (\_ a b -&gt; a &lt;&gt; b) odds evens
--   [3 :+ "cb",4 :+ "cd",5 :+ "ed",6 :+ "ef",7 :+ "gf",8 :+ "gh"]
--   
--   &gt;&gt;&gt; mergeAlternating (\t a b -&gt; if t `mod` 2 == 0 then a else b) odds evens
--   [3 :+ "b",4 :+ "c",5 :+ "d",6 :+ "e",7 :+ "f",8 :+ "g"]
--   
--   &gt;&gt;&gt; mergeAlternating (\_ a b -&gt; a &lt;&gt; b) odds (Alternating "b" [0 :+ "d", 5 :+ "e", 8 :+ "h"])
--   [0 :+ "ad",3 :+ "cd",5 :+ "ee",7 :+ "ge",8 :+ "gh"]
--   </pre>
mergeAlternating :: Ord t => (t -> a -> b -> c) -> Alternating a t -> Alternating b t -> [t :+ c]

-- | Adds additional t-values in the alternating, (in sorted order). I.e.
--   if we insert a "breakpoint" at time t the current '<tt>a</tt>' value
--   is used at that time.
--   
--   <pre>
--   &gt;&gt;&gt; insertBreakPoints [0,2,4,6,8,10] $ Alternating "a" [3 :+ "c", 5 :+ "e", 7 :+ "g"]
--   Alternating "a" [0 :+ "a",2 :+ "a",3 :+ "c",4 :+ "c",5 :+ "e",6 :+ "e",7 :+ "g",8 :+ "g",10 :+ "g"]
--   </pre>
insertBreakPoints :: Ord t => [t] -> Alternating a t -> Alternating a t

-- | Reverses an alternating list.
--   
--   <pre>
--   &gt;&gt;&gt; reverse $ Alternating "a" [3 :+ "c", 5 :+ "e", 7 :+ "g"]
--   Alternating "g" [7 :+ "e",5 :+ "c",3 :+ "a"]
--   </pre>
reverse :: Alternating a b -> Alternating a b
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.List.Alternating.Alternating a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.List.Alternating.Alternating a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.List.Alternating.Alternating a b)
instance Data.Bifunctor.Bifunctor Data.List.Alternating.Alternating
instance Data.Bifoldable.Bifoldable Data.List.Alternating.Alternating
instance Data.Bitraversable.Bitraversable Data.List.Alternating.Alternating


module Data.List.Set

-- | A Set of <tt>a</tt>'s, implemented using a simple list. The only
--   advantage of this implementation over <a>Set</a> from containers is
--   that most operations require only <tt>'Eq a'</tt> rather than <tt>'Ord
--   a'</tt>.
data Set a

-- | Creates a singleton set.
singleton :: a -> Set a

-- | &lt;math&gt; Inserts an element in the set
insert :: Eq a => a -> Set a -> Set a

-- | &lt;math&gt; Deletes an element from the set
delete :: Eq a => a -> Set a -> Set a

-- | &lt;math&gt; Computes the union of two sets
union :: Eq a => Set a -> Set a -> Set a

-- | &lt;math&gt; Computes the intersection of two sets
intersection :: Eq a => Set a -> Set a -> Set a

-- | &lt;math&gt; Computes the difference of two sets
difference :: Eq a => Set a -> Set a -> Set a

-- | &lt;math&gt; Create a set from a finite list of elements.
fromList :: Eq a => [a] -> Set a

-- | &lt;math&gt; Insert an element in a set.
insertAll :: Eq a => [a] -> Set a -> Set a
instance Data.Traversable.Traversable Data.List.Set.Set
instance Data.Foldable.Foldable Data.List.Set.Set
instance GHC.Base.Functor Data.List.Set.Set
instance GHC.Read.Read a => GHC.Read.Read (Data.List.Set.Set a)
instance GHC.Show.Show a => GHC.Show.Show (Data.List.Set.Set a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.List.Set.Set a)
instance GHC.Classes.Eq a => GHC.Base.Semigroup (Data.List.Set.Set a)
instance GHC.Classes.Eq a => GHC.Base.Monoid (Data.List.Set.Set a)


module Data.List.Zipper

-- | Simple Zipper for Lists.
data Zipper a
Zipper :: [a] -> [a] -> Zipper a

-- | Construct a Zipper from a list
--   
--   running time: &lt;math&gt;
fromList :: [a] -> Zipper a

-- | Go to the Next Element
--   
--   running time: &lt;math&gt;
goNext :: Zipper a -> Maybe (Zipper a)

-- | Go to the previous Element
--   
--   running time: &lt;math&gt;
goPrev :: Zipper a -> Maybe (Zipper a)

-- | Computes all nexts, even one that has no elements initially or at the
--   end.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ allNexts $ fromList [1..5]
--   Zipper [] [1,2,3,4,5]
--   Zipper [1] [2,3,4,5]
--   Zipper [2,1] [3,4,5]
--   Zipper [3,2,1] [4,5]
--   Zipper [4,3,2,1] [5]
--   Zipper [5,4,3,2,1] []
--   </pre>
allNexts :: Zipper a -> [Zipper a]

-- | Returns the next element, and the zipper without it
extractNext :: Zipper a -> Maybe (a, Zipper a)

-- | Drops the next element in the zipper.
--   
--   running time: &lt;math&gt;
dropNext :: Zipper a -> Maybe (Zipper a)

-- | Computes all list that still have next elements.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ allNonEmptyNexts $ fromList [1..5]
--   Zipper [] [1,2,3,4,5]
--   Zipper [1] [2,3,4,5]
--   Zipper [2,1] [3,4,5]
--   Zipper [3,2,1] [4,5]
--   Zipper [4,3,2,1] [5]
--   </pre>
allNonEmptyNexts :: Zipper a -> [Zipper a]
instance GHC.Base.Functor Data.List.Zipper.Zipper
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.List.Zipper.Zipper a)
instance GHC.Show.Show a => GHC.Show.Show (Data.List.Zipper.Zipper a)
instance Data.Foldable.Foldable Data.List.Zipper.Zipper


module Data.List.Util

-- | Given an input list, computes all lists in which just one element is
--   missing.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ leaveOutOne [1..5]
--   (1,[2,3,4,5])
--   (2,[1,3,4,5])
--   (3,[1,2,4,5])
--   (4,[1,2,3,5])
--   (5,[1,2,3,4])
--   
--   &gt;&gt;&gt; leaveOutOne []
--   []
--   
--   &gt;&gt;&gt; leaveOutOne [1]
--   [(1,[])]
--   </pre>
leaveOutOne :: [a] -> [(a, [a])]

-- | Safe variant of Prelude.minimum.
--   
--   <pre>
--   &gt;&gt;&gt; minimum1 [] :: Maybe ()
--   Nothing
--   
--   &gt;&gt;&gt; minimum1 [1,2,3]
--   Just 1
--   </pre>
minimum1 :: Ord a => [a] -> Maybe a

-- | Safe variant of Prelude.maximum.
--   
--   <pre>
--   &gt;&gt;&gt; maximum1 [] :: Maybe ()
--   Nothing
--   
--   &gt;&gt;&gt; maximum1 [1,2,3]
--   Just 3
--   </pre>
maximum1 :: Ord a => [a] -> Maybe a

-- | Total variant of Data.List.minimumBy.
--   
--   <pre>
--   &gt;&gt;&gt; minimum1By (comparing abs) [] :: Maybe Int
--   Nothing
--   
--   &gt;&gt;&gt; minimum1By (comparing abs) [1,-2,3]
--   Just 1
--   </pre>
minimum1By :: (a -> a -> Ordering) -> [a] -> Maybe a

-- | Computes all minima by comparing some property.
--   
--   <pre>
--   &gt;&gt;&gt; minimaOn (max 2) [1,2,3,4,5,-1]
--   [-1,2,1]
--   </pre>
minimaOn :: Ord b => (a -> b) -> [a] -> [a]

-- | Computes all minima.
--   
--   <pre>
--   &gt;&gt;&gt; minimaBy (comparing abs) [1,2,3,2,1,-1]
--   [-1,1,1]
--   </pre>
minimaBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | extracts all minima from the list. The result consists of the list of
--   minima, and all remaining points. Both lists are returned in the order
--   in which they occur in the input.
--   
--   <pre>
--   &gt;&gt;&gt; extractMinimaBy compare [1,2,3,0,1,2,3,0,1,2,0,2]
--   [0,0,0] :+ [2,3,1,2,3,1,2,1,2]
--   </pre>
extractMinimaBy :: (a -> a -> Ordering) -> [a] -> [a] :+ [a]

-- | Given a function f, partitions the list into three lists (lts,eqs,gts)
--   such that:
--   
--   <ul>
--   <li>f x == LT for all x in lts</li>
--   <li>f x == EQ for all x in eqs</li>
--   <li>f x == gt for all x in gts</li>
--   </ul>
--   
--   <pre>
--   &gt;&gt;&gt; partition3 (compare 4) [0,1,2,2,3,4,5,5,6,6,7,7,7,7,7,8]
--   ([5,5,6,6,7,7,7,7,7,8],[4],[0,1,2,2,3])
--   </pre>
partition3 :: Foldable f => (a -> Ordering) -> f a -> ([a], [a], [a])

-- | A version of groupBy that uses the given Ordering to group consecutive
--   Equal items
--   
--   <pre>
--   &gt;&gt;&gt; groupBy' compare [0,1,2,2,3,4,5,5,6,6,7,7,7,7,7,8]
--   [0 :| [],1 :| [],2 :| [2],3 :| [],4 :| [],5 :| [5],6 :| [6],7 :| [7,7,7,7],8 :| []]
--   </pre>
groupBy' :: (a -> a -> Ordering) -> [a] -> [NonEmpty a]


module Data.Measured.Class

-- | Things that can be measured.
class Semigroup v => Measured v a | a -> v
measure :: Measured v a => a -> v

-- | Things that can be inserted.
class Measured v a => CanInsert v a
insertA :: CanInsert v a => a -> v -> v

-- | Things that can be deleted.
class Measured v a => CanDelete v a
deleteA :: CanDelete v a => a -> v -> Maybe v


module Data.Measured


module Data.Measured.Size

-- | Measured size. Always non-negative.
newtype Size
Size :: Word -> Size

-- | Newtype wrapper for things for which we can measure the size
newtype Elem a
Elem :: a -> Elem a
[_unElem] :: Elem a -> a

-- | Things that have a size
data Sized a
Sized :: {-# UNPACK #-} !Size -> a -> Sized a
instance Control.DeepSeq.NFData Data.Measured.Size.Size
instance GHC.Generics.Generic Data.Measured.Size.Size
instance GHC.Classes.Ord Data.Measured.Size.Size
instance GHC.Real.Real Data.Measured.Size.Size
instance GHC.Enum.Enum Data.Measured.Size.Size
instance GHC.Real.Integral Data.Measured.Size.Size
instance GHC.Num.Num Data.Measured.Size.Size
instance GHC.Classes.Eq Data.Measured.Size.Size
instance GHC.Read.Read Data.Measured.Size.Size
instance GHC.Show.Show Data.Measured.Size.Size
instance Data.Traversable.Traversable Data.Measured.Size.Elem
instance Data.Foldable.Foldable Data.Measured.Size.Elem
instance GHC.Base.Functor Data.Measured.Size.Elem
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Measured.Size.Elem a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Measured.Size.Elem a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Measured.Size.Elem a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Measured.Size.Elem a)
instance GHC.Generics.Generic (Data.Measured.Size.Sized a)
instance Data.Traversable.Traversable Data.Measured.Size.Sized
instance Data.Foldable.Foldable Data.Measured.Size.Sized
instance GHC.Base.Functor Data.Measured.Size.Sized
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Measured.Size.Sized a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Measured.Size.Sized a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Measured.Size.Sized a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Measured.Size.Sized a)
instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.Measured.Size.Sized a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.Measured.Size.Sized a)
instance Data.Measured.Class.Measured Data.Measured.Size.Size (Data.Measured.Size.Elem a)
instance GHC.Base.Semigroup Data.Measured.Size.Size
instance GHC.Base.Monoid Data.Measured.Size.Size


module Data.OrdSeq

-- | Sequence of ordered elements.
data OrdSeq a

-- | Signature for functions that give the ordering of two values.
type Compare a = a -> a -> Ordering

-- | Insert into a monotone OrdSeq.
--   
--   pre: the comparator maintains monotonicity
--   
--   &lt;math&gt;
insertBy :: Compare a -> a -> OrdSeq a -> OrdSeq a

-- | Insert into a sorted OrdSeq
--   
--   &lt;math&gt;
insert :: Ord a => a -> OrdSeq a -> OrdSeq a

-- | &lt;math&gt;
splitBy :: Compare a -> a -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)

-- | Given a monotonic function f that maps a to b, split the sequence s
--   depending on the b values. I.e. the result (l,m,r) is such that
--   
--   <ul>
--   <li><pre>all (&lt; x) . fmap f $ l</pre></li>
--   <li><pre>all (== x) . fmap f $ m</pre></li>
--   <li><pre>all (&gt; x) . fmap f $ r</pre></li>
--   </ul>
--   
--   <pre>
--   &gt;&gt;&gt; splitOn id 3 $ fromAscList [1..5]
--   (fromAscList [1,2],fromAscList [3],fromAscList [4,5])
--   
--   &gt;&gt;&gt; splitOn fst 2 $ fromAscList [(0,"-"),(1,"A"),(2,"B"),(2,"C"),(3,"D"),(4,"E")]
--   (fromAscList [(0,"-"),(1,"A")],fromAscList [(2,"B"),(2,"C")],fromAscList [(3,"D"),(4,"E")])
--   </pre>
splitOn :: Ord b => (a -> b) -> b -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)

-- | Given a monotonic predicate p, splits the sequence s into two
--   sequences (as,bs) such that all (not p) as and all p bs
--   
--   &lt;math&gt;
splitMonotonic :: (a -> Bool) -> OrdSeq a -> (OrdSeq a, OrdSeq a)

-- | Deletes all elements from the OrdDeq
--   
--   &lt;math&gt;
deleteAll :: Ord a => a -> OrdSeq a -> OrdSeq a

-- | &lt;math&gt;. Delete all elements that compare as equal to <tt>x</tt>.
deleteAllBy :: Compare a -> a -> OrdSeq a -> OrdSeq a

-- | inserts all eleements in order &lt;math&gt;
fromListBy :: Compare a -> [a] -> OrdSeq a

-- | inserts all eleements in order &lt;math&gt;
fromListByOrd :: Ord a => [a] -> OrdSeq a

-- | &lt;math&gt;
fromAscList :: [a] -> OrdSeq a

-- | &lt;math&gt;
lookupBy :: Compare a -> a -> OrdSeq a -> Maybe a

-- | &lt;math&gt;. Queries for the existance of any elements that compare
--   as equal to <tt>x</tt>.
memberBy :: Compare a -> a -> OrdSeq a -> Bool

-- | &lt;math&gt; Fmap, assumes the order does not change
mapMonotonic :: (a -> b) -> OrdSeq a -> OrdSeq b

-- | &lt;math&gt; Gets the first element from the sequence
viewl :: OrdSeq a -> ViewL OrdSeq a

-- | &lt;math&gt; Gets the last element from the sequence
viewr :: OrdSeq a -> ViewR OrdSeq a

-- | &lt;math&gt;
minView :: OrdSeq a -> Maybe (a, OrdSeq a)

-- | &lt;math&gt;
lookupMin :: OrdSeq a -> Maybe a

-- | &lt;math&gt;
maxView :: OrdSeq a -> Maybe (a, OrdSeq a)

-- | &lt;math&gt;
lookupMax :: OrdSeq a -> Maybe a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.OrdSeq.Key a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.OrdSeq.Key a)
instance GHC.Show.Show a => GHC.Show.Show (Data.OrdSeq.Key a)
instance GHC.Base.Functor Data.OrdSeq.Elem
instance Data.Foldable.Foldable Data.OrdSeq.Elem
instance Data.Traversable.Traversable Data.OrdSeq.Elem
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.OrdSeq.Elem a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.OrdSeq.Elem a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.OrdSeq.OrdSeq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.OrdSeq.OrdSeq a)
instance GHC.Base.Semigroup (Data.OrdSeq.OrdSeq a)
instance GHC.Base.Monoid (Data.OrdSeq.OrdSeq a)
instance Data.Foldable.Foldable Data.OrdSeq.OrdSeq
instance (Test.QuickCheck.Arbitrary.Arbitrary a, GHC.Classes.Ord a) => Test.QuickCheck.Arbitrary.Arbitrary (Data.OrdSeq.OrdSeq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.OrdSeq.Elem a)
instance Data.FingerTree.Measured (Data.OrdSeq.Key a) (Data.OrdSeq.Elem a)
instance GHC.Base.Semigroup (Data.OrdSeq.Key a)
instance GHC.Base.Monoid (Data.OrdSeq.Key a)


-- | Data type for representing a Permutation
module Data.Permutation

-- | Orbits (Cycles) are represented by vectors
type Orbit a = Vector a

-- | Cyclic representation of a permutation.
data Permutation a
Permutation :: Vector (Orbit a) -> Vector (Int, Int) -> Permutation a
[_orbits] :: Permutation a -> Vector (Orbit a)

-- | idxes (fromEnum a) = (i,j) implies that a is the j^th item in the i^th
--   orbit
[_indexes] :: Permutation a -> Vector (Int, Int)
orbits :: forall a_arfH a_arnZ. Lens (Permutation a_arfH) (Permutation a_arnZ) (Vector (Orbit a_arfH)) (Vector (Orbit a_arnZ))
indexes :: forall a_arfH. Lens' (Permutation a_arfH) (Vector (Int, Int))
elems :: Permutation a -> Vector a
size :: Permutation a -> Int

-- | The cycle containing a given item
cycleOf :: Enum a => Permutation a -> a -> Orbit a

-- | Next item in a cyclic permutation
next :: Vector v a => v a -> Int -> a

-- | Previous item in a cyclic permutation
previous :: Vector v a => v a -> Int -> a

-- | Lookup the indices of an element, i.e. in which orbit the item is, and
--   the index within the orbit.
--   
--   runnign time: &lt;math&gt;
lookupIdx :: Enum a => Permutation a -> a -> (Int, Int)

-- | Apply the permutation, i.e. consider the permutation as a function.
apply :: Enum a => Permutation a -> a -> a

-- | Find the cycle in the permutation starting at element s
orbitFrom :: Eq a => a -> (a -> a) -> [a]

-- | Given a vector with items in the permutation, and a permutation (by
--   its functional representation) construct the cyclic representation of
--   the permutation.
cycleRep :: (Vector v a, Enum a, Eq a) => v a -> (a -> a) -> Permutation a

-- | Given the size n, and a list of Cycles, turns the cycles into a cyclic
--   representation of the Permutation.
toCycleRep :: Enum a => Int -> [[a]] -> Permutation a
genIndexes :: Enum a => Int -> [[a]] -> Vector (Int, Int)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Permutation.Permutation a)
instance GHC.Base.Functor Data.Permutation.Permutation
instance Data.Foldable.Foldable Data.Permutation.Permutation
instance Data.Traversable.Traversable Data.Permutation.Permutation
instance GHC.Generics.Generic (Data.Permutation.Permutation a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Permutation.Permutation a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Permutation.Permutation a)


-- | Data types that to represent a planar graph as Adjacency Lists. The
--   main purpose is to help encode<i>decode a PlanarGraph as a
--   JSON</i>YAML file.
module Data.PlanarGraph.AdjRep

-- | Data type representing the graph in its JSON/Yaml format
data Gr v f
Gr :: [v] -> [f] -> Gr v f
[adjacencies] :: Gr v f -> [v]
[faces] :: Gr v f -> [f]

-- | A vertex, represented by an id, its adjacencies, and its data.
data Vtx v e
Vtx :: Int -> [(Int, e)] -> v -> Vtx v e
[id] :: Vtx v e -> Int

-- | adjacent vertices + data on the edge. Some functions, like
--   <tt>fromAdjRep</tt> may assume that the adjacencies are given in
--   counterclockwise order around the vertices. This is not (yet) enforced
--   by the data type.
[adj] :: Vtx v e -> [(Int, e)]
[vData] :: Vtx v e -> v

-- | Faces
data Face f
Face :: (Int, Int) -> f -> Face f

-- | an edge (u,v) s.t. the face is right from (u,v)
[incidentEdge] :: Face f -> (Int, Int)
[fData] :: Face f -> f
instance (GHC.Classes.Eq v, GHC.Classes.Eq f) => GHC.Classes.Eq (Data.PlanarGraph.AdjRep.Gr v f)
instance (GHC.Show.Show v, GHC.Show.Show f) => GHC.Show.Show (Data.PlanarGraph.AdjRep.Gr v f)
instance GHC.Generics.Generic (Data.PlanarGraph.AdjRep.Gr v f)
instance (GHC.Classes.Eq e, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.PlanarGraph.AdjRep.Vtx v e)
instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.PlanarGraph.AdjRep.Vtx v e)
instance GHC.Generics.Generic (Data.PlanarGraph.AdjRep.Vtx v e)
instance GHC.Classes.Eq f => GHC.Classes.Eq (Data.PlanarGraph.AdjRep.Face f)
instance GHC.Show.Show f => GHC.Show.Show (Data.PlanarGraph.AdjRep.Face f)
instance GHC.Base.Functor Data.PlanarGraph.AdjRep.Face
instance GHC.Generics.Generic (Data.PlanarGraph.AdjRep.Face f)
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.AdjRep.Face f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.AdjRep.Face f)
instance Data.Bifunctor.Bifunctor Data.PlanarGraph.AdjRep.Vtx
instance (Data.Aeson.Types.ToJSON.ToJSON v, Data.Aeson.Types.ToJSON.ToJSON e) => Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.AdjRep.Vtx v e)
instance (Data.Aeson.Types.FromJSON.FromJSON v, Data.Aeson.Types.FromJSON.FromJSON e) => Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.AdjRep.Vtx v e)
instance Data.Bifunctor.Bifunctor Data.PlanarGraph.AdjRep.Gr
instance (Data.Aeson.Types.ToJSON.ToJSON v, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.AdjRep.Gr v f)
instance (Data.Aeson.Types.FromJSON.FromJSON v, Data.Aeson.Types.FromJSON.FromJSON f) => Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.AdjRep.Gr v f)


-- | Data type for representing Darts (edges) in a planar graph.
module Data.PlanarGraph.Dart

-- | An Arc is a directed edge in a planar graph. The type s is used to tie
--   this arc to a particular graph.
newtype Arc s
Arc :: Int -> Arc s
[_unArc] :: Arc s -> Int

-- | Darts have a direction which is either Positive or Negative (shown as
--   +1 or -1, respectively).
data Direction
Negative :: Direction
Positive :: Direction

-- | Reverse the direcion
rev :: Direction -> Direction

-- | A dart represents a bi-directed edge. I.e. a dart has a direction,
--   however the dart of the oposite direction is always present in the
--   planar graph as well.
data Dart s
Dart :: !Arc s -> !Direction -> Dart s
[_arc] :: Dart s -> !Arc s
[_direction] :: Dart s -> !Direction

-- | Arc lens.
arc :: Lens' (Dart s) (Arc s)

-- | Direction lens.
direction :: Lens' (Dart s) Direction

-- | Get the twin of this dart (edge)
--   
--   <pre>
--   &gt;&gt;&gt; twin (dart 0 "+1")
--   Dart (Arc 0) -1
--   
--   &gt;&gt;&gt; twin (dart 0 "-1")
--   Dart (Arc 0) +1
--   </pre>
twin :: Dart s -> Dart s

-- | test if a dart is Positive
isPositive :: Dart s -> Bool

-- | Enumerates all darts such that allDarts !! i = d <a>=</a> i ==
--   fromEnum d
allDarts :: [Dart s]
instance forall k (s :: k). Control.DeepSeq.NFData (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). GHC.Generics.Generic (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). GHC.Enum.Bounded (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). GHC.Enum.Enum (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). GHC.Classes.Ord (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). GHC.Classes.Eq (Data.PlanarGraph.Dart.Arc s)
instance GHC.Generics.Generic Data.PlanarGraph.Dart.Direction
instance GHC.Enum.Enum Data.PlanarGraph.Dart.Direction
instance GHC.Enum.Bounded Data.PlanarGraph.Dart.Direction
instance GHC.Classes.Ord Data.PlanarGraph.Dart.Direction
instance GHC.Classes.Eq Data.PlanarGraph.Dart.Direction
instance forall k (s :: k). GHC.Generics.Generic (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). GHC.Classes.Ord (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). GHC.Classes.Eq (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). Control.DeepSeq.NFData (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). GHC.Show.Show (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k). GHC.Enum.Enum (Data.PlanarGraph.Dart.Dart s)
instance Control.DeepSeq.NFData Data.PlanarGraph.Dart.Direction
instance GHC.Show.Show Data.PlanarGraph.Dart.Direction
instance GHC.Read.Read Data.PlanarGraph.Dart.Direction
instance Test.QuickCheck.Arbitrary.Arbitrary Data.PlanarGraph.Dart.Direction
instance forall k (s :: k). GHC.Show.Show (Data.PlanarGraph.Dart.Arc s)
instance forall k (s :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PlanarGraph.Dart.Arc s)


-- | Data type for representing connected planar graphs
module Data.PlanarGraph.Core

-- | The world in which the graph lives
data World
Primal :: World
Dual :: World

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

-- | The Dual of the Dual is the Primal.
dualDualIdentity :: forall w. DualOf (DualOf w) :~: w

-- | A vertex in a planar graph. A vertex is tied to a particular planar
--   graph by the phantom type s, and to a particular world w.
newtype VertexId s (w :: World)
VertexId :: Int -> VertexId s (w :: World)
[_unVertexId] :: VertexId s (w :: World) -> Int

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

-- | Getter for a VertexId's unique number.
unVertexId :: Getter (VertexId s w) Int

-- | The type to represent FaceId's
newtype FaceId s w
FaceId :: VertexId s (DualOf w) -> FaceId s w
[_unFaceId] :: FaceId s w -> VertexId s (DualOf w)

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

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

-- | Get the embedding, represented as a permutation of the darts, of this
--   graph.
embedding :: Getter (PlanarGraph s w v e f) (Permutation (Dart s))

-- | O(1) access, &lt;math&gt; update.
vertexData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v' e f) (Vector v) (Vector v')

-- | O(1) access, &lt;math&gt; update.
rawDartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector e) (Vector e')

-- | O(1) access, &lt;math&gt; update.
faceData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e f') (Vector f) (Vector f')

-- | Get the dual graph of this graph.
dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v)

-- | lens to access the Dart Data
dartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e'))

-- | edgeData is just an alias for <a>dartData</a>
edgeData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e'))

-- | Helper function to update the data in a planar graph. Takes care to
--   update both the data in the original graph as well as in the dual.
updateData :: forall s w v e f v' e' f'. (Vector v -> Vector v') -> (Vector e -> Vector e') -> (Vector f -> Vector f') -> PlanarGraph s w v e f -> PlanarGraph s w v' e' f'

-- | The function that does the actual work for <a>updateData</a>
updateData' :: DualOf (DualOf w) ~ w => (Vector v -> Vector v') -> (Vector e -> Vector e') -> (Vector f -> Vector f') -> PlanarGraph s w v e f -> PlanarGraph s w v' e' f'

-- | Reorders the edge data to be in the right order to set edgeData
reorderEdgeData :: Foldable f => f (Dart s, e) -> Vector e

-- | Traverse the vertices
--   
--   <pre>
--   &gt;&gt;&gt; (^.vertexData) &lt;$&gt; traverseVertices (\i x -&gt; Just (i,x)) myGraph
--   Just [(VertexId 0,"u"),(VertexId 1,"v"),(VertexId 2,"w"),(VertexId 3,"x")]
--   
--   &gt;&gt;&gt; traverseVertices (\i x -&gt; print (i,x)) myGraph &gt;&gt; pure ()
--   (VertexId 0,"u")
--   (VertexId 1,"v")
--   (VertexId 2,"w")
--   (VertexId 3,"x")
--   </pre>
traverseVertices :: Applicative m => (VertexId s w -> v -> m v') -> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f)

-- | Traverses the darts
--   
--   <pre>
--   &gt;&gt;&gt; traverseDarts (\d x -&gt; print (d,x)) myGraph &gt;&gt; pure ()
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 0) -1,"a-")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 2) -1,"c-")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
traverseDarts :: Applicative m => (Dart s -> e -> m e') -> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f)

-- | Traverses the faces
--   
--   <pre>
--   &gt;&gt;&gt; traverseFaces (\i x -&gt; print (i,x)) myGraph &gt;&gt; pure ()
--   (FaceId 0,"f_3")
--   (FaceId 1,"f_infty")
--   (FaceId 2,"f_1")
--   (FaceId 3,"f_2")
--   </pre>
traverseFaces :: Applicative m => (FaceId s w -> f -> m f') -> PlanarGraph s w v e f -> m (PlanarGraph s w v e f')

-- | Construct a planar graph
--   
--   running time: &lt;math&gt;.
planarGraph' :: Permutation (Dart s) -> PlanarGraph s w () () ()

-- | Construct a planar graph, given the darts in cyclic order around each
--   vertex.
--   
--   running time: &lt;math&gt;.
planarGraph :: [[(Dart s, e)]] -> PlanarGraph s Primal () e ()

-- | Produces the adjacencylists for all vertices in the graph. For every
--   vertex, the adjacent vertices are given in counter clockwise order.
--   
--   Note that in case a vertex u as a self loop, we have that this
--   vertexId occurs twice in the list of neighbours, i.e.: u :
--   [...,u,..,u,...]. Similarly, if there are multiple darts between a
--   pair of edges they occur multiple times.
--   
--   running time: &lt;math&gt;
toAdjacencyLists :: PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))]

-- | Get the number of vertices
--   
--   <pre>
--   &gt;&gt;&gt; numVertices myGraph
--   4
--   </pre>
numVertices :: PlanarGraph s w v e f -> Int

-- | Get the number of Darts
--   
--   <pre>
--   &gt;&gt;&gt; numDarts myGraph
--   12
--   </pre>
numDarts :: PlanarGraph s w v e f -> Int

-- | Get the number of Edges
--   
--   <pre>
--   &gt;&gt;&gt; numEdges myGraph
--   6
--   </pre>
numEdges :: PlanarGraph s w v e f -> Int

-- | Get the number of faces
--   
--   <pre>
--   &gt;&gt;&gt; numFaces myGraph
--   4
--   </pre>
numFaces :: PlanarGraph s w v e f -> Int

-- | Enumerate all vertices
--   
--   <pre>
--   &gt;&gt;&gt; vertices' myGraph
--   [VertexId 0,VertexId 1,VertexId 2,VertexId 3]
--   </pre>
vertices' :: PlanarGraph s w v e f -> Vector (VertexId s w)

-- | Enumerate all vertices, together with their vertex data
vertices :: PlanarGraph s w v e f -> Vector (VertexId s w, v)

-- | Enumerate all darts
darts' :: PlanarGraph s w v e f -> Vector (Dart s)

-- | Get all darts together with their data
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ darts myGraph
--   (Dart (Arc 0) -1,"a-")
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 2) -1,"c-")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
darts :: PlanarGraph s w v e f -> Vector (Dart s, e)

-- | Enumerate all edges. We report only the Positive darts
edges' :: PlanarGraph s w v e f -> Vector (Dart s)

-- | Enumerate all edges with their edge data. We report only the Positive
--   darts.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ edges myGraph
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 3) +1,"d+")
--   </pre>
edges :: PlanarGraph s w v e f -> Vector (Dart s, e)

-- | The tail of a dart, i.e. the vertex this dart is leaving from
--   
--   <pre>
--   &gt;&gt;&gt; showWithData myGraph $ tailOf (Dart (Arc 3) Positive) myGraph
--   (VertexId 2,"w")
--   </pre>
--   
--   running time: &lt;math&gt;
tailOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w

-- | The vertex this dart is heading in to
--   
--   showWithData myGraph $ headOf (Dart (Arc 3) Positive) myGraph
--   (VertexId 1,"v")
--   
--   running time: &lt;math&gt;
headOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w

-- | endPoints d g = (tailOf d g, headOf d g)
--   
--   <pre>
--   &gt;&gt;&gt; endPoints (Dart (Arc 3) Positive) myGraph
--   (VertexId 2,VertexId 1)
--   </pre>
--   
--   running time: &lt;math&gt;
endPoints :: Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)

-- | All edges incident to vertex v, in counterclockwise order around v.
--   
--   <pre>
--   &gt;&gt;&gt; incidentEdges (VertexId 1) myGraph
--   [Dart (Arc 4) -1,Dart (Arc 1) -1,Dart (Arc 3) -1,Dart (Arc 5) +1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incidentEdges (VertexId 1) myGraph
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 5) +1,"g+")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incidentEdges (VertexId 3) myGraph
--   (Dart (Arc 5) -1,"g-")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size
incidentEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | All edges incident to vertex v in incoming direction (i.e. pointing
--   into v) in counterclockwise order around v.
--   
--   <pre>
--   &gt;&gt;&gt; incomingEdges (VertexId 1) myGraph
--   [Dart (Arc 4) +1,Dart (Arc 1) +1,Dart (Arc 3) +1,Dart (Arc 5) -1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incomingEdges (VertexId 1) myGraph
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
--   
--   running time: &lt;math&gt;, where (k) is the total number of incident
--   edges of v
incomingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | All edges incident to vertex v in outgoing direction (i.e. pointing
--   away from v) in counterclockwise order around v.
--   
--   running time: &lt;math&gt;, where (k) is the total number of incident
--   edges of v
outgoingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | Gets the neighbours of a particular vertex, in counterclockwise order
--   around the vertex.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 1) myGraph -- around v
--   (VertexId 2,"w")
--   (VertexId 0,"u")
--   (VertexId 2,"w")
--   (VertexId 3,"x")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 3) myGraph -- around x
--   (VertexId 1,"v")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size
neighboursOf :: VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)

-- | Given a dart d that points into some vertex v, report the next dart in
--   the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; nextIncidentEdge (dart 3 "+1") myGraph
--   Dart (Arc 5) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdge (dart 3 "+1") myGraph
--   (Dart (Arc 5) +1,"g+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdge (dart 1 "+1") myGraph
--   (Dart (Arc 3) -1,"d-")
--   </pre>
--   
--   running time: &lt;math&gt;
nextIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points into some vertex v, report the previous
--   dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; prevIncidentEdge (dart 3 "+1") myGraph
--   Dart (Arc 1) -1
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdge (dart 3 "+1") myGraph
--   (Dart (Arc 1) -1,"b-")
--   </pre>
--   
--   running time: &lt;math&gt;
prevIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points away from some vertex v, report the next
--   dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   Dart (Arc 2) -1
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdgeFrom (dart 1 "+1") myGraph
--   (Dart (Arc 0) +1,"a+")
--   </pre>
--   
--   running time: &lt;math&gt;
nextIncidentEdgeFrom :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points into away from vertex v, report the
--   previous dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   Dart (Arc 4) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   (Dart (Arc 4) +1,"e+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 1) Positive) myGraph
--   (Dart (Arc 2) +1,"c+")
--   </pre>
--   
--   running time: &lt;math&gt;
prevIncidentEdgeFrom :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | General interface to accessing vertex data, dart data, and face data.
class HasDataOf g i where {
    type family DataOf g i;
}

-- | get the data associated with the value i.
--   
--   running time: &lt;math&gt; to read the data, &lt;math&gt; to write it.
dataOf :: HasDataOf g i => i -> Lens' g (DataOf g i)

-- | Data corresponding to the endpoints of the dart
--   
--   <pre>
--   &gt;&gt;&gt; myGraph^.endPointDataOf (Dart (Arc 3) Positive)
--   ("w","v")
--   </pre>
endPointDataOf :: Dart s -> Getter (PlanarGraph s w v e f) (v, v)

-- | Data corresponding to the endpoints of the dart
--   
--   running time: &lt;math&gt;
endPointData :: Dart s -> PlanarGraph s w v e f -> (v, v)

-- | The dual of this graph
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    let fromList = V.fromList
--        answer = fromList [ fromList [dart 0 "-1"]
--                          , fromList [dart 2 "+1",dart 4 "+1",dart 1 "-1",dart 0 "+1"]
--                          , fromList [dart 1 "+1",dart 3 "-1",dart 2 "-1"]
--                          , fromList [dart 4 "-1",dart 3 "+1",dart 5 "+1",dart 5 "-1"]
--                          ]
--    in (computeDual myGraph)^.embedding.orbits == answer
--   :}
--   True
--   </pre>
--   
--   running time: &lt;math&gt;.
computeDual :: forall s w v e f. PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v

-- | Does the actual work for dualGraph
computeDual' :: DualOf (DualOf w) ~ w => PlanarGraph s w v e f -> PlanarGraph s (DualOf w) f e v
instance GHC.Classes.Eq Data.PlanarGraph.Core.World
instance GHC.Show.Show Data.PlanarGraph.Core.World
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Control.DeepSeq.NFData (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Generics.Generic (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Enum.Enum (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Classes.Ord (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Classes.Eq (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Enum.Enum (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Classes.Ord (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Classes.Eq (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) v e f. GHC.Generics.Generic (Data.PlanarGraph.Core.PlanarGraph s w v e f)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) v e f. Data.PlanarGraph.Core.HasDataOf (Data.PlanarGraph.Core.PlanarGraph s w v e f) (Data.PlanarGraph.Core.VertexId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) v e f. Data.PlanarGraph.Core.HasDataOf (Data.PlanarGraph.Core.PlanarGraph s w v e f) (Data.PlanarGraph.Dart.Dart s)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) v e f. Data.PlanarGraph.Core.HasDataOf (Data.PlanarGraph.Core.PlanarGraph s w v e f) (Data.PlanarGraph.Core.FaceId s w)
instance forall k v e f (s :: k) (w :: Data.PlanarGraph.Core.World). (GHC.Show.Show v, GHC.Show.Show e, GHC.Show.Show f) => GHC.Show.Show (Data.PlanarGraph.Core.PlanarGraph s w v e f)
instance forall k v e f (s :: k) (w :: Data.PlanarGraph.Core.World). (GHC.Classes.Eq v, GHC.Classes.Eq e, GHC.Classes.Eq f) => GHC.Classes.Eq (Data.PlanarGraph.Core.PlanarGraph s w v e f)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Show.Show (Data.PlanarGraph.Core.FaceId s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Show.Show (Data.PlanarGraph.Core.VertexId s w)


-- | Data type for representing connected planar graphs. This module
--   contains everything that has to do with the dual graph (i.e. computing
--   it/ operations on faces etc.)
module Data.PlanarGraph.Dual

-- | Enumerate all faces in the planar graph
faces' :: PlanarGraph s w v e f -> Vector (FaceId s w)

-- | All faces with their face data.
faces :: PlanarGraph s w v e f -> Vector (FaceId s w, f)

-- | The face to the left of the dart
--   
--   <pre>
--   &gt;&gt;&gt; leftFace (dart 1 "+1") myGraph
--   FaceId 1
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 1 "+1") myGraph
--   (FaceId 1,"f_infty")
--   
--   &gt;&gt;&gt; leftFace (dart 1 "-1") myGraph
--   FaceId 2
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 1 "-1") myGraph
--   (FaceId 2,"f_1")
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 0 "+1") myGraph
--   (FaceId 0,"f_3")
--   </pre>
--   
--   running time: &lt;math&gt;.
leftFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w

-- | The face to the right of the dart
--   
--   <pre>
--   &gt;&gt;&gt; rightFace (dart 1 "+1") myGraph
--   FaceId 2
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 1 "+1") myGraph
--   (FaceId 2,"f_1")
--   
--   &gt;&gt;&gt; rightFace (dart 1 "-1") myGraph
--   FaceId 1
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 1 "-1") myGraph
--   (FaceId 1,"f_infty")
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 0 "+1") myGraph
--   (FaceId 1,"f_infty")
--   </pre>
--   
--   running time: &lt;math&gt;.
rightFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w

-- | Get the next edge (in clockwise order) along the face that is to the
--   right of this dart.
--   
--   <pre>
--   &gt; showWithData myGraph $ nextEdge (dart 1 "+1") myGraph
--   </pre>
--   
--   (Dart (Arc 3) -1,"d-") &gt;&gt; showWithData myGraph $ nextEdge (dart
--   2 "+1") myGraph (Dart (Arc 4) +1,"e+")
--   
--   running time: &lt;math&gt;.
nextEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Get the previous edge (in clockwise order) along the face that is to
--   the right of this dart.
--   
--   <pre>
--   &gt;&gt;&gt; showWithData myGraph $ prevEdge (dart 1 "+1") myGraph
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevEdge (dart 3 "-1") myGraph
--   (Dart (Arc 1) +1,"b+")
--   </pre>
--   
--   running time: &lt;math&gt;.
prevEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Gets a dart bounding this face. I.e. a dart d such that the face lies
--   to the right of the dart.
--   
--   <pre>
--   &gt;&gt;&gt; boundaryDart (FaceId $ VertexId 2) myGraph
--   Dart (Arc 1) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ boundaryDart (FaceId $ VertexId 2) myGraph
--   (Dart (Arc 1) +1,"b+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ boundaryDart (FaceId $ VertexId 1) myGraph
--   (Dart (Arc 2) +1,"c+")
--   </pre>
boundaryDart :: FaceId s w -> PlanarGraph s w v e f -> Dart s

-- | The darts bounding this face. The darts are reported in order along
--   the face. This means that for internal faces the darts are reported in
--   *clockwise* order along the boundary, whereas for the outer face the
--   darts are reported in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; boundary (FaceId $ VertexId 2) myGraph
--   [Dart (Arc 1) +1,Dart (Arc 3) -1,Dart (Arc 2) -1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary (FaceId $ VertexId 2) myGraph
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; boundary (FaceId $ VertexId 1) myGraph
--   [Dart (Arc 2) +1,Dart (Arc 4) +1,Dart (Arc 1) -1,Dart (Arc 0) +1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary (FaceId $ VertexId 1) myGraph
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 0) +1,"a+")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size.
boundary :: FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | Given a dart d, generates the darts bounding the face that is to the
--   right of the given dart. The darts are reported in order along the
--   face. This means that for internal faces the darts are reported in
--   *clockwise* order along the boundary, whereas for the outer face the
--   darts are reported in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary' (dart 1 "+1") myGraph
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 2) -1,"c-")
--   </pre>
--   
--   &lt;math&gt;, where &lt;math&gt; is the number of darts reported
boundary' :: Dart s -> PlanarGraph s w v e f -> Vector (Dart s)

-- | The vertices bounding this face, for internal faces in clockwise
--   order, for the outer face in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 2) myGraph
--   (VertexId 0,"u")
--   (VertexId 1,"v")
--   (VertexId 2,"w")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 1) myGraph
--   (VertexId 0,"u")
--   (VertexId 2,"w")
--   (VertexId 1,"v")
--   (VertexId 0,"u")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size.
boundaryVertices :: FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)


-- | Data structure to represent a planar graph with which we can test in
--   &lt;math&gt; time if an edge between a pair of vertices exists.
module Data.PlanarGraph.EdgeOracle

-- | Edge Oracle:
--   
--   main idea: store adjacency lists in such a way that we store an edge
--   (u,v) either in u's adjacency list or in v's. This can be done s.t.
--   all adjacency lists have length at most 6.
--   
--   note: Every edge is stored exactly once (i.e. either at u or at v, but
--   not both)
newtype EdgeOracle s w a
EdgeOracle :: Vector (Vector (VertexId s w :+ a)) -> EdgeOracle s w a
[_unEdgeOracle] :: EdgeOracle s w a -> Vector (Vector (VertexId s w :+ a))

-- | Given a planar graph, construct an edge oracle. Given a pair of
--   vertices this allows us to efficiently find the dart representing this
--   edge in the graph.
--   
--   pre: No self-loops and no multi-edges!!!
--   
--   running time: &lt;math&gt;
edgeOracle :: PlanarGraph s w v e f -> EdgeOracle s w (Dart s)

-- | Builds an edge oracle that can be used to efficiently test if two
--   vertices are connected by an edge.
--   
--   running time: &lt;math&gt;
buildEdgeOracle :: forall f s w e. Foldable f => [(VertexId s w, f (VertexId s w :+ e))] -> EdgeOracle s w e

-- | Test if u and v are connected by an edge.
--   
--   running time: &lt;math&gt;
hasEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Bool

-- | Find the edge data corresponding to edge (u,v) if such an edge exists
--   
--   running time: &lt;math&gt;
findEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Maybe a

-- | Given a pair of vertices (u,v) returns the dart, oriented from u to v,
--   corresponding to these vertices.
--   
--   running time: &lt;math&gt;
findDart :: VertexId s w -> VertexId s w -> EdgeOracle s w (Dart s) -> Maybe (Dart s)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) a. GHC.Classes.Eq a => GHC.Classes.Eq (Data.PlanarGraph.EdgeOracle.EdgeOracle s w a)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World) a. GHC.Show.Show a => GHC.Show.Show (Data.PlanarGraph.EdgeOracle.EdgeOracle s w a)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). GHC.Base.Functor (Data.PlanarGraph.EdgeOracle.EdgeOracle s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Foldable.Foldable (Data.PlanarGraph.EdgeOracle.EdgeOracle s w)
instance forall k (s :: k) (w :: Data.PlanarGraph.Core.World). Data.Traversable.Traversable (Data.PlanarGraph.EdgeOracle.EdgeOracle s w)


-- | Converting from<i>to our JSON</i>Yaml representation of the plane
--   graph
module Data.PlanarGraph.IO

-- | Transforms the planar graph into a format that can be easily converted
--   into JSON format. For every vertex, the adjacent vertices are given in
--   counter-clockwise order.
--   
--   See <a>toAdjacencyLists</a> for notes on how we handle self-loops.
--   
--   running time: &lt;math&gt;
toAdjRep :: PlanarGraph s w v e f -> Gr (Vtx v e) (Face f)

-- | Read a planar graph, given in JSON format into a planar graph. The
--   adjacencylists should be in counter clockwise order.
--   
--   running time: &lt;math&gt;
fromAdjRep :: proxy s -> Gr (Vtx v e) (Face f) -> PlanarGraph s Primal v e f

-- | Builds the graph from the adjacency lists (but ignores all associated
--   data)
buildGraph :: proxy s -> Gr (Vtx v e) (Face f) -> PlanarGraph s Primal () () ()
reorder :: Vector (i :+ a) -> (i -> Int) -> Vector a

-- | Construct a planar graph from a adjacency matrix. For every vertex,
--   all vertices should be given in counter-clockwise order.
--   
--   pre: No self-loops, and no multi-edges
--   
--   running time: &lt;math&gt;.
fromAdjacencyLists :: forall s w h. (Foldable h, Functor h) => [(VertexId s w, h (VertexId s w))] -> PlanarGraph s w () () ()
assignArcs :: EdgeOracle s w e -> EdgeOracle s w (Int :+ e)
instance forall k v e f (s :: k) (w :: Data.PlanarGraph.Core.World). (Data.Aeson.Types.ToJSON.ToJSON v, Data.Aeson.Types.ToJSON.ToJSON e, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (Data.PlanarGraph.Core.PlanarGraph s w v e f)
instance forall k v e f (s :: k). (Data.Aeson.Types.FromJSON.FromJSON v, Data.Aeson.Types.FromJSON.FromJSON e, Data.Aeson.Types.FromJSON.FromJSON f) => Data.Aeson.Types.FromJSON.FromJSON (Data.PlanarGraph.Core.PlanarGraph s 'Data.PlanarGraph.Core.Primal v e f)


-- | Data type for representing connected planar graphs
module Data.PlanarGraph

-- | A *connected* Planar graph with bidirected edges. I.e. the edges
--   (darts) are directed, however, for every directed edge, the edge in
--   the oposite direction is also in the graph.
--   
--   The types v, e, and f are the are the types of the data associated
--   with the vertices, edges, and faces, respectively.
--   
--   The orbits in the embedding are assumed to be in counterclockwise
--   order. Therefore, every dart directly bounds the face to its right.
data PlanarGraph s (w :: World) v e f

-- | Get the embedding, represented as a permutation of the darts, of this
--   graph.
embedding :: Getter (PlanarGraph s w v e f) (Permutation (Dart s))

-- | O(1) access, &lt;math&gt; update.
vertexData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v' e f) (Vector v) (Vector v')

-- | lens to access the Dart Data
dartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e'))

-- | O(1) access, &lt;math&gt; update.
faceData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e f') (Vector f) (Vector f')

-- | O(1) access, &lt;math&gt; update.
rawDartData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector e) (Vector e')

-- | edgeData is just an alias for <a>dartData</a>
edgeData :: Lens (PlanarGraph s w v e f) (PlanarGraph s w v e' f) (Vector (Dart s, e)) (Vector (Dart s, e'))

-- | The world in which the graph lives
data World
Primal :: World
Dual :: World

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

-- | An Arc is a directed edge in a planar graph. The type s is used to tie
--   this arc to a particular graph.
newtype Arc s
Arc :: Int -> Arc s
[_unArc] :: Arc s -> Int

-- | Darts have a direction which is either Positive or Negative (shown as
--   +1 or -1, respectively).
data Direction
Negative :: Direction
Positive :: Direction

-- | Reverse the direcion
rev :: Direction -> Direction

-- | A dart represents a bi-directed edge. I.e. a dart has a direction,
--   however the dart of the oposite direction is always present in the
--   planar graph as well.
data Dart s
Dart :: !Arc s -> !Direction -> Dart s
[_arc] :: Dart s -> !Arc s
[_direction] :: Dart s -> !Direction

-- | Arc lens.
arc :: Lens' (Dart s) (Arc s)

-- | Direction lens.
direction :: Lens' (Dart s) Direction

-- | Get the twin of this dart (edge)
--   
--   <pre>
--   &gt;&gt;&gt; twin (dart 0 "+1")
--   Dart (Arc 0) -1
--   
--   &gt;&gt;&gt; twin (dart 0 "-1")
--   Dart (Arc 0) +1
--   </pre>
twin :: Dart s -> Dart s

-- | test if a dart is Positive
isPositive :: Dart s -> Bool

-- | A vertex in a planar graph. A vertex is tied to a particular planar
--   graph by the phantom type s, and to a particular world w.
newtype VertexId s (w :: World)
VertexId :: Int -> VertexId s (w :: World)
[_unVertexId] :: VertexId s (w :: World) -> Int

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

-- | Construct a planar graph, given the darts in cyclic order around each
--   vertex.
--   
--   running time: &lt;math&gt;.
planarGraph :: [[(Dart s, e)]] -> PlanarGraph s Primal () e ()

-- | Construct a planar graph
--   
--   running time: &lt;math&gt;.
planarGraph' :: Permutation (Dart s) -> PlanarGraph s w () () ()

-- | Construct a planar graph from a adjacency matrix. For every vertex,
--   all vertices should be given in counter-clockwise order.
--   
--   pre: No self-loops, and no multi-edges
--   
--   running time: &lt;math&gt;.
fromAdjacencyLists :: forall s w h. (Foldable h, Functor h) => [(VertexId s w, h (VertexId s w))] -> PlanarGraph s w () () ()

-- | Produces the adjacencylists for all vertices in the graph. For every
--   vertex, the adjacent vertices are given in counter clockwise order.
--   
--   Note that in case a vertex u as a self loop, we have that this
--   vertexId occurs twice in the list of neighbours, i.e.: u :
--   [...,u,..,u,...]. Similarly, if there are multiple darts between a
--   pair of edges they occur multiple times.
--   
--   running time: &lt;math&gt;
toAdjacencyLists :: PlanarGraph s w v e f -> [(VertexId s w, Vector (VertexId s w))]

-- | Read a planar graph, given in JSON format into a planar graph. The
--   adjacencylists should be in counter clockwise order.
--   
--   running time: &lt;math&gt;
fromAdjRep :: proxy s -> Gr (Vtx v e) (Face f) -> PlanarGraph s Primal v e f

-- | Transforms the planar graph into a format that can be easily converted
--   into JSON format. For every vertex, the adjacent vertices are given in
--   counter-clockwise order.
--   
--   See <a>toAdjacencyLists</a> for notes on how we handle self-loops.
--   
--   running time: &lt;math&gt;
toAdjRep :: PlanarGraph s w v e f -> Gr (Vtx v e) (Face f)

-- | Get the number of vertices
--   
--   <pre>
--   &gt;&gt;&gt; numVertices myGraph
--   4
--   </pre>
numVertices :: PlanarGraph s w v e f -> Int

-- | Get the number of Darts
--   
--   <pre>
--   &gt;&gt;&gt; numDarts myGraph
--   12
--   </pre>
numDarts :: PlanarGraph s w v e f -> Int

-- | Get the number of Edges
--   
--   <pre>
--   &gt;&gt;&gt; numEdges myGraph
--   6
--   </pre>
numEdges :: PlanarGraph s w v e f -> Int

-- | Get the number of faces
--   
--   <pre>
--   &gt;&gt;&gt; numFaces myGraph
--   4
--   </pre>
numFaces :: PlanarGraph s w v e f -> Int

-- | Enumerate all darts
darts' :: PlanarGraph s w v e f -> Vector (Dart s)

-- | Get all darts together with their data
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ darts myGraph
--   (Dart (Arc 0) -1,"a-")
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 2) -1,"c-")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
darts :: PlanarGraph s w v e f -> Vector (Dart s, e)

-- | Enumerate all edges. We report only the Positive darts
edges' :: PlanarGraph s w v e f -> Vector (Dart s)

-- | Enumerate all edges with their edge data. We report only the Positive
--   darts.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ print $ edges myGraph
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 3) +1,"d+")
--   </pre>
edges :: PlanarGraph s w v e f -> Vector (Dart s, e)

-- | Enumerate all vertices
--   
--   <pre>
--   &gt;&gt;&gt; vertices' myGraph
--   [VertexId 0,VertexId 1,VertexId 2,VertexId 3]
--   </pre>
vertices' :: PlanarGraph s w v e f -> Vector (VertexId s w)

-- | Enumerate all vertices, together with their vertex data
vertices :: PlanarGraph s w v e f -> Vector (VertexId s w, v)

-- | Enumerate all faces in the planar graph
faces' :: PlanarGraph s w v e f -> Vector (FaceId s w)

-- | All faces with their face data.
faces :: PlanarGraph s w v e f -> Vector (FaceId s w, f)

-- | Traverse the vertices
--   
--   <pre>
--   &gt;&gt;&gt; (^.vertexData) &lt;$&gt; traverseVertices (\i x -&gt; Just (i,x)) myGraph
--   Just [(VertexId 0,"u"),(VertexId 1,"v"),(VertexId 2,"w"),(VertexId 3,"x")]
--   
--   &gt;&gt;&gt; traverseVertices (\i x -&gt; print (i,x)) myGraph &gt;&gt; pure ()
--   (VertexId 0,"u")
--   (VertexId 1,"v")
--   (VertexId 2,"w")
--   (VertexId 3,"x")
--   </pre>
traverseVertices :: Applicative m => (VertexId s w -> v -> m v') -> PlanarGraph s w v e f -> m (PlanarGraph s w v' e f)

-- | Traverses the darts
--   
--   <pre>
--   &gt;&gt;&gt; traverseDarts (\d x -&gt; print (d,x)) myGraph &gt;&gt; pure ()
--   (Dart (Arc 0) +1,"a+")
--   (Dart (Arc 0) -1,"a-")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 2) -1,"c-")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 5) +1,"g+")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
traverseDarts :: Applicative m => (Dart s -> e -> m e') -> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f)

-- | Traverses the faces
--   
--   <pre>
--   &gt;&gt;&gt; traverseFaces (\i x -&gt; print (i,x)) myGraph &gt;&gt; pure ()
--   (FaceId 0,"f_3")
--   (FaceId 1,"f_infty")
--   (FaceId 2,"f_1")
--   (FaceId 3,"f_2")
--   </pre>
traverseFaces :: Applicative m => (FaceId s w -> f -> m f') -> PlanarGraph s w v e f -> m (PlanarGraph s w v e f')

-- | The tail of a dart, i.e. the vertex this dart is leaving from
--   
--   <pre>
--   &gt;&gt;&gt; showWithData myGraph $ tailOf (Dart (Arc 3) Positive) myGraph
--   (VertexId 2,"w")
--   </pre>
--   
--   running time: &lt;math&gt;
tailOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w

-- | The vertex this dart is heading in to
--   
--   showWithData myGraph $ headOf (Dart (Arc 3) Positive) myGraph
--   (VertexId 1,"v")
--   
--   running time: &lt;math&gt;
headOf :: Dart s -> PlanarGraph s w v e f -> VertexId s w

-- | endPoints d g = (tailOf d g, headOf d g)
--   
--   <pre>
--   &gt;&gt;&gt; endPoints (Dart (Arc 3) Positive) myGraph
--   (VertexId 2,VertexId 1)
--   </pre>
--   
--   running time: &lt;math&gt;
endPoints :: Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)

-- | All edges incident to vertex v, in counterclockwise order around v.
--   
--   <pre>
--   &gt;&gt;&gt; incidentEdges (VertexId 1) myGraph
--   [Dart (Arc 4) -1,Dart (Arc 1) -1,Dart (Arc 3) -1,Dart (Arc 5) +1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incidentEdges (VertexId 1) myGraph
--   (Dart (Arc 4) -1,"e-")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 5) +1,"g+")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incidentEdges (VertexId 3) myGraph
--   (Dart (Arc 5) -1,"g-")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size
incidentEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | All edges incident to vertex v in incoming direction (i.e. pointing
--   into v) in counterclockwise order around v.
--   
--   <pre>
--   &gt;&gt;&gt; incomingEdges (VertexId 1) myGraph
--   [Dart (Arc 4) +1,Dart (Arc 1) +1,Dart (Arc 3) +1,Dart (Arc 5) -1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ incomingEdges (VertexId 1) myGraph
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) +1,"d+")
--   (Dart (Arc 5) -1,"g-")
--   </pre>
--   
--   running time: &lt;math&gt;, where (k) is the total number of incident
--   edges of v
incomingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | All edges incident to vertex v in outgoing direction (i.e. pointing
--   away from v) in counterclockwise order around v.
--   
--   running time: &lt;math&gt;, where (k) is the total number of incident
--   edges of v
outgoingEdges :: VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | Gets the neighbours of a particular vertex, in counterclockwise order
--   around the vertex.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 1) myGraph -- around v
--   (VertexId 2,"w")
--   (VertexId 0,"u")
--   (VertexId 2,"w")
--   (VertexId 3,"x")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 3) myGraph -- around x
--   (VertexId 1,"v")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size
neighboursOf :: VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)

-- | Given a dart d that points into some vertex v, report the next dart in
--   the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; nextIncidentEdge (dart 3 "+1") myGraph
--   Dart (Arc 5) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdge (dart 3 "+1") myGraph
--   (Dart (Arc 5) +1,"g+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdge (dart 1 "+1") myGraph
--   (Dart (Arc 3) -1,"d-")
--   </pre>
--   
--   running time: &lt;math&gt;
nextIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points into some vertex v, report the previous
--   dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; prevIncidentEdge (dart 3 "+1") myGraph
--   Dart (Arc 1) -1
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdge (dart 3 "+1") myGraph
--   (Dart (Arc 1) -1,"b-")
--   </pre>
--   
--   running time: &lt;math&gt;
prevIncidentEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points away from some vertex v, report the next
--   dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   Dart (Arc 2) -1
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; showWithData myGraph $ nextIncidentEdgeFrom (dart 1 "+1") myGraph
--   (Dart (Arc 0) +1,"a+")
--   </pre>
--   
--   running time: &lt;math&gt;
nextIncidentEdgeFrom :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Given a dart d that points into away from vertex v, report the
--   previous dart in the cyclic (counterclockwise) order around v.
--   
--   <pre>
--   &gt;&gt;&gt; prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   Dart (Arc 4) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph
--   (Dart (Arc 4) +1,"e+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 1) Positive) myGraph
--   (Dart (Arc 2) +1,"c+")
--   </pre>
--   
--   running time: &lt;math&gt;
prevIncidentEdgeFrom :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | General interface to accessing vertex data, dart data, and face data.
class HasDataOf g i where {
    type family DataOf g i;
}

-- | get the data associated with the value i.
--   
--   running time: &lt;math&gt; to read the data, &lt;math&gt; to write it.
dataOf :: HasDataOf g i => i -> Lens' g (DataOf g i)

-- | Data corresponding to the endpoints of the dart
--   
--   <pre>
--   &gt;&gt;&gt; myGraph^.endPointDataOf (Dart (Arc 3) Positive)
--   ("w","v")
--   </pre>
endPointDataOf :: Dart s -> Getter (PlanarGraph s w v e f) (v, v)

-- | Data corresponding to the endpoints of the dart
--   
--   running time: &lt;math&gt;
endPointData :: Dart s -> PlanarGraph s w v e f -> (v, v)

-- | Get the dual graph of this graph.
dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v)

-- | The type to represent FaceId's
newtype FaceId s w
FaceId :: VertexId s (DualOf w) -> FaceId s w
[_unFaceId] :: FaceId s w -> VertexId s (DualOf w)

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

-- | The face to the left of the dart
--   
--   <pre>
--   &gt;&gt;&gt; leftFace (dart 1 "+1") myGraph
--   FaceId 1
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 1 "+1") myGraph
--   (FaceId 1,"f_infty")
--   
--   &gt;&gt;&gt; leftFace (dart 1 "-1") myGraph
--   FaceId 2
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 1 "-1") myGraph
--   (FaceId 2,"f_1")
--   
--   &gt;&gt;&gt; showWithData myGraph $ leftFace (dart 0 "+1") myGraph
--   (FaceId 0,"f_3")
--   </pre>
--   
--   running time: &lt;math&gt;.
leftFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w

-- | The face to the right of the dart
--   
--   <pre>
--   &gt;&gt;&gt; rightFace (dart 1 "+1") myGraph
--   FaceId 2
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 1 "+1") myGraph
--   (FaceId 2,"f_1")
--   
--   &gt;&gt;&gt; rightFace (dart 1 "-1") myGraph
--   FaceId 1
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 1 "-1") myGraph
--   (FaceId 1,"f_infty")
--   
--   &gt;&gt;&gt; showWithData myGraph $ rightFace (dart 0 "+1") myGraph
--   (FaceId 1,"f_infty")
--   </pre>
--   
--   running time: &lt;math&gt;.
rightFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w

-- | Gets a dart bounding this face. I.e. a dart d such that the face lies
--   to the right of the dart.
--   
--   <pre>
--   &gt;&gt;&gt; boundaryDart (FaceId $ VertexId 2) myGraph
--   Dart (Arc 1) +1
--   
--   &gt;&gt;&gt; showWithData myGraph $ boundaryDart (FaceId $ VertexId 2) myGraph
--   (Dart (Arc 1) +1,"b+")
--   
--   &gt;&gt;&gt; showWithData myGraph $ boundaryDart (FaceId $ VertexId 1) myGraph
--   (Dart (Arc 2) +1,"c+")
--   </pre>
boundaryDart :: FaceId s w -> PlanarGraph s w v e f -> Dart s

-- | The darts bounding this face. The darts are reported in order along
--   the face. This means that for internal faces the darts are reported in
--   *clockwise* order along the boundary, whereas for the outer face the
--   darts are reported in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; boundary (FaceId $ VertexId 2) myGraph
--   [Dart (Arc 1) +1,Dart (Arc 3) -1,Dart (Arc 2) -1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary (FaceId $ VertexId 2) myGraph
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; boundary (FaceId $ VertexId 1) myGraph
--   [Dart (Arc 2) +1,Dart (Arc 4) +1,Dart (Arc 1) -1,Dart (Arc 0) +1]
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary (FaceId $ VertexId 1) myGraph
--   (Dart (Arc 2) +1,"c+")
--   (Dart (Arc 4) +1,"e+")
--   (Dart (Arc 1) -1,"b-")
--   (Dart (Arc 0) +1,"a+")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size.
boundary :: FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s)

-- | Given a dart d, generates the darts bounding the face that is to the
--   right of the given dart. The darts are reported in order along the
--   face. This means that for internal faces the darts are reported in
--   *clockwise* order along the boundary, whereas for the outer face the
--   darts are reported in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundary' (dart 1 "+1") myGraph
--   (Dart (Arc 1) +1,"b+")
--   (Dart (Arc 3) -1,"d-")
--   (Dart (Arc 2) -1,"c-")
--   </pre>
--   
--   &lt;math&gt;, where &lt;math&gt; is the number of darts reported
boundary' :: Dart s -> PlanarGraph s w v e f -> Vector (Dart s)

-- | The vertices bounding this face, for internal faces in clockwise
--   order, for the outer face in counter clockwise order.
--   
--   <pre>
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 2) myGraph
--   (VertexId 0,"u")
--   (VertexId 1,"v")
--   (VertexId 2,"w")
--   
--   &gt;&gt;&gt; mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 1) myGraph
--   (VertexId 0,"u")
--   (VertexId 2,"w")
--   (VertexId 1,"v")
--   (VertexId 0,"u")
--   </pre>
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the output size.
boundaryVertices :: FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)

-- | Get the next edge (in clockwise order) along the face that is to the
--   right of this dart.
--   
--   <pre>
--   &gt; showWithData myGraph $ nextEdge (dart 1 "+1") myGraph
--   </pre>
--   
--   (Dart (Arc 3) -1,"d-") &gt;&gt; showWithData myGraph $ nextEdge (dart
--   2 "+1") myGraph (Dart (Arc 4) +1,"e+")
--   
--   running time: &lt;math&gt;.
nextEdge :: Dart s -> PlanarGraph s w v e f -> Dart s

-- | Get the previous edge (in clockwise order) along the face that is to
--   the right of this dart.
--   
--   <pre>
--   &gt;&gt;&gt; showWithData myGraph $ prevEdge (dart 1 "+1") myGraph
--   (Dart (Arc 2) -1,"c-")
--   
--   &gt;&gt;&gt; showWithData myGraph $ prevEdge (dart 3 "-1") myGraph
--   (Dart (Arc 1) +1,"b+")
--   </pre>
--   
--   running time: &lt;math&gt;.
prevEdge :: Dart s -> PlanarGraph s w v e f -> Dart s


module Algorithms.Graph.DFS

-- | DFS on a planar graph.
--   
--   Running time: &lt;math&gt;
--   
--   Note that since our planar graphs are always connected there is no
--   need need for dfs to take a list of start vertices.
dfs :: forall s w v e f. PlanarGraph s w v e f -> VertexId s w -> Tree (VertexId s w)

-- | Adjacency list representation of a graph: for each vertex we simply
--   list all connected neighbours.
type AdjacencyLists s w = Vector [VertexId s w]

-- | Transform into adjacencylist representation
adjacencyLists :: PlanarGraph s w v e f -> AdjacencyLists s w

-- | DFS, from a given vertex, on a graph in AdjacencyLists representation.
--   
--   Running time: &lt;math&gt;
dfs' :: forall s w. AdjacencyLists s w -> VertexId s w -> Tree (VertexId s w)

-- | DFS, from a given vertex, on a graph in AdjacencyLists representation.
--   Cycles are not removed. If your graph may contain cycles, see
--   <a>dfsFilterCycles</a>.
--   
--   Running time: &lt;math&gt;, where &lt;math&gt; is the number of nodes
--   consumed.
dfsSensitive :: forall s w. (VertexId s w -> [VertexId s w]) -> VertexId s w -> Tree (VertexId s w)

-- | Remove infinite cycles from a DFS search tree.
dfsFilterCycles :: Tree (VertexId s w) -> Tree (VertexId s w)


module Algorithms.Graph.MST

-- | Minimum spanning tree of the edges. The result is a rooted tree, in
--   which the nodes are the vertices in the planar graph together with the
--   edge weight of the edge to their parent. The root's weight is zero.
--   
--   The algorithm used is Kruskal's.
--   
--   running time: &lt;math&gt;
mst :: Ord e => PlanarGraph s w v e f -> Tree (VertexId s w)

-- | Computes the set of edges in the Minimum spanning tree
--   
--   running time: &lt;math&gt;
mstEdges :: Ord e => PlanarGraph s w v e f -> [Dart s]

-- | Given an underlying planar graph, and a set of edges that form a tree,
--   create the actual tree.
--   
--   pre: the planar graph has at least one vertex.
makeTree :: forall s w v e f. PlanarGraph s w v e f -> [Dart s] -> Tree (VertexId s w)

module Data.PlanarGraph.Mutable
data PlanarGraph s

-- | &lt;math&gt;
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2,3]]
--   </pre>
--   
pgFromFaces :: [[VertexId]] -> ST s (PlanarGraph s)
pgFromFacesCV :: [CircularVector VertexId] -> ST s (PlanarGraph s)

-- | &lt;math&gt;
pgClone :: PlanarGraph s -> ST s (PlanarGraph s)
pgHash :: PlanarGraph s -> ST s Int
data Vertex s
type VertexId = Int

-- | &lt;math&gt;
vertexFromId :: VertexId -> PlanarGraph s -> Vertex s

-- | &lt;math&gt;
vertexToId :: Vertex s -> VertexId

-- | &lt;math&gt;
vertexHalfEdge :: Vertex s -> ST s (HalfEdge s)

-- | &lt;math&gt;
vertexIsBoundary :: Vertex s -> ST s Bool

-- | O(k)
vertexOutgoingHalfEdges :: Vertex s -> ST s (CircularVector (HalfEdge s))

-- | O(k), more efficient than <a>vertexOutgoingHalfEdges</a>.
vertexWithOutgoingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s ()

-- | O(k)
vertexIncomingHalfEdges :: Vertex s -> ST s (CircularVector (HalfEdge s))

-- | O(k)
vertexWithIncomingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s ()

-- | O(k)
vertexNeighbours :: Vertex s -> ST s (CircularVector (Vertex s))
data Edge s
type EdgeId = Int

-- | O(1)
edgeFromId :: EdgeId -> PlanarGraph s -> Edge s

-- | O(1)
edgeToId :: Edge s -> EdgeId

-- | O(1)
edgeFromHalfEdge :: HalfEdge s -> Edge s
data HalfEdge s
type HalfEdgeId = Int

-- | O(1)
halfEdgeFromId :: HalfEdgeId -> PlanarGraph s -> HalfEdge s

-- | O(1)
halfEdgeToId :: HalfEdge s -> HalfEdgeId

-- | O(1)
halfEdgeNext :: HalfEdge s -> ST s (HalfEdge s)

-- | O(1)
halfEdgePrev :: HalfEdge s -> ST s (HalfEdge s)

-- | O(1) Next half-edge with the same vertex.
halfEdgeNextOutgoing :: HalfEdge s -> ST s (HalfEdge s)

-- | O(1) Next half-edge with the same vertex.
halfEdgeNextIncoming :: HalfEdge s -> ST s (HalfEdge s)

-- | O(1)
halfEdgeVertex :: HalfEdge s -> ST s (Vertex s)

-- | O(1)
halfEdgeTwin :: HalfEdge s -> HalfEdge s

-- | O(1) Tail vertex. IE. the vertex of the twin edge.
halfEdgeTailVertex :: HalfEdge s -> ST s (Vertex s)

-- | O(1) Synonym of <a>halfEdgeVertex</a>.
halfEdgeTipVertex :: HalfEdge s -> ST s (Vertex s)

-- | &lt;math&gt;
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; show &lt;$&gt; halfEdgeFace (halfEdgeFromId 0 pg)
--   "Face 0"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; show &lt;$&gt; halfEdgeFace (halfEdgeFromId 1 pg)
--   "Boundary 0"
--   </pre>
halfEdgeFace :: HalfEdge s -> ST s (Face s)

-- | &lt;math&gt; Check if a half-edge's face is interior or exterior.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 0 pg)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 1 pg)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 2 pg)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; runST $ do pg &lt;- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 3 pg)
--   False
--   </pre>
halfEdgeIsInterior :: HalfEdge s -> ST s Bool
data Face s

-- | Numerical face identifier. Negative numbers indicate boundaries,
--   non-negative numbers are internal faces.
type FaceId = Int

-- | O(1)
faceInvalid :: PlanarGraph s -> Face s

-- | O(1)
faceIsValid :: Face s -> Bool

-- | O(1)
faceIsInvalid :: Face s -> Bool

-- | O(1)
faceFromId :: FaceId -> PlanarGraph s -> Face s

-- | O(1)
faceToId :: Face s -> FaceId

-- | O(1)
faceHalfEdge :: Face s -> ST s (HalfEdge s)

-- | O(1)
faceIsInterior :: Face s -> Bool

-- | O(1)
faceIsBoundary :: Face s -> Bool

-- | O(k) Counterclockwise vector of edges.
faceHalfEdges :: Face s -> ST s (CircularVector (HalfEdge s))

-- | O(k)
faceBoundary :: Face s -> ST s (CircularVector (Vertex s))

-- | O(k) where <tt>k</tt> is the number of edges in new face.
--   
--   The two half-edges must be different, must have the same face, and may
--   not be consecutive. The first half-edge will stay in the original
--   face. The second half-edge will be in the newly created face.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2,3]]
--   </pre>
--   
--   
--   <pre>
--   do pg &lt;- <a>pgFromFaces</a> [[0,1,2,3]]
--      let he0 = <a>halfEdgeFromId</a> 0 pg'
--          he4 = <a>halfEdgeFromId</a> 4 pg'
--      <a>pgConnectVertices</a> he0 he4
--   </pre>
--   
pgConnectVertices :: HalfEdge s -> HalfEdge s -> ST s (Edge s)
instance GHC.Classes.Eq (Data.PlanarGraph.Mutable.HalfEdge s)
instance GHC.Classes.Eq (Data.PlanarGraph.Mutable.Edge s)
instance GHC.Classes.Eq (Data.PlanarGraph.Mutable.Vertex s)
instance GHC.Classes.Eq (Data.PlanarGraph.Mutable.Face s)
instance GHC.Show.Show (Data.PlanarGraph.Mutable.Face s)
instance GHC.Show.Show (Data.PlanarGraph.Mutable.Vertex s)
instance Data.Hashable.Class.Hashable (Data.PlanarGraph.Mutable.Vertex s)
instance GHC.Show.Show (Data.PlanarGraph.Mutable.HalfEdge s)
instance Data.Hashable.Class.Hashable (Data.PlanarGraph.Mutable.HalfEdge s)


-- | 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:
--   <a>https://en.wikipedia.org/wiki/Planar_graph</a>
--   
--   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:
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2]]
--   </pre>
--   
--   
--   The above pictures shows three vertices (named <tt>'0'</tt>,
--   <tt>'1'</tt>, and <tt>'2'</tt>), a single face (named <tt>'0'</tt>
--   with an underscore), and 6 half-edges (named <tt>'0'</tt> through
--   <tt>'5'</tt>). Vertices, faces, and half-edges can be efficiently
--   queried and traversed.
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   
--   &gt;&gt;&gt; pgFaces pg
--   [Face 0]
--   
--   &gt;&gt;&gt; faceBoundary (Face 0) pg
--   [Vertex 1,Vertex 2,Vertex 0]
--   </pre>
--   
--   <h2>Planar graph examples:</h2>
--   
--   Faces in planar graphs do not have to be triangular:
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2,3]]
--   </pre>
--   
--   
--   Vertices may be interior or lie on a boundary:
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   
--   &gt;&gt;&gt; pgFaces pg
--   [Face 0,Face 1]
--   
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 0) pg
--   True
--   
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 2) pg
--   False
--   </pre>
--   
--   Planar graphs may have multiple boundaries. Notice how the area
--   between vertices <tt>'1'</tt>, <tt>'2'</tt> and <tt>'3'</tt> does not
--   have a face ID:
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--   
--   &gt;&gt;&gt; pgFaces pg
--   [Face 0,Face 1,Face 2,Face 3,Face 4,Face 5]
--   
--   &gt;&gt;&gt; pgBoundaries pg
--   [Boundary 0,Boundary 1]
--   
--   &gt;&gt;&gt; faceBoundary (Boundary 0) pg {- Outer boundary -}
--   [Vertex 0,Vertex 4,Vertex 5]
--   
--   &gt;&gt;&gt; faceBoundary (Boundary 1) pg {- Inner boundary -}
--   [Vertex 1,Vertex 2,Vertex 3]
--   </pre>
--   
--   Planar graphs may also have multiple unconnected components but they
--   cannot be automatically rendered:
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2], [3,4,5]]
--   
--   &gt;&gt;&gt; pgFaces pg
--   [Face 0,Face 1]
--   
--   &gt;&gt;&gt; pgBoundaries pg
--   [Boundary 0,Boundary 1]
--   
--   &gt;&gt;&gt; faceBoundary (Boundary 0) pg
--   [Vertex 0,Vertex 1,Vertex 2]
--   
--   &gt;&gt;&gt; faceBoundary (Boundary 1) pg
--   [Vertex 3,Vertex 4,Vertex 5]
--   </pre>
--   
--   <h2>Big-O Notation</h2>
--   
--   When describing runtime complexity, <tt>n</tt> refers to the size of
--   the graph (vertices, half-edges, faces, etcs). Some functions are
--   output-sensitive and use <tt>k</tt> to indicate the amount of data
--   consumed. For example, <a>vertexNeighbours</a> runs in &lt;math&gt;
--   and taking the first neighbour is therefore an &lt;math&gt; operation
--   (because k=1).
module Data.PlanarGraph.Immutable

-- | Immutable planar graph.
data PlanarGraph

-- | &lt;math&gt;
--   
--   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 <tt><a>pgFromFaces</a> [[0,1,2]]</tt> has the same connectivity
--   as <tt><a>pgFromFaces</a> [[7,8,9]]</tt> but uses three times less
--   memory.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   <a>pgFromFaces</a> [[0,1,2,3]]
--   </pre>
--   
--   
--   <pre>
--   <a>pgFromFaces</a> [[1,2,3]]
--   </pre>
--   
pgFromFaces :: [[VertexId]] -> PlanarGraph

-- | &lt;math&gt;
--   
--   Construct a planar graph from a list of faces. This is a slightly more
--   efficient version of <a>pgFromFacesCV</a>.
pgFromFacesCV :: [CircularVector VertexId] -> PlanarGraph

-- | &lt;math&gt;
--   
--   List all vertices in a graph.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; pgVertices pg
--   [Vertex 0,Vertex 1,Vertex 2]
--   </pre>
pgVertices :: PlanarGraph -> [Vertex]

-- | &lt;math&gt;
--   
--   List all edges in a graph.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; pgEdges pg
--   [Edge 0,Edge 1,Edge 2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map edgeHalfEdges $ pgEdges pg
--   [(HalfEdge 0,HalfEdge 1),(HalfEdge 2,HalfEdge 3),(HalfEdge 4,HalfEdge 5)]
--   </pre>
pgEdges :: PlanarGraph -> [Edge]

-- | &lt;math&gt;
--   
--   List all half-edges in a graph.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; pgHalfEdges pg
--   [HalfEdge 0,HalfEdge 1,HalfEdge 2,HalfEdge 3,HalfEdge 4,HalfEdge 5]
--   </pre>
pgHalfEdges :: PlanarGraph -> [HalfEdge]

-- | &lt;math&gt;
--   
--   List all faces in a graph.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; pgFaces pg
--   [Face 0,Face 1,Face 2,Face 3,Face 4,Face 5]
--   </pre>
pgFaces :: PlanarGraph -> [Face]

-- | &lt;math&gt;
--   
--   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.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; pgBoundaries pg
--   [Boundary 0,Boundary 1]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Boundary 0) pg
--   [Vertex 0,Vertex 4,Vertex 5]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Boundary 1) pg
--   [Vertex 1,Vertex 2,Vertex 3]
--   </pre>
pgBoundaries :: PlanarGraph -> [Face]

-- | Graph vertices. For best performance, make sure to use consecutive
--   numbers.
newtype Vertex
Vertex :: Int -> Vertex
[vertexId] :: Vertex -> Int

-- | &lt;math&gt;
--   
--   Each vertex has an assigned half-edge with the following properties:
--   
--   <pre>
--   <a>halfEdgeVertex</a> (<a>vertexHalfEdge</a> vertex pg) pg = vertex
--   </pre>
--   
--   <pre>
--   <a>faceIsInterior</a> (<a>halfEdgeFace</a> (<a>vertexHalfEdge</a> vertex pg) pg) = True
--   </pre>
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexHalfEdge (Vertex 0) pg
--   HalfEdge 4
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexHalfEdge (Vertex 1) pg
--   HalfEdge 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexHalfEdge (Vertex 6) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: 6
--   ...
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexHalfEdge (Vertex (-10)) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: -10
--   ...
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeVertex (vertexHalfEdge (Vertex 2) pg) pg
--   Vertex 2
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeFace (vertexHalfEdge (Vertex 0) pg) pg
--   Face 0
--   </pre>
vertexHalfEdge :: Vertex -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   Returns <tt>True</tt> iff the vertex is interior, ie. does not lie on
--   a boundary.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsInterior (Vertex 0) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsInterior (Vertex 2) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsInterior (Vertex 4) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsInterior (Vertex 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexIsInterior: Out-of-bounds vertex access: 12
--   ...
--   </pre>
vertexIsInterior :: Vertex -> PlanarGraph -> Bool

-- | &lt;math&gt;
--   
--   Returns <tt>True</tt> iff the vertex lies on a boundary.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 0) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 2) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 4) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIsBoundary (Vertex 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexIsBoundary: Out-of-bounds vertex access: 12
--   ...
--   </pre>
vertexIsBoundary :: Vertex -> PlanarGraph -> Bool

-- | &lt;math&gt;
--   
--   Query outgoing half-edges from a given vertex in counter-clockwise
--   order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexOutgoingHalfEdges (Vertex 1) pg
--   [HalfEdge 0,HalfEdge 11,HalfEdge 3]
--   </pre>
--   
--   Each half-edge will point out from the origin vertex:
--   
--   <pre>
--   &gt;&gt;&gt; map (`halfEdgeVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg
--   [Vertex 1,Vertex 1,Vertex 1]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (`halfEdgeTipVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg
--   [Vertex 0,Vertex 4,Vertex 2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexOutgoingHalfEdges (Vertex 2) pg
--   [HalfEdge 2,HalfEdge 5]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexOutgoingHalfEdges (Vertex 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexOutgoingHalfEdges: Out-of-bounds vertex access: 12
--   ...
--   </pre>
vertexOutgoingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]

-- | &lt;math&gt;
--   
--   Query incoming half-edges from a given vertex in counter-clockwise
--   order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexIncomingHalfEdges (Vertex 1) pg
--   [HalfEdge 1,HalfEdge 10,HalfEdge 2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (`halfEdgeVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg
--   [Vertex 0,Vertex 4,Vertex 2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (`halfEdgeTipVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg
--   [Vertex 1,Vertex 1,Vertex 1]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIncomingHalfEdges (Vertex 2) pg
--   [HalfEdge 3,HalfEdge 4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexIncomingHalfEdges (Vertex 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexIncomingHalfEdges: Out-of-bounds vertex access: 12
--   ...
--   </pre>
vertexIncomingHalfEdges :: Vertex -> PlanarGraph -> [HalfEdge]

-- | &lt;math&gt;
--   
--   Query vertex neighbours in counter-clockwise order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; vertexNeighbours (Vertex 0) pg
--   [Vertex 3,Vertex 1]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexNeighbours (Vertex 1) pg
--   [Vertex 0,Vertex 4,Vertex 2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexNeighbours (Vertex 2) pg
--   [Vertex 1,Vertex 3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; vertexNeighbours (Vertex 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.vertexNeighbours: Out-of-bounds vertex access: 12
--   ...
--   </pre>
vertexNeighbours :: Vertex -> PlanarGraph -> [Vertex]

-- | Edges are bidirectional and connect two vertices. No two edges are
--   allowed to cross.
newtype Edge
Edge :: Int -> Edge
[edgeId] :: Edge -> Int

-- | &lt;math&gt;
--   
--   Split a bidirectional edge into directed half-edges.
edgeHalfEdges :: Edge -> (HalfEdge, HalfEdge)

-- | 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 :: Int -> HalfEdge
[halfEdgeId] :: HalfEdge -> Int

-- | &lt;math&gt;
--   
--   Query the half-edge in the pointed direction. Internal half-edges are
--   arranged clockwise and external half-edges go counter-clockwise.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNext (HalfEdge 4) pg {- clockwise -}
--   HalfEdge 2
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNext (HalfEdge 3) pg {- clockwise -}
--   HalfEdge 5
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNext (HalfEdge 1) pg {- counter-clockwise -}
--   HalfEdge 11
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNext (HalfEdge 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeNext: Out-of-bounds half-edge access: 12
--   ...
--   </pre>
halfEdgeNext :: HalfEdge -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   Query the half-edge opposite the pointed direction. This means
--   counter-clockwise for internal half-edges and clockwise for external
--   half-edges.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgePrev (HalfEdge 4) pg {- counter-clockwise -}
--   HalfEdge 6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgePrev (HalfEdge 3) pg {- counter-clockwise -}
--   HalfEdge 10
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgePrev (HalfEdge 1) pg {- clockwise -}
--   HalfEdge 7
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgePrev (HalfEdge 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgePrev: Out-of-bounds half-edge access: 12
--   ...
--   </pre>
halfEdgePrev :: HalfEdge -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   <pre>
--   <a>halfEdgeTwin</a> . <a>halfEdgeTwin</a> == id
--   </pre>
halfEdgeTwin :: HalfEdge -> HalfEdge

-- | &lt;math&gt;
--   
--   Next half-edge with the same vertex in counter-clockwise order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <tt>HalfEdge 0</tt> is poiting out from <tt>Vertex 1</tt>. Moving
--   counter-clockwise around <tt>Vertex 1</tt> yields <tt>HalfEdge 11</tt>
--   and <tt>HalfEdge 3</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextOutgoing (HalfEdge 0) pg
--   HalfEdge 11
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextOutgoing (HalfEdge 11) pg
--   HalfEdge 3
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextOutgoing (HalfEdge 3) pg
--   HalfEdge 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextOutgoing (HalfEdge 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeNextOutgoing: Out-of-bounds half-edge access: 12
--   ...
--   </pre>
halfEdgeNextOutgoing :: HalfEdge -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   Next half-edge with the same vertex in counter-clockwise order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <tt>HalfEdge 6</tt> is poiting towards <tt>Vertex 3</tt>. Moving
--   clockwise around <tt>Vertex 3</tt> yields <tt>HalfEdge 11</tt> and
--   <tt>HalfEdge 3</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextIncoming (HalfEdge 6) pg
--   HalfEdge 5
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextIncoming (HalfEdge 5) pg
--   HalfEdge 9
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextIncoming (HalfEdge 9) pg
--   HalfEdge 6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeNextIncoming (HalfEdge 12) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeNextIncoming: Out-of-bounds half-edge access: 12
--   ...
--   </pre>
halfEdgeNextIncoming :: HalfEdge -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   Tail-end of a half-edge. Synonym of <a>halfEdgeTailVertex</a>.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeVertex (HalfEdge 1) pg
--   Vertex 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeVertex (HalfEdge 2) pg
--   Vertex 2
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeVertex (HalfEdge 6) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeVertex: Out-of-bounds half-edge access: 6
--   ...
--   </pre>
halfEdgeVertex :: HalfEdge -> PlanarGraph -> Vertex

-- | O(1)
--   
--   Tail-end of a half-edge. Synonym of <a>halfEdgeVertex</a>.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeTailVertex (HalfEdge 1) pg
--   Vertex 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeTailVertex (HalfEdge 2) pg
--   Vertex 2
--   </pre>
halfEdgeTailVertex :: HalfEdge -> PlanarGraph -> Vertex

-- | O(1)
--   
--   Tip-end of a half-edge. This is the tail-end vertex of the twin
--   half-edge.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeTipVertex (HalfEdge 1) pg
--   Vertex 1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeTipVertex (HalfEdge 5) pg
--   Vertex 0
--   </pre>
halfEdgeTipVertex :: HalfEdge -> PlanarGraph -> Vertex

-- | &lt;math&gt;
--   
--   Query the face of a half-edge.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeFace (HalfEdge 0) pg
--   Face 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeFace (HalfEdge 1) pg
--   Boundary 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeFace (HalfEdge 6) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeFace: Out-of-bounds half-edge access: 6
--   ...
--   </pre>
halfEdgeFace :: HalfEdge -> PlanarGraph -> Face

-- | &lt;math&gt;
--   
--   Check if a half-edge's face is interior.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsInterior (HalfEdge 0) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsInterior (HalfEdge 1) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsInterior (HalfEdge 2) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsInterior (HalfEdge 3) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsInterior (HalfEdge 6) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeIsInterior: Out-of-bounds half-edge access: 6
--   ...
--   </pre>
halfEdgeIsInterior :: HalfEdge -> PlanarGraph -> Bool

-- | &lt;math&gt;
--   
--   Check if a half-edge's face is on a boundary.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsBoundary (HalfEdge 0) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsBoundary (HalfEdge 1) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsBoundary (HalfEdge 2) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsBoundary (HalfEdge 3) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; halfEdgeIsBoundary (HalfEdge 6) pg
--   ... Exception: Data.PlanarGraph.Immutable.halfEdgeIsBoundary: Out-of-bounds half-edge access: 6
--   ...
--   </pre>
halfEdgeIsBoundary :: HalfEdge -> PlanarGraph -> Bool

-- | 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 -> Face
Boundary :: FaceId -> Face

-- | Numerical face identifier. Negative numbers indicate boundaries,
--   non-negative numbers are internal faces.
type FaceId = Int

-- | &lt;math&gt;
--   
--   Returns <tt>True</tt> iff a face or boundary is part of the planar
--   graph.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Face 0) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Face 1) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Face 100) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Face (-100)) pg
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Boundary 0) pg
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceMember (Boundary 1) pg
--   False
--   </pre>
faceMember :: Face -> PlanarGraph -> Bool

-- | &lt;math&gt;
--   
--   Maps interior faces to positive integers and boundary faces to
--   negative integers.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; faceId (Face 0)
--   0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceId (Face 10)
--   10
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceId (Boundary 0)
--   -1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceId (Boundary 10)
--   -11
--   </pre>
faceId :: Face -> FaceId

-- | &lt;math&gt;
--   
--   Query the half-edge associated with a face or boundary.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdge (Face 0) pg
--   HalfEdge 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdge (Face 1) pg
--   HalfEdge 8
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdge (Boundary 0) pg
--   HalfEdge 1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdge (Face 10) pg {- Invalid face -}
--   ... Exception: Data.PlanarGraph.Immutable.faceHalfEdge: Out-of-bounds face access: 10
--   ...
--   </pre>
faceHalfEdge :: Face -> PlanarGraph -> HalfEdge

-- | &lt;math&gt;
--   
--   Returns <tt>True</tt> iff a face is interior. Does not check if the
--   face actually exists.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsInterior (Face 0)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsInterior (Face 10000)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsInterior (Boundary 0)
--   False
--   </pre>
faceIsInterior :: Face -> Bool

-- | &lt;math&gt;
--   
--   Returns <tt>True</tt> iff a face is a boundary. Does not check if the
--   face actually exists.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsBoundary (Face 0)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsBoundary (Face 10000)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceIsBoundary (Boundary 0)
--   True
--   </pre>
faceIsBoundary :: Face -> Bool

-- | &lt;math&gt;
--   
--   Query the half-edges around a face in counter-clockwise order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdges (Face 0) pg
--   [HalfEdge 0,HalfEdge 2,HalfEdge 4,HalfEdge 6]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdges (Face 1) pg
--   [HalfEdge 8,HalfEdge 5,HalfEdge 3,HalfEdge 10]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdges (Boundary 0) pg
--   [HalfEdge 1,HalfEdge 11,HalfEdge 9,HalfEdge 7]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceHalfEdges (Face 10) pg
--   ... Exception: Data.PlanarGraph.Immutable.faceHalfEdges: Out-of-bounds face access: 10
--   ...
--   </pre>
faceHalfEdges :: Face -> PlanarGraph -> [HalfEdge]

-- | &lt;math&gt;
--   
--   Query the vertices of a face in counter-clockwise order.
--   
--   <h4><b>Examples:</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]]
--   </pre>
--   
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Face 0) pg
--   [Vertex 1,Vertex 2,Vertex 3,Vertex 0]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Face 1) pg
--   [Vertex 3,Vertex 2,Vertex 1,Vertex 4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Boundary 0) pg
--   [Vertex 0,Vertex 1,Vertex 4,Vertex 3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; faceBoundary (Face 10) pg
--   ... Exception: Data.PlanarGraph.Immutable.faceBoundary: Out-of-bounds face access: 10
--   ...
--   </pre>
faceBoundary :: Face -> PlanarGraph -> [Vertex]

-- | &lt;math&gt;
pgMutate :: PlanarGraph -> (forall s. PlanarGraph s -> ST s ()) -> PlanarGraph

-- | &lt;math&gt;
pgCreate :: (forall s. ST s (PlanarGraph s)) -> PlanarGraph

-- | &lt;math&gt;
pgThaw :: PlanarGraph -> ST s (PlanarGraph s)

-- | &lt;math&gt;
pgFreeze :: PlanarGraph s -> ST s PlanarGraph

-- | &lt;math&gt;
pgUnsafeThaw :: PlanarGraph -> ST s (PlanarGraph s)

-- | &lt;math&gt;
pgUnsafeFreeze :: PlanarGraph s -> ST s PlanarGraph

-- | &lt;math&gt;
tutteEmbedding :: PlanarGraph -> Vector (V2 Double)
instance Data.Hashable.Class.Hashable Data.PlanarGraph.Immutable.HalfEdge
instance GHC.Classes.Eq Data.PlanarGraph.Immutable.HalfEdge
instance Data.Hashable.Class.Hashable Data.PlanarGraph.Immutable.Edge
instance GHC.Classes.Eq Data.PlanarGraph.Immutable.Edge
instance Data.Hashable.Class.Hashable Data.PlanarGraph.Immutable.Vertex
instance GHC.Classes.Eq Data.PlanarGraph.Immutable.Vertex
instance GHC.Show.Show Data.PlanarGraph.Immutable.Face
instance GHC.Read.Read Data.PlanarGraph.Immutable.Face
instance GHC.Classes.Eq Data.PlanarGraph.Immutable.Face
instance GHC.Classes.Eq Data.PlanarGraph.Immutable.PlanarGraph
instance Data.Hashable.Class.Hashable Data.PlanarGraph.Immutable.PlanarGraph
instance GHC.Show.Show Data.PlanarGraph.Immutable.Vertex
instance GHC.Read.Read Data.PlanarGraph.Immutable.Vertex
instance GHC.Show.Show Data.PlanarGraph.Immutable.Edge
instance GHC.Read.Read Data.PlanarGraph.Immutable.Edge
instance GHC.Show.Show Data.PlanarGraph.Immutable.HalfEdge
instance GHC.Read.Read Data.PlanarGraph.Immutable.HalfEdge

module Data.PlanarGraph.Persistent
type HalfEdge = Int
type Vertex = Int
type Face = Int
data PlanarGraph
PlanarGraph :: HalfEdge -> Vertex -> Face -> HashMap HalfEdge HalfEdge -> HashMap HalfEdge Vertex -> HashMap HalfEdge Face -> HashMap Vertex HalfEdge -> HashMap Face HalfEdge -> PlanarGraph
[pgNextHalfEdgeId] :: PlanarGraph -> HalfEdge
[pgNextVertexId] :: PlanarGraph -> Vertex
[pgNextFaceId] :: PlanarGraph -> Face
[pgNext] :: PlanarGraph -> HashMap HalfEdge HalfEdge
[pgVertex] :: PlanarGraph -> HashMap HalfEdge Vertex
[pgFace] :: PlanarGraph -> HashMap HalfEdge Face
[pgHalfEdgeFromVertex] :: PlanarGraph -> HashMap Vertex HalfEdge
[pgHalfEdgeFromFace] :: PlanarGraph -> HashMap Face HalfEdge
new :: Int -> PlanarGraph
halfEdgeNext :: HalfEdge -> PlanarGraph -> HalfEdge
halfEdgeNextM :: MonadState PlanarGraph m => HalfEdge -> m HalfEdge


-- | Data type for representing Generic Ranges (Intervals) and functions
--   that work with them.
module Data.Range

-- | Endpoints of a range may either be open or closed.
data EndPoint a
Open :: !a -> EndPoint a
Closed :: !a -> EndPoint a

-- | True iff EndPoint is open.
isOpen :: EndPoint a -> Bool

-- | True iff EndPoint is closed.
isClosed :: EndPoint a -> Bool

-- | Access lens for EndPoint value regardless of whether it is open or
--   closed.
--   
--   <pre>
--   &gt;&gt;&gt; Open 5 ^. unEndPoint
--   5
--   
--   &gt;&gt;&gt; Closed 10 ^. unEndPoint
--   10
--   
--   &gt;&gt;&gt; Open 4 &amp; unEndPoint .~ 0
--   Open 0
--   </pre>
unEndPoint :: Lens (EndPoint a) (EndPoint b) a b

-- | Data type for representing ranges.
data Range a
Range :: !EndPoint a -> !EndPoint a -> Range a
[_lower] :: Range a -> !EndPoint a
[_upper] :: Range a -> !EndPoint a
pattern OpenRange :: a -> a -> Range a
pattern ClosedRange :: a -> a -> Range a

-- | A range from l to u, ignoring/forgetting the type of the endpoints
pattern Range' :: a -> a -> Range a

-- | Helper function to show a range in mathematical notation.
--   
--   <pre>
--   &gt;&gt;&gt; prettyShow $ OpenRange 0 2
--   "(0,2)"
--   
--   &gt;&gt;&gt; prettyShow $ ClosedRange 0 2
--   "[0,2]"
--   
--   &gt;&gt;&gt; prettyShow $ Range (Open 0) (Closed 5)
--   "(0,5]"
--   </pre>
prettyShow :: Show a => Range a -> String

-- | Lens access for the lower part of a range.
lower :: Lens' (Range a) (EndPoint a)

-- | Lens access for the upper part of a range.
upper :: Lens' (Range a) (EndPoint a)

-- | Test if a value lies in a range.
--   
--   <pre>
--   &gt;&gt;&gt; 1 `inRange` (OpenRange 0 2)
--   True
--   
--   &gt;&gt;&gt; 1 `inRange` (OpenRange 0 1)
--   False
--   
--   &gt;&gt;&gt; 1 `inRange` (ClosedRange 0 1)
--   True
--   
--   &gt;&gt;&gt; 1 `inRange` (ClosedRange 1 1)
--   True
--   
--   &gt;&gt;&gt; 10 `inRange` (OpenRange 1 10)
--   False
--   
--   &gt;&gt;&gt; 10 `inRange` (ClosedRange 0 1)
--   False
--   </pre>
--   
--   This one is kind of weird
--   
--   <pre>
--   &gt;&gt;&gt; 0 `inRange` Range (Closed 0) (Open 0)
--   False
--   </pre>
inRange :: Ord a => a -> Range a -> Bool

-- | Get the width of the interval
--   
--   <pre>
--   &gt;&gt;&gt; width $ ClosedRange 1 10
--   9
--   
--   &gt;&gt;&gt; width $ OpenRange 5 10
--   5
--   </pre>
width :: Num r => Range r -> r

-- | Clip the interval from below. I.e. intersect with the interval
--   {l,infty), where { is either open, (, orr closed, [.
clipLower :: Ord a => EndPoint a -> Range a -> Maybe (Range a)

-- | Clip the interval from above. I.e. intersect with (-infty, u}, where }
--   is either open, ), or closed, ],
clipUpper :: Ord a => EndPoint a -> Range a -> Maybe (Range a)

-- | Compute the halfway point between the start and end of a range.
midPoint :: Fractional r => Range r -> r

-- | Clamps a value to a range. I.e. if the value lies outside the range we
--   report the closest value "in the range". Note that if an endpoint of
--   the range is open we report that value anyway, so we return a value
--   that is truely inside the range only if that side of the range is
--   closed.
--   
--   <pre>
--   &gt;&gt;&gt; clampTo (ClosedRange 0 10) 20
--   10
--   
--   &gt;&gt;&gt; clampTo (ClosedRange 0 10) (-20)
--   0
--   
--   &gt;&gt;&gt; clampTo (ClosedRange 0 10) 5
--   5
--   
--   &gt;&gt;&gt; clampTo (OpenRange 0 10) 20
--   10
--   
--   &gt;&gt;&gt; clampTo (OpenRange 0 10) (-20)
--   0
--   
--   &gt;&gt;&gt; clampTo (OpenRange 0 10) 5
--   5
--   </pre>
clampTo :: Ord r => Range r -> r -> r

-- | Check if the range is valid and nonEmpty, i.e. if the lower endpoint
--   is indeed smaller than the right endpoint. Note that we treat empty
--   open-ranges as invalid as well.
isValidRange :: Ord a => Range a -> Bool

-- | Wether or not the first range completely covers the second one
covers :: forall a. Ord a => Range a -> Range a -> Bool

-- | Shift a range x units to the left
--   
--   <pre>
--   &gt;&gt;&gt; prettyShow $ shiftLeft 10 (ClosedRange 10 20)
--   "[0,10]"
--   
--   &gt;&gt;&gt; prettyShow $ shiftLeft 10 (OpenRange 15 25)
--   "(5,15)"
--   </pre>
shiftLeft :: Num r => r -> Range r -> Range r

-- | Shifts the range to the right
--   
--   <pre>
--   &gt;&gt;&gt; prettyShow $ shiftRight 10 (ClosedRange 10 20)
--   "[20,30]"
--   
--   &gt;&gt;&gt; prettyShow $ shiftRight 10 (OpenRange 15 25)
--   "(25,35)"
--   </pre>
shiftRight :: Num r => r -> Range r -> Range r
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Range.EndPoint a)
instance GHC.Generics.Generic (Data.Range.EndPoint a)
instance Data.Traversable.Traversable Data.Range.EndPoint
instance Data.Foldable.Foldable Data.Range.EndPoint
instance GHC.Base.Functor Data.Range.EndPoint
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Range.EndPoint a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Range.Range a)
instance GHC.Generics.Generic (Data.Range.Range a)
instance Data.Traversable.Traversable Data.Range.Range
instance Data.Foldable.Foldable Data.Range.Range
instance GHC.Base.Functor Data.Range.Range
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Range.Range a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Range.Range a)
instance Data.Functor.Classes.Show1 Data.Range.Range
instance GHC.Read.Read a => GHC.Read.Read (Data.Range.Range a)
instance Data.Functor.Classes.Read1 Data.Range.Range
instance (Test.QuickCheck.Arbitrary.Arbitrary r, GHC.Classes.Ord r) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Range.Range r)
instance GHC.Classes.Ord a => Data.Intersection.HasIntersectionWith (Data.Range.Range a) (Data.Range.Range a)
instance GHC.Classes.Ord a => Data.Intersection.IsIntersectableWith (Data.Range.Range a) (Data.Range.Range a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Range.EndPoint a)
instance Data.Functor.Classes.Show1 Data.Range.EndPoint
instance GHC.Read.Read a => GHC.Read.Read (Data.Range.EndPoint a)
instance Data.Functor.Classes.Read1 Data.Range.EndPoint
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Range.EndPoint a)
instance Test.QuickCheck.Arbitrary.Arbitrary r => Test.QuickCheck.Arbitrary.Arbitrary (Data.Range.EndPoint r)


module Data.RealNumber.Rational

-- | Real Numbers represented using Rational numbers. The number type
--   itself is exact in the sense that we can represent any rational
--   number.
--   
--   The parameter, a natural number, represents the precision (in number
--   of decimals behind the period) with which we display the numbers when
--   printing them (using Show).
--   
--   If the number cannot be displayed exactly a '~' is printed after the
--   number.
newtype RealNumber (p :: Nat)
RealNumber :: Rational -> RealNumber (p :: Nat)

-- | Fixed-precision representation of a <a>RealNumber</a>. If there's
--   insufficient precision to accurately represent the <a>RealNumber</a>
--   then the <a>Lossy</a> constructor will be used.
data AsFixed p
Exact :: !Fixed p -> AsFixed p
Lossy :: !Fixed p -> AsFixed p

-- | Cast <a>RealNumber</a> to a fixed-precision number. Data-loss caused
--   by insufficient precision will be marked by the <a>Lossy</a>
--   constructor.
asFixed :: KnownNat p => RealNumber p -> AsFixed (NatPrec p)

-- | Cast <a>RealNumber</a> to a fixed-precision number. Data is silently
--   lost if there's insufficient precision.
toFixed :: KnownNat p => RealNumber p -> Fixed (NatPrec p)

-- | Cast a fixed-precision number to a <a>RealNumber</a>.
fromFixed :: KnownNat p => Fixed (NatPrec p) -> RealNumber p

-- | (Kind) This is the kind of type-level natural numbers.
data Nat
instance Control.DeepSeq.NFData (Data.RealNumber.Rational.RealNumber p)
instance Data.Aeson.Types.FromJSON.FromJSON (Data.RealNumber.Rational.RealNumber p)
instance Data.Aeson.Types.ToJSON.ToJSON (Data.RealNumber.Rational.RealNumber p)
instance Data.Hashable.Class.Hashable (Data.RealNumber.Rational.RealNumber p)
instance GHC.Generics.Generic (Data.RealNumber.Rational.RealNumber p)
instance GHC.Real.RealFrac (Data.RealNumber.Rational.RealNumber p)
instance GHC.Real.Real (Data.RealNumber.Rational.RealNumber p)
instance GHC.Real.Fractional (Data.RealNumber.Rational.RealNumber p)
instance GHC.Num.Num (Data.RealNumber.Rational.RealNumber p)
instance GHC.TypeNats.KnownNat p => Data.Data.Data (Data.RealNumber.Rational.RealNumber p)
instance GHC.Classes.Ord (Data.RealNumber.Rational.RealNumber p)
instance GHC.Classes.Eq (Data.RealNumber.Rational.RealNumber p)
instance forall k (p :: k). GHC.Classes.Eq (Data.RealNumber.Rational.AsFixed p)
instance forall k (p :: k). Data.Fixed.HasResolution p => GHC.Show.Show (Data.RealNumber.Rational.AsFixed p)
instance GHC.TypeNats.KnownNat p => GHC.Show.Show (Data.RealNumber.Rational.RealNumber p)
instance GHC.TypeNats.KnownNat p => Data.Fixed.HasResolution (Data.RealNumber.Rational.NatPrec p)
instance GHC.TypeNats.KnownNat p => GHC.Read.Read (Data.RealNumber.Rational.RealNumber p)
instance GHC.TypeNats.KnownNat p => Test.QuickCheck.Arbitrary.Arbitrary (Data.RealNumber.Rational.RealNumber p)
instance System.Random.Random (Data.RealNumber.Rational.RealNumber p)


module Data.Sequence.Util

-- | Partition the seq s given a monotone predicate p into (xs,ys) such
--   that
--   
--   all elements in xs do *not* satisfy the predicate p all elements in ys
--   do satisfy the predicate p
--   
--   all elements in s occur in either xs or ys.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the time to execute
--   the predicate.
splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a)


module Data.Set.Util
data S
S :: String -> S
cmpS :: S -> S -> Ordering

-- | Given a monotonic function f that maps a to b, split the sequence s
--   depending on the b values. I.e. the result (l,m,r) is such that * all
--   (&lt; x) . fmap f $ l * all (== x) . fmap f $ m * all (&gt; x) . fmap
--   f $ r
--   
--   running time: &lt;math&gt;
splitOn :: Ord b => (a -> b) -> b -> Set a -> (Set a, Set a, Set a)

-- | Given a monotonic function f that orders <tt>a</tt>, split the
--   sequence <tt>s</tt> into three parts. I.e. the result (lt,eq,gt) is
--   such that * all (x -&gt; f x == LT) . fmap f $ lt * all (x -&gt; f x
--   == EQ) . fmap f $ eq * all (x -&gt; f x == GT) . fmap f $ gt
--   
--   running time: &lt;math&gt;
splitBy :: (a -> Ordering) -> Set a -> (Set a, Set a, Set a)

-- | Constructs a Set using the given Order.
--   
--   Note that this is dangerous as the resulting set may not abide the
--   ordering expected of such sets.
--   
--   running time: &lt;math&gt;
fromListBy :: (a -> a -> Ordering) -> [a] -> Set a

-- | Given two sets l and r, such that all elements of l occur before r,
--   join the two sets into a combined set.
--   
--   running time: &lt;math&gt;
join :: Set a -> Set a -> Set a

-- | Inserts an element into the set, assuming that the set is ordered by
--   the given order.
--   
--   <pre>
--   &gt;&gt;&gt; insertBy cmpS (S "ccc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
--   fromList [S "a",S "bb",S "ccc",S "dddd"]
--   </pre>
--   
--   When trying to insert an element that equals an element already in the
--   set (according to the given comparator), this function replaces the
--   old element by the new one:
--   
--   <pre>
--   &gt;&gt;&gt; insertBy cmpS (S "cc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
--   fromList [S "a",S "cc",S "dddd"]
--   </pre>
--   
--   running time: &lt;math&gt;
insertBy :: (a -> a -> Ordering) -> a -> Set a -> Set a

-- | Deletes an element from the set, assuming the set is ordered by the
--   given ordering.
--   
--   <pre>
--   &gt;&gt;&gt; deleteAllBy cmpS (S "bb") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]
--   fromList [S "a",S "dddd"]
--   
--   &gt;&gt;&gt; deleteAllBy cmpS (S "bb") $ fromListBy cmpS [S "a" , S "bb" , S "cc", S "dd", S "ee", S "ff", S "dddd"]
--   fromList [S "a",S "dddd"]
--   </pre>
--   
--   running time: &lt;math&gt;
deleteAllBy :: (a -> a -> Ordering) -> a -> Set a -> Set a

-- | Run a query, eg. lookupGE, on the set with the given ordering.
--   
--   Note: The <a>binarySearchIn</a> function may be a useful alternative
--   to <a>queryBy</a>
--   
--   <pre>
--   &gt;&gt;&gt; queryBy cmpS Set.lookupGE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
--   Just (S "bbb")
--   
--   &gt;&gt;&gt; queryBy cmpS Set.lookupLE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
--   Just (S "a")
--   
--   &gt;&gt;&gt; queryBy cmpS Set.lookupGE (S "333") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]
--   Just (S "bbb")
--   </pre>
queryBy :: (a -> a -> Ordering) -> (forall b. Ord b => b -> Set b -> t b) -> a -> Set a -> t a
instance GHC.Show.Show Data.Set.Util.S


-- | Tree-related utilities.
module Data.Tree.Util

-- | Nodes in a tree are typically either an internal node or a leaf node
data TreeNode v a
InternalNode :: v -> TreeNode v a
LeafNode :: a -> TreeNode v a

-- | A TreeNode is isomorphic to Either
_TreeNodeEither :: Iso' (TreeNode v p) (Either v p)

-- | Zipper for rose trees
data Zipper a
Zipper :: Tree a -> [([Tree a], a, [Tree a])] -> Zipper a
[focus] :: Zipper a -> Tree a
[ancestors] :: Zipper a -> [([Tree a], a, [Tree a])]

-- | Create a new zipper focussiong on the root.
root :: Tree a -> Zipper a

-- | Move the focus to the parent of this node.
up :: Zipper a -> Maybe (Zipper a)

-- | Move the focus to the first child of this node.
--   
--   <pre>
--   &gt;&gt;&gt; firstChild $ root myTree
--   Just (Zipper {focus = Node {rootLabel = 1, subForest = []}, ancestors = [([],0,[Node {rootLabel = 2, subForest = []},Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})
--   </pre>
firstChild :: Zipper a -> Maybe (Zipper a)

-- | Move the focus to the next sibling of this node
--   
--   <pre>
--   &gt;&gt;&gt; (firstChild $ root myTree) &gt;&gt;= nextSibling
--   Just (Zipper {focus = Node {rootLabel = 2, subForest = []}, ancestors = [([Node {rootLabel = 1, subForest = []}],0,[Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})
--   </pre>
nextSibling :: Zipper a -> Maybe (Zipper a)

-- | Move the focus to the next sibling of this node
prevSibling :: Zipper a -> Maybe (Zipper a)

-- | Given a zipper that focussses on some subtree t, construct a list with
--   zippers that focus on each child.
allChildren :: Zipper a -> [Zipper a]

-- | Given a zipper that focussses on some subtree t, construct a list with
--   zippers that focus on each of the nodes in the subtree of t.
allTrees :: Zipper a -> [Zipper a]

-- | Creates a new tree from the zipper that thas the current node as root.
--   The ancestorTree (if there is any) forms the first child in this new
--   root.
unZipperLocal :: Zipper a -> Tree a

-- | Constructs a tree from the list of ancestors (if there are any)
constructTree :: [([Tree a], a, [Tree a])] -> Maybe (Tree a)

-- | Given a predicate on an element, find a node that matches the
--   predicate, and turn that node into the root of the tree.
--   
--   running time: &lt;math&gt; where &lt;math&gt; is the size of the tree,
--   and &lt;math&gt; is the time to evaluate a predicate.
--   
--   <pre>
--   &gt;&gt;&gt; findEvert (== 4) myTree
--   Just (Node {rootLabel = 4, subForest = [Node {rootLabel = 3, subForest = [Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []},Node {rootLabel = 2, subForest = []}]}]}]})
--   
--   &gt;&gt;&gt; findEvert (== 5) myTree
--   Nothing
--   </pre>
findEvert :: (a -> Bool) -> Tree a -> Maybe (Tree a)

-- | Given a predicate matching on a subtree, find a node that matches the
--   predicate, and turn that node into the root of the tree.
--   
--   running time: &lt;math&gt; where &lt;math&gt; is the size of the tree,
--   and &lt;math&gt; is the time to evaluate a predicate on a subtree of
--   size &lt;math&gt;.
findEvert' :: (Tree a -> Bool) -> Tree a -> Maybe (Tree a)

-- | Function to extract a path between a start node and an end node (if
--   such a path exists). If there are multiple paths, no guarantees are
--   given about which one is returned.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the size of the
--   tree, and &lt;math&gt; and &lt;math&gt; are the times it takes to
--   evaluate the <tt>isStartingNode</tt> and <tt>isEndingNode</tt>
--   predicates.
--   
--   <pre>
--   &gt;&gt;&gt; findPath (== 1) (==4) myTree
--   Just [1,0,3,4]
--   
--   &gt;&gt;&gt; findPath (== 1) (==2) myTree
--   Just [1,0,2]
--   
--   &gt;&gt;&gt; findPath (== 1) (==1) myTree
--   Just [1]
--   
--   &gt;&gt;&gt; findPath (== 1) (==2) myTree
--   Just [1,0,2]
--   
--   &gt;&gt;&gt; findPath (== 4) (==2) myTree
--   Just [4,3,0,2]
--   </pre>
findPath :: (a -> Bool) -> (a -> Bool) -> Tree a -> Maybe [a]

-- | Given a predicate on a, find (the path to) a node that satisfies the
--   predicate.
--   
--   <pre>
--   &gt;&gt;&gt; findNode (== 4) myTree
--   Just [0,3,4]
--   </pre>
findNode :: (a -> Bool) -> Tree a -> Maybe [a]

-- | Find all paths to nodes that satisfy the predicate
--   
--   running time: &lt;math&gt; where &lt;math&gt; is the size of the tree,
--   and &lt;math&gt; is the time to evaluate a predicate on a subtree of
--   size &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; findNodes ((&lt; 4) . rootLabel) myTree
--   [[0],[0,1],[0,2],[0,3]]
--   
--   &gt;&gt;&gt; findNodes (even . rootLabel) myTree
--   [[0],[0,2],[0,3,4]]
--   
--   &gt;&gt;&gt; let size = length in findNodes ((&gt; 1) . size) myTree
--   [[0],[0,3]]
--   </pre>
findNodes :: (Tree a -> Bool) -> Tree a -> [[a]]

-- | BFS Traversal of the rose tree that decomposes it into levels.
--   
--   running time: &lt;math&gt;
levels :: Tree a -> NonEmpty (NonEmpty a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Tree.Util.TreeNode v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.Tree.Util.TreeNode v a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Tree.Util.Zipper a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Tree.Util.Zipper a)
instance Data.Bifunctor.Bifunctor Data.Tree.Util.TreeNode
instance Data.Bifoldable.Bifoldable Data.Tree.Util.TreeNode
instance Data.Bitraversable.Bitraversable Data.Tree.Util.TreeNode


-- | Several types of Binary trees.
module Data.BinaryTree

-- | Binary tree that stores its values (of type a) in the leaves. Internal
--   nodes store something of type v.
data BinLeafTree v a
Leaf :: !a -> BinLeafTree v a
Node :: BinLeafTree v a -> !v -> BinLeafTree v a -> BinLeafTree v a

-- | smart constructor
node :: Measured v a => BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a

-- | Create a balanced tree, i.e. a tree of height &lt;math&gt; with the
--   elements in the leaves.
--   
--   &lt;math&gt; time.
asBalancedBinLeafTree :: NonEmpty a -> BinLeafTree Size (Elem a)

-- | Given a function to combine internal nodes into b's and leafs into
--   b's, traverse the tree bottom up, and combine everything into one b.
foldUp :: (b -> v -> b -> b) -> (a -> b) -> BinLeafTree v a -> b

-- | Traverses the tree bottom up, recomputing the assocated values.
foldUpData :: (w -> v -> w -> w) -> (a -> w) -> BinLeafTree v a -> BinLeafTree w a

-- | Takes two trees, that have the same structure, and uses the provided
--   functions to "zip" them together
zipExactWith :: (u -> v -> w) -> (a -> b -> c) -> BinLeafTree u a -> BinLeafTree v b -> BinLeafTree w c

-- | &lt;math&gt; Convert binary tree to a rose tree, aka <a>Tree</a>.
toRoseTree :: BinLeafTree v a -> Tree (TreeNode v a)

-- | 2-dimensional ASCII drawing of a tree.
drawTree :: (Show v, Show a) => BinLeafTree v a -> String

-- | Binary tree in which we store the values of type a in internal nodes.
data BinaryTree a
Nil :: BinaryTree a
Internal :: BinaryTree a -> !a -> BinaryTree a -> BinaryTree a

-- | Get the element stored at the root, if it exists
access :: BinaryTree a -> Maybe a

-- | Create a balanced binary tree.
--   
--   running time: &lt;math&gt;
asBalancedBinTree :: [a] -> BinaryTree a

-- | Fold function for folding over a binary tree.
foldBinaryUp :: b -> (a -> b -> b -> b) -> BinaryTree a -> BinaryTree (a, b)

-- | Convert a <tt>BinaryTree</tt> into a RoseTree
toRoseTree' :: BinaryTree a -> Maybe (Tree a)

-- | Draw a binary tree.
drawTree' :: Show a => BinaryTree a -> String
instance GHC.Generics.Generic (Data.BinaryTree.BinLeafTree v a)
instance GHC.Base.Functor (Data.BinaryTree.BinLeafTree v)
instance (GHC.Classes.Ord a, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.BinaryTree.BinLeafTree v a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.BinaryTree.BinLeafTree v a)
instance (GHC.Read.Read a, GHC.Read.Read v) => GHC.Read.Read (Data.BinaryTree.BinLeafTree v a)
instance (GHC.Show.Show a, GHC.Show.Show v) => GHC.Show.Show (Data.BinaryTree.BinLeafTree v a)
instance GHC.Generics.Generic (Data.BinaryTree.BinaryTree a)
instance Data.Traversable.Traversable Data.BinaryTree.BinaryTree
instance Data.Foldable.Foldable Data.BinaryTree.BinaryTree
instance GHC.Base.Functor Data.BinaryTree.BinaryTree
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.BinaryTree.BinaryTree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.BinaryTree.BinaryTree a)
instance GHC.Read.Read a => GHC.Read.Read (Data.BinaryTree.BinaryTree a)
instance GHC.Show.Show a => GHC.Show.Show (Data.BinaryTree.BinaryTree a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.BinaryTree.BinaryTree a)
instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.BinaryTree.BinaryTree a)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.BinaryTree.BinLeafTree v a)
instance Data.Bifunctor.Bifunctor Data.BinaryTree.BinLeafTree
instance Data.Measured.Class.Measured v a => Data.Measured.Class.Measured v (Data.BinaryTree.BinLeafTree v a)
instance Data.Foldable.Foldable (Data.BinaryTree.BinLeafTree v)
instance Data.Semigroup.Foldable.Class.Foldable1 (Data.BinaryTree.BinLeafTree v)
instance Data.Traversable.Traversable (Data.BinaryTree.BinLeafTree v)
instance Data.Measured.Class.Measured v a => GHC.Base.Semigroup (Data.BinaryTree.BinLeafTree v a)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.BinaryTree.BinLeafTree v a)


-- | Add an unbounded/infintity element to a data type. Essentially,
--   <a>Bottom</a> adds &lt;math&gt; (and is pretty much identical to
--   Maybe), whereas <a>Top</a> adds &lt;math&gt;. The <a>UnBounded</a>
--   type adds both.
module Data.UnBounded

-- | <tt>Top a</tt> represents the type a, together with a <a>Top</a>
--   element, i.e. an element that is greater than any other element. We
--   can think of `Top a` being defined as:
--   
--   <pre>
--   &gt;&gt;&gt; data Top a = ValT a | Top
--   </pre>
data Top a
pattern ValT :: a -> Top a
pattern Top :: Top a

-- | <tt>Top a</tt> values are isomorphing to <tt>Maybe a</tt> values.
topToMaybe :: Top a -> Maybe a

-- | <a>ValT</a> prism. Can be used to access the non-bottom element if it
--   exists:
--   
--   <pre>
--   &gt;&gt;&gt; ValT True &amp; _ValT %~ not
--   ValT False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Top &amp; _ValT %~ not
--   Top
--   </pre>
_ValT :: Prism (Top a) (Top b) a b

-- | <a>Top</a> prism.
_Top :: Prism' (Top a) ()

-- | Iso between a <tt>Top a</tt> and a <tt>Maybe a</tt>, interpreting a
--   <a>Top</a> as a <a>Nothing</a> and vice versa. Note that this reverses
--   the ordering of the elements.
--   
--   <pre>
--   &gt;&gt;&gt; ValT 5 ^. _TopMaybe
--   Just 5
--   
--   &gt;&gt;&gt; Just 5 ^.re _TopMaybe
--   ValT 5
--   
--   &gt;&gt;&gt; Top ^. _TopMaybe
--   Nothing
--   
--   &gt;&gt;&gt; Nothing ^.re _TopMaybe
--   Top
--   </pre>
_TopMaybe :: Iso' (Top a) (Maybe a)

-- | <tt>`Bottom a`</tt> represents the type a, together with a
--   <a>Bottom</a> element, i.e. an element that is smaller than any other
--   element. We can think of <tt>`Bottom a`</tt> being defined as:
--   
--   <pre>
--   &gt;&gt;&gt; data Bottom a = Bottom | ValB a
--   </pre>
data Bottom a
pattern Bottom :: Bottom a
pattern ValB :: a -> Bottom a

-- | `Bottom a` values are isomorphing to `Maybe a` values.
bottomToMaybe :: Bottom a -> Maybe a

-- | <a>ValB</a> prism. Can be used to access the non-bottom element if it
--   exists:
--   
--   <pre>
--   &gt;&gt;&gt; ValB True &amp; _ValB %~ not
--   ValB False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Bottom &amp; _ValB %~ not
--   Bottom
--   </pre>
_ValB :: Prism (Bottom a) (Bottom b) a b

-- | <a>Bottom</a> prism.
_Bottom :: Prism' (Bottom a) ()

-- | Iso between a 'Bottom a' and a 'Maybe a', interpreting a Bottom as a
--   Nothing and vice versa.
--   
--   <pre>
--   &gt;&gt;&gt; ValB 5 ^. _BottomMaybe
--   Just 5
--   
--   &gt;&gt;&gt; Just 5 ^.re _BottomMaybe
--   ValB 5
--   
--   &gt;&gt;&gt; Bottom ^. _BottomMaybe
--   Nothing
--   
--   &gt;&gt;&gt; Nothing ^.re _BottomMaybe
--   Bottom
--   </pre>
_BottomMaybe :: Iso' (Bottom a) (Maybe a)

-- | `UnBounded a` represents the type a, together with an element
--   <a>MaxInfinity</a> larger than any other element, and an element
--   <a>MinInfinity</a>, smaller than any other element.
data UnBounded a
MinInfinity :: UnBounded a
Val :: a -> UnBounded a
[_unUnBounded] :: UnBounded a -> a
MaxInfinity :: UnBounded a

-- | Prism to access unbounded value if it exists.
--   
--   <pre>
--   &gt;&gt;&gt; Val True ^? _Val
--   Just True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; MinInfinity ^? _Val :: Maybe Bool
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Val True &amp; _Val %~ not
--   Val False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; MaxInfinity &amp; _Val %~ not
--   MaxInfinity
--   </pre>
_Val :: Prism (UnBounded a) (UnBounded b) a b

-- | Test if an Unbounded is actually bounded.
--   
--   <pre>
--   &gt;&gt;&gt; unBoundedToMaybe (Val 5)
--   Just 5
--   
--   &gt;&gt;&gt; unBoundedToMaybe MinInfinity
--   Nothing
--   
--   &gt;&gt;&gt; unBoundedToMaybe MaxInfinity
--   Nothing
--   </pre>
unBoundedToMaybe :: UnBounded a -> Maybe a
instance Data.Functor.Classes.Eq1 Data.UnBounded.Top
instance GHC.Base.Monad Data.UnBounded.Top
instance GHC.Base.Applicative Data.UnBounded.Top
instance Data.Traversable.Traversable Data.UnBounded.Top
instance Data.Foldable.Foldable Data.UnBounded.Top
instance GHC.Base.Functor Data.UnBounded.Top
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.UnBounded.Top a)
instance Data.Functor.Classes.Ord1 Data.UnBounded.Bottom
instance Data.Functor.Classes.Eq1 Data.UnBounded.Bottom
instance GHC.Base.Monad Data.UnBounded.Bottom
instance GHC.Base.Applicative Data.UnBounded.Bottom
instance Data.Traversable.Traversable Data.UnBounded.Bottom
instance Data.Foldable.Foldable Data.UnBounded.Bottom
instance GHC.Base.Functor Data.UnBounded.Bottom
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.UnBounded.Bottom a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.UnBounded.Bottom a)
instance Data.Traversable.Traversable Data.UnBounded.UnBounded
instance Data.Foldable.Foldable Data.UnBounded.UnBounded
instance GHC.Base.Functor Data.UnBounded.UnBounded
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.UnBounded.UnBounded a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.UnBounded.UnBounded a)
instance GHC.Show.Show a => GHC.Show.Show (Data.UnBounded.UnBounded a)
instance GHC.Num.Num a => GHC.Num.Num (Data.UnBounded.UnBounded a)
instance GHC.Real.Fractional a => GHC.Real.Fractional (Data.UnBounded.UnBounded a)
instance GHC.Show.Show a => GHC.Show.Show (Data.UnBounded.Bottom a)
instance Data.Functor.Classes.Ord1 Data.UnBounded.Top
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.UnBounded.Top a)
instance GHC.Show.Show a => GHC.Show.Show (Data.UnBounded.Top a)


-- | Some basic types, mostly strict triples and pairs.
module Data.Util

-- | strict triple
data STR a b c
STR :: !a -> !b -> !c -> STR a b c

-- | Strict Triple with all items the same
type Three = V3

-- | Pattern synonym for strict triples.
pattern Three :: a -> a -> a -> Three a

-- | Generate All unique unordered triplets.
uniqueTriplets :: [a] -> [Three a]

-- | Strict pair
data SP a b
SP :: !a -> !b -> SP a b

-- | <ul>
--   <li>Strict pair whose elements are of the same type.</li>
--   </ul>
--   
--   Strict pair with both items the same
type Two = V2

-- | Pattern synonym for strict pairs.
pattern Two :: a -> a -> Two a

-- | Given a list xs, generate all unique (unordered) pairs.
uniquePairs :: [a] -> [Two a]

-- | A version of List.tails in which we remove the emptylist
nonEmptyTails :: [a] -> [[a]]
instance GHC.Generics.Generic (Data.Util.STR a b c)
instance GHC.Base.Functor (Data.Util.STR a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b, GHC.Classes.Ord c) => GHC.Classes.Ord (Data.Util.STR a b c)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b, GHC.Classes.Eq c) => GHC.Classes.Eq (Data.Util.STR a b c)
instance (GHC.Show.Show a, GHC.Show.Show b, GHC.Show.Show c) => GHC.Show.Show (Data.Util.STR a b c)
instance GHC.Generics.Generic (Data.Util.SP a b)
instance GHC.Base.Functor (Data.Util.SP a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Util.SP a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Util.SP a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Util.SP a b)
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b) => GHC.Base.Semigroup (Data.Util.SP a b)
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b, GHC.Base.Monoid a, GHC.Base.Monoid b) => GHC.Base.Monoid (Data.Util.SP a b)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData b) => Control.DeepSeq.NFData (Data.Util.SP a b)
instance Control.Lens.Tuple.Field1 (Data.Util.SP a b) (Data.Util.SP c b) a c
instance Control.Lens.Tuple.Field2 (Data.Util.SP a b) (Data.Util.SP a c) b c
instance Data.Bifunctor.Bifunctor Data.Util.SP
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b, GHC.Base.Semigroup c) => GHC.Base.Semigroup (Data.Util.STR a b c)
instance (GHC.Base.Semigroup a, GHC.Base.Semigroup b, GHC.Base.Semigroup c, GHC.Base.Monoid a, GHC.Base.Monoid b, GHC.Base.Monoid c) => GHC.Base.Monoid (Data.Util.STR a b c)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData b, Control.DeepSeq.NFData c) => Control.DeepSeq.NFData (Data.Util.STR a b c)
instance Control.Lens.Tuple.Field1 (Data.Util.STR a b c) (Data.Util.STR d b c) a d
instance Control.Lens.Tuple.Field2 (Data.Util.STR a b c) (Data.Util.STR a d c) b d
instance Control.Lens.Tuple.Field3 (Data.Util.STR a b c) (Data.Util.STR a b d) c d


module Data.IndexedDoublyLinkedList.Bare

-- | Doubly linked list implemented by a mutable vector. So actually this
--   data type can represent a collection of Linked Lists that can
--   efficiently be concatenated and split.
--   
--   Supports O(1) indexing, and O(1) insertions, deletions
newtype IDLList s
IDLList :: MVector s Cell -> IDLList s
[llist] :: IDLList s -> MVector s Cell

-- | Cells in the Linked List
data Cell
Cell :: !Maybe Index -> !Maybe Index -> Cell
[prev] :: Cell -> !Maybe Index
[next] :: Cell -> !Maybe Index

-- | Empty cell with no next or prev cells.
emptyCell :: Cell

-- | Monad in which we can use the IndexedDoublyLinkedList.
data IDLListMonad s a

-- | Runs a DLList Computation, starting with n singleton values
runIDLListMonad :: Int -> (forall s. IDLListMonad s a) -> a

-- | Cell indices. Must be non-negative.
type Index = Int

-- | Constructs a new DoublyLinkedList, of size at most n
singletons :: (PrimMonad m, s ~ PrimState m) => Int -> m (IDLList s)

-- | Sets the DoublyLinkedList to the given List.
--   
--   Indices that do not occur in the list are not touched.
writeList :: NonEmpty Index -> IDLListMonad s ()

-- | Next element in the List
getNext :: Index -> IDLListMonad s (Maybe Index)

-- | Previous Element in the List
getPrev :: Index -> IDLListMonad s (Maybe Index)

-- | Computes a maximal length list starting from the Given index
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListFrom :: Index -> IDLListMonad s (NonEmpty Index)

-- | Computes a maximal length list by walking backwards in the
--   DoublyLinkedList, starting from the Given index
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListFromR :: Index -> IDLListMonad s (NonEmpty Index)

-- | Computes a maximal length list that contains the element i.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListContains :: Index -> IDLListMonad s (NonEmpty Index)

-- | Takes the current element and its k next's
toListFromK :: Index -> Int -> IDLListMonad s (NonEmpty Index)

-- | Takes the current element and its k prev's
toListFromRK :: Index -> Int -> IDLListMonad s (NonEmpty Index)

-- | Inserts the second argument after the first one into the linked list
insertAfter :: Index -> Index -> IDLListMonad s ()

-- | Inserts the second argument before the first one into the linked list
insertBefore :: Index -> Index -> IDLListMonad s ()

-- | Deletes the element from the linked list. This element thus
--   essentially becomes a singleton list.
delete :: Index -> IDLListMonad s ()

-- | For debugging purposes, dump the values and the cells
dump :: IDLListMonad s (Vector Cell)
instance GHC.Classes.Eq Data.IndexedDoublyLinkedList.Bare.Cell
instance GHC.Show.Show Data.IndexedDoublyLinkedList.Bare.Cell
instance GHC.Base.Monad (Data.IndexedDoublyLinkedList.Bare.IDLListMonad s)
instance GHC.Base.Applicative (Data.IndexedDoublyLinkedList.Bare.IDLListMonad s)
instance GHC.Base.Functor (Data.IndexedDoublyLinkedList.Bare.IDLListMonad s)
instance Control.Monad.Primitive.PrimMonad (Data.IndexedDoublyLinkedList.Bare.IDLListMonad s)
instance Control.Monad.Reader.Class.MonadReader (Data.IndexedDoublyLinkedList.Bare.IDLList s) (Data.IndexedDoublyLinkedList.Bare.IDLListMonad s)


module Data.IndexedDoublyLinkedList

-- | Doubly linked list implemented by a mutable vector. So actually this
--   data type can represent a collection of Linked Lists that can
--   efficiently be concatenated and split.
--   
--   Supports O(1) indexing, and O(1) insertions, deletions
data DLList s a
DLList :: !Vector a -> !MVector s Cell -> DLList s a
[values] :: DLList s a -> !Vector a
[llist] :: DLList s a -> !MVector s Cell

-- | Cells in the Linked List
data Cell
Cell :: Maybe Index -> Maybe Index -> Cell
[prev] :: Cell -> Maybe Index
[next] :: Cell -> Maybe Index

-- | Empty cell with no next or prev cells.
emptyCell :: Cell

-- | Monad in which we can use the IndexedDoublyLinkedList.
data DLListMonad s b a

-- | Runs a DLList Computation, starting with singleton values, crated from
--   the input vector.
runDLListMonad :: Vector b -> (forall s. DLListMonad s b a) -> a

-- | Cell indices. Must be non-negative.
type Index = Int

-- | Constructs a new DoublyLinkedList. Every element is its own singleton
--   list
singletons :: (PrimMonad m, s ~ PrimState m) => Vector b -> m (DLList s b)

-- | Sets the DoublyLinkedList to the given List.
--   
--   Indices that do not occur in the list are not touched.
writeList :: NonEmpty Index -> DLListMonad s b ()

-- | Gets the value at Index i
valueAt :: Index -> DLListMonad s b b

-- | Next element in the List
getNext :: Index -> DLListMonad s b (Maybe Index)

-- | Previous Element in the List
getPrev :: Index -> DLListMonad s b (Maybe Index)

-- | Computes a maximal length list starting from the Given index
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListFrom :: Index -> DLListMonad s b (NonEmpty Index)

-- | Computes a maximal length list by walking backwards in the
--   DoublyLinkedList, starting from the Given index
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListFromR :: Index -> DLListMonad s b (NonEmpty Index)

-- | Computes a maximal length list that contains the element i.
--   
--   running time: &lt;math&gt;, where &lt;math&gt; is the length of the
--   output list
toListContains :: Index -> DLListMonad s b (NonEmpty Index)

-- | Takes the current element and its k next's
toListFromK :: Index -> Int -> DLListMonad s b (NonEmpty Index)

-- | Takes the current element and its k prev's
toListFromRK :: Index -> Int -> DLListMonad s b (NonEmpty Index)

-- | Inserts the second argument after the first one into the linked list
insertAfter :: Index -> Index -> DLListMonad s b ()

-- | Inserts the second argument before the first one into the linked list
insertBefore :: Index -> Index -> DLListMonad s b ()

-- | Deletes the element from the linked list. This element thus
--   essentially becomes a singleton list. Returns the pair of indices that
--   now have become neighbours (i.e. the predecessor and successor of j
--   just before we deleted j).
delete :: Index -> DLListMonad s b (Maybe Index, Maybe Index)

-- | For debugging purposes, dump the values and the cells
dump :: DLListMonad s a (Vector a, Vector Cell)
instance GHC.Classes.Eq Data.IndexedDoublyLinkedList.Cell
instance GHC.Show.Show Data.IndexedDoublyLinkedList.Cell
instance GHC.Base.Monad (Data.IndexedDoublyLinkedList.DLListMonad s b)
instance GHC.Base.Applicative (Data.IndexedDoublyLinkedList.DLListMonad s b)
instance GHC.Base.Functor (Data.IndexedDoublyLinkedList.DLListMonad s b)
instance Control.Monad.Primitive.PrimMonad (Data.IndexedDoublyLinkedList.DLListMonad s b)
instance Control.Monad.Reader.Class.MonadReader (Data.IndexedDoublyLinkedList.DLList s b) (Data.IndexedDoublyLinkedList.DLListMonad s b)
instance GHC.Base.Functor (Data.IndexedDoublyLinkedList.DLList s)


module Data.Vector.Circular.Util

-- | Access the ith item in the CircularVector (w.r.t the rotation) as a
--   lens
item :: Int -> Lens' (CircularVector a) a

-- | All elements, starting with the focus, going to the right
--   
--   <pre>
--   &gt;&gt;&gt; rightElements $ unsafeFromList [3,4,5,1,2]
--   [3,4,5,1,2]
--   </pre>
rightElements :: CircularVector a -> NonEmptyVector a

-- | All elements, starting with the focus, going to the left
--   
--   <pre>
--   &gt;&gt;&gt; leftElements $ unsafeFromList [3,4,5,1,2]
--   [3,2,1,5,4]
--   </pre>
leftElements :: CircularVector a -> NonEmptyVector a

-- | Finds an element in the CircularVector
--   
--   <pre>
--   &gt;&gt;&gt; findRotateTo (== 3) $ unsafeFromList [1..5]
--   Just (CircularVector {vector = [1,2,3,4,5], rotation = 2})
--   
--   &gt;&gt;&gt; findRotateTo (== 7) $ unsafeFromList [1..5]
--   Nothing
--   </pre>
findRotateTo :: (a -> Bool) -> CircularVector a -> Maybe (CircularVector a)

-- | Test if the circular list is a cyclic shift of the second list.
--   
--   Running time: &lt;math&gt;, where &lt;math&gt; and &lt;math&gt; are
--   the sizes of the lists.
isShiftOf :: Eq a => CircularVector a -> CircularVector a -> Bool

-- | label the circular vector with indices, starting from zero at the
--   current focus, going right.
--   
--   Running time: &lt;math&gt;
withIndicesRight :: CircularVector a -> CircularVector (Int :+ a)
instance Data.Semigroup.Foldable.Class.Foldable1 Data.Vector.NonEmpty.Internal.NonEmptyVector
instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.Vector.Circular.CircularVector a)


module Data.Yaml.Util

-- | Write the output to yaml
encodeYaml :: ToJSON a => a -> ByteString

-- | Encode a yaml file
encodeYamlFile :: ToJSON a => FilePath -> a -> IO ()

-- | alias for decodeEither' from the Yaml Package
decodeYaml :: FromJSON a => ByteString -> Either ParseException a

-- | alias for reading a yaml file
decodeYamlFile :: FromJSON a => FilePath -> IO (Either ParseException a)

-- | Prints the yaml
printYaml :: ToJSON a => a -> IO ()

-- | Given a list of candidate parsers, select the right one
parseVersioned :: [(Version -> Bool, Value -> Parser a)] -> Value -> Parser (Versioned a)

-- | Data type for things that have a version
data Versioned a
Versioned :: Version -> a -> Versioned a

-- | Unpack versioned data type.
unversioned :: Versioned a -> a
instance Data.Traversable.Traversable Data.Yaml.Util.Versioned
instance Data.Foldable.Foldable Data.Yaml.Util.Versioned
instance GHC.Base.Functor Data.Yaml.Util.Versioned
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Yaml.Util.Versioned a)
instance GHC.Generics.Generic (Data.Yaml.Util.Versioned a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Yaml.Util.Versioned a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Yaml.Util.Versioned a)
instance Data.Aeson.Types.FromJSON.FromJSON Data.Yaml.Util.V
instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.Yaml.Util.Versioned a)


-- | Implements Fishyer-Yates shuffle.
module System.Random.Shuffle

-- | Fisher–Yates shuffle, which shuffles a list/foldable uniformly at
--   random.
--   
--   running time: &lt;math&gt;.
shuffle :: (Foldable f, MonadRandom m) => f a -> m (Vector a)