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

Data.OrdSeq

Synopsis

# Documentation

data Key a Source #

Constructors

 NoKey Key FieldsgetKey :: !a
Instances
 Eq a => Eq (Key a) Source # Instance detailsDefined in Data.OrdSeq Methods(==) :: Key a -> Key a -> Bool #(/=) :: Key a -> Key a -> Bool # Ord a => Ord (Key a) Source # Instance detailsDefined in Data.OrdSeq Methodscompare :: 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 detailsDefined in Data.OrdSeq MethodsshowsPrec :: Int -> Key a -> ShowS #show :: Key a -> String #showList :: [Key a] -> ShowS # Semigroup (Key a) Source # Instance detailsDefined 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 detailsDefined in Data.OrdSeq Methodsmempty :: Key a #mappend :: Key a -> Key a -> Key a #mconcat :: [Key a] -> Key a # Measured (Key a) (Elem a) Source # Instance detailsDefined in Data.OrdSeq Methodsmeasure :: Elem a -> Key a #

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

newtype Elem a Source #

Constructors

 Elem FieldsgetElem :: a
Instances
 Source # Instance detailsDefined in Data.OrdSeq Methodsfmap :: (a -> b) -> Elem a -> Elem b #(<$) :: a -> Elem b -> Elem a # Source # Instance detailsDefined in Data.OrdSeq Methodsfold :: 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 # Source # Instance detailsDefined in Data.OrdSeq Methodstraverse :: 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 detailsDefined in Data.OrdSeq Methods(==) :: Elem a -> Elem a -> Bool #(/=) :: Elem a -> Elem a -> Bool # Ord a => Ord (Elem a) Source # Instance detailsDefined in Data.OrdSeq Methodscompare :: 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 detailsDefined in Data.OrdSeq MethodsshowsPrec :: Int -> Elem a -> ShowS #show :: Elem a -> String #showList :: [Elem a] -> ShowS # Measured (Key a) (Elem a) Source # Instance detailsDefined in Data.OrdSeq Methodsmeasure :: Elem a -> Key a # newtype OrdSeq a Source # Constructors  OrdSeq Fields_asFingerTree :: FingerTree (Key a) (Elem a) Instances  Source # Instance detailsDefined in Data.OrdSeq Methodsfold :: 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 detailsDefined in Data.OrdSeq Methods(==) :: OrdSeq a -> OrdSeq a -> Bool #(/=) :: OrdSeq a -> OrdSeq a -> Bool # Show a => Show (OrdSeq a) Source # Instance detailsDefined in Data.OrdSeq MethodsshowsPrec :: Int -> OrdSeq a -> ShowS #show :: OrdSeq a -> String #showList :: [OrdSeq a] -> ShowS # Source # Instance detailsDefined 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 detailsDefined in Data.OrdSeq Methodsmappend :: OrdSeq a -> OrdSeq a -> OrdSeq a #mconcat :: [OrdSeq a] -> OrdSeq a # (Arbitrary a, Ord a) => Arbitrary (OrdSeq a) # Instance detailsDefined in Test.QuickCheck.HGeometryInstances Methodsarbitrary :: 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)

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