-- File: TreeSet.hs
-- Copyright (C) 2010 Gregory D. Weber
-- Revised 2013 Nov 4: removed datatype context for TreeSet.
-- TreeSet is a set using an encapsulated binary search tree.

-- Exports the type constructor but not the data constructor,
-- thereby hiding the binary search tree

-- instance declaration

module TreeSet 
    (TreeSet -- hides internal structure
    , newTreeSet
    , insert
    , member
    , remove
    , fromList
    , toList
    )

where

import qualified BinarySearchTree as BST
import BinaryTree

data TreeSet a = TreeSet (BinaryTree a)

instance (Ord a, Show a) => Show (TreeSet a) where
  show s = "fromList " ++ show (toList s)

newTreeSet :: (Ord a) => TreeSet a
newTreeSet = TreeSet BST.newSearchTree

insert :: (Ord a) => a -> TreeSet a -> TreeSet a
insert x (TreeSet t) = TreeSet (BST.insert x t)

-- member x t tells whether x is a member (element) of (i.e., contained in) t.
member :: (Ord a) => a -> TreeSet a -> Bool
member x (TreeSet t) = BST.member x t

remove :: (Ord a) => a -> TreeSet a -> TreeSet a
remove x (TreeSet t) = TreeSet (BST.remove x t)

toList :: (Ord a) => TreeSet a -> [a]
toList (TreeSet t) = preorder t

fromList :: (Ord a) => [a] -> TreeSet a
fromList xs = TreeSet (fromList' xs BST.newSearchTree)

fromList' xs t =
    case xs of
      [] -> t
      x:xs' -> fromList' xs' (BST.insert x t)