punch function does not build.

[lailoken]

I was getting a compile error with:

 using TradeIntervalTree = lib_interval_tree::interval_tree<lib_interval_tree::interval<size_t, lib_interval_tree::right_open>>;
 TradeIntervalTree::interval_type missingRanges;
 std::vector<TradeIntervalTree::interval_type> coveredRanges;
 // ...
 for (auto const& covered : coveredRanges) missingRanges = missingRanges.punch(covered);

Possible fix:

@@ -1353,21 +1353,21 @@ namespace lib_interval_tree
 
 interval_tree result;
 auto i = std::begin(*this);
- if (ival.low() < i->interval()->low())
- result.insert({ival.low(), i->interval()->low()});
+ if (ival.low() < i->low())
+ result.insert({ival.low(), i->low()});
 
 for (auto e = end(); i != e; ++i)
 {
 auto next = i;
 ++next;
 if (next != e)
- result.insert({i->interval()->high(), next->interval()->low()});
+ result.insert({i->high(), next->low()});
 else
 break;
 }
 
- if (i != end() && i->interval()->high() < ival.high())
- result.insert({i->interval()->high(), ival.high()});
+ if (i != end() && i->high() < ival.high())
+ result.insert({i->high(), ival.high()});
 
 return result;
 }

[lailoken]

As an aside, I thought the punch worked the other way round (interval punches hole in tree), but it did not, and sadly the tree does not have a tree.erase(interval) method?

[5cript]

I will take a look as soon as I can, perhaps Europe/Berline TZ tomorrow, depending on whether or not I am getting sick right now or not -.-
Punch should remove all intervals in a range and replace them with the gaps between them. And slice where the punch interval edge is inside an interval of the tree.
A range erase should be simple to implement if it imposes the same deoverlapped requirement like punch, and if not, I dont know didnt spend a thought as of yet.

It apparently lacks unit tests or this would have been found immediately. So the fix will include some unit tests.

[lailoken]

Well, I've tried SEVERAL different IntervalTree implementations, and your's is by far the best.

As for the punch, I realized it did something totally diferent than I initally thought (not really sure what punch is needed for).
So I implemented my own locally, but I'm sure it is sub-optimal.

[5cript]

I am in the process of completely rewriting the punch function. It was written in a time where the library was not aware of all the different interval types.
And also trying to get it as performance optimal as practically doable (except that more meta programming could squeeze out more, but I dont want to run into the risk of not being able to maintain it anymore myself)

EDIT: This will take a bit longer

[5cript]

I split the erase range feature request off into another issue #51

[lailoken]

The punch function documentation confused me:

 Returns: A new interval_tree containing the gaps.

I was not sure what these gaps were, I initially thought they were gaps between the remaining intervals!
But instead they were the remaining intervals. Perhaps it's just me that would think that.
(Which is why I thought it was named punch() and not erase*() as I initially expected. I now know it's because the tree is punching holes in the interval)

[5cript]

The previous implementation was incorrect for the current interval capabilities of the library.
punch is supposed to take an interval and remove all the ranges from it that are within the given tree. Like a signal inversion, or a cookie cutter in a line of dough.

Redone with #53.

Will review and merge tomorrow, to give myself some time to have spontanious revelations of what I forgot to do or test (always happens)

[lailoken]

@5cript , I notice the images of the interval_tree punch function is broken in the README.

[5cript]

How so?

punch(-10,60)

open:
(0,5)(10,15)(20,25)(30,35)(40,45) => (-10,0)(5,10)(15,20)(25,30)(35,40)(45,60)

closed:
[0,5][10,15][20,25][30,35][40,45] => [-10,0][5,10][15,20][25,30][35,40][45,60]

closed_adjacent (including gaps)
[0,5][10,15][20,25][30,35][40,45] => [-10,-1] [0,5] [6,9] [10,15] [16,19] [20,25] [26,29] [30,35] [36,39] [40,45] [46,60]

unless thats undesired behavior. I dont use that function in my projects right now. I want to make closed behave like that too at first, but decided against it and let it behave like open intervals. Because technically if [a,b][c,d], where b=c both intervals contain the same edge. Maybe I need to have this behavior toggleable with an option? I was thinking about that, because maybe someone wants the overlap behavior of "closed_adjacent", but wants to use the punch like closed. I cant say because as I said, its probably unused right now. I know that because you were the first one to complain that it doesnt build.
Or did you mean something else entirely? (I think the RB tree properties are held up and the max value is correct, ordered traversal is also correct)