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

Add a DiscreteRangeMap + Set #24

Closed
ripytide opened this issue Apr 6, 2023 · 3 comments
Closed

Add a DiscreteRangeMap + Set #24

ripytide opened this issue Apr 6, 2023 · 3 comments
Labels
enhancement New feature or request

Comments

@ripytide
Copy link
Owner

ripytide commented Apr 6, 2023

Unlike continuous mathematical intervals over the Real Domain, intervals stored in modern computers are most likely over Discrete Domains, which are characterized by having a partial function that identifies the previous/next number in the Domain. Something like:

trait Discrete {
    fn incremented(&self) -> Option<Self>;
    fn decremented(&self) -> Option<Self>;
}

Importantly, we can losslessy convert between Inclusive and Exclusive ranges! We also gain another Invalid RangeBounds condition! Here's some examples over the Integers Domain:

Conversions:
Excluded(4)-Included(6) => Included(5)-Excluded(7)
Unbounded-Excluded(-5) => Unbounded-Included(-4)

The New Invalid RangeBounds:
Excluded(3)-Excluded(3) => INVALID!
Excluded(x)-Excluded(x) => INVALID!

Due to these added abilities available to Discrete Domain RangeBounds, I think it would be really nice to create a DiscreteRange{Map,Set} wrapper type of RangeBounds{Map,Set} that deal exclusively with Discrete Ranges and so are aware of the extra Invalid RangeBounds condition to filter it upon output and panic on input etc.

@ripytide
Copy link
Owner Author

Also! The touching predicate is different also! Since in a Continuous Map Included(4)-Included(6) would NOT touch Included(7)-Included(10) since their exists the value 6.5 inbetween them, BUT in over the Discrete Integer Domain They WOULD touch since their is no value between 6 and 7!!!

Because of this we should probably rename RangeBounds{Map,Set} to ContinuousRange{Map,Set} to make this clear! That opens the door for a new DiscreteRange{Map,Set} to cater to the Discrete set of properties!

@ripytide
Copy link
Owner Author

ripytide commented Apr 19, 2023

In terms of implementation simplicity for the DiscreteRange datastructures, I think internally representing all bounds as either Unbounded or Included but NOT Excluded would make the implementation much simpler, this could be done quite easily with a helper trait (perhaps an extension to NiceRange) as follows:

enum DiscreteBound<I> {
    Included(I),
    Unbounded,
}

trait NiceDiscreteRange {
    fn start(&self) -> DiscreteBound<I>;
    fn end(&self) -> DiscreteBound<I>;
}

A blanket implementation for any Discrete RangeBounds type would then be trivial.

@ripytide ripytide added the enhancement New feature or request label Apr 19, 2023
@ripytide
Copy link
Owner Author

ripytide commented Apr 20, 2023

Upon further thought, It occurs to me that all my use cases for RangeMaps all prefer the Discrete versions over the Continuous versions. Upon this surprising enlightenment I think assuming Continuous-ness was a great mistake. Therefore I think the best course of action would be to Replace the current RangeBounds{Set,Map} behavior with the Discrete version RATHER than maintaining both versions alongside one-another.

Therefore I am closing this in favor of #37

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

No branches or pull requests

1 participant