A set of unboxed ShortText strings

The memory footprint of this data-structure is a single heap object (an unlifted ByteArray#) with the size expressed in words

\[ 3 + n + \left\lceil \frac{1}{w} \sum_{i=0}^{n-1} len(s_i) \right\rceil \]

where the word-size \(w\) is either \(w = 4\) or \(w = 8\) bytes; and where \(len(s_i)\) denotes the UTF-8 size in bytes of the \(i\)-th text string.

NOTE: Depending on whether you UNPACK the TextSet wrapper, you need at least one additional word for the pointer to the internal ByteArray# heap object.

\(\mathcal{O}(1)\). Report number of elements in TextSet.

>>> size empty
0

>>> size (singleton "")
1

>>> size (fromList ["Hey","Hey","Jude"])
2

\(\mathcal{O}(1)\). Check for empty set.

>>> null empty
True

>>> null (singleton "")
False

\(\mathcal{O}(\log n)\). Test whether set contains a string.

>>> member "empty" empty
False

>>> member "a" (fromList ["a","b","c"])
True

>>> member "d" (fromList ["a","b","c"])
False

\(\mathcal{O}(1)\). Extract minimal element from set.

>>> lookupMin empty
Nothing

>>> lookupMin (fromList ["a","b","c"])
Just "a"

\(\mathcal{O}(1)\). Extract maximal element from set.

>>> lookupMax empty
Nothing

>>> lookupMax (fromList ["a","b","c"])
Just "c"

\(\mathcal{O}(\log n)\). Look up "greatest" string (together with its index) in set less or equal to given string.

>>> lookupLE "a" (fromList ["bb","cc"])
Nothing

>>> lookupLE "c" (fromList ["bb","cc"])
Just (0,"bb")

>>> lookupLE "cc" (fromList ["bb","cc"])
Just (1,"cc")

>>> lookupLE "z" (fromList ["bb","cc"])
Just (1,"cc")

\(\mathcal{O}(\log n)\). Look up "least" string (together with its index) in set greater or equal to given string.

>>> lookupGE "a" (fromList ["bb","cc"])
Just (0,"bb")

>>> lookupGE "c" (fromList ["bb","cc"])
Just (1,"cc")

>>> lookupGE "cc" (fromList ["bb","cc"])
Just (1,"cc")

>>> lookupGE "z" (fromList ["bb","cc"])
Nothing

\(\mathcal{O}(1)\). Retrieve \(i\)-th element in the sorted sequence of elements.

>>> fromList ["Hey","","Jude"] !? 0
Just ""

>>> fromList ["Hey","","Jude"] !? 1
Just "Hey"

>>> fromList ["Hey","","Jude"] !? 3
Nothing

See also lookupIndex.

\(\mathcal{O}(\log n)\). Look up element in set and report its zero-based index in the sorted sequence elements.

>>> lookupIndex "" (fromList ["Hey","","Jude"])
Just 0

>>> lookupIndex "Hey" (fromList ["Hey","","Jude"])
Just 1

>>> lookupIndex "Law" (fromList ["Hey","","Jude"])
Nothing

See also !?.

\(\mathcal{O}(1)\). An empty TextSet.

\(\mathcal{O}(1)\). Construct set containing one element.

>>> toList (singleton "alone")
["alone"]

\(\mathcal{O}(n \log n)\). Construct set from list of elements.

>>> toList (fromList ["Hey","Jude","Hey","Law","Hey",""])
["","Hey","Jude","Law"]

\(\mathcal{O}(n)\). Construct set from list of distinct elements in ascending order.

NOTE: If the input list is not strictly ascending, an error is thrown.

\(\mathcal{O}(n)\). Convert Set to TextSet.

\(\mathcal{O}(n)\). Convert TextSet to list of ShortText in ascending order.

\(\mathcal{O}(1)\). Convert TextSet to TextArray of ShortText in ascending order.

>>> toList (fromList ["Hey","Jude","Hey","Law","Hey",""])
["","Hey","Jude","Law"]

\(\mathcal{O}(n)\). Convert TextSet to Set.