8 releases
0.2.0 | Jan 28, 2022 |
---|---|
0.1.6 | Jan 11, 2021 |
0.1.5 | Oct 11, 2020 |
0.1.3 | Sep 22, 2020 |
#1022 in Data structures
541 downloads per month
Used in 8 crates
(3 directly)
44KB
1K
SLoC
quickscope
Multi-layer HashMap
and HashSet
implementations for performant representation of variable scopes.
Installation
Please use cargo-edit to always add the latest version of this library:
cargo add quickscope
Purpose
This crate contains two data structures, ScopeMap
and ScopeSet
, for representing variable scopes and, in the case of ScopeMap
, associated variable values. Access operations are such that variables in higher (i.e. more specific) scopes override variables in lower (i.e. more general) scopes.
Rationale (i.e. "why another one of these?")
I know I'm not the first one to do this! There are other, equally usable crates for the same purpose (see: hash-chain, chainmap, chain-map), but their implementations are such that lookups are O(n) worst-case in relation to layer count. I found that this didn't suit my needs.
This crate is optimized so that lookups are O(1) on average in relation to layer count. The trade-off is that popping layers is an O(n) operation in relation to the number of keys stored in the removed layer. I think this is an acceptable compromise in use cases requiring fast lookups across a large number of layers.
Example
let mut vars = ScopeMap::new();
// Define two variables in main scope
vars.define("a", 1);
vars.define("b", 2);
// Add a child scope
vars.push_layer();
// Override value of `a`
vars.define("a", 3);
assert_eq!(Some(&3), vars.get("a"));
assert_eq!(Some(&2), vars.get("b"));
// Remove child scope
vars.pop_layer();
// Value of `a` is no longer overridden
assert_eq!(Some(&1), vars.get("a"));
Why is it missing X feature from the regular HashMap/HashSet?
ScopeMap
and ScopeSet
are optimized for representing variable scopes. As such, they are missing many of the typical methods found in more general-purpose HashMap/HashSet implementations. If there's a feature that you feel should be added, feel free to submit a PR or post an issue about it.
License
This library is distributed under the MIT License. See LICENSE for details.
Dependencies
~1MB
~18K SLoC