Faster implementation for IntervalMap

[AliceRixte]

Hi there !

As mentionned in #50, the current complexity for insert is $O(n)$. This is inevitable, as insertion at the interval $]-\infty, \infty[$ needs the values at every single key.

However, for a small interval, say a singleton, the current implementation is still linear, and this is a problem. It would be great if it was logarithmic.

A faster implementation would be the following type :

newtype IntervalMap r a =
  IntervalMap (Maybe a, Map (r, Boundary) (Maybe a))

The idea being that we store the values "between" the keys :

• at each key of the map, we store the value of the map until the next key.
• if there is no next key, then this is the value for the interval of the form $(maxk, +\infty[$, with maxk the maximum key of the map
• we need to store the value for the first interval of the form $]-\infty, mink)$ separately, with minkthe minimum key of the map

For instance, the following interval map

[ (-inf <..< 0  , a)
, (1 <=..<= 1   , b)
, (2 <=..< 3    , c)
, (4 <..< 5     , d)
, (5 <=..< inf  , e)
]

would be implemented by (suppose that Closed < Open, which is the opposite, but we can use a newtype)

( Just a
, Map.fromList
  [ ((0, Closed), Nothing)
  , ((1, Closed), Just b )
  , ((1, Open  ), Nothing)
  , ((2, Closed), Just c )
  , ((3, Closed), Nothing)
  , ((4, Open  ), Just d )
  , ((5, Closed), Just e )
])

This way, the insertion of a singleton interval will be logarithmic, which is not the case with the current implementation.

This also suggests that we could implement total interval maps, that always contain a value. This is something I will need to implement for one of my projects :

newtype TotalMap r a =
  TotalMap (a, Map (r, Boundary) a)

then IntervalMap could be defined as a newtype wrapper for TotalMap r (Maybe a) .

What are your thoughts on this ?

Cheers !

[Bodigrim]

Is it somewhat similar to what I tried to do in interval-set-super-new branch, extended to maps? (BTW I ran out of time there, but if you have a capacity to finish up insert and delete I'd be most grateful)

[AliceRixte]

Yes we are definitely playing with similar ideas. To lift your version of IntervalSet to IntervalMap, we could store pairs (a,TabStop), and, just like for what I propose, one would need to store the value for the first interval separately.

To implement IntervalSet with my approach, if we imagine that TotalMap is merging the intervals with the same values (we probably should not, this is just for explaining), we could simply use a newtype wrapper

newtype IntervalSet r  =
  UnsafeIntervalSet (TotalMap r Bool)

Then inserting or deleting an interval amounts to setting an interval to True or to False.

[AliceRixte]

Which approach is better between yours and mine ?

• Your approach is better in memory, it definitely saves a few bytes per entry.
• Implementation of my approach might be more straightworward, as deleting or inserting mainly consists of using restrictMapKeysToInterval and withoutMapKeysFromInterval we added a month ago.

I'll play around both ideas and benchmark the result to see which performs better.

In any case, what I really need is a total interval map, so I will mainly focus on this first. I think that finishing your implementation will come "for free" after that so I will definitely do it.