KeyReplacementTrie

public sealed class KeyReplacementTrie

Namespace: RhoMicro.BindSight.Transformations

Inheritance:

• DirectoryKeyReplacementTrie

  • Object

Summary

Implements a key replacement algorithm.

Remarks

 Construction  We construct a trie that associates replacement prefixes  with their replacement value.  Keys are split into tokens via the ':' separator, which  is defined as the conventional separator for configuration  keys.  The parent of a node with an associated replacement rule  is the ordered list of tokens in the key up to that token.  Search  We traverse the trie in order of tokens in a given key  until we hit a node that does not allow further traversal,  i.e. its children do not contain the next token.  While traversing the trie, we memorize the current nodes  replacement rule if it is associated with one, as well as  the token index up to that point.  Upon reaching the last navigable node, we then apply the  memorized replacement up to the memorized index.  This way, the maximum depth traversed will be linearly  proportional to the amount of tokens in a given key.  The time complexity for a single lookup is therefore O(n).  a:b  a:b  a:b:c  a:b:d  b:a:b:b:b  a:b:c:d:e  b:d:e  a set of rules like such:  a:b -> f:g:h  a:b:c -> x:y:z  a:d -> m  a:b:d:e:f -> v  u -> w  is built into a trie like this:  _  _:a  _:a:b -> f:g:h  _:a:b:c -> x:y:z  _:a:d -> m  _:u -> w  a:b -> f:g:h  a:b:c -> f:g:h:c  a:b:d -> f:g:h:d  a:b:c:d:e -> f:g:h:c:d:e  b:d:e -> b:d:e

Constructors

KeyReplacementTrie(Node)

private KeyReplacementTrie(Node root)

Methods

Create(IReadOnlyDictionary<string, string>)

public static KeyReplacementTrie Create(IReadOnlyDictionary<string, string> replacements)

Summary

Creates a new trie from a set of keys and associated replacement.

Parameters

Name	Type	Description
replacements	IReadOnlyDictionary<String, String>	The dictionary providing keys and their replacement,

Returns

A new replacement trie.

TryGetReplaced(string, string)

public bool TryGetReplaced(string key, out string? replaced)

Summary

Attempts to locate a replacement key prefixing key and applies it to key.

Parameters

Name	Type	Description
key	String	The key to locate a replacement for.
replaced	String	The replaced key if a replacement could be located; otherwise, null.

Returns

true if a replacement could be located; otherwise, false.