EdisonCore-1.2.2.1: A library of efficent, purely-functional data structures (Core Implementations)

Portability GHC, Hugs (MPTC and FD) stable robdockins AT fastmail DOT fm None

Data.Edison.Coll.SplayHeap

Description

Splay heaps.

If `minElem` is called frequently, then SplayHeap should be used in conjunction with Data.Edison.Coll.MinHeap.

References:

• Chris Okasaki. Purely Functional Data Structures. 1998. Section 5.4.

Synopsis

# Type of splay heaps

data Heap a Source

Instances

 Ord a => Eq (Heap a) Ord a => Ord (Heap a) (Ord a, Read a) => Read (Heap a) (Ord a, Show a) => Show (Heap a) (Ord a, Arbitrary a) => Arbitrary (Heap a) (Ord a, CoArbitrary a) => CoArbitrary (Heap a) Ord a => Monoid (Heap a) Ord a => CollX (Heap a) a Ord a => OrdCollX (Heap a) a Ord a => Coll (Heap a) a Ord a => OrdColl (Heap a) a

# CollX operations

fromSeq :: (Ord a, Sequence s) => s a -> Heap aSource

insert :: Ord a => a -> Heap a -> Heap aSource

insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap aSource

union :: Ord a => Heap a -> Heap a -> Heap aSource

unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap aSource

delete :: Ord a => a -> Heap a -> Heap aSource

deleteAll :: Ord a => a -> Heap a -> Heap aSource

deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap aSource

member :: Ord a => a -> Heap a -> BoolSource

count :: Ord a => a -> Heap a -> IntSource

# Coll operations

toSeq :: (Ord a, Sequence s) => Heap a -> s aSource

lookup :: Ord a => a -> Heap a -> aSource

lookupM :: (Ord a, Monad m) => a -> Heap a -> m aSource

lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s aSource

lookupWithDefault :: Ord a => a -> a -> Heap a -> aSource

fold :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource

fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource

fold1 :: Ord a => (a -> a -> a) -> Heap a -> aSource

fold1' :: Ord a => (a -> a -> a) -> Heap a -> aSource

filter :: Ord a => (a -> Bool) -> Heap a -> Heap aSource

partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

strictWith :: (a -> b) -> Heap a -> Heap aSource

# OrdCollX operations

deleteMin :: Ord a => Heap a -> Heap aSource

deleteMax :: Ord a => Heap a -> Heap aSource

unsafeInsertMin :: Ord a => a -> Heap a -> Heap aSource

unsafeInsertMax :: Ord a => a -> Heap a -> Heap aSource

unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap aSource

unsafeAppend :: Ord a => Heap a -> Heap a -> Heap aSource

filterLT :: Ord a => a -> Heap a -> Heap aSource

filterLE :: Ord a => a -> Heap a -> Heap aSource

filterGT :: Ord a => a -> Heap a -> Heap aSource

filterGE :: Ord a => a -> Heap a -> Heap aSource

partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)Source

partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)Source

partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)Source

# OrdColl operations

minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)Source

minElem :: Ord a => Heap a -> aSource

maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)Source

maxElem :: Ord a => Heap a -> aSource

foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource

foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource

foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource

foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource

foldr1 :: Ord a => (a -> a -> a) -> Heap a -> aSource

foldr1' :: Ord a => (a -> a -> a) -> Heap a -> aSource

foldl1 :: Ord a => (a -> a -> a) -> Heap a -> aSource

foldl1' :: Ord a => (a -> a -> a) -> Heap a -> aSource

toOrdSeq :: (Ord a, Sequence s) => Heap a -> s aSource

unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap bSource