-- | This module provides alternating finger trees, which are similar
-- to "Data.Sequence" in the @containers@ package, or
-- "Data.FingerTree" in the @fingertree@ package, except that, between
-- every element (of type @e@) in the \'normal\' finger tree, there is
-- a \'separator\' of type @a@. @'TwoFingerOddA' e ()@ is isomorphic
-- to @[e]@, and @'TwoFingerOddA' e a@ is isomorphic to @([(a, e)], a)@.
-- (The type variables are in that order because that permits a
-- 'Traversable1' instance for 'TwoFingerOddA'.)
--
-- Four flavours of alternating finger trees are present,
-- corresponding to different element patterns:
--
--   * @'TwoFingerOddA' e a@, which is like @a (e a)*@.
--   * @'TwoFingerOddE' e a@, which is like @e (a e)*@.
--   * @'TwoFingerEvenA' e a@, which is like @(a e)*@.
--   * @'TwoFingerEvenE' e a@, which is like @(e a)*@.
--
-- The flavours' names first describe whether they have the same
-- number of @a@s and @e@s within them (the @Even@ flavours do, the
-- @Odd@ ones do not), and then whether the first element is an @e@ or
-- an @a@.
--
-- (Full) conses and snocs prepend or append a pair of elements to the
-- front or rear of an alternating finger tree, keeping the flavour
-- the same. Half-conses and -snocs transform between these flavours,
-- adding only half the pair. All cons-like operations have an inverse
-- operation. Some half-conses and -snocs and their inverses are
-- \(O(1)\) amortised, with \(O(\log n)\) worst case, while some are \(O(1)\)
-- always. All full conses, snocs and inverses are \(O(1)\) amortised
-- and \(O(\log n)\) worst case.
--
-- Note that the names of half-conses and -snocs take the flavour that
-- they operate on, which means that, for example, 'halfconsOddA' and
-- 'halfunconsOddA' are __not__ inverses; the actual inverse pairs are
-- 'halfconsOddA' + 'halfunconsEvenE' and 'halfconsEvenE' +
-- 'halfunconsOddA'.
--
-- Appending alternating finger trees is also efficient. As well as
-- the usual 'Monoid' and 'Semigroup' instances, the two @Even@
-- flavours can be viewed as monoid actions of the @Odd@ flavours. All
-- append-like operations are \(O(\log(\min(n, m)))\) amortised and
-- \(O(\log(\max(n, m)))\) worst case.
--
-- For more information on finger trees, see:
--
--    * Ralf Hinze and Ross Paterson,
--      \"Finger trees: a simple general-purpose data structure\",
--      /Journal of Functional Programming/ 16:2 (2006) pp 197-217.
--      <http://staff.city.ac.uk/~ross/papers/FingerTree.html>
--
-- This package's alternating finger trees are not annotated with
-- sizes as described in section 4 of the paper.
module Q4C12.TwoFinger
  ( -- * TwoFingerOddA
    TwoFingerOddA,
    -- ** Construction and analysis
    singletonOddA, unitOddA, onlyOddA, interleavingOddA,
    -- ** Full conses
    consOddA, unconsOddA, snocOddA, unsnocOddA,
    -- ** Half conses
    halfconsOddA, halfunconsOddA, halfsnocOddA, halfunsnocOddA,
    -- ** Lenses
    firstOddA, lastOddA,
    -- * TwoFingerOddE
    TwoFingerOddE,
    -- ** Construction
    singletonOddE,
    -- ** Full conses
    consOddE, snocOddE, unconsOddE, unsnocOddE,
    -- ** Half conses
    halfconsOddE, halfsnocOddE, halfunconsOddE, halfunsnocOddE,
    -- * TwoFingerEvenA
    TwoFingerEvenA,
    -- ** Full conses
    consEvenA, unconsEvenA, snocEvenA, unsnocEvenA,
    -- ** Half conses
    halfconsEvenA, halfsnocEvenA, halfunconsEvenA, halfunsnocEvenA,
    -- * TwoFingerEvenE
    TwoFingerEvenE,
    -- ** Full conses
    consEvenE, unconsEvenE, snocEvenE, unsnocEvenE,
    -- ** Half conses
    halfconsEvenE, halfsnocEvenE, halfunconsEvenE, halfunsnocEvenE,
    -- * Appending different flavours
    -- $monoid_action_properties
    -- ** Monoid actions
    appendEvenAOddA, appendOddEEvenA,
    appendOddAEvenE, appendEvenEOddE,
    -- ** Two odds make an even
    appendOddAOddE, appendOddEOddA,
    -- * Aligning (zipping)
    alignLeftOddAOddA, alignLeftOddAEvenA,
    alignLeftOddEOddE, alignLeftOddEEvenE,
    -- * Infinite trees
    repeatOddA, repeatOddE,
    repeatEvenA, repeatEvenE,
    infiniteOddA, infiniteOddE,
    infiniteEvenA, infiniteEvenE
  )
  where

import Q4C12.TwoFinger.Internal
  (
    TwoFingerOddA,
    singletonOddA, unitOddA, onlyOddA, interleavingOddA,
    consOddA, unconsOddA, snocOddA, unsnocOddA,
    halfconsOddA, halfunconsOddA, halfsnocOddA, halfunsnocOddA,
    firstOddA, lastOddA,
    TwoFingerOddE,
    singletonOddE,
    consOddE, snocOddE, unconsOddE, unsnocOddE,
    halfconsOddE, halfsnocOddE, halfunconsOddE, halfunsnocOddE,
    TwoFingerEvenA,
    consEvenA, unconsEvenA, snocEvenA, unsnocEvenA,
    halfconsEvenA, halfsnocEvenA, halfunconsEvenA, halfunsnocEvenA,
    TwoFingerEvenE,
    consEvenE, unconsEvenE, snocEvenE, unsnocEvenE,
    halfconsEvenE, halfsnocEvenE, halfunconsEvenE, halfunsnocEvenE,
    appendEvenAOddA, appendOddEEvenA,
    appendOddAEvenE, appendEvenEOddE,
    appendOddAOddE, appendOddEOddA,
    alignLeftOddAOddA, alignLeftOddAEvenA,
    alignLeftOddEOddE, alignLeftOddEEvenE,
    repeatOddA, repeatOddE,
    repeatEvenA, repeatEvenE,
    infiniteOddA, infiniteOddE,
    infiniteEvenA, infiniteEvenE
  )

-- $setup
-- >>> import Q4C12.TwoFinger.Internal (AnyOddA (AnyOddA), AnyOddE (AnyOddE), AnyEvenA (AnyEvenA), AnyEvenE (AnyEvenE))
-- >>> import Data.Semigroup ((<>))

-- $monoid_action_properties
-- prop> \(AnyOddA a) (AnyOddA b) (AnyEvenE c) -> appendOddAEvenE (a <> b) c == a <> appendOddAEvenE b c
-- prop> \(AnyOddA a) (AnyOddE b) (AnyOddA c) -> appendEvenAOddA (appendOddAOddE a b) c == appendOddAEvenE a (appendOddEOddA b c)
-- prop> \(AnyOddA a) (AnyOddE b) (AnyEvenA c) -> appendOddAOddE a (appendOddEEvenA b c) == appendOddAOddE a b <> c
-- prop> \(AnyOddA a) (AnyEvenE b) (AnyOddE c) -> appendOddAOddE a (appendEvenEOddE b c) == appendOddAOddE (appendOddAEvenE a b) c
-- prop> \(AnyOddA a) (AnyEvenE b) (AnyEvenE c) -> appendOddAEvenE a (b <> c) == appendOddAEvenE (appendOddAEvenE a b) c
--
-- prop> \(AnyOddE a) (AnyOddA b) (AnyOddE c) -> appendOddEEvenA a (appendOddAOddE b c) == appendEvenEOddE (appendOddEOddA a b) c
-- prop> \(AnyOddE a) (AnyOddA b) (AnyEvenE c) -> appendOddEOddA a (appendOddAEvenE b c) == appendOddEOddA a b <> c 
-- prop> \(AnyOddE a) (AnyEvenA b) (AnyOddA c) -> appendOddEOddA a (appendEvenAOddA b c) == appendOddEOddA (appendOddEEvenA a b) c
-- prop> \(AnyOddE a) (AnyEvenA b) (AnyEvenA c) -> appendOddEEvenA a (b <> c) == appendOddEEvenA (appendOddEEvenA a b) c
--
-- prop> \(AnyEvenA a) (AnyOddA b) (AnyOddA c) -> appendEvenAOddA a (b <> c) == appendEvenAOddA a b <> c
-- prop> \(AnyEvenA a) (AnyOddA b) (AnyOddE c) -> appendOddAOddE (appendEvenAOddA a b) c == a <> appendOddAOddE b c
-- prop> \(AnyEvenA a) (AnyOddA b) (AnyEvenE c) -> appendOddAEvenE (appendEvenAOddA a b) c == appendEvenAOddA a (appendOddAEvenE b c)
-- prop> \(AnyEvenA a) (AnyEvenA b) (AnyOddA c) -> appendEvenAOddA (a <> b) c == appendEvenAOddA a (appendEvenAOddA b c)
--
-- prop> \(AnyEvenE a) (AnyOddE b) (AnyOddA c) -> appendOddEOddA (appendEvenEOddE a b) c == a <> appendOddEOddA b c
-- prop> \(AnyEvenE a) (AnyOddE b) (AnyEvenA c) -> appendOddEEvenA (appendEvenEOddE a b) c == appendEvenEOddE a (appendOddEEvenA b c)
-- prop> \(AnyEvenE a) (AnyEvenE b) (AnyOddE c) -> appendEvenEOddE (a <> b) c == appendEvenEOddE a (appendEvenEOddE b c)