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


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


-- | The underlying structure for a Trie.
--   
--   This is an internal module, but is exposed for now because I'm not
--   sure how to best generically target features such as structural diffs.
--   And we might eventually benefit from zippers, etc. After experimenting
--   and learning, I ask you to push the best generic code into the
--   vcache-trie package (i.e. send a pull request).
module Data.VCache.Trie.Type

-- | A trie data structure with bytestring keys, above VCache.
--   
--   A trie supports keys of arbitrary size, though very large keys may
--   cause performance degradation. Values are directly serialized into
--   nodes, so very large values should use indirection.
data Trie a
Trie :: !(Child a) -> !VSpace -> Trie a
trie_root :: Trie a -> !(Child a)
trie_space :: Trie a -> !VSpace

-- | A node should either accept a value or branch into at least two
--   children.
data Node a
Node :: {-# UNPACK #-} !(Children a) -> {-# UNPACK #-} !ByteString -> !(Maybe a) -> Node a
trie_branch :: Node a -> {-# UNPACK #-} !(Children a)
trie_prefix :: Node a -> {-# UNPACK #-} !ByteString
trie_accept :: Node a -> !(Maybe a)
type Children a = Array Word8 (Child a)
type Child a = Maybe (VRef (Node a))

-- | 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
instance Typeable Node
instance Typeable Trie
instance Eq a => Eq (Node a)
instance Eq (Trie a)
instance Show (Trie a)
instance VCacheable a => VCacheable (Trie a)
instance VCacheable a => VCacheable (Node a)


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

-- | A trie data structure with bytestring keys, above VCache.
--   
--   A trie supports keys of arbitrary size, though very large keys may
--   cause performance degradation. Values are directly serialized into
--   nodes, so very large values should use indirection.
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 with user-provided deref.
lookup' :: DerefNode a -> 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 in VCache, e.g. to delete some
--   fraction of the requested prefix. This isn't optimal for performance.
lookupPrefix :: VCacheable a => ByteString -> Trie a -> Trie a

-- | lookup prefix with user-provided deref function.
lookupPrefix' :: VCacheable a => DerefNode a -> ByteString -> Trie a -> Trie a

-- | Obtain a trie node rooted at a given prefix, if any content exists at
--   this prefix. This operation allows some performance benefits compared
--   to <a>lookupPrefix</a> because it never allocates at the VCache layer.
lookupPrefixNode :: VCacheable a => ByteString -> Trie a -> Maybe (Node a)

-- | lookup prefix node with user-provided deref function
lookupPrefixNode' :: VCacheable a => DerefNode a -> ByteString -> Trie a -> Maybe (Node 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

-- | function to dereference a Trie cache node. This improves user control
--   over caching on lookup.
type DerefNode a = VRef (Node a) -> Node a