{-# LANGUAGE DefaultSignatures #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  HGeometry.Algorithms.LogarithmicMethod
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--------------------------------------------------------------------------------
module HGeometry.Algorithms.LogarithmicMethod
  ( InsertionOnly(..)
  , empty
  , LogarithmicMethodDS(..)
  , insert
  , queryWith
  )
  where

import Data.List.NonEmpty (NonEmpty(..))
import Data.Maybe (mapMaybe)
import Data.Foldable1

--------------------------------------------------------------------------------

-- | 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]\).
newtype InsertionOnly static a = InsertionOnly [Maybe (static a)]
  deriving (Int -> InsertionOnly static a -> ShowS
[InsertionOnly static a] -> ShowS
InsertionOnly static a -> String
(Int -> InsertionOnly static a -> ShowS)
-> (InsertionOnly static a -> String)
-> ([InsertionOnly static a] -> ShowS)
-> Show (InsertionOnly static a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k (static :: k -> *) (a :: k).
Show (static a) =>
Int -> InsertionOnly static a -> ShowS
forall k (static :: k -> *) (a :: k).
Show (static a) =>
[InsertionOnly static a] -> ShowS
forall k (static :: k -> *) (a :: k).
Show (static a) =>
InsertionOnly static a -> String
$cshowsPrec :: forall k (static :: k -> *) (a :: k).
Show (static a) =>
Int -> InsertionOnly static a -> ShowS
showsPrec :: Int -> InsertionOnly static a -> ShowS
$cshow :: forall k (static :: k -> *) (a :: k).
Show (static a) =>
InsertionOnly static a -> String
show :: InsertionOnly static a -> String
$cshowList :: forall k (static :: k -> *) (a :: k).
Show (static a) =>
[InsertionOnly static a] -> ShowS
showList :: [InsertionOnly static a] -> ShowS
Show,InsertionOnly static a -> InsertionOnly static a -> Bool
(InsertionOnly static a -> InsertionOnly static a -> Bool)
-> (InsertionOnly static a -> InsertionOnly static a -> Bool)
-> Eq (InsertionOnly static a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (static :: k -> *) (a :: k).
Eq (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
$c== :: forall k (static :: k -> *) (a :: k).
Eq (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
== :: InsertionOnly static a -> InsertionOnly static a -> Bool
$c/= :: forall k (static :: k -> *) (a :: k).
Eq (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
/= :: InsertionOnly static a -> InsertionOnly static a -> Bool
Eq,Eq (InsertionOnly static a)
Eq (InsertionOnly static a) =>
(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)
-> (InsertionOnly static a
    -> InsertionOnly static a -> InsertionOnly static a)
-> (InsertionOnly static a
    -> InsertionOnly static a -> InsertionOnly static a)
-> Ord (InsertionOnly static a)
InsertionOnly static a -> InsertionOnly static a -> Bool
InsertionOnly static a -> InsertionOnly static a -> Ordering
InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k (static :: k -> *) (a :: k).
Ord (static a) =>
Eq (InsertionOnly static a)
forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Ordering
forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
$ccompare :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Ordering
compare :: InsertionOnly static a -> InsertionOnly static a -> Ordering
$c< :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
< :: InsertionOnly static a -> InsertionOnly static a -> Bool
$c<= :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
<= :: InsertionOnly static a -> InsertionOnly static a -> Bool
$c> :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
> :: InsertionOnly static a -> InsertionOnly static a -> Bool
$c>= :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a -> InsertionOnly static a -> Bool
>= :: InsertionOnly static a -> InsertionOnly static a -> Bool
$cmax :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
max :: InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
$cmin :: forall k (static :: k -> *) (a :: k).
Ord (static a) =>
InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
min :: InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
Ord)

-- | Builds an empty structure
empty :: InsertionOnly static a
empty :: forall {k} (static :: k -> *) (a :: k). InsertionOnly static a
empty = [Maybe (static a)] -> InsertionOnly static a
forall {k} (static :: k -> *) (a :: k).
[Maybe (static a)] -> InsertionOnly static a
InsertionOnly []

instance Functor static => Functor (InsertionOnly static) where
  fmap :: forall a b.
(a -> b) -> InsertionOnly static a -> InsertionOnly static b
fmap a -> b
f (InsertionOnly [Maybe (static a)]
dss) = [Maybe (static b)] -> InsertionOnly static b
forall {k} (static :: k -> *) (a :: k).
[Maybe (static a)] -> InsertionOnly static a
InsertionOnly ([Maybe (static b)] -> InsertionOnly static b)
-> [Maybe (static b)] -> InsertionOnly static b
forall a b. (a -> b) -> a -> b
$ (Maybe (static a) -> Maybe (static b))
-> [Maybe (static a)] -> [Maybe (static b)]
forall a b. (a -> b) -> [a] -> [b]
map ((static a -> static b) -> Maybe (static a) -> Maybe (static b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> static a -> static b
forall a b. (a -> b) -> static a -> static b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f)) [Maybe (static a)]
dss

instance Traversable static => Traversable (InsertionOnly static) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> InsertionOnly static a -> f (InsertionOnly static b)
traverse a -> f b
f (InsertionOnly [Maybe (static a)]
dss) = [Maybe (static b)] -> InsertionOnly static b
forall {k} (static :: k -> *) (a :: k).
[Maybe (static a)] -> InsertionOnly static a
InsertionOnly ([Maybe (static b)] -> InsertionOnly static b)
-> f [Maybe (static b)] -> f (InsertionOnly static b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Maybe (static a) -> f (Maybe (static b)))
-> [Maybe (static a)] -> f [Maybe (static b)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse ((static a -> f (static b))
-> Maybe (static a) -> f (Maybe (static b))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse ((a -> f b) -> static a -> f (static b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> static a -> f (static b)
traverse a -> f b
f)) [Maybe (static a)]
dss

instance Foldable static => Foldable (InsertionOnly static) where
  foldMap :: forall m a. Monoid m => (a -> m) -> InsertionOnly static a -> m
foldMap a -> m
f = (static a -> m) -> InsertionOnly static a -> m
forall {k} m (static :: k -> *) (a :: k).
Monoid m =>
(static a -> m) -> InsertionOnly static a -> m
queryWith ((a -> m) -> static a -> m
forall m a. Monoid m => (a -> m) -> static a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f)
  length :: forall a. InsertionOnly static a -> Int
length = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ([Int] -> Int)
-> (InsertionOnly static a -> [Int])
-> InsertionOnly static a
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, Maybe (static a)) -> Maybe Int)
-> [(Int, Maybe (static a))] -> [Int]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe ((Int -> Maybe (static a) -> Maybe Int)
-> (Int, Maybe (static a)) -> Maybe Int
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> Maybe (static a) -> Maybe Int
forall a b. a -> Maybe b -> Maybe a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
(<$)) ([(Int, Maybe (static a))] -> [Int])
-> (InsertionOnly static a -> [(Int, Maybe (static a))])
-> InsertionOnly static a
-> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InsertionOnly static a -> [(Int, Maybe (static a))]
forall {k} i (static :: k -> *) (a :: k).
Integral i =>
InsertionOnly static a -> [(i, Maybe (static a))]
withSizes

instance LogarithmicMethodDS static a => Semigroup (InsertionOnly static a) where
  (InsertionOnly [Maybe (static a)]
ds1) <> :: InsertionOnly static a
-> InsertionOnly static a -> InsertionOnly static a
<> (InsertionOnly [Maybe (static a)]
ds2) = [Maybe (static a)] -> InsertionOnly static a
forall {k} (static :: k -> *) (a :: k).
[Maybe (static a)] -> InsertionOnly static a
InsertionOnly ([Maybe (static a)] -> InsertionOnly static a)
-> [Maybe (static a)] -> InsertionOnly static a
forall a b. (a -> b) -> a -> b
$ Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1 Power
0 [Maybe (static a)]
ds2 Power
0

instance LogarithmicMethodDS static a => Monoid (InsertionOnly static a) where
  mempty :: InsertionOnly static a
mempty = InsertionOnly static a
forall {k} (static :: k -> *) (a :: k). InsertionOnly static a
empty


-- | Class representing data structures that can be constructed using
-- the Logarithmic method.
class LogarithmicMethodDS static a where
  {-# MINIMAL build #-}
  -- | Create a new static data structure storing only one value.
  singleton :: a          -> static a
  singleton = NonEmpty a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
NonEmpty a -> static a
build (NonEmpty a -> static a) -> (a -> NonEmpty a) -> a -> static a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [])

  -- | Given a NonEmpty list of a's build a static a.
  build     :: NonEmpty a -> static a

  -- | Merges two structurs of the same size. Has a default
  -- implementation via build in case the static structure is Foldable1.
  merge     :: static a   -> static a -> static a
  default merge :: Foldable1 static => static a -> static a -> static a
  merge static a
as static a
bs = NonEmpty a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
NonEmpty a -> static a
build (NonEmpty a -> static a) -> NonEmpty a -> static a
forall a b. (a -> b) -> a -> b
$ static a -> NonEmpty a
forall a. static a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
toNonEmpty static a
as NonEmpty a -> NonEmpty a -> NonEmpty a
forall a. Semigroup a => a -> a -> a
<> static a -> NonEmpty a
forall a. static a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
toNonEmpty static a
bs


type Power = Word

-- | 2^h, for whatever value h.
pow2   :: Integral i => Power -> i
pow2 :: forall i. Integral i => Power -> i
pow2 Power
h = i
2 i -> Power -> i
forall a b. (Num a, Integral b) => a -> b -> a
^ Power
h

-- | Annotate the data structures with their sizes
withSizes                     :: Integral i => InsertionOnly static a -> [(i,Maybe (static a))]
withSizes :: forall {k} i (static :: k -> *) (a :: k).
Integral i =>
InsertionOnly static a -> [(i, Maybe (static a))]
withSizes (InsertionOnly [Maybe (static a)]
dss) = (Power -> Maybe (static a) -> (i, Maybe (static a)))
-> [Power] -> [Maybe (static a)] -> [(i, Maybe (static a))]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\Power
i Maybe (static a)
ds -> (Power -> i
forall i. Integral i => Power -> i
pow2 Power
i,Maybe (static a)
ds))  [Power
0..] [Maybe (static a)]
dss

-- | 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\).
insert                       :: LogarithmicMethodDS static a
                             => a -> InsertionOnly static a -> InsertionOnly static a
insert :: forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
a -> InsertionOnly static a -> InsertionOnly static a
insert a
x (InsertionOnly [Maybe (static a)]
dss) = [Maybe (static a)] -> InsertionOnly static a
forall {k} (static :: k -> *) (a :: k).
[Maybe (static a)] -> InsertionOnly static a
InsertionOnly ([Maybe (static a)] -> InsertionOnly static a)
-> [Maybe (static a)] -> InsertionOnly static a
forall a b. (a -> b) -> a -> b
$ static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
runMerge (a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
a -> static a
singleton a
x) Power
0 Power
0 [Maybe (static a)]
dss

-- | Runs the merging procedure. If there are two data structures of
-- the same size they are merged.
runMerge         :: LogarithmicMethodDS static a
                 => static a -- ^ ds1
                 -> Power    -- ^ ds1 has size 2^i
                 -> Power    -- ^ the first entry in the next list corresponds to size 2^j
                 -> [Maybe (static a)] -> [Maybe (static a)]
runMerge :: forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
runMerge static a
ds1 Power
i Power
j = \case
  []                                -> [static a -> Maybe (static a)
forall a. a -> Maybe a
Just static a
ds1]
  dss :: [Maybe (static a)]
dss@(Maybe (static a)
Nothing  : [Maybe (static a)]
dss') | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> static a -> Maybe (static a)
forall a. a -> Maybe a
Just static a
ds1 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: [Maybe (static a)]
dss' -- replace
                        | Bool
otherwise -> static a -> Maybe (static a)
forall a. a -> Maybe a
Just static a
ds1 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: [Maybe (static a)]
dss  -- cons
  dss :: [Maybe (static a)]
dss@(Just static a
ds2 : [Maybe (static a)]
dss') | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> Maybe (static a)
forall a. Maybe a
Nothing Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
runMerge (static a
ds1 static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
ds2) (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
dss'
                        | Bool
otherwise -> static a -> Maybe (static a)
forall a. a -> Maybe a
Just static a
ds1 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: [Maybe (static a)]
dss -- cons -- I don't think insert can ever
                                                              -- trigger this scenario.

-- | merges two structures (potentially with a carry)
--
-- invariant: size carry == size ds1 <= size ds2
runMergeWith                ::  LogarithmicMethodDS static a
                            => Maybe (static a) -- ^ carry, if it exists
                            -> [Maybe (static a)] -> Power
                            -- ^ size of the first ds
                            -> [Maybe (static a)] -> Power
                            -- ^ size of the second ds
                            -> [Maybe (static a)]
runMergeWith :: forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
mc [Maybe (static a)]
ds1 Power
i [Maybe (static a)]
ds2 Power
j = case ([Maybe (static a)]
ds1,[Maybe (static a)]
ds2) of
  ([],[Maybe (static a)]
_)            -> case Maybe (static a)
mc of
                         Maybe (static a)
Nothing  -> [Maybe (static a)]
ds2
                         Just static a
c   -> static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
runMerge static a
c Power
i Power
j [Maybe (static a)]
ds2
  ([Maybe (static a)]
_,[])            -> case Maybe (static a)
mc of
                         Maybe (static a)
Nothing  -> [Maybe (static a)]
ds1
                         Just static a
c   -> static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a
-> Power -> Power -> [Maybe (static a)] -> [Maybe (static a)]
runMerge static a
c Power
i Power
i [Maybe (static a)]
ds1
  (Maybe (static a)
m1:[Maybe (static a)]
ds1',Maybe (static a)
m2:[Maybe (static a)]
ds2') -> case (Maybe (static a)
m1,Maybe (static a)
m2) of
    (Maybe (static a)
Nothing,Maybe (static a)
Nothing) -> Maybe (static a)
mc Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
    (Maybe (static a)
Nothing,Just static a
d2) -> case Maybe (static a)
mc of
         Maybe (static a)
Nothing | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> Maybe (static a)
m2 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
                 | Bool
otherwise -> Maybe (static a)
m1 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2 Power
j
         Just static a
c  | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> Maybe (static a)
forall a. Maybe a
Nothing Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith (static a -> Maybe (static a)
forall a. a -> Maybe a
Just (static a -> Maybe (static a)) -> static a -> Maybe (static a)
forall a b. (a -> b) -> a -> b
$ static a
c static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
d2) [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
                 | Bool
otherwise -> Maybe (static a)
mc Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2 Power
j
                   -- i < j, so invariant (i+1) <= j again holds holds

    (Just static a
d1,Maybe (static a)
Nothing) -> case Maybe (static a)
mc of
                           Maybe (static a)
Nothing -> Maybe (static a)
m1 Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
                           Just static a
c  -> Maybe (static a)
forall a. Maybe a
Nothing Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith (static a -> Maybe (static a)
forall a. a -> Maybe a
Just (static a -> Maybe (static a)) -> static a -> Maybe (static a)
forall a b. (a -> b) -> a -> b
$ static a
c static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
d1) [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)

    (Just static a
d1,Just static a
d2) -> case Maybe (static a)
mc of
         Maybe (static a)
Nothing | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> Maybe (static a)
forall a. Maybe a
Nothing Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith (static a -> Maybe (static a)
forall a. a -> Maybe a
Just (static a -> Maybe (static a)) -> static a -> Maybe (static a)
forall a b. (a -> b) -> a -> b
$ static a
d1 static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
d2) [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
                 | Bool
otherwise -> Maybe (static a)
m1      Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith Maybe (static a)
forall a. Maybe a
Nothing [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2 Power
j

         Just static a
c  | Power
i Power -> Power -> Bool
forall a. Eq a => a -> a -> Bool
== Power
j    -> Maybe (static a)
mc Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith (static a -> Maybe (static a)
forall a. a -> Maybe a
Just (static a -> Maybe (static a)) -> static a -> Maybe (static a)
forall a b. (a -> b) -> a -> b
$ static a
d1 static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
d2) [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2' (Power
jPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1)
                 | Bool
otherwise -> Maybe (static a)
forall a. Maybe a
Nothing Maybe (static a) -> [Maybe (static a)] -> [Maybe (static a)]
forall a. a -> [a] -> [a]
: Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
Maybe (static a)
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
-> Power
-> [Maybe (static a)]
runMergeWith (static a -> Maybe (static a)
forall a. a -> Maybe a
Just (static a -> Maybe (static a)) -> static a -> Maybe (static a)
forall a b. (a -> b) -> a -> b
$ static a
c static a -> static a -> static a
forall (static :: * -> *) a.
LogarithmicMethodDS static a =>
static a -> static a -> static a
`merge` static a
d1) [Maybe (static a)]
ds1' (Power
iPower -> Power -> Power
forall a. Num a => a -> a -> a
+Power
1) [Maybe (static a)]
ds2 Power
j
                       -- i < j, so invariant holds

-- | 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.
queryWith                           :: Monoid m => (static a -> m) -> InsertionOnly static a -> m
queryWith :: forall {k} m (static :: k -> *) (a :: k).
Monoid m =>
(static a -> m) -> InsertionOnly static a -> m
queryWith static a -> m
query (InsertionOnly [Maybe (static a)]
dss) = (Maybe (static a) -> m) -> [Maybe (static a)] -> m
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((static a -> m) -> Maybe (static a) -> m
forall m a. Monoid m => (a -> m) -> Maybe a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap static a -> m
query) [Maybe (static a)]
dss