+
+-------------------
+splitUFM fm key = split fm (getKeyFastInt (getUnique key))
+
+split :: UniqFM a -> FastInt -> (UniqFM a, Maybe a, UniqFM a)
+-- Splits a UFM into things less than, equal to, and greater than the key
+split EmptyUFM _ = (EmptyUFM, Nothing, EmptyUFM)
+split fm i = go fm
+ where
+ go (LeafUFM j b) | i <# j = (EmptyUFM, Nothing, LeafUFM j b)
+ | i ># j = (LeafUFM j b, Nothing, EmptyUFM)
+ | otherwise = (EmptyUFM, Just b, EmptyUFM)
+
+ go (NodeUFM j p t1 t2)
+ | j ># i
+ , (lt, eq, gt) <- go t1 = (lt, eq, mkSLNodeUFM (NodeUFMData j p) gt t2)
+ | (lt, eq, gt) <- go t2 = (mkLSNodeUFM (NodeUFMData j p) t1 lt, eq, gt)
+
+ go EmptyUFM = panic "splitUFM failed"