-- | This module provides alternating finger trees, based on
-- 'Data.Seq.Seq' from the @containers@ package. 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>
--
-- Many of the functions in this package follow laws, which are not
-- documented inline. [tests/Properties.hs](https://github.com/quasicomputational/mega/blob/master/packages/twofinger/test/Properties.hs)
--is an  automatically-tested QuickCheck suite of properties.
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 actions
    appendEvenAOddA, appendOddEEvenA,
    appendOddAEvenE, appendEvenEOddE,
    -- ** Two odds make an even
    appendOddAOddE, appendOddEOddA,
  )
  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,
  )