hgeometry-combinatorial-0.14: Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.LogarithmicMethod

Description

 
Synopsis

Documentation

newtype InsertionOnly static a 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 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 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 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) #

Eq (static a) => Eq (InsertionOnly static a) Source # 
Instance details

Defined in 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 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 #

Show (static a) => Show (InsertionOnly static a) Source # 
Instance details

Defined in Algorithms.LogarithmicMethod

Methods

showsPrec :: Int -> InsertionOnly static a -> ShowS #

show :: InsertionOnly static a -> String #

showList :: [InsertionOnly static a] -> ShowS #

LogarithmicMethodDS static a => Semigroup (InsertionOnly static a) Source # 
Instance details

Defined in 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 #

LogarithmicMethodDS static a => Monoid (InsertionOnly static a) Source # 
Instance details

Defined in Algorithms.LogarithmicMethod

Methods

mempty :: InsertionOnly static a #

mappend :: InsertionOnly static a -> InsertionOnly static a -> InsertionOnly static a #

mconcat :: [InsertionOnly static a] -> InsertionOnly static a #

empty :: InsertionOnly static a Source #

Builds an empty structure

class LogarithmicMethodDS static a where Source #

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 :: 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 :: 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.