Safe Haskell	None
Language	Haskell2010

Data.SlowSeq

Synopsis

data Key a
- = NoKey
- | Key {
  - getKey :: a
  }
liftCmp :: (a -> a -> Ordering) -> Key a -> Key a -> Ordering
newtype OrdSeq a = OrdSeq {
- _asSeq :: Seq a
}
type Compare a = a -> a -> Ordering
insertBy :: Compare a -> a -> OrdSeq a -> OrdSeq a
insert :: Ord a => a -> OrdSeq a -> OrdSeq a
deleteAllBy :: Compare a -> a -> OrdSeq a -> OrdSeq a
splitBy :: Compare a -> a -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)
splitOn :: Ord b => (a -> b) -> b -> OrdSeq a -> (OrdSeq a, OrdSeq a, OrdSeq a)
splitMonotonic :: (a -> Bool) -> OrdSeq a -> (OrdSeq a, OrdSeq a)
split :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
deleteAll :: Ord a => a -> OrdSeq a -> OrdSeq a
fromListBy :: Compare a -> [a] -> OrdSeq a
fromListByOrd :: Ord a => [a] -> OrdSeq a
fromAscList' :: [a] -> OrdSeq a
lookupBy :: Compare a -> a -> OrdSeq a -> Maybe a
memberBy :: Compare a -> a -> OrdSeq a -> Bool
mapMonotonic :: (a -> b) -> OrdSeq a -> OrdSeq b
viewl :: OrdSeq a -> ViewL OrdSeq a
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

Documentation

data Key a Source #

Constructors

NoKey
Key
Fields getKey :: a

Instances

Eq a => Eq (Key a) Source #
Instance details Defined in Data.SlowSeq Methods (==) :: Key a -> Key a -> Bool # (/=) :: Key a -> Key a -> Bool #
Ord a => Ord (Key a) Source #
Instance details 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) Source #
Instance details Defined in Data.SlowSeq Methods showsPrec :: Int -> Key a -> ShowS # show :: Key a -> String # showList :: [Key a] -> ShowS #
Semigroup (Key a) Source #
Instance details 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) Source #
Instance details 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 Source #

newtype OrdSeq a Source #

Constructors

OrdSeq
Fields _asSeq :: Seq a

Instances

Foldable OrdSeq Source #
Instance details 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) Source #
Instance details Defined in Data.SlowSeq Methods (==) :: OrdSeq a -> OrdSeq a -> Bool # (/=) :: OrdSeq a -> OrdSeq a -> Bool #
Show a => Show (OrdSeq a) Source #
Instance details Defined in Data.SlowSeq Methods showsPrec :: Int -> OrdSeq a -> ShowS # show :: OrdSeq a -> String # showList :: [OrdSeq a] -> ShowS #
Semigroup (OrdSeq a) Source #
Instance details 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) Source #
Instance details 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 Source #

insertBy :: Compare a -> a -> OrdSeq a -> OrdSeq a Source #

Insert into a monotone OrdSeq.

pre: the comparator maintains monotonicity

$O(\log^2 n)$

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

Insert into a sorted OrdSeq

$O(\log^2 n)$

deleteAllBy :: Compare a -> a -> OrdSeq a -> OrdSeq a Source #

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

$O(\log^2 n)$

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

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

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

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

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

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

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

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

fromAscList' :: [a] -> OrdSeq a Source #

O(n)