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

-- | Generic finger-tree structure, with example instances
--   
--   A general sequence representation with arbitrary annotations, for use
--   as a base for implementations of various collection types, with
--   examples, as described in section 4 of
--   
--   
--   
- Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", Journal of Functional
--   Programming 16:2 (2006) pp 197-217.
--   http://staff.city.ac.uk/~ross/papers/FingerTree.html
--   
--   
--   For a tuned sequence type, see Data.Sequence in the
--   containers package, which is a specialization of this
--   structure.
@package fingertree
@version 0.1.5.0

-- | A general sequence representation with arbitrary annotations, for use
--   as a base for implementations of various collection types, as
--   described in section 4 of
--   
--   
--   
- Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", Journal of Functional
--   Programming 16:2 (2006) pp 197-217.
--   http://staff.city.ac.uk/~ross/papers/FingerTree.html
--   
--   
--   For a directly usable sequence type, see Data.Sequence, which
--   is a specialization of this structure.
--   
--   An amortized running time is given for each operation, with n
--   referring to the length of the sequence. These bounds hold even in a
--   persistent (shared) setting.
--   
--   Note: Many of these operations have the same names as similar
--   operations on lists in the Prelude. The ambiguity may be
--   resolved using either qualification or the hiding clause.
module Data.FingerTree

-- | A representation of a sequence of values of type a, allowing
--   access to the ends in constant time, and append and split in time
--   logarithmic in the size of the smaller piece.
--   
--   The collection is also parameterized by a measure type v,
--   which is used to specify a position in the sequence for the
--   split operation. The types of the operations enforce the
--   constraint Measured v a, which also implies that the
--   type v is determined by a.
--   
--   A variety of abstract data types can be implemented by using different
--   element types and measurements.
data FingerTree v a

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

-- | O(1). The empty sequence.
empty :: Measured v a => FingerTree v a

-- | O(1). A singleton sequence.
singleton :: Measured v a => a -> FingerTree v a

-- | O(1). Add an element to the left end of a sequence. Mnemonic: a
--   triangle with the single element at the pointy end.
(<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a
infixr 5 <|

-- | O(1). Add an element to the right end of a sequence. Mnemonic:
--   a triangle with the single element at the pointy end.
(|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a
infixl 5 |>

-- | O(log(min(n1,n2))). Concatenate two sequences.
(><) :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a
infixr 5 ><

-- | O(n). Create a sequence from a finite list of elements. The
--   opposite operation toList is supplied by the Foldable
--   instance.
fromList :: Measured v a => [a] -> FingerTree v a

-- | O(1). Is this the empty sequence?
null :: FingerTree v a -> Bool

-- | View of the left end of a sequence.
data ViewL s a

-- | empty sequence
EmptyL :: ViewL s a

-- | leftmost element and the rest of the sequence
(:<) :: a -> s a -> ViewL s a
infixr 5 :<

-- | O(1). Analyse the left end of a sequence.
viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a

-- | View of the right end of a sequence.
data ViewR s a

-- | empty sequence
EmptyR :: ViewR s a

-- | the sequence minus the rightmost element, and the rightmost element
(:>) :: s a -> a -> ViewR s a
infixl 5 :>

-- | O(1). Analyse the right end of a sequence.
viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a

-- | A result of search, attempting to find a point where a
--   predicate on splits of the sequence changes from False to
--   True.
data SearchResult v a

-- | A tree opened at a particular element: the prefix to the left, the
--   element, and the suffix to the right.
Position :: !FingerTree v a -> a -> !FingerTree v a -> SearchResult v a

-- | A position to the left of the sequence, indicating that the predicate
--   is True at both ends.
OnLeft :: SearchResult v a

-- | A position to the right of the sequence, indicating that the predicate
--   is False at both ends.
OnRight :: SearchResult v a

-- | No position in the tree, returned if the predicate is True at
--   the left end and False at the right end. This will not occur if
--   the predicate in monotonic on the tree.
Nowhere :: SearchResult v a

-- | O(log(min(i,n-i))). Search a sequence for a point where a
--   predicate on splits of the sequence changes from False to
--   True.
--   
--   The argument p is a relation between the measures of the two
--   sequences that could be appended together to form the sequence
--   t. If the relation is False at the leftmost split and
--   True at the rightmost split, i.e.
--   
--   
--   not (p mempty (measure t)) && p (measure t) mempty
--   
--   
--   then there must exist an element x in the sequence such that
--   p is False for the split immediately before x
--   and True for the split just after it:
--   
--   
--   In this situation, search p t returns such an element
--   x and the pieces l and r of the sequence to
--   its left and right respectively. That is, it returns
--   Position l x r such that
--   
--   
--   
- 
l >< (x <| r) = t

--   
- 
not (p (measure l) (measure (x <| r))

--   
- 
p (measure (l |> x)) (measure r)

--   
--   
--   For predictable results, one should ensure that there is only one such
--   point, i.e. that the predicate is monotonic on t.
search :: Measured v a => (v -> v -> Bool) -> FingerTree v a -> SearchResult v a

-- | O(log(min(i,n-i))). Split a sequence at a point where the
--   predicate on the accumulated measure of the prefix changes from
--   False to True.
--   
--   For predictable results, one should ensure that there is only one such
--   point, i.e. that the predicate is monotonic.
split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)

-- | O(log(min(i,n-i))). Given a monotonic predicate p,
--   takeUntil p t is the largest prefix of t
--   whose measure does not satisfy p.
--   
--   
--   
- 
takeUntil p t = fst (split p
--   t)

--   
takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a

-- | O(log(min(i,n-i))). Given a monotonic predicate p,
--   dropUntil p t is the rest of t after removing
--   the largest prefix whose measure does not satisfy p.
--   
--   
--   
- 
dropUntil p t = snd (split p
--   t)

--   
dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a

-- | O(n). The reverse of a sequence.
reverse :: Measured v a => FingerTree v a -> FingerTree v a

-- | Like fmap, but with constraints on the element types.
fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2

-- | Map all elements of the tree with a function that also takes the
--   measure of the prefix of the tree to the left of the element.
fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2

-- | Map all elements of the tree with a function that also takes the
--   measure of the prefix to the left and of the suffix to the right of
--   the element.
fmapWithContext :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> v1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2

-- | Like fmap, but safe only if the function preserves the measure.
unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b

-- | Fold the tree from the left with a function that also takes the
--   measure of the prefix to the left of the element.
foldlWithPos :: Measured v a => (b -> v -> a -> b) -> b -> FingerTree v a -> b

-- | Fold the tree from the right with a function that also takes the
--   measure of the prefix to the left of the element.
foldrWithPos :: Measured v a => (v -> a -> b -> b) -> b -> FingerTree v a -> b

-- | Fold the tree from the left with a function that also takes the
--   measure of the prefix to the left of the element and the measure of
--   the suffix to the right of the element.
foldlWithContext :: Measured v a => (b -> v -> a -> v -> b) -> b -> FingerTree v a -> b

-- | Fold the tree from the right with a function that also takes the
--   measure of the prefix to the left of the element and the measure of
--   the suffix to the right of the element.
foldrWithContext :: Measured v a => (v -> a -> v -> b -> b) -> b -> FingerTree v a -> b

-- | Like traverse, but with constraints on the element types.
traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)

-- | Traverse the tree from left to right with a function that also takes
--   the measure of the prefix of the tree to the left of the element.
traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)

-- | Traverse the tree from left to right with a function that also takes
--   the measure of the prefix to the left and the measure of the suffix to
--   the right of the element.
traverseWithContext :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> v1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)

-- | Like traverse, but safe only if the function preserves the
--   measure.
unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b)
instance GHC.Generics.Generic (Data.FingerTree.ViewL s a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (Data.FingerTree.ViewL s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (Data.FingerTree.ViewL s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (Data.FingerTree.ViewL s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (Data.FingerTree.ViewL s a)
instance GHC.Generics.Generic (Data.FingerTree.ViewR s a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (Data.FingerTree.ViewR s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (Data.FingerTree.ViewR s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (Data.FingerTree.ViewR s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (Data.FingerTree.ViewR s a)
instance GHC.Generics.Generic (Data.FingerTree.Digit a)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.Digit a)
instance GHC.Generics.Generic (Data.FingerTree.Node v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.FingerTree.Node v a)
instance GHC.Generics.Generic (Data.FingerTree.FingerTree v a)
instance GHC.Generics.Generic (Data.FingerTree.SearchResult v a)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.SearchResult v a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.FingerTree.SearchResult v a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.FingerTree.SearchResult v a)
instance Data.FingerTree.Measured v a => GHC.Base.Semigroup (Data.FingerTree.FingerTree v a)
instance Data.FingerTree.Measured v a => GHC.Base.Monoid (Data.FingerTree.FingerTree v a)
instance Data.FingerTree.Measured v a => Data.FingerTree.Measured v (Data.FingerTree.FingerTree v a)
instance Data.Foldable.Foldable (Data.FingerTree.FingerTree v)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.FingerTree.FingerTree v a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.FingerTree.FingerTree v a)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.FingerTree v a)
instance Data.Foldable.Foldable (Data.FingerTree.Node v)
instance GHC.Base.Monoid v => Data.FingerTree.Measured v (Data.FingerTree.Node v a)
instance Data.FingerTree.Measured v a => Data.FingerTree.Measured v (Data.FingerTree.Digit a)
instance Data.Foldable.Foldable Data.FingerTree.Digit
instance GHC.Base.Functor s => GHC.Base.Functor (Data.FingerTree.ViewR s)
instance GHC.Base.Functor s => GHC.Base.Functor (Data.FingerTree.ViewL s)

-- | Interval maps implemented using the FingerTree type, following
--   section 4.8 of
--   
--   
--   
- Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", Journal of Functional
--   Programming 16:2 (2006) pp 197-217.
--   http://staff.city.ac.uk/~ross/papers/FingerTree.html
--   
--   
--   An amortized running time is given for each operation, with n
--   referring to the size of the priority queue. These bounds hold even in
--   a persistent (shared) setting.
--   
--   Note: Many of these operations have the same names as similar
--   operations on lists in the Prelude. The ambiguity may be
--   resolved using either qualification or the hiding clause.
module Data.IntervalMap.FingerTree

-- | A closed interval. The lower bound should be less than or equal to the
--   upper bound.
data Interval v

-- | Lower and upper bounds of the interval.
Interval :: v -> v -> Interval v

-- | Lower bound of the interval
low :: Interval v -> v

-- | Upper bound of the interval
high :: Interval v -> v

-- | An interval in which the lower and upper bounds are equal.
point :: v -> Interval v

-- | Map of closed intervals, possibly with duplicates.
data IntervalMap v a

-- | O(1). The empty interval map.
empty :: Ord v => IntervalMap v a

-- | O(1). Interval map with a single entry.
singleton :: Ord v => Interval v -> a -> IntervalMap v a

-- | O(log n). Insert an interval and associated value into a map.
--   The map may contain duplicate intervals; the new entry will be
--   inserted before any existing entries for the same interval.
insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a

-- | O(m log (n/m)). Merge two interval maps. The map may
--   contain duplicate intervals; entries with equal intervals are kept in
--   the original order.
union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a

-- | O(k log (n/k)). All intervals that contain the given
--   point, in lexicographical order.
search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]

-- | O(k log (n/k)). All intervals that intersect with the
--   given interval, in lexicographical order.
intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]

-- | O(k log (n/k)). All intervals that contain the given
--   interval, in lexicographical order.
dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]

-- | O(1). bounds m returns Nothing
--   if m is empty, and otherwise Just i, where
--   i is the smallest interval containing all the intervals in
--   the map.
bounds :: Ord v => IntervalMap v a -> Maybe (Interval v)

-- | O(1). leastView m returns
--   Nothing if m is empty, and otherwise
--   Just ((i, x), m'), where i is the least
--   interval, x is the associated value, and m' is the
--   rest of the map.
leastView :: Ord v => IntervalMap v a -> Maybe ((Interval v, a), IntervalMap v a)

-- | O(log(min(i,n-i))). splitAfter k m returns a
--   pair of submaps, one consisting of intervals whose lower bound is less
--   than or equal to k, and the other of those whose lower bound
--   is greater.
splitAfter :: Ord v => v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a)
instance GHC.Generics.Generic (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Read.Read v => GHC.Read.Read (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Show.Show v => GHC.Show.Show (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Classes.Ord v => GHC.Classes.Ord (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Generics.Generic (Data.IntervalMap.FingerTree.Node v a)
instance (GHC.Read.Read v, GHC.Read.Read a) => GHC.Read.Read (Data.IntervalMap.FingerTree.Node v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.IntervalMap.FingerTree.Node v a)
instance (GHC.Classes.Ord v, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.IntervalMap.FingerTree.Node v a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.IntervalMap.FingerTree.Node v a)
instance GHC.Generics.Generic (Data.IntervalMap.FingerTree.IntInterval v)
instance GHC.Generics.Generic (Data.IntervalMap.FingerTree.IntervalMap v a)
instance GHC.Base.Functor (Data.IntervalMap.FingerTree.IntervalMap v)
instance Data.Foldable.Foldable (Data.IntervalMap.FingerTree.IntervalMap v)
instance Data.Traversable.Traversable (Data.IntervalMap.FingerTree.IntervalMap v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.IntervalMap.FingerTree.IntervalMap v a)
instance (GHC.Classes.Ord v, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.IntervalMap.FingerTree.IntervalMap v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.IntervalMap.FingerTree.IntervalMap v a)
instance GHC.Classes.Ord v => GHC.Base.Semigroup (Data.IntervalMap.FingerTree.IntervalMap v a)
instance GHC.Classes.Ord v => GHC.Base.Monoid (Data.IntervalMap.FingerTree.IntervalMap v a)
instance GHC.Classes.Ord v => GHC.Base.Semigroup (Data.IntervalMap.FingerTree.IntInterval v)
instance GHC.Classes.Ord v => GHC.Base.Monoid (Data.IntervalMap.FingerTree.IntInterval v)
instance GHC.Classes.Ord v => Data.FingerTree.Measured (Data.IntervalMap.FingerTree.IntInterval v) (Data.IntervalMap.FingerTree.Node v a)
instance GHC.Base.Functor (Data.IntervalMap.FingerTree.Node v)
instance Data.Foldable.Foldable (Data.IntervalMap.FingerTree.Node v)
instance Data.Traversable.Traversable (Data.IntervalMap.FingerTree.Node v)

-- | Min-priority queues implemented using the FingerTree type,
--   following section 4.6 of
--   
--   
--   
- Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", Journal of Functional
--   Programming 16:2 (2006) pp 197-217.
--   http://staff.city.ac.uk/~ross/papers/FingerTree.html
--   
--   
--   These have the same big-O complexity as skew heap implementations, but
--   are approximately an order of magnitude slower. On the other hand,
--   they are stable, so they can be used for fair queueing. They are also
--   shallower, so that fmap consumes less space.
--   
--   An amortized running time is given for each operation, with n
--   referring to the size of the priority queue. These bounds hold even in
--   a persistent (shared) setting.
--   
--   Note: Many of these operations have the same names as similar
--   operations on lists in the Prelude. The ambiguity may be
--   resolved using either qualification or the hiding clause.
module Data.PriorityQueue.FingerTree

-- | Priority queues.
data PQueue k v

-- | O(1). The empty priority queue.
empty :: Ord k => PQueue k v

-- | O(1). A singleton priority queue.
singleton :: Ord k => k -> v -> PQueue k v

-- | O(log(min(n1,n2))). Concatenate two priority queues.
--   union is associative, with identity empty.
--   
--   If there are entries with the same priority in both arguments,
--   minView of union xs ys will return those from
--   xs before those from ys.
union :: Ord k => PQueue k v -> PQueue k v -> PQueue k v

-- | O(1). Add a (priority, value) pair to the front of a priority
--   queue.
--   
--   
--   
- 
insert k v q = union (singleton k v)
--   q

--   
--   
--   If q contains entries with the same priority k,
--   minView of insert k v q will return them after
--   this one.
insert :: Ord k => k -> v -> PQueue k v -> PQueue k v

-- | O(log n). Add a (priority, value) pair to the back of a
--   priority queue.
--   
--   
--   
- 
add k v q = union q (singleton k
--   v)

--   
--   
--   If q contains entries with the same priority k,
--   minView of add k v q will return them before
--   this one.
add :: Ord k => k -> v -> PQueue k v -> PQueue k v

-- | O(n). Create a priority queue from a finite list of priorities
--   and values.
fromList :: Ord k => [(k, v)] -> PQueue k v

-- | O(1). Is this the empty priority queue?
null :: Ord k => PQueue k v -> Bool

-- | O(1) for the element, O(log(n)) for the reduced queue.
--   Returns Nothing for an empty map, or the value associated with
--   the minimal priority together with the rest of the priority queue.
--   
--   
--   
- 
minView empty = Nothing

--   
- 
minView (singleton k v) = Just (v,
--   empty)

--   
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)

-- | O(1) for the element, O(log(n)) for the reduced queue.
--   Returns Nothing for an empty map, or the minimal (priority,
--   value) pair together with the rest of the priority queue.
--   
--   
--   
- 
minViewWithKey empty =
--   Nothing

--   
- 
minViewWithKey (singleton k v) = Just
--   ((k, v), empty)

--   
- If minViewWithKey qi = Just ((ki, vi), qi')
--   and k1 <= k2, then minViewWithKey (union
--   q1 q2) = Just ((k1, v1), union q1' q2)
--   
- If minViewWithKey qi = Just ((ki, vi), qi')
--   and k2 < k1, then minViewWithKey (union
--   q1 q2) = Just ((k2, v2), union q1 q2')
--   
minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)
instance GHC.Generics.Generic (Data.PriorityQueue.FingerTree.Entry k v)
instance GHC.Generics.Generic (Data.PriorityQueue.FingerTree.Prio k v)
instance GHC.Generics.Generic (Data.PriorityQueue.FingerTree.PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Functor (Data.PriorityQueue.FingerTree.PQueue k)
instance GHC.Classes.Ord k => Data.Foldable.Foldable (Data.PriorityQueue.FingerTree.PQueue k)
instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.PriorityQueue.FingerTree.PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PriorityQueue.FingerTree.PQueue k v)
instance (GHC.Classes.Ord k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.PriorityQueue.FingerTree.PQueue k v)
instance (GHC.Classes.Ord k, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.PriorityQueue.FingerTree.PQueue k v)
instance (GHC.Classes.Ord k, GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Data.PriorityQueue.FingerTree.PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.PriorityQueue.FingerTree.Prio k v)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PriorityQueue.FingerTree.Prio k v)
instance GHC.Classes.Ord k => Data.FingerTree.Measured (Data.PriorityQueue.FingerTree.Prio k v) (Data.PriorityQueue.FingerTree.Entry k v)
instance GHC.Base.Functor (Data.PriorityQueue.FingerTree.Entry k)
instance Data.Foldable.Foldable (Data.PriorityQueue.FingerTree.Entry k)
