Copyright | (c) Lars Petersen 2016 |
---|---|
License | MIT |
Maintainer | info@lars-petersen.net |
Stability | experimental |
Safe Haskell | Safe |
Language | Haskell2010 |
- newtype Trie a = Trie {}
- class TrieValue a where
- data TrieNode a
- null :: Trie a -> Bool
- empty :: Trie a
- size :: TrieValue a => Trie a -> Int
- sizeWith :: TrieValue a => (a -> Int) -> Trie a -> Int
- singleton :: TrieValue a => Filter -> a -> Trie a
- matchTopic :: TrieValue a => Topic -> Trie a -> Bool
- matchFilter :: TrieValue a => Filter -> Trie a -> Bool
- lookup :: (TrieValue a, Monoid a) => Topic -> Trie a -> a
- findMaxBounded :: (TrieValue a, Ord a, Bounded a) => Topic -> Trie a -> Maybe a
- insert :: TrieValue a => Filter -> a -> Trie a -> Trie a
- insertWith :: TrieValue a => (a -> a -> a) -> Filter -> a -> Trie a -> Trie a
- insertFoldable :: (TrieValue a, Foldable t) => t (Filter, a) -> Trie a -> Trie a
- map :: (TrieValue a, TrieValue b) => (a -> b) -> Trie a -> Trie b
- mapMaybe :: (TrieValue a, TrieValue b) => (a -> Maybe b) -> Trie a -> Trie b
- foldl' :: TrieValue b => (a -> b -> a) -> a -> Trie b -> a
- delete :: TrieValue a => Filter -> Trie a -> Trie a
- union :: (TrieValue a, Monoid a) => Trie a -> Trie a -> Trie a
- unionWith :: TrieValue a => (a -> a -> a) -> Trie a -> Trie a -> Trie a
- differenceWith :: (TrieValue a, TrieValue b) => (a -> b -> Maybe a) -> Trie a -> Trie b -> Trie a
Trie
The Trie
is a map-like data structure designed to hold elements
that can efficiently be queried according to the matching rules specified
by MQTT.
The primary purpose is to manage client subscriptions, but it can just
as well be used to manage permissions etc.
The tree consists of nodes that may or may not contain values. The edges
are filter components. As some value types have the concept of a null
(i.e. an empty set) the TrieValue
is a class defining the data
family TrieNode
. This is a performance and size optimization to
avoid unnecessary boxing and case distinction.
null
empty
size
sizeWith
singleton
matchTopic
matchFilter
matchFilter :: TrieValue a => Filter -> Trie a -> Bool Source #
Match a Filter
against a Trie
.
The function returns true iff the tree contains a path that is
less or equally specific than the filter and the terminal node contains
a value that is not nodeNull
.
match (singleton "#") "a" = True match (singleton "#") "+" = True match (singleton "#") "a/+/b" = True match (singleton "#") "a/+/#" = True match (singleton "+") "a" = True match (singleton "+") "+" = True match (singleton "+") "+/a" = False match (singleton "+") "#" = False match (singleton "a") "a" = True match (singleton "a") "b" = False match (singleton "a") "+" = False match (singleton "a") "#" = False
lookup
lookup :: (TrieValue a, Monoid a) => Topic -> Trie a -> a Source #
Collect all values of nodes that match a given topic (according to the matching rules specified by the MQTT protocol).
findMaxBounded
insert
insertWith
insertFoldable
map
mapMaybe
mapMaybe :: (TrieValue a, TrieValue b) => (a -> Maybe b) -> Trie a -> Trie b Source #
Applies a functor to a try and removes nodes for which the mapping
function returns Nothing
.