module Data.Set.StringSet where
import Data.Binary
import Control.Monad
data StringSet = SNode !Char !StringSet !StringSet !StringSet | SEnd
deriving (Show, Eq)
insert :: String -> StringSet -> StringSet
insert xss@(x:xs) (SNode ele l e h) =
case compare x ele of
LT -> SNode ele (insert xss l) e h
EQ -> SNode ele l (insert xs e) h
GT -> SNode ele l e (insert xss h)
insert xss@(x:xs) SEnd =
insert' xss
insert [] t@(SNode ele l e h) =
case compare '\0' ele of
EQ -> t
LT -> SNode ele (insert [] l) e h
insert [] SEnd =
SNode '\0' SEnd SEnd SEnd
insert' :: String -> StringSet
insert' (x:xs) = SNode x SEnd (insert' xs) SEnd
insert' [] = SNode '\0' SEnd SEnd SEnd
isElem :: String -> StringSet -> Bool
isElem _ SEnd = False
isElem [] (SNode ele l e h) = ele == '\0' || isElem [] l
isElem xss@(x:xs) (SNode ele l e h) =
case compare x ele of
LT -> isElem xss l
EQ -> isElem xs e
GT -> isElem xss h
treeSize :: StringSet -> Int
treeSize SEnd = 0
treeSize (SNode '\0' l e h) = treeSize l + treeSize e + treeSize h
treeSize (SNode _ l e h) = 1 + treeSize l + treeSize e + treeSize h
numEntries :: StringSet -> Int
numEntries SEnd = 0
numEntries (SNode '\0' l e h) = 1 + numEntries l + numEntries e + numEntries h
numEntries (SNode _ l e h) = numEntries l + numEntries e + numEntries h
fromList :: [String] -> StringSet
fromList = foldl (flip insert) SEnd
instance Binary StringSet where
put SEnd = put (0 :: Word8)
put (SNode ch SEnd SEnd SEnd) = do
putWord8 1
put ch
put (SNode ch SEnd e SEnd) = do
putWord8 2
put ch
put e
put (SNode ch l e h) = do
putWord8 3
put ch
put l
put e
put h
get = do
tag <- getWord8
case tag of
0 -> return SEnd
1 -> do
ch <- get
return (SNode ch SEnd SEnd SEnd)
2 -> do
ch <- get
e <- get
return (SNode ch SEnd e SEnd)
3 -> liftM4 SNode get get get get