uulib-0.9.5: Haskell Utrecht Tools LibraryContentsIndex
UU.DData.IntBag
Contents
Bag type
Operators
Query
Construction
Combine
Filter
Fold
Conversion
List
Ordered list
Occurrence lists
IntMap
Debugging
Description
Synopsis
data IntBag
(\\) :: IntBag -> IntBag -> IntBag
isEmpty :: IntBag -> Bool
size :: IntBag -> Int
distinctSize :: IntBag -> Int
member :: Int -> IntBag -> Bool
occur :: Int -> IntBag -> Int
subset :: IntBag -> IntBag -> Bool
properSubset :: IntBag -> IntBag -> Bool
empty :: IntBag
single :: Int -> IntBag
insert :: Int -> IntBag -> IntBag
insertMany :: Int -> Int -> IntBag -> IntBag
delete :: Int -> IntBag -> IntBag
deleteAll :: Int -> IntBag -> IntBag
union :: IntBag -> IntBag -> IntBag
difference :: IntBag -> IntBag -> IntBag
intersection :: IntBag -> IntBag -> IntBag
unions :: [IntBag] -> IntBag
filter :: (Int -> Bool) -> IntBag -> IntBag
partition :: (Int -> Bool) -> IntBag -> (IntBag, IntBag)
fold :: (Int -> b -> b) -> b -> IntBag -> b
foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> b
elems :: IntBag -> [Int]
toList :: IntBag -> [Int]
fromList :: [Int] -> IntBag
toAscList :: IntBag -> [Int]
fromAscList :: [Int] -> IntBag
fromDistinctAscList :: [Int] -> IntBag
toOccurList :: IntBag -> [(Int, Int)]
toAscOccurList :: IntBag -> [(Int, Int)]
fromOccurList :: [(Int, Int)] -> IntBag
fromAscOccurList :: [(Int, Int)] -> IntBag
toMap :: IntBag -> IntMap Int
fromMap :: IntMap Int -> IntBag
fromOccurMap :: IntMap Int -> IntBag
showTree :: IntBag -> String
showTreeWith :: Bool -> Bool -> IntBag -> String
Bag type
data IntBag
A bag of integers.
show/hide Instances
Operators
(\\) :: IntBag -> IntBag -> IntBag
O(n+m). See difference.
Query
isEmpty :: IntBag -> Bool
O(1). Is the bag empty?
size :: IntBag -> Int
O(n). The number of elements in the bag.
distinctSize :: IntBag -> Int
O(n). Returns the number of distinct elements in the bag, ie. (distinctSize bag == length (nub (toList bag))).
member :: Int -> IntBag -> Bool
O(min(n,W)). Is the element in the bag?
occur :: Int -> IntBag -> Int
O(min(n,W)). The number of occurrences of an element in the bag.
subset :: IntBag -> IntBag -> Bool
O(n+m). Is this a subset of the bag?
properSubset :: IntBag -> IntBag -> Bool
O(n+m). Is this a proper subset? (ie. a subset and not equal)
Construction
empty :: IntBag
O(1). Create an empty bag.
single :: Int -> IntBag
O(1). Create a singleton bag.
insert :: Int -> IntBag -> IntBag
O(min(n,W)). Insert an element in the bag.
insertMany :: Int -> Int -> IntBag -> IntBag
O(min(n,W)). The expression (insertMany x count bag) inserts count instances of x in the bag bag.
delete :: Int -> IntBag -> IntBag
O(min(n,W)). Delete a single element.
deleteAll :: Int -> IntBag -> IntBag
O(min(n,W)). Delete all occurrences of an element.
Combine
union :: IntBag -> IntBag -> IntBag

O(n+m). Union of two bags. The union adds the elements together.

 IntBag\> union (fromList [1,1,2]) (fromList [1,2,2,3])
 {1,1,1,2,2,2,3}
difference :: IntBag -> IntBag -> IntBag

O(n+m). Difference between two bags.

 IntBag\> difference (fromList [1,1,2]) (fromList [1,2,2,3])
 {1}
intersection :: IntBag -> IntBag -> IntBag

O(n+m). Intersection of two bags.

 IntBag\> intersection (fromList [1,1,2]) (fromList [1,2,2,3])
 {1,2}
unions :: [IntBag] -> IntBag
The union of a list of bags.
Filter
filter :: (Int -> Bool) -> IntBag -> IntBag
O(n). Filter all elements that satisfy some predicate.
partition :: (Int -> Bool) -> IntBag -> (IntBag, IntBag)
O(n). Partition the bag according to some predicate.
Fold
fold :: (Int -> b -> b) -> b -> IntBag -> b
O(n). Fold over each element in the bag.
foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> b
O(n). Fold over all occurrences of an element at once. In a call (foldOccur f z bag), the function f takes the element first and than the occur count.
Conversion
elems :: IntBag -> [Int]
O(n). The list of elements.
List
toList :: IntBag -> [Int]
O(n). Create a list with all elements.
fromList :: [Int] -> IntBag
O(n*min(n,W)). Create a bag from a list of elements.
Ordered list
toAscList :: IntBag -> [Int]
O(n). Create an ascending list of all elements.
fromAscList :: [Int] -> IntBag
O(n*min(n,W)). Create a bag from an ascending list.
fromDistinctAscList :: [Int] -> IntBag
O(n*min(n,W)). Create a bag from an ascending list of distinct elements.
Occurrence lists
toOccurList :: IntBag -> [(Int, Int)]
O(n). Create a list of element/occurrence pairs.
toAscOccurList :: IntBag -> [(Int, Int)]
O(n). Create an ascending list of element/occurrence pairs.
fromOccurList :: [(Int, Int)] -> IntBag
O(n*min(n,W)). Create a bag from a list of element/occurrence pairs.
fromAscOccurList :: [(Int, Int)] -> IntBag
O(n*min(n,W)). Create a bag from an ascending list of element/occurrence pairs.
IntMap
toMap :: IntBag -> IntMap Int
O(1). Convert to an IntMap from elements to number of occurrences.
fromMap :: IntMap Int -> IntBag
O(n). Convert a IntMap from elements to occurrences into a bag.
fromOccurMap :: IntMap Int -> IntBag
O(1). Convert a IntMap from elements to occurrences into a bag. Assumes that the IntMap contains only elements that occur at least once.
Debugging
showTree :: IntBag -> String
O(n). Show the tree structure that implements the IntBag. The tree is shown as a compressed and hanging.
showTreeWith :: Bool -> Bool -> IntBag -> String
O(n). The expression (showTreeWith hang wide map) shows the tree that implements the bag. The tree is shown hanging when hang is True and otherwise as a rotated tree. When wide is True an extra wide version is shown.
Produced by Haddock version 0.8