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

Copyright Copyright (c) 1998-1999 2008 Chris Okasaki MIT; see COPYRIGHT file for terms and conditions robdockins AT fastmail DOT fm stable GHC, Hugs (MPTC and FD) None Haskell2010

Data.Edison.Coll.SkewHeap

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 # Methodscompare :: 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 # MethodsreadsPrec :: Int -> ReadS (Heap a) #readList :: ReadS [Heap a] # (Ord a, Show a) => Show (Heap a) Source # MethodsshowsPrec :: 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 # Methodsmempty :: Heap a #mappend :: Heap a -> Heap a -> Heap a #mconcat :: [Heap a] -> Heap a # (Ord a, Arbitrary a) => Arbitrary (Heap a) Source # Methodsarbitrary :: Gen (Heap a) #shrink :: Heap a -> [Heap a] # (Ord a, CoArbitrary a) => CoArbitrary (Heap a) Source # Methodscoarbitrary :: Heap a -> Gen b -> Gen b # Ord a => CollX (Heap a) a Source # Methodssingleton :: 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 #instanceName :: Heap a -> String # Ord a => OrdCollX (Heap a) a Source # MethodsdeleteMin :: 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 # MethodstoSeq :: 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 # MethodsminView :: 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 #