Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

red-black nodes should carry length info #23

Open
tarakc02 opened this issue Aug 15, 2023 · 1 comment
Open

red-black nodes should carry length info #23

tarakc02 opened this issue Aug 15, 2023 · 1 comment

Comments

@tarakc02
Copy link
Owner

i had removed these to make the dicts/sets more compact, but it would be nice to support efficiently calculating ranks/quantiles as well as iterating from them (e.g. iterate values between 25th and 75th quantile).

could this be set up to be decided at runtime? maybe e.g. by making two different nonempty types, one with length and one without, and specialize the NE constructor based on the types of left and right. updating length is just 1+length(left)+length(right)

@tarakc02
Copy link
Owner Author

this turned out to be a very simple fix (just had to change two lines of code), but for a small key type (Int64), the size of the whole data structure will grow to 133% of previous size, for a feature that may or may not be useful. the main immediate use for length info would be to implement amount for #11 , but maybe that can be accomplished by storing length of the entire container (e.g. as an added field in RBDict/RBSet), which doesn't cause the same overhead.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant