4 ms·

Finding overlapping intervals and querying on those ranges. E.g. answering this question: on January 2nd, what payment schedules apply (more than one because di

Finding overlapping intervals and querying on those ranges. E.g. answering this question: on January 2nd, what payment schedules apply (more than one because different countries pay out differently)? Or: if I add this schedule, does it overlap another one? If so, which ones? That's a date range based use case for this interval tree structure. Another team is doing something similar query-wise, but with integer based ranges. I forget what their use case is, but our data structure is exactly what they need, but we either need to use reflection (unacceptable) or copy and paste (also garbage) or code generation (bad) to accept and return the right types. This is trivial in Java, where I have a version of this written and used without complaint.

marcrosoft 10y ago
I could be totally off but, if all the intervals were integer based would this problem go away? If so (probably not), would that mean that the lack of generics in Go influence good design from the beginning? Edit: Thank you for the use case!
- Zach_the_Lizard 10y ago
  >I could be totally off but, if all the intervals were integer based would this problem go away? No. Even if you represent date ranges as pairs of integer timestamps in UTC (for consistency) you now need to do annoying and possibly bug prone casting and converting. Remember, code not written is bug free. Those tests won't write themselves. Also think of N dimensions; those come up often and are hard to handle with this input type. The moment someone needs a pair of GPS coordinates that are doubles you're SOL. Which incidentally is a common situation with interval trees: find things in a viewport, intersecting roads, etc. Even the tree itself is actually generic. You could build on a red black tree and using generics use an internal data type to order the tree with some extra book keeping and thus use the same underlying tree implementation for, say, an ordered set structure, interval trees, etc. You can do this all now with error prone casting. I don't know if you've done Java pre generics but it is a vastly more error prone world than post generics Java. Incidentally the lack of these other structures leads to lots of OrderedXYZTypeSet type code in our codebase that are generated to avoid cssting. With generics we'd not only have one implementation for all types, but we'd likely open source it since the broader Go community could use it and add additional useful types and functions. Go has very few built in data structures which exacerbates this problem. It at least partially has so few because the generics support in maps and slices etc. is basically a special cased hack since it's not baked into the language and is thus likely hard to maintain.
- HelloNurse 10y ago
  Intervals can only be "based" on ordered pairs of things with a total ordering and a finite computer representation, of which integers (trivially) and dates (only if represented with adequate constraints) are only two examples. If a generic implementation of interval trees is not possible, the programming language is (deliberately) simplified, for the sake of stupid users or stupid implementations. Note that this is a very low bar: in C interval extremes can be void* and their total ordering can be represented as a function pointer int (f)(void,void*), while in old Java the interval tree could refer to a suitable "Element" interface, leaving cumbersome adapters and downcasts to client code.

marcrosoft 10y ago

I could be totally off but, if all the intervals were integer based would this problem go away? If so (probably not), would that mean that the lack of generics in Go influence good design from the beginning? Edit: Thank you for the use case!

Zach_the_Lizard 10y ago
>I could be totally off but, if all the intervals were integer based would this problem go away? No. Even if you represent date ranges as pairs of integer timestamps in UTC (for consistency) you now need to do annoying and possibly bug prone casting and converting. Remember, code not written is bug free. Those tests won't write themselves. Also think of N dimensions; those come up often and are hard to handle with this input type. The moment someone needs a pair of GPS coordinates that are doubles you're SOL. Which incidentally is a common situation with interval trees: find things in a viewport, intersecting roads, etc. Even the tree itself is actually generic. You could build on a red black tree and using generics use an internal data type to order the tree with some extra book keeping and thus use the same underlying tree implementation for, say, an ordered set structure, interval trees, etc. You can do this all now with error prone casting. I don't know if you've done Java pre generics but it is a vastly more error prone world than post generics Java. Incidentally the lack of these other structures leads to lots of OrderedXYZTypeSet type code in our codebase that are generated to avoid cssting. With generics we'd not only have one implementation for all types, but we'd likely open source it since the broader Go community could use it and add additional useful types and functions. Go has very few built in data structures which exacerbates this problem. It at least partially has so few because the generics support in maps and slices etc. is basically a special cased hack since it's not baked into the language and is thus likely hard to maintain.
HelloNurse 10y ago
Intervals can only be "based" on ordered pairs of things with a total ordering and a finite computer representation, of which integers (trivially) and dates (only if represented with adequate constraints) are only two examples. If a generic implementation of interval trees is not possible, the programming language is (deliberately) simplified, for the sake of stupid users or stupid implementations. Note that this is a very low bar: in C interval extremes can be void* and their total ordering can be represented as a function pointer int (f)(void,void*), while in old Java the interval tree could refer to a suitable "Element" interface, leaving cumbersome adapters and downcasts to client code.