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

-- | Efficient relational queries on Haskell sets.
--   
--   Create and query sets that are indexed by multiple indices.
@package ixset
@version 1.0.5

-- | This module defines Typeable indexes and convenience functions.
--   Should probably be considered private to Data.IxSet.
module Data.IxSet.Ix

-- | Ix is a Map from some Typeable key to a
--   Set of values for that key. Ix carries type information
--   inside.
data Ix a
Ix :: (Map key (Set a)) -> (a -> [key]) -> Ix a

-- | Convenience function for inserting into Maps of Sets as
--   in the case of an Ix. If they key did not already exist in the
--   Map, then a new Set is added transparently.
insert :: (Ord a, Ord k) => k -> a -> Map k (Set a) -> Map k (Set a)

-- | Convenience function for deleting from Maps of Sets. If
--   the resulting Set is empty, then the entry is removed from the
--   Map.
delete :: (Ord a, Ord k) => k -> a -> Map k (Set a) -> Map k (Set a)

-- | Helper function to insert a list of elements into a set.
insertList :: (Ord a, Ord k) => [(k, a)] -> Map k (Set a) -> Map k (Set a)

-- | Helper function to delete a list of elements from a set.
deleteList :: (Ord a, Ord k) => [(k, a)] -> Map k (Set a) -> Map k (Set a)

-- | Takes the union of two sets.
union :: (Ord a, Ord k) => Map k (Set a) -> Map k (Set a) -> Map k (Set a)

-- | Takes the intersection of two sets.
intersection :: (Ord a, Ord k) => Map k (Set a) -> Map k (Set a) -> Map k (Set a)
instance [overlap ok] Typeable1 Ix
instance [overlap ok] (Data ctx a, Sat (ctx (Ix a))) => Data ctx (Ix a)
instance [overlap ok] Data a => Data (Ix a)

-- | An efficient implementation of queryable sets.
--   
--   Assume you have a type like:
--   
--   
--   data Entry = Entry Author [Author] Updated Id Content
--   newtype Updated = Updated EpochTime
--   newtype Id = Id Int64
--   newtype Content = Content String
--   newtype Author = Author Email
--   type Email = String
--   
--   
--   
--   
- Decide what parts of your type you want indexed and make your type
--   an instance of Indexable. Use ixFun and ixGen to
--   build indexes:
--   
--   
--   
--   instance Indexable Entry where
--       empty = ixSet
--                 [ ixGen (Proxy :: Proxy Author)        -- out of order
--                 , ixGen (Proxy :: Proxy Id)
--                 , ixGen (Proxy :: Proxy Updated)
--                 , ixGen (Proxy :: Proxy Test)          -- bogus index
--                 ]
--   
--   
--   
--   
- Use insert, delete, updateIx, deleteIx
--   and empty to build up an IxSet collection:
--   
--   
--   
--   entries = foldr insert empty [e1,e2,e3,e4]
--   entries' = foldr delete entries [e1,e3]
--   entries'' = update e4 e5 entries
--   
--   
--   
--   
- Use the query functions below to grab data from it:
--   
--   
--   
--   entries @= (Author "john@doe.com") @< (Updated t1)
--   
--   
--   Statement above will find all items in entries updated earlier than
--   t1 by john@doe.com.
--   
--   
--   
- Text index
--   
--   
--   If you want to do add a text index create a calculated index. Then if
--   you want all entries with either word1 or word2, you
--   change the instance to:
--   
--   
--   getWords (Entry _ _ _ _ (Content s)) = map Word $ words s
--   
--   instance Indexable Entry where
--       empty = ixSet [ ...
--                       ixFun getWords
--                     ]
--   
--   
--   Now you can do this query to find entries with any of the words:
--   
--   
--   entries @+ [Word "word1", Word "word2"]
--   
--   
--   And if you want all entries with both:
--   
--   
--   entries @* [Word "word1", Word "word2"]
--   
--   
--   
--   
- Find only the first author
--   
--   
--   If an Entry has multiple authors and you want to be able to
--   query on the first author only, define a FirstAuthor datatype
--   and create an index with this type. Now you can do:
--   
--   
--   newtype FirstAuthor = FirstAuthor Email
--   
--   getFirstAuthor (Entry author _ _ _ _) = [FirstAuthor author]
--   
--   instance Indexable Entry where
--       ...
--       empty = ixSet [ ...
--                       ixFun getFirstAuthor
--                     ]
--   
--       entries @= (FirstAuthor "john@doe.com")  -- guess what this does
--   
module Data.IxSet

-- | Set with associated indexes.
data IxSet a

-- | Defines objects that can be members of IxSet.
class Indexable a
empty :: Indexable a => IxSet a
data Proxy a
Proxy :: Proxy a

-- | Function to be used for calcs in inferIxSet when you
--   don't want any calculated values.
noCalcs :: t -> ()

-- | Template Haskell helper function for automatically building an
--   Indexable instance from a data type, e.g.
--   
--   
--   data Foo = Foo Int String
--   
--   
--   and
--   
--   
--   $(inferIxSet "FooDB" ''Foo 'noCalcs [''Int,''String])
--   
--   
--   will build a type synonym
--   
--   
--   type FooDB = IxSet Foo
--   
--   
--   with Int and String as indexes.
--   
--   WARNING: The type specified as the first index must be a type
--   which appears in all values in the IxSet or toList,
--   toSet and serialization will not function properly. You will be
--   warned not to do this with a runtime error. You can always use the
--   element type itself. For example:
--   
--   
--   $(inferIxSet "FooDB" ''Foo 'noCalcs [''Foo, ''Int, ''String])
--   
inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]

-- | Create an IxSet using a list of indexes. Useful in the
--   Indexable empty method. Use ixFun and
--   ixGen as list elements.
--   
--   
--   instance Indexable Type where
--       empty = ixSet [ ...
--                       ixFun getIndex1
--                       ixGen (Proxy :: Proxy Index2Type)
--                     ]
--   
--   
--   Every value in the IxSet must be reachable by the first index
--   in this list, or you'll get a runtime error.
ixSet :: [Ix a] -> IxSet a

-- | Create a functional index. Provided function should return a list of
--   indexes where the value should be found.
--   
--   
--   getIndexes value = [...indexes...]
--   
--   
--   
--   instance Indexable Type where
--       empty = ixSet [ ixFun getIndexes ]
--   
--   
--   This is the recommended way to create indexes.
ixFun :: (Ord b, Typeable b) => (a -> [b]) -> Ix a

-- | Create a generic index. Provided example is used only as type source
--   so you may use a Proxy. This uses flatten to traverse values
--   using their Data instances.
--   
--   
--   instance Indexable Type where
--       empty = ixSet [ ixGen (Proxy :: Proxy Type) ]
--   
--   
--   In production systems consider using ixFun in place of
--   ixGen as the former one is much faster.
ixGen :: (Data a, Ord b, Typeable b) => Proxy b -> Ix a
type IndexOp = forall k a. (Ord k, Ord a) => k -> a -> Map k (Set a) -> Map k (Set a)

-- | Higher order operator for modifying IxSets. Use this when your
--   final function should have the form a -> IxSet a ->
--   IxSet a, e.g. insert or delete.
change :: (Typeable a, Indexable a, Ord a) => IndexOp -> a -> IxSet a -> IxSet a

-- | Inserts an item into the IxSet. If your data happens to have a
--   primary key this function might not be what you want. See
--   updateIx.
insert :: (Typeable a, Ord a, Indexable a) => a -> IxSet a -> IxSet a

-- | Removes an item from the IxSet.
delete :: (Typeable a, Ord a, Indexable a) => a -> IxSet a -> IxSet a

-- | Will replace the item with index k. Only works if there is at most one
--   item with that index in the IxSet. Will not change IxSet
--   if you have more then 1 item with given index.
updateIx :: (Indexable a, Ord a, Typeable a, Typeable k) => k -> a -> IxSet a -> IxSet a

-- | Will delete the item with index k. Only works if there is at most one
--   item with that index in the IxSet. Will not change IxSet
--   if you have more then 1 item with given index.
deleteIx :: (Indexable a, Ord a, Typeable a, Typeable k) => k -> IxSet a -> IxSet a

-- | Converts a Set to an IxSet.
fromSet :: (Indexable a, Ord a, Typeable a) => Set a -> IxSet a

-- | Converts a list to an IxSet.
fromList :: (Indexable a, Ord a, Typeable a) => [a] -> IxSet a

-- | Converts an IxSet to a Set of its elements.
toSet :: Ord a => IxSet a -> Set a

-- | Converts an IxSet to its list of elements.
toList :: Ord a => IxSet a -> [a]

-- | Converts an IxSet to its list of elements.
--   
--   List will be sorted in ascending order by the index k.
--   
--   The list may contain duplicate entries if a single value produces
--   multiple keys.
toAscList :: (Indexable a, Typeable a, Typeable k) => Proxy k -> IxSet a -> [a]

-- | Converts an IxSet to its list of elements.
--   
--   List will be sorted in descending order by the index k.
--   
--   The list may contain duplicate entries if a single value produces
--   multiple keys.
toDescList :: (Indexable a, Typeable a, Typeable k) => Proxy k -> IxSet a -> [a]

-- | If the IxSet is a singleton it will return the one item stored
--   in it. If IxSet is empty or has many elements this function
--   returns Nothing.
getOne :: Ord a => IxSet a -> Maybe a

-- | Like getOne with a user-provided default.
getOneOr :: Ord a => a -> IxSet a -> a

-- | Returns the number of unique items in the IxSet.
size :: Ord a => IxSet a -> Int

-- | Return True if the IxSet is empty, False
--   otherwise.
null :: IxSet a -> Bool

-- | An infix intersection operation.
(&&&) :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a

-- | An infix union operation.
(|||) :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a

-- | Takes the union of the two IxSets.
union :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a

-- | Takes the intersection of the two IxSets.
intersection :: (Ord a, Typeable a, Indexable a) => IxSet a -> IxSet a -> IxSet a

-- | Infix version of getEQ.
(@=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a

-- | Infix version of getLT.
(@<) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a

-- | Infix version of getGT.
(@>) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a

-- | Infix version of getLTE.
(@<=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a

-- | Infix version of getGTE.
(@>=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> k -> IxSet a

-- | Returns the subset with indexes in the open interval (k,k).
(@><) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a

-- | Returns the subset with indexes in [k,k).
(@>=<) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a

-- | Returns the subset with indexes in (k,k].
(@><=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a

-- | Returns the subset with indexes in [k,k].
(@>=<=) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> (k, k) -> IxSet a

-- | Creates the subset that has an index in the provided list.
(@+) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> [k] -> IxSet a

-- | Creates the subset that matches all the provided indexes.
(@*) :: (Indexable a, Typeable a, Ord a, Typeable k) => IxSet a -> [k] -> IxSet a

-- | Returns the subset with an index equal to the provided key. The set
--   must be indexed over key type, doing otherwise results in runtime
--   error.
getEQ :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet a

-- | Returns the subset with an index less than the provided key. The set
--   must be indexed over key type, doing otherwise results in runtime
--   error.
getLT :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet a

-- | Returns the subset with an index greater than the provided key. The
--   set must be indexed over key type, doing otherwise results in runtime
--   error.
getGT :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet a

-- | Returns the subset with an index less than or equal to the provided
--   key. The set must be indexed over key type, doing otherwise results in
--   runtime error.
getLTE :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet a

-- | Returns the subset with an index greater than or equal to the provided
--   key. The set must be indexed over key type, doing otherwise results in
--   runtime error.
getGTE :: (Indexable a, Typeable a, Ord a, Typeable k) => k -> IxSet a -> IxSet a

-- | Returns the subset with an index within the interval provided. The
--   bottom of the interval is closed and the top is open, i. e. [k1;k2).
--   The set must be indexed over key type, doing otherwise results in
--   runtime error.
getRange :: (Indexable a, Typeable k, Ord a, Typeable a) => k -> k -> IxSet a -> IxSet a

-- | Returns lists of elements paired with the indexes determined by type
--   inference.
groupBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]

-- | Returns lists of elements paired with the indexes determined by type
--   inference.
--   
--   The resulting list will be sorted in ascending order by k.
--   The values in '[t]' will be sorted in ascending order as well.
groupAscBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]

-- | Returns lists of elements paired with the indexes determined by type
--   inference.
--   
--   The resulting list will be sorted in descending order by k.
--   
--   NOTE: The values in '[t]' are currently sorted in ascending order. But
--   this may change if someone bothers to add toDescList. So do not
--   rely on the sort order of '[t]'.
groupDescBy :: (Typeable k, Typeable t) => IxSet t -> [(k, [t])]

-- | Generically traverses the argument to find all occurences of values of
--   type b and returns them as a list.
--   
--   This function properly handles String as String not as
--   [Char].
flatten :: (Typeable a, Data a, Typeable b) => a -> [b]

-- | Generically traverses the argument and calculated values to find all
--   occurences of values of type b and returns them as a list.
--   Equivalent to:
--   
--   
--   flatten (x,calcs x)
--   
--   
--   This function properly handles String as String not as
--   [Char].
flattenWithCalcs :: (Data c, Typeable a, Data a, Typeable b) => (a -> c) -> a -> [b]

-- | Statistics about IxSet. This function returns quadruple
--   consisting of 1. total number of elements in the set 2. number of
--   declared indexes 3. number of keys in all indexes 4. number of values
--   in all keys in all indexes. This can aid you in debugging and
--   optimisation.
stats :: Ord a => IxSet a -> (Int, Int, Int, Int)
instance [overlap ok] Typeable1 IxSet
instance [overlap ok] Data a => Data (IxSet a)
instance [overlap ok] (Indexable a, Typeable a, Ord a) => Monoid (IxSet a)
instance [overlap ok] (Ord a, Read a, Typeable a, Indexable a) => Read (IxSet a)
instance [overlap ok] (Ord a, Show a) => Show (IxSet a)
instance [overlap ok] (Data ctx a, Data ctx [a], Sat (ctx (IxSet a)), Sat (ctx [a]), Indexable a, Data a, Ord a) => Data ctx (IxSet a)
instance [overlap ok] (SafeCopy a, Ord a, Typeable a, Indexable a) => SafeCopy (IxSet a)
instance [overlap ok] (Eq a, Ord a, Typeable a) => Ord (IxSet a)
instance [overlap ok] (Eq a, Ord a, Typeable a) => Eq (IxSet a)
