Closed srhickma closed 4 years ago
Merging #184 into master will decrease coverage by
0.08%
. The diff coverage is93.89%
.
@@ Coverage Diff @@
## master #184 +/- ##
==========================================
- Coverage 95.11% 95.02% -0.09%
==========================================
Files 26 27 +1
Lines 3295 3478 +183
==========================================
+ Hits 3134 3305 +171
- Misses 161 173 +12
Impacted Files | Coverage Δ | |
---|---|---|
src/lib.rs | 88.7% <ø> (ø) |
:arrow_up: |
src/core/data/mod.rs | 100% <ø> (ø) |
:arrow_up: |
src/core/parse/mod.rs | 93.15% <ø> (ø) |
:arrow_up: |
src/core/spec/region.rs | 95.12% <100%> (ø) |
:arrow_up: |
src/core/fmt/pattern.rs | 97.59% <100%> (+0.03%) |
:arrow_up: |
src/core/lex/longest_match.rs | 97.43% <100%> (+0.06%) |
:arrow_up: |
src/core/spec/lang.rs | 100% <100%> (ø) |
:arrow_up: |
src/core/lex/mod.rs | 88.03% <69.56%> (-1.97%) |
:arrow_down: |
src/core/lex/ecdfa.rs | 96.56% <92%> (-1.01%) |
:arrow_down: |
src/core/data/interval.rs | 96.32% <96.32%> (ø) |
|
... and 3 more |
Continue to review full report at Codecov.
Legend - Click here to learn more
Δ = absolute <relative> (impact)
,ø = not affected
,? = missing data
Powered by Codecov. Last update 6e37fa9...64e2571. Read the comment docs.
This pr makes several changes:
Interval
type andIntervalMap
data structure, which can be used to map key-ranges to values, rather than single keys to values.IntervalMap
is implemented as a modified interval tree, which is internally implemented as an AVL tree.TransitionTrie
using an internalIntervalMap
. This ensures that extremely large ranges can be stored without impacting performance. For example, in the previous implementation a range of 1000 characters would result in 1000 hashmap entries in the transition trie root node. Now, the entire range can be represented as a singleInterval
struct, and membership can be queried inO(log(n))
time (worst-case), wheren
is the number of ranges for a particular state.closes #155