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


-- | Provides an annotated splay tree
--   
--   Annotated splay trees (compare to 2-3 finger trees)
@package splaytree
@version 0.1

module Data.SplayTree
data SplayTree a
Tip :: SplayTree a
Branch :: (Measure a) -> (SplayTree a) -> !a -> (SplayTree a) -> SplayTree a
class Monoid (Measure a) => Measured a where { type family Measure a :: *; }
measure :: Measured a => a -> Measure a
empty :: SplayTree a
(|>) :: Measured a => SplayTree a -> a -> SplayTree a
(<|) :: Measured a => a -> SplayTree a -> SplayTree a

-- | Append two trees.
(><) :: Measured a => SplayTree a -> SplayTree a -> SplayTree a

-- | Is the tree empty?
null :: SplayTree a -> Bool
singleton :: Measured a => a -> SplayTree a
size :: SplayTree a -> Int

-- | Split a tree at the point where the predicate on the measure changes
--   from False to True.
split :: Measured a => (Measure a -> Bool) -> SplayTree a -> (SplayTree a, SplayTree a)

-- | find the first point where the predicate returns True. Returns a tree
--   splayed with that node at the top.
query :: (Measured a, (Measure a) ~ (Measure (SplayTree a))) => (Measure a -> Bool) -> SplayTree a -> Maybe (a, SplayTree a)
memberSplay :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> (Bool, SplayTree a)
delete :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> SplayTree a
insert :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> SplayTree a
difference :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree a
intersection :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree a

-- | rebalance a splay tree. The order of elements does not change.
balance :: Measured a => SplayTree a -> SplayTree a

-- | descend to the deepest left-hand branch
deepL :: Measured a => SplayTree a -> SplayTree a

-- | descend to the deepest right-hand branch
deepR :: Measured a => SplayTree a -> SplayTree a

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

-- | <i>O(n)</i>. Create a Tree from a finite list of elements.
--   
--   After the tree is created, it is balanced. This is useful with sorted
--   data, which would otherwise create a completely unbalanced tree.
fromListBalance :: Measured a => [a] -> SplayTree a

-- | Like fmap, but with a more restrictive type.
fmap' :: Measured b => (a -> b) -> SplayTree a -> SplayTree b

-- | Like traverse, but with a more restrictive type.
traverse' :: (Measured b, Applicative f) => (a -> f b) -> SplayTree a -> f (SplayTree b)
instance Typeable1 SplayTree
instance Show a => Show (ElemD a)
instance Ord a => Ord (ElemD a)
instance Eq a => Eq (ElemD a)
instance Num a => Num (ElemD a)
instance Enum a => Enum (ElemD a)
instance Show Depth
instance Ord Depth
instance Eq Depth
instance Num Depth
instance Enum Depth
instance Real Depth
instance Integral Depth
instance Measured (ElemD a)
instance Monoid Depth
instance Foldable SplayTree
instance Measured a => Measured (SplayTree a)
instance Measured a => Monoid (SplayTree a)
instance (Show a, Show (Measure a)) => Show (SplayTree a)
instance Ord a => Ord (SplayTree a)
instance Eq a => Eq (SplayTree a)
instance (NFData a, NFData (Measure a)) => NFData (SplayTree a)

module Data.SplayTree.RangeSet

-- | a RangeSet element
data Range a
Range :: !a -> !a -> Range a
rMin :: Range a -> !a
rang :: Range a -> !a
type RangeSet a = SplayTree (Range a)

-- | A range of a single point (range =0)
point :: Num a => a -> Range a

-- | Create a <tt>Range</tt> from a minimum value and range
range :: (Num a, Ord a) => a -> a -> Range a

-- | Create a <tt>Range</tt> from the two endpoints.
rangePs :: (Num a, Ord a) => a -> a -> Range a

-- | check if a value is within the range
inRange :: (Num a, Ord a) => a -> Range a -> Bool
rangeMax :: Num a => Range a -> a
null :: RangeSet a -> Bool
singleton :: (Num a, Ord a) => Range a -> RangeSet a
empty :: RangeSet a
append :: (Num a, Ord a) => RangeSet a -> RangeSet a -> RangeSet a
insert :: (Num a, Ord a) => RangeSet a -> Range a -> RangeSet a
delete :: (Num a, Ord a) => RangeSet a -> Range a -> RangeSet a
fromList :: (Num a, Ord a) => [Range a] -> RangeSet a
instance Show a => Show (Range a)
instance Ord a => Ord (Range a)
instance Eq a => Eq (Range a)
instance Functor Range
instance Foldable Range
instance Traversable Range
instance Show a => Show (RangeM a)
instance Ord a => Ord (RangeM a)
instance Eq a => Eq (RangeM a)
instance (Num a, Ord a) => Measured (Range a)
instance (Num a, Ord a) => Monoid (RangeM a)

module Data.SplayTree.Seq
data Seq a
instance Show a => Show (Elem a)
instance Ord a => Ord (Elem a)
instance Eq a => Eq (Elem a)
instance Num a => Num (Elem a)
instance Enum a => Enum (Elem a)
instance Functor Elem
instance Foldable Elem
instance Traversable Elem
instance Eq a => Eq (Seq a)
instance Show a => Show (Seq a)
instance Ord a => Ord (Seq a)
instance Foldable Seq
instance Monoid (Seq a)
instance Traversable Seq
instance Functor Seq
instance Measured (Elem a)

module Data.SplayTree.Set
data Set a

-- | Construct an empty set
empty :: Ord a => Set a

-- | <a>True</a> if this set is empty, <a>False</a> otherwise.
null :: Ord a => Set a -> Bool

-- | Return the number of elements in this set.
size :: Ord a => Set a -> Int

-- | Return <a>True</a> if the given value is present in this set,
--   <a>False</a> otherwise.
member :: Ord a => a -> Set a -> Bool

-- | Check if <tt>a</tt> is a member, and return a set splayed to
--   <tt>a</tt>. The return set is splayed to an element near <tt>a</tt> if
--   <tt>a</tt> isn't in the set.
memberSplay :: Ord a => a -> Set a -> (Bool, Set a)

-- | Add the specified value to this set.
insert :: Ord a => a -> Set a -> Set a

-- | Remove the specified value from this set if present.
delete :: Ord a => a -> Set a -> Set a

-- | Construct a set containing all elements from both sets.
--   
--   The smaller set should be presented as the second argument.
union :: Ord a => Set a -> Set a -> Set a

-- | Difference of two sets. Contains elements of the first set that are
--   not present in the second.
difference :: Ord a => Set a -> Set a -> Set a

-- | Intersection of two sets. Contains all elements which are in both
--   sets.
intersection :: Ord a => Set a -> Set a -> Set a

-- | Transform this set by applying a function to every value.
map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

-- | Construct a <tt>Set</tt> from a list of elements.
--   
--   The Set is created by calling <tt>Data.SplayTree.fromListBalance</tt>.
fromList :: Ord a => [a] -> Set a
instance Show a => Show (Elem a)
instance Ord a => Ord (Elem a)
instance Eq a => Eq (Elem a)
instance Functor Elem
instance Foldable Elem
instance Traversable Elem
instance Eq a => Eq (Set a)
instance Show a => Show (Set a)
instance Ord a => Ord (Set a)
instance Foldable Set
instance Ord a => Monoid (Set a)
instance Ord a => Measured (Elem a)
instance Ord a => Monoid (Elem a)