Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.OrdSeq

Description

Synopsis

data OrdSeq a
type Compare a = a -> a -> Ordering
insertBy :: Compare a -> a -> OrdSeq a -> OrdSeq a
insert :: Ord 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)
deleteAll :: Ord a => a -> OrdSeq a -> OrdSeq a
deleteAllBy :: Compare 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 OrdSeq a Source #

Sequence of ordered elements.

Instances

Instances details

Foldable OrdSeq Source #
Instance details Defined in Data.OrdSeq Methods fold :: Monoid m => OrdSeq m -> m # foldMap :: Monoid m => (a -> m) -> OrdSeq a -> 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.OrdSeq Methods (==) :: OrdSeq a -> OrdSeq a -> Bool # (/=) :: OrdSeq a -> OrdSeq a -> Bool #
Show a => Show (OrdSeq a) Source #
Instance details Defined in Data.OrdSeq Methods showsPrec :: Int -> OrdSeq a -> ShowS # show :: OrdSeq a -> String # showList :: [OrdSeq a] -> ShowS #
Semigroup (OrdSeq a) Source #
Instance details Defined in Data.OrdSeq 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.OrdSeq Methods mempty :: OrdSeq a # mappend :: OrdSeq a -> OrdSeq a -> OrdSeq a # mconcat :: [OrdSeq a] -> OrdSeq a #
(Arbitrary a, Ord a) => Arbitrary (OrdSeq a) Source #
Instance details Defined in Data.OrdSeq Methods arbitrary :: Gen (OrdSeq a) # shrink :: OrdSeq a -> [OrdSeq a] #

type Compare a = a -> a -> Ordering Source #

Signature for functions that give the ordering of two values.

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

Insert into a monotone OrdSeq.

pre: the comparator maintains monotonicity

$O(\log n)$

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

Insert into a sorted OrdSeq

$O(\log n)$

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

$O(\log 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]
(fromAscList [1,2],fromAscList [3],fromAscList [4,5])
>>> splitOn fst 2 $ fromAscList [(0,"-"),(1,"A"),(2,"B"),(2,"C"),(3,"D"),(4,"E")]
(fromAscList [(0,"-"),(1,"A")],fromAscList [(2,"B"),(2,"C")],fromAscList [(3,"D"),(4,"E")])

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 n)$

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

Deletes all elements from the OrdDeq

$O(n\log n)$

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

$ O(\log n) $. Delete all elements that compare as equal to x.

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)$