mfi+      !"#$%&'()*(c) Sam T. 2013BSD3pxqr.sta@gmail.com experimentalportableNone+4 Monoid under . Don't mix up  with . Monoid under .You could use + from  as well. Monoid under . Used by default for .You could use , from  as well. Integer set.Empty set. Contains nothing.Layout: Prefix up to mask of bitmap sizea, and mask specifing how large is set. There is no branching bit at all. Tip is never full.IIntSet = Fin: contains all elements from prefix to (prefix - mask - 1)Layout: Prefix up to mask of bitmap size-, and bitmap containing elements starting from the prefix.IntSet = Tip: contains elements^Layout: prefix up to branching bit, mask for branching bit, left subtree and right subtree.IntSet = Bin: contains elements of left and right subtrees thus just merge to subtrees. All elements of left subtree is less that from right subtree. Except non-negative numbers, they are in left subtree of root bin, if any.Type of IntSet elements.-SBitmap is used to make intset dense. To achive this we throw away last bits 6 or 7 bits from any(!) prefix and thus any(!) mask should be more than word size in bits. Bitmap by itself contain flags which indicates "is an element present in a set?" by marking suffices indices. For exsample bitmap 01001010 contain elements 2, 5 and 7.OOne bitmap might contain up to word size in bits (depending on arch) elements..cMask is used to specify mask for branching bit. For exsample if we have mask 0000100 that means:-We do not consider last three bits in prefix.DBranching bit is at position 3 starting from least significant bit.1Prefix mask is 4 bits. (at left of the bitstring)/Prefix is used to distinguish subtrees by its prefix bits. When new prefix is created its non prefix bits are zeroed. Prefix is big endian. This means that we throw away only least significant bits0AThe following invariants should be hold in all subtrees of a set: + Nil is never child of Bin;@+ Bin is never contain two Fins with masks equal to mask of Bin;%- Mask becomes smaller at each child;-- Bin, Fin, Tip masks is always power of two;@+ Fin mask is always greater or equal than size of bits in word;b- Bin left subtree contains element each of which is less than each element of right subtree;+ Tip bitmap is never full;)+ Tip mask is multiple of word bit count;See 18 to find out when two intsets should be merged into one.TODO check 3, 4, 6 invariants O(1). Is this the empty set? O(n) or O(1). Cardinality of a set.  O(min(W, n)) or O(1)-. Test if the value is element of the set.  O(min(W, n)) or O(1)4. Test if the value is not an element of the set. O(n + m) or O(1)<. Test if the second set contain each element of the first.O(n + m) or O(1)1. Test if the second set is subset of the first.2O(n + m) or O(1)7. Test if the first set is proper subset of the other.3O(n + m) or O(1)8. Test if the second set is proper subset of the first.O(1). The empty set.O(1). A set containing one element.O(n)3. Set containing elements from the specified range. interval a b = fromList [a..b]4O(1)). The set containing all natural numbers.5O(1)*. The set containing all negative numbers.6O(1)7. The set containing the all integers it might contain. O(min(W, n) or O(1). Add a value to the set. O(min(n, W)). Delete a value from the set.71Chunk fin to buddies or to single tip in the end.O(n + m) or O(1)@. Find set which contains elements of both right and left sets.O(max(n)^2 * spine) or O(spine). The union of list of sets.O(n + m) or O(1)4. Find maximal common subset of the two given sets.O(max(n) * spine) or O(spine)0. Find out common subset of the list of sets.O(n + m) or O(1)". Find difference of the two sets.O(n + m) or O(1). Find symmetric difference of the two sets: resulting set containts elements that either in first or second set, but not in both simultaneous. O(min(W, n). Split the set such that the left projection of the resulting pair contains elements less than the key and right element contains greater than the key. The exact key is excluded from result: Asplit 5 (fromList [0..10]) == (fromList [0..4], fromList [6..10])^Performance note: if need only lesser or greater keys, use splitLT or splitGT respectively. O(min(W, n)p. Takes subset such that each element is greater than the specified key. The exact key is excluded from result. O(min(W, n)m. Takes subset such that each element is less than the specified key. The exact key is excluded from result.O(n)$. Split a set using given predicate. Uforall f. fst . partition f = filter f forall f. snd . partition f = filter (not . f) O(min(W, n)) or O(1)L. Find minimal element of the set. If set is empty then min is undefined. O(min(W, n)) or O(1)K. Find maximal element of the set. Is set is empty then max is undefined. O(n * min(W, n))3. Apply the function to each element of the set.#Do not use this operation with the 6, 4 or 5 sets.!O(n)I. Fold the element using the given right associative binary operator."O(n)1. Filter all elements that satisfy the predicate.#Do not use this operation with the 6, 4 or 5 sets.#O(n * min(W, n)) or O(n)-. Create a set from a list of its elements.$O(n),. Convert the set to a list of its elements.%% is alias to $ for compatibility.&O(n)@. Convert the set to a list of its element in ascending order.'O(n)A. Convert the set to a list of its element in descending order.(/Build a set from an ascending list of elements.80Return a word where only the highest bit is set.9:;<=>?@A-./0 B23C456DE7FGHIJKLMNOPQRSTUVWX !"Y#$%&'(Z[\1]^_`abcdefghijklmnopqrstuvw8xyz{|}~K-./0 23456D7GIJMN !"#$%&'(Z[\^`abceghijkrsty{9:;<=>?@A-./0 B23C456DE7FGHIJKLMNOPQRSTUVWX !"Y#$%&'(Z[\1]^_`abcdefghijklmnopqrstuvw8xyz{|}~(c) Sam T. 2013BSD3pxqr.sta@gmail.com experimentallittle endian archNone)Unpack  from bitmap.* Pack the $ as bitmap to the strict bytestring.$NOTE: negative elements are ignored!)*)*)*)*(c) Sam T. 2013BSD3pxqr.sta@gmail.com experimentalportableNone)  !"#$%&'()  !"%$#&'(      !"#$%&'()*+,-./012312456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~intset-0.1.0.0Data.IntervalSetData.IntervalSet.ByteStringData.IntervalSet.InternalDataMonoid Difference IntersectionUnionIntSetNilFinTipBinKeynullsizemember notMember isSubsetOf isSupersetOfempty singletonintervalinsertdeleteunionunions intersection intersections differencesymDiffsplitsplitGTsplitLT partitionfindMinfindMaxmapfoldrfilterfromListtoListelems toAscList toDescList fromAscListfromByteString toByteStringbase Data.MonoidProductSumBitMapMaskPrefixisValidbinIisProperSubsetOfisProperSupersetOfnaturals negativesuniversesplitFinhighestBitMaskNatSPair:*: getDifferencegetIntersectiongetUnion isSubsetOfBM intervalBMinsertBMdeleteBM complement insertFinisBuddyproperSubsetOfunionBM intersectFin finSubsetOf intersectBMsymDiff' symDiffTip symDiffFinunStrictsplitBM splitBMGT splitBMLT findMinBM findMaxBMstreamunstreamlistFintipItipDtipbinDbinjoinbinCounttipCountfinCount wordCountorigSize savedSpacebsSizeppStatsshowTreeshowRawputTreeputRaw foldrBits filterBitMapisFull natFromInt intFromNatzeromaskmatchnomatchshorter shorterEq branchMaskmaskWfinMask suffixBitMask prefixBitMaskprefixOfsuffixOfbitmapOfSuffixbitmapOf$fMonoidDifference$fMonoidIntersection $fMonoidUnion$fNFDataIntSet$fBoundedIntSet $fNumIntSet$fMonoidIntSet $fOrdIntSet $fReadIntSet $fShowIntSet foldrWord