h$I      !"#$%&'()*+,-./0123456789 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~      !!!"""""""""""""""""""""""""""""""""""""""""""""""""""""""""#####################################################################$$$$$$$$$$$$$$$$%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%&'''''''''''(((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))*************************************************+++++++++++++++++++++++++++++++++,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,----------------------------------........//////////////////03(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Yhgeometry-combinatorialGiven a monotonic predicate p and a data structure v, find the element v[h] such that thatfor every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True)returns Nothing if no element satisfies prunning time:  O(T*\log n), where T' is the time to execute the predicate.hgeometry-combinatorialGiven a monotonic predicate p and a data structure v, find the index h such that thatfor every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True)returns Nothing if no element satisfies prunning time:  O(T*\log n), where T' is the time to execute the predicate.hgeometry-combinatorialGiven 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 = Truerunning time: O(\log(u - l))hgeometry-combinatorialGiven a value  \varepsilon, a monotone predicate p, and two values l and u with:p l = Falsep u = Truel < uwe find a value h such that:p h = Truep (h - \varepsilon) = False0binarySearchUntil (0.1) (>= 0.5) 0 (1 :: Double)0.51binarySearchUntil (0.1) (>= 0.51) 0 (1 :: Double)0.56252binarySearchUntil (0.01) (>= 0.51) 0 (1 :: Double)0.515625(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? = hgeometry-combinatorialDivide and conquer strategy0the 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. hgeometry-combinatorial!Divide and conquer strategy. See  . hgeometry-combinatorialDivide and conquer strategy0the 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.hgeometry-combinatorial1Merges two sorted non-Empty lists in linear time.hgeometry-combinatorial'Merges two sorted lists in linear time.hgeometry-combinatorialGiven an ordering and two nonempty sequences ordered according to that ordering, merge them.running time: O(n*T), where n! is the length of the list, and T+ the time required to compare two elements.hgeometry-combinatorialGiven an ordering and two nonempty sequences ordered according to that ordering, merge themrunning time: O(n*T), where n! is the length of the list, and T+ the time required to compare two elements.  (C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone&'(-./25678>?!hgeometry-combinatorial O(n^3) hgeometry-combinatorial1Compute the index of an element in a given range.hgeometry-combinatorial Construct a weighted graph from n5 vertices, a max bound, and a list of weighted edges.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?#~hgeometry-combinatorialRuns a BFS from the first vertex in the graph. The graph is given in adjacency list representation.running time: O(V + E)hgeometry-combinatorialRuns a BFS from the first vertex in the graph. The graph is given in adjacency list representation.running time: O(V + E)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./256789>?)hgeometry-combinatorial:Create a new static data structure storing only one value.hgeometry-combinatorial.Given a NonEmpty list of a's build a static a.hgeometry-combinatorialMerges two structurs of the same size. Has a default implementation via build in case the static structure is Foldable1.hgeometry-combinatorialRepresents an insertion-only data structure built from static data structures.In particular, we maintain  O(\log n)" static data structures of sizes 2^i, for i \in [0..c\log n].hgeometry-combinatorialBuilds an empty structurehgeometry-combinatorial*Inserts an element into the data structurerunning time: O(M(n)\log n / n), where M(n)< is the time required to merge two data structures of size n.hgeometry-combinatorialGiven 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 A \cup B by answering the query on A and B* separately, and combining their results.running time:  O(Q(n)\log n), where Q(n), is the query time on the static structure.  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?+(hgeometry-combinatorial Constructs the failure function.running time: O(m).)hgeometry-combinatorialTest if the first argument, the pattern p, occurs as a consecutive subsequence in t.running time: O(n+m), where p has length m and t has length n.*hgeometry-combinatorialTest if the first argument, the pattern p, occurs as a consecutive subsequence in t.running time: O(n+m), where p has length m and t has length n.()*)*((C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?.+hgeometry-combinatorial A type that can act as an Index.-hgeometry-combinatorial=Types that have an instance of this class can act as indices./hgeometry-combinatorial/A value of type i can obtain something of type 'a'0hgeometry-combinatorial3Run a computation on something that can aquire i's.1hgeometry-combinatorialReplaces 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).2hgeometry-combinatorialLabel each element with its index. Returns the new collection as well as its size.+,-./0120./,-12+ (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?19hgeometry-combinatorial;A State monad that can store earlier versions of the state.:hgeometry-combinatorial;A State monad that can store earlier versions of the state.;hgeometry-combinatorialCreate a snapshot of the current state and add it to the list of states that we store.<hgeometry-combinatorialRun a persistentStateT, returns a triplet with the value, the last state and a list of all states (including the last one) in chronological order=hgeometry-combinatorialRun a persistentStateT, returns a triplet with the value, the last state and a list of all states (including the last one) in chronological order9:;<=:9;<= (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?6Bhgeometry-combinatorialGiven a circular list, whose elements are in increasing order, insert the new element into the Circular list in its sorted order.insertOrd 1 C.empty fromList [1]insertOrd 1 $ C.fromList [2]fromList [2,1]insertOrd 2 $ C.fromList [1,3]fromList [1,2,3]insertOrd 31 ordList fromList [5,6,10,20,30,31,1,2,3]insertOrd 1 ordListfromList [5,6,10,20,30,1,1,2,3]insertOrd 4 ordListfromList [5,6,10,20,30,1,2,3,4]insertOrd 11 ordList fromList [5,6,10,11,20,30,1,2,3]Chgeometry-combinatorialInsert an element into an increasingly ordered circular list, with specified compare operator.Dhgeometry-combinatorialList version of insertOrdBy; i.e. the list contains the elements in cirulcar order. Again produces a list that has the items in circular order.Ehgeometry-combinatorialGiven 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.Fhgeometry-combinatorialTest if the circular list is a cyclic shift of the second list. Running time: O(n), where n is the size of the smallest listBCDEFBCDEF None&'(-./25678>?<Ghgeometry-combinatorialCustom double floating-point type with a relative error margin of rel number of  4https://en.wikipedia.org/wiki/Unit_in_the_last_placeULPs$ and an absolute error margin of abs times  -https://en.wikipedia.org/wiki/Machine_epsilonepsilon.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.Ihgeometry-combinatorialRelatively safe double floating-point type with a relative error margin of 10  4https://en.wikipedia.org/wiki/Unit_in_the_last_placeULPs- and an absolute margin around zero of 10* -https://en.wikipedia.org/wiki/Machine_epsilonepsilon.Warning: All numbers within 10* -https://en.wikipedia.org/wiki/Machine_epsilonepsilon! of zero will be considered zero.m_epsilon * 102.220446049250313e-15.realToFrac (m_epsilon * 10) == (0::SafeDouble)False-realToFrac (m_epsilon * 9) == (0::SafeDouble)True1e-20 == (5e-20 :: Double)False1e-20 == (5e-20 :: SafeDouble)True and  are approximations:sin pi1.2246467991473532e-16sin pi == (0 :: Double)Falsesin pi == (0 :: SafeDouble)TrueGHIIGH None #$&'(-./25678>?DWhgeometry-combinatorial:Double-precision floating point numbers with error-bounds.Some digits can be represented exactly and have essentially an infinitely number of significant digits:significativeDigits 1Infinity8Some fractional numbers can also be represented exactly:significativeDigits 0.5Infinity(Other numbers are merely approximations:significativeDigits 0.116.255619765854984Pi is an irrational number so we can't represent it with infinite precision:significativeDigits pi15.849679651557175sin pi should theoretically be zero but we cannot do better than saying it is near zero:sin pi1.2246467991473532e-16The error margins are greater than value itself so we have no significant digits:significativeDigits (sin pi)0.0Since 'near zero' is not zero, the following fails when using Doubles:sin pi == (0 :: Double)FalseEquality testing for Shaman numbers tests whether the two intervals overlap:sin pi == (0 :: Shaman)TrueXhgeometry-combinatorialDouble-precision floating point numbers that throw exceptions if the accumulated errors grow large enough to cause unstable branching.If  SDouble n works without throwing any exceptions, it'll be safe to use DoubleRelAbs n 0) instead for a sizable performance boost.sin pi == (0 :: SDouble 0)&*** Exception: Insufficient precision.... SDouble 0 failed so DoubleRelAbs 0 0 will lead to an unstable branch. In other words, it'll return False when it should have returned True:!sin pi == (0 :: DoubleRelAbs 0 0)False0Comparing to within 1 ULP stabalizes the branch:sin pi == (0 :: SDouble 1)True!sin pi == (0 :: DoubleRelAbs 1 0)TrueYhgeometry-combinatorial$Number of significant bits (base 2).Zhgeometry-combinatorial'Number of significant digits (base 10).WXYZWYZX (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?I"ohgeometry-combinatorialAn Ord Dictionaryrhgeometry-combinatorialValues of type 'a!' in our dynamically constructed  instanceuhgeometry-combinatorial'Run a computation with a given orderingvhgeometry-combinatorial8Lifts a container f whose values (of type a) depend on 's7' into a more general computation in that produces a 'f a' (depending on s).running time: O(1)whgeometry-combinatorial(Introduce dynamic order in a container 'f'.running time: O(1)xhgeometry-combinatorial,Lifts a function that works on a container 'f' of orderable-things into one that works on dynamically ordered ones.yhgeometry-combinatorial6Lifts a container f whose keys (of type k) depend on 's6' into a more general computation in that produces a `f k v` (depending on s).running time: O(1)zhgeometry-combinatorial(Introduce dynamic order in a container 'f' that has keys of type k.running time: O(1) opqrstuvwxyz rstopquvwxyz(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678:>?K~hgeometry-combinatorialOur Ext type that represents the core datatype core extended with extra information of type .hgeometry-combinatorial%Access the core of an extended value.hgeometry-combinatorial+Access the extra part of an extended value.hgeometry-combinatorial-Lens access to the core of an extended value.hgeometry-combinatorial3Lens access to the extra part of an extended value.hgeometry-combinatorialTag a value with the unit type.~~~11(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?^hgeometry-combinatorialNonempty circular sequencehgeometry-combinatorialO(1) CSeq with exactly one element.hgeometry-combinatorialGets the focus of the CSeq.running time: O(1)hgeometry-combinatorialAccess 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: O(\log (i \mod n))index (fromList [0..5]) 11index (fromList [0..5]) 22index (fromList [0..5]) 55index (fromList [0..5]) 104index (fromList [0..5]) 60index (fromList [0..5]) (-1)5index (fromList [0..5]) (-6)0hgeometry-combinatorial Label the elements with indices.withIndices $ fromList [0..5]0CSeq [0 :+ 0,1 :+ 1,2 :+ 2,3 :+ 3,4 :+ 4,5 :+ 5]hgeometry-combinatorial4Adjusts the i^th element w.r.t the focus in the CSeqrunning time: O(\log (i \mod n))'adjust (const 1000) 2 (fromList [0..5])CSeq [0,1,1000,3,4,5]hgeometry-combinatorial;Access the ith item in the CSeq (w.r.t the focus) as a lenshgeometry-combinatorial5smart constructor that automatically balances the seqhgeometry-combinatorialrotates one to the rightrunning time: O(1) (amortized)rotateR $ fromList [3,4,5,1,2]CSeq [4,5,1,2,3]hgeometry-combinatorialrotates the focus to the leftrunning time: O(1) (amortized)rotateL $ fromList [3,4,5,1,2]CSeq [2,3,4,5,1]8mapM_ 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]hgeometry-combinatorial1Convert to a single Seq, starting with the focus.hgeometry-combinatorial9All elements, starting with the focus, going to the righthgeometry-combinatorial8All elements, starting with the focus, going to the left#leftElements $ fromList [3,4,5,1,2]fromList [3,2,1,5,4]hgeometry-combinatorial builds a CSeqhgeometry-combinatorialO(n) 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!hgeometry-combinatorial Rotates i elements to the right.pre: 0 <= i < nrunning time:  O(\log i) amortizedrotateNR 0 $ fromList [1..5]CSeq [1,2,3,4,5]rotateNR 1 $ fromList [1..5]CSeq [2,3,4,5,1]rotateNR 4 $ fromList [1..5]CSeq [5,1,2,3,4]hgeometry-combinatorialRotates i elements to the left.pre: 0 <= i < nrunning time:  O(\log i) amoritzedrotateNL 0 $ fromList [1..5]CSeq [1,2,3,4,5]rotateNL 1 $ fromList [1..5]CSeq [5,1,2,3,4]rotateNL 2 $ fromList [1..5]CSeq [4,5,1,2,3]rotateNL 3 $ fromList [1..5]CSeq [3,4,5,1,2]rotateNL 4 $ fromList [1..5]CSeq [2,3,4,5,1]hgeometry-combinatorial"Reverses the direction of the CSeqrunning time: O(n)"reverseDirection $ fromList [1..5]CSeq [1,5,4,3,2]hgeometry-combinatorialFinds an element in the CSeq%findRotateTo (== 3) $ fromList [1..5]Just (CSeq [3,4,5,1,2])%findRotateTo (== 7) $ fromList [1..5]Nothinghgeometry-combinatorial)Rotate to a specific element in the CSeq.hgeometry-combinatorial+All rotations, the input CSeq is the focus.,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]hgeometry-combinatorial"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.hgeometry-combinatorial see 'zipLWithhgeometry-combinatorial%same as zipLWith but with three itemshgeometry-combinatorialGiven a circular seq, whose elements are in increasing order, insert the new element into the Circular seq in its sorted order.insertOrd 1 $ fromList [2] CSeq [2,1]insertOrd 2 $ fromList [1,3] CSeq [1,2,3]insertOrd 31 ordListCSeq [5,6,10,20,30,31,1,2,3]insertOrd 1 ordListCSeq [5,6,10,20,30,1,1,2,3]insertOrd 4 ordListCSeq [5,6,10,20,30,1,2,3,4]insertOrd 11 ordListCSeq [5,6,10,11,20,30,1,2,3]running time: O(n)hgeometry-combinatorialInsert an element into an increasingly ordered circular list, with specified compare operator.running time: O(n)hgeometry-combinatorialTest if the circular list is a cyclic shift of the second list. We have that(xs `isShiftOf` ys) == (xs `elem` allRotations (ys :: CSeq Int))Running time: O(n+m), where n and m are the sizes of the lists.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./256789>?b hgeometry-combinatorialWhen using IntersectionOf we may need some constraints that are always true anyway.hgeometry-combinatorial;Class relationship between intersectable geometric objects.hgeometry-combinatorialHelper to implement .hgeometry-combinatorialg  h  =* 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.hgeometry-combinatorialThe type family specifying the list of possible result types of an intersection.hgeometry-combinatorial6The result of interesecting two geometries is a CoRec,hgeometry-combinatorial=A simple data type expressing that there are no intersectionshgeometry-combinatorialHelper to produce a corechgeometry-combinatorial5Returns True iff the result is *not* a NoIntersection  ?Wrapper around Data.Sequence with type level length annotation.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?u$hgeometry-combinatorial$View of the right end of a sequence.hgeometry-combinatorial#View of the left end of a sequence.hgeometry-combinatorial;LSeq n a certifies that the sequence has *at least* n itemshgeometry-combinatorialA bidirectional pattern synonym viewing the rear of a non-empty sequence.hgeometry-combinatorialThe empty sequence.hgeometry-combinatorialA unidirectional pattern synonym viewing the front of a non-empty sequence.hgeometry-combinatorialA bidirectional pattern synonym viewing the front of a non-empty sequence.hgeometry-combinatorial O(1) 7 Convert to a sequence by dropping the type-level size.hgeometry-combinatorial O(1)  The empty sequence.hgeometry-combinatorial O(1)  Add an element to the left end of a sequence. Mnemonic: a triangle with the single element at the pointy end.hgeometry-combinatorial O(1)  Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end.hgeometry-combinatorial O(log(min(n,m)))  Concatenate two sequences.hgeometry-combinatorial O(1)  Prove a sequence has at least n elements.eval @3 (fromList [1,2,3])Just (LSeq (fromList [1,2,3]))eval @3 (fromList [1,2])Nothingeval @3 (fromList [1..10])-Just (LSeq (fromList [1,2,3,4,5,6,7,8,9,10]))hgeometry-combinatorial5Implementatio nof eval' that takes an explicit proxy.hgeometry-combinatorialPromises that the length of this LSeq is actually n. This is not checked.This function should be a noophgeometry-combinatorial'Forces the first n elements of the LSeqhgeometry-combinatorialappends two sequences.hgeometry-combinatorial O(log(min(i,n-i)))  Get the element with index i, counting from the left and starting at 0.hgeometry-combinatorial O(log(min(i,nDi)))  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.hgeometry-combinatorial O(n)  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.hgeometry-combinatorialA generalization of ,  takes a mapping function that also depends on the element's index, and applies it to every element in the sequence.hgeometry-combinatorial O(\log(\min(i,n-i)))  . The first i elements of a sequence. If i is negative,  i s yields the empty sequence. If the sequence contains fewer than i+ elements, the whole sequence is returned.hgeometry-combinatorial O(\log(\min(i,n-i))) ). Elements of a sequence after the first i. If i is negative,  i s yields the whole sequence. If the sequence contains fewer than i+ elements, the empty sequence is returned.hgeometry-combinatorial O(n \log n) . A generalization of ,  takes an arbitrary comparator and sorts the specified sequence. The sort is not stable. This algorithm is frequently faster and uses less memory than 12.hgeometry-combinatorial O(n \log n) .  sorts the specified  by the natural ordering of its elements, but the sort is not stable. This algorithm is frequently faster and uses less memory than 13.hgeometry-combinatorialReverses the sequence.hgeometry-combinatorial O(1) 3. Create an l-sequence from a sequence of elements.hgeometry-combinatorial O(n) 6. Create an l-sequence from a finite list of elements.hgeometry-combinatorial O(n) -. Create an l-sequence from a non-empty list.hgeometry-combinatorial-( O(1) ). Analyse the left end of a sequence.hgeometry-combinatorial O(1) &. Analyse the right end of a sequence.hgeometry-combinatorial"Gets the first element of the LSeq6head $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]1hgeometry-combinatorialGet the LSeq without its first element -- >>> head $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3] LSeq (fromList [2,3])hgeometry-combinatorial Get the last element of the LSeq6last $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]3hgeometry-combinatorial%The sequence without its last element6init $ forceLSeq (Proxy :: Proxy 3) $ fromList [1,2,3]LSeq (fromList [1,2])hgeometry-combinatorialZips two equal length LSeqs&*55555555(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?}hgeometry-combinatorial"A (non-empty) alternating list of a's and b'shgeometry-combinatorial$Computes a b with all its neighbours=withNeighbours (Alternating 0 ['a' :+ 1, 'b' :+ 2, 'c' :+ 3])([(0,'a' :+ 1),(1,'b' :+ 2),(2,'c' :+ 3)]hgeometry-combinatorialGeneric merging scheme that merges two Alternatings and applies the function 'f', 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)):let odds = Alternating "a" [3 :+ "c", 5 :+ "e", 7 :+ "g"]:let evens = Alternating "b" [4 :+ "d", 6 :+ "f", 8 :+ "h"].mergeAlternating (\_ a b -> a <> b) odds evens=[3 :+ "cb",4 :+ "cd",5 :+ "ed",6 :+ "ef",7 :+ "gf",8 :+ "gh"]mergeAlternating (\t a b -> if t `mod` 2 == 0 then a else b) odds evens7[3 :+ "b",4 :+ "c",5 :+ "d",6 :+ "e",7 :+ "f",8 :+ "g"]mergeAlternating (\_ a b -> a <> b) odds (Alternating "b" [0 :+ "d", 5 :+ "e", 8 :+ "h"])3[0 :+ "ad",3 :+ "cd",5 :+ "ee",7 :+ "ge",8 :+ "gh"]hgeometry-combinatorialAdds additional t-values in the alternating, (in sorted order). I.e. if we insert a "breakpoint" at time t the current 'a' value is used at that time.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"]hgeometry-combinatorialReverses an alternating list.8reverse $ Alternating "a" [3 :+ "c", 5 :+ "e", 7 :+ "g"],Alternating "g" [7 :+ "e",5 :+ "c",3 :+ "a"](C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?x hgeometry-combinatorial A Set of a's, implemented using a simple list. The only advantage of this implementation over 457 from containers is that most operations require only 'Eq a' rather than 'Ord a'.hgeometry-combinatorialCreates a singleton set.hgeometry-combinatorialO(n) Inserts an element in the sethgeometry-combinatorial O(n^2)  Insert an element in a set.hgeometry-combinatorial O(n^2) - Create a set from a finite list of elements.hgeometry-combinatorialO(n) Deletes an element from the sethgeometry-combinatorialO(n^2) Computes the union of two setshgeometry-combinatorialO(n^2)& Computes the intersection of two setshgeometry-combinatorialO(n^2)$ Computes the difference of two sets  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorialSimple Zipper for Lists.hgeometry-combinatorialConstruct a Zipper from a listrunning time: O(1)hgeometry-combinatorialGo to the Next Elementrunning time: O(1)hgeometry-combinatorialGo to the previous Elementrunning time: O(1)hgeometry-combinatorialComputes all nexts, even one that has no elements initially or at the end.(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] []hgeometry-combinatorial3Returns the next element, and the zipper without ithgeometry-combinatorial%Drops the next element in the zipper.running time: O(1)hgeometry-combinatorial0Computes all list that still have next elements.0mapM_ 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]  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?r hgeometry-combinatorialGiven an input list, computes all lists in which just one element is missing. 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])leaveOutOne [][]leaveOutOne [1][(1,[])]hgeometry-combinatorial Safe variant of Prelude.minimum.minimum1 [] :: Maybe ()Nothingminimum1 [1,2,3]Just 1hgeometry-combinatorial Safe variant of Prelude.maximum.maximum1 [] :: Maybe ()Nothingmaximum1 [1,2,3]Just 3hgeometry-combinatorial%Total variant of Data.List.minimumBy.*minimum1By (comparing abs) [] :: Maybe IntNothing#minimum1By (comparing abs) [1,-2,3]Just 1hgeometry-combinatorial/Computes all minima by comparing some property.minimaOn (max 2) [1,2,3,4,5,-1][-1,2,1]hgeometry-combinatorialComputes all minima.'minimaBy (comparing abs) [1,2,3,2,1,-1][-1,1,1]hgeometry-combinatorialextracts 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.1extractMinimaBy 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]hgeometry-combinatorialGiven a function f, partitions the list into three lists (lts,eqs,gts) such that:f x == LT for all x in ltsf x == EQ for all x in eqsf x == gt for all x in gts8partition3 (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])hgeometry-combinatorialA version of groupBy that uses the given Ordering to group consecutive Equal items2groupBy' 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 :| []]  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorialThings that can be deleted.hgeometry-combinatorialThings that can be inserted.hgeometry-combinatorialThings that can be measured.6(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?T(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorialThings that have a sizehgeometry-combinatorial?hgeometry-combinatorial=Signature for functions that give the ordering of two values.hgeometry-combinatorialSequence of ordered elements.hgeometry-combinatorialInsert into a monotone OrdSeq.*pre: the comparator maintains monotonicity O(\log n)hgeometry-combinatorialInsert into a sorted OrdSeq O(\log n)hgeometry-combinatorial O(\log n) /. Delete all elements that compare as equal to x.hgeometry-combinatorial O(\log n)hgeometry-combinatorialGiven 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 (< x) . fmap f $ l all (== x) . fmap f $ m all (> x) . fmap f $ r!splitOn id 3 $ fromAscList [1..5]5(fromAscList [1,2],fromAscList [3],fromAscList [4,5])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")])hgeometry-combinatorialGiven a monotonic predicate p, splits the sequence s into two sequences (as,bs) such that all (not p) as and all p bs O(\log n)hgeometry-combinatorial$Deletes all elements from the OrdDeq O(n\log n)hgeometry-combinatorial inserts all eleements in order  O(n\log n)hgeometry-combinatorial inserts all eleements in order  O(n\log n)hgeometry-combinatorial O(n) hgeometry-combinatorial O(\log n)hgeometry-combinatorial O(\log n). Queries for the existance of any elements that compare as equal to x.hgeometry-combinatorial O(n) ( Fmap, assumes the order does not changehgeometry-combinatorialO(1)) Gets the first element from the sequencehgeometry-combinatorialO(1)( Gets the last element from the sequencehgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry-combinatorial'Cyclic representation of a permutation.hgeometry-combinatorialidxes (fromEnum a) = (i,j) implies that a is the j^th item in the i^th orbithgeometry-combinatorial*Orbits (Cycles) are represented by vectorshgeometry-combinatorial!The cycle containing a given itemhgeometry-combinatorial!Next item in a cyclic permutationhgeometry-combinatorial%Previous item in a cyclic permutationhgeometry-combinatorialLookup the indices of an element, i.e. in which orbit the item is, and the index within the orbit.runnign time: O(1)hgeometry-combinatorialApply the permutation, i.e. consider the permutation as a function.hgeometry-combinatorial7Find the cycle in the permutation starting at element shgeometry-combinatorialGiven a vector with items in the permutation, and a permutation (by its functional representation) construct the cyclic representation of the permutation.hgeometry-combinatorialGiven the size n, and a list of Cycles, turns the cycles into a cyclic representation of the Permutation.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorialFaceshgeometry-combinatorial0an edge (u,v) s.t. the face is right from (u,v)hgeometry-combinatorial>A vertex, represented by an id, its adjacencies, and its data.hgeometry-combinatorial>adjacent vertices + data on the edge. Some functions, like  fromAdjRep may assume that the adjacencies are given in counterclockwise order around the vertices. This is not (yet) enforced by the data type.hgeometry-combinatorial8Data type representing the graph in its JSON/Yaml format  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?) hgeometry-combinatorialA 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.hgeometry-combinatorialDarts have a direction which is either Positive or Negative (shown as +1 or -1, respectively).hgeometry-combinatorialAn Arc is a directed edge in a planar graph. The type s is used to tie this arc to a particular graph.hgeometry-combinatorialReverse the direcionhgeometry-combinatorial Arc lens.hgeometry-combinatorialDirection lens.hgeometry-combinatorial Get the twin of this dart (edge)twin (dart 0 "+1")Dart (Arc 0) -1twin (dart 0 "-1")Dart (Arc 0) +1hgeometry-combinatorialtest if a dart is Positivehgeometry-combinatorial4Enumerates all darts such that allDarts !! i = d  = i == fromEnum d(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?4hgeometry-combinatorialGeneral interface to accessing vertex data, dart data, and face data.hgeometry-combinatorial)get the data associated with the value i.running time: O(1) to read the data, O(n) to write it.hgeometry-combinatorialA *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.hgeometry-combinatorial%Shorthand for FaceId's in the primal.hgeometry-combinatorialThe type to represent FaceId'shgeometry-combinatorial%Shorthand for vertices in the primal.hgeometry-combinatorialA 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.hgeometry-combinatorialWe can take the dual of a world. For the Primal this gives us the Dual, for the Dual this gives us the Primal.hgeometry-combinatorial"The world in which the graph liveshgeometry-combinatorial#The Dual of the Dual is the Primal.hgeometry-combinatorial&Getter for a VertexId's unique number.hgeometry-combinatorialGet the embedding, represented as a permutation of the darts, of this graph.hgeometry-combinatorial O(1) access,  O(n)  update.hgeometry-combinatorial O(1) access,  O(n)  update.hgeometry-combinatorial O(1) access,  O(n)  update.hgeometry-combinatorial!Get the dual graph of this graph.hgeometry-combinatoriallens to access the Dart Datahgeometry-combinatorialedgeData is just an alias for hgeometry-combinatorialHelper 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.hgeometry-combinatorial+The function that does the actual work for hgeometry-combinatorial?Reorders the edge data to be in the right order to set edgeDatahgeometry-combinatorialTraverse the vertices(^.vertexData) <$> traverseVertices (\i x -> Just (i,x)) myGraphJust [(VertexId 0,"u"),(VertexId 1,"v"),(VertexId 2,"w"),(VertexId 3,"x")]9traverseVertices (\i x -> print (i,x)) myGraph >> pure ()(VertexId 0,"u")(VertexId 1,"v")(VertexId 2,"w")(VertexId 3,"x")hgeometry-combinatorialTraverses the darts6traverseDarts (\d x -> print (d,x)) myGraph >> pure () (Dart (Arc 0) +1,"a+")(Dart (Arc 0) -1,"a-")(Dart (Arc 1) +1,"b+")(Dart (Arc 1) -1,"b-")(Dart (Arc 2) +1,"c+")(Dart (Arc 2) -1,"c-")(Dart (Arc 3) +1,"d+")(Dart (Arc 3) -1,"d-")(Dart (Arc 4) +1,"e+")(Dart (Arc 4) -1,"e-")(Dart (Arc 5) +1,"g+")(Dart (Arc 5) -1,"g-")hgeometry-combinatorialTraverses the faces6traverseFaces (\i x -> print (i,x)) myGraph >> pure ()(FaceId 0,"f_3")(FaceId 1,"f_infty")(FaceId 2,"f_1")(FaceId 3,"f_2")hgeometry-combinatorialConstruct a planar graphrunning time: O(n).hgeometry-combinatorialConstruct a planar graph, given the darts in cyclic order around each vertex.running time: O(n).hgeometry-combinatorialProduces the adjacencylists for all vertices in the graph. For every vertex, the adjacent vertices are given in counter clockwise order.Note that in case a vertex u as a self loop, we have that this vertexId occurs twice in the list of neighbours, i.e.: u : [...,u,..,u,...]. Similarly, if there are multiple darts between a pair of edges they occur multiple times.running time: O(n)hgeometry-combinatorialGet the number of verticesnumVertices myGraph4hgeometry-combinatorialGet the number of DartsnumDarts myGraph12hgeometry-combinatorialGet the number of EdgesnumEdges myGraph6hgeometry-combinatorialGet the number of facesnumFaces myGraph4hgeometry-combinatorialEnumerate all verticesvertices' myGraph-[VertexId 0,VertexId 1,VertexId 2,VertexId 3]hgeometry-combinatorial7Enumerate all vertices, together with their vertex datahgeometry-combinatorialEnumerate all dartshgeometry-combinatorial&Get all darts together with their datamapM_ 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-")hgeometry-combinatorial6Enumerate all edges. We report only the Positive dartshgeometry-combinatorialEnumerate all edges with their edge data. We report only the Positive darts.mapM_ print $ edges myGraph(Dart (Arc 2) +1,"c+")(Dart (Arc 1) +1,"b+")(Dart (Arc 0) +1,"a+")(Dart (Arc 5) +1,"g+")(Dart (Arc 4) +1,"e+")(Dart (Arc 3) +1,"d+")hgeometry-combinatorial=The tail of a dart, i.e. the vertex this dart is leaving from=showWithData myGraph $ tailOf (Dart (Arc 3) Positive) myGraph(VertexId 2,"w")running time: O(1)hgeometry-combinatorial%The vertex this dart is heading in toshowWithData myGraph $ headOf (Dart (Arc 3) Positive) myGraph (VertexId 1,"v")running time: O(1)hgeometry-combinatorial(endPoints d g = (tailOf d g, headOf d g))endPoints (Dart (Arc 3) Positive) myGraph(VertexId 2,VertexId 1)running time: O(1)hgeometry-combinatorialAll edges incident to vertex v, in counterclockwise order around v."incidentEdges (VertexId 1) myGraph[Dart (Arc 4) -1,Dart (Arc 1) -1,Dart (Arc 3) -1,Dart (Arc 5) +1]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+")mapM_ (print . showWithData myGraph) $ incidentEdges (VertexId 3) myGraph(Dart (Arc 5) -1,"g-")running time: O(k), where k is the output sizehgeometry-combinatorialAll edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v."incomingEdges (VertexId 1) myGraph[Dart (Arc 4) +1,Dart (Arc 1) +1,Dart (Arc 3) +1,Dart (Arc 5) -1]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-")running time: O(k)6, where (k) is the total number of incident edges of vhgeometry-combinatorialAll edges incident to vertex v in outgoing direction (i.e. pointing away from v) in counterclockwise order around v.running time: O(k)6, where (k) is the total number of incident edges of vhgeometry-combinatorialGets the neighbours of a particular vertex, in counterclockwise order around the vertex.mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 1) myGraph -- around v(VertexId 2,"w")(VertexId 0,"u")(VertexId 2,"w")(VertexId 3,"x")mapM_ (print . showWithData myGraph) $ neighboursOf (VertexId 3) myGraph -- around x(VertexId 1,"v")running time: O(k), where k is the output sizehgeometry-combinatorialGiven a dart d that points into some vertex v, report the next dart in the cyclic (counterclockwise) order around v.&nextIncidentEdge (dart 3 "+1") myGraphDart (Arc 5) +1=showWithData myGraph $ nextIncidentEdge (dart 3 "+1") myGraph(Dart (Arc 5) +1,"g+")=showWithData myGraph $ nextIncidentEdge (dart 1 "+1") myGraph(Dart (Arc 3) -1,"d-")running time: O(1)hgeometry-combinatorialGiven a dart d that points into some vertex v, report the previous dart in the cyclic (counterclockwise) order around v.&prevIncidentEdge (dart 3 "+1") myGraphDart (Arc 1) -1=showWithData myGraph $ prevIncidentEdge (dart 3 "+1") myGraph(Dart (Arc 1) -1,"b-")running time: O(1)hgeometry-combinatorialGiven a dart d that points away from some vertex v, report the next dart in the cyclic (counterclockwise) order around v.4nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraphDart (Arc 2) -1showWithData myGraph $ nextIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph(Dart (Arc 2) -1,"c-")showWithData myGraph $ nextIncidentEdgeFrom (dart 1 "+1") myGraph(Dart (Arc 0) +1,"a+")running time: O(1)hgeometry-combinatorialGiven a dart d that points into away from vertex v, report the previous dart in the cyclic (counterclockwise) order around v.4prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraphDart (Arc 4) +1showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 3) Positive) myGraph(Dart (Arc 4) +1,"e+")showWithData myGraph $ prevIncidentEdgeFrom (Dart (Arc 1) Positive) myGraph(Dart (Arc 2) +1,"c+")running time: O(1)hgeometry-combinatorial/Data corresponding to the endpoints of the dart/myGraph^.endPointDataOf (Dart (Arc 3) Positive) ("w","v")hgeometry-combinatorial/Data corresponding to the endpoints of the dartrunning time: O(1)hgeometry-combinatorialThe dual of this graph:{  let fromList = V.fromList/ answer = fromList [ fromList [dart 0 "-1"] , fromList [dart 2 "+1",dart 4 "+1",dart 1 "-1",dart 0 "+1"] , fromList [dart 1 "+1",dart 3 "-1",dart 2 "-1"] , fromList [dart 4 "-1",dart 3 "+1",dart 5 "+1",dart 5 "-1"] ]5 in (computeDual myGraph)^.embedding.orbits == answer:}Truerunning time: O(n).hgeometry-combinatorial"Does the actual work for dualGraph(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry-combinatorial'Enumerate all faces in the planar graphhgeometry-combinatorialAll faces with their face data.hgeometry-combinatorial The face to the left of the dartleftFace (dart 1 "+1") myGraphFaceId 15showWithData myGraph $ leftFace (dart 1 "+1") myGraph(FaceId 1,"f_infty")leftFace (dart 1 "-1") myGraphFaceId 25showWithData myGraph $ leftFace (dart 1 "-1") myGraph(FaceId 2,"f_1")5showWithData myGraph $ leftFace (dart 0 "+1") myGraph(FaceId 0,"f_3")running time: O(1).hgeometry-combinatorial!The face to the right of the dartrightFace (dart 1 "+1") myGraphFaceId 26showWithData myGraph $ rightFace (dart 1 "+1") myGraph(FaceId 2,"f_1")rightFace (dart 1 "-1") myGraphFaceId 16showWithData myGraph $ rightFace (dart 1 "-1") myGraph(FaceId 1,"f_infty")6showWithData myGraph $ rightFace (dart 0 "+1") myGraph(FaceId 1,"f_infty")running time: O(1).hgeometry-combinatorialGet the next edge (in clockwise order) along the face that is to the right of this dart. 7> showWithData myGraph $ nextEdge (dart 1 "+1") myGraph(Dart (Arc 3) -1,"d-") >> showWithData myGraph $ nextEdge (dart 2 "+1") myGraph (Dart (Arc 4) +1,"e+")running time: O(1).hgeometry-combinatorialGet the previous edge (in clockwise order) along the face that is to the right of this dart.5showWithData myGraph $ prevEdge (dart 1 "+1") myGraph(Dart (Arc 2) -1,"c-")5showWithData myGraph $ prevEdge (dart 3 "-1") myGraph(Dart (Arc 1) +1,"b+")running time: O(1).hgeometry-combinatorialGets a dart bounding this face. I.e. a dart d such that the face lies to the right of the dart.*boundaryDart (FaceId $ VertexId 2) myGraphDart (Arc 1) +1showWithData myGraph $ boundaryDart (FaceId $ VertexId 2) myGraph(Dart (Arc 1) +1,"b+")showWithData myGraph $ boundaryDart (FaceId $ VertexId 1) myGraph(Dart (Arc 2) +1,"c+")hgeometry-combinatorialThe 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.&boundary (FaceId $ VertexId 2) myGraph1[Dart (Arc 1) +1,Dart (Arc 3) -1,Dart (Arc 2) -1]mapM_ (print . showWithData myGraph) $ boundary (FaceId $ VertexId 2) myGraph(Dart (Arc 1) +1,"b+")(Dart (Arc 3) -1,"d-")(Dart (Arc 2) -1,"c-")&boundary (FaceId $ VertexId 1) myGraph[Dart (Arc 2) +1,Dart (Arc 4) +1,Dart (Arc 1) -1,Dart (Arc 0) +1]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+")running time: O(k), where k is the output size.hgeometry-combinatorialGiven 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.mapM_ (print . showWithData myGraph) $ boundary' (dart 1 "+1") myGraph(Dart (Arc 1) +1,"b+")(Dart (Arc 3) -1,"d-")(Dart (Arc 2) -1,"c-")O(k), where k is the number of darts reportedhgeometry-combinatorialThe vertices bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 2) myGraph(VertexId 0,"u")(VertexId 1,"v")(VertexId 2,"w")mapM_ (print . showWithData myGraph) $ boundaryVertices (FaceId $ VertexId 1) myGraph(VertexId 0,"u")(VertexId 2,"w")(VertexId 1,"v")(VertexId 0,"u")running time: O(k), where k is the output size.  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorial 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)hgeometry-combinatorialGiven 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: O(n)hgeometry-combinatorialBuilds an edge oracle that can be used to efficiently test if two vertices are connected by an edge.running time: O(n)hgeometry-combinatorial)Test if u and v are connected by an edge.running time: O(1)hgeometry-combinatorialFind the edge data corresponding to edge (u,v) if such an edge existsrunning time: O(1)hgeometry-combinatorialGiven a pair of vertices (u,v) returns the dart, oriented from u to v, corresponding to these vertices.running time: O(1)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?rhgeometry-combinatorialTransforms 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 ' for notes on how we handle self-loops.running time: O(n)hgeometry-combinatorialRead a planar graph, given in JSON format into a planar graph. The adjacencylists should be in counter clockwise order.running time: O(n)hgeometry-combinatorialBuilds the graph from the adjacency lists (but ignores all associated data)hgeometry-combinatorialConstruct 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-edgesrunning time: O(n).7(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorialAdjacency list representation of a graph: for each vertex we simply list all connected neighbours.hgeometry-combinatorialDFS on a planar graph.Running time: O(n)Note that since our planar graphs are always connected there is no need need for dfs to take a list of start vertices.hgeometry-combinatorial+Transform into adjacencylist representationhgeometry-combinatorialDFS, from a given vertex, on a graph in AdjacencyLists representation.Running time: O(n)hgeometry-combinatorialDFS, from a given vertex, on a graph in AdjacencyLists representation. Cycles are not removed. If your graph may contain cycles, see .Running time: O(k), where k! is the number of nodes consumed.hgeometry-combinatorial.Remove infinite cycles from a DFS search tree.!(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry-combinatorialMinimum 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:  O(n \log n)hgeometry-combinatorial6Computes the set of edges in the Minimum spanning treerunning time:  O(n \log n)hgeometry-combinatorialGiven 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.8None&'(-./25678>?hgeometry-combinatorialNumerical face identifier. Negative numbers indicate boundaries, non-negative numbers are internal faces."None&'(-./25678>?e%hgeometry-combinatorial O(n \log n)  Examples:  [[0,1,2]]  9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg  [[0,1,2,3]]  9docs/Data/PlanarGraph/planargraph-2506803680640023584.svghgeometry-combinatorial O(n) hgeometry-combinatorial O(1) hgeometry-combinatorial O(1) hgeometry-combinatorial O(1) hgeometry-combinatorial O(1) hgeometry-combinatorialO(k)hgeometry-combinatorialO(k), more efficient than .hgeometry-combinatorialO(k)hgeometry-combinatorialO(k)hgeometry-combinatorialO(k)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorial,O(1) Next half-edge with the same vertex.hgeometry-combinatorial,O(1) Next half-edge with the same vertex.hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorial5O(1) Tail vertex. IE. the vertex of the twin edge.hgeometry-combinatorialO(1) Synonym of .hgeometry-combinatorial O(1)  Examples:  [[0,1,2]]  9docs/Data/PlanarGraph/planargraph-2959979592048325618.svgrunST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 0 pg)"Face 0"runST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 1 pg) "Boundary 0"hgeometry-combinatorial O(1) 8 Check if a half-edge's face is interior or exterior. Examples:  [[0,1,2]]  9docs/Data/PlanarGraph/planargraph-2959979592048325618.svgrunST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 0 pg)TruerunST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 1 pg)FalserunST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 2 pg)TruerunST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 3 pg)Falsehgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorialO(1)hgeometry-combinatorial)O(k) Counterclockwise vector of edges.hgeometry-combinatorialO(k)hgeometry-combinatorial O(k) where k$ 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. Examples:  [[0,1,2,3]]  9docs/Data/PlanarGraph/planargraph-2506803680640023584.svg  do pg <-  [[0,1,2,3]] let he0 =  0 pg' he4 =  4 pg'  he0 he4  9docs/Data/PlanarGraph/planargraph-1902492848341357096.svg00#(C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone#$&'(-./25678>?8,hgeometry-combinatorialImmutable planar graph.hgeometry-combinatorialFaces are the areas divided by edges. If a face is not surrounded by a set of vertices, it is called a boundary.hgeometry-combinatorialGraph vertices. For best performance, make sure to use consecutive numbers.hgeometry-combinatorialEdges are bidirectional and connect two vertices. No two edges are allowed to cross.hgeometry-combinatorialHalf-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. hgeometry-combinatorial O(n \log n) Construct a planar graph from a list of faces. Vertices are assumed to be dense (ie without gaps) but this only affects performance, not correctness. Memory usage is defined by the largest vertex ID. That means  [[0,1,2]]! has the same connectivity as  [[7,8,9]]% but uses three times less memory. Examples:  [[0,1,2]]  9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg  [[0,1,2,3]]  9docs/Data/PlanarGraph/planargraph-2506803680640023584.svg  [[1,2,3]]  9docs/Data/PlanarGraph/planargraph-2486673127436488352.svg hgeometry-combinatorial O(n \log n) Construct a planar graph from a list of faces. This is a slightly more efficient version of . hgeometry-combinatorial O(k) List all vertices in a graph. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg pgVertices pg[Vertex 0,Vertex 1,Vertex 2] hgeometry-combinatorial O(1) Each vertex has an assigned half-edge with the following properties:  ( vertex pg) pg = vertex  ( ( vertex pg) pg) = True Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svgvertexHalfEdge (Vertex 0) pg HalfEdge 4vertexHalfEdge (Vertex 1) pg HalfEdge 0vertexHalfEdge (Vertex 6) pg... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: 6... vertexHalfEdge (Vertex (-10)) pg... Exception: Data.PlanarGraph.Immutable.vertexHalfEdge: Out-of-bounds vertex access: -10...0halfEdgeVertex (vertexHalfEdge (Vertex 2) pg) pgVertex 2.halfEdgeFace (vertexHalfEdge (Vertex 0) pg) pgFace 0 hgeometry-combinatorial O(1) Returns True# iff the vertex lies on a boundary. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgvertexIsBoundary (Vertex 0) pgTruevertexIsBoundary (Vertex 2) pgFalsevertexIsBoundary (Vertex 4) pgTruevertexIsBoundary (Vertex 12) pg... Exception: Data.PlanarGraph.Immutable.vertexIsBoundary: Out-of-bounds vertex access: 12... hgeometry-combinatorial O(1) Returns True< iff the vertex is interior, ie. does not lie on a boundary. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgvertexIsInterior (Vertex 0) pgFalsevertexIsInterior (Vertex 2) pgTruevertexIsInterior (Vertex 4) pgFalsevertexIsInterior (Vertex 12) pg... Exception: Data.PlanarGraph.Immutable.vertexIsInterior: Out-of-bounds vertex access: 12... hgeometry-combinatorial O(k) Query outgoing half-edges from a given vertex in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg%vertexOutgoingHalfEdges (Vertex 1) pg#[HalfEdge 0,HalfEdge 11,HalfEdge 3]5Each half-edge will point out from the origin vertex:map (`halfEdgeVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg[Vertex 1,Vertex 1,Vertex 1]map (`halfEdgeTipVertex` pg) $ vertexOutgoingHalfEdges (Vertex 1) pg[Vertex 0,Vertex 4,Vertex 2]%vertexOutgoingHalfEdges (Vertex 2) pg[HalfEdge 2,HalfEdge 5]&vertexOutgoingHalfEdges (Vertex 12) pg... Exception: Data.PlanarGraph.Immutable.vertexOutgoingHalfEdges: Out-of-bounds vertex access: 12... hgeometry-combinatorial O(k) Query incoming half-edges from a given vertex in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg%vertexIncomingHalfEdges (Vertex 1) pg#[HalfEdge 1,HalfEdge 10,HalfEdge 2]map (`halfEdgeVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg[Vertex 0,Vertex 4,Vertex 2]map (`halfEdgeTipVertex` pg) $ vertexIncomingHalfEdges (Vertex 1) pg[Vertex 1,Vertex 1,Vertex 1]%vertexIncomingHalfEdges (Vertex 2) pg[HalfEdge 3,HalfEdge 4]&vertexIncomingHalfEdges (Vertex 12) pg... Exception: Data.PlanarGraph.Immutable.vertexIncomingHalfEdges: Out-of-bounds vertex access: 12... hgeometry-combinatorial O(k) 3Query vertex neighbours in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgvertexNeighbours (Vertex 0) pg[Vertex 3,Vertex 1]vertexNeighbours (Vertex 1) pg[Vertex 0,Vertex 4,Vertex 2]vertexNeighbours (Vertex 2) pg[Vertex 1,Vertex 3]vertexNeighbours (Vertex 12) pg... Exception: Data.PlanarGraph.Immutable.vertexNeighbours: Out-of-bounds vertex access: 12... hgeometry-combinatorial O(k) List all edges in a graph. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg pgEdges pg[Edge 0,Edge 1,Edge 2]map edgeHalfEdges $ pgEdges pg[(HalfEdge 0,HalfEdge 1),(HalfEdge 2,HalfEdge 3),(HalfEdge 4,HalfEdge 5)] hgeometry-combinatorial O(1) 4Split a bidirectional edge into directed half-edges. hgeometry-combinatorial O(k) List all half-edges in a graph. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svgpgHalfEdges pg[HalfEdge 0,HalfEdge 1,HalfEdge 2,HalfEdge 3,HalfEdge 4,HalfEdge 5] hgeometry-combinatorial O(1) Query the half-edge in the pointed direction. Internal half-edges are arranged clockwise and external half-edges go counter-clockwise. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg,halfEdgeNext (HalfEdge 4) pg {- clockwise -} HalfEdge 2,halfEdgeNext (HalfEdge 3) pg {- clockwise -} HalfEdge 54halfEdgeNext (HalfEdge 1) pg {- counter-clockwise -} HalfEdge 11halfEdgeNext (HalfEdge 12) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeNext: Out-of-bounds half-edge access: 12... hgeometry-combinatorial O(1) Query the half-edge opposite the pointed direction. This means counter-clockwise for internal half-edges and clockwise for external half-edges. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg4halfEdgePrev (HalfEdge 4) pg {- counter-clockwise -} HalfEdge 64halfEdgePrev (HalfEdge 3) pg {- counter-clockwise -} HalfEdge 10,halfEdgePrev (HalfEdge 1) pg {- clockwise -} HalfEdge 7halfEdgePrev (HalfEdge 12) pg... Exception: Data.PlanarGraph.Immutable.halfEdgePrev: Out-of-bounds half-edge access: 12... hgeometry-combinatorial O(1) ?Next half-edge with the same vertex in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg HalfEdge 0 is poiting out from Vertex 1#. Moving counter-clockwise around Vertex 1 yields  HalfEdge 11 and  HalfEdge 3.$halfEdgeNextOutgoing (HalfEdge 0) pg HalfEdge 11%halfEdgeNextOutgoing (HalfEdge 11) pg HalfEdge 3$halfEdgeNextOutgoing (HalfEdge 3) pg HalfEdge 0%halfEdgeNextOutgoing (HalfEdge 12) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeNextOutgoing: Out-of-bounds half-edge access: 12... hgeometry-combinatorial O(1) ?Next half-edge with the same vertex in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svg HalfEdge 6 is poiting towards Vertex 3. Moving clockwise around Vertex 3 yields  HalfEdge 11 and  HalfEdge 3.$halfEdgeNextIncoming (HalfEdge 6) pg HalfEdge 5$halfEdgeNextIncoming (HalfEdge 5) pg HalfEdge 9$halfEdgeNextIncoming (HalfEdge 9) pg HalfEdge 6%halfEdgeNextIncoming (HalfEdge 12) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeNextIncoming: Out-of-bounds half-edge access: 12... hgeometry-combinatorial O(1)  .  == id  hgeometry-combinatorial O(1) $Tail-end of a half-edge. Synonym of . Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svghalfEdgeVertex (HalfEdge 1) pgVertex 0halfEdgeVertex (HalfEdge 2) pgVertex 2halfEdgeVertex (HalfEdge 6) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeVertex: Out-of-bounds half-edge access: 6... hgeometry-combinatorialO(1)$Tail-end of a half-edge. Synonym of . Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg"halfEdgeTailVertex (HalfEdge 1) pgVertex 0"halfEdgeTailVertex (HalfEdge 2) pgVertex 2 hgeometry-combinatorialO(1)Tip-end of a half-edge. This is the tail-end vertex of the twin half-edge. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg!halfEdgeTipVertex (HalfEdge 1) pgVertex 1!halfEdgeTipVertex (HalfEdge 5) pgVertex 0 hgeometry-combinatorial O(1) Query the face of a half-edge. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svghalfEdgeFace (HalfEdge 0) pgFace 0halfEdgeFace (HalfEdge 1) pg Boundary 0halfEdgeFace (HalfEdge 6) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeFace: Out-of-bounds half-edge access: 6... hgeometry-combinatorial O(1) -Check if a half-edge's face is on a boundary. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg"halfEdgeIsBoundary (HalfEdge 0) pgFalse"halfEdgeIsBoundary (HalfEdge 1) pgTrue"halfEdgeIsBoundary (HalfEdge 2) pgFalse"halfEdgeIsBoundary (HalfEdge 3) pgTrue"halfEdgeIsBoundary (HalfEdge 6) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeIsBoundary: Out-of-bounds half-edge access: 6... hgeometry-combinatorial O(1) (Check if a half-edge's face is interior. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svg"halfEdgeIsInterior (HalfEdge 0) pgTrue"halfEdgeIsInterior (HalfEdge 1) pgFalse"halfEdgeIsInterior (HalfEdge 2) pgTrue"halfEdgeIsInterior (HalfEdge 3) pgFalse"halfEdgeIsInterior (HalfEdge 6) pg... Exception: Data.PlanarGraph.Immutable.halfEdgeIsInterior: Out-of-bounds half-edge access: 6... hgeometry-combinatorial O(k) List all faces in a graph. Examples:let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]] docs/Data/PlanarGraph/planargraph-2635031442529484236.compact.svg pgFaces pg+[Face 0,Face 1,Face 2,Face 3,Face 4,Face 5] hgeometry-combinatorial O(k) List all boundaries (ie external faces) in a graph. There may be multiple boundaries and they may or may not be reachable from each other. Examples:let pg = pgFromFaces [[0,4,1],[0,1,2],[4,3,1],[4,5,3],[3,5,2],[2,5,0]] docs/Data/PlanarGraph/planargraph-2635031442529484236.compact.svgpgBoundaries pg[Boundary 0,Boundary 1]faceBoundary (Boundary 0) pg[Vertex 0,Vertex 4,Vertex 5]faceBoundary (Boundary 1) pg[Vertex 1,Vertex 2,Vertex 3] hgeometry-combinatorial O(1) Returns True4 iff a face or boundary is part of the planar graph. Examples:let pg = pgFromFaces [[0,1,2]] 9docs/Data/PlanarGraph/planargraph-2959979592048325618.svgfaceMember (Face 0) pgTruefaceMember (Face 1) pgFalsefaceMember (Face 100) pgFalsefaceMember (Face (-100)) pgFalsefaceMember (Boundary 0) pgTruefaceMember (Boundary 1) pgFalse hgeometry-combinatorial O(1) Maps interior faces to positive integers and boundary faces to negative integers. Examples:faceId (Face 0)0faceId (Face 10)10faceId (Boundary 0)-1faceId (Boundary 10)-11 hgeometry-combinatorial O(1) 7Query the half-edge associated with a face or boundary. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgfaceHalfEdge (Face 0) pg HalfEdge 0faceHalfEdge (Face 1) pg HalfEdge 8faceHalfEdge (Boundary 0) pg HalfEdge 1,faceHalfEdge (Face 10) pg {- Invalid face -}... Exception: Data.PlanarGraph.Immutable.faceHalfEdge: Out-of-bounds face access: 10... hgeometry-combinatorial O(1) Returns True iff a face is interior. Does not check if the face actually exists. Examples:faceIsInterior (Face 0)TruefaceIsInterior (Face 10000)TruefaceIsInterior (Boundary 0)False hgeometry-combinatorial O(1) Returns True iff a face is a boundary. Does not check if the face actually exists. Examples:faceIsBoundary (Face 0)FalsefaceIsBoundary (Face 10000)FalsefaceIsBoundary (Boundary 0)True hgeometry-combinatorial O(k) >Query the half-edges around a face in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgfaceHalfEdges (Face 0) pg-[HalfEdge 0,HalfEdge 2,HalfEdge 4,HalfEdge 6]faceHalfEdges (Face 1) pg.[HalfEdge 8,HalfEdge 5,HalfEdge 3,HalfEdge 10]faceHalfEdges (Boundary 0) pg.[HalfEdge 1,HalfEdge 11,HalfEdge 9,HalfEdge 7]faceHalfEdges (Face 10) pg... Exception: Data.PlanarGraph.Immutable.faceHalfEdges: Out-of-bounds face access: 10... hgeometry-combinatorial O(k) 8Query the vertices of a face in counter-clockwise order. Examples:*let pg = pgFromFaces [[0,1,2,3],[4,3,2,1]] 9docs/Data/PlanarGraph/planargraph-1711135548958680232.svgfaceBoundary (Face 0) pg%[Vertex 1,Vertex 2,Vertex 3,Vertex 0]faceBoundary (Face 1) pg%[Vertex 3,Vertex 2,Vertex 1,Vertex 4]faceBoundary (Boundary 0) pg%[Vertex 0,Vertex 1,Vertex 4,Vertex 3]faceBoundary (Face 10) pg... Exception: Data.PlanarGraph.Immutable.faceBoundary: Out-of-bounds face access: 10... hgeometry-combinatorial O(n)  hgeometry-combinatorial O(1)  hgeometry-combinatorial O(n)  hgeometry-combinatorial O(1)  hgeometry-combinatorial O(n)  hgeometry-combinatorial O(1)  hgeometry-combinatorial O(n^3) 55$None&'(-./25678>?9%(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678:>?Ehgeometry-combinatorial"Data type for representing ranges.hgeometry-combinatorial2Endpoints of a range may either be open or closed.hgeometry-combinatorialA range from l to u, ignoring/forgetting the type of the endpointshgeometry-combinatorialAccess lens for EndPoint value regardless of whether it is open or closed.Open 5 ^. unEndPoint5Closed 10 ^. unEndPoint10Open 4 & unEndPoint .~ 0Open 0hgeometry-combinatorialTrue iff EndPoint is open.hgeometry-combinatorialTrue iff EndPoint is closed.hgeometry-combinatorial*Lens access for the lower part of a range.hgeometry-combinatorial*Lens access for the upper part of a range.hgeometry-combinatorial9Helper function to show a range in mathematical notation.prettyShow $ OpenRange 0 2"(0,2)"prettyShow $ ClosedRange 0 2"[0,2]"&prettyShow $ Range (Open 0) (Closed 5)"(0,5]"hgeometry-combinatorial Test if a value lies in a range.1 `inRange` (OpenRange 0 2)True1 `inRange` (OpenRange 0 1)False1 `inRange` (ClosedRange 0 1)True1 `inRange` (ClosedRange 1 1)True10 `inRange` (OpenRange 1 10)False10 `inRange` (ClosedRange 0 1)FalseThis one is kind of weird%0 `inRange` Range (Closed 0) (Open 0)Falsehgeometry-combinatorialGet the width of the intervalwidth $ ClosedRange 1 109width $ OpenRange 5 105hgeometry-combinatorial?Compute the halfway point between the start and end of a range.hgeometry-combinatorialClamps 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.clampTo (ClosedRange 0 10) 2010 clampTo (ClosedRange 0 10) (-20)0clampTo (ClosedRange 0 10) 55clampTo (OpenRange 0 10) 2010clampTo (OpenRange 0 10) (-20)0clampTo (OpenRange 0 10) 55hgeometry-combinatorialClip the interval from below. I.e. intersect with the interval {l,infty), where { is either open, (, orr closed, [.hgeometry-combinatorialClip the interval from above. I.e. intersect with (-infty, u}, where } is either open, ), or closed, ],hgeometry-combinatorial>Wether or not the first range completely covers the second onehgeometry-combinatorialCheck 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.hgeometry-combinatorial!Shift a range x units to the left-prettyShow $ shiftLeft 10 (ClosedRange 10 20)"[0,10]"+prettyShow $ shiftLeft 10 (OpenRange 15 25)"(5,15)"hgeometry-combinatorialShifts the range to the right.prettyShow $ shiftRight 10 (ClosedRange 10 20) "[20,30]",prettyShow $ shiftRight 10 (OpenRange 15 25) "(25,35)"(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./235678>?Jhgeometry-combinatorial$Fixed-precision representation of a . If there's insufficient precision to accurately represent the  then the  constructor will be used.hgeometry-combinatorialReal 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.hgeometry-combinatorialCast  to a fixed-precision number. Data is silently lost if there's insufficient precision.hgeometry-combinatorial#Cast a fixed-precision number to a .hgeometry-combinatorialCast  to a fixed-precision number. Data-loss caused by insufficient precision will be marked by the  constructor.  &(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Lhgeometry-combinatorialPartition the seq s given a monotone predicate p into (xs,ys) such thatall 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: O(\log^2 n + T*\log n), where T' is the time to execute the predicate.'(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Vkhgeometry-combinatorialGiven 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 (< x) . fmap f $ l * all (== x) . fmap f $ m * all (> x) . fmap f $ rrunning time:  O(\log n)hgeometry-combinatorial)Given a monotonic function f that orders a, split the sequence s into three parts. I.e. the result (lt,eq,gt) is such that * all (x -> f x == LT) . fmap f $ lt * all (x -> f x == EQ) . fmap f $ eq * all (x -> f x == GT) . fmap f $ gtrunning time:  O(\log n)hgeometry-combinatorial'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:  O(n\log n)hgeometry-combinatorialGiven two sets l and r, such that all elements of l occur before r, join the two sets into a combined set.running time:  O(\log n)hgeometry-combinatorialInserts an element into the set, assuming that the set is ordered by the given order.insertBy cmpS (S "ccc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"](fromList [S "a",S "bb",S "ccc",S "dddd"]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:insertBy cmpS (S "cc") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"] fromList [S "a",S "cc",S "dddd"]running time:  O(\log n)hgeometry-combinatorialDeletes an element from the set, assuming the set is ordered by the given ordering.deleteAllBy cmpS (S "bb") $ fromListBy cmpS [S "a" , S "bb" , S "dddd"]fromList [S "a",S "dddd"]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"]running time:  O(\log n)hgeometry-combinatorial>Run a query, eg. lookupGE, on the set with the given ordering. Note: The 9* function may be a useful alternative to queryBy cmpS Set.lookupGE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]Just (S "bbb")queryBy cmpS Set.lookupLE (S "22") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"] Just (S "a")queryBy cmpS Set.lookupGE (S "333") $ fromListBy cmpS [S "a" , S "bbb" , S "ddddddd"]Just (S "bbb")  (None&'(-./25678>?fhgeometry-combinatorialZipper for rose treeshgeometry-combinatorialNodes in a tree are typically either an internal node or a leaf nodehgeometry-combinatorial"A TreeNode is isomorphic to Eitherhgeometry-combinatorial+Create a new zipper focussiong on the root.hgeometry-combinatorial*Move the focus to the parent of this node.hgeometry-combinatorial/Move the focus to the first child of this node.firstChild $ root myTreeJust (Zipper {focus = Node {rootLabel = 1, subForest = []}, ancestors = [([],0,[Node {rootLabel = 2, subForest = []},Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})hgeometry-combinatorial/Move the focus to the next sibling of this node*(firstChild $ root myTree) >>= nextSiblingJust (Zipper {focus = Node {rootLabel = 2, subForest = []}, ancestors = [([Node {rootLabel = 1, subForest = []}],0,[Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})hgeometry-combinatorial/Move the focus to the next sibling of this nodehgeometry-combinatorialGiven a zipper that focussses on some subtree t, construct a list with zippers that focus on each child.hgeometry-combinatorialGiven 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.hgeometry-combinatorialCreates 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.hgeometry-combinatorial?Constructs a tree from the list of ancestors (if there are any)hgeometry-combinatorialGiven a predicate on an element, find a node that matches the predicate, and turn that node into the root of the tree.running time: O(nT) where n is the size of the tree, and T& is the time to evaluate a predicate.findEvert (== 4) myTreeJust (Node {rootLabel = 4, subForest = [Node {rootLabel = 3, subForest = [Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []},Node {rootLabel = 2, subForest = []}]}]}]})findEvert (== 5) myTreeNothinghgeometry-combinatorialGiven 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: O(nT(n)) where n is the size of the tree, and T(m); is the time to evaluate a predicate on a subtree of size m.hgeometry-combinatorialFunction 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:  O(n(T_p+T_s), where n is the size of the tree, and T_p and T_s( are the times it takes to evaluate the isStartingNode and  isEndingNode predicates.findPath (== 1) (==4) myTreeJust [1,0,3,4]findPath (== 1) (==2) myTree Just [1,0,2]findPath (== 1) (==1) myTreeJust [1]findPath (== 1) (==2) myTree Just [1,0,2]findPath (== 4) (==2) myTreeJust [4,3,0,2]hgeometry-combinatorialGiven a predicate on a, find (the path to) a node that satisfies the predicate.findNode (== 4) myTree Just [0,3,4]hgeometry-combinatorial2Find all paths to nodes that satisfy the predicaterunning time: O(nT(n)) where n is the size of the tree, and T(m); is the time to evaluate a predicate on a subtree of size m.$findNodes ((< 4) . rootLabel) myTree[[0],[0,1],[0,2],[0,3]]#findNodes (even . rootLabel) myTree[[0],[0,2],[0,3,4]]4let size = length in findNodes ((> 1) . size) myTree [[0],[0,3]]hgeometry-combinatorial>BFS Traversal of the rose tree that decomposes it into levels.running time: O(n)hgeometry-combinatorialis this node a starting nodehgeometry-combinatorialis this node an ending node)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?l2hgeometry-combinatorialBinary tree in which we store the values of type a in internal nodes.hgeometry-combinatorialBinary tree that stores its values (of type a) in the leaves. Internal nodes store something of type v.hgeometry-combinatorialsmart constructorhgeometry-combinatorial.Create a balanced tree, i.e. a tree of height  O(\log n)" with the elements in the leaves.O(n) time.hgeometry-combinatorialGiven 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.hgeometry-combinatorial?Traverses the tree bottom up, recomputing the assocated values.hgeometry-combinatorialTakes two trees, that have the same structure, and uses the provided functions to "zip" them togetherhgeometry-combinatorial O(n) ) Convert binary tree to a rose tree, aka .hgeometry-combinatorial&2-dimensional ASCII drawing of a tree.hgeometry-combinatorial0Get the element stored at the root, if it existshgeometry-combinatorialCreate a balanced binary tree.running time: O(n)hgeometry-combinatorial-Fold function for folding over a binary tree.hgeometry-combinatorial Convert a  BinaryTree into a RoseTreehgeometry-combinatorialDraw a binary tree.*(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?u hgeometry-combinatorial?`UnBounded a` represents the type a, together with an element / larger than any other element, and an element ", smaller than any other element.hgeometry-combinatorial `Bottom a`( represents the type a, together with a  element, i.e. an element that is smaller than any other element. We can think of  `Bottom a` being defined as:data Bottom a = Bottom | ValB ahgeometry-combinatorialTop a( represents the type a, together with a  element, i.e. an element that is greater than any other element. We can think of `Top a` being defined as:data Top a = ValT a | Tophgeometry-combinatorialTop a values are isomorphing to Maybe a values.hgeometry-combinatorial prism. Can be used to access the non-bottom element if it exists:ValT True & _ValT %~ not ValT FalseTop & _ValT %~ notTophgeometry-combinatorial prism.hgeometry-combinatorialIso between a Top a and a Maybe a, interpreting a  as a  and vice versa. Note that this reverses the ordering of the elements.ValT 5 ^. _TopMaybeJust 5Just 5 ^.re _TopMaybeValT 5Top ^. _TopMaybeNothingNothing ^.re _TopMaybeTophgeometry-combinatorial6`Bottom a` values are isomorphing to `Maybe a` values.hgeometry-combinatorial prism. Can be used to access the non-bottom element if it exists:ValB True & _ValB %~ not ValB FalseBottom & _ValB %~ notBottomhgeometry-combinatorial prism.hgeometry-combinatorialIso between a 'Bottom a' and a 'Maybe a', interpreting a Bottom as a Nothing and vice versa.ValB 5 ^. _BottomMaybeJust 5Just 5 ^.re _BottomMaybeValB 5Bottom ^. _BottomMaybeNothingNothing ^.re _BottomMaybeBottomhgeometry-combinatorial-Prism to access unbounded value if it exists.Val True ^? _Val Just True!MinInfinity ^? _Val :: Maybe BoolNothingVal True & _Val %~ not Val FalseMaxInfinity & _Val %~ not MaxInfinityhgeometry-combinatorial)Test if an Unbounded is actually bounded.unBoundedToMaybe (Val 5)Just 5unBoundedToMaybe MinInfinityNothingunBoundedToMaybe MaxInfinityNothing+(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?y hgeometry-combinatorial0Strict pair whose elements are of the same type.$Strict pair with both items the samehgeometry-combinatorial Strict pairhgeometry-combinatorial%Strict Triple with all items the samehgeometry-combinatorial strict triplehgeometry-combinatorial!Pattern synonym for strict pairs.hgeometry-combinatorial#Pattern synonym for strict triples.hgeometry-combinatorial'Generate All unique unordered triplets.hgeometry-combinatorial7Given a list xs, generate all unique (unordered) pairs.hgeometry-combinatorial8A version of List.tails in which we remove the emptylist  ,(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?hgeometry-combinatorial6Monad in which we can use the IndexedDoublyLinkedList.hgeometry-combinatorialDoubly 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.6Supports O(1) indexing, and O(1) insertions, deletionshgeometry-combinatorialCells in the Linked Listhgeometry-combinatorial#Cell indices. Must be non-negative.hgeometry-combinatorial&Empty cell with no next or prev cells.hgeometry-combinatorial;Runs a DLList Computation, starting with n singleton valueshgeometry-combinatorial4Constructs a new DoublyLinkedList, of size at most nhgeometry-combinatorial,Sets the DoublyLinkedList to the given List.6Indices that do not occur in the list are not touched.hgeometry-combinatorialNext element in the Listhgeometry-combinatorialPrevious Element in the Listhgeometry-combinatorial?hgeometry-combinatorial6Monad in which we can use the IndexedDoublyLinkedList.hgeometry-combinatorialDoubly 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.6Supports O(1) indexing, and O(1) insertions, deletionshgeometry-combinatorialCells in the Linked Listhgeometry-combinatorial#Cell indices. Must be non-negative.hgeometry-combinatorial&Empty cell with no next or prev cells.hgeometry-combinatorialRuns a DLList Computation, starting with singleton values, crated from the input vector.hgeometry-combinatorialConstructs a new DoublyLinkedList. Every element is its own singleton listhgeometry-combinatorial,Sets the DoublyLinkedList to the given List.6Indices that do not occur in the list are not touched.hgeometry-combinatorialGets the value at Index ihgeometry-combinatorialNext element in the Listhgeometry-combinatorialPrevious Element in the Listhgeometry-combinatorial?lhgeometry-combinatorialAccess the ith item in the CircularVector (w.r.t the rotation) as a lenshgeometry-combinatorial9All elements, starting with the focus, going to the right*rightElements $ unsafeFromList [3,4,5,1,2] [3,4,5,1,2]hgeometry-combinatorial8All elements, starting with the focus, going to the left)leftElements $ unsafeFromList [3,4,5,1,2] [3,2,1,5,4]hgeometry-combinatorial&Finds an element in the CircularVector+findRotateTo (== 3) $ unsafeFromList [1..5]:Just (CircularVector {vector = [1,2,3,4,5], rotation = 2})+findRotateTo (== 7) $ unsafeFromList [1..5]Nothinghgeometry-combinatorialTest if the circular list is a cyclic shift of the second list.Running time: O(n+m), where n and m are the sizes of the lists.hgeometry-combinatoriallabel the circular vector with indices, starting from zero at the current focus, going right.Running time: O(n)/&Helper functions for working with yaml(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?hgeometry-combinatorial(Data type for things that have a versionhgeometry-combinatorialWrite the output to yamlhgeometry-combinatorialPrints the yamlhgeometry-combinatorial-alias for decodeEither' from the Yaml Packagehgeometry-combinatorialalias for reading a yaml filehgeometry-combinatorialEncode a yaml filehgeometry-combinatorialUnpack versioned data type.hgeometry-combinatorial7Given a list of candidate parsers, select the right one  0(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Ahgeometry-combinatorialFisher@Yates shuffle, which shuffles a list/foldable uniformly at random.running time: O(n).:;<=>?9@ABCDEFGHIJKLMNOPQRSTUVVWXYZ[\]^_`abcdefghijklmnopqr s t u v w x y z { | } ~                                                         S|}W5SX??X      !!!88888""""""""""""""""""""""""""""""""""""""""""""""""""""#####################################################################$$$$$$$$$$$$$$$$%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%&'''''''''''(((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))*************************************************+++++++++++++++++++++++++++++++++,,,,,,,,,>,,,,,,,,,,,,,,,,,,,,,,---------->------------------------........//////////////////0:88888888888888888888883hgeometry-combinatorial-0.13-FqkqJCsl9I37c4Aln2AxaYData.RealNumber.RationalAlgorithms.BinarySearchAlgorithms.DivideAndConquerAlgorithms.FloydWarshallAlgorithms.Graph.BFSAlgorithms.LogarithmicMethodAlgorithms.StringSearch.KMPControl.CanAquireControl.Monad.State.PersistentData.CircularList.UtilData.Double.ApproximateData.Double.ShamanData.DynamicOrdData.ExtData.CircularSeqData.Intersection Data.LSeqData.List.Alternating Data.List.SetData.List.ZipperData.List.UtilData.Measured.ClassData.Measured.Size Data.OrdSeqData.PermutationData.PlanarGraph.AdjRepData.PlanarGraph.DartData.PlanarGraph.CoreData.PlanarGraph.DualData.PlanarGraph.EdgeOracleData.PlanarGraph.IOAlgorithms.Graph.DFSAlgorithms.Graph.MSTData.PlanarGraph.MutableData.PlanarGraph.ImmutableData.PlanarGraph.Persistent Data.RangeData.Sequence.Util Data.Set.UtilData.Tree.UtilData.BinaryTreeData.UnBounded Data.Util!Data.IndexedDoublyLinkedList.BareData.IndexedDoublyLinkedListData.Vector.Circular.UtilData.Yaml.UtilSystem.Random.Shuffle Data.SequencesortBysortDataSet Data.MeasuredData.PlanarGraphData.PlanarGraph.InternalbinarySearchInghc-prim GHC.TypesNat BinarySearchIndexElembinarySearchIdxIn binarySearchbinarySearchUntil$fBinarySearchSet$fBinarySearchv$fBinarySearchSeqdivideAndConquer1divideAndConquerdivideAndConquer1With mergeSortedmergeSortedLists mergeSortedBymergeSortedListsBy floydWarshallmkIndexmkGraphbfsbfs'LogarithmicMethodDS singletonbuildmerge InsertionOnlyemptyinsert queryWith$fFoldableInsertionOnly$fTraversableInsertionOnly$fFunctorInsertionOnly$fMonoidInsertionOnly$fSemigroupInsertionOnly$fShowInsertionOnly$fEqInsertionOnly$fOrdInsertionOnlybuildFailureFunction isSubStringOfkmpMatchIHasIndexindexOf CanAquireaquire runAcquirereplaceByIndexlabelWithIndex $fCanAquireIa$fHasIndexIInt$fShowI$fEqI$fOrdI$fEnumIPersistentStatePersistentStateTstorerunPersistentStateTrunPersistentState$fMonadStatesPersistentStateT$fFunctorPersistentStateT$fApplicativePersistentStateT$fMonadPersistentStateT insertOrd insertOrdBy insertOrdBy' splitIncr isShiftOf DoubleRelAbs SafeDouble$fReadDoubleRelAbs$fShowDoubleRelAbs$fOrdDoubleRelAbs$fEqDoubleRelAbs$fNumDoubleRelAbs$fEnumDoubleRelAbs$fFloatingDoubleRelAbs$fFractionalDoubleRelAbs$fRealDoubleRelAbs$fRealFloatDoubleRelAbs$fRealFracDoubleRelAbs$fRandomDoubleRelAbs$fNFDataDoubleRelAbsShamanSDoublesignificativeBitssignificativeDigits $fOrdShaman $fEqShaman$fRealFloatShaman$fRealFracShaman $fRealShaman$fFloatingShaman$fFractionalShaman $fNumShaman $fReadShaman $fShowShaman $fOrdSDouble $fEqSDouble $fReadSDouble $fShowSDouble $fNumSDouble$fFractionalSDouble$fFloatingSDouble $fRealSDouble$fRealFracSDouble$fRealFloatSDoubleOrdDictcompare_OrunOwithOrd extractOrd1 introOrd1liftOrd1 extractOrd2 introOrd2$fOrdO$fEqO$fShowO:+_core_extracoreextraext $fArbitrary:+ $fFromJSON:+ $fToJSON:+ $fSemigroup:+$fBitraversable1:+$fBifoldable1:+$fBitraversable:+$fBifoldable:+$fBiapplicative:+ $fBiapply:+ $fBifunctor:+$fShow:+$fRead:+$fEq:+$fOrd:+ $fBounded:+ $fGeneric:+ $fNFData:+CSeqfocusindex withIndicesadjustitemcseqrotateRrotateLasSeq rightElements leftElements fromNonEmptyfromListrotateNRrotateNLreverseDirection findRotateTorotateTo allRotationszipLWithzipL zip3LWith$fArbitraryCSeq $fFunctorCSeq$fFoldableCSeq$fFoldable1CSeq$fTraversableCSeq $fReadCSeq $fShowCSeq$fEqCSeq $fNFDataCSeq $fGenericCSeqAlwaysTrueIntersectionIsIntersectableWith intersectnonEmptyIntersectionHasIntersectionWith intersectsIntersectionOf IntersectionNoIntersectioncoRecdefaultNonEmptyIntersection$fShowNoIntersection$fReadNoIntersection$fEqNoIntersection$fOrdNoIntersectionViewR:>ViewL:<LSeq:|>EmptyL:<<:<|toSeq<||>><evaleval'promise forceLSeqappend partition mapWithIndextakedropunstableSortBy unstableSortreversefromSeqviewlviewrheadtaillastinitzipWith$fTraversable1LSeq$fFoldable1LSeq $fIxedLSeq$fFromJSONLSeq $fToJSONLSeq$fArbitraryLSeq $fMonoidLSeq$fSemigroupLSeq $fOrdViewL $fEqViewL$fTraversable1ViewL$fFoldable1ViewL$fTraversableViewL$fFoldableViewL$fFunctorViewL$fSemigroupViewL $fOrdViewR $fEqViewR$fTraversableViewR$fFoldableViewR$fFunctorViewR$fSemigroupViewR $fShowLSeq $fReadLSeq$fEqLSeq $fOrdLSeq$fFoldableLSeq $fFunctorLSeq$fTraversableLSeq $fGenericLSeq $fNFDataLSeq $fShowViewR $fShowViewL AlternatingwithNeighboursmergeAlternatinginsertBreakPoints$fBitraversableAlternating$fBifoldableAlternating$fBifunctorAlternating$fShowAlternating$fEqAlternating$fOrdAlternating insertAlldeleteunion intersection difference $fMonoidSet$fSemigroupSet$fEqSet $fShowSet $fReadSet $fFunctorSet $fFoldableSet$fTraversableSetZippergoNextgoPrevallNexts extractNextdropNextallNonEmptyNexts$fFoldableZipper $fShowZipper $fEqZipper$fFunctorZipper leaveOutOneminimum1maximum1 minimum1ByminimaOnminimaByextractMinimaBy partition3groupBy' CanDeletedeleteA CanInsertinsertAMeasuredmeasureSized_unElemSize $fMonoidSize$fSemigroupSize$fMeasuredSizeElem $fMonoidSized$fSemigroupSized $fNFDataSized $fShowSized $fEqSized $fOrdSized$fFunctorSized$fFoldableSized$fTraversableSized$fGenericSized $fShowElem $fReadElem$fEqElem $fOrdElem $fFunctorElem$fFoldableElem$fTraversableElem $fShowSize $fReadSize$fEqSize $fNumSize$fIntegralSize $fEnumSize $fRealSize $fOrdSize $fGenericSize $fNFDataSizeCompareOrdSeqinsertBy deleteAllBysplitBysplitOnsplitMonotonic deleteAll fromListBy fromListByOrd fromAscListlookupBymemberBy mapMonotonicminView lookupMinmaxView lookupMax $fMonoidKey$fSemigroupKey$fMeasuredKeyElem$fArbitraryOrdSeq$fFoldableOrdSeq$fMonoidOrdSeq$fSemigroupOrdSeq $fShowOrdSeq $fEqOrdSeq $fShowKey$fEqKey$fOrdKey Permutation_orbits_indexesOrbit$fShowPermutation$fEqPermutation$fGenericPermutationindexesorbitselemssizecycleOfnextprevious lookupIdxapply orbitFromcycleRep toCycleRep genIndexes$fTraversablePermutation$fFoldablePermutation$fFunctorPermutation$fNFDataPermutationFace incidentEdgefDataVtxidadjvDataGr adjacenciesfaces $fFromJSONGr $fToJSONGr $fBifunctorGr $fFromJSONVtx $fToJSONVtx$fBifunctorVtx$fFromJSONFace $fToJSONFace $fGenericFace $fFunctorFace $fShowFace$fEqFace $fGenericVtx $fShowVtx$fEqVtx $fGenericGr$fShowGr$fEqGrDart_arc _direction DirectionNegativePositiveArc_unArcrevarc directiontwin isPositiveallDarts$fArbitraryArc $fShowArc$fArbitraryDirection$fReadDirection$fShowDirection$fNFDataDirection $fEnumDart$fArbitraryDart $fShowDart $fNFDataDart$fEqDart $fOrdDart $fGenericDart $fEqDirection$fOrdDirection$fBoundedDirection$fEnumDirection$fGenericDirection$fEqArc$fOrdArc $fEnumArc $fBoundedArc $fGenericArc $fNFDataArc HasDataOfDataOfdataOf PlanarGraph _embedding _vertexData _rawDartData _faceData_dualFaceId'FaceId _unFaceId VertexId'VertexId _unVertexIdDualOfWorldPrimalDualdualDualIdentity unVertexId embedding vertexData rawDartDatafaceDatadualdartDataedgeData updateData updateData'reorderEdgeDatatraverseVertices traverseDarts traverseFaces planarGraph' planarGraphtoAdjacencyLists numVerticesnumDartsnumEdgesnumFaces vertices'verticesdarts'dartsedges'edgestailOfheadOf endPoints incidentEdges incomingEdges outgoingEdges neighboursOfnextIncidentEdgeprevIncidentEdgenextIncidentEdgeFromprevIncidentEdgeFromendPointDataOf endPointData computeDual computeDual'$fShowVertexId $fShowFaceId$fEqPlanarGraph$fShowPlanarGraph$fHasDataOfPlanarGraphFaceId$fHasDataOfPlanarGraphDart$fHasDataOfPlanarGraphVertexId$fGenericPlanarGraph $fEqFaceId $fOrdFaceId $fEnumFaceId$fToJSONFaceId$fFromJSONFaceId $fEqVertexId $fOrdVertexId$fEnumVertexId$fToJSONVertexId$fFromJSONVertexId$fGenericVertexId$fNFDataVertexId $fShowWorld $fEqWorldfaces'leftFace rightFacenextEdgeprevEdge boundaryDartboundary boundary'boundaryVertices EdgeOracle _unEdgeOracle edgeOraclebuildEdgeOraclehasEdgefindEdgefindDart$fTraversableEdgeOracle$fFoldableEdgeOracle$fFunctorEdgeOracle$fShowEdgeOracle$fEqEdgeOracletoAdjRep fromAdjRep buildGraphreorderfromAdjacencyLists assignArcs$fFromJSONPlanarGraph$fToJSONPlanarGraphAdjacencyListsdfsadjacencyListsdfs' dfsSensitivedfsFilterCyclesmstmstEdgesmakeTree HalfEdgeIdEdgeIdVertexEdgeHalfEdge pgFromFaces pgFromFacesCVpgClonepgHash vertexFromId vertexToIdvertexHalfEdgevertexIsBoundaryvertexOutgoingHalfEdgesvertexWithOutgoingHalfEdgesvertexIncomingHalfEdgesvertexWithIncomingHalfEdgesvertexNeighbours edgeFromIdedgeToIdedgeFromHalfEdgehalfEdgeFromId halfEdgeToId halfEdgeNext halfEdgePrevhalfEdgeNextOutgoinghalfEdgeNextIncominghalfEdgeVertex halfEdgeTwinhalfEdgeTailVertexhalfEdgeTipVertex halfEdgeFacehalfEdgeIsInterior faceInvalid faceIsValid faceIsInvalid faceFromIdfaceToId faceHalfEdgefaceIsInteriorfaceIsBoundary faceHalfEdges faceBoundarypgConnectVertices$fHashableHalfEdge$fShowHalfEdge$fHashableVertex $fShowVertex $fEqVertex$fEqEdge $fEqHalfEdgeBoundaryvertexIdedgeId halfEdgeId pgVerticesvertexIsInteriorpgEdges edgeHalfEdges pgHalfEdgeshalfEdgeIsBoundarypgFaces pgBoundaries faceMemberfaceIdpgMutatepgCreatepgThaw pgUnsafeThawpgFreezepgUnsafeFreezetutteEmbedding$fReadHalfEdge $fReadEdge $fShowEdge $fReadVertex$fHashablePlanarGraph $fReadFace$fHashableEdgepgNextHalfEdgeIdpgNextVertexId pgNextFaceIdpgNextpgVertexpgFacepgHalfEdgeFromVertexpgHalfEdgeFromFacenew halfEdgeNextMRange_lower_upperEndPointOpenClosedRange' ClosedRange OpenRange unEndPointisOpenisClosedlowerupper prettyShowinRangewidthmidPointclampTo clipLower clipUppercovers isValidRange shiftLeft shiftRight$fArbitraryEndPoint $fOrdEndPoint$fRead1EndPoint$fReadEndPoint$fShow1EndPoint$fShowEndPoint$fIsIntersectableWithRangeRange$fHasIntersectionWithRangeRange$fArbitraryRange $fRead1Range $fReadRange $fShow1Range $fShowRange $fEqRange$fFunctorRange$fFoldableRange$fTraversableRange$fGenericRange $fNFDataRange $fEqEndPoint$fFunctorEndPoint$fFoldableEndPoint$fTraversableEndPoint$fGenericEndPoint$fNFDataEndPointAsFixedExactLossy RealNumbertoFixed fromFixedasFixed$fRandomRealNumber$fArbitraryRealNumber$fReadRealNumber$fHasResolutionTYPENatPrec$fShowRealNumber $fShowAsFixed $fEqAsFixed$fEqRealNumber$fOrdRealNumber$fDataRealNumber$fNumRealNumber$fFractionalRealNumber$fRealRealNumber$fRealFracRealNumber$fGenericRealNumber$fHashableRealNumber$fToJSONRealNumber$fFromJSONRealNumber$fNFDataRealNumber splitMonotoneScmpSjoinqueryBy$fShowS ancestorsTreeNode InternalNodeLeafNode_TreeNodeEitherrootup firstChild nextSibling prevSibling allChildrenallTrees unZipperLocal constructTree findEvert findEvert'findPathfindNode findNodeslevels$fBitraversableTreeNode$fBifoldableTreeNode$fBifunctorTreeNode$fShowTreeNode $fEqTreeNode BinaryTreeNilInternal BinLeafTreeLeafNodenodeasBalancedBinLeafTreefoldUp foldUpData zipExactWith toRoseTreedrawTreeaccessasBalancedBinTree foldBinaryUp toRoseTree' drawTree'$fArbitraryBinLeafTree$fSemigroupBinLeafTree$fTraversableBinLeafTree$fFoldable1BinLeafTree$fFoldableBinLeafTree$fMeasuredvBinLeafTree$fBifunctorBinLeafTree$fNFDataBinLeafTree$fArbitraryBinaryTree$fNFDataBinaryTree$fShowBinaryTree$fReadBinaryTree$fEqBinaryTree$fOrdBinaryTree$fFunctorBinaryTree$fFoldableBinaryTree$fTraversableBinaryTree$fGenericBinaryTree$fShowBinLeafTree$fReadBinLeafTree$fEqBinLeafTree$fOrdBinLeafTree$fFunctorBinLeafTree$fGenericBinLeafTree UnBounded MinInfinityVal MaxInfinity _unUnBoundedBottomTopValBValT topToMaybe_ValT_Top _TopMaybe bottomToMaybe_ValB_Bottom _BottomMaybe_ValunBoundedToMaybe $fShowTop$fOrdTop $fOrd1Top $fShowBottom$fFractionalUnBounded$fNumUnBounded$fShowUnBounded $fEqUnBounded$fOrdUnBounded$fFunctorUnBounded$fFoldableUnBounded$fTraversableUnBounded $fEqBottom $fOrdBottom$fFunctorBottom$fFoldableBottom$fTraversableBottom$fApplicativeBottom $fMonadBottom $fEq1Bottom $fOrd1Bottom$fEqTop $fFunctorTop $fFoldableTop$fTraversableTop$fApplicativeTop $fMonadTop$fEq1TopTwoSPThreeSTRuniqueTriplets uniquePairs nonEmptyTails$fField3STRSTRcd$fField2STRSTRbd$fField1STRSTRad $fNFDataSTR $fMonoidSTR$fSemigroupSTR $fBifunctorSP$fField2SPSPbc$fField1SPSPac $fNFDataSP $fMonoidSP $fSemigroupSP$fShowSP$fEqSP$fOrdSP $fFunctorSP $fGenericSP $fShowSTR$fEqSTR$fOrdSTR $fFunctorSTR $fGenericSTR IDLListMonadIDLListllistCellprev emptyCellrunIDLListMonad singletons writeListgetNextgetPrev toListFrom toListFromK toListFromR toListFromRKtoListContains insertAfter insertBeforedump $fMonadReaderIDLListIDLListMonad$fPrimMonadIDLListMonad$fFunctorIDLListMonad$fApplicativeIDLListMonad$fMonadIDLListMonad $fShowCell$fEqCell DLListMonadDLListvaluesrunDLListMonadvalueAt$fFunctorDLList$fMonadReaderDLListDLListMonad$fPrimMonadDLListMonad$fFunctorDLListMonad$fApplicativeDLListMonad$fMonadDLListMonadwithIndicesRight$fArbitraryCircularVector$fFoldable1NonEmptyVector Versioned encodeYaml printYaml decodeYamldecodeYamlFileencodeYamlFile unversionedparseVersioned$fToJSONVersioned $fFromJSONV$fShowVersioned$fReadVersioned$fGenericVersioned $fEqVersioned$fFunctorVersioned$fFoldableVersioned$fTraversableVersionedshufflebase GHC.Floatpisin GHC.ClassesOrdGHC.BasefmappgBoundaryEdges pgFaceEdges pgVertexEdgespgHalfEdgeFacepgHalfEdgeVertexpgHalfEdgePrevpgHalfEdgeNextpgNextBoundaryId GrowVector newVector setVector readVector writeVector freezeVectorunsafeFreezeVector thawVectorunsafeThawVectorfreezeCircularVectorcontainers-0.6.2.1 Data.TreeTree GHC.MaybeNothing