Re: [Boost-users] [BGL] combining kdtree-style operations

From: martin f krafft (madduck_at_[hidden])
Date: 2005-05-19 12:23:27

also sprach Douglas Gregor <doug.gregor_at_[hidden]> [2005.05.19.0511 +0200]:
> libkdtree could clearly be proposed as a Boost library with
> primarily cosmetic changes ("Boostifying" the code, as it were).
> If you would like to pursue this, I'd be glad to help guide you
> through the process.

Well, I would be honoured. I must warn you though that this process
could take months because I am completely overworked right now. If
you have no problem working over long periods on the same thing with
infrequent change bursts, I would be glad.

What would be the first step? The licence is currently artistic,
which is probably not a problem. I have no problem in changing that
either. Note that one other person has contributed to this licence,
and I have asked him about the licence issues. He is okay with the
artistic licence, so if that is compatible, there is no problem.

One thing I know for sure is the need for unit
tests/examples/regression tests (though I have to read up on what
exactly regression tests are...), but since I just finished reading
Kent Beck's TDD book, I am all too excited to add those when I have
another free moment (like in 2006 or so ;>).

Documentation is missing. Other than that, I cannot immediately tell
what I would have to do to boostify. Note that I have zero (!)
experience with portability; I have used GNU/Linux basically all my
life.

> graph, it doesn't strike me as being the right abstraction. Rather, I 
> think your central data structure will be something very like a KD tree 
> (although perhaps drawing a more pronounced distinction between 
> vertices and edges in the data structure). Then, you can give it a BGL 
> interface just by writing free functions that make the KD tree look 
> like a graph... vertices(), edges(), out_edges(), etc. If the data 

This *does* sound nice. The problem is that the edges in the KDTree
are not necessarily the edges in the graph (in fact, they are not
most of the time). Thus, in order to be able to answer out_edges(),
I would have to keep an edge list for each node -- the primary
reason I wanted to use the BGL in the first place so that I don't
have to worry about that.

> >  - would this library be a candidate for Boost and/or the BGL?
> >  I realise that it's way too STL-centric right now (I somehow
> >  got a kick out of using the same variable naming scheme as the
> >  SGI STL implementation, which was made by people with obvious
> >  psychiatric needs (</humour>).
> 
> Boost tends to use a similar naming scheme. I'll let you draw your
> own conclusions :)

Really? Here's a quote from the code:

        if (_S_left(__N))
          {
            _Link_type __l = _M_get_j_max(_S_left(__N), __j, __L+1);
            if (__cmp(__ret, __l))
              {
                __ret = __l;
              }
          }

I liked it at the time; it made me feel special and cool. Now
I regret using this crap.

Also, the leading underscores are a problem with gcc (reserved for
internal use), so they will have to go anyway.

Cheers,

-- 
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net_at_madduck
 
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: madduck.bogus_at_[hidden]
 
why didn't noah swat those two mosquitoes?