EdisonCore-1.3.2: A library of efficient, purely-functional data structures (Core Implementations)

CopyrightCopyright (c) 1998-1999 2008 Chris Okasaki
LicenseMIT; see COPYRIGHT file for terms and conditions
Maintainerrobdockins AT fastmail DOT fm
Stabilitystable
PortabilityGHC, Hugs (MPTC and FD)
Safe HaskellNone
LanguageHaskell2010

Data.Edison.Coll.SkewHeap

Contents

Description

Skew heaps.

References:

  • Daniel Sleator and Robert Tarjan. "Self-Adjusting Heaps". SIAM Journal on Computing, 15(1):52-69, February 1986.

Synopsis

Type of skew heaps

data Heap a Source #

Instances

Ord a => Eq (Heap a) Source # 

Methods

(==) :: Heap a -> Heap a -> Bool #

(/=) :: Heap a -> Heap a -> Bool #

Ord a => Ord (Heap a) Source # 

Methods

compare :: Heap a -> Heap a -> Ordering #

(<) :: Heap a -> Heap a -> Bool #

(<=) :: Heap a -> Heap a -> Bool #

(>) :: Heap a -> Heap a -> Bool #

(>=) :: Heap a -> Heap a -> Bool #

max :: Heap a -> Heap a -> Heap a #

min :: Heap a -> Heap a -> Heap a #

(Ord a, Read a) => Read (Heap a) Source # 
(Ord a, Show a) => Show (Heap a) Source # 

Methods

showsPrec :: Int -> Heap a -> ShowS #

show :: Heap a -> String #

showList :: [Heap a] -> ShowS #

Ord a => Semigroup (Heap a) Source # 

Methods

(<>) :: Heap a -> Heap a -> Heap a #

sconcat :: NonEmpty (Heap a) -> Heap a #

stimes :: Integral b => b -> Heap a -> Heap a #

Ord a => Monoid (Heap a) Source # 

Methods

mempty :: Heap a #

mappend :: Heap a -> Heap a -> Heap a #

mconcat :: [Heap a] -> Heap a #

(Ord a, Arbitrary a) => Arbitrary (Heap a) Source # 

Methods

arbitrary :: Gen (Heap a) #

shrink :: Heap a -> [Heap a] #

(Ord a, CoArbitrary a) => CoArbitrary (Heap a) Source # 

Methods

coarbitrary :: Heap a -> Gen b -> Gen b #

Ord a => CollX (Heap a) a Source # 

Methods

singleton :: a -> Heap a #

fromSeq :: Sequence seq => seq a -> Heap a #

unionSeq :: Sequence seq => seq (Heap a) -> Heap a #

insert :: a -> Heap a -> Heap a #

insertSeq :: Sequence seq => seq a -> Heap a -> Heap a #

delete :: a -> Heap a -> Heap a #

deleteAll :: a -> Heap a -> Heap a #

deleteSeq :: Sequence seq => seq a -> Heap a -> Heap a #

null :: Heap a -> Bool #

size :: Heap a -> Int #

member :: a -> Heap a -> Bool #

count :: a -> Heap a -> Int #

strict :: Heap a -> Heap a #

structuralInvariant :: Heap a -> Bool #

instanceName :: Heap a -> String #

Ord a => OrdCollX (Heap a) a Source # 

Methods

deleteMin :: Heap a -> Heap a #

deleteMax :: Heap a -> Heap a #

unsafeInsertMin :: a -> Heap a -> Heap a #

unsafeInsertMax :: a -> Heap a -> Heap a #

unsafeFromOrdSeq :: Sequence seq => seq a -> Heap a #

unsafeAppend :: Heap a -> Heap a -> Heap a #

filterLT :: a -> Heap a -> Heap a #

filterLE :: a -> Heap a -> Heap a #

filterGT :: a -> Heap a -> Heap a #

filterGE :: a -> Heap a -> Heap a #

partitionLT_GE :: a -> Heap a -> (Heap a, Heap a) #

partitionLE_GT :: a -> Heap a -> (Heap a, Heap a) #

partitionLT_GT :: a -> Heap a -> (Heap a, Heap a) #

Ord a => Coll (Heap a) a Source # 

Methods

toSeq :: Sequence seq => Heap a -> seq a #

lookup :: a -> Heap a -> a #

lookupM :: Monad m => a -> Heap a -> m a #

lookupAll :: Sequence seq => a -> Heap a -> seq a #

lookupWithDefault :: a -> a -> Heap a -> a #

fold :: (a -> b -> b) -> b -> Heap a -> b #

fold' :: (a -> b -> b) -> b -> Heap a -> b #

fold1 :: (a -> a -> a) -> Heap a -> a #

fold1' :: (a -> a -> a) -> Heap a -> a #

filter :: (a -> Bool) -> Heap a -> Heap a #

partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a) #

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

Ord a => OrdColl (Heap a) a Source # 

Methods

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

minElem :: Heap a -> a #

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

maxElem :: Heap a -> a #

foldr :: (a -> b -> b) -> b -> Heap a -> b #

foldr' :: (a -> b -> b) -> b -> Heap a -> b #

foldl :: (b -> a -> b) -> b -> Heap a -> b #

foldl' :: (b -> a -> b) -> b -> Heap a -> b #

foldr1 :: (a -> a -> a) -> Heap a -> a #

foldr1' :: (a -> a -> a) -> Heap a -> a #

foldl1 :: (a -> a -> a) -> Heap a -> a #

foldl1' :: (a -> a -> a) -> Heap a -> a #

toOrdSeq :: Sequence seq => Heap a -> seq a #

unsafeMapMonotonic :: (a -> a) -> Heap a -> Heap a #

CollX operations

empty :: Ord a => Heap a Source #

singleton :: Ord a => a -> Heap a Source #

fromSeq :: (Ord a, Sequence seq) => seq a -> Heap a Source #

insert :: Ord a => a -> Heap a -> Heap a Source #

insertSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a Source #

union :: Ord a => Heap a -> Heap a -> Heap a Source #

unionSeq :: (Ord a, Sequence seq) => seq (Heap a) -> Heap a Source #

delete :: Ord a => a -> Heap a -> Heap a Source #

deleteAll :: Ord a => a -> Heap a -> Heap a Source #

deleteSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a Source #

null :: Ord a => Heap a -> Bool Source #

size :: Ord a => Heap a -> Int Source #

member :: Ord a => a -> Heap a -> Bool Source #

count :: Ord a => a -> Heap a -> Int Source #

strict :: Heap a -> Heap a Source #

Coll operations

toSeq :: (Ord a, Sequence seq) => Heap a -> seq a Source #

lookup :: Ord a => a -> Heap a -> a Source #

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

lookupAll :: (Ord a, Sequence seq) => a -> Heap a -> seq a Source #

lookupWithDefault :: Ord a => a -> a -> Heap a -> a Source #

fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source #

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

fold1 :: Ord a => (a -> a -> a) -> Heap a -> a Source #

fold1' :: Ord a => (a -> a -> a) -> Heap a -> a Source #

filter :: Ord a => (a -> Bool) -> Heap a -> Heap a Source #

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

strictWith :: (a -> b) -> Heap a -> Heap a Source #

OrdCollX operations

deleteMin :: Ord a => Heap a -> Heap a Source #

deleteMax :: Ord a => Heap a -> Heap a Source #

unsafeInsertMin :: Ord a => a -> Heap a -> Heap a Source #

unsafeInsertMax :: Ord a => a -> Heap a -> Heap a Source #

unsafeFromOrdSeq :: (Ord a, Sequence seq) => seq a -> Heap a Source #

unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a Source #

filterLT :: Ord a => a -> Heap a -> Heap a Source #

filterLE :: Ord a => a -> Heap a -> Heap a Source #

filterGT :: Ord a => a -> Heap a -> Heap a Source #

filterGE :: Ord a => a -> Heap a -> Heap a Source #

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 -> a Source #

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

maxElem :: Ord a => Heap a -> a Source #

foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source #

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

foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b Source #

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

foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a Source #

foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a Source #

foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a Source #

foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a Source #

toOrdSeq :: (Ord a, Sequence seq) => Heap a -> seq a Source #

unsafeMapMonotonic :: Ord a => (a -> a) -> Heap a -> Heap a Source #

Documentation