-- 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.7


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

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

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

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

-- | Helper function to <a>insert</a> 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 <a>delete</a> 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 Data.Data.Data a => Data.Data.Data (Data.IxSet.Ix.Ix a)
instance (Data.Typeable.Internal.Typeable1 Data.IxSet.Ix.Ix, Data.Generics.SYB.WithClass.Basics.Data ctx a, Data.Generics.SYB.WithClass.Context.Sat (ctx (Data.IxSet.Ix.Ix a))) => Data.Generics.SYB.WithClass.Basics.Data ctx (Data.IxSet.Ix.Ix a)


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

-- | Set with associated indexes.
data IxSet a

-- | Defines objects that can be members of <a>IxSet</a>.
class Indexable a

-- | Defines what an empty <a>IxSet</a> for this particular type should
--   look like. It should have all necessary indexes. Use the <a>ixSet</a>
--   function to create the set and fill it in with <a>ixFun</a> and
--   <a>ixGen</a>.
empty :: Indexable a => IxSet a
data Proxy a
Proxy :: Proxy a

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

-- | Template Haskell helper function for automatically building an
--   <a>Indexable</a> instance from a data type, e.g.
--   
--   <pre>
--   data Foo = Foo Int String
--   </pre>
--   
--   and
--   
--   <pre>
--   $(inferIxSet "FooDB" ''Foo 'noCalcs [''Int,''String])
--   </pre>
--   
--   will build a type synonym
--   
--   <pre>
--   type FooDB = IxSet Foo
--   </pre>
--   
--   with <tt>Int</tt> and <tt>String</tt> as indexes.
--   
--   <i>WARNING</i>: The type specified as the first index must be a type
--   which appears in all values in the <a>IxSet</a> or <a>toList</a>,
--   <a>toSet</a> 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:
--   
--   <pre>
--   $(inferIxSet "FooDB" ''Foo 'noCalcs [''Foo, ''Int, ''String])
--   </pre>
inferIxSet :: String -> Name -> Name -> [Name] -> Q [Dec]

-- | Create an <a>IxSet</a> using a list of indexes. Typically used to
--   create the <a>empty</a> method for an <a>Indexable</a> instance.
--   
--   The list elements are generally created by using the <a>ixFun</a> and
--   <a>ixGen</a> helper functions.
--   
--   <pre>
--   instance Indexable Type where
--       empty = ixSet [ ...
--                     , ixFun getIndex1
--                     , ixGen (Proxy :: Proxy Index2Type)
--                     ]
--   </pre>
--   
--   Every value in the <a>IxSet</a> 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.
--   
--   <pre>
--   getIndexes value = [...indexes...]
--   </pre>
--   
--   <pre>
--   instance Indexable Type where
--       empty = ixSet [ ixFun getIndexes ]
--   </pre>
--   
--   This is the recommended way to create indexes.
ixFun :: forall a b. (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 <a>Proxy</a>. This uses flatten to traverse values
--   using their <a>Data</a> instances.
--   
--   <pre>
--   instance Indexable Type where
--       empty = ixSet [ ixGen (Proxy :: Proxy Type) ]
--   </pre>
--   
--   In production systems consider using <a>ixFun</a> in place of
--   <a>ixGen</a> as the former one is much faster.
ixGen :: forall a b. (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 <a>IxSet</a>s. Use this when your
--   final function should have the form <tt>a -&gt; <a>IxSet</a> a -&gt;
--   <a>IxSet</a> a</tt>, e.g. <a>insert</a> or <a>delete</a>.
change :: (Typeable a, Indexable a, Ord a) => IndexOp -> a -> IxSet a -> IxSet a

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

-- | Removes an item from the <a>IxSet</a>.
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 <a>IxSet</a>. Will not change <a>IxSet</a>
--   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 <a>IxSet</a>. Will not change <a>IxSet</a>
--   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 <a>Set</a> to an <a>IxSet</a>.
fromSet :: (Indexable a, Ord a, Typeable a) => Set a -> IxSet a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | Infix version of <a>getGTE</a>.
(@>=) :: (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 <tt>k</tt>.
--   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 <tt>k</tt>.
--   
--   NOTE: The values in '[t]' are currently sorted in ascending order. But
--   this may change if someone bothers to add <a>toDescList</a>. 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 <tt>b</tt> and returns them as a list.
--   
--   This function properly handles <a>String</a> as <a>String</a> not as
--   <tt>[<a>Char</a>]</tt>.
flatten :: (Typeable a, Data a, Typeable b) => a -> [b]

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

-- | Statistics about <a>IxSet</a>. 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 Data.Data.Data a => Data.Data.Data (Data.IxSet.IxSet a)
instance (GHC.Classes.Eq a, GHC.Classes.Ord a, Data.Typeable.Internal.Typeable a) => GHC.Classes.Eq (Data.IxSet.IxSet a)
instance (GHC.Classes.Eq a, GHC.Classes.Ord a, Data.Typeable.Internal.Typeable a) => GHC.Classes.Ord (Data.IxSet.IxSet a)
instance (Data.SafeCopy.SafeCopy.SafeCopy a, GHC.Classes.Ord a, Data.Typeable.Internal.Typeable a, Data.IxSet.Indexable a) => Data.SafeCopy.SafeCopy.SafeCopy (Data.IxSet.IxSet a)
instance (Data.Generics.SYB.WithClass.Basics.Data ctx a, Data.Generics.SYB.WithClass.Basics.Data ctx [a], Data.Generics.SYB.WithClass.Context.Sat (ctx (Data.IxSet.IxSet a)), Data.Generics.SYB.WithClass.Context.Sat (ctx [a]), Data.Typeable.Internal.Typeable1 Data.IxSet.IxSet, Data.IxSet.Indexable a, Data.Data.Data a, GHC.Classes.Ord a) => Data.Generics.SYB.WithClass.Basics.Data ctx (Data.IxSet.IxSet a)
instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Data.IxSet.IxSet a)
instance (GHC.Classes.Ord a, GHC.Read.Read a, Data.Typeable.Internal.Typeable a, Data.IxSet.Indexable a) => GHC.Read.Read (Data.IxSet.IxSet a)
instance (Data.IxSet.Indexable a, Data.Typeable.Internal.Typeable a, GHC.Classes.Ord a) => GHC.Base.Monoid (Data.IxSet.IxSet a)
