UHC.Util.TreeTrie

A TreeTrie is a search structure where the key actually consists of a tree of keys, represented as a list of layers in the tree, 1 for every depth, starting at the top, which are iteratively used for searching. The search structure for common path/prefixes is shared, the trie branches to multiple corresponding to available children, length equality of children is used in searching (should match)

The TreeTrie structure implemented in this module deviates from the usual TreeTrie implementations in that it allows wildcard matches besides the normal full match. The objective is to also be able to retrieve values for which (at insertion time) it has been indicated that part does not need full matching. This intentionally is similar to unification, where matching on a variable will succeed for arbitrary values. Unification is not the job of this TreeTrie implementation, but by returning partial matches as well, a list of possible match candidates is returned.

Key into TreeTrie

data TreeTrie1Key k

Both key and trie can allow partial matching, indicated by TreeTrie1Key

Constructors

TT1K_One !k

TT1K_Any

Instances

Eq k => Eq (TreeTrie1Key k)

Methods

(==) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

(/=) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

Ord k => Ord (TreeTrie1Key k)

Methods

compare :: TreeTrie1Key k -> TreeTrie1Key k -> Ordering

(<) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

(<=) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

(>) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

(>=) :: TreeTrie1Key k -> TreeTrie1Key k -> Bool

max :: TreeTrie1Key k -> TreeTrie1Key k -> TreeTrie1Key k

min :: TreeTrie1Key k -> TreeTrie1Key k -> TreeTrie1Key k

Show k => Show (TreeTrie1Key k)

Methods

showsPrec :: Int -> TreeTrie1Key k -> ShowS

show :: TreeTrie1Key k -> String

showList :: [TreeTrie1Key k] -> ShowS

PP k => PP (TreeTrie1Key k)

Methods

pp :: TreeTrie1Key k -> PP_Doc

ppList :: [TreeTrie1Key k] -> PP_Doc

Serialize k => Serialize (TreeTrie1Key k)

Methods

sput :: TreeTrie1Key k -> SPut

sget :: SGet (TreeTrie1Key k)

sputNested :: TreeTrie1Key k -> SPut

sgetNested :: SGet (TreeTrie1Key k)

data TreeTrieMp1Key k

A key in a layer of TreeTrieMpKey

Constructors

TTM1K [TreeTrie1Key k]

TTM1K_Any

Instances

Eq k => Eq (TreeTrieMp1Key k)

Methods

(==) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

(/=) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

Ord k => Ord (TreeTrieMp1Key k)

Methods

compare :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Ordering

(<) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

(<=) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

(>) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

(>=) :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> Bool

max :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> TreeTrieMp1Key k

min :: TreeTrieMp1Key k -> TreeTrieMp1Key k -> TreeTrieMp1Key k

Show k => Show (TreeTrieMp1Key k)

Methods

showsPrec :: Int -> TreeTrieMp1Key k -> ShowS

show :: TreeTrieMp1Key k -> String

showList :: [TreeTrieMp1Key k] -> ShowS

PP k => PP (TreeTrieMp1Key k)

Methods

pp :: TreeTrieMp1Key k -> PP_Doc

ppList :: [TreeTrieMp1Key k] -> PP_Doc

Serialize k => Serialize (TreeTrieMp1Key k)

Methods

sput :: TreeTrieMp1Key k -> SPut

sget :: SGet (TreeTrieMp1Key k)

sputNested :: TreeTrieMp1Key k -> SPut

sgetNested :: SGet (TreeTrieMp1Key k)

type TreeTrieMpKey k = [TreeTrieMp1Key k]

The key into a map used internally by the trie

type TreeTrieKey k = [TreeTrieMpKey k]

The key used externally to index into a trie

type family TrTrKey x :: *

Instances

type TrTrKey (Maybe x)

type TrTrKey (Maybe x) = TTKey x

ppTreeTrieKey :: PP k => TreeTrieKey k -> PP_Doc

Pretty print TrieKey

ttkSingleton :: TreeTrie1Key k -> TreeTrieKey k

Make singleton, which should at end be stripped from bottom layer of empty TTM1K []

ttkAdd' :: TreeTrie1Key k -> TreeTrieKey k -> TreeTrieKey k

Add a new layer with single node on top, combining the rest.

ttkAdd :: TreeTrie1Key k -> [TreeTrieKey k] -> TreeTrieKey k

Add a new layer with single node on top, combining the rest. length ks >= 2

ttkChildren :: [TreeTrieKey k] -> TreeTrieKey k

Construct intermediate structure for children for a new Key length ks >= 2

ttkFixate :: TreeTrieKey k -> TreeTrieKey k

Fixate by removing lowest layer empty children

ttkParentChildren :: TreeTrieKey k -> (TreeTrie1Key k, TreeTrieKey k)

Split key into parent and children components, inverse of ttkAdd'

Keyable

class TreeTrieKeyable x where

Keyable values, i.e. capable of yielding a TreeTrieKey for retrieval from a trie

Minimal complete definition

toTreeTrieKey

Methods

toTreeTrieKey :: x -> TreeTrieKey (TrTrKey x)

TreeTrie

data TreeTrie k v

The trie structure, branching out on (1) kind, (2) nr of children, (3) actual key

Instances

(Show k, Show v) => Show (TreeTrie k v)

Methods

showsPrec :: Int -> TreeTrie k v -> ShowS

show :: TreeTrie k v -> String

showList :: [TreeTrie k v] -> ShowS

(PP k, PP v) => PP (TreeTrie k v)

Methods

pp :: TreeTrie k v -> PP_Doc

ppList :: [TreeTrie k v] -> PP_Doc

(Ord k, Serialize k, Serialize v) => Serialize (TreeTrie k v)

Methods

sput :: TreeTrie k v -> SPut

sget :: SGet (TreeTrie k v)

sputNested :: TreeTrie k v -> SPut

sgetNested :: SGet (TreeTrie k v)

emptyTreeTrie :: TreeTrie k v

empty :: TreeTrie k v

toListByKey :: TreeTrie k v -> [(TreeTrieKey k, v)]

toList :: TreeTrie k v -> [(TreeTrieKey k, v)]

fromListByKeyWith :: Ord k => (v -> v -> v) -> [(TreeTrieKey k, v)] -> TreeTrie k v

fromList :: Ord k => [(TreeTrieKey k, v)] -> TreeTrie k v

Lookup

data TreeTrieLookup

How to lookup in a TreeTrie

Constructors

TTL_Exact

TTL_WildInTrie

TTL_WildInKey

Instances

Eq TreeTrieLookup

Methods

(==) :: TreeTrieLookup -> TreeTrieLookup -> Bool

(/=) :: TreeTrieLookup -> TreeTrieLookup -> Bool

lookupPartialByKey :: (PP k, Ord k) => TreeTrieLookup -> TreeTrieKey k -> TreeTrie k v -> ([v], Maybe v)

lookupPartialByKey' :: forall k v v'. (PP k, Ord k) => (TreeTrieKey k -> v -> v') -> TreeTrieLookup -> TreeTrieKey k -> TreeTrie k v -> ([v'], Maybe v')

Normal lookup for exact match + partial matches (which require some sort of further unification, determining whether it was found)

lookupByKey :: (PP k, Ord k) => TreeTrieKey k -> TreeTrie k v -> Maybe v

lookup :: (PP k, Ord k) => TreeTrieKey k -> TreeTrie k v -> Maybe v

lookupResultToList :: ([v], Maybe v) -> [v]

Convert the lookup result to a list of results

Properties/observations

isEmpty :: TreeTrie k v -> Bool

null :: TreeTrie k v -> Bool

elems :: TreeTrie k v -> [v]

Construction

singleton :: Ord k => TreeTrieKey k -> v -> TreeTrie k v

singletonKeyable :: (Ord (TrTrKey v), TreeTrieKeyable v) => v -> TreeTrie (TrTrKey v) v

unionWith :: Ord k => (v -> v -> v) -> TreeTrie k v -> TreeTrie k v -> TreeTrie k v

union :: Ord k => TreeTrie k v -> TreeTrie k v -> TreeTrie k v

unionsWith :: Ord k => (v -> v -> v) -> [TreeTrie k v] -> TreeTrie k v

unions :: Ord k => [TreeTrie k v] -> TreeTrie k v

insertByKeyWith :: Ord k => (v -> v -> v) -> TreeTrieKey k -> v -> TreeTrie k v -> TreeTrie k v

insertByKey :: Ord k => TreeTrieKey k -> v -> TreeTrie k v -> TreeTrie k v

Deletion

deleteByKey :: Ord k => TreeTrieKey k -> TreeTrie k v -> TreeTrie k v

delete :: Ord k => TreeTrieKey k -> TreeTrie k v -> TreeTrie k v

deleteListByKey :: Ord k => [TreeTrieKey k] -> TreeTrie k v -> TreeTrie k v