On Mon, Jul 8, 2019 at 10:09 PM Pavel Stehule <pavel.steh...@gmail.com> wrote: > po 8. 7. 2019 v 18:47 odesÃlatel Paul A Jungwirth > <p...@illuminatedcomputing.com> napsal: > I am not against a multirange type, but I miss a explanation why you > introduce new kind of types and don't use just array of ranges.
Hi Pavel, I'm sorry, and thanks for your feedback! I had a response to your earlier email but it was stuck in my Drafts folder. I do think a multirange would have enough new functionality to be worth doing. I was pretty reluctant to take it on at first but the idea is growing on me, and it does seem to offer a more sensible interface. A lot of the value would come from range and multirange operators, which we can't do with just arrays (I think). Having a range get merged correctly when you add it would be very helpful. Also it would be nice to have a data type that enforces a valid structure, since not all range arrays are valid multiranges. My reply yesterday to Jeff expands on this with all the functions/operators/etc we could offer. Your other email also asked: > I don't think - working with large arrays is slow, due often cache miss. >I understand so it depends on data, but in this area, I can imagine >significant memory reduction based on running processing. > > array builder doesn't respect work_men, and I think so any different way is > safer. I'm still thinking about this one. I tried to work out how I'd implement a tree-based sorted list of ranges so that I can quickly insert/remove ranges. It is very complicated, and I started to feel like I was just re-implementing GiST but in memory. I did find the interval_set class from Boost's boost_icl library which could offer some guidance. But for now I want to press forward with a sort-then-iterate implementation and consider a different implementation later. If you have any guidance I would appreciate it! I especially want something that is O(n log n) to insert n ranges. Other suggestions here are very welcome! :-) Regards, Paul
