bert hubert 🇺🇦🇪🇺🇺🇦Does anyone know of a performant, well-tested C++ implementation of an interval tree that you can attach values to? I know of: https://github.com/ekg/intervaltree which has bugs & is very slow, https://doc.cgal.org/latest/Interval_skip_list/index.html#Chapter_Interval_Skip_List which looks amazing but appears to bring a lot of baggage & I don't know about performance and https://www.boost.org/doc/libs/latest/libs/icl/doc/html/boost/icl/interval_map.html which I hear is slow. Help?
So DNA (where these trees are used a lot) has a local Fabrice Bellard-equivalent, and he (Heng Li) wrote https://github.com/lh3/cgranges which appears to be excellent. Will give it a spin! Although I'm using this for IPv6 addresses and not DNA loci. Let's hope it works!
Can confirm, the code intended to work on 32 bit offsets within chromosomes works without altering on 128 bit IPv6 addresses. Well done DNA people! Thanks to @ekg for pointing me in the right direction.
Chris Adams@bert_hubert are you allowed to talk about what you’re using the software before? I’ve never heard of anyone doing software designed for bioinformatics on network addresses like that before.
@mrchrisadams sure, this is all open source! I use this to rapidly use a list of 500k IP address ranges (IPv4 and IPv6) to their presumed country origin. For me it is not strange to mix these worlds since I do work in both.
@bert_hubert would you mind pointing me to the repository you’re working in?
I have a few detailed questions that immediately come up because we are doing likely to be doing some related work in the Netherlands this year as well.
I think it might be good to compare notes, but they may be answered by looking at the repo as well - and if that means you have more time to keep writing about EU cloud market dynamics that seems a win in my book - it’s v helpful to have out there.
AkaSci 🛰️@bert_hubert
You mention IPv6. Are you using this for longest prefix lookup?
Can the intervals overlap partially or do they only overlap fully?
You mention IPv6. Are you using this for longest prefix lookup?
Can the intervals overlap partially or do they only overlap fully?
@AkaSci sadly the IP ranges *could* overlap, and are not on neat bit boundaries. This is not longest prefix lookup. I need to map IP address to countries using (for example) the Maxmind CSV https://db-ip.com/db/download/ip-to-country-lite - but good news, it all works now!
cubeos@bert_hubert My goto library for efficient and well tested c++ algorithms is leda. It used to be commercial but now seems to be free, see https://leda.uni-trier.de/
@cubeos That looks promising, thank you! Will check it out.
@bert_hubert Take a look at the interval_set datatype, that might just do what you need.
@cubeos it does look promising but (understandably) it is hardcoded on double precision intervals, and I need more flexibility than that. Thanks for the tip though, LEDA could be useful for many other things!
Mike Spooner@cubeos @bert_hubert "goto library" 🤔