-- | Simple but efficient strict sequence type based on a nested data type and polymorphic recursion.
--
-- It is like a list, but instead of @O(1)@ cons\/uncons and @O(k)@ lookup, 
-- we have amortized @O(1)@ cons/uncons and @O(log(k))@ lookup (both are @O(log(n))@ in the worst case).
-- This is somewhat similar to a finger tree (which is also represented by a nested data type), but 
-- much simpler and more memory efficient (memory usage is basically the same as with lists: amortized 
-- 3 words per element, plus the data itself).
--
-- However, modifying the right end of the sequence is still slow: @O(n)@. This affects the functions 
-- 'snoc', 'unSnoc', 'append', 'take', 'init'. Somewhat surprisingly, /extracting/ the last element is 
-- still fast.
--
-- An example usage is a pure random-access stack.
--
-- This module is intended to be imported qualified.
--

{-# LANGUAGE CPP, BangPatterns, PatternSynonyms, PatternGuards #-}
module Data.Nested.Seq.Strict 

#include "exp_imp.inc"

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

data StrictPair a = StrictPair !a !a deriving (Eq,Show)

type Pair a = StrictPair a

-- | The strict sequence type. See "Data.Nested.Seq.Lazy" for more detailed information.
data Seq a 
  = Nil                      -- ^ empty sequence
  | ZZ    !(Seq (Pair a))    -- ^ even sequence (we will use a pattern synonym to maintain an invariant, hence the strange name)
  | O  !a !(Seq (Pair a))    -- ^ odd sequence
#ifdef TESTING
  deriving Show
#endif

-- so that we can use the same source code for the strict and the lazy versions
pattern Pair x y = StrictPair x y

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

#include "sequence.inc"

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