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


-- | patricia tries modeled above VCache
--   
@package vcache-trie
@version 0.1


-- | A compact bytestring trie implemented above VCache.
module Data.VCache.Trie

-- | A trie data structure with bytesting keys, above VCache.
--   
--   This trie uses a simple node structure, with a large branching factor
--   (arity 256), and serializing large shared prefixes and the element
--   values into the same node. The root of the trie is simply a `Maybe
--   (VRef node)`, so is efficient for equality comparisons and
--   serialization purposes. The basic <a>Show</a> instance reports only
--   the root reference address.
--   
--   The trie supports keys of arbitrary size, though very large keys may
--   cause some performance degradation. Similarly, very large values may
--   cause performance degradation since every lookup will load every value
--   in the path.
data Trie a
trie_space :: Trie a -> VSpace

-- | Construct Trie with no elements.
empty :: VSpace -> Trie a

-- | Construct Trie with one element.
singleton :: VCacheable a => VSpace -> ByteString -> a -> Trie a

-- | O(1), test whether trie is empty.
null :: Trie a -> Bool

-- | O(n). Compute size of the trie.
size :: Trie a -> Int

-- | Lookup an object by key
lookup :: ByteString -> Trie a -> Maybe a

-- | Lookup an object by key without caching nodes
lookup' :: ByteString -> Trie a -> Maybe a

-- | Lookup object by key with a specific cache mode.
lookupc :: CacheMode -> ByteString -> Trie a -> Maybe a

-- | O(1). Add a common prefix to all keys currently in the Trie
prefixKeys :: VCacheable a => ByteString -> Trie a -> Trie a

-- | Obtain a trie rooted at a given prefix.
--   
--   This operation may need to allocate a new node.
lookupPrefix :: VCacheable a => ByteString -> Trie a -> Trie a

-- | Delete all keys sharing a given prefix.
deletePrefix :: VCacheable a => ByteString -> Trie a -> Trie a

-- | Insert a single key,value pair into the trie, replacing any existing
--   value at that location.
insert :: VCacheable a => ByteString -> a -> Trie a -> Trie a

-- | Remove a single key from the trie.
delete :: VCacheable a => ByteString -> Trie a -> Trie a

-- | Update an element in the Trie with a given function. Capable of
--   inserts, modifies, and deletes.
adjust :: VCacheable a => (Maybe a -> Maybe a) -> ByteString -> Trie a -> Trie a

-- | Insert a list of (key,value) pairs into the trie. At the moment this
--   is just a linear insert, but it may later be replaced by an efficient
--   batch-insert model. If a key appears more than once in this list, the
--   last entry will win.
insertList :: VCacheable a => [(ByteString, a)] -> Trie a -> Trie a

-- | Remove a collection of keys from the trie. At the moment this is just
--   a sequential deletion, but it may later be replaced by a more
--   efficient batch-deletion model.
deleteList :: VCacheable a => [ByteString] -> Trie a -> Trie a

-- | O(n). Obtain a list of (key,val) pairs, sorted by key.
toList :: Trie a -> [(ByteString, a)]
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

-- | O(n). Obtain list of elements in the trie.
elems :: Trie a -> [a]

-- | O(n). Obtain a sorted list of of keys.
keys :: Trie a -> [ByteString]
foldr :: (a -> b -> b) -> b -> Trie a -> b
foldr' :: (a -> b -> b) -> b -> Trie a -> b
foldrM :: Monad m => (a -> b -> m b) -> b -> Trie a -> m b
foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b
foldrWithKey' :: (ByteString -> a -> b -> b) -> b -> Trie a -> b
foldrWithKeyM :: Monad m => (ByteString -> a -> b -> m b) -> b -> Trie a -> m b
foldl :: (b -> a -> b) -> b -> Trie a -> b
foldl' :: (b -> a -> b) -> b -> Trie a -> b
foldlM :: Monad m => (b -> a -> m b) -> b -> Trie a -> m b
foldlWithKey :: (b -> ByteString -> a -> b) -> b -> Trie a -> b
foldlWithKey' :: (b -> ByteString -> a -> b) -> b -> Trie a -> b
foldlWithKeyM :: Monad m => (b -> ByteString -> a -> m b) -> b -> Trie a -> m b
map :: VCacheable b => (a -> b) -> Trie a -> Trie b
mapM :: (VCacheable b, Monad m) => (a -> m b) -> Trie a -> m (Trie b)
mapWithKey :: VCacheable b => (ByteString -> a -> b) -> Trie a -> Trie b
mapWithKeyM :: (Monad m, VCacheable b) => (ByteString -> a -> m b) -> Trie a -> m (Trie b)

-- | Validate the invariant structure of the Trie. Every node must branch
--   or contain a value.
validate :: Trie a -> Bool

-- | Obtain unique address for Trie value. As with VRef addresses, this
--   should be stable while the Trie is reachable, but may change if the
--   value is GC'd and later reconstructed at a new address. Exposed for
--   memoization and similar purposes.
unsafeTrieAddr :: Trie a -> Word64