Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Codec.Archive.Tar.Index.IntTrie
Synopsis
- newtype IntTrie = IntTrie (UArray Word32 Word32)
- construct :: [([Key], Value)] -> IntTrie
- toList :: IntTrie -> [([Key], Value)]
- newtype IntTrieBuilder = IntTrieBuilder (IntMap TrieNode)
- empty :: IntTrieBuilder
- insert :: [Key] -> Value -> IntTrieBuilder -> IntTrieBuilder
- finalise :: IntTrieBuilder -> IntTrie
- unfinalise :: IntTrie -> IntTrieBuilder
- lookup :: IntTrie -> [Key] -> Maybe TrieLookup
- data TrieLookup
- serialise :: IntTrie -> Builder
- serialiseSize :: IntTrie -> Int
- deserialise :: ByteString -> Maybe (IntTrie, ByteString)
- data TrieNode
- type Completions = [(Key, TrieLookup)]
- inserts :: [([Key], Value)] -> IntTrieBuilder -> IntTrieBuilder
- completionsFrom :: IntTrie -> Word32 -> Completions
- flattenTrie :: IntTrieBuilder -> [Word32]
- tagLeaf :: Word32 -> Word32
- tagNode :: Word32 -> Word32
- newtype Key = Key {}
- newtype Value = Value {}
Documentation
A compact mapping from sequences of nats to nats.
NOTE: The tries in this module have values only at the leaves (which correspond to files), they do not have values at the branch points (which correspond to directories).
construct :: [([Key], Value)] -> IntTrie Source #
Build an IntTrie
from a bunch of (key, value) pairs, where the keys
are sequences.
toList :: IntTrie -> [([Key], Value)] Source #
Convert the trie to a list
This is the left inverse to construct
(modulo ordering).
newtype IntTrieBuilder Source #
Constructors
IntTrieBuilder (IntMap TrieNode) |
Instances
Show IntTrieBuilder Source # | |
Defined in Codec.Archive.Tar.Index.IntTrie Methods showsPrec :: Int -> IntTrieBuilder -> ShowS # show :: IntTrieBuilder -> String # showList :: [IntTrieBuilder] -> ShowS # | |
Eq IntTrieBuilder Source # | |
Defined in Codec.Archive.Tar.Index.IntTrie Methods (==) :: IntTrieBuilder -> IntTrieBuilder -> Bool # (/=) :: IntTrieBuilder -> IntTrieBuilder -> Bool # |
insert :: [Key] -> Value -> IntTrieBuilder -> IntTrieBuilder Source #
finalise :: IntTrieBuilder -> IntTrie Source #
unfinalise :: IntTrie -> IntTrieBuilder Source #
data TrieLookup Source #
Constructors
Entry !Value | |
Completions Completions |
Instances
Show TrieLookup Source # | |
Defined in Codec.Archive.Tar.Index.IntTrie Methods showsPrec :: Int -> TrieLookup -> ShowS # show :: TrieLookup -> String # showList :: [TrieLookup] -> ShowS # | |
Eq TrieLookup Source # | |
Defined in Codec.Archive.Tar.Index.IntTrie | |
Ord TrieLookup Source # | |
Defined in Codec.Archive.Tar.Index.IntTrie Methods compare :: TrieLookup -> TrieLookup -> Ordering # (<) :: TrieLookup -> TrieLookup -> Bool # (<=) :: TrieLookup -> TrieLookup -> Bool # (>) :: TrieLookup -> TrieLookup -> Bool # (>=) :: TrieLookup -> TrieLookup -> Bool # max :: TrieLookup -> TrieLookup -> TrieLookup # min :: TrieLookup -> TrieLookup -> TrieLookup # |
serialiseSize :: IntTrie -> Int Source #
deserialise :: ByteString -> Maybe (IntTrie, ByteString) Source #
Constructors
TrieLeaf !Word32 | |
TrieNode !IntTrieBuilder |
type Completions = [(Key, TrieLookup)] Source #
inserts :: [([Key], Value)] -> IntTrieBuilder -> IntTrieBuilder Source #
completionsFrom :: IntTrie -> Word32 -> Completions Source #
flattenTrie :: IntTrieBuilder -> [Word32] Source #
The most significant bit is used for tagging,
see tagLeaf
/ tagNode
below, so morally it's Word31 only.