ripytide / nodit Goto Github PK

It's possible to access the functions from https://github.com/ripytide/discrete_range_map/blob/408f4e020ebdb984b752b00fc1b8a9ef604909f7/src/test_ranges.rs#L20
They also show up in the documentation. Ideally, those would either

• be internal and inaccessible
• or be generic, with maybe slightly longer names and publicly exposed

It is often necessary when using a RangeMap to want to merge ranges that touch but only if the associated values are equal so as to maintain accuracy unlike insert_merge_touching() which will merge and so also overwrite the values regardless of equality.

I believe this is also the last requirement for this library to also become a Full superset (kinda) of the jeffparsons/rangemap library as that libraries insert() method also allows this functionality.

I propose we call the method insert_merge_touching_if_values_equal() for as it's the best name I can think of which follows our predefined naming conventions and philosophies.

All over this library the words Range and Interval are used which is a bit inconsistent in my opinion and I would like to pick one and stick to it. Now on the one hand Wikipedia calls them Intervals, but on the other the crate is already called discrete_range_map which would suggest Range and so wouldn't require changing the crate name, again.

I think I'll sleep on this issue for a while.

This makes it more consistent with the other insert_* methods, since overwrite also inserts into the collection, albeit more forcefully.

I was looking at the https://docs.rs/discrete_range_map/latest/discrete_range_map/discrete_range_map/struct.DiscreteRangeMap.html#method.insert_merge_overlapping functions, and realised that I had no clue what merge exactly means. Does it merge stuff if it's equal? Does it do more than that? Is there a way of customising it, or would that be nonsense?

Ideally, that documentation would link to
https://docs.rs/discrete_range_map/latest/discrete_range_map/index.html#merging
and that section would be slightly expanded.

As suggested by @mfigurski80 the use of the word platonic causes some degree of confusion or astonishment as to the function of the function. In alignment with the theory of the least astonishment and KISS it would be better to switch to the word strict which is less esoteric and more accurate for the given functionality.

After attempting #21 and failing, I decided several of my approaches in the v0.1.1 release were misguided, not assuming Copy on K and I made the implementations so so so painful despite the fact all the K's and I's I ever plan on using this data structure with will be Copy.

Secondly and more specifically to #21, is that it still doesn't address the OrdWrapper bodge which also greatly complicates the implementations as you have to encode the orderings into the type at compile time which is a right pain when you require runtime dependent comparisons.

So after taking inspiration from eggyal/copse I forked it and created ripytide/btree_monstrousity. I modified every single function to take a Closure that decides all the Orderings at runtime! And hence the keys you store no longer have to be Ord!!

This has made the code much simpler and more elegant than before. I have also removed many of the "helper-style" functions such as cut_same, append_platonic etc.. since they are all easily achievable on the user side and it's a lot of work to maintain so many extra functions.

It'd be lovely to be able to to turn one of the rather unwieldy Rust RangeInclusives into a InclusiveInterval and back.

I'm more than happy to create a PR for this if desired.

Since the documentation wasn't that clear it may be worth explaining the trimming effect and adding an untrimmed method so that all behavior is obvious and available.

As a part of #37 and #39 it occurs to me that the name of the crate would no longer be accurate.

As a new name I propose discrete_range_map to match the DiscreteRangeMap type.

This crate requires InclusiveRanges to be valid when passing them to any of the functions, otherwise a panic will happen

	/// Is the range is valid, which according to this crate means `start()`
	/// <= `end()`
	fn is_valid(&self) -> bool
	where
		I: PointType,
	{
		self.start() <= self.end()
	}

Would it make sense to verify that in the constructor of InclusiveInterval? Then the implementation of InclusiveRange for InclusiveInterval could have is_valid be a no-op, and errors might be caught slightly sooner.

Since unlike the upstream BTreeMap we have multiple ways in which to insert a RangeBounds into the structure it follows that we have multiple append_* functions as all an append function consists of is repeated insertion. See #8 too.

There is no reason why it shouldn't apart from implementation difficulties.

Since unlike most upstream collections we have multiple insert functions, this makes conversion from iterators or RangeBounds ambiguous as we can insert each new RangeBounds multiple ways as the non-overlapping invariant we normally impose may not apply.

Due to this I propose removing the current implementations of these traits that currently use the most conservative insert_strict.

I think this decision pits two notable philosophies against one another ease-of-use vs stability-of-use. And much like rust itself's own design philosophy, I choose stability-of-use.

Worse ease-of-use:

• Annoyance when users can't convert their other collections into RangeBounds* types as they normally expect to. (using .collect() or .into() and other similar methods.

Better stability-of-use:

• Less unintentional bugs as conversion forces a user to find and read the appropriate documentation about the different insertion behaviour before being able to write what they really intend using the correct insert_* method or it's equivalent append_* method.

There are many functions which may panic if given certain inputs (I'm pretty sure only InvalidRangeBounds currently), we should make this explicit where it is intended behaviour, such as with InvalidRangeBounds. See upstreams BTreeMaps documentation for an example here.

Seemingly on a never-ending path of enlightenment for my faulty base assumptions with this library. Next up is that Finite-ness is unnecessary to represent explicitly within the library since all finite discrete types have a MAX and MIN values anyway.

And in fact the specific way I can represent Infinite types with an enum to make code nicer is as follows:

enum PossiblyInfinite {
    //start, end
    Finite(BaseType, BaseType),
    //start
    Infinite(BaseType),
}

impl RangeBounds<BaseType> for PossiblyInfinite {
..... blah blah 
Infinite(start).end_bound() = Bound::Included(BaseType::MAX)!!!!

There is a custom impl of InclusiveInterval. And the traits are not impled for core::ops::range. The syntax is really ugly. Why ?

Again taking inspiration from jeffparsons/rangemap#67 it looks to me like a more friendly experience for the developer if we would include a link to the docs' section on Invalid RangeBounds in the panic messages.

I think it'd be worthwhile to document that this crate requires a nightly Rust toolchain for the time being

Migrate GitHub release notes to a KeepAChangelog and automate releases somehow using:

• https://github.com/crate-ci/cargo-release
• https://github.com/taiki-e/create-gh-release-action

And while at it might as well add a CI step for clippy/rustfmt/testing stuffs.

The current implementation is very much a bodge of using the range method largely in a unintended fashion.

Instead I propose we switch to using btree_cursors, which is a new API that was proposed with the express intention of improving the implementations of interval collections such as this ones this project provides.

The btree_cursors feature is currently a nightly unstable feature so this would more concretely lock us onto the nightly version of rust than the currently used, but more work-a-roundable features we are using at the moment.

Overall I think this will greatly improve the simplicity of the code, and will also greatly improve the performance due to using more fit-for-purpose methods on the raw BTreeMap.

Related btree_cursors Issues and PRs
Tracking Issue: rust-lang/rust#107540
Proposal: rust-lang/libs-team#141
Implementation: rust-lang/rust#105641
Related Entry Proposal: rust-lang/libs-team#73

Following from jeffparsons/rangemap#78

It would be a nice piece of extra information to have.

Would it be possible to implement DiscreteFinite for usize?

https://github.com/ripytide/discrete_range_map/blob/main/src/discrete_finite.rs

I have a use case where I'm using array indices as the keys for a range map. The rough idea is that most of the time, the array has mostly the same values, so storing it as a range map is far more efficient (and makes a few algorithms easier to implement). Hence this request.

I would have expected insert_overwrite to return an iterator over the old items, since most other insert methods return the old values or something.

Judging from the source code, it'd be a quick tweak.
https://docs.rs/discrete_range_map/latest/src/discrete_range_map/discrete_range_map.rs.html#1232-1240

This is a collection issue to list the things necessary to switch the main behavior to Discrete over Continuous as decided in #24
Things to do:

• Change NiceRange to DiscreteRange to also enforce the unstable Step trait
• Remake TryFromBounds with DiscreteBounds
• Redo touching() is_valid() and similar logic functions with DiscreteBounds
• Switch all the trait bounds to DiscreteRange and review the implementations and return types.
• Fix any tests that break due to the new behavior
• Update docs anywhere appropriate and add a new section on the main lib/readme page to discuss Continuous-ness vs Discrete-ness and that this library is Discrete since nearly all use-cases prefer Discrete.

This is due to the function using BTreeMap's drain_filter() since BTreeMap doesn't yet have the more relevant drain_range() yet.

As a bodge fix we can use the new btree_cursors feature to implement a sort-of faster version. I measure a 4-10x improvement in my library, hence I am willing to switch to this bodge.

It follows from sister project rangemap's issue jeffparsons/rangemap#62 that this projects philosophy, more fine-grained interval manipulation, allows us to add the iter_mut and overlapping_mut methods quite easily. Therefore we should do just that.

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.

This method is nearly identical to overlapping except it trims the returned RangeBounds so they only reside within the given search_range_bounds.

Example:

set = [1..8, 8..10, 14..20]

set.trimmed_overlapping(&(4..16)).collect() == [4..8, 8..10, 14..16]

Since this function has the same issues as cut() and gaps() it could also do with an associated trimmed_overlapping_same() to keep things consistent with cut_same and gaps_same()

The word coalesce is much more esoteric in the English language than merge and there is not any meaningful functional semantic difference in our use-case therefore in KISS principle we should switch to using the word merge.

These operations underpin the core logic of the collections, but they are not limited to it.

Such functionality such as they provide may also be useful to others working with RangeBounds hence it would be nice if we could document and expose them.

Ideally, such core RangeBounds logic and operations would be centralized, perhaps in it's own crate so users may choose to use the operations even if they don't want to use the RangeBounds* collections. But this seems like an over-complication at this stage of time. Instead I will hold this idea in reserve.