Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/bleach/_vendor/html5lib/_trie/py.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 from __future__ import absolute_import, division, unicode_literals | |
2 from six import text_type | |
3 | |
4 from bisect import bisect_left | |
5 | |
6 from ._base import Trie as ABCTrie | |
7 | |
8 | |
9 class Trie(ABCTrie): | |
10 def __init__(self, data): | |
11 if not all(isinstance(x, text_type) for x in data.keys()): | |
12 raise TypeError("All keys must be strings") | |
13 | |
14 self._data = data | |
15 self._keys = sorted(data.keys()) | |
16 self._cachestr = "" | |
17 self._cachepoints = (0, len(data)) | |
18 | |
19 def __contains__(self, key): | |
20 return key in self._data | |
21 | |
22 def __len__(self): | |
23 return len(self._data) | |
24 | |
25 def __iter__(self): | |
26 return iter(self._data) | |
27 | |
28 def __getitem__(self, key): | |
29 return self._data[key] | |
30 | |
31 def keys(self, prefix=None): | |
32 if prefix is None or prefix == "" or not self._keys: | |
33 return set(self._keys) | |
34 | |
35 if prefix.startswith(self._cachestr): | |
36 lo, hi = self._cachepoints | |
37 start = i = bisect_left(self._keys, prefix, lo, hi) | |
38 else: | |
39 start = i = bisect_left(self._keys, prefix) | |
40 | |
41 keys = set() | |
42 if start == len(self._keys): | |
43 return keys | |
44 | |
45 while self._keys[i].startswith(prefix): | |
46 keys.add(self._keys[i]) | |
47 i += 1 | |
48 | |
49 self._cachestr = prefix | |
50 self._cachepoints = (start, i) | |
51 | |
52 return keys | |
53 | |
54 def has_keys_with_prefix(self, prefix): | |
55 if prefix in self._data: | |
56 return True | |
57 | |
58 if prefix.startswith(self._cachestr): | |
59 lo, hi = self._cachepoints | |
60 i = bisect_left(self._keys, prefix, lo, hi) | |
61 else: | |
62 i = bisect_left(self._keys, prefix) | |
63 | |
64 if i == len(self._keys): | |
65 return False | |
66 | |
67 return self._keys[i].startswith(prefix) |