Algorithms.LogarithmicMethod

Documentation

newtype InsertionOnly static a

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

Functor static => Functor (InsertionOnly static)

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)

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)

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)

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)

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)

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)

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)

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

Builds an empty structure

class LogarithmicMethodDS static a where

Minimal complete definition

build

Methods

singleton :: a -> static a

Create a new static data structure storing only one value.

build :: NonEmpty a -> static a

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

merge :: static a -> static a -> static a

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

insert :: LogarithmicMethodDS static a => a -> InsertionOnly static a -> InsertionOnly static a

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

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.