hgeometry-0.7.0.0: Geometric Algorithms, Data structures, and Data types.

Safe HaskellNone
LanguageHaskell2010

Data.OrdSeq

Synopsis

Documentation

data Key a Source #

Constructors

NoKey 
Key 

Fields

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

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

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) # 
Instance details

Defined in Test.QuickCheck.HGeometryInstances

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 #

\(O(\log n)\)

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

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

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

viewl :: OrdSeq a -> ViewL OrdSeq a Source #

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