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


-- | Generic strict finger-tree structure
--   
--   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
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programming</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   For a tuned sequence type, see <tt>Data.Sequence</tt> in the
--   <tt>containers</tt> package, which is a specialization of this
--   structure.
@package hw-fingertree-strict
@version 0.1.1.1


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

-- | A representation of a sequence of values of type <tt>a</tt>, 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 <tt>v</tt>,
--   which is used to specify a position in the sequence for the
--   <a>split</a> operation. The types of the operations enforce the
--   constraint <tt><a>Measured</a> v a</tt>, which also implies that the
--   type <tt>v</tt> is determined by <tt>a</tt>.
--   
--   A variety of abstract data types can be implemented by using different
--   element types and measurements.
data FingerTree v a
Empty :: FingerTree v a
Single :: !a -> FingerTree v a
Deep :: !v -> !Digit a -> !FingerTree v (Node v a) -> !Digit a -> FingerTree v a
data Digit a
One :: !a -> Digit a
Two :: !a -> !a -> Digit a
Three :: !a -> !a -> !a -> Digit a
Four :: !a -> !a -> !a -> !a -> Digit a
data Node v a
Node2 :: !v -> !a -> !a -> Node v a
Node3 :: !v -> !a -> !a -> !a -> Node v a
deep :: Measured v a => Digit a -> FingerTree v (Node v a) -> Digit a -> FingerTree v a
node2 :: Measured v a => a -> a -> Node v a
node3 :: Measured v a => a -> a -> a -> Node v a

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

-- | <i>O(1)</i>. The empty sequence.
empty :: FingerTree v a

-- | <i>O(1)</i>. A singleton sequence.
singleton :: a -> FingerTree v a

-- | <i>O(1)</i>. 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 <|

-- | <i>O(1)</i>. 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 |>

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

-- | <i>O(n)</i>. Create a sequence from a finite list of elements.
fromList :: Measured v a => [a] -> FingerTree v a

-- | <i>O(1)</i>. 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 :<

-- | 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 :>

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

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

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

-- | <i>O(log(min(i,n-i)))</i>. Given a monotonic predicate <tt>p</tt>,
--   <tt><a>takeUntil</a> p t</tt> is the largest prefix of <tt>t</tt>
--   whose measure does not satisfy <tt>p</tt>.
--   
--   <ul>
--   <li><pre><a>takeUntil</a> p t = <a>fst</a> (<a>split</a> p
--   t)</pre></li>
--   </ul>
takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a

-- | <i>O(log(min(i,n-i)))</i>. Given a monotonic predicate <tt>p</tt>,
--   <tt><a>dropUntil</a> p t</tt> is the rest of <tt>t</tt> after removing
--   the largest prefix whose measure does not satisfy <tt>p</tt>.
--   
--   <ul>
--   <li><pre><a>dropUntil</a> p t = <a>snd</a> (<a>split</a> p
--   t)</pre></li>
--   </ul>
dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a

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

-- | Like <a>fmap</a>, but with a more constrained type.
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

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

-- | Like <a>traverse</a>, but with a more constrained type.
traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)

-- | Traverse the tree 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)

-- | Like <a>traverse</a>, but safe only if the function preserves the
--   measure.
unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b)
maybeHead :: Measured v a => FingerTree v a -> Maybe a
maybeLast :: Measured v a => FingerTree v a -> Maybe a
instance (Control.DeepSeq.NFData t, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.Split t a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.Split t a)
instance (GHC.Show.Show t, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.Split t a)
instance (GHC.Classes.Eq t, GHC.Classes.Eq a) => GHC.Classes.Eq (HaskellWorks.Data.FingerTree.Strict.Split t a)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance (GHC.Show.Show a, GHC.Show.Show v) => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.Node v a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.Node v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.Node v a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.Digit a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.Digit a)
instance GHC.Show.Show a => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.Digit a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (HaskellWorks.Data.FingerTree.Strict.Digit a)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData (s a)) => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (HaskellWorks.Data.FingerTree.Strict.ViewR s a)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData (s a)) => Control.DeepSeq.NFData (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance GHC.Generics.Generic (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (HaskellWorks.Data.FingerTree.Strict.ViewL s a)
instance HaskellWorks.Data.FingerTree.Strict.Measured v a => GHC.Base.Semigroup (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance HaskellWorks.Data.FingerTree.Strict.Measured v a => GHC.Base.Monoid (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance HaskellWorks.Data.FingerTree.Strict.Measured v a => HaskellWorks.Data.FingerTree.Strict.Measured v (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance Data.Foldable.Foldable (HaskellWorks.Data.FingerTree.Strict.FingerTree v)
instance GHC.Classes.Eq a => GHC.Classes.Eq (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (HaskellWorks.Data.FingerTree.Strict.FingerTree v a)
instance Data.Foldable.Foldable (HaskellWorks.Data.FingerTree.Strict.Node v)
instance GHC.Base.Monoid v => HaskellWorks.Data.FingerTree.Strict.Measured v (HaskellWorks.Data.FingerTree.Strict.Node v a)
instance HaskellWorks.Data.FingerTree.Strict.Measured v a => HaskellWorks.Data.FingerTree.Strict.Measured v (HaskellWorks.Data.FingerTree.Strict.Digit a)
instance Data.Foldable.Foldable HaskellWorks.Data.FingerTree.Strict.Digit
instance GHC.Base.Functor s => GHC.Base.Functor (HaskellWorks.Data.FingerTree.Strict.ViewR s)
instance GHC.Base.Functor s => GHC.Base.Functor (HaskellWorks.Data.FingerTree.Strict.ViewL s)


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

-- | A closed interval. The lower bound should be less than or equal to the
--   higher bound.
data Interval v
Interval :: !v -> !v -> Interval v
[low] :: Interval v -> !v
[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. The <a>Foldable</a>
--   and <a>Traversable</a> instances process the intervals in
--   lexicographical order.
newtype IntervalMap v a
IntervalMap :: FingerTree (IntInterval v) (Node v a) -> IntervalMap v a

-- | <i>O(1)</i>. The empty interval map.
empty :: IntervalMap v a

-- | <i>O(1)</i>. Interval map with a single entry.
singleton :: Interval v -> a -> IntervalMap v a

-- | <i>O(log n)</i>. Insert an interval 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

-- | <i>O(m log (n</i>/<i>m))</i>. 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

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

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

-- | <i>O(k log (n</i>/<i>k))</i>. All intervals that contain the given
--   interval, in lexicographical order.
dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance GHC.Generics.Generic (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance Control.DeepSeq.NFData v => Control.DeepSeq.NFData (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance GHC.Generics.Generic (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance GHC.Show.Show v => GHC.Show.Show (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.IntervalMap.Strict.Node v a)
instance GHC.Generics.Generic (HaskellWorks.Data.IntervalMap.Strict.Node v a)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.IntervalMap.Strict.Node v a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (HaskellWorks.Data.IntervalMap.Strict.Node v a)
instance Control.DeepSeq.NFData v => Control.DeepSeq.NFData (HaskellWorks.Data.IntervalMap.Strict.Interval v)
instance GHC.Generics.Generic (HaskellWorks.Data.IntervalMap.Strict.Interval v)
instance GHC.Show.Show v => GHC.Show.Show (HaskellWorks.Data.IntervalMap.Strict.Interval v)
instance GHC.Classes.Ord v => GHC.Classes.Ord (HaskellWorks.Data.IntervalMap.Strict.Interval v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (HaskellWorks.Data.IntervalMap.Strict.Interval v)
instance GHC.Base.Functor (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v)
instance Data.Foldable.Foldable (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v)
instance Data.Traversable.Traversable (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v)
instance GHC.Classes.Ord v => GHC.Base.Semigroup (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance GHC.Classes.Ord v => GHC.Base.Monoid (HaskellWorks.Data.IntervalMap.Strict.IntervalMap v a)
instance GHC.Classes.Ord v => GHC.Base.Semigroup (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance GHC.Classes.Ord v => GHC.Base.Monoid (HaskellWorks.Data.IntervalMap.Strict.IntInterval v)
instance GHC.Classes.Ord v => HaskellWorks.Data.FingerTree.Strict.Measured (HaskellWorks.Data.IntervalMap.Strict.IntInterval v) (HaskellWorks.Data.IntervalMap.Strict.Node v a)
instance GHC.Base.Functor (HaskellWorks.Data.IntervalMap.Strict.Node v)
instance Data.Foldable.Foldable (HaskellWorks.Data.IntervalMap.Strict.Node v)
instance Data.Traversable.Traversable (HaskellWorks.Data.IntervalMap.Strict.Node v)

module HaskellWorks.Data.Item.Strict
data Item k a
Item :: !k -> !a -> Item k a
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.Item.Strict.Item k a)
instance GHC.Generics.Generic (HaskellWorks.Data.Item.Strict.Item k a)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.Item.Strict.Item k a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (HaskellWorks.Data.Item.Strict.Item k a)
instance GHC.Base.Functor (HaskellWorks.Data.Item.Strict.Item k)
instance Data.Foldable.Foldable (HaskellWorks.Data.Item.Strict.Item k)
instance Data.Traversable.Traversable (HaskellWorks.Data.Item.Strict.Item k)
instance GHC.Base.Monoid k => HaskellWorks.Data.FingerTree.Strict.Measured k (HaskellWorks.Data.Item.Strict.Item k a)


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

-- | Priority queues.
data PQueue k v

-- | <i>O(1)</i>. The empty priority queue.
empty :: PQueue k v

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

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

-- | <i>O(log n)</i>. Add a (priority, value) pair to the front of a
--   priority queue.
--   
--   <ul>
--   <li><pre><a>insert</a> k v q = <a>union</a> (<a>singleton</a> k v)
--   q</pre></li>
--   </ul>
--   
--   If <tt>q</tt> contains entries with the same priority <tt>k</tt>,
--   <a>minView</a> of <tt><a>insert</a> k v q</tt> will return them after
--   this one.
insert :: Ord k => k -> v -> PQueue k v -> PQueue k v

-- | <i>O(log n)</i>. Add a (priority, value) pair to the back of a
--   priority queue.
--   
--   <ul>
--   <li><pre><a>add</a> k v q = <a>union</a> q (<a>singleton</a> k
--   v)</pre></li>
--   </ul>
--   
--   If <tt>q</tt> contains entries with the same priority <tt>k</tt>,
--   <a>minView</a> of <tt><a>add</a> k v q</tt> will return them before
--   this one.
add :: Ord k => k -> v -> PQueue k v -> PQueue k v

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

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

-- | <i>O(1)</i> for the element, <i>O(log(n))</i> for the reduced queue.
--   Returns <a>Nothing</a> for an empty map, or the value associated with
--   the minimal priority together with the rest of the priority queue.
--   
--   <ul>
--   <li><pre><a>minView</a> <a>empty</a> = <a>Nothing</a></pre></li>
--   <li><pre><a>minView</a> (<a>singleton</a> k v) = <a>Just</a> (v,
--   <a>empty</a>)</pre></li>
--   </ul>
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)

-- | <i>O(1)</i> for the element, <i>O(log(n))</i> for the reduced queue.
--   Returns <a>Nothing</a> for an empty map, or the minimal (priority,
--   value) pair together with the rest of the priority queue.
--   
--   <ul>
--   <li><pre><a>minViewWithKey</a> <a>empty</a> =
--   <a>Nothing</a></pre></li>
--   <li><pre><a>minViewWithKey</a> (<a>singleton</a> k v) = <a>Just</a>
--   ((k, v), <a>empty</a>)</pre></li>
--   <li>If <tt><a>minViewWithKey</a> qi = <a>Just</a> ((ki, vi), qi')</tt>
--   and <tt>k1 &lt;= k2</tt>, then <tt><a>minViewWithKey</a> (<a>union</a>
--   q1 q2) = <a>Just</a> ((k1, v1), <a>union</a> q1' q2)</tt></li>
--   <li>If <tt><a>minViewWithKey</a> qi = <a>Just</a> ((ki, vi), qi')</tt>
--   and <tt>k2 &lt; k1</tt>, then <tt><a>minViewWithKey</a> (<a>union</a>
--   q1 q2) = <a>Just</a> ((k2, v2), <a>union</a> q1 q2')</tt></li>
--   </ul>
minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)

-- | <i>O(n)</i> for number of elements taken.
takeWithKeys :: Ord k => Int -> PQueue k v -> ([(k, v)], PQueue k v)

-- | <i>O(n)</i> for number of elements taken.
take :: Ord k => Int -> PQueue k v -> ([v], PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Functor (HaskellWorks.Data.PriorityQueue.Strict.PQueue k)
instance GHC.Classes.Ord k => Data.Foldable.Foldable (HaskellWorks.Data.PriorityQueue.Strict.PQueue k)
instance GHC.Classes.Ord k => GHC.Base.Semigroup (HaskellWorks.Data.PriorityQueue.Strict.PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Monoid (HaskellWorks.Data.PriorityQueue.Strict.PQueue k v)
instance GHC.Classes.Ord k => GHC.Base.Semigroup (HaskellWorks.Data.PriorityQueue.Strict.Prio k v)
instance GHC.Classes.Ord k => GHC.Base.Monoid (HaskellWorks.Data.PriorityQueue.Strict.Prio k v)
instance GHC.Classes.Ord k => HaskellWorks.Data.FingerTree.Strict.Measured (HaskellWorks.Data.PriorityQueue.Strict.Prio k v) (HaskellWorks.Data.PriorityQueue.Strict.Entry k v)
instance GHC.Base.Functor (HaskellWorks.Data.PriorityQueue.Strict.Entry k)
instance Data.Foldable.Foldable (HaskellWorks.Data.PriorityQueue.Strict.Entry k)

module HaskellWorks.Data.Segment.Strict

-- | A closed segment. The lower bound should be less than or equal to the
--   higher bound.
data Segment k
Segment :: !k -> !k -> Segment k
[low] :: Segment k -> !k
[high] :: Segment k -> !k

-- | A segment in which the lower and upper bounds are equal.
point :: k -> Segment k
instance Control.DeepSeq.NFData k => Control.DeepSeq.NFData (HaskellWorks.Data.Segment.Strict.Segment k)
instance GHC.Generics.Generic (HaskellWorks.Data.Segment.Strict.Segment k)
instance GHC.Show.Show k => GHC.Show.Show (HaskellWorks.Data.Segment.Strict.Segment k)
instance GHC.Classes.Ord k => GHC.Classes.Ord (HaskellWorks.Data.Segment.Strict.Segment k)
instance GHC.Classes.Eq k => GHC.Classes.Eq (HaskellWorks.Data.Segment.Strict.Segment k)
instance GHC.Base.Monoid k => HaskellWorks.Data.FingerTree.Strict.Measured k (HaskellWorks.Data.Segment.Strict.Segment k)


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

-- | A closed segment. The lower bound should be less than or equal to the
--   higher bound.
data Segment k
Segment :: !k -> !k -> Segment k
[low] :: Segment k -> !k
[high] :: Segment k -> !k

-- | A segment in which the lower and upper bounds are equal.
point :: k -> Segment k
newtype SegmentMap k a
SegmentMap :: OrderedMap (Max k) (Segment k, a) -> SegmentMap k a

-- | Map of closed segments, possibly with duplicates. The <a>Foldable</a>
--   and <a>Traversable</a> instances process the segments in
--   lexicographical order.
newtype OrderedMap k a
OrderedMap :: FingerTree k (Item k a) -> OrderedMap k a
delete :: forall k a. (Bounded k, Ord k, Enum k, Eq a, Show k, Show a) => Segment k -> SegmentMap k a -> SegmentMap k a

-- | <i>O(1)</i>. The empty segment map.
empty :: SegmentMap k a
fromList :: (Ord v, Enum v, Eq a, Bounded v, Show v, Show a) => [(Segment v, a)] -> SegmentMap v a
insert :: forall k a. (Bounded k, Ord k, Enum k, Eq a, Show k, Show a) => Segment k -> a -> SegmentMap k a -> SegmentMap k a

-- | <i>O(1)</i>. Segment map with a single entry.
singleton :: Segment k -> a -> SegmentMap k a
update :: forall k a. (Ord k, Enum k, Bounded k, Eq a, Show k, Show a) => Segment k -> Maybe a -> SegmentMap k a -> SegmentMap k a
segmentMapToList :: SegmentMap k a -> [(Segment k, a)]
data Item k a
Item :: !k -> !a -> Item k a
cappedL :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k, a)) -> (FingerTree (Max k) (Item (Max k) (Segment k, a)), FingerTree (Max k) (Item (Max k) (Segment k, a)))
cappedM :: (Enum k, Ord k, Bounded k, Show k, Show a) => k -> FingerTree (Max k) (Item (Max k) (Segment k, a)) -> FingerTree (Max k) (Item (Max k) (Segment k, a))
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.SegmentMap.Strict.SegmentMap k a)
instance GHC.Generics.Generic (HaskellWorks.Data.SegmentMap.Strict.SegmentMap k a)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.SegmentMap.Strict.SegmentMap k a)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k a)
instance GHC.Generics.Generic (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k a)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k a)
instance GHC.Base.Functor (HaskellWorks.Data.SegmentMap.Strict.SegmentMap k)
instance GHC.Base.Functor (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k)
instance Data.Foldable.Foldable (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k)
instance Data.Traversable.Traversable (HaskellWorks.Data.SegmentMap.Strict.OrderedMap k)


-- | SegmentSet provides an efficient implementation of a set of segments
--   (a.k.a intervals). Segments in the set are non-overlapping. Adjacent
--   segments are merged (i.e. (a .. b), (b + 1 .. c) -&gt; (a .. c)).
--   
--   Segment sets are implemented using the <a>FingerTree</a> type,
--   following section 4.8 of
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programmaxg</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the size of the set. These bounds hold even in a
--   persistent (shared) setting.
--   
--   <i>Note</i>: Many of these operations have the same names as similar
--   operations on lists in the <a>Prelude</a>. The ambiguity may be
--   resolved using either qualification or the <tt>hiding</tt> clause.
module HaskellWorks.Data.SegmentSet.Strict

-- | A closed segment. The lower bound should be less than or equal to the
--   higher bound.
data Segment k
Segment :: !k -> !k -> Segment k
[low] :: Segment k -> !k
[high] :: Segment k -> !k

-- | A segment in which the lower and upper bounds are equal.
point :: k -> Segment k
newtype SegmentSet k
SegmentSet :: OrderedMap (Max k) (Segment k) -> SegmentSet k

-- | Map of closed segments, possibly with duplicates. The <a>Foldable</a>
--   and <a>Traversable</a> instances process the segments in
--   lexicographical order.
newtype OrderedMap k a
OrderedMap :: FingerTree k (Item k a) -> OrderedMap k a

-- | <i>O(log(n))</i>. Remove a segment from the set. Alias of update.
delete :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k

-- | <i>O(1)</i>. The empty segment set.
empty :: SegmentSet k
fromList :: (Ord v, Enum v, Bounded v, Show v) => [Segment v] -> SegmentSet v

-- | <i>O(log(n))</i>. Insert a segment into the set. Alias of update.
insert :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k

-- | <i>O(1)</i>. Segment set with a single entry.
singleton :: Segment k -> SegmentSet k

-- | Update a segment set. Prefer <a>insert</a> or <a>delete</a> in most
--   cases.
update :: forall k a. (Ord k, Enum k, Bounded k, Show k) => Segment k -> Bool -> SegmentSet k -> SegmentSet k
segmentSetToList :: SegmentSet k -> [Segment k]
data Item k a
Item :: !k -> !a -> Item k a
cappedL :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> (FingerTree (Max k) (Item (Max k) (Segment k)), FingerTree (Max k) (Item (Max k) (Segment k)))
cappedM :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> FingerTree (Max k) (Item (Max k) (Segment k))
instance Control.DeepSeq.NFData k => Control.DeepSeq.NFData (HaskellWorks.Data.SegmentSet.Strict.SegmentSet k)
instance GHC.Generics.Generic (HaskellWorks.Data.SegmentSet.Strict.SegmentSet k)
instance GHC.Show.Show k => GHC.Show.Show (HaskellWorks.Data.SegmentSet.Strict.SegmentSet k)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k a)
instance GHC.Generics.Generic (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k a)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k a)
instance GHC.Base.Functor (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k)
instance Data.Foldable.Foldable (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k)
instance Data.Traversable.Traversable (HaskellWorks.Data.SegmentSet.Strict.OrderedMap k)
