Lazy.hs

{-| 
Module      : LazySet
Description : A truly lazy Set. 
Copyright   : (c) Carlos Freund, 2016
License     : MIT
Maintainer  : carlosfreund@gmail.com
Stability   : experimental

A Set that can be created from lazy, ordered, infinite lists. 
-}
module Data.Set.Lazy where 

import Prelude hiding(lookup)
import qualified Data.List as List
import qualified Data.Set as NSet
import qualified Data.List.Ordered as OList
import Data.Maybe (isJust)
import Data.Ord

    
data LazySet a = LazySet [NSet.Set a]
    deriving (Eq, Show)
    
-- * Query    

-- | Checks if the value is a member of the 'LazySet'. 
-- Performance: O(m)=log m  
--Where m is the position of the element beeing searched for. 
-- This only applies after the element has been fetched from the underlying list.
member :: Ord a => a -> LazySet a ->  Bool
member e set = isJust $ lookup e set             
    
-- | Searches for a value in a Set. If it can not be found returns 'Nothing' otherwhise 
-- Returns 'Just a' if it can find it. The returned value will be the one from the set, not the one that was passed. 
lookup :: Ord a => a -> LazySet a -> Maybe a
lookup e (LazySet sets) = findIn sets
    where findIn [] = Nothing
          findIn (set:rest) = case NSet.lookupLE e set of 
            Nothing -> Nothing
            Just x ->  if (x == e) then Just x else findIn rest  


-- | Returns true if the 'LazSet' is empty. 
null :: LazySet a -> Bool
null (LazySet (x:xs)) = True
null _ = False

-- | Returns the size of the set. Do not use this on infinite Sets.
size :: Ord a => LazySet a -> Int
size = length . toList 

-- * Combine
    
-- | Splits the 'LazySet' into two parts. 
-- The first containing all consecutive elements of the Set where the predicate applies.
-- The second contains the (infinite) rest. 
spanAntitone :: Ord a => (a -> Bool) -> LazySet a -> (LazySet a, LazySet a)
spanAntitone pred (LazySet sets) = let
    (lesser, (middle:higher)) = List.span (pred . NSet.findMax) sets
    (middleLesser, middleHigher) = NSet.spanAntitone pred middle
    in (LazySet (lesser++[middleLesser]), LazySet (middleHigher:higher))
    
-- | Union of two LazySets.     
union :: Ord a => LazySet a -> LazySet a -> LazySet a
union s1 s2 = let  
    in fromList $ OList.union (toList s1) (toList s2)


-- * Build


-- | Create an 'empty' 'LazySet'.    
empty :: Ord a => LazySet a    
empty = fromList []
    
  
-- | Builds a 'LazySet' from an ascending ordered list.
-- If the list is not ordered an error is thrown. 
fromAscList :: Ord a => [a] -> LazySet a
fromAscList = growFromAscList 2.0               


-- | Like 'fromAscList' but with a custom growth-factor. 
growFromAscList :: Ord a => 
    Float   -- ^ The factor by which the subtrees grow. 
    --Must be >= 1.0. A growth of 1.0 makes the 'LazySet' behave like a List. 
    -- The higher it is set, the more it behaves like a 'Data.Set'.
    -- The downside of a higher growth-factor is that bigger batches are extracted from the source-list at once. 
    -> [a]  -- ^ An ascending List
    -> LazySet a     
growFromAscList growth _ | growth < 1.0 = error "growth must be at least 1" 
growFromAscList growth xs = LazySet (build 0 growth (checkDir xs))
    where checkDir (a:b:s)| a > b = error "Elements must be ascending." 
          checkDir  xs = xs   

-- | Alias for 'fromAscList'.
fromList :: Ord a => [a] -> LazySet a
fromList = fromAscList
          
-- | Create a 'LazSet' from a descending list.           
fromDescList :: Ord a => [a] -> LazySet (Down a)
fromDescList xs = fromAscList (map Down xs)
    
-- | Kind of internal. 
build :: Ord a => Int -- ^ starting-depth 
    -> Float -- ^ growth-factor
    -> [a] -- ^Ascending source-list 
    -> [NSet.Set a]         
build _ _ [] = []
build level growth xs = let 
    (elementsForThisLevel, elementsFurtherDown) = List.splitAt (ceiling $ growth^level) xs
    in (NSet.fromAscList elementsForThisLevel):(build (level + 1) growth elementsFurtherDown)
    
    
-- * Export
      
-- | List with all elements in order.
toList :: Ord a => LazySet a -> [a]
toList (LazySet sets) = concat $ map NSet.toAscList sets