HaskellWorks.Data.SegmentSet.Strict

SegmentSet provides an efficient implementation of a set of segments (a.k.a intervals). Segments in the set are non-overlapping. Adjacent segments are merged (i.e. (a .. b), (b + 1 .. c) -> (a .. c)).

Segment sets are implemented using the FingerTree type, following section 4.8 of

• Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programmaxg 16:2 (2006) pp 197-217. http://staff.city.ac.uk/~ross/papers/FingerTree.html

An amortized running time is given for each operation, with n referring to the size of the set. These bounds hold even in a persistent (shared) setting.

Note: Many of these operations have the same names as similar operations on lists in the Prelude. The ambiguity may be resolved using either qualification or the hiding clause.

Segments

data Segment k

A closed segment. The lower bound should be less than or equal to the higher bound.

Constructors

Segment

Fields

• low :: !k
• high :: !k

Instances

Monoid k => Measured k (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Methods

measure :: Segment k -> k

Eq k => Eq (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Methods

(==) :: Segment k -> Segment k -> Bool

(/=) :: Segment k -> Segment k -> Bool

Ord k => Ord (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Methods

compare :: Segment k -> Segment k -> Ordering

(<) :: Segment k -> Segment k -> Bool

(<=) :: Segment k -> Segment k -> Bool

(>) :: Segment k -> Segment k -> Bool

(>=) :: Segment k -> Segment k -> Bool

max :: Segment k -> Segment k -> Segment k

min :: Segment k -> Segment k -> Segment k

Show k => Show (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Methods

showsPrec :: Int -> Segment k -> ShowS

show :: Segment k -> String

showList :: [Segment k] -> ShowS

Generic (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Associated Types

type Rep (Segment k) :: Type -> Type

Methods

from :: Segment k -> Rep (Segment k) x

to :: Rep (Segment k) x -> Segment k

NFData k => NFData (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

Methods

rnf :: Segment k -> ()

type Rep (Segment k)

Defined in HaskellWorks.Data.Segment.Strict

type Rep (Segment k) = D1 (MetaData "Segment" "HaskellWorks.Data.Segment.Strict" "hw-fingertree-strict-0.1.1.3-EgbVhr6i12l2vYC8XWLWwK" False) (C1 (MetaCons "Segment" PrefixI True) (S1 (MetaSel (Just "low") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 k) :*: S1 (MetaSel (Just "high") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 k)))

point :: k -> Segment k

A segment in which the lower and upper bounds are equal.

Segment maps

newtype SegmentSet k

Constructors

SegmentSet (OrderedMap (Max k) (Segment k))

Instances

Show k => Show (SegmentSet k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

showsPrec :: Int -> SegmentSet k -> ShowS

show :: SegmentSet k -> String

showList :: [SegmentSet k] -> ShowS

Generic (SegmentSet k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Associated Types

type Rep (SegmentSet k) :: Type -> Type

Methods

from :: SegmentSet k -> Rep (SegmentSet k) x

to :: Rep (SegmentSet k) x -> SegmentSet k

NFData k => NFData (SegmentSet k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

rnf :: SegmentSet k -> ()

type Rep (SegmentSet k)

Defined in HaskellWorks.Data.SegmentSet.Strict

type Rep (SegmentSet k) = D1 (MetaData "SegmentSet" "HaskellWorks.Data.SegmentSet.Strict" "hw-fingertree-strict-0.1.1.3-EgbVhr6i12l2vYC8XWLWwK" True) (C1 (MetaCons "SegmentSet" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (OrderedMap (Max k) (Segment k)))))

newtype OrderedMap k a

Map of closed segments, possibly with duplicates. The Foldable and Traversable instances process the segments in lexicographical order.

Constructors

OrderedMap (FingerTree k (Item k a))

Instances

Functor (OrderedMap k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

fmap :: (a -> b) -> OrderedMap k a -> OrderedMap k b

(<$) :: a -> OrderedMap k b -> OrderedMap k a

Foldable (OrderedMap k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

fold :: Monoid m => OrderedMap k m -> m

foldMap :: Monoid m => (a -> m) -> OrderedMap k a -> m

foldr :: (a -> b -> b) -> b -> OrderedMap k a -> b

foldr' :: (a -> b -> b) -> b -> OrderedMap k a -> b

foldl :: (b -> a -> b) -> b -> OrderedMap k a -> b

foldl' :: (b -> a -> b) -> b -> OrderedMap k a -> b

foldr1 :: (a -> a -> a) -> OrderedMap k a -> a

foldl1 :: (a -> a -> a) -> OrderedMap k a -> a

toList :: OrderedMap k a -> [a]

null :: OrderedMap k a -> Bool

length :: OrderedMap k a -> Int

elem :: Eq a => a -> OrderedMap k a -> Bool

maximum :: Ord a => OrderedMap k a -> a

minimum :: Ord a => OrderedMap k a -> a

sum :: Num a => OrderedMap k a -> a

product :: Num a => OrderedMap k a -> a

Traversable (OrderedMap k)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

traverse :: Applicative f => (a -> f b) -> OrderedMap k a -> f (OrderedMap k b)

sequenceA :: Applicative f => OrderedMap k (f a) -> f (OrderedMap k a)

mapM :: Monad m => (a -> m b) -> OrderedMap k a -> m (OrderedMap k b)

sequence :: Monad m => OrderedMap k (m a) -> m (OrderedMap k a)

(Show k, Show a) => Show (OrderedMap k a)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

showsPrec :: Int -> OrderedMap k a -> ShowS

show :: OrderedMap k a -> String

showList :: [OrderedMap k a] -> ShowS

Generic (OrderedMap k a)

Defined in HaskellWorks.Data.SegmentSet.Strict

Associated Types

type Rep (OrderedMap k a) :: Type -> Type

Methods

from :: OrderedMap k a -> Rep (OrderedMap k a) x

to :: Rep (OrderedMap k a) x -> OrderedMap k a

(NFData k, NFData a) => NFData (OrderedMap k a)

Defined in HaskellWorks.Data.SegmentSet.Strict

Methods

rnf :: OrderedMap k a -> ()

type Rep (OrderedMap k a)

Defined in HaskellWorks.Data.SegmentSet.Strict

type Rep (OrderedMap k a) = D1 (MetaData "OrderedMap" "HaskellWorks.Data.SegmentSet.Strict" "hw-fingertree-strict-0.1.1.3-EgbVhr6i12l2vYC8XWLWwK" True) (C1 (MetaCons "OrderedMap" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (FingerTree k (Item k a)))))

delete :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k

O(log(n)). Remove a segment from the set. Alias of update.

empty :: SegmentSet k

O(1). The empty segment set.

fromList :: (Ord v, Enum v, Bounded v, Show v) => [Segment v] -> SegmentSet v

insert :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k

O(log(n)). Insert a segment into the set. Alias of update.

singleton :: Segment k -> SegmentSet k

O(1). Segment set with a single entry.

update :: forall k a. (Ord k, Enum k, Bounded k, Show k) => Segment k -> Bool -> SegmentSet k -> SegmentSet k

Update a segment set. Prefer insert or delete in most cases.

segmentSetToList :: SegmentSet k -> [Segment k]

data Item k a

Constructors

Item !k !a

Instances

Monoid k => Measured k (Item k a)

Defined in HaskellWorks.Data.Item.Strict

Methods

measure :: Item k a -> k

Functor (Item k)

Defined in HaskellWorks.Data.Item.Strict

Methods

fmap :: (a -> b) -> Item k a -> Item k b

(<$) :: a -> Item k b -> Item k a

Foldable (Item k)

Defined in HaskellWorks.Data.Item.Strict

Methods

fold :: Monoid m => Item k m -> m

foldMap :: Monoid m => (a -> m) -> Item k a -> m

foldr :: (a -> b -> b) -> b -> Item k a -> b

foldr' :: (a -> b -> b) -> b -> Item k a -> b

foldl :: (b -> a -> b) -> b -> Item k a -> b

foldl' :: (b -> a -> b) -> b -> Item k a -> b

foldr1 :: (a -> a -> a) -> Item k a -> a

foldl1 :: (a -> a -> a) -> Item k a -> a

toList :: Item k a -> [a]

null :: Item k a -> Bool

length :: Item k a -> Int

elem :: Eq a => a -> Item k a -> Bool

maximum :: Ord a => Item k a -> a

minimum :: Ord a => Item k a -> a

sum :: Num a => Item k a -> a

product :: Num a => Item k a -> a

Traversable (Item k)

Defined in HaskellWorks.Data.Item.Strict

Methods

traverse :: Applicative f => (a -> f b) -> Item k a -> f (Item k b)

sequenceA :: Applicative f => Item k (f a) -> f (Item k a)

mapM :: Monad m => (a -> m b) -> Item k a -> m (Item k b)

sequence :: Monad m => Item k (m a) -> m (Item k a)

(Eq k, Eq a) => Eq (Item k a)

Defined in HaskellWorks.Data.Item.Strict

Methods

(==) :: Item k a -> Item k a -> Bool

(/=) :: Item k a -> Item k a -> Bool

(Show k, Show a) => Show (Item k a)

Defined in HaskellWorks.Data.Item.Strict

Methods

showsPrec :: Int -> Item k a -> ShowS

show :: Item k a -> String

showList :: [Item k a] -> ShowS

Generic (Item k a)

Defined in HaskellWorks.Data.Item.Strict

Associated Types

type Rep (Item k a) :: Type -> Type

Methods

from :: Item k a -> Rep (Item k a) x

to :: Rep (Item k a) x -> Item k a

(NFData k, NFData a) => NFData (Item k a)

Defined in HaskellWorks.Data.Item.Strict

Methods

rnf :: Item k a -> ()

type Rep (Item k a)

Defined in HaskellWorks.Data.Item.Strict

type Rep (Item k a) = D1 (MetaData "Item" "HaskellWorks.Data.Item.Strict" "hw-fingertree-strict-0.1.1.3-EgbVhr6i12l2vYC8XWLWwK" False) (C1 (MetaCons "Item" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 k) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a)))

cappedL :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> (FingerTree (Max k) (Item (Max k) (Segment k)), FingerTree (Max k) (Item (Max k) (Segment k)))

cappedM :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> FingerTree (Max k) (Item (Max k) (Segment k))