-- 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
--   
--   <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://www.soi.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 fingertree
@version 0.1.0.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
--   
--   <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://www.soi.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 Data.FingerTree

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

-- | 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 :: Measured v a => FingerTree v a

-- | <i>O(1)</i>. A singleton sequence.
singleton :: Measured v a => 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

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

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

-- | <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 :: Measured v a => 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

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

-- | <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 <tt>traverse</tt>, 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 <tt>traverse</tt>, but safe only if the function preserves the
--   measure.
unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b)
instance (Eq a, Eq (s a)) => Eq (ViewL s a)
instance (Ord a, Ord (s a)) => Ord (ViewL s a)
instance (Show a, Show (s a)) => Show (ViewL s a)
instance (Read a, Read (s a)) => Read (ViewL s a)
instance (Eq a, Eq (s a)) => Eq (ViewR s a)
instance (Ord a, Ord (s a)) => Ord (ViewR s a)
instance (Show a, Show (s a)) => Show (ViewR s a)
instance (Read a, Read (s a)) => Read (ViewR s a)
instance Show a => Show (Digit a)
instance (Show v, Show a) => Show (Node v a)
instance Show a => Show (FingerTree v a)
instance Ord a => Ord (FingerTree v a)
instance Eq a => Eq (FingerTree v a)
instance Foldable (FingerTree v)
instance Measured v a => Measured v (FingerTree v a)
instance Monoid v => Measured v (Node v a)
instance Foldable (Node v)
instance Measured v a => Measured v (Digit a)
instance Foldable Digit
instance Measured v a => Monoid (FingerTree v a)
instance Functor s => Functor (ViewR s)
instance Functor s => Functor (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://www.soi.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 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 Data.IntervalMap.FingerTree

-- | 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.
data IntervalMap v a

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

-- | <i>O(1)</i>. Interval map with a single entry.
singleton :: Ord v => 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 Eq v => Eq (Interval v)
instance Ord v => Ord (Interval v)
instance Show v => Show (Interval v)
instance Ord v => Monoid (IntervalMap v a)
instance Traversable (IntervalMap v)
instance Foldable (IntervalMap v)
instance Functor (IntervalMap v)
instance Ord v => Measured (IntInterval v) (Node v a)
instance Ord v => Monoid (IntInterval v)
instance Traversable (Node v)
instance Foldable (Node v)
instance Functor (Node v)


-- | 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://www.soi.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 Data.PriorityQueue.FingerTree

-- | Priority queues.
data PQueue k v

-- | <i>O(1)</i>. The empty priority queue.
empty :: Ord k => 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 :: Ord k => 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)
instance Ord k => Monoid (PQueue k v)
instance Ord k => Foldable (PQueue k)
instance Ord k => Functor (PQueue k)
instance Ord k => Measured (Prio k v) (Entry k v)
instance Ord k => Monoid (Prio k v)
instance Foldable (Entry k)
instance Functor (Entry k)
