O(n+m). The union of two sets, preferring the first set when
+ equal elements are encountered.
+ The implementation uses the efficient hedge-union algorithm.
+ Hedge-union is more efficient on (bigset union smallset).
+
O(n+m). The intersection of two sets.
+ Elements of the result come from the first set, so for example
+
import qualified Data.Set as S
+ data AB = A | B deriving Show
+ instance Ord AB where compare _ _ = EQ
+ instance Eq AB where _ == _ = True
+ main = print (S.singleton A `S.intersection` S.singleton B,
+ S.singleton B `S.intersection` S.singleton A)
+
O(n). Partition the set into two sets, one with all elements that satisfy
+ the predicate and one with all elements that don't satisfy the predicate.
+ See also split.
+
O(log n). The expression (split x set) is a pair (set1,set2)
+ where set1 comprises the elements of set less than x and set2
+ comprises the elements of set greater than x.
+
O(n). The expression (showTreeWith hang wide map) shows
+ the tree that implements the set. If hang is
+ True, a hanging tree is shown otherwise a rotated tree is shown. If
+ wide is True, an extra wide version is shown.
+
{-# LANGUAGE TypeFamilies, CPP, ViewPatterns, MagicHash, UnboxedTuples, PatternGuards #-}
+{-# OPTIONS_GHC -fno-warn-overlapping-patterns #-}
+
+{------------------------------------------------------------------------------
+-- |
+-- Module : Data.Set.Unboxed
+-- Copyright : (c) Edward Kmett 2009
+-- (c) Daan Leijen 2002
+-- License : BSD3
+-- Maintainer : ekmett@gmail.com
+-- Stability : experimental
+-- Portability : non-portable (type families, view patterns, unboxed tuples)
+--
+-- An efficient implementation of sets.
+--
+-- Since many function names (but not the type name) clash with
+-- "Prelude" names, this module is usually imported @qualified@, e.g.
+--
+-- > import Data.Set.Unboxed (USet)
+-- > import qualified Data.Set.Unboxed as USet
+--
+-- The implementation of 'USet' is based on /size balanced/ binary trees (or
+-- trees of /bounded balance/) as described by:
+--
+-- * Stephen Adams, \"/Efficient sets: a balancing act/\",
+-- Journal of Functional Programming 3(4):553-562, October 1993,
+-- <http://www.swiss.ai.mit.edu/~adams/BB/>.
+--
+-- * J. Nievergelt and E.M. Reingold,
+-- \"/Binary search trees of bounded balance/\",
+-- SIAM journal of computing 2(1), March 1973.
+--
+-- Note that the implementation is /left-biased/ -- the elements of a
+-- first argument are always preferred to the second, for example in
+-- 'union' or 'insert'. Of course, left-biasing can only be observed
+-- when equality is an equivalence relation instead of structural
+-- equality.
+--
+-- Modified from "Data.Set" to use type families for automatic unboxing
+-----------------------------------------------------------------------------
+-}
+
+moduleData.Set.Unboxed(
+-- * Set type
+USet-- instance Eq,Ord,Show,Read,Data,Typeable
+,US
+,Boxed(Boxed)
+
+-- * Operators
+,(\\)
+
+-- * Query
+,null
+,size
+,member
+,notMember
+,isSubsetOf
+,isProperSubsetOf
+
+-- * Construction
+,empty
+,singleton
+,insert
+,delete
+
+-- * Combine
+,union,unions
+,difference
+,intersection
+
+-- * Filter
+,filter
+,partition
+,split
+,splitMember
+
+-- * Map
+,map
+,mapMonotonic
+
+-- * Fold
+,fold
+
+-- * Min\/Max
+,findMin
+,findMax
+,deleteMin
+,deleteMax
+,deleteFindMin
+,deleteFindMax
+,maxView
+,minView
+
+-- * Conversion
+
+-- ** List
+,elems
+,toList
+,fromList
+
+-- ** Ordered list
+,toAscList
+,fromAscList
+,fromDistinctAscList
+
+-- * Debugging
+,showTree
+,showTreeWith
+,valid
+)where
+
+importPreludehiding(filter,foldr,null,map)
+importqualifiedData.ListasList
+importData.Monoid(Monoid(..))
+importData.Word
+importData.Int
+
+{-
+-- just for testing
+import Test.QuickCheck
+import Data.List (nub,sort)
+import qualified Data.List as List
+-}
+
+#if __GLASGOW_HASKELL__
+importText.Read
+#endif
+
+{--------------------------------------------------------------------
+ Operators
+--------------------------------------------------------------------}
+infixl9\\--
+
+-- | /O(n+m)/. See 'difference'.
+(\\)::(USa,Orda)=>USeta->USeta->USeta
+m1\\m2=differencem1m2
+
+{--------------------------------------------------------------------
+ Sets are size balanced trees
+--------------------------------------------------------------------}
+typeSize=Int
+
+-- | A set of values @a@.
+dataSeta=Tip
+|Bin{-# UNPACK #-}!Size!a!(USeta)!(USeta)
+
+-- smart unboxed types
+classUSawhere
+dataUSeta
+
+-- | Extract and rebox the specialized node format
+view::USeta->Seta
+
+-- | Apply the view to tip and bin continuations
+viewk::b->(Size->a->USeta->USeta->b)->USeta->b
+viewkfkx=caseviewxof
+Binsilr->ksilr
+Tip->f
+
+-- | View just the value and left and right child of a bin
+viewBin::USeta->(#a,USeta,USeta#)
+viewBinx=caseviewxof
+Bin_ilr->(#i,l,r#)
+Tip->error"viewBin"
+
+-- | /O(1)/. The number of elements in the set.
+size::USeta->Size
+size=viewk0size'where
+size's___=s
+
+-- | /O(1)/. Is this the empty set?
+null::USeta->Bool
+
+-- | Smart tip constructor
+tip::USeta
+
+-- | Smart bin constructor
+bin::Size->a->USeta->USeta->USeta
+
+instance(USa,Orda)=>Monoid(USeta)where
+mempty=empty
+mappend=union
+mconcat=unions
+
+{-
+instance US a => Generator (USet a) where
+ type Elem (USet a) = a
+ mapReduce _ (null -> True) = mempty
+ mapReduce f (view -> Bin _s k l r) = mapReduce f l `mappend` f k `mappend` mapReduce f r
+-}
+
+{--------------------------------------------------------------------
+ Query
+--------------------------------------------------------------------}
+-- | /O(log n)/. Is the element in the set?
+member::(USa,Orda)=>a->USeta->Bool
+memberx=gowhere
+go=viewkFalse(\_ylr->casecomparexyof
+LT->gol
+GT->gor
+EQ->True)
+
+-- | /O(log n)/. Is the element not in the set?
+notMember::(USa,Orda)=>a->USeta->Bool
+notMemberxt=not$memberxt
+
+{--------------------------------------------------------------------
+ Construction
+--------------------------------------------------------------------}
+-- | /O(1)/. The empty set.
+empty::USa=>USeta
+empty=tip
+
+-- | /O(1)/. Create a singleton set.
+singleton::USa=>a->USeta
+singletonx=bin1xtiptip
+
+{--------------------------------------------------------------------
+ Insertion, Deletion
+--------------------------------------------------------------------}
+-- | /O(log n)/. Insert an element in a set.
+-- If the set already contains an element equal to the given value,
+-- it is replaced with the new value.
+insert::(USa,Orda)=>a->USeta->USeta
+insertx=gowhere
+go=viewk(singletonx)(\szylr->casecomparexyof
+LT->balancey(gol)r
+GT->balanceyl(gor)
+EQ->binszxlr)
+{-# SPECIALIZE INLINE insert :: Int -> USet Int -> USet Int #-}
+
+-- | /O(log n)/. Delete an element from a set.
+delete::(USa,Orda)=>a->USeta->USeta
+deletex=gowhere
+go=viewktip$\_ylr->casecomparexyof
+LT->balancey(gol)r
+GT->balanceyl(gor)
+EQ->gluelr
+
+{--------------------------------------------------------------------
+ Subset
+--------------------------------------------------------------------}
+-- | /O(n+m)/. Is this a proper subset? (ie. a subset but not equal).
+isProperSubsetOf::(USa,Orda)=>USeta->USeta->Bool
+isProperSubsetOfs1s2=(sizes1<sizes2)&&(isSubsetOfs1s2)
+
+-- | /O(n+m)/. Is this a subset?
+-- @(s1 `isSubsetOf` s2)@ tells whether @s1@ is a subset of @s2@.
+isSubsetOf::(USa,Orda)=>USeta->USeta->Bool
+isSubsetOft1t2=(sizet1<=sizet2)&&(isSubsetOfXt1t2)
+
+isSubsetOfX::(USa,Orda)=>USeta->USeta->Bool
+isSubsetOfX_(null->True)=False
+isSubsetOfX(null->True)_=True
+isSubsetOfX(view->Bin_xlr)t=found&&isSubsetOfXllt&&isSubsetOfXrgt
+where
+(lt,found,gt)=splitMemberxt
+
+
+{--------------------------------------------------------------------
+ Minimal, Maximal
+--------------------------------------------------------------------}
+-- | /O(log n)/. The minimal element of a set.
+findMin::USa=>USeta->a
+findMin(view->Bin_x(null->True)_)=x
+findMin(view->Bin__l_)=findMinl
+findMin_=error"Set.findMin: empty set has no minimal element"
+
+-- | /O(log n)/. The maximal element of a set.
+findMax::USa=>USeta->a
+findMax(view->Bin_x_(null->True))=x
+findMax(view->Bin___r)=findMaxr
+findMax_=error"Set.findMax: empty set has no maximal element"
+
+-- | /O(log n)/. Delete the minimal element.
+deleteMin::USa=>USeta->USeta
+deleteMin(view->Bin__(null->True)r)=r
+deleteMin(view->Bin_xlr)=balancex(deleteMinl)r
+deleteMin_=tip
+
+-- | /O(log n)/. Delete the maximal element.
+deleteMax::USa=>USeta->USeta
+deleteMax(view->Bin__l(null->True))=l
+deleteMax(view->Bin_xlr)=balancexl(deleteMaxr)
+deleteMax_=tip
+
+{--------------------------------------------------------------------
+ Union.
+--------------------------------------------------------------------}
+-- | The union of a list of sets: (@'unions' == 'foldl' 'union' 'empty'@).
+unions::(USa,Orda)=>[USeta]->USeta
+unionsts
+=foldlStrictunionemptyts
+
+
+-- | /O(n+m)/. The union of two sets, preferring the first set when
+-- equal elements are encountered.
+-- The implementation uses the efficient /hedge-union/ algorithm.
+-- Hedge-union is more efficient on (bigset `union` smallset).
+union::(USa,Orda)=>USeta->USeta->USeta
+union(null->True)t2=t2
+uniont1(null->True)=t1
+uniont1t2=hedgeUnion(constLT)(constGT)t1t2
+
+hedgeUnion::(USa,Orda)=>(a->Ordering)->(a->Ordering)->USeta->USeta->USeta
+hedgeUnion__t1(null->True)=t1
+hedgeUnioncmplocmphi(null->True)(view->Bin_xlr)=joinx(filterGtcmplol)(filterLtcmphir)
+hedgeUnioncmplocmphi(view->Bin_xlr)t2=joinx(hedgeUnioncmplocmpxl(trimcmplocmpxt2))(hedgeUnioncmpxcmphir(trimcmpxcmphit2))
+where
+cmpx=comparex
+
+{--------------------------------------------------------------------
+ Difference
+--------------------------------------------------------------------}
+-- | /O(n+m)/. Difference of two sets.
+-- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.
+difference::(USa,Orda)=>USeta->USeta->USeta
+difference(null->True)_=tip
+differencet1(null->True)=t1
+differencet1t2=hedgeDiff(constLT)(constGT)t1t2
+
+hedgeDiff::(USa,Orda)=>(a->Ordering)->(a->Ordering)->USeta->USeta->USeta
+hedgeDiff__(null->True)_=tip
+hedgeDiffcmplocmphi(view->Bin_xlr)(null->True)=joinx(filterGtcmplol)(filterLtcmphir)
+hedgeDiffcmplocmphit(view->Bin_xlr)=merge(hedgeDiffcmplocmpx(trimcmplocmpxt)l)(hedgeDiffcmpxcmphi(trimcmpxcmphit)r)
+where
+cmpx=comparex
+
+{--------------------------------------------------------------------
+ Intersection
+--------------------------------------------------------------------}
+-- | /O(n+m)/. The intersection of two sets.
+-- Elements of the result come from the first set, so for example
+--
+-- > import qualified Data.Set as S
+-- > data AB = A | B deriving Show
+-- > instance Ord AB where compare _ _ = EQ
+-- > instance Eq AB where _ == _ = True
+-- > main = print (S.singleton A `S.intersection` S.singleton B,
+-- > S.singleton B `S.intersection` S.singleton A)
+--
+-- prints @(fromList [A],fromList [B])@.
+intersection::(USa,Orda)=>USeta->USeta->USeta
+intersection(null->True)_=tip
+intersection_(null->True)=tip
+intersectiont1@(view->Bins1x1l1r1)t2@(view->Bins2x2l2r2)=
+ifs1>=s2then
+let(lt,found,gt)=splitLookupx2t1
+tl=intersectionltl2
+tr=intersectiongtr2
+incasefoundof
+Justx->joinxtltr
+Nothing->mergetltr
+elselet(lt,found,gt)=splitMemberx1t2
+tl=intersectionl1lt
+tr=intersectionr1gt
+iniffoundthenjoinx1tltr
+elsemergetltr
+
+{--------------------------------------------------------------------
+ Filter and partition
+--------------------------------------------------------------------}
+-- | /O(n)/. Filter all elements that satisfy the predicate.
+filter::(USa,Orda)=>(a->Bool)->USeta->USeta
+filterp=gowhere
+go=viewktip
+(\_xlr->
+ifpx
+thenjoinx(gol)(gor)
+elsemerge(gol)(gor)
+)
+
+-- | /O(n)/. Partition the set into two sets, one with all elements that satisfy
+-- the predicate and one with all elements that don't satisfy the predicate.
+-- See also 'split'.
+partition::(USa,Orda)=>(a->Bool)->USeta->(USeta,USeta)
+partitionp=gowhere
+go=viewk(tip,tip)
+(\_xlr->
+let
+(l1,l2)=gol
+(r1,r2)=gor
+inifpx
+then(joinxl1r1,mergel2r2)
+else(mergel1r1,joinxl2r2)
+)
+
+{----------------------------------------------------------------------
+ Map
+----------------------------------------------------------------------}
+
+-- | /O(n*log n)/.
+-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
+--
+-- It's worth noting that the size of the result may be smaller if,
+-- for some @(x,y)@, @x \/= y && f x == f y@
+
+map::(USa,USb,Orda,Ordb)=>(a->b)->USeta->USetb
+mapf=fromList.List.mapf.toList
+
+-- | /O(n)/. The
+--
+-- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is monotonic.
+-- /The precondition is not checked./
+-- Semi-formally, we have:
+--
+-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
+-- > ==> mapMonotonic f s == map f s
+-- > where ls = toList s
+
+mapMonotonic::(USa,USb)=>(a->b)->USeta->USetb
+mapMonotonicf(view->Binszxlr)=binsz(fx)(mapMonotonicfl)(mapMonotonicfr)
+mapMonotonic__=tip
+
+
+{--------------------------------------------------------------------
+ Fold
+--------------------------------------------------------------------}
+-- | /O(n)/. Fold over the elements of a set in an unspecified order.
+fold::USa=>(a->b->b)->b->USeta->b
+foldfzs=foldrfzs
+
+-- | /O(n)/. Post-order fold.
+foldr::USa=>(a->b->b)->b->USeta->b
+--foldr f z (view -> Bin _ x l r) = foldr f (f x (foldr f z r)) l
+--foldr _ z _ = z
+
+foldrfzx|nullx=z
+|(#x,l,r#)<-viewBinx=foldrf(fx(foldrfzr))l
+{-# INLINE foldr #-}
+
+{--------------------------------------------------------------------
+ List variations
+--------------------------------------------------------------------}
+-- | /O(n)/. The elements of a set.
+elems::USa=>USeta->[a]
+elemsx=toListx
+
+{--------------------------------------------------------------------
+ Lists
+--------------------------------------------------------------------}
+-- | /O(n)/. Convert the set to a list of elements.
+toList::USa=>USeta->[a]
+toListx=toAscListx
+{-# INLINE toList #-}
+
+-- | /O(n)/. Convert the set to an ascending list of elements.
+toAscList::USa=>USeta->[a]
+toAscList=foldr(:)[]
+
+
+-- | /O(n*log n)/. Create a set from a list of elements.
+fromList::(USa,Orda)=>[a]->USeta
+fromList=foldlStrictinsempty
+where
+instx=insertxt
+
+{--------------------------------------------------------------------
+ Building trees from ascending/descending lists can be done in linear time.
+
+ Note that if [xs] is ascending that:
+ fromAscList xs == fromList xs
+--------------------------------------------------------------------}
+-- | /O(n)/. Build a set from an ascending list in linear time.
+-- /The precondition (input list is ascending) is not checked./
+fromAscList::(USa,Eqa)=>[a]->USeta
+fromAscListxs
+=fromDistinctAscList(combineEqxs)
+where
+-- [combineEq xs] combines equal elements with [const] in an ordered list [xs]
+combineEqxs'
+=casexs'of
+[]->[]
+[x]->[x]
+(x:xx)->combineEq'xxx
+
+combineEq'z[]=[z]
+combineEq'z(x:xs')
+|z==x=combineEq'zxs'
+|otherwise=z:combineEq'xxs'
+
+
+-- | /O(n)/. Build a set from an ascending list of distinct elements in linear time.
+-- /The precondition (input list is strictly ascending) is not checked./
+fromDistinctAscList::USa=>[a]->USeta
+fromDistinctAscListxs
+=buildconst(lengthxs)xs
+where
+-- 1) use continutations so that we use heap space instead of stack space.
+-- 2) special case for n==5 to build bushier trees.
+buildc0xs'=ctipxs'
+buildc5xs'=casexs'of
+(x1:x2:x3:x4:x5:xx)
+->c(bin_x4(bin_x2(singletonx1)(singletonx3))(singletonx5))xx
+_->error"fromDistinctAscList build 5"
+buildcnxs'=seqnr$build(buildRnrc)nlxs'
+where
+nl=n`div`2
+nr=n-nl-1
+
+buildRncl(x:ys)=build(buildBlxc)nys
+buildR___[]=error"fromDistinctAscList buildR []"
+buildBlxcrzs=c(bin_xlr)zs
+
+{--------------------------------------------------------------------
+ Eq converts the set to a list. In a lazy setting, this
+ actually seems one of the faster methods to compare two trees
+ and it is certainly the simplest :-)
+--------------------------------------------------------------------}
+instance(USa,Eqa)=>Eq(USeta)where
+t1==t2=(sizet1==sizet2)&&(toAscListt1==toAscListt2)
+
+{--------------------------------------------------------------------
+ Ord
+--------------------------------------------------------------------}
+
+instance(USa,Orda)=>Ord(USeta)where
+compares1s2=compare(toAscLists1)(toAscLists2)
+
+{--------------------------------------------------------------------
+ Show
+--------------------------------------------------------------------}
+instance(USa,Showa)=>Show(USeta)where
+showsPrecpxs=showParen(p>10)$
+showString"fromList ".shows(toListxs)
+
+{--------------------------------------------------------------------
+ Read
+--------------------------------------------------------------------}
+instance(USa,Reada,Orda)=>Read(USeta)where
+#ifdef __GLASGOW_HASKELL__
+readPrec=parens$prec10$do
+Ident"fromList"<-lexP
+fromList`fmap`readPrec
+
+readListPrec=readListPrecDefault
+#else
+readsPrecp=readParen(p>10)$\r->do
+("fromList",s)<-lexr
+(xs,t)<-readss
+return(fromListxs,t)
+#endif
+
+{--------------------------------------------------------------------
+ Utility functions that return sub-ranges of the original
+ tree. Some functions take a comparison function as argument to
+ allow comparisons against infinite values. A function [cmplo x]
+ should be read as [compare lo x].
+
+ [trim cmplo cmphi t] A tree that is either empty or where [cmplo x == LT]
+ and [cmphi x == GT] for the value [x] of the root.
+ [filterGt cmp t] A tree where for all values [k]. [cmp k == LT]
+ [filterLt cmp t] A tree where for all values [k]. [cmp k == GT]
+
+ [split k t] Returns two trees [l] and [r] where all values
+ in [l] are <[k] and all keys in [r] are >[k].
+ [splitMember k t] Just like [split] but also returns whether [k]
+ was found in the tree.
+--------------------------------------------------------------------}
+
+{--------------------------------------------------------------------
+ [trim lo hi t] trims away all subtrees that surely contain no
+ values between the range [lo] to [hi]. The returned tree is either
+ empty or the key of the root is between @lo@ and @hi@.
+--------------------------------------------------------------------}
+trim::USa=>(a->Ordering)->(a->Ordering)->USeta->USeta
+trimcmplocmphit@(view->Bin_xlr)
+=casecmploxof
+LT->casecmphixof
+GT->t
+_->trimcmplocmphil
+_->trimcmplocmphir
+trim___=tip
+
+{--------------------------------------------------------------------
+ [filterGt x t] filter all values >[x] from tree [t]
+ [filterLt x t] filter all values <[x] from tree [t]
+--------------------------------------------------------------------}
+filterGt::USa=>(a->Ordering)->USeta->USeta
+filterGtcmp(view->Bin_xlr)
+=casecmpxof
+LT->joinx(filterGtcmpl)r
+GT->filterGtcmpr
+EQ->r
+filterGt__=tip
+
+filterLt::USa=>(a->Ordering)->USeta->USeta
+filterLtcmp(view->Bin_xlr)
+=casecmpxof
+LT->filterLtcmpl
+GT->joinxl(filterLtcmpr)
+EQ->l
+filterLt__=tip
+
+
+{--------------------------------------------------------------------
+ Split
+--------------------------------------------------------------------}
+-- | /O(log n)/. The expression (@'split' x set@) is a pair @(set1,set2)@
+-- where @set1@ comprises the elements of @set@ less than @x@ and @set2@
+-- comprises the elements of @set@ greater than @x@.
+split::(USa,Orda)=>a->USeta->(USeta,USeta)
+splitx(view->Bin_ylr)
+=casecomparexyof
+LT->let(lt,gt)=splitxlin(lt,joinygtr)
+GT->let(lt,gt)=splitxrin(joinyllt,gt)
+EQ->(l,r)
+split__=(tip,tip)
+
+-- | /O(log n)/. Performs a 'split' but also returns whether the pivot
+-- element was found in the original set.
+splitMember::(USa,Orda)=>a->USeta->(USeta,Bool,USeta)
+splitMemberxt=let(l,m,r)=splitLookupxtin
+(l,maybeFalse(constTrue)m,r)
+
+-- | /O(log n)/. Performs a 'split' but also returns the pivot
+-- element that was found in the original set.
+splitLookup::(USa,Orda)=>a->USeta->(USeta,Maybea,USeta)
+splitLookupx(view->Bin_ylr)
+=casecomparexyof
+LT->let(lt,found,gt)=splitLookupxlin(lt,found,joinygtr)
+GT->let(lt,found,gt)=splitLookupxrin(joinyllt,found,gt)
+EQ->(l,Justy,r)
+splitLookup__=(tip,Nothing,tip)
+
+{--------------------------------------------------------------------
+ Utility functions that maintain the balance properties of the tree.
+ All constructors assume that all values in [l] < [x] and all values
+ in [r] > [x], and that [l] and [r] are valid trees.
+
+ In order of sophistication:
+ [Bin sz x l r] The type constructor.
+ [bin_ x l r] Maintains the correct size, assumes that both [l]
+ and [r] are balanced with respect to each other.
+ [balance x l r] Restores the balance and size.
+ Assumes that the original tree was balanced and
+ that [l] or [r] has changed by at most one element.
+ [join x l r] Restores balance and size.
+
+ Furthermore, we can construct a new tree from two trees. Both operations
+ assume that all values in [l] < all values in [r] and that [l] and [r]
+ are valid:
+ [glue l r] Glues [l] and [r] together. Assumes that [l] and
+ [r] are already balanced with respect to each other.
+ [merge l r] Merges two trees and restores balance.
+
+ Note: in contrast to Adam's paper, we use (<=) comparisons instead
+ of (<) comparisons in [join], [merge] and [balance].
+ Quickcheck (on [difference]) showed that this was necessary in order
+ to maintain the invariants. It is quite unsatisfactory that I haven't
+ been able to find out why this is actually the case! Fortunately, it
+ doesn't hurt to be a bit more conservative.
+--------------------------------------------------------------------}
+
+{--------------------------------------------------------------------
+ Join
+--------------------------------------------------------------------}
+join::USa=>a->USeta->USeta->USeta
+joinx(null->True)r=insertMinxr
+joinxl(null->True)=insertMaxxl
+joinxl@(view->BinsizeLylyry)r@(view->BinsizeRzlzrz)
+|delta*sizeL<=sizeR=balancez(joinxllz)rz
+|delta*sizeR<=sizeL=balanceyly(joinxryr)
+|otherwise=bin_xlr
+
+
+-- insertMin and insertMax don't perform potentially expensive comparisons.
+insertMax,insertMin::USa=>a->USeta->USeta
+insertMaxxt
+=caseviewtof
+Bin_ylr->balanceyl(insertMaxxr)
+_->singletonx
+
+insertMinxt
+=caseviewtof
+Bin_ylr->balancey(insertMinxl)r
+_->singletonx
+
+{--------------------------------------------------------------------
+ [merge l r]: merges two trees.
+--------------------------------------------------------------------}
+merge::USa=>USeta->USeta->USeta
+merge(null->True)r=r
+mergel(null->True)=l
+mergel@(view->BinsizeLxlxrx)r@(view->BinsizeRylyry)
+|delta*sizeL<=sizeR=balancey(mergelly)ry
+|delta*sizeR<=sizeL=balancexlx(mergerxr)
+|otherwise=gluelr
+
+{--------------------------------------------------------------------
+ [glue l r]: glues two trees together.
+ Assumes that [l] and [r] are already balanced with respect to each other.
+--------------------------------------------------------------------}
+glue::USa=>USeta->USeta->USeta
+glue(null->True)r=r
+gluel(null->True)=l
+gluelr
+|sizel>sizer=let(m,l')=deleteFindMaxlinbalanceml'r
+|otherwise=let(m,r')=deleteFindMinrinbalancemlr'
+
+
+-- | /O(log n)/. Delete and find the minimal element.
+--
+-- > deleteFindMin set = (findMin set, deleteMin set)
+
+deleteFindMin::USa=>USeta->(a,USeta)
+deleteFindMint
+=caseviewtof
+Bin_x(null->True)r->(x,r)
+Bin_xlr->let(xm,l')=deleteFindMinlin(xm,balancexl'r)
+Tip->(error"Set.deleteFindMin: can not return the minimal element of an empty set",tip)
+
+-- | /O(log n)/. Delete and find the maximal element.
+--
+-- > deleteFindMax set = (findMax set, deleteMax set)
+deleteFindMax::USa=>USeta->(a,USeta)
+deleteFindMaxt
+=caseviewtof
+Bin_xl(null->True)->(x,l)
+Bin_xlr->let(xm,r')=deleteFindMaxrin(xm,balancexlr')
+_->(error"Set.deleteFindMax: can not return the maximal element of an empty set",tip)
+
+-- | /O(log n)/. Retrieves the minimal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+minView::USa=>USeta->Maybe(a,USeta)
+minView(null->True)=Nothing
+minViewx=Just(deleteFindMinx)
+
+-- | /O(log n)/. Retrieves the maximal key of the set, and the set
+-- stripped of that element, or 'Nothing' if passed an empty set.
+maxView::USa=>USeta->Maybe(a,USeta)
+maxView(null->True)=Nothing
+maxViewx=Just(deleteFindMaxx)
+
+{--------------------------------------------------------------------
+ [balance x l r] balances two trees with value x.
+ The sizes of the trees should balance after decreasing the
+ size of one of them. (a rotation).
+
+ [delta] is the maximal relative difference between the sizes of
+ two trees, it corresponds with the [w] in Adams' paper,
+ or equivalently, [1/delta] corresponds with the $\alpha$
+ in Nievergelt's paper. Adams shows that [delta] should
+ be larger than 3.745 in order to garantee that the
+ rotations can always restore balance.
+
+ [ratio] is the ratio between an outer and inner sibling of the
+ heavier subtree in an unbalanced setting. It determines
+ whether a double or single rotation should be performed
+ to restore balance. It is correspondes with the inverse
+ of $\alpha$ in Adam's article.
+
+ Note that:
+ - [delta] should be larger than 4.646 with a [ratio] of 2.
+ - [delta] should be larger than 3.745 with a [ratio] of 1.534.
+
+ - A lower [delta] leads to a more 'perfectly' balanced tree.
+ - A higher [delta] performs less rebalancing.
+
+ - Balancing is automatic for random data and a balancing
+ scheme is only necessary to avoid pathological worst cases.
+ Almost any choice will do in practice
+
+ - Allthough it seems that a rather large [delta] may perform better
+ than smaller one, measurements have shown that the smallest [delta]
+ of 4 is actually the fastest on a wide range of operations. It
+ especially improves performance on worst-case scenarios like
+ a sequence of ordered insertions.
+
+ Note: in contrast to Adams' paper, we use a ratio of (at least) 2
+ to decide whether a single or double rotation is needed. Allthough
+ he actually proves that this ratio is needed to maintain the
+ invariants, his implementation uses a (invalid) ratio of 1.
+ He is aware of the problem though since he has put a comment in his
+ original source code that he doesn't care about generating a
+ slightly inbalanced tree since it doesn't seem to matter in practice.
+ However (since we use quickcheck :-) we will stick to strictly balanced
+ trees.
+--------------------------------------------------------------------}
+delta,ratio::Int
+delta=4
+ratio=2
+
+balance::USa=>a->USeta->USeta->USeta
+balancexlr
+|sizeL+sizeR<=1=binsizeXxlr
+|sizeR>=delta*sizeL=rotateLxlr
+|sizeL>=delta*sizeR=rotateRxlr
+|otherwise=binsizeXxlr
+where
+sizeL=sizel
+sizeR=sizer
+sizeX=sizeL+sizeR+1
+{-# SPECIALIZE balance :: Int -> USet Int -> USet Int -> USet Int #-}
+
+-- rotate
+rotateL::USa=>a->USeta->USeta->USeta
+rotateLxl(viewBin->(#v,ly,ry#))
+|sizely<ratio*sizery=singleLxlvlyry
+|otherwise=doubleLxlvlyry
+
+rotateR::USa=>a->USeta->USeta->USeta
+rotateRx(viewBin->(#v,ly,ry#))r
+|sizery<ratio*sizely=singleRxvlyryr
+|otherwise=doubleRxvlyryr
+
+singleL::USa=>a->USeta->a->USeta->USeta->USeta
+singleLx1t1x2t2t3
+=bin_x2(bin_x1t1t2)t3
+
+singleR::USa=>a->a->USeta->USeta->USeta->USeta
+singleRx1x2t1t2t3
+=bin_x2t1(bin_x1t2t3)
+
+doubleL::USa=>a->USeta->a->USeta->USeta->USeta
+doubleLx1t1x2(viewBin->(#x3,t2,t3#))t4
+=bin_x3(bin_x1t1t2)(bin_x2t3t4)
+
+doubleR::USa=>a->a->USeta->USeta->USeta->USeta
+doubleRx1x2t1(viewBin->(#x3,t2,t3#))t4
+=bin_x3(bin_x2t1t2)(bin_x1t3t4)
+
+{--------------------------------------------------------------------
+ The bin constructor maintains the size of the tree
+--------------------------------------------------------------------}
+bin_::USa=>a->USeta->USeta->USeta
+bin_xlr
+=bin(sizel+sizer+1)xlr
+{-# INLINE bin_ #-}
+
+
+{--------------------------------------------------------------------
+ Utilities
+--------------------------------------------------------------------}
+foldlStrict::(a->b->a)->a->[b]->a
+foldlStrictfzxs
+=casexsof
+[]->z
+(x:xx)->letz'=fzxinseqz'(foldlStrictfz'xx)
+
+
+{--------------------------------------------------------------------
+ Debugging
+--------------------------------------------------------------------}
+-- | /O(n)/. Show the tree that implements the set. The tree is shown
+-- in a compressed, hanging format.
+showTree::(USa,Showa)=>USeta->String
+showTrees
+=showTreeWithTrueFalses
+
+
+{- | /O(n)/. The expression (@showTreeWith hang wide map@) shows
+ the tree that implements the set. If @hang@ is
+ @True@, a /hanging/ tree is shown otherwise a rotated tree is shown. If
+ @wide@ is 'True', an extra wide version is shown.
+
+> Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
+> 4
+> +--2
+> | +--1
+> | +--3
+> +--5
+>
+> Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
+> 4
+> |
+> +--2
+> | |
+> | +--1
+> | |
+> | +--3
+> |
+> +--5
+>
+> Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+> +--5
+> |
+> 4
+> |
+> | +--3
+> | |
+> +--2
+> |
+> +--1
+
+-}
+showTreeWith::(USa,Showa)=>Bool->Bool->USeta->String
+showTreeWithhangwidet
+|hang=(showsTreeHangwide[]t)""
+|otherwise=(showsTreewide[][]t)""
+
+showsTree::(USa,Showa)=>Bool->[String]->[String]->USeta->ShowS
+showsTreewidelbarsrbarst
+=caseviewtof
+Tip->showsBarslbars.showString"|\n"
+Bin_x(null->True)(null->True)
+->showsBarslbars.showsx.showString"\n"
+Bin_xlr
+->showsTreewide(withBarrbars)(withEmptyrbars)r.
+showWidewiderbars.
+showsBarslbars.showsx.showString"\n".
+showWidewidelbars.
+showsTreewide(withEmptylbars)(withBarlbars)l
+
+showsTreeHang::(USa,Showa)=>Bool->[String]->USeta->ShowS
+showsTreeHangwidebarst
+=caseviewtof
+Tip->showsBarsbars.showString"|\n"
+Bin_x(null->True)(null->True)
+->showsBarsbars.showsx.showString"\n"
+Bin_xlr
+->showsBarsbars.showsx.showString"\n".
+showWidewidebars.
+showsTreeHangwide(withBarbars)l.
+showWidewidebars.
+showsTreeHangwide(withEmptybars)r
+
+showWide::Bool->[String]->String->String
+showWidewidebars
+|wide=showString(concat(reversebars)).showString"|\n"
+|otherwise=id
+
+showsBars::[String]->ShowS
+showsBarsbars
+=casebarsof
+[]->id
+_->showString(concat(reverse(tailbars))).showStringnode
+
+node::String
+node="+--"
+
+withBar,withEmpty::[String]->[String]
+withBarbars="| ":bars
+withEmptybars=" ":bars
+
+{--------------------------------------------------------------------
+ Assertions
+--------------------------------------------------------------------}
+-- | /O(n)/. Test if the internal set structure is valid.
+valid::(USa,Orda)=>USeta->Bool
+validt
+=balancedt&&orderedt&&validsizet
+
+ordered::(USa,Orda)=>USeta->Bool
+orderedt
+=bounded(constTrue)(constTrue)t
+where
+boundedlohit'
+=caseviewt'of
+Bin_xlr->(lox)&&(hix)&&boundedlo(<x)l&&bounded(>x)hir
+_->True
+
+balanced::USa=>USeta->Bool
+balancedt
+=caseviewtof
+Bin__lr->(sizel+sizer<=1||(sizel<=delta*sizer&&sizer<=delta*sizel))&&
+balancedl&&balancedr
+_->True
+
+validsize::USa=>USeta->Bool
+validsizet
+=(realsizet==Just(sizet))
+where
+realsizet'
+=caseviewt'of
+Binsz_lr->case(realsizel,realsizer)of
+(Justn,Justm)|n+m+1==sz->Justsz
+_->Nothing
+_->Just0
+
+{-
+{--------------------------------------------------------------------
+ Testing
+--------------------------------------------------------------------}
+testTree :: [Int] -> USet Int
+testTree xs = fromList xs
+test1 = testTree [1..20]
+test2 = testTree [30,29..10]
+test3 = testTree [1,4,6,89,2323,53,43,234,5,79,12,9,24,9,8,423,8,42,4,8,9,3]
+
+{--------------------------------------------------------------------
+ QuickCheck
+--------------------------------------------------------------------}
+
+{-
+qcheck prop
+ = check config prop
+ where
+ config = Config
+ { configMaxTest = 500
+ , configMaxFail = 5000
+ , configSize = \n -> (div n 2 + 3)
+ , configEvery = \n args -> let s = show n in s ++ [ '\b' | _ <- s ]
+ }
+-}
+
+
+{--------------------------------------------------------------------
+ Arbitrary, reasonably balanced trees
+--------------------------------------------------------------------}
+instance (US a, Enum a) => Arbitrary (USet a) where
+ arbitrary = sized (arbtree 0 maxkey)
+ where maxkey = 10000
+
+arbtree :: (US a, Enum a) => Int -> Int -> Int -> Gen (USet a)
+arbtree lo hi n
+ | n <= 0 = return tip
+ | lo >= hi = return tip
+ | otherwise = do{ i <- choose (lo,hi)
+ ; m <- choose (1,30)
+ ; let (ml,mr) | m==(1::Int)= (1,2)
+ | m==2 = (2,1)
+ | m==3 = (1,1)
+ | otherwise = (2,2)
+ ; l <- arbtree lo (i-1) (n `div` ml)
+ ; r <- arbtree (i+1) hi (n `div` mr)
+ ; return (bin_ (toEnum i) l r)
+ }
+
+
+{--------------------------------------------------------------------
+ Valid tree's
+--------------------------------------------------------------------}
+forValid :: (US a, Enum a,Show a,Testable b) => (USet a -> b) -> Property
+forValid f
+ = forAll arbitrary $ \t ->
+-- classify (balanced t) "balanced" $
+ classify (size t == 0) "empty" $
+ classify (size t > 0 && size t <= 10) "small" $
+ classify (size t > 10 && size t <= 64) "medium" $
+ classify (size t > 64) "large" $
+ balanced t ==> f t
+
+forValidIntTree :: Testable a => (USet Int -> a) -> Property
+forValidIntTree f
+ = forValid f
+
+forValidUnitTree :: Testable a => (USet Int -> a) -> Property
+forValidUnitTree f
+ = forValid f
+
+
+prop_Valid
+ = forValidUnitTree $ \t -> valid t
+
+{--------------------------------------------------------------------
+ Single, Insert, Delete
+--------------------------------------------------------------------}
+prop_Single :: Int -> Bool
+prop_Single x
+ = (insert x empty == singleton x)
+
+prop_InsertValid :: Int -> Property
+prop_InsertValid k
+ = forValidUnitTree $ \t -> valid (insert k t)
+
+prop_InsertDelete :: Int -> USet Int -> Property
+prop_InsertDelete k t
+ = not (member k t) ==> delete k (insert k t) == t
+
+prop_DeleteValid :: Int -> Property
+prop_DeleteValid k
+ = forValidUnitTree $ \t ->
+ valid (delete k (insert k t))
+
+{--------------------------------------------------------------------
+ Balance
+--------------------------------------------------------------------}
+prop_Join :: Int -> Property
+prop_Join x
+ = forValidUnitTree $ \t ->
+ let (l,r) = split x t
+ in valid (join x l r)
+
+prop_Merge :: Int -> Property
+prop_Merge x
+ = forValidUnitTree $ \t ->
+ let (l,r) = split x t
+ in valid (merge l r)
+
+
+{--------------------------------------------------------------------
+ Union
+--------------------------------------------------------------------}
+prop_UnionValid :: Property
+prop_UnionValid
+ = forValidUnitTree $ \t1 ->
+ forValidUnitTree $ \t2 ->
+ valid (union t1 t2)
+
+prop_UnionInsert :: Int -> USet Int -> Bool
+prop_UnionInsert x t
+ = union t (singleton x) == insert x t
+
+prop_UnionAssoc :: USet Int -> USet Int -> USet Int -> Bool
+prop_UnionAssoc t1 t2 t3
+ = union t1 (union t2 t3) == union (union t1 t2) t3
+
+prop_UnionComm :: USet Int -> USet Int -> Bool
+prop_UnionComm t1 t2
+ = (union t1 t2 == union t2 t1)
+
+
+prop_DiffValid
+ = forValidUnitTree $ \t1 ->
+ forValidUnitTree $ \t2 ->
+ valid (difference t1 t2)
+
+prop_Diff :: [Int] -> [Int] -> Bool
+prop_Diff xs ys
+ = toAscList (difference (fromList xs) (fromList ys))
+ == List.sort ((List.\\) (nub xs) (nub ys))
+
+prop_IntValid
+ = forValidUnitTree $ \t1 ->
+ forValidUnitTree $ \t2 ->
+ valid (intersection t1 t2)
+
+prop_Int :: [Int] -> [Int] -> Bool
+prop_Int xs ys
+ = toAscList (intersection (fromList xs) (fromList ys))
+ == List.sort (nub ((List.intersect) (xs) (ys)))
+
+{--------------------------------------------------------------------
+ Lists
+--------------------------------------------------------------------}
+prop_Ordered
+ = forAll (choose (5,100)) $ \n ->
+ let xs = [0..n::Int]
+ in fromAscList xs == fromList xs
+
+prop_List :: [Int] -> Bool
+prop_List xs
+ = (sort (nub xs) == toList (fromList xs))
+-}
+
+
+newtypeBoxeda=Boxedaderiving(Eq,Ord,Show,Read,Bounded)
+instanceUS(Boxeda)where
+dataUSet(Boxeda)=BoxedTip|BoxedBin{-# UNPACK #-}!Size(Boxeda)!(USet(Boxeda))!(USet(Boxeda))
+viewBoxedTip=Tip
+view(BoxedBinsilr)=Binsilr
+viewkt_BoxedTip=t
+viewk_k(BoxedBinsilr)=ksilr
+viewBin(BoxedBin_ilr)=(#i,l,r#)
+tip=BoxedTip
+bin=BoxedBin
+sizeBoxedTip=0
+size(BoxedBins___)=s
+nullBoxedTip=True
+null_=False
+
+instanceUSCharwhere
+dataUSetChar=CharTip|CharBin{-# UNPACK #-}!Size{-# UNPACK #-}!Char!(USetChar)!(USetChar)
+viewCharTip=Tip
+view(CharBinsilr)=Binsilr
+viewkt_CharTip=t
+viewk_k(CharBinsilr)=ksilr
+viewBin(CharBin_ilr)=(#i,l,r#)
+tip=CharTip
+bin=CharBin
+nullCharTip=True
+null_=False
+
+instanceUSIntwhere
+dataUSetInt=IntTip|IntBin{-# UNPACK #-}!Size{-# UNPACK #-}!Int!(USetInt)!(USetInt)
+viewIntTip=Tip
+view(IntBinsilr)=Binsilr
+viewkt_IntTip=t
+viewk_k(IntBinsilr)=ksilr
+viewBin(IntBin_ilr)=(#i,l,r#)
+sizeIntTip=0
+size(IntBins___)=s
+tip=IntTip
+bin=IntBin
+nullIntTip=True
+null_=False
+
+instanceUSIntegerwhere
+dataUSetInteger=IntegerTip|IntegerBin{-# UNPACK #-}!Size{-# UNPACK #-}!Integer!(USetInteger)!(USetInteger)
+viewIntegerTip=Tip
+view(IntegerBinsilr)=Binsilr
+viewkt_IntegerTip=t
+viewk_k(IntegerBinsilr)=ksilr
+viewBin(IntegerBin_ilr)=(#i,l,r#)
+tip=IntegerTip
+bin=IntegerBin
+nullIntegerTip=True
+null_=False
+
+instanceUSInt8where
+dataUSetInt8=Int8Tip|Int8Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Int8!(USetInt8)!(USetInt8)
+viewInt8Tip=Tip
+view(Int8Binsilr)=Binsilr
+viewkt_Int8Tip=t
+viewk_k(Int8Binsilr)=ksilr
+viewBin(Int8Bin_ilr)=(#i,l,r#)
+tip=Int8Tip
+bin=Int8Bin
+nullInt8Tip=True
+null_=False
+
+instanceUSInt16where
+dataUSetInt16=Int16Tip|Int16Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Int16!(USetInt16)!(USetInt16)
+viewInt16Tip=Tip
+view(Int16Binsilr)=Binsilr
+viewkt_Int16Tip=t
+viewk_k(Int16Binsilr)=ksilr
+viewBin(Int16Bin_ilr)=(#i,l,r#)
+tip=Int16Tip
+bin=Int16Bin
+nullInt16Tip=True
+null_=False
+
+instanceUSInt32where
+dataUSetInt32=Int32Tip|Int32Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Int32!(USetInt32)!(USetInt32)
+viewInt32Tip=Tip
+view(Int32Binsilr)=Binsilr
+viewkt_Int32Tip=t
+viewk_k(Int32Binsilr)=ksilr
+viewBin(Int32Bin_ilr)=(#i,l,r#)
+tip=Int32Tip
+bin=Int32Bin
+nullInt32Tip=True
+null_=False
+
+instanceUSInt64where
+dataUSetInt64=Int64Tip|Int64Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Int64!(USetInt64)!(USetInt64)
+viewInt64Tip=Tip
+view(Int64Binsilr)=Binsilr
+viewkt_Int64Tip=t
+viewk_k(Int64Binsilr)=ksilr
+viewBin(Int64Bin_ilr)=(#i,l,r#)
+tip=Int64Tip
+bin=Int64Bin
+nullInt64Tip=True
+null_=False
+
+instanceUSWord8where
+dataUSetWord8=Word8Tip|Word8Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Word8!(USetWord8)!(USetWord8)
+viewWord8Tip=Tip
+view(Word8Binsilr)=Binsilr
+viewkt_Word8Tip=t
+viewk_k(Word8Binsilr)=ksilr
+viewBin(Word8Bin_ilr)=(#i,l,r#)
+tip=Word8Tip
+bin=Word8Bin
+nullWord8Tip=True
+null_=False
+
+instanceUSWord16where
+dataUSetWord16=Word16Tip|Word16Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Word16!(USetWord16)!(USetWord16)
+viewWord16Tip=Tip
+view(Word16Binsilr)=Binsilr
+viewkt_Word16Tip=t
+viewk_k(Word16Binsilr)=ksilr
+viewBin(Word16Bin_ilr)=(#i,l,r#)
+bin=Word16Bin
+tip=Word16Tip
+nullWord16Tip=True
+null_=False
+
+instanceUSWord32where
+dataUSetWord32=Word32Tip|Word32Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Word32!(USetWord32)!(USetWord32)
+viewWord32Tip=Tip
+view(Word32Binsilr)=Binsilr
+viewkt_Word32Tip=t
+viewk_k(Word32Binsilr)=ksilr
+viewBin(Word32Bin_ilr)=(#i,l,r#)
+tip=Word32Tip
+bin=Word32Bin
+nullWord32Tip=True
+null_=False
+
+instanceUSWord64where
+dataUSetWord64=Word64Tip|Word64Bin{-# UNPACK #-}!Size{-# UNPACK #-}!Word64!(USetWord64)!(USetWord64)
+viewWord64Tip=Tip
+view(Word64Binsilr)=Binsilr
+viewkt_Word64Tip=t
+viewk_k(Word64Binsilr)=ksilr
+viewBin(Word64Bin_ilr)=(#i,l,r#)
+tip=Word64Tip
+bin=Word64Bin
+nullWord64Tip=True
+null_=False
+
+instanceUSDoublewhere
+dataUSetDouble=DoubleTip|DoubleBin{-# UNPACK #-}!Size{-# UNPACK #-}!Double!(USetDouble)!(USetDouble)
+viewDoubleTip=Tip
+view(DoubleBinsilr)=Binsilr
+viewkt_DoubleTip=t
+viewk_k(DoubleBinsilr)=ksilr
+viewBin(DoubleBin_ilr)=(#i,l,r#)
+tip=DoubleTip
+bin=DoubleBin
+nullDoubleTip=True
+null_=False
+
+instanceUSFloatwhere
+dataUSetFloat=FloatTip|FloatBin{-# UNPACK #-}!Size{-# UNPACK #-}!Float!(USetFloat)!(USetFloat)
+viewFloatTip=Tip
+view(FloatBinsilr)=Binsilr
+viewkt_FloatTip=t
+viewk_k(FloatBinsilr)=ksilr
+viewBin(FloatBin_ilr)=(#i,l,r#)
+tip=FloatTip
+bin=FloatBin
+nullFloatTip=True
+null_=False
+
+
Instances