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


-- | patricia tries modeled above VCache
--   
--   VCache supports larger-than-memory values with caching, persistence,
--   and structure sharing. Effective use of VCache requires useful data
--   structures be modeled above it. The trie is useful for modeling key
--   value databases or abstract virtual filesystems, where keys have
--   shared prefixes or elements with a common prefix are likely to be
--   updated together.
--   
--   Currently, the implementation is specialized to a bytestring trie.
@package vcache-trie
@version 0.2.3


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

-- | Return byte count for prefix common among two strings.
sharedPrefixLen :: ByteString -> ByteString -> Int
instance GHC.Classes.Eq (Data.VCache.Trie.Type.Trie a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.VCache.Trie.Type.Node a)
instance Database.VCache.Types.VCacheable a => Database.VCache.Types.VCacheable (Data.VCache.Trie.Type.Node a)
instance Database.VCache.Types.VCacheable a => Database.VCache.Types.VCacheable (Data.VCache.Trie.Type.Trie a)
instance GHC.Show.Show (Data.VCache.Trie.Type.Trie 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)

-- | Quickly find keys to the left or right of a given key. If the given
--   key is matched, it appears at the head of the right list. The left
--   list is reverse-ordered, finding keys to the left of the requested
--   key.
--   
--   The intention here is to support efficient ranged searches or lookups.
--   The lists returned are computed lazily.
toListOnKey :: ByteString -> Trie a -> ([(ByteString, a)], [(ByteString, a)])

-- | Compute differences between two tries. The provided functions
--   determine the difference type for values in just the left or right or
--   both.
diff :: (Eq a) => Trie a -> Trie a -> [(ByteString, Diff a)]

-- | a simple difference data structure. We're either just in the left,
--   just in the right, or have some simple difference in both (e.g. based
--   on Eq).
data Diff a
InL :: a -> Diff a
Diff :: a -> a -> Diff a
InR :: a -> Diff a

-- | 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
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.VCache.Trie.Diff a)
instance GHC.Show.Show a => GHC.Show.Show (Data.VCache.Trie.Diff a)