Data.SlowSeq

Documentation

data Key a

Constructors

NoKey

Key

Fields

• getKey :: a

Instances

Eq a => Eq (Key a)

Defined in Data.SlowSeq

Methods

(==) :: Key a -> Key a -> Bool

(/=) :: Key a -> Key a -> Bool

Ord a => Ord (Key a)

Defined in Data.SlowSeq

Methods

compare :: Key a -> Key a -> Ordering

(<) :: Key a -> Key a -> Bool

(<=) :: Key a -> Key a -> Bool

(>) :: Key a -> Key a -> Bool

(>=) :: Key a -> Key a -> Bool

max :: Key a -> Key a -> Key a

min :: Key a -> Key a -> Key a

Show a => Show (Key a)

Defined in Data.SlowSeq

Methods

showsPrec :: Int -> Key a -> ShowS

show :: Key a -> String

showList :: [Key a] -> ShowS

Semigroup (Key a)

Defined in Data.SlowSeq

Methods

(<>) :: Key a -> Key a -> Key a

sconcat :: NonEmpty (Key a) -> Key a

stimes :: Integral b => b -> Key a -> Key a

Monoid (Key a)

Defined in Data.SlowSeq

Methods

mempty :: Key a

mappend :: Key a -> Key a -> Key a

mconcat :: [Key a] -> Key a

liftCmp :: (a -> a -> Ordering) -> Key a -> Key a -> Ordering

newtype OrdSeq a

Constructors

OrdSeq

Fields

• _asSeq :: Seq a

Instances

Foldable OrdSeq

Defined in Data.SlowSeq

Methods

fold :: Monoid m => OrdSeq m -> m

foldMap :: Monoid m => (a -> m) -> OrdSeq a -> m

foldr :: (a -> b -> b) -> b -> OrdSeq a -> b

foldr' :: (a -> b -> b) -> b -> OrdSeq a -> b

foldl :: (b -> a -> b) -> b -> OrdSeq a -> b

foldl' :: (b -> a -> b) -> b -> OrdSeq a -> b

foldr1 :: (a -> a -> a) -> OrdSeq a -> a

foldl1 :: (a -> a -> a) -> OrdSeq a -> a

toList :: OrdSeq a -> [a]

null :: OrdSeq a -> Bool

length :: OrdSeq a -> Int

elem :: Eq a => a -> OrdSeq a -> Bool

maximum :: Ord a => OrdSeq a -> a

minimum :: Ord a => OrdSeq a -> a

sum :: Num a => OrdSeq a -> a

product :: Num a => OrdSeq a -> a

Eq a => Eq (OrdSeq a)

Defined in Data.SlowSeq

Methods

(==) :: OrdSeq a -> OrdSeq a -> Bool

(/=) :: OrdSeq a -> OrdSeq a -> Bool

Show a => Show (OrdSeq a)

Defined in Data.SlowSeq

Methods

showsPrec :: Int -> OrdSeq a -> ShowS

show :: OrdSeq a -> String

showList :: [OrdSeq a] -> ShowS

Semigroup (OrdSeq a)

Defined in Data.SlowSeq

Methods

(<>) :: OrdSeq a -> OrdSeq a -> OrdSeq a

sconcat :: NonEmpty (OrdSeq a) -> OrdSeq a

stimes :: Integral b => b -> OrdSeq a -> OrdSeq a

Monoid (OrdSeq a)

Defined in Data.SlowSeq

Methods

mempty :: OrdSeq a

mappend :: OrdSeq a -> OrdSeq a -> OrdSeq a

mconcat :: [OrdSeq a] -> OrdSeq a

type Compare a = a -> a -> Ordering

insertBy :: Compare a -> a -> OrdSeq a -> OrdSeq a

Insert into a monotone OrdSeq.

pre: the comparator maintains monotonicity

\(O(\log^2 n)\)

insert :: Ord a => a -> OrdSeq a -> OrdSeq a

Insert into a sorted OrdSeq

\(O(\log^2 n)\)

deleteAllBy :: Compare a -> a -> OrdSeq a -> OrdSeq a

splitBy :: Compare a -> a -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)

\(O(\log^2 n)\)

splitOn :: Ord b => (a -> b) -> b -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)

Given a monotonic function f that maps a to b, split the sequence s depending on the b values. I.e. the result (l,m,r) is such that * all (< x) . fmap f $ l * all (== x) . fmap f $ m * all (> x) . fmap f $ r

>>> splitOn id 3 $ fromAscList' [1..5]
(OrdSeq {_asSeq = fromList [Elem 1,Elem 2]},OrdSeq {_asSeq = fromList [Elem 3]},OrdSeq {_asSeq = fromList [Elem 4,Elem 5]})
>>> splitOn fst 2 $ fromAscList' [(0,"-"),(1,"A"),(2,"B"),(2,"C"),(3,"D"),(4,"E")]
(OrdSeq {_asSeq = fromList [Elem (0,"-"),Elem (1,"A")]},OrdSeq {_asSeq = fromList [Elem (2,"B"),Elem (2,"C")]},OrdSeq {_asSeq = fromList [Elem (3,"D"),Elem (4,"E")]})

\(O(\log^2 n)\)

splitMonotonic :: (a -> Bool) -> OrdSeq a -> (OrdSeq a, OrdSeq a)

Given a monotonic predicate p, splits the sequence s into two sequences (as,bs) such that all (not p) as and all p bs

\(O(\log^2 n)\)

split :: (a -> Bool) -> Seq a -> (Seq a, Seq a)

deleteAll :: Ord a => a -> OrdSeq a -> OrdSeq a

fromListBy :: Compare a -> [a] -> OrdSeq a

inserts all eleements in order \(O(n\log n)\)

fromListByOrd :: Ord a => [a] -> OrdSeq a

inserts all eleements in order \(O(n\log n)\)

fromAscList' :: [a] -> OrdSeq a

O(n)

lookupBy :: Compare a -> a -> OrdSeq a -> Maybe a

\(O(\log^2 n)\)

memberBy :: Compare a -> a -> OrdSeq a -> Bool

mapMonotonic :: (a -> b) -> OrdSeq a -> OrdSeq b

Fmap, assumes the order does not change \(O(n)\)

viewl :: OrdSeq a -> ViewL OrdSeq a

Gets the first element from the sequence \(O(1)\)

viewr :: OrdSeq a -> ViewR OrdSeq a

minView :: OrdSeq a -> Maybe (a, OrdSeq a)

lookupMin :: OrdSeq a -> Maybe a

maxView :: OrdSeq a -> Maybe (a, OrdSeq a)

lookupMax :: OrdSeq a -> Maybe a