Looking for gaps

[WarDaft]

I've given this a fair amount of thought, and so far I haven't been able to come up with any clean, fast, solutions (though I have come up with fast solutions).

I'm indexing a group of items, each of which has a number of intervals associated with it. I definitely need to store the intervals associated with each item, and I need to index over this. I also however, need to find items which do not have any overlaps with a specified interval.

So far, the only reasonable solution I've been able to think of is also calculating and storing open intervals and indexing over that as well. This is a fast solution, but it is essentially storing the exact same data twice.


Also, the indexing library I have to work with does not support anything equivalent to set difference operations.
This is for a side project, not homework or anything. My homework is currently at the intro to pointers level.

[Xanthir]

I assume this is for a calendaring app or something similar, where your items are events that cover certain intervals of time?

You say that your indexing library doesn't support set operations. I'm confused as to why your indexing library has to come into this at all. The obvious/clean way would be to use the index to find the set of items that do overlap a given interval, then just subtract that from the set of all items. Do you have too many items for this to be feasible or something?

If so, then your current solution of storing the open intervals as well seems to be pretty reasonable. Denormalizing your data is often required when you need to speed things up.

[WarDaft]

It would be for a calendar scheduling functionality yes. It would be server side, so it has to be efficient for returning small chunks of the whole result. If the indexing aspect supported set difference (it supports only unions and intersections =/), then that would be the clean solution I think, but it doesn't.

[Xanthir]

I still don't understand quite why you're mentioning the details that you do; they seem irrelevant to the problem. On the server-side, take the list of all items, and use your index to find a list of the items that overlap your interval. Subtract the two yourself - it should be a linear-time operation in the number of items. What you're left with is the information you want.

You don't need the database search to be able to do the difference for you.