From 67c28dbe67209effad83d93b850caba5ee1e20e3 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 3 May 2023 11:12:28 +0200 Subject: Merging upstream version 11.7.1. Signed-off-by: Daniel Baumann --- docs/sqlglot/trie.html | 209 +++++++++++++++++++++++++------------------------ 1 file changed, 106 insertions(+), 103 deletions(-) (limited to 'docs/sqlglot/trie.html') diff --git a/docs/sqlglot/trie.html b/docs/sqlglot/trie.html index 632b67a..93c0938 100644 --- a/docs/sqlglot/trie.html +++ b/docs/sqlglot/trie.html @@ -3,7 +3,7 @@ - + sqlglot.trie API documentation @@ -64,7 +64,7 @@ 3key = t.Sequence[t.Hashable] 4 5 - 6def new_trie(keywords: t.Iterable[key]) -> t.Dict: + 6def new_trie(keywords: t.Iterable[key], trie: t.Optional[t.Dict] = None) -> t.Dict: 7 """ 8 Creates a new trie out of a collection of keywords. 9 @@ -77,57 +77,58 @@ 16 17 Args: 18 keywords: the keywords to create the trie from. -19 -20 Returns: -21 The trie corresponding to `keywords`. -22 """ -23 trie: t.Dict = {} -24 -25 for key in keywords: -26 current = trie -27 -28 for char in key: -29 current = current.setdefault(char, {}) -30 current[0] = True -31 -32 return trie -33 +19 trie: a trie to mutate instead of creating a new one +20 +21 Returns: +22 The trie corresponding to `keywords`. +23 """ +24 trie = {} if trie is None else trie +25 +26 for key in keywords: +27 current = trie +28 +29 for char in key: +30 current = current.setdefault(char, {}) +31 current[0] = True +32 +33 return trie 34 -35def in_trie(trie: t.Dict, key: key) -> t.Tuple[int, t.Dict]: -36 """ -37 Checks whether a key is in a trie. -38 -39 Examples: -40 >>> in_trie(new_trie(["cat"]), "bob") -41 (0, {'c': {'a': {'t': {0: True}}}}) -42 -43 >>> in_trie(new_trie(["cat"]), "ca") -44 (1, {'t': {0: True}}) -45 -46 >>> in_trie(new_trie(["cat"]), "cat") -47 (2, {0: True}) -48 -49 Args: -50 trie: the trie to be searched. -51 key: the target key. -52 -53 Returns: -54 A pair `(value, subtrie)`, where `subtrie` is the sub-trie we get at the point where the search stops, and `value` -55 is either 0 (search was unsuccessful), 1 (`value` is a prefix of a keyword in `trie`) or 2 (`key is in `trie`). -56 """ -57 if not key: -58 return (0, trie) -59 -60 current = trie -61 -62 for char in key: -63 if char not in current: -64 return (0, current) -65 current = current[char] -66 -67 if 0 in current: -68 return (2, current) -69 return (1, current) +35 +36def in_trie(trie: t.Dict, key: key) -> t.Tuple[int, t.Dict]: +37 """ +38 Checks whether a key is in a trie. +39 +40 Examples: +41 >>> in_trie(new_trie(["cat"]), "bob") +42 (0, {'c': {'a': {'t': {0: True}}}}) +43 +44 >>> in_trie(new_trie(["cat"]), "ca") +45 (1, {'t': {0: True}}) +46 +47 >>> in_trie(new_trie(["cat"]), "cat") +48 (2, {0: True}) +49 +50 Args: +51 trie: the trie to be searched. +52 key: the target key. +53 +54 Returns: +55 A pair `(value, subtrie)`, where `subtrie` is the sub-trie we get at the point where the search stops, and `value` +56 is either 0 (search was unsuccessful), 1 (`value` is a prefix of a keyword in `trie`) or 2 (`key is in `trie`). +57 """ +58 if not key: +59 return (0, trie) +60 +61 current = trie +62 +63 for char in key: +64 if char not in current: +65 return (0, current) +66 current = current[char] +67 +68 if 0 in current: +69 return (2, current) +70 return (1, current) @@ -137,13 +138,13 @@
def - new_trie(keywords: Iterable[Sequence[Hashable]]) -> Dict: + new_trie( keywords: Iterable[Sequence[Hashable]], trie: Optional[Dict] = None) -> Dict:
- 
 7def new_trie(keywords: t.Iterable[key]) -> t.Dict:
+            
 7def new_trie(keywords: t.Iterable[key], trie: t.Optional[t.Dict] = None) -> t.Dict:
  8    """
  9    Creates a new trie out of a collection of keywords.
 10
@@ -156,20 +157,21 @@
 17
 18    Args:
 19        keywords: the keywords to create the trie from.
-20
-21    Returns:
-22        The trie corresponding to `keywords`.
-23    """
-24    trie: t.Dict = {}
-25
-26    for key in keywords:
-27        current = trie
-28
-29        for char in key:
-30            current = current.setdefault(char, {})
-31        current[0] = True
-32
-33    return trie
+20        trie: a trie to mutate instead of creating a new one
+21
+22    Returns:
+23        The trie corresponding to `keywords`.
+24    """
+25    trie = {} if trie is None else trie
+26
+27    for key in keywords:
+28        current = trie
+29
+30        for char in key:
+31            current = current.setdefault(char, {})
+32        current[0] = True
+33
+34    return trie
 

 
 
@@ -192,6 +194,7 @@ strings, or by 0, which is used to designate that a keyword is in the trie.

 
 
    
 
  • keywords:  the keywords to create the trie from.
    • 
+
  • trie:  a trie to mutate instead of creating a new one
    • 
 

 
 
Returns:

@@ -214,41 +217,41 @@ strings, or by 0, which is used to designate that a keyword is in the trie.
- 
36def in_trie(trie: t.Dict, key: key) -> t.Tuple[int, t.Dict]:
-37    """
-38    Checks whether a key is in a trie.
-39
-40    Examples:
-41        >>> in_trie(new_trie(["cat"]), "bob")
-42        (0, {'c': {'a': {'t': {0: True}}}})
-43
-44        >>> in_trie(new_trie(["cat"]), "ca")
-45        (1, {'t': {0: True}})
-46
-47        >>> in_trie(new_trie(["cat"]), "cat")
-48        (2, {0: True})
-49
-50    Args:
-51        trie: the trie to be searched.
-52        key: the target key.
-53
-54    Returns:
-55        A pair `(value, subtrie)`, where `subtrie` is the sub-trie we get at the point where the search stops, and `value`
-56        is either 0 (search was unsuccessful), 1 (`value` is a prefix of a keyword in `trie`) or 2 (`key is in `trie`).
-57    """
-58    if not key:
-59        return (0, trie)
-60
-61    current = trie
-62
-63    for char in key:
-64        if char not in current:
-65            return (0, current)
-66        current = current[char]
-67
-68    if 0 in current:
-69        return (2, current)
-70    return (1, current)
+            
37def in_trie(trie: t.Dict, key: key) -> t.Tuple[int, t.Dict]:
+38    """
+39    Checks whether a key is in a trie.
+40
+41    Examples:
+42        >>> in_trie(new_trie(["cat"]), "bob")
+43        (0, {'c': {'a': {'t': {0: True}}}})
+44
+45        >>> in_trie(new_trie(["cat"]), "ca")
+46        (1, {'t': {0: True}})
+47
+48        >>> in_trie(new_trie(["cat"]), "cat")
+49        (2, {0: True})
+50
+51    Args:
+52        trie: the trie to be searched.
+53        key: the target key.
+54
+55    Returns:
+56        A pair `(value, subtrie)`, where `subtrie` is the sub-trie we get at the point where the search stops, and `value`
+57        is either 0 (search was unsuccessful), 1 (`value` is a prefix of a keyword in `trie`) or 2 (`key is in `trie`).
+58    """
+59    if not key:
+60        return (0, trie)
+61
+62    current = trie
+63
+64    for char in key:
+65        if char not in current:
+66            return (0, current)
+67        current = current[char]
+68
+69    if 0 in current:
+70        return (2, current)
+71    return (1, current)
 

 
 
-- 
cgit v1.2.3