Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	GHC2021

HGeometry.Algorithms.LogarithmicMethod

Description

Synopsis

newtype InsertionOnly (static :: k -> Type) (a :: k) = InsertionOnly [Maybe (static a)]
empty :: forall {k} (static :: k -> Type) (a :: k). InsertionOnly static a
class LogarithmicMethodDS (static :: Type -> Type) a where
- singleton :: a -> static a
- build :: NonEmpty a -> static a
- merge :: static a -> static a -> static a
insert :: forall (static :: Type -> Type) a. LogarithmicMethodDS static a => a -> InsertionOnly static a -> InsertionOnly static a
queryWith :: forall {k} m static (a :: k). Monoid m => (static a -> m) -> InsertionOnly static a -> m

Documentation

newtype InsertionOnly (static :: k -> Type) (a :: k) Source #

Represents an insertion-only data structure built from static data structures.

In particular, we maintain $O(\log n)$ static data structures of sizes $2^i$, for $i \in [0..c\log n]$.

Constructors

InsertionOnly [Maybe (static a)]

Instances

Instances details

Functor static => Functor (InsertionOnly static) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods fmap :: (a -> b) -> InsertionOnly static a -> InsertionOnly static b # (<$) :: a -> InsertionOnly static b -> InsertionOnly static a #
Foldable static => Foldable (InsertionOnly static) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods fold :: Monoid m => InsertionOnly static m -> m # foldMap :: Monoid m => (a -> m) -> InsertionOnly static a -> m # foldMap' :: Monoid m => (a -> m) -> InsertionOnly static a -> m # foldr :: (a -> b -> b) -> b -> InsertionOnly static a -> b # foldr' :: (a -> b -> b) -> b -> InsertionOnly static a -> b # foldl :: (b -> a -> b) -> b -> InsertionOnly static a -> b # foldl' :: (b -> a -> b) -> b -> InsertionOnly static a -> b # foldr1 :: (a -> a -> a) -> InsertionOnly static a -> a # foldl1 :: (a -> a -> a) -> InsertionOnly static a -> a # toList :: InsertionOnly static a -> [a] # null :: InsertionOnly static a -> Bool # length :: InsertionOnly static a -> Int # elem :: Eq a => a -> InsertionOnly static a -> Bool # maximum :: Ord a => InsertionOnly static a -> a # minimum :: Ord a => InsertionOnly static a -> a # sum :: Num a => InsertionOnly static a -> a # product :: Num a => InsertionOnly static a -> a #
Traversable static => Traversable (InsertionOnly static) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods traverse :: Applicative f => (a -> f b) -> InsertionOnly static a -> f (InsertionOnly static b) # sequenceA :: Applicative f => InsertionOnly static (f a) -> f (InsertionOnly static a) # mapM :: Monad m => (a -> m b) -> InsertionOnly static a -> m (InsertionOnly static b) # sequence :: Monad m => InsertionOnly static (m a) -> m (InsertionOnly static a) #
LogarithmicMethodDS static a => Monoid (InsertionOnly static a) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods mempty :: InsertionOnly static a # mappend :: InsertionOnly static a -> InsertionOnly static a -> InsertionOnly static a # mconcat :: [InsertionOnly static a] -> InsertionOnly static a #
LogarithmicMethodDS static a => Semigroup (InsertionOnly static a) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods (<>) :: InsertionOnly static a -> InsertionOnly static a -> InsertionOnly static a # sconcat :: NonEmpty (InsertionOnly static a) -> InsertionOnly static a # stimes :: Integral b => b -> InsertionOnly static a -> InsertionOnly static a #
Show (static a) => Show (InsertionOnly static a) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods showsPrec :: Int -> InsertionOnly static a -> ShowS # show :: InsertionOnly static a -> String # showList :: [InsertionOnly static a] -> ShowS #
Eq (static a) => Eq (InsertionOnly static a) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods (==) :: InsertionOnly static a -> InsertionOnly static a -> Bool # (/=) :: InsertionOnly static a -> InsertionOnly static a -> Bool #
Ord (static a) => Ord (InsertionOnly static a) Source #
Instance details Defined in HGeometry.Algorithms.LogarithmicMethod Methods compare :: InsertionOnly static a -> InsertionOnly static a -> Ordering # (<) :: InsertionOnly static a -> InsertionOnly static a -> Bool # (<=) :: InsertionOnly static a -> InsertionOnly static a -> Bool # (>) :: InsertionOnly static a -> InsertionOnly static a -> Bool # (>=) :: InsertionOnly static a -> InsertionOnly static a -> Bool # max :: InsertionOnly static a -> InsertionOnly static a -> InsertionOnly static a # min :: InsertionOnly static a -> InsertionOnly static a -> InsertionOnly static a #

empty :: forall {k} (static :: k -> Type) (a :: k). InsertionOnly static a Source #

Builds an empty structure

class LogarithmicMethodDS (static :: Type -> Type) a where Source #

Class representing data structures that can be constructed using the Logarithmic method.

Minimal complete definition

build

Methods

singleton :: a -> static a Source #

Create a new static data structure storing only one value.

build :: NonEmpty a -> static a Source #

Given a NonEmpty list of a's build a static a.

merge :: static a -> static a -> static a Source #

Merges two structurs of the same size. Has a default implementation via build in case the static structure is Foldable1.

default merge :: Foldable1 static => static a -> static a -> static a Source #

insert :: forall (static :: Type -> Type) a. LogarithmicMethodDS static a => a -> InsertionOnly static a -> InsertionOnly static a Source #

Inserts an element into the data structure

running time: $O(M(n)\log n / n)$, where $M(n)$ is the time required to merge two data structures of size $n$.

queryWith :: forall {k} m static (a :: k). Monoid m => (static a -> m) -> InsertionOnly static a -> m Source #

Given a decomposable query algorithm for the static structure, lift it to a query algorithm on the insertion only structure.

pre: (As indicated by the Monoid constraint), the query answer should be decomposable. I.e. we should be able to anser the query on a set $A \cup B$ by answering the query on $A$ and $B$ separately, and combining their results.

running time: $O(Q(n)\log n)$, where $Q(n)$ is the query time on the static structure.