[Roadnav-devel] Thoughts about adding external dependencies

[Dustin S. <du...@vi...>]

Hey,

So after a bit of a hiatus, I'm working a bit more on improving 
libroadnav (though, my time is still currently somewhat limited). Right 
now, I'm starting work on recreating the backend for Roadnav to scale a 
bit better, and be OpenStreetMap focused. Along the way, I've come 
across some dependencies that I'm currently thinking about adding to 
Roadnav, and I welcome any thoughts about this. I have listed the 
libraries in order of importance.

bzip2 (important):

OSM distributes the planet.osm (for those not familiar, its a collection 
of all OSM data) file in a 4GB bz2 file. While I plan to support 
primarily the live API, it seems like it would be good to support 
reading directly from the planet file if the user really wants to spend 
a few days compiling maps from it. wxWidgets currently does not support 
bzip files.

expat (important):

expat is used by wxWidgets internally to parse XML, and more importantly 
it can parse XML files in a streaming fashion, which will be 
particularly important for the planet.osm file... given its 90GB 
uncompressed. The current OSM data importer uses a custom set of 
operations to parse the XML file, but it seems to be that it could be a 
good idea (and possibly less error-prone) to use expat to do this instead.

STXXL (thinking about this):

STXXL is an STL-like library designed/optimized for very large data sets 
using external memory. There are a number of features from this library 
that could potentially be really useful (the vector and map containers 
in particular), depending on the performance of this library for smaller 
data sets (hundreds of thousands to millions, which is the range Roadnav 
uses).  It has also occurred to me that adapting the map implementation 
(its a btree, which is similar to an rtree) to use an R tree index (such 
as the one I've implemented) could be a *huge* win, and save lots of 
time. I've actually contacted the author about this idea to see if he 
would be willing to accept some patches to that effect.

Boost (semi-thinking about this, still a long way off):

Currently roadnav has an implementation of routing algorithms 
(Dijkstra's algorithm, in particular). However, one thing that is 
particularly attractive to me is moving this to use the Boost Graph 
Library, which not only has implementations for Dijkstra's, but other 
routing-related algorithms too (which may help improve performance). 
Interestingly enough, there are also some graph-related items in STXXL 
also, so this may not be necessary. Of course, this is not really a 
priority yet, but I figured that I would throw it out there...

I realize that for Linux versions of roadnav, the dependencies aren't 
quite as big of an issue, whereas for windows it can get trickier and so 
we would probably have to import these external dependencies into the 
project in their own set of directories or something. If anyone is 
interested, I'm doing work on the backend in 
libroadnav/branches/TestConcepts/Backend

As I said, let me know your thoughts about any of this. For the most 
part, I haven't actually made up my mind about it yet, just trying to 
consider good ways to do this stuff. Thanks!

Dustin

-- 
Innovation is just a problem away