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

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.SegmentTree.Generic

Description

Description : Implementation of SegmentTrees

Synopsis

Documentation

data NodeData v r Source #

Internal nodes store a split point, the range, and an associated data structure

Constructors

NodeData 

Fields

Instances
Functor (NodeData v) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

fmap :: (a -> b) -> NodeData v a -> NodeData v b #

(<$) :: a -> NodeData v b -> NodeData v a #

(Eq r, Eq v) => Eq (NodeData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: NodeData v r -> NodeData v r -> Bool #

(/=) :: NodeData v r -> NodeData v r -> Bool #

(Show r, Show v) => Show (NodeData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> NodeData v r -> ShowS #

show :: NodeData v r -> String #

showList :: [NodeData v r] -> ShowS #

Generic (NodeData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Associated Types

type Rep (NodeData v r) :: Type -> Type #

Methods

from :: NodeData v r -> Rep (NodeData v r) x #

to :: Rep (NodeData v r) x -> NodeData v r #

(NFData v, NFData r) => NFData (NodeData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: NodeData v r -> () #

type Rep (NodeData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type Rep (NodeData v r) = D1 (MetaData "NodeData" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" False) (C1 (MetaCons "NodeData" PrefixI True) (S1 (MetaSel (Just "_splitPoint") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (EndPoint r)) :*: (S1 (MetaSel (Just "_range") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Range r)) :*: S1 (MetaSel (Just "_assoc") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 v))))

splitPoint :: forall v r. Lens' (NodeData v r) (EndPoint r) Source #

range :: forall v r. Lens' (NodeData v r) (Range r) Source #

assoc :: forall v r v. Lens (NodeData v r) (NodeData v r) v v Source #

data LeafData v r Source #

Leaf nodes store an atomic range, and an associated data structure.

Constructors

LeafData 

Fields

Instances
Functor (LeafData v) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

fmap :: (a -> b) -> LeafData v a -> LeafData v b #

(<$) :: a -> LeafData v b -> LeafData v a #

(Eq r, Eq v) => Eq (LeafData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: LeafData v r -> LeafData v r -> Bool #

(/=) :: LeafData v r -> LeafData v r -> Bool #

(Show r, Show v) => Show (LeafData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> LeafData v r -> ShowS #

show :: LeafData v r -> String #

showList :: [LeafData v r] -> ShowS #

Generic (LeafData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Associated Types

type Rep (LeafData v r) :: Type -> Type #

Methods

from :: LeafData v r -> Rep (LeafData v r) x #

to :: Rep (LeafData v r) x -> LeafData v r #

(NFData v, NFData r) => NFData (LeafData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: LeafData v r -> () #

type Rep (LeafData v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type Rep (LeafData v r)

atomicRange :: forall v r r. Lens (LeafData v r) (LeafData v r) (AtomicRange r) (AtomicRange r) Source #

leafAssoc :: forall v r v. Lens (LeafData v r) (LeafData v r) v v Source #

newtype SegmentTree v r Source #

Segment tree on a Fixed set of endpoints

Constructors

SegmentTree 
Instances
(Eq r, Eq v) => Eq (SegmentTree v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: SegmentTree v r -> SegmentTree v r -> Bool #

(/=) :: SegmentTree v r -> SegmentTree v r -> Bool #

(Show r, Show v) => Show (SegmentTree v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> SegmentTree v r -> ShowS #

show :: SegmentTree v r -> String #

showList :: [SegmentTree v r] -> ShowS #

Generic (SegmentTree v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Associated Types

type Rep (SegmentTree v r) :: Type -> Type #

Methods

from :: SegmentTree v r -> Rep (SegmentTree v r) x #

to :: Rep (SegmentTree v r) x -> SegmentTree v r #

(NFData v, NFData r) => NFData (SegmentTree v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: SegmentTree v r -> () #

type Rep (SegmentTree v r) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type Rep (SegmentTree v r) = D1 (MetaData "SegmentTree" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "SegmentTree" PrefixI True) (S1 (MetaSel (Just "_unSegmentTree") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree (NodeData v r) (LeafData v r)))))

unSegmentTree :: forall v r v r. Iso (SegmentTree v r) (SegmentTree v r) (BinLeafTree (NodeData v r) (LeafData v r)) (BinLeafTree (NodeData v r) (LeafData v r)) Source #

class Measured v i => Assoc v i where Source #

Class for associcated data structures

Methods

insertAssoc :: i -> v -> v Source #

deleteAssoc :: i -> v -> v Source #

Instances
Eq a => Assoc [I a] (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

insertAssoc :: I a -> [I a] -> [I a] Source #

deleteAssoc :: I a -> [I a] -> [I a] Source #

createTree :: NonEmpty r -> v -> SegmentTree v r Source #

Given a sorted list of endpoints, without duplicates, construct a segment tree

\(O(n)\) time

fromIntervals :: (Ord r, Eq p, Assoc v i, IntervalLike i, Monoid v, NumType i ~ r) => (Interval p r -> i) -> NonEmpty (Interval p r) -> SegmentTree v r Source #

Build a SegmentTree

\(O(n \log n)\)

insert :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r Source #

Pre: the interval should have one of the endpoints on which the tree is built.

delete :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r Source #

Delete an interval from the tree

pre: The segment is in the tree!

search :: (Ord r, Monoid v) => r -> SegmentTree v r -> v Source #

Search for all intervals intersecting x

\(O(\log n + k)\) where \(k\) is the output size

stab :: Ord r => r -> SegmentTree v r -> [v] Source #

Returns the associated values of the nodes on the search path to x

\(O(\log n)\)

newtype I a Source #

Interval

Constructors

I 

Fields

Instances
Eq a => Eq (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: I a -> I a -> Bool #

(/=) :: I a -> I a -> Bool #

Ord a => Ord (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

compare :: I a -> I a -> Ordering #

(<) :: I a -> I a -> Bool #

(<=) :: I a -> I a -> Bool #

(>) :: I a -> I a -> Bool #

(>=) :: I a -> I a -> Bool #

max :: I a -> I a -> I a #

min :: I a -> I a -> I a #

Read a => Read (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

readsPrec :: Int -> ReadS (I a) #

readList :: ReadS [I a] #

readPrec :: ReadPrec (I a) #

readListPrec :: ReadPrec [I a] #

Show a => Show (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> I a -> ShowS #

show :: I a -> String #

showList :: [I a] -> ShowS #

Generic (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Associated Types

type Rep (I a) :: Type -> Type #

Methods

from :: I a -> Rep (I a) x #

to :: Rep (I a) x -> I a #

NFData a => NFData (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: I a -> () #

IntervalLike a => IntervalLike (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

toRange :: I a -> Range (NumType (I a)) Source #

Measured [I a] (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

measure :: I a -> [I a] Source #

Eq a => Assoc [I a] (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

insertAssoc :: I a -> [I a] -> [I a] Source #

deleteAssoc :: I a -> [I a] -> [I a] Source #

type Rep (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type Rep (I a) = D1 (MetaData "I" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "I" PrefixI True) (S1 (MetaSel (Just "_unI") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))
type NumType (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type NumType (I a) = NumType a

newtype Count Source #

Constructors

Count 

Fields

Instances
Enum Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Eq Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: Count -> Count -> Bool #

(/=) :: Count -> Count -> Bool #

Integral Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Num Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Ord Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

compare :: Count -> Count -> Ordering #

(<) :: Count -> Count -> Bool #

(<=) :: Count -> Count -> Bool #

(>) :: Count -> Count -> Bool #

(>=) :: Count -> Count -> Bool #

max :: Count -> Count -> Count #

min :: Count -> Count -> Count #

Real Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

toRational :: Count -> Rational #

Show Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> Count -> ShowS #

show :: Count -> String #

showList :: [Count] -> ShowS #

Generic Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Associated Types

type Rep Count :: Type -> Type #

Methods

from :: Count -> Rep Count x #

to :: Rep Count x -> Count #

Semigroup Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

(<>) :: Count -> Count -> Count #

sconcat :: NonEmpty Count -> Count #

stimes :: Integral b => b -> Count -> Count #

Monoid Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

mempty :: Count #

mappend :: Count -> Count -> Count #

mconcat :: [Count] -> Count #

NFData Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: Count -> () #

type Rep Count Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

type Rep Count = D1 (MetaData "Count" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "Count" PrefixI True) (S1 (MetaSel (Just "getCount") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word)))