Safe Haskell	None
Language	Haskell2010

Data.OrdSeq

Synopsis

data Key a
- = NoKey
- | Key {
  - getKey :: !a
  }
liftCmp :: (a -> a -> Ordering) -> Key a -> Key a -> Ordering
newtype Elem a = Elem {
- getElem :: a
}
newtype OrdSeq a = OrdSeq {
- _asFingerTree :: FingerTree (Key a) (Elem 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)
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.OrdSeq Methods (==) :: Key a -> Key a -> Bool # (/=) :: Key a -> Key a -> Bool #
Ord a => Ord (Key a) Source #
Instance details Defined in Data.OrdSeq 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.OrdSeq Methods showsPrec :: Int -> Key a -> ShowS # show :: Key a -> String # showList :: [Key a] -> ShowS #
Semigroup (Key a) Source #
Instance details Defined in Data.OrdSeq 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.OrdSeq Methods mempty :: Key a # mappend :: Key a -> Key a -> Key a # mconcat :: [Key a] -> Key a #
Measured (Key a) (Elem a) Source #
Instance details Defined in Data.OrdSeq Methods measure :: Elem a -> Key a #

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

newtype Elem a Source #

Constructors

Elem
Fields getElem :: a

Instances

Functor Elem Source #
Instance details Defined in Data.OrdSeq Methods fmap :: (a -> b) -> Elem a -> Elem b # (<$) :: a -> Elem b -> Elem a #
Foldable Elem Source #
Instance details Defined in Data.OrdSeq Methods fold :: Monoid m => Elem m -> m # foldMap :: Monoid m => (a -> m) -> Elem a -> m # foldr :: (a -> b -> b) -> b -> Elem a -> b # foldr' :: (a -> b -> b) -> b -> Elem a -> b # foldl :: (b -> a -> b) -> b -> Elem a -> b # foldl' :: (b -> a -> b) -> b -> Elem a -> b # foldr1 :: (a -> a -> a) -> Elem a -> a # foldl1 :: (a -> a -> a) -> Elem a -> a # toList :: Elem a -> [a] # null :: Elem a -> Bool # length :: Elem a -> Int # elem :: Eq a => a -> Elem a -> Bool # maximum :: Ord a => Elem a -> a # minimum :: Ord a => Elem a -> a # sum :: Num a => Elem a -> a # product :: Num a => Elem a -> a #
Traversable Elem Source #
Instance details Defined in Data.OrdSeq Methods traverse :: Applicative f => (a -> f b) -> Elem a -> f (Elem b) # sequenceA :: Applicative f => Elem (f a) -> f (Elem a) # mapM :: Monad m => (a -> m b) -> Elem a -> m (Elem b) # sequence :: Monad m => Elem (m a) -> m (Elem a) #
Eq a => Eq (Elem a) Source #
Instance details Defined in Data.OrdSeq Methods (==) :: Elem a -> Elem a -> Bool # (/=) :: Elem a -> Elem a -> Bool #
Ord a => Ord (Elem a) Source #
Instance details Defined in Data.OrdSeq Methods compare :: Elem a -> Elem a -> Ordering # (<) :: Elem a -> Elem a -> Bool # (<=) :: Elem a -> Elem a -> Bool # (>) :: Elem a -> Elem a -> Bool # (>=) :: Elem a -> Elem a -> Bool # max :: Elem a -> Elem a -> Elem a # min :: Elem a -> Elem a -> Elem a #
Show a => Show (Elem a) Source #
Instance details Defined in Data.OrdSeq Methods showsPrec :: Int -> Elem a -> ShowS # show :: Elem a -> String # showList :: [Elem a] -> ShowS #
Measured (Key a) (Elem a) Source #
Instance details Defined in Data.OrdSeq Methods measure :: Elem a -> Key a #

newtype OrdSeq a Source #

Constructors

OrdSeq
Fields _asFingerTree :: FingerTree (Key a) (Elem a)

Instances

Foldable OrdSeq Source #
Instance details Defined in Data.OrdSeq 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.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 #

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

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

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]
(OrdSeq {_asFingerTree = fromList [Elem 1,Elem 2]},OrdSeq {_asFingerTree = fromList [Elem 3]},OrdSeq {_asFingerTree = fromList [Elem 4,Elem 5]})
>>> splitOn fst 2 $ fromAscList' [(0,"-"),(1,"A"),(2,"B"),(2,"C"),(3,"D"),(4,"E")]
(OrdSeq {_asFingerTree = fromList [Elem (0,"-"),Elem (1,"A")]},OrdSeq {_asFingerTree = fromList [Elem (2,"B"),Elem (2,"C")]},OrdSeq {_asFingerTree = fromList [Elem (3,"D"),Elem (4,"E")]})

$O(\log 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 n)$

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)

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