I don't know of one, nor did a quick search of Google or CPAN turn up one.
If you have a concrete problem to solve, my strongest piece of advice is to solve it without worrying about efficiency. What you should do is create a class for searching intervals, and implement it in the stupidest way possible - as an array of arrays that you grep through to find your intervals. Give this class a good API, and develop the rest of your program using it. Odds are that, inefficient as it is, performance will be fine.
Junior programmers often have an involuntary shudder when writing such deliberately inefficient code. Try to suppress that reaction. Yes, it is horribly inefficient. But writing "just enough to do the job" is an essential part of exploratory programming, and knowing how and when to do it is a very valuable skill. It is essential to use a good interface so that you can improve the code later if needed, but don't get sidetracked solving problems you don't have until you have them.
After you're finished your program if performance is a real issue, then you can write an efficient one. To do that I would suggest starting by reading about B-Trees in Perl, and then modify the B-Tree algorithm to add the maximum heights, resulting in an Augmented Tree implementation.
The final implementation should be very similar to the B-Tree code in that article with one additional attribute in your nodes, but figuring out the details is likely to be an "educational experience". A good set of tests will be very helpful in tracking down your likely mistakes. If you're happy with the result, I'd suggest contributing it to CPAN.
If your efficient solution is not efficient enough, then you can interface to an existing library in a lower level language.
Based on past experience I would be willing to bet money that you'll find that the naive and inefficient version is sufficient for your needs. |