Module

Data.Search.Trie.Internal

Package: purescript-search-trie
Repository: klntsky/purescript-search-trie

#Trie Source

data Trie k v

Constructors

Branch (Maybe v) (Map k (Trie k v))
Arc Int (List k) (Trie k v)

Instances

(Eq k, Eq v) => Eq (Trie k v)
(Show k, Show v) => Show (Trie k v)
(Ord k) => Semigroup (Trie k v)
(Ord k) => Monoid (Trie k v)
(Ord k) => Functor (Trie k)

#Ctx Source

data Ctx k v

Constructors

BranchCtx (Maybe v) k (Map k (Trie k v))
ArcCtx Int (List k)

#Zipper Source

data Zipper k v

Constructors

Zipper (Trie k v) (List (Ctx k v))

#alter Source

alter :: forall v k. Ord k => List k -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v

Delete, insert or update the entry by a given path. It is recommended to use specialized functions for each case.

#delete Source

delete :: forall v k. Ord k => List k -> Trie k v -> Trie k v

Delete the entry at a given path.

#deleteByPrefix Source

deleteByPrefix :: forall v k. Ord k => List k -> Trie k v -> Trie k v

Delete all entries by a given path prefix.

#descend Source

descend :: forall v k. Ord k => List k -> Zipper k v -> { children :: Map k (Trie k v), ctxs :: List (Ctx k v), mbValue :: Maybe v }

Follows a given path, constructing new branches as necessary. Returns the contents of the last branch with context from which the trie can be restored using fromZipper.

#entries Source

entries :: forall v k. Trie k v -> List (Tuple (List k) v)

Resulting List will be sorted.

#entriesUnordered Source

entriesUnordered :: forall v k. Trie k v -> List (Tuple (List k) v)

A version of entries defined using Data.Map.toUnfoldableUnordered.

#eq' Source

eq' :: forall v k. Eq k => Eq v => Trie k v -> Trie k v -> Boolean

Check that two tries are not only equal, but also have the same internal structure.

#follow Source

follow :: forall v k. Ord k => List k -> Zipper k v -> Maybe { children :: Map k (Trie k v), ctxs :: List (Ctx k v), mbValue :: Maybe v }

Follows a given path, but unlike descend, fails instead of creating new branches.

#fromFoldable Source

fromFoldable :: forall v k p f. Ord k => Foldable f => Foldable p => f (Tuple (p k) v) -> Trie k v

#fromList Source

fromList :: forall v k. Ord k => List (Tuple (List k) v) -> Trie k v

#fromZipper Source

fromZipper :: forall v k. Ord k => Zipper k v -> Trie k v

#insert Source

insert :: forall v k. Ord k => List k -> v -> Trie k v -> Trie k v

Insert an entry into a trie.

#isEmpty Source

isEmpty :: forall v k. Trie k v -> Boolean

#lookup Source

lookup :: forall v k. Ord k => List k -> Trie k v -> Maybe v

#mkZipper Source

mkZipper :: forall v k. Trie k v -> Zipper k v

#prune Source

prune :: forall v k. Ord k => List (Ctx k v) -> Zipper k v

Delete everything until the first non-empty context.

#query Source

query :: forall v k. Ord k => List k -> Trie k v -> List (Tuple (List k) v)

#queryValues Source

queryValues :: forall v k. Ord k => List k -> Trie k v -> List v

#size Source

size :: forall v k. Trie k v -> Int

Number of elements in a trie.

#subtrie Source

subtrie :: forall v k. Ord k => List k -> Trie k v -> Maybe (Trie k v)

Returns a subtrie containing all paths with given prefix. Path prefixes are not saved.

#subtrieWithPrefixes Source

subtrieWithPrefixes :: forall v k. Ord k => List k -> Trie k v -> Maybe (Trie k v)

A version of subtrie that does not cut the prefixes.

#toUnfoldable Source

toUnfoldable :: forall v k p f. Unfoldable f => Unfoldable p => Trie k v -> f (Tuple (p k) v)

#update Source

update :: forall v k. Ord k => (v -> v) -> List k -> Trie k v -> Trie k v

Update the entry at a given path.

#values Source

values :: forall v k. Trie k v -> List v

Modules: Data.Search.Trie; Data.Search.Trie.Internal