module Data.StableTree
( StableTree(..)
, IsKey(..)
, fromMap
, toMap
) where
import Data.StableTree.Types
import qualified Data.Map as Map
import Data.Map ( Map )
import Data.Maybe ( isNothing )
data StableTree k v = StableTree_I (Tree Incomplete k v)
| StableTree_C (Tree Complete k v)
fromMap :: (Ord k, IsKey k) => Map k v -> StableTree k v
fromMap m = go m Map.empty
where
go values accum =
case nextBottom values of
Left incomplete ->
if Map.null accum
then StableTree_I incomplete
else case getKey incomplete of
Just k -> buildParents accum (Just (k, incomplete)) Map.empty
Nothing -> buildParents accum Nothing Map.empty
Right (complete, remain) ->
if Map.null remain && Map.null accum
then StableTree_C complete
else go remain $ Map.insert (completeKey complete) complete accum
buildParents completes mIncomplete accum =
case nextBranch completes mIncomplete of
Left incomplete ->
if Map.null accum
then StableTree_I incomplete
else case getKey incomplete of
Just k -> buildParents accum (Just (k, incomplete)) Map.empty
Nothing -> buildParents accum Nothing Map.empty
Right (complete, remain) ->
if Map.null remain && Map.null accum && isNothing mIncomplete
then StableTree_C complete
else
let accum' = Map.insert (completeKey complete) complete accum
in buildParents remain mIncomplete accum'
toMap :: Ord k => StableTree k v -> Map k v
toMap (StableTree_I t) = treeContents t
toMap (StableTree_C t) = treeContents t
instance (Ord k, Show k, Show v) => Show (StableTree k v) where
show (StableTree_I t) = show t
show (StableTree_C t) = show t