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


-- | An efficient finite map from (byte)strings to values.
--   
--   An efficient finite map from (byte)strings to values.
--   
--   The implementation is based on big-endian patricia trees, like
--   <a>Data.IntMap</a>. We first trie on the elements of
--   <a>Data.ByteString</a> and then trie on the big-endian bit
--   representation of those elements. Patricia trees have efficient
--   algorithms for union and other merging operations, but they're also
--   quick for lookups and insertions.
--   
--   If you are only interested in being able to associate strings to
--   values, then you may prefer the <tt>hashmap</tt> package which is
--   faster for those only needing a map-like structure. This package is
--   intended for those who need the extra capabilities that a trie-like
--   structure can offer (e.g., structure sharing to reduce memory costs
--   for highly redundant keys, taking the submap of all keys with a given
--   prefix, contextual mapping, extracting the minimum and maximum keys,
--   etc.)
@package bytestring-trie
@version 0.2.3


-- | Internal definition of the <a>Trie</a> data type and generic functions
--   for manipulating them. Almost everything here is re-exported from
--   <a>Data.Trie</a>, which is the preferred API for users. This module is
--   for developers who need deeper (and potentially fragile) access to the
--   abstract type.
module Data.Trie.Internal

-- | A map from <a>ByteString</a>s to <tt>a</tt>. For all the generic
--   functions, note that tries are strict in the <tt>Maybe</tt> but not in
--   <tt>a</tt>.
--   
--   The <a>Monad</a> instance is strange. If a key <tt>k1</tt> is a prefix
--   of other keys, then results from binding the value at <tt>k1</tt> will
--   override values from longer keys when they collide. If this is useful
--   for anything, or if there's a more sensible instance, I'd be curious
--   to know.
data Trie a

-- | Visualization fuction for debugging.
showTrie :: Show a => Trie a -> String

-- | Returns the longest shared prefix and the two remaining suffixes for a
--   pair of strings.
--   
--   <pre>
--   s == (\(pre,s',z') -&gt; pre `append` s') (breakMaximalPrefix s z)
--   z == (\(pre,s',z') -&gt; pre `append` z') (breakMaximalPrefix s z)
--   </pre>
breakMaximalPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

-- | <i>O(1)</i>, Construct the empty trie.
empty :: Trie a

-- | <i>O(1)</i>, Is the trie empty?
null :: Trie a -> Bool

-- | <i>O(1)</i>, Construct a singleton trie.
singleton :: ByteString -> a -> Trie a

-- | <i>O(n)</i>, Get count of elements in trie.
size :: Trie a -> Int

-- | Convert a trie into a list (in key-sorted order) using a function,
--   folding the list as we go.
foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b

-- | Convert a trie into a list using a function. Resulting values are in
--   key-sorted order.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

-- | Generic function to find a value (if it exists) and the subtrie rooted
--   at the prefix. The first function argument is called if and only if a
--   node is exactly reachable by the query; if no node is exactly
--   reachable the default value is used; if the middle of an arc is
--   reached, the second function argument is used.
--   
--   This function is intended for internal use. For the public-facing
--   version, see <tt>lookupBy</tt> in <a>Data.Trie</a>.
lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> ByteString -> Trie a -> b

-- | Return the subtrie containing all keys beginning with a prefix.
submap :: ByteString -> Trie a -> Trie a

-- | Generic function to alter a trie by one element with a function to
--   resolve conflicts (or non-conflicts).
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>alterBy</a> which also allows modifying the sub-trie.
alterBy_ :: (ByteString -> a -> Maybe a -> Trie a -> (Maybe a, Trie a)) -> ByteString -> a -> Trie a -> Trie a

-- | Alter the value associated with a given key. If the key is not
--   present, then the trie is returned unaltered. See <a>alterBy</a> if
--   you are interested in inserting new keys or deleting old keys. Because
--   this function does not need to worry about changing the trie
--   structure, it is somewhat faster than <a>alterBy</a>.
adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | Combine two tries, using a function to resolve collisions. This can
--   only define the space of functions between union and symmetric
--   difference but, with those two, all set operations can be defined
--   (albeit inefficiently).
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a

-- | Generic version of <a>fmap</a>. This function is notably more
--   expensive than <a>fmap</a> or <a>filterMap</a> because we have to
--   reconstruct the keys.
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b

-- | Apply a function to all values, potentially removing them.
filterMap :: (a -> Maybe b) -> Trie a -> Trie b

-- | A variant of <a>fmap</a> which provides access to the subtrie rooted
--   at each value.
contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b

-- | A variant of <a>contextualMap</a> which applies the function strictly.
contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b

-- | A contextual variant of <a>filterMap</a>.
contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b

-- | A contextual variant of <a>mapBy</a>. Again note that this is
--   expensive since we must reconstruct the keys.
contextualMapBy :: (ByteString -> a -> Trie a -> Maybe b) -> Trie a -> Trie b
minAssoc :: Trie a -> Maybe (ByteString, a)
maxAssoc :: Trie a -> Maybe (ByteString, a)
updateMinViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)
updateMaxViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)
instance Eq a => Eq (Trie a)
instance Monoid a => Monoid (Trie a)
instance Monad Trie
instance Applicative Trie
instance Traversable Trie
instance Foldable Trie
instance Functor Trie
instance Binary a => Binary (Trie a)
instance Show a => Show (Trie a)


-- | An efficient implementation of finite maps from strings to values. The
--   implementation is based on <i>big-endian patricia trees</i>, like
--   <a>Data.IntMap</a>. We first trie on the elements of
--   <a>Data.ByteString</a> and then trie on the big-endian bit
--   representation of those elements. For further details on the latter,
--   see
--   
--   <ul>
--   <li>Chris Okasaki and Andy Gill, "<i>Fast Mergeable Integer Maps</i>",
--   Workshop on ML, September 1998, pages 77-86,
--   <a>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452</a></li>
--   <li>D.R. Morrison, "<i>PATRICIA -- Practical Algorithm To Retrieve</i>
--   <i>Information Coded In Alphanumeric</i>", Journal of the ACM, 15(4),
--   October 1968, pages 514-534.</li>
--   </ul>
--   
--   This module aims to provide an austere interface, while being detailed
--   enough for most users. For an extended interface with many additional
--   functions, see <a>Data.Trie.Convenience</a>. For functions that give
--   more detailed (potentially abstraction-breaking) access to the data
--   strucuture, or for experimental functions which aren't quite ready for
--   the public API, see <a>Data.Trie.Internal</a>.
module Data.Trie

-- | A map from <a>ByteString</a>s to <tt>a</tt>. For all the generic
--   functions, note that tries are strict in the <tt>Maybe</tt> but not in
--   <tt>a</tt>.
--   
--   The <a>Monad</a> instance is strange. If a key <tt>k1</tt> is a prefix
--   of other keys, then results from binding the value at <tt>k1</tt> will
--   override values from longer keys when they collide. If this is useful
--   for anything, or if there's a more sensible instance, I'd be curious
--   to know.
data Trie a

-- | <i>O(1)</i>, Construct the empty trie.
empty :: Trie a

-- | <i>O(1)</i>, Is the trie empty?
null :: Trie a -> Bool

-- | <i>O(1)</i>, Construct a singleton trie.
singleton :: ByteString -> a -> Trie a

-- | <i>O(n)</i>, Get count of elements in trie.
size :: Trie a -> Int

-- | Convert association list into a trie. On key conflict, values earlier
--   in the list shadow later ones.
fromList :: [(ByteString, a)] -> Trie a

-- | Convert a trie into a list using a function. Resulting values are in
--   key-sorted order.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

-- | Convert trie into association list. Keys will be in sorted order.
toList :: Trie a -> [(ByteString, a)]

-- | Return all keys in the trie, in sorted order.
keys :: Trie a -> [ByteString]

-- | Return all values in the trie, in sorted order according to the keys.
elems :: Trie a -> [a]

-- | Generic function to find a value (if it exists) and the subtrie rooted
--   at the prefix.
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b

-- | Return the value associated with a query string if it exists.
lookup :: ByteString -> Trie a -> Maybe a

-- | Does a string have a value in the trie?
member :: ByteString -> Trie a -> Bool

-- | Return the subtrie containing all keys beginning with a prefix.
submap :: ByteString -> Trie a -> Trie a

-- | Generic function to alter a trie by one element with a function to
--   resolve conflicts (or non-conflicts).
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a

-- | Insert a new key. If the key is already present, overrides the old
--   value
insert :: ByteString -> a -> Trie a -> Trie a

-- | Apply a function to the value at a key.
adjust :: (a -> a) -> ByteString -> Trie a -> Trie a

-- | Remove the value stored at a key.
delete :: ByteString -> Trie a -> Trie a

-- | Combine two tries, using a function to resolve collisions. This can
--   only define the space of functions between union and symmetric
--   difference but, with those two, all set operations can be defined
--   (albeit inefficiently).
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a

-- | Combine two tries, resolving conflicts by choosing the value from the
--   left trie.
unionL :: Trie a -> Trie a -> Trie a

-- | Combine two tries, resolving conflicts by choosing the value from the
--   right trie.
unionR :: Trie a -> Trie a -> Trie a

-- | Generic version of <a>fmap</a>. This function is notably more
--   expensive than <a>fmap</a> or <a>filterMap</a> because we have to
--   reconstruct the keys.
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b

-- | Apply a function to all values, potentially removing them.
filterMap :: (a -> Maybe b) -> Trie a -> Trie b


-- | Additional convenience functions. In order to keep <a>Data.Trie</a>
--   concise, non-essential and uncommonly used functions have been moved
--   here. Most of these functions simplify the generic functions from
--   <a>Data.Trie</a>, following after the interface for <a>Data.Map</a>
--   and <a>Data.IntMap</a>.
module Data.Trie.Convenience

-- | A left-fold version of <a>fromList</a>. If you run into issues with
--   stack overflows when using <a>fromList</a> or <a>fromListR</a>, then
--   you should use this function instead.
fromListL :: [(ByteString, a)] -> Trie a

-- | An explicitly right-fold variant of <a>fromList</a>. It is a good
--   consumer for list fusion. Worst-case behavior is somewhat worse than
--   worst-case for <a>fromListL</a>. The <a>fromList</a> function is
--   currently just an alias for <a>fromListR</a>.
fromListR :: [(ByteString, a)] -> Trie a

-- | This variant sorts the list before folding over it. This adds <i>O(n
--   log n)</i> overhead and requires the whole list be in memory at once,
--   but it ensures that the list is in best-case order. The benefits
--   generally outweigh the costs.
fromListS :: [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListR</a> that takes a function for combining
--   values on conflict. The first argument to the combining function is
--   the `<tt>new'</tt> value from the initial portion of the list; the
--   second argument is the value that has been accumulated into the trie
--   from the tail of the list (just like the first argument to
--   <a>foldr</a>). Thus, <tt>fromList = fromListWith const</tt>.
fromListWith :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListWith</a> which applies the combining function
--   strictly. This function is a good consumer for list fusion. If you
--   need list fusion and are running into stack overflow problems with
--   <a>fromListWith</a>, then this function may solve the problem.
fromListWith' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A left-fold variant of <a>fromListWith</a>. Note that the arguments to
--   the combining function are swapped: the first is the value in the trie
--   which has been accumulated from the initial part of the list; the
--   second argument is the `<tt>new'</tt> value from the remaining tail of
--   the list (just like the first argument to <a>foldl</a>). Thus,
--   <tt>fromListL = fromListWithL const</tt>.
fromListWithL :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListWithL</a> which applies the combining function
--   strictly.
fromListWithL' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | Lookup a key, returning a default value if it's not found.
lookupWithDefault :: a -> ByteString -> Trie a -> a

-- | Insert a new key, retaining old value on conflict.
insertIfAbsent :: ByteString -> a -> Trie a -> Trie a

-- | Insert a new key, with a function to resolve conflicts.
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWith</a> which applies the combining function
--   strictly.
insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWith</a> which also provides the key to the
--   combining function.
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWithKey</a> which applies the combining function
--   strictly.
insertWithKey' :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | Apply a function to change the value at a key.
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a

-- | Apply a function to the value at a key, possibly removing it.
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a

-- | A variant of <a>update</a> which also provides the key to the
--   function.
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a

-- | Combine two tries, a la symmetric difference. If they define the same
--   key, it is removed; otherwise it is retained with the value it has in
--   whichever trie.
disunion :: Trie a -> Trie a -> Trie a

-- | Combine two tries, using a function to resolve conflicts.
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

-- | A variant of <a>unionWith</a> which applies the combining function
--   strictly.
unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
