content: -- |
  --   Module      :  Data.Edison.Coll
  --   Copyright   :  Copyright (c) 2006, 2008 Robert Dockins
  --   License     :  MIT; see COPYRIGHT file for terms and conditions
  --
  --   Maintainer  :  robdockins AT fastmail DOT fm
  --   Stability   :  stable
  --   Portability :  GHC, Hugs (MPTC and FD)
  --
  --   The standard library "Data.Set" repackaged as an Edison collection.
  
  module Data.Edison.Coll.StandardSet (
      -- * Set type
      Set,
  
      -- * CollX operations
      empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
      deleteSeq,null,size,member,count,strict,
  
      -- * Coll operations
      toSeq,lookup,lookupM,lookupAll,lookupWithDefault,fold,fold',
      fold1,fold1',filter,partition,strictWith,structuralInvariant,
  
      -- * OrdCollX operations
      deleteMin,deleteMax,unsafeInsertMin,unsafeInsertMax,unsafeFromOrdSeq,
      unsafeAppend,filterLT,filterLE,filterGT,filterGE,partitionLT_GE,
      partitionLE_GT,partitionLT_GT,
  
      -- * OrdColl operations
      minView,minElem,maxView,maxElem,foldr,foldr',foldl,foldl',
      foldr1,foldr1',foldl1,foldl1',toOrdSeq,unsafeMapMonotonic,
  
      -- * SetX operations
      intersection,difference,symmetricDifference,properSubset,subset,
  
      -- * Set operations
      fromSeqWith,insertWith,insertSeqWith,unionl,unionr,unionWith,
      unionSeqWith,intersectionWith,
  
      -- * Documentation
      moduleName
  ) where
  
  import Prelude hiding (null,foldr,foldl,foldr1,foldl1,foldl',lookup,filter)
  import qualified Prelude
  import qualified Control.Monad.Fail as Fail
  import qualified Data.List
  
  import qualified Data.Edison.Coll as C
  import qualified Data.Edison.Seq as S
  import qualified Data.Edison.Seq.ListSeq as L
  import Data.Edison.Coll.Defaults
  import Test.QuickCheck
  
  import qualified Data.Set as DS
  
  -- signatures for exported functions
  moduleName :: String
  empty      :: Set a
  singleton  :: a -> Set a
  fromSeq    :: (Ord a,S.Sequence seq) => seq a -> Set a
  insert     :: Ord a => a -> Set a -> Set a
  insertSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
  union      :: Ord a => Set a -> Set a -> Set a
  unionSeq   :: (Ord a,S.Sequence seq) => seq (Set a) -> Set a
  delete     :: Ord a => a -> Set a -> Set a
  deleteAll  :: Ord a => a -> Set a -> Set a
  deleteSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
  null       :: Set a -> Bool
  size       :: Set a -> Int
  member     :: Ord a => a -> Set a -> Bool
  count      :: Ord a => a -> Set a -> Int
  strict     :: Ord a => Set a -> Set a
  
  toSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a
  lookup     :: Ord a => a -> Set a -> a
  lookupM    :: (Ord a, Monad m, Fail.MonadFail m) => a -> Set a -> m a
  lookupAll  :: (Ord a,S.Sequence seq) => a -> Set a -> seq a
  lookupWithDefault :: Ord a => a -> a -> Set a  -> a
  fold       :: (a -> b -> b) -> b -> Set a -> b
  fold1      :: (a -> a -> a) -> Set a -> a
  fold'      :: (a -> b -> b) -> b -> Set a -> b
  fold1'     :: (a -> a -> a) -> Set a -> a
  filter     :: Ord a => (a -> Bool) -> Set a -> Set a
  partition  :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
  strictWith :: Ord a => (a -> b) -> Set a -> Set a
  
  deleteMin        :: Ord a => Set a -> Set a
  deleteMax        :: Ord a => Set a -> Set a
  unsafeInsertMin  :: Ord a => a -> Set a -> Set a
  unsafeInsertMax  :: Ord a => a -> Set a -> Set a
  unsafeFromOrdSeq :: (Ord a,S.Sequence seq) => seq a -> Set a
  unsafeAppend     :: Ord a => Set a -> Set a -> Set a
  filterLT         :: Ord a => a -> Set a -> Set a
  filterLE         :: Ord a => a -> Set a -> Set a
  filterGT         :: Ord a => a -> Set a -> Set a
  filterGE         :: Ord a => a -> Set a -> Set a
  partitionLT_GE   :: Ord a => a -> Set a -> (Set a, Set a)
  partitionLE_GT   :: Ord a => a -> Set a -> (Set a, Set a)
  partitionLT_GT   :: Ord a => a -> Set a -> (Set a, Set a)
  
  minView       :: (Ord a, Monad m, Fail.MonadFail m) => Set a -> m (a, Set a)
  minElem       :: Set a -> a
  maxView       :: (Ord a, Monad m, Fail.MonadFail m) => Set a -> m (a, Set a)
  maxElem       :: Set a -> a
  foldr         :: (a -> b -> b) -> b -> Set a -> b
  foldl         :: (b -> a -> b) -> b -> Set a -> b
  foldr1        :: (a -> a -> a) -> Set a -> a
  foldl1        :: (a -> a -> a) -> Set a -> a
  foldr'        :: (a -> b -> b) -> b -> Set a -> b
  foldl'        :: (b -> a -> b) -> b -> Set a -> b
  foldr1'       :: (a -> a -> a) -> Set a -> a
  foldl1'       :: (a -> a -> a) -> Set a -> a
  toOrdSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a
  
  intersection  :: Ord a => Set a -> Set a -> Set a
  difference    :: Ord a => Set a -> Set a -> Set a
  symmetricDifference :: Ord a => Set a -> Set a -> Set a
  properSubset  :: Ord a => Set a -> Set a -> Bool
  subset        :: Ord a => Set a -> Set a -> Bool
  
  fromSeqWith   :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a
  insertWith    :: Ord a => (a -> a -> a) -> a -> Set a -> Set a
  insertSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a -> Set a
  unionl       :: Ord a => Set a -> Set a -> Set a
  unionr       :: Ord a => Set a -> Set a -> Set a
  unionWith    :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
  unionSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq (Set a) -> Set a
  intersectionWith :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
  unsafeMapMonotonic :: Ord a => (a -> a) -> Set a -> Set a
  
  moduleName = "Data.Edison.Coll.StandardSet"
  
  type Set = DS.Set
  
  structuralInvariant :: Ord a => Set a -> Bool
  structuralInvariant = DS.valid
  
  empty              = DS.empty
  singleton          = DS.singleton
  fromSeq            = fromSeqUsingFoldr
  insert             = DS.insert
  insertSeq          = insertSeqUsingUnion
  union              = DS.union
  unionSeq se        = DS.unions $ S.toList se
  delete             = DS.delete
  deleteAll          = DS.delete -- by set property
  deleteSeq          = deleteSeqUsingDelete
  null               = DS.null
  size               = DS.size
  member             = DS.member
  count              = countUsingMember
  strict xs          = DS.fold (flip const) () xs `seq` xs
  
  toSeq              = toSeqUsingFold
  lookup el set      = DS.findMin (DS.intersection set (DS.singleton el))
  lookupM            = lookupMUsingLookupAll
  lookupAll el set   = toSeqUsingFold (DS.intersection set (DS.singleton el))
  lookupWithDefault  = lookupWithDefaultUsingLookupAll
  fold               = DS.fold
  fold' f x xs       = L.foldl' (flip f) x (DS.toList xs)
  fold1 f set        = let (x,s) = DS.deleteFindMin set in DS.fold f x s
  fold1' f xs        = L.foldl1' (flip f) (DS.toList xs)
  filter             = DS.filter
  partition          = DS.partition
  strictWith f xs    = DS.fold (\x z -> f x `seq` z) () xs `seq` xs
  
  deleteMin          = DS.deleteMin
  deleteMax          = DS.deleteMax
  unsafeInsertMin    = DS.insert
  unsafeInsertMax    = DS.insert
  unsafeFromOrdSeq   = DS.fromDistinctAscList . S.toList
  unsafeAppend       = DS.union
  filterLT x         = fst . DS.split x
  filterLE x         = DS.filter (<=x)
  filterGT x         = snd . DS.split x
  filterGE x         = DS.filter (>=x)
  partitionLT_GE x   = DS.partition (<x)
  partitionLE_GT x   = DS.partition (<=x)
  partitionLT_GT     = DS.split
  
  minView set        = if DS.null set
                          then fail (moduleName ++ ".minView: failed")
                          else return (DS.deleteFindMin set)
  minElem            = DS.findMin
  
  maxView set        = if DS.null set
                          then fail (moduleName ++ ".maxView: failed")
                          else return (DS.deleteFindMax set)
  maxElem            = DS.findMax
  
  foldr   f x set     = L.foldr   f x (DS.toAscList set)
  foldr'  f x set     = L.foldr'  f x (DS.toAscList set)
  foldr1  f   set     = L.foldr1  f   (DS.toAscList set)
  foldr1' f   set     = L.foldr1' f   (DS.toAscList set)
  foldl   f x set     = L.foldl   f x (DS.toAscList set)
  foldl'  f x set     = L.foldl'  f x (DS.toAscList set)
  foldl1  f   set     = L.foldl1  f   (DS.toAscList set)
  foldl1' f   set     = L.foldl1' f   (DS.toAscList set)
  
  toOrdSeq           = S.fromList . DS.toAscList
  
  intersection       = DS.intersection
  difference         = DS.difference
  symmetricDifference = symmetricDifferenceUsingDifference
  properSubset       = DS.isProperSubsetOf
  subset             = DS.isSubsetOf
  
  fromSeqWith        = fromSeqWithUsingInsertWith
  insertWith f x set = case lookupM x set of
                          Nothing -> DS.insert x set
                          Just x' -> DS.insert (f x x') set
  insertSeqWith      = insertSeqWithUsingInsertWith
  unionl             = DS.union
  unionr             = flip DS.union
  unionWith          = unionWithUsingOrdLists
  unionSeqWith       = unionSeqWithUsingReducer
  intersectionWith   = intersectionWithUsingOrdLists
  unsafeMapMonotonic = DS.mapMonotonic
  
  
  
  instance Ord a => C.CollX (Set a) a where
    {singleton = singleton; fromSeq = fromSeq; insert = insert;
     insertSeq = insertSeq; unionSeq = unionSeq;
     delete = delete; deleteAll = deleteAll; deleteSeq = deleteSeq;
     null = null; size = size; member = member; count = count;
     strict = strict;
     structuralInvariant = structuralInvariant; instanceName _ = moduleName}
  
  instance Ord a => C.OrdCollX (Set a) a where
    {deleteMin = deleteMin; deleteMax = deleteMax;
     unsafeInsertMin = unsafeInsertMin; unsafeInsertMax = unsafeInsertMax;
     unsafeFromOrdSeq = unsafeFromOrdSeq; unsafeAppend = unsafeAppend;
     filterLT = filterLT; filterLE = filterLE; filterGT = filterGT;
     filterGE = filterGE; partitionLT_GE = partitionLT_GE;
     partitionLE_GT = partitionLE_GT; partitionLT_GT = partitionLT_GT}
  
  instance Ord a => C.Coll (Set a) a where
    {toSeq = toSeq; lookup = lookup; lookupM = lookupM;
     lookupAll = lookupAll; lookupWithDefault = lookupWithDefault;
     fold = fold; fold' = fold'; fold1 = fold1; fold1' = fold1';
     filter = filter; partition = partition; strictWith = strictWith}
  
  instance Ord a => C.OrdColl (Set a) a where
    {minView = minView; minElem = minElem; maxView = maxView;
     maxElem = maxElem; foldr = foldr; foldr' = foldr'; foldl = foldl;
     foldl' = foldl'; foldr1 = foldr1; foldr1' = foldr1';
     foldl1 = foldl1; foldl1' = foldl1'; toOrdSeq = toOrdSeq;
     unsafeMapMonotonic = unsafeMapMonotonic }
  
  instance Ord a => C.SetX (Set a) a where
    {intersection = intersection; difference = difference;
     symmetricDifference = symmetricDifference;
     properSubset = properSubset; subset = subset}
  
  instance Ord a => C.Set (Set a) a where
    {fromSeqWith = fromSeqWith; insertWith = insertWith;
     insertSeqWith = insertSeqWith; unionl = unionl; unionr = unionr;
     unionWith = unionWith; unionSeqWith = unionSeqWith;
     intersectionWith = intersectionWith}
  
  instance Ord a => C.OrdSetX (Set a) a
  
  instance Ord a => C.OrdSet (Set a) a
  