> module SplaySet       (  BinTree(..),
>                          Set(..),
>                       -- construction
>                          empty, singleton, add, addMany,
>                       -- modification
>                          delete, deleteMany,
>                       -- conversion
>                          toList, fromList,
>                       -- size
>                          lengthSet,
>                       -- testing
>                          nullSet, isSingleton, setElem,
>                       -- *additional functions*
>                          search, toSortedList, fromSortedList
>                       )
> where

> import Sort           (  mergeSort, unique  )
> import BinTree        (  Pretty(..), Txt, BinTree(..),
>                          empty, leaf, right, inorder, size, member  )
> import Splay          (  splay, join  )

> type Set a            =  BinTree a

> singleton             =  leaf

> add                   :: Ord a => a -> Set a -> Set a
> add a t               =  case splay (compare a) t of
>     (_, Empty)        -> Node Empty a Empty
>     (_EQ, Node l _ r) -> Node l a r
>     (_LT, Node l b r) -> Node l a (Node Empty b r)
>     (_GT, Node l b r) -> Node (Node l b Empty) a r

> addMany               :: Ord a => [a] -> Set a -> Set a
> addMany x s           =  foldr add s x

> delete                :: Ord a => a -> Set a -> Set a
> delete a t            =  case splay (compare a) t of
>     (_, Empty)        -> Empty
>     (_EQ, Node l _ r) -> join l r
>     _                 -> t

> deleteMany                    :: Ord a => [a] -> Set a -> Set a
> deleteMany x s                =  foldr delete s x

> toList                        :: Set a -> [a]
> toList                        =  inorder

> fromList                      :: Ord a => [a] -> Set a
> fromList                      =  fromSortedList . mergeSort

> lengthSet                     :: Set a -> Int
> lengthSet                     =  size

> nullSet                       :: Set a -> Bool
> nullSet Empty                 =  True
> nullSet (Node _ _ _)          =  False

> isSingleton                           :: Set a -> Bool
> isSingleton (Node Empty a Empty)      =  True
> isSingleton _                         =  False

> setElem                       :: Ord a => a -> Set a -> Bool
> setElem                       =  member

> search                :: Ord a => a -> Set a -> (Bool, Set a)
> search a t            =  case splay (compare a) t of
>     (_, Empty)        -> (False, Empty)
>     (_EQ, t)          -> (True, t)
>     (_, t)            -> (False, t)

> toSortedList                  :: Set a -> [a]
> toSortedList                  =  inorder

> fromSortedList                :: Ord a => [a] -> Set a
> fromSortedList                =  right . unique

> type Ordering         =  _CMP_TAG

> compare               :: Ord a => a -> a -> Ordering
> compare               =  _tagCmp
> {-# INLINE compare #-}