|0.2.0||Jan 28, 2022|
|0.1.6||Jan 11, 2021|
|0.1.5||Oct 11, 2020|
|0.1.3||Sep 22, 2020|
#893 in Data structures
169 downloads per month
Used in 3 crates (2 directly)
HashSet implementations for performant representation of variable scopes.
Please use cargo-edit to always add the latest version of this library:
cargo add quickscope
This crate contains two data structures,
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.
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?
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.
This library is distributed under the MIT License. See LICENSE for details.