--------------------------------------------------------------------------------
-- |
-- Module : Data.Sequence.Util
-- Copyright : (C) Frank Staals
-- License : see the LICENSE file
-- Maintainer : Frank Staals
--------------------------------------------------------------------------------
module Data.Sequence.Util where
import Algorithms.BinarySearch
import qualified Data.Sequence as S
import Data.Sequence (Seq)
--------------------------------------------------------------------------------
-- | Partition the seq s given a monotone predicate p into (xs,ys) such that
--
-- all elements in xs do *not* satisfy the predicate p
-- all elements in ys do satisfy the predicate p
--
-- all elements in s occur in either xs or ys.
--
-- running time: \(O(\log^2 n + T*\log n)\), where \(T\) is the time to execute the
-- predicate.
splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
splitMonotone p s = case binarySearchIdxIn p s of
Nothing -> (s,S.empty)
Just i -> S.splitAt i s