module Data.Splay.Sequence
( Seq
, singleton
, (<|)
, (|>)
, fromList
, null
, length
, splitAt
) where
import Control.Applicative
import Data.Foldable hiding (null, length)
import Data.Function
import Data.Monoid
import Data.Traversable
import Prelude hiding (null, length, splitAt, foldr)
import qualified Data.Splay as S
newtype Size = Size { getSize :: Int }
deriving (Num, Eq, Ord)
newtype Item a = Item { getItem :: a }
instance Monoid Size where
mempty = 0
mappend = (+)
instance S.Measured Size (Item a) where
measure _ = 1
newtype Seq a = Seq { getSeq :: S.Splay Size (Item a) }
instance Functor Seq where fmap = fmapDefault
instance Foldable Seq where foldMap = foldMapDefault
instance Traversable Seq where
traverse f (Seq x) = Seq <$> S.traverseSplay (fmap Item . f . getItem) x
instance Monoid (Seq a) where
mempty = Seq mempty
Seq a `mappend` Seq b = Seq $ a <> b
instance Eq a => Eq (Seq a) where
(==) = (==) `on` toList
(/=) = (/=) `on` toList
instance Ord a => Ord (Seq a) where
compare = compare `on` toList
instance Show a => Show (Seq a) where
showsPrec p xs =
showParen (p > 10) $ showString "fromList " . shows (toList xs)
singleton :: a -> Seq a
singleton = Seq . S.singleton . Item
(<|) :: a -> Seq a -> Seq a
x <| xs = singleton x <> xs
(|>) :: Seq a -> a -> Seq a
xs |> x = xs <> singleton x
fromList :: [a] -> Seq a
fromList = foldr (<|) mempty
null :: Seq a -> Bool
null = (== 0) . length
length :: Seq a -> Int
length = getSize . S.measure . getSeq
splitAt :: Int -> Seq a -> (Seq a, Seq a)
splitAt n (Seq s) = case S.split (> Size n) s of (a, b) -> (Seq a, Seq b)