rset alternatives and similar packages
Based on the "Data" category.
Alternatively, view rset alternatives based on common mentions on social networks and blogs.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
streaming
An optimized general monad transformer for streaming applications, with a simple prelude of functions -
-
-
-
text-icu
This package provides the Haskell Data.Text.ICU library, for performing complex manipulation of Unicode text. -
InfluxDB - Power Real-Time Data Analytics at Scale
Do you think we are missing an alternative of rset or a related project?
README
Data.Set.Range
API
The module offers a wide spectrum of operations on a set of ranges, mostly
aiming at mimicking the existing API of the Data.Set module. All types
handled by the data structure have to be instances of the Eq, Ord and
Enum typeclasses.
Types
The module consists of two main types: Range which is a alias for a tuple,
denoting the low and high inclusive boundaries of the range, and the
RangeSet type, which is an alias for a list of Range instances. The
RangeSet type should be treated in a opaque fashion due to portability
reasons, as it may become a data or newtype defined type in the future
releases of the module. Format definitions of the types mentioned above are:
type Range a = (a,a)
type RangeSet a = [Range a]
Functions
All provided functions can be divided into the following 5 categories: list conversions, combinations of multiple range sets, membership testing, modifications of range set contents and general utility functions.
empty :: RangeSet a
Create an empty range set.
null :: RangeSet a -> Bool
Test whether the range set is empty.
size :: (Num n, Enum a) => RangeSet a -> n
Get the overall number of points.
fromAscList :: (Ord a, Enum a) => [a] -> RangeSet a
Create a range set from a list of ascending points.
fromDescList :: (Ord a, Enum a) => [a] -> RangeSet a
Create a range set from a list of descending points.
fromList :: (Ord a, Enum a) => [a] -> RangeSet a
Create a range set from any list of points.
toList :: Enum a => RangeSet a -> [a]
Convert a range set into list of points.
insertPoint :: (Ord a, Enum a) => a -> RangeSet a -> RangeSet a
Insert a point into the range set.
insertRange :: (Ord a, Enum a) => (a,a) -> RangeSet a -> RangeSet a
Insert a range into the range set.
removePoint :: (Ord a, Enum a) => a -> RangeSet a -> RangeSet a
Remove a point from the range set.
removeRange :: (Ord a, Enum a) => (a,a) -> RangeSet a -> RangeSet a
Remove a range from the range set.
queryPoint :: Ord a => a -> RangeSet a -> Bool
Test whether a point is part of the range set.
queryRange :: Ord a => (a,a) -> RangeSet a -> Bool
Test whether a range is part of the range set.
difference :: (Ord a, Enum a) => RangeSet a -> RangeSet a -> RangeSet a
Select points contained only in the first range set.
intersect :: (Ord a, Enum a) => RangeSet a -> RangeSet a -> RangeSet a
Select points contained in both of the range sets.
union :: (Ord a, Enum a) => RangeSet a -> RangeSet a -> RangeSet a
Select points contained in either of the range sets.
Complexity
| Function | Time | Space |
|---|---|---|
empty |
O(1) | O(1) |
null |
O(1) | O(1) |
size |
O(n) | O(l) |
fromAscList |
O(n) | O(n) |
fromDescList |
O(n) | O(n) |
fromList |
O(n) | O(k) |
toList |
O(k) | O(n) |
insertPoint |
O(k) | O(1) |
insertRange |
O(k) | O(1) |
removePoint |
O(k) | O(1) |
removeRange |
O(k) | O(1) |
queryPoint |
O(k) | O(1) |
queryRange |
O(k) | O(1) |
difference |
O(k) | O(k) |
intersect |
O(k) | O(k) |
union |
O(k) | O(k) |
- n is the number of all points in the set
- k is the number of distinct ranges in the set
- l is the length of the largest range in the set
Given the example range set [(1,4),(10,11)] the variables above would be:
nis 6kis 2lis 4
Testing
The library is tested with the QuickCheck property testing library. All tests
are using the set functions from the standard library module Data.List to
verify the correctnes of Data.Set.Range functions. Moreover, the set of tests
is executed after every push to the GitHub repository by the Travis continuous
integration service.
The most recent test coverage reported by HPC is as follows:
100% expressions used (468/468)
75% boolean coverage (12/16)
75% guards (12/16), 4 always True
100% 'if' conditions (0/0)
100% qualifiers (0/0)
100% alternatives used (61/61)
100% local declarations used (6/6)
100% top-level declarations used (18/18)
License
The rset package is licensed under the terms of the [2-clause BSD
license](LICENSE). In case you need any other license, feel free to contact the
author.
Author
Daniel Lovasko [email protected]
*Note that all licence references and agreements mentioned in the rset README section above
are relevant to that project's source code only.