-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Memory efficient sets with continuous ranges of elements.
--   
--   Memory efficient sets with continuous ranges of elements. List based
--   implementation. Interface mimics <a>Data.Set</a> interface where
--   possible.
@package range-set-list
@version 0.0.4


-- | A trivial implementation of range sets.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude functions, e.g.
--   
--   <pre>
--   import Data.RangeSet.List (RSet)
--   import qualified Data.RangeSet.List as RSet
--   </pre>
--   
--   The implementation of <a>RSet</a> is based on <i>list</i>.
--   
--   Compared to <a>Set</a>, this module imposes also <a>Enum</a>
--   restriction for many functions. We must be able to identify
--   consecutive elements to be able to <i>glue</i> and <i>split</i> ranges
--   properly.
--   
--   The implementation assumes that
--   
--   <pre>
--   x &lt; succ x
--   pred x &lt; x
--   </pre>
--   
--   and there aren't elements in between (not true for <a>Float</a> and
--   <a>Double</a>). Also <a>succ</a> and <a>pred</a> are never called for
--   largest or smallest value respectively.
module Data.RangeSet.List

-- | Internally set is represented as sorted list of distinct inclusive
--   ranges.
data RSet a

-- | <i>O(n+m)</i>. See <a>difference</a>.
(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a

-- | <i>O(1)</i>. Is this the empty set?
null :: RSet a -> Bool

-- | <i>O(n)</i>. Is the element in the set?
member :: (Ord a, Enum a) => a -> RSet a -> Bool

-- | <i>O(n)</i>. Is the element not in the set?
notMember :: (Ord a, Enum a) => a -> RSet a -> Bool

-- | <i>O(1)</i>. The empty set.
empty :: RSet a

-- | <i>O(1)</i>. Create a singleton set.
singleton :: a -> RSet a

-- | <i>O(1)</i>. Create a continuos range set.
singletonRange :: Ord a => (a, a) -> RSet a

-- | <i>O(n)</i>. Insert an element in a set.
insert :: (Ord a, Enum a) => a -> RSet a -> RSet a

-- | <i>O(n)</i>. Insert a continuos range in a set.
insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a

-- | /O(n). Delete an element from a set.
delete :: (Ord a, Enum a) => a -> RSet a -> RSet a

-- | /O(n). Delete a continuos range from a set.
deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a

-- | <i>O(n*m)</i>. The union of two sets.
union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a

-- | <i>O(n*m)</i>. Difference of two sets.
difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a

-- | <i>O(n*m)</i>. The intersection of two sets.
intersection :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a

-- | <i>O(n)</i>. Complement of the set.
complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a

-- | <i>O(n*r)</i>. Convert the set to a list of elements. <i>r</i> is the
--   size of longest range.
elems :: Enum a => RSet a -> [a]

-- | <i>O(n*r)</i>. Convert the set to a list of elements. <i>r</i> is the
--   size of longest range.
toList :: Enum a => RSet a -> [a]

-- | <i>O(n^2)</i>. Create a set from a list of elements.
fromList :: (Ord a, Enum a) => [a] -> RSet a

-- | <i>O(1)</i>. Convert the set to a list of range pairs.
toRangeList :: RSet a -> [(a, a)]

-- | <i>O(n^2)</i>. Create a set from a list of range pairs.
fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a
instance Eq a => Eq (RSet a)
instance Ord a => Ord (RSet a)
instance (Ord a, Enum a) => Monoid (RSet a)
instance Show a => Show (RSet a)