- data IntSet
- (\\) :: IntSet -> IntSet -> IntSet
- isEmpty :: IntSet -> Bool
- size :: IntSet -> Int
- member :: Int -> IntSet -> Bool
- subset :: IntSet -> IntSet -> Bool
- properSubset :: IntSet -> IntSet -> Bool
- empty :: IntSet
- single :: Int -> IntSet
- insert :: Int -> IntSet -> IntSet
- delete :: Int -> IntSet -> IntSet
- union :: IntSet -> IntSet -> IntSet
- unions :: [IntSet] -> IntSet
- difference :: IntSet -> IntSet -> IntSet
- intersection :: IntSet -> IntSet -> IntSet
- filter :: (Int -> Bool) -> IntSet -> IntSet
- partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)
- split :: Int -> IntSet -> (IntSet, IntSet)
- splitMember :: Int -> IntSet -> (Bool, IntSet, IntSet)
- fold :: (Int -> b -> b) -> b -> IntSet -> b
- elems :: IntSet -> [Int]
- toList :: IntSet -> [Int]
- fromList :: [Int] -> IntSet
- toAscList :: IntSet -> [Int]
- fromAscList :: [Int] -> IntSet
- fromDistinctAscList :: [Int] -> IntSet
- showTree :: IntSet -> String
- showTreeWith :: Bool -> Bool -> IntSet -> String

# Set type

# Operators

# Query

properSubset :: IntSet -> IntSet -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

# Construction

insert :: Int -> IntSet -> IntSetSource

*O(min(n,W))*. Add a value to the set. When the value is already
an element of the set, it is replaced by the new one, ie. `insert`

is left-biased.

delete :: Int -> IntSet -> IntSetSource

*O(min(n,W))*. Delete a value in the set. Returns the
original set when the value was not present.

# Combine

difference :: IntSet -> IntSet -> IntSetSource

*O(n+m)*. Difference between two sets.

intersection :: IntSet -> IntSet -> IntSetSource

*O(n+m)*. The intersection of two sets.

# Filter

filter :: (Int -> Bool) -> IntSet -> IntSetSource

*O(n)*. Filter all elements that satisfy some predicate.

partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)Source

*O(n)*. partition the set according to some predicate.

split :: Int -> IntSet -> (IntSet, IntSet)Source

*O(log n)*. The expression (`split x set`

) is a pair `(set1,set2)`

where all elements in `set1`

are lower than `x`

and all elements in
`set2`

larger than `x`

.

splitMember :: Int -> IntSet -> (Bool, IntSet, IntSet)Source

*O(log n)*. Performs a `split`

but also returns whether the pivot
element was found in the original set.

# Fold

fold :: (Int -> b -> b) -> b -> IntSet -> bSource

*O(n)*. Fold over the elements of a set in an unspecified order.

sum set = fold (+) 0 set elems set = fold (:) [] set

# Conversion

## List

## Ordered list

fromAscList :: [Int] -> IntSetSource

*O(n*min(n,W))*. Build a set from an ascending list of elements.

fromDistinctAscList :: [Int] -> IntSetSource

*O(n*min(n,W))*. Build a set from an ascending list of distinct elements.